Linear Programming Exercises Week 1

Exercise 1 Consider the case of the Betta Machine Products Company described in the lecture notes. (a) Use a graphical method to obtain the new optimal solution when the selling price of product 2 changes to (i) 55 pounds or (ii) 54 pounds. (b) A third product is being considered which would take 8, 3, 2 minutes of casting, machinery, and assembly time per unit. The unit cost would be 20 pounds and the selling price 38 pounds. It is thought possible that Betta might be short of casting capability so there is the possibility of subcontracting some or all of the casting of product 3. For items cast at the sub-contractors the unit cost would be 25 pounds. Formulate, but do not try to solve, the enlarged problem. Exercise 2 Solve the following problems graphically. (a) maximise z = x1 + x2 subject to: x1 + 2x2 10 2x1 + x2 16 x1 + x2 3 x1 0, x2 0. (b) minimise z = x1 + 3x2 subject to: x1 + 2 x2 6 x1 x2 3 x1 0, x2 0. (c) Minimise 2x1 x2 subject to the constraints in (b).

Exercise 3 A factory makes 3 components, A, B and C using the same production process for each. A unit of A take 1 hr, a unit of B takes 0.75 hrs and a unit of C takes 0.5 hrs. In addition, C has to be hand nished, an activity taking 0.25 hrs per unit. Each week total production time (excluding hand nishing) must not exceed 300 hrs and hand nishing must not exceed 45 hrs. The components are nally assembled to make two nished products. One product consists of 1 unit of A and 1 unit of C selling for 30 pounds whilst the other consists of 2 units of B and 1 unit of C and sells for 45 pounds. At most 130 of the rst product and 100 of the second product can be sold each week. Formulate the problem of planning weekly production to maximise total proceeds as a linear programming problem in 2 variables and obtain the solution graphically. Exercise 4 The Claverton Police Force has the following minimum daily requirements for policemen on duty.
0.00 4.00 4.00 8.00 8.00 12.00 15 35 65 12.00 16.00 16.00 20.00 80 40 20.00 24.00 25

Each policeman comes on duty at 0.00, 4.00, 8.00, 12.00, 16.00 or 20.00 hrs and works for eight consecutive hours. Formulate the problem of nding the duty schedule that minimises the total number of policemen required. Assume that the same schedule is repeated day after day. Do not attempt to solve the problem.

Week 2

Exercise 5 Consider a linear programming problem given in standard form (S). That is to say, maximise z = c x subject to: Ax b x 0n where A Rmn , x Rn and b Rm . Write down the associated problem in canonical form (C). Prove that if (C) has an optimal solution then its restriction to Rn is also the optimal solution to (S). Conversely suppose that (S) has an optimal solution x Rn , then there exists an optimal solution to (C) whose restriction to Rn is x. Exercise 6 Put the following problem in canonical form and solve by determining all its basic solutions. Interpret graphically. maximise z = 3x1 + 2x2 subject to: x1 + x2 4 x1 + 2 x2 6 x1 , x2 0. Exercise 7 Prove that if the system Ax = b, x 0 has a feasible solution it has a basic feasible solution. Use a simplied version of the proof of the fundamental theorem.

Week 3

Exercise 8 A mining company produces 100 tons of red ore and 80 tons of black ore each week. These can be treated in dierent ways to produce three dierent alloys, Soft, Hard or Strong. To produce 1 ton of Soft alloy requires 5 tons of red ore and 3 tons of black. For the Hard alloy the requirements are 3 tons of red and 5 tons of black, whilst for the Strong alloy they are 5 tons of red and 5 tons of black. The prot per ton from selling the alloys (after allowing for production but not mining costs, which are regarded as xed) are 250, 300 and 400 for Soft, Hard and Strong respectively. Formulate the problem of deciding how much of each alloy to make each week as a L.P. problem and use the Simplex method to nd the optimal solution. Exercise 9 Prove that if for some basic solution and for some value l such that xl is not in the basis, there is an entry in the objective row ol > 0 and also all values ail 0, then the problem has no nite maximising solution. (See pages 3031 of lecture notes for notation as well as the example ending on p33 for a numerical example of such a phenomena). Exercise 10 Use the Simplex method to show that the following problem has no nite maximising solution. maximise z = x1 + 2x2 + x3 subject to: 3x1 + x2 4x3 4 x1 x2 x3 10 x1 2x2 + 6x3 9 x1 , x 2 , x 3 0 Find a particular solution with z > 1000.

Week 4

Exercise 11 Solve the following problem by the two phase method. maximise z = x1 + x2 2x3 + 2x4 subject to: x1 x2 x3 2x4 2 x1 + x2 + x4 8 x1 + 2 x2 x3 = 4 x1 , ..., x4 0. Exercise 12 A health food shop packages three types of snack foods; chewy, crunchy and nutty. These are made by mixing sunower seeds, rasins, and peanuts. The specications for each food being given in the following table. Mixture Chewy Crunchy Nutty Sunower seeds at least 60 % at most 20% Rasisns at least 60% Peanuts at most 25 % at least 60% Retail price/kg 2.00 1.60 1.20

The suppliers of the ingredients can deliver each week at most 100kg of sunower seeds at 1.00/kg, 80kg of rasins at 1.50/kg and 60kg of peanuts at 0,80/kg. Assuming there is no limit to what can be sold, formulate (but do not solve) the problem of nding the mixing scheme that maximises weekly prot. Exercise 13 A coee packer blends Brazilian coee and Colombian coee to prepare two products, super and deluxe brands. Each kilogram of super coee contains 0.5 kg of Brazilian coee and 0.5 kg of Colombian coee, whereas each kilogram of deluxe coee contains 0.25 kg of Brazilian coee and 0.75 kg of Colombian coee. The packer has 120kg of Brazilian coee and 160kg of Colombian coee on hand. If the prot one each kilogram of super coee is 22 cents and the prot on each kilogram of Deluxe coee is 30 cents, how many kilograms of each type of coee should be blended to maximise prots? Formulate and solve.

Exercise 14 Major oil companies use linear programming to model many phases of their operations. Consider the following simplied version of part of a renery operation. Two kinds of aviation gasoline, high-octane and low-octane, are made by blending four components from the renery output. For the low octane gasoline the components are augmented with a small amount of tetraethyllead (TEL) to give the low-octane ratings shown in the accompanying table. The high-octane gasoline is made from the same components when these have been augmented with a larger amount of TEL, giving the high-octane ratings in the table. Assume that the octane rating (OR) of the mixture is the volumetric average of the octane ratings of the components. That is, letting V denote volume, we have ORmix = ORcomp1 Vcomp1 + ORcomp2 Vcomp2 + . Vcomp1 + Vcomp2 +

The vapour pressure (a measure of the tendency of the gasoline to evaporate) of both gasolines must be 7. Assume that the vapour pressure of a mixture is the volumetric average of the vapour pressures of the components. Vapour pressure and octane rating are the only two physical properties for which there are constraints. Data for the components and desired mixtures are given in the accompanying table.
Vapour presure Component Alkylate Catalytic cracked Straight run Isopentane Mixture High octane Low octane 5 6.5 4 18 7 7 OR High Low 108 98 94 87 87 80 108 100 100 - 90 Demand 1300 800 Supply 700 600 900 500 Revenue 6.50 7.50 Cost 7.20 4.35 3.80 4.30 -

Assuming that demands must be met exactly, maximise revenue minus cost. Formulate this problem in the form of a linear programming problem.

Week 5

Exercise 15 Suppose that we consider the asymmetric dual to the primal canonical linear programming problem maximise z = c x subject to: Ax = b x 0n where A Rmn , b Rm and c Rn are given. Prove that the conclusion of the Weak Duality Theorem is still valid. That is to say, for any feasible solution x to the primal and feasible solution to the dual y it is still true that c x b y. Further, it is still true that if c x = b y then x and y are optimal for the primal and dual respectively. Exercise 16 Consider the linear programming problem in canonical form maximise z = c x subject to: Ax = b x 0n where A Rmn , b Rm and c Rn are given. Recall from Section 5.3 of the lecture notes that if we have a basic feasible solution in the form x= 0nm xB

and partitioning A accordingly as (Ao |B) and similarly with c then the tableau associated with the next step of the simplex algorithm may be rearranged as follows: . . . . T 1 0 0 T (cB B A (c ) ) . . B1 A0 Suppose now that x is optimal. (a) Deduce that cB T B1 A0 (co )T . 7 Im 0T m xB cB B1 b
T

(b) Now suppose that we dene wT = cB T B1 and note that w Rm . Show that wT A cT . (c) Finally show that b w = c x. Use the weak duality theorem to show that w is the optimal solution to the asymmetric dual of the canonical linear programming problem. Note that this question also tells you how to solve explicitly the dual of a given linear programming problem - this is useful in the next two questions. Exercise 17 The problem maximise z = 3x1 + 6x2 + 2x3 subject to: 3x1 + 4x2 + 2x3 200 x1 + 3x2 + 2x3 100 x1 , x 2 , x 2 0 has its optimal solution with x1 and x2 as basic variables. Use this information to obtain the simplex tableau for the optimal solution directly without using the simplex algorithm. (ie calculate B1 etc). Write down the dual problem and use the tableau to obtain both the primal and the dual optimal solutions. Check that the solutions are (i) feasible (ii) have equal values of the objectives and (iii) (for later) satisfy the complementary slackness conditions. Exercise 18 Consider the problem of the mining company in Exercise 8. Write down the dual problem and use your simplex tableau corresponding to the optimal primal solution to obtain the optimal dual solution. Give an economic interpretation of the dual variables and in terms of this explain why none of the hard alloy was made. By how much would the prot per ton for this alloy have to increase before it could be produced economically?

Week 6

Exercise 19 Go back and do part (iii) of Exercise 17. Exercise 20 Show without using the Simplex Method that xT = ( 5 5 27 , , ) 26 2 26

is an optimal solution to the following linear programming problem: maximise z = 9x1 + 14x2 + 7x3 subject to: 2x1 + x2 + 3x3 6 5x1 + 4x2 + x3 12 2x2 5 x1 , x2 , x3 unrestricted. Exercise 21 Consider the linear programming problem maximise z = 3x1 + 4x2 subject to: x1 + 2x2 10 x1 + x2 8 3x1 + 5x2 26 x1 , x2 0. By using the principle of complementary slackness, show that y1 = 0 in any optimal solution y to the dual.

Week 7

Exercise 22 Solve the transportation problem having the following cost, requirement, availability table. Start with your rst solution coming from the matrix method. 80 100 20 55 70 35 40 13 11 18 17 2 14 10 1 5 8 18 11

Exercise 23 It is required to move machines from factories A, B and C to warehouses X, Y and Z. There are 5 required at X, 4 at Y and 3 at Z, whilst there are 8 available at A, 5 at B and 3 at C. The transport cost in between the sites is as follows. A B C X Y 50 60 60 40 40 70 Z 30 20 30

Plan the movements to minimise total transport cost. Exercise 24 Suppose in question 23 there is now an increase in transport cost of 10 per machine taken from B for any machines above three (i.e. for the 4th and 5th). Does this alter the best plan? To solve this you will need to split source B into two sources. This device only works because the cost is increased for higher quantity. Why?

10

Week 8

Exercise 25 Suppose now in question 23 there is a reduction in transport cost of 10 per machine taken from A for any machines above six. (This is separate from and not in addition to the change described question 3.) Use the same device as in question 3 to nd the new optimal solution, but because this time there has been a decrease in price for higher quantity, you will need to solve two problems and also use pricing out1 . Sort out the details yourself. Exercise 26 A factory uses a raw material whose price and availability vary seasonally. The price, availability and factory requirement for each quarter of the next year are given in the following table. Quarter Price/ton in Availability (tons) Requirement (tons) 1 110 1000 750 2 100 1700 900 3 120 800 1000 4 130 400 850

The cost per ton of storing the material from one quarter to the next is 4 + 10% of the purchase price. The material may also be stored for two quarters at double the above cost per ton, but will not keep for longer than two quarters. No stock is held initially and none is required at the end. Find the pattern of buying and storing that minimises the total cost. State any assumptions that you make. Exercise 27 Solve the following transportation problem starting with the N.W.corner solution. The point here is that care is needed in handling degenerate solutions.2 10 5 10
1

5 10 10 4 2 3 6 5 8 1 4 3

Recall the pricing out is a technique by which one imposes a very high transportation cost in order to avoid such a route appearing in the solution 2 Recall that a degenerate solution occurs when one of the basic variables is equal to zero.

11

Week 9

Exercise 28 Find a maximal ow and a minimal cut for the following network. Show explicitly the ows in the individual arcs. 0 9 6 2 0 0 0 0 0 0 0 6 0 0 0 0 0 4 2 5 0 0 0 3 0 0 5 0 0 6 3 0 0 0 5 0 0 5 5 0 0 12 0 0 0 0 0 0 0 Exercise 29 For the rst worked example given in the lecture notes, consider applying the following sequence of ows 1 3 5 6 : ow 13246: 1 2 5 6 : ow 1 3 6 : ow 1 1 2 4 6 : ow 5 ow 2 1 2.

First adjust the residual capacities only in the direction of the ows of the paths above and you will see that the ow appears optimal. Now, correctly, adjust the residual capacities in both directions and you will see that there is an unsaturated path and the ow can be augmented. In doing this, you may be able to calculate the residual capacities in one step ore prefer to do it in several steps. Exercise 30 Show that a maximal ow problem may be expressed as a linear programming problem with positive variables.

12