Decision and Discrete 2 Coursework - Mark Hutchinson

Introduction

The reader may recall (though I rather doubt it) that in my Decision and Discrete 1 coursework I examined the issues surrounding the process of putting up a bell-tent at the children's camps which my father runs, using critical path analysis and resource levelling to minimise the time required. This problem examines another issue arising from the camp, namely that of food ordering. I aim to use linear programming with the simplex algorithm to try and minimise the cost of food deliveries. The problem has been simplified somewhat to make it feasible, but the issues involved remain the same.

Specification of problem

At camp, food is ordered for each week at the start of that week. The estimated requirements of the bulk foodstuffs[1] for a week's worth of camp, for all the children and leaders, including seconds, is as follows (in kg due to the difficulty of providing volumes for all the foodstuffs):

Foodstuff Amount required (kg)
Cereal 5.25
Meat 35.5
Flour 14
Sugar 14
Pasta 6
Cheese 3.5

The camp is at a fairly remote site in Dursley, so there are only two supermarkets who will deliver there (here given the pseudonyms Safebury's and Tesda). Although both provide free delivery, they offer different prices for the foods:

Foodstuff Safebury's price (per kilo) Tesda price (per kilo)
Cereal £1 75p
Meat £3 £3.50
Flour 50p 60p
Sugar £2 £1.80
Pasta £1 £1.20
Cheese £2.50 £2

In addition, the vans can only carry a certain amount in one delivery. We don't want two separate deliveries from any one company, because the van drivers invariably have to ring up and ask for directions, and we want as few irritating phone calls as possible. Based on past experience of situations where multiple vans were sent, we have estimated that Safebury's van can fit around 38kg of food and Tesda can fit around 45kg.

Now we have specified the problem, we can try to model it using linear programming.

Modelling the problem

The things to be considered in formulating an LP problem here are:

Considering all these things, I have formulated the following (rather scary-looking) LP problem, denoting each item by its initial (except cheese which is h), followed by a s for Safebury's and a t for Tesda. As the problem will be solved by a computer program (written by myself), the size shouldn't present a great problem. Note that whilst weights are still given in kg, costs have been converted to pence; it is assumed the shop will round up any fractional pence given in the solution.

Minimise 100cs + 75ct + 300ms + 350mt + 50fs + 60ft + 200ss + 180st

+ 100ps + 120pt + 250hs + 200ht

subject to cs + ct >= 5.25

ms + mt >= 35.5

fs + ft >= 14

ss + st >= 14

ps + pt >= 6

hs + ht >= 3.5

cs + ms + fs + ss + ps + hs Å 38

ct + mt + ft + st + pt + ht Å 45

Substituting slack variables for inequalities and inserting artificial variables where required (I will be using two-stage simplex, not the big M method, as it is easier to implement in a program), this gives the following:

Minimise A + cs + ct + ms + mt + fs + ft + ss + st + ps + pt + hs + ht - s1 - s2

- s3 - s4 - s5 - s6 = 78.25

and I - 100cs - 75ct - 300ms - 350mt - 50fs - 60ft - 200ss - 180st

- 100ps - 120pt - 250hs - 200ht = 0

subject to cs + ct + a1 - s1 = 5.25

ms + mt + a2 - s2 = 35.5

fs + ft + a3 - s3 = 14

ss + st + a4 - s4 = 14

ps + pt + a5 - s5 = 6

hs + ht + a6 - s6 = 3.5

cs + ms + fs + ss + ps + hs + s7 = 38

ct + mt + ft + st + pt + ht + s8 = 45

which gives the following initial tableau (printed small because it's so wide):

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 78.25
0 1 -100 -75 -300 -350 -50 -60 -200 -180 -100 -120 -250 -200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 5.25
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 35.5
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 3.5
0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 38
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 45

The first stage then proceeds as shown by the following sequence of tableaux:

Pivot about row 3, column 3

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 -1 -1 -1 -1 -1 0 0 -1 0 0 0 0 0 73
0 1 0 25 -300 -350 -50 -60 -200 -180 -100 -120 -250 -200 -100 0 0 0 0 0 0 0 100 0 0 0 0 0 525
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 5.25
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 35.5
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 3.5
0 0 0 -1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 -1 0 0 0 0 0 32.75
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 45

Pivot about row 9, column 5

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 0 1 0 1 0 1 0 1 0 1 0 1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 40.25
0 1 0 -275 0 -350 250 -60 100 -180 200 -120 50 -200 200 0 0 0 0 0 300 0 -200 0 0 0 0 0 10350
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 5.25
0 0 0 1 0 1 -1 0 -1 0 -1 0 -1 0 -1 -1 0 0 0 0 -1 0 1 1 0 0 0 0 2.75
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 3.5
0 0 0 -1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 -1 0 0 0 0 0 32.75
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 45

Pivot about row 4, column 4

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 -1 -1 -1 -1 0 0 -1 -1 0 0 0 0 37.5
0 1 0 0 0 -75 -25 -60 -175 -180 -75 -120 -225 -200 -75 -275 0 0 0 0 25 0 75 275 0 0 0 0 11106.25
0 0 1 0 0 -1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 -1 0 0 0 0 2.5
0 0 0 1 0 1 -1 0 -1 0 -1 0 -1 0 -1 -1 0 0 0 0 -1 0 1 1 0 0 0 0 2.75
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 3.5
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 35.5
0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 -1 -1 0 0 0 0 42.25

Pivot about row 3, column 7

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 -1 0 0 1 0 1 0 1 0 1 0 1 0 -1 -1 -1 -1 -1 -1 0 -1 0 0 0 0 0 35
0 1 25 0 0 -100 0 -60 -150 -180 -50 -120 -200 -200 -75 -250 0 0 0 0 50 0 75 250 0 0 0 0 11168.75
0 0 1 0 0 -1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 -1 0 0 0 0 2.5
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 5.25
0 0 -1 0 0 1 0 1 -1 0 -1 0 -1 0 0 -1 -1 0 0 0 -1 0 0 1 1 0 0 0 11.5
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 3.5
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 35.5
0 0 -1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 -1 0 0 0 0 0 39.75

Pivot about row 5, column 6

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 0 23.5
0 1 -75 0 0 0 0 40 -250 -180 -150 -120 -300 -200 -75 -350 -100 0 0 0 -50 0 75 350 100 0 0 0 12318.75
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 5.25
0 0 -1 0 0 1 0 1 -1 0 -1 0 -1 0 0 -1 -1 0 0 0 -1 0 0 1 1 0 0 0 11.5
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 3.5
0 0 1 0 1 0 0 -1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 -1 0 0 0 24
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 -1 -1 -1 0 0 0 28.25

Pivot about row 6, column 9

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 -1 -1 0 0 -1 -1 -1 -1 0 0 9.5
0 1 -75 0 0 0 0 40 0 70 -150 -120 -300 -200 -75 -350 -100 -250 0 0 -50 0 75 350 100 250 0 0 15818.75
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 5.25
0 0 -1 0 0 1 0 1 0 1 -1 0 -1 0 0 -1 -1 -1 0 0 -1 0 0 1 1 1 0 0 25.5
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 3.5
0 0 1 0 1 0 0 -1 0 -1 1 0 1 0 0 0 1 1 0 0 1 0 0 0 -1 -1 0 0 10
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 -1 -1 -1 -1 0 0 14.25

Pivot about row 7, column 11

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 -1 -1 -1 -1 -1 0 3.5
0 1 -75 0 0 0 0 40 0 70 0 30 -300 -200 -75 -350 -100 -250 -150 0 -50 0 75 350 100 250 150 0 16718.75
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 5.25
0 0 -1 0 0 1 0 1 0 1 0 1 -1 0 0 -1 -1 -1 -1 0 -1 0 0 1 1 1 1 0 31.5
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 3.5
0 0 1 0 1 0 0 -1 0 -1 0 -1 1 0 0 0 1 1 1 0 1 0 0 0 -1 -1 -1 0 4
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 -1 -1 -1 -1 -1 0 8.25

Pivot about row 8, column 13

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 0
0 1 -75 0 0 0 0 40 0 70 0 30 0 100 -75 -350 -100 -250 -150 -300 -50 0 75 350 100 250 150 300 17768.75
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 5.25
0 0 -1 0 0 1 0 1 0 1 0 1 0 1 0 -1 -1 -1 -1 -1 -1 0 0 1 1 1 1 1 35
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 3.5
0 0 1 0 1 0 0 -1 0 -1 0 -1 0 -1 0 0 1 1 1 1 1 0 0 0 -1 -1 -1 -1 0.5
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 4.75

At the end the initial feasible solution can be seen from the tableau (I will not interpret it until the second stage is finished). Stripping away the now-unnecessary artificial variables and first objective gives the following initial tableau for the second stage:

I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 RHS
1 -75 0 0 0 0 40 0 70 0 30 0 100 -75 -350 -100 -250 -150 -300 -50 0 17768.75
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 14
0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 5.25
0 -1 0 0 1 0 1 0 1 0 1 0 1 0 -1 -1 -1 -1 -1 -1 0 35
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 14
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 6
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 3.5
0 1 0 1 0 0 -1 0 -1 0 -1 0 -1 0 0 1 1 1 1 1 0 0.5
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 4.75

This then proceeds as follows:

Pivot about row 7, column 13

I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 RHS
1 -75 0 0 0 0 40 0 70 0 30 -100 0 -75 -350 -100 -250 -150 -200 -50 0 17418.75
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 14
0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 5.25
0 -1 0 0 1 0 1 0 1 0 1 -1 0 0 -1 -1 -1 -1 0 -1 0 31.5
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 14
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 6
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 3.5
0 1 0 1 0 0 -1 0 -1 0 -1 1 0 0 0 1 1 1 0 1 0 4
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 4.75

Pivot about row 5, column 9

I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 RHS
1 -75 0 0 0 0 40 -70 0 0 30 -100 0 -75 -350 -100 -180 -150 -200 -50 0 16438.75
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 14
0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 5.25
0 -1 0 0 1 0 1 -1 0 0 1 -1 0 0 -1 -1 0 -1 0 -1 0 17.5
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 14
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 6
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 3.5
0 1 0 1 0 0 -1 1 0 0 -1 1 0 0 0 1 0 1 0 1 0 18
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 4.75

Pivot about row 2, column 7

I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 RHS
1 -75 0 0 0 -40 0 -70 0 0 30 -100 0 -75 -350 -60 -180 -150 -200 -50 0 15878.75
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 14
0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 5.25
0 -1 0 0 1 -1 0 -1 0 0 1 -1 0 0 -1 0 0 -1 0 -1 0 3.5
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 14
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 6
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 3.5
0 1 0 1 0 1 0 1 0 0 -1 1 0 0 0 0 0 1 0 1 0 32
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 4.75

Pivot about row 4, column 11

I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 RHS
1 -45 0 0 -30 -10 0 -40 0 0 0 -70 0 -75 -320 -60 -180 -120 -200 -20 0 15773.75
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 14
0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 5.25
0 -1 0 0 1 -1 0 -1 0 0 1 -1 0 0 -1 0 0 -1 0 -1 0 3.5
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 14
0 1 0 0 -1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 2.5
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 3.5
0 0 0 1 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 35.5
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 4.75

This gives a final cost of £157.74 and the following purchases:

Foodstuff Amount from Safebury's (kilos) Amount from Tesda (kilos)
Cereal 0 5.25
Meat 35.5 0
Flour 0 14
Sugar 0 14
Pasta 2.5 3.5
Cheese 0 3.5
Total 38 40.25

A quick glance confirms that this meets all the constraints; there is enough of each foodstuff and neither of the vans are overloaded. In most instances the algorithm has followed the obvious tactic of purchasing from the cheapest shop; however, as the vans start to fill up it is forced to mix and match. This is seen with the pasta and especially with the flour, which comes entirely from the (slightly) more expensive Tesda.

Developing the model

It has been mutely assumed throughout the problem that the supermarkets can supply any fractional quantity of each product. Actually, as it stands, this is not a problem; most products are available in 500g as well as 1kg quantities, and cereals are available in 750g as well, so the optimal solution is also a feasible one in these terms. However, it must be recognised that normally this problem would be an integer programming one. In order to consider how to deal with this kind of problem, let us assume that products are only available in 1kg bags (maybe we are now trying to take advantage of lower prices for bulk orders). This would obviously immediately imply an alteration in the constraints, because several are currently fractional themselves, and must therefore be rounded up:

Foodstuff Amount required (kg)
Cereal 6
Meat 36
Flour 14
Sugar 14
Pasta 6
Cheese 4

This would then give the following LP:

Minimise 100cs + 75ct + 300ms + 350mt + 50fs + 60ft + 200ss + 180st

+ 100ps + 120pt + 250hs + 200ht

subject to cs + ct >= 6

ms + mt >= 36

fs + ft >= 14

ss + st >= 14

ps + pt >= 6

hs + ht >= 4

cs + ms + fs + ss + ps + hs Å 38

ct + mt + ft + st + pt + ht Å 45

which would convert (with slack and artificial variables) to this:

Minimise A + cs + ct + ms + mt + fs + ft + ss + st + ps + pt + hs + ht - s1 - s2

- s3 - s4 - s5 - s6 = 80

and I - 100cs - 75ct - 300ms - 350mt - 50fs - 60ft - 200ss - 180st

- 100ps - 120pt - 250hs - 200ht = 0

subject to cs + ct + a1 - s1 = 6

ms + mt + a2 - s2 = 36

fs + ft + a3 - s3 = 14

ss + st + a4 - s4 = 14

ps + pt + a5 - s5 = 6

hs + ht + a6 - s6 = 4

cs + ms + fs + ss + ps + hs + s7 = 38

ct + mt + ft + st + pt + ht + s8 = 45

giving the following initial tableau:

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 80
0 1 -100 -75 -300 -350 -50 -60 -200 -180 -100 -120 -250 -200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 6
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 36
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 4
0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 38
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 45

The whole sequence of pivots will not be shown as it is basically the same as before, just with a different RHS, but the at the end of stage 1 the tableau looks as follows:

A I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 a1 a2 a3 a4 a5 a6 RHS
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 0
0 1 -75 0 0 0 0 40 0 70 0 30 0 100 -75 -350 -100 -250 -150 -300 -50 0 75 350 100 250 150 300 18150
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 14
0 0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 6
0 0 -1 0 0 1 0 1 0 1 0 1 0 1 0 -1 -1 -1 -1 -1 -1 0 0 1 1 1 1 1 36
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 14
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 6
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 4
0 0 1 0 1 0 0 -1 0 -1 0 -1 0 -1 0 0 1 1 1 1 1 0 0 0 -1 -1 -1 -1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 3

This then reduces to the following initial tableau for stage 2:

I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 RHS
1 -75 0 0 0 0 40 0 70 0 30 0 100 -75 -350 -100 -250 -150 -300 -50 0 18150
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 14
0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 6
0 -1 0 0 1 0 1 0 1 0 1 0 1 0 -1 -1 -1 -1 -1 -1 0 36
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 14
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 -1 0 0 0 6
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 4
0 1 0 1 0 0 -1 0 -1 0 -1 0 -1 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 3

which gives the following final tableau:

I cs ct ms mt fs ft ss st ps pt hs ht s1 s2 s3 s4 s5 s6 s7 s8 RHS
1 -45 0 0 -30 -10 0 -40 0 0 0 -70 0 -75 -320 -60 -180 -120 -200 -20 0 16090
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 14
0 1 1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 6
0 -1 0 0 1 -1 0 -1 0 0 1 -1 0 0 -1 0 0 -1 0 -1 0 4
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 14
0 1 0 0 -1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 2
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 4
0 0 0 1 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 36
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 3

The final cost is £160.90 and the purchases are as follows:

Foodstuff Amount from Safebury's (kilos) Amount from Tesda (kilos)
Cereal 0 6
Meat 36 0
Flour 0 14
Sugar 0 14
Pasta 2 4
Cheese 0 4
Total 38 42

I had expected to encounter a non-feasible solution here (due to introduced fractions by the algorithm) but as it transpires the solution is an integer one anyway. The cost has only been increased by £3.16, and the left-over stock could be saved for the next week of camp. Interestingly, there has been a knock-on effect on the purchase of pasta (the amount of which was not changed from the last problem).

Conclusion

The simplex algorithm is an extremely powerful tool. Here it has been used to find the cheapest combination of orders from two shops, something which could have taken a human a long time to work out. I have also investigated the consequences of restricting the products to integer amounts, which here had only a very slight effect on the result. A computer program has been used throughout to compute the algorithm, as without it the algorithm (here requiring 12 pivots) would have taken a very long time.

Mark Hutchinson




[1]  or at least, those which are bought from supermarkets; fruit and veg is bought from a grocer, and dessert mix is not included because it weighs so little.