Pavel would like to buy a number of items at the grocery store and is trying to decide how much of each item to buy. Each item is pre-packaged. The maximum number of packages n; of each item i that Pavel would like to buy, and the weight W; of each package is listed below: 1 1 Item Flour Milk Apples Oil Onions (j) 2 3 4 5 Maximum no. of packages (n;) 2 4 3 2 Weight per package (w; kg) 1.5 2 1.3 3 2.2 Pavel has four bags, each of which can safely hold up to 4 kg of goods. Pavel would like to determine the largest number of packages he can buy and safely carry home in the bags he has, without opening any of the packages. (a) Formulate Pavel's problem as an IP, using variables to denote how many packages of each item he can safely pack in each of the four bags. (b) Consider the LP relaxation (P) obtained by removing the integrality constraints in the IP obtained in Part (a). State the dual LP (D) of the LP (P) that you get by following the same steps as in Question 2(b). State it in terms of n; and w; rather than the numbers given in the table. You need not show your work for this part. (c) Starting with a specific IP formulation and solving the resulting dual LP (D), we get that the optimum is 9.5. Taking this as a given, conclude that the optimum of the IP is at most 9. (d) Find, by inspection, a set of 9 packages that Pavel can buy and carry home safely, and state how he can pack them in his bags. Pavel would like to buy a number of items at the grocery store and is trying to decide how much of each item to buy. Each item is pre-packaged. The maximum number of packages n; of each item i that Pavel would like to buy, and the weight W; of each package is listed below: 1 1 Item Flour Milk Apples Oil Onions (j) 2 3 4 5 Maximum no. of packages (n;) 2 4 3 2 Weight per package (w; kg) 1.5 2 1.3 3 2.2 Pavel has four bags, each of which can safely hold up to 4 kg of goods. Pavel would like to determine the largest number of packages he can buy and safely carry home in the bags he has, without opening any of the packages. (a) Formulate Pavel's problem as an IP, using variables to denote how many packages of each item he can safely pack in each of the four bags. (b) Consider the LP relaxation (P) obtained by removing the integrality constraints in the IP obtained in Part (a). State the dual LP (D) of the LP (P) that you get by following the same steps as in Question 2(b). State it in terms of n; and w; rather than the numbers given in the table. You need not show your work for this part. (c) Starting with a specific IP formulation and solving the resulting dual LP (D), we get that the optimum is 9.5. Taking this as a given, conclude that the optimum of the IP is at most 9. (d) Find, by inspection, a set of 9 packages that Pavel can buy and carry home safely, and state how he can pack them in his bags
