An Icelandic horse farmer would like to supply her animals with sufficient vitamins A, B, C and D. Two types of feed, Isi1 and Isi2, are available for this purpose. The prices of both types of feed (in € per 100 g), the vitamins they contain (in mg per 100 g of feed) and the minimum requirement of vitamins per Icelandic horse (in mg per day) are given in the following table. A B C D costs Isi1 6 7 6 3 1.50 Isi2 1 4 10 9 1.00 minimum requirement per horse 22 71 120 72 How must the breeder compose her feed from the two different feed types in order to keep the financial expenditure for this as low as possible and at the same time cover the vitamin requirements of the Icelandic horses? It should be noted that an Icelandic horse may not receive more than 2 kg feed per day. (a) Set up the optimisation problem (objective function/target, constraints, non-negativity constraints). (b) Draw the feasible set and determine the vertices. (c) Determine graphically the optimal feed mixture and provide the optimal costs for the feed per Icelandic horse. Describe what you are doing. 2 Next, we want to solve the minimisation problem with the simplex algorithm. However, the standard simplex algorithm, as we learned in the lecture, is not applicable here. It is only suitable for optimisation problems of the form z = c T x −→ max . s.t. Ax ≤ b x ≥ 0 To solve our minimisation problem, we follow the procedure below. (d) Transform the minimisation problem into the form z = c T x −→ min . s.t. Ax ≥ b x ≥ 0 Hint: How can you transform an inequality whose inequality sign is „the wrong way round“? (e) Set up the matrix M = A b c T 0 ! and determine MT . We now interpret this matrix as MT = A˜ b˜ ˜cT 0 ! and thus obtain the following (dual) maximisation problem: z˜ = ˜cT y −→ max . s.t. Ay˜ ≤ b˜ y ≥ 0 The solution to this maximisation problem has the same optimal objective function value as the original minimisation problem: z˜max = zmin . (f) Set up the (dual) maximisation problem. (g) Calculate the optimal solution using the simplex algorithm from the lecture. Compare with your graphically found solution. Note: You will find the optimal feed amount of Isi1 and Isi2 at the end of the algorithm in the column of the slack variables or in the row of the objective function (each with a negative sign).