Consider the following variation of the diet problem: There are n foods and m nu
ID: 3228227 • Letter: C
Question
Consider the following variation of the diet problem: There are n foods and m nutrients where one unit of food j contains a_ij greaterthanorequalto 0 units of nutrient i. Consider a parent with two children with minimal nutritional requirements b^1 Element R^m_greaterthanorequalto0 and b^2 Element R^m_greaterthanorequalto0 respectively. Finally, let c_j > 0 be the cost of one unit of food j. The parent has to buy food to satisfy the children's needs, at minimum cost. To avoid jealousy, there is the additional constraint that the amount to be spent for each child is the same. (a) Provide a standard form formulation of this problem. What are the dimensions of the constraint matrix? (b) If the Dantzig-Wolfe method is used to solve the problem in part a), construct the subproblems solved during a typical iteration of the master problem. (c) Suggest a direct approach for solving this problem based on the solution of two single-child diet problems.Explanation / Answer
(a) Say, the number of units of food j consumed by child A = qjA.
Therefore, the total cost of food for child A = n qjA*cj where j = 1 to n
Similarly, say the number of units of food consumed by child B = qjB.
Therefore, the total cost of food for child B = n qjB*cj where j = 1 to n
The total consumption of nutrient i by child A = n qjA*aij, where j = 1 to n
Therefore, the total consumption of all nutrients by child A = mn qjA*aij, where j = 1 to n, i = 1 to m
The total consumption of nutrient I by child B = m qjB*aij, where j = 1 to m
Therefore, the total consumption of all nutrients by child B = mn qjB*aij, where j = 1 to n, i = 1 to m
Therefore the problem can be stated as follows:
Minimize:
n qjA*cj and n qjB*cj
subject to the following constraints:
mn qjA*aij b1
mn qjB*aij b2
n qjA*cj = n qjB*cj (Jealousy constraint)
The dimensions of the constraint matrix should be (n+2) * mn.
(b) To construct a subproblem, we will consider a proposal that b2 = 0. If b2 = 0, then qjB can be 0 for all j. Therefore, the subproblem reduces to:
Minimize:
n qjA*cj
subject to the following constraints:
mn qjA*aij b1
(c) This problem can be looked upon as two separate single child diet problems if we consider the nutritional requirements for the two children separately. As an example, the problem for the first child will be:
Minimize:
n qjA*cj
subject to the following constraints:
mn qjA*aij b1
The jealousy constraint does not come into the picture as the cost can be replicating by replicating the quantities of the different foods.