Question 5 Consider the problem of finding a minimum cost diet containing at least 70 units of protein and 90 units of carbohydrates. Four foods are available with the following nutritional content and costs. Food 1 2 3 4 Protein/kilo 2 3 4 5 Carbohydrate/kilo 5 4 3 2 Cost in /kilo 18 8 13 12 (a) Formulate the minimum cost diet problem as a linear programming problem. (b) Write down the dual of the problem you formulated in part (a), and solve it by drawing a 2-dimensional diagram. Find the corresponding solution to the primal problem. Use your solution to answer the following questions. (1) There are two foods that will not be used in any minimum cost solution, irrespective of the quantity of proteins or carbohydrates needed in a diet. Which ones? Why? (ii) Due to your new-found passion for body building, your protein requirement has doubled. How much does your daily food cost increase? (iii) It turns out that food 1 is "really good for you", so you should have at least one unit of it. By how much does the minimum cost of a diet increase due to this new constraint? (This is with respect to the original problem, not with the doubling of the protein requirement at point (ii).) (d) More generally, suppose you have n foods to choose from, j = 1,..., n, each with unit cost ej. and m nutrients, i = 1,...,m, that you need in your diet, each with minimum requirement bi Let aij be the content of nutrienti in one unit of food j. (0) Write down an LP to determine a minimum-cost diet satisfying the nutritional requirements. (1) Explain why there always exists a minimum cost diet that uses at most m foods