Chapter 23.2, Problem 9P

You manage a chemical company with 2 warehouses. The following quantities of Important Chemical A have arrived from an international supplier at 3 different ports: Chemical Available (L) Port 1 Port 2 Port 3 400 110 100 The following amounts of Important Chemical A are required at your warehouses: Warehouse 1 Warehouse 2 Chemical Required (L) 380 230 The cost in £ to ship 1L of chemical from each port to each warehouse is as follows: Warehouse 1 Warehouse 2 Port 1 £10 £45 Port 2 £20 £28 Port 3 £13 £11 (a) You want to know how to send these shipments as cheaply as possible. For- mulate this as a linear program (you do not need to formulate it in standard inequality form) indicating what each variable represents.

a) Suppose that we are carrying out the 1-phase simplex algorithm on a linear program in standard inequality form (with 3 variables and 4 constraints) and suppose that we have reached a point where we have obtained the following tableau. Apply one more pivot operation, indicating the highlighted row and column and the row operations you carry out. What can you conclude from your updated tableau? x1 12 23 81 82 83 S4 $1 -20 1 1 0 0 0 3 82 3 0 -2 0 1 2 0 6 12 1 1 -3 0 0 1 0 2 84 -3 0 2 0 0 -1 1 4 2 -2 0 11 0 0 -4 0 -8 b) Solve the following linear program using the 2-phase simplex algorithm. You should give the initial tableau and each further tableau produced during the execution of the algorithm. If the program has an optimal solution, give this solution and state its objective value. If it does not have an optimal solution, say why. maximize 21 - - 2x2 + x3 - 4x4 subject to 2x1+x22x3x4≥ 1, 5x1+x2-x3-4 -1, 2x1+x2-x3-342, 1, 2, 3, 4 ≥0.

Suppose we have a linear program in standard equation form maximize c'x subject to Ax=b, x≥ 0. and suppose u, v, and w are all optimal solutions to this linear program. (a) Prove that zu+v+w is an optimal solution. (b) If you try to adapt your proof from part (a) to prove that that u+v+w is an optimal solution, say exactly which part(s) of the proof go wrong. (c) If you try to adapt your proof from part (a) to prove that u+v-w is an optimal solution, say exactly which part(s) of the proof go wrong.