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):

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:

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:

• The price of items (obviously I will want to minimise this)
• The amount of each item required (which will be a lower bound for that item)
• The storage capacity of the two vans (which will be upper bounds)

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 100c_s + 75c_t + 300m_s + 350m_t + 50f_s + 60f_t + 200s_s + 180s_t

+ 100p_s + 120p_t + 250h_s + 200h_t

subject to c_s + c_t >= 5.25

m_s + m_t >= 35.5

f_s + f_t >= 14

s_s + s_t >= 14

p_s + p_t >= 6

h_s + h_t >= 3.5

c_s + m_s + f_s + s_s + p_s + h_s Å 38

c_t + m_t + f_t + s_t + p_t + h_t Å 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 + c_s + c_t + m_s + m_t + f_s + f_t + s_s + s_t + p_s + p_t + h_s + h_t - s₁ - s₂

- s₃ - s₄ - s₅ - s₆ = 78.25

and I - 100c_s - 75c_t - 300m_s - 350m_t - 50f_s - 60f_t - 200s_s - 180s_t

- 100p_s - 120p_t - 250h_s - 200h_t = 0

subject to c_s + c_t + a₁ - s₁ = 5.25

m_s + m_t + a₂ - s₂ = 35.5

f_s + f_t + a₃ - s₃ = 14

s_s + s_t + a₄ - s₄ = 14

p_s + p_t + a₅ - s₅ = 6

h_s + h_t + a₆ - s₆ = 3.5

c_s + m_s + f_s + s_s + p_s + h_s + s₇ = 38

c_t + m_t + f_t + s_t + p_t + h_t + s₈ = 45

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

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

Pivot about row 3, column 3

Pivot about row 9, column 5

Pivot about row 4, column 4

Pivot about row 3, column 7

Pivot about row 5, column 6

Pivot about row 6, column 9

Pivot about row 7, column 11

Pivot about row 8, column 13

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:

This then proceeds as follows:

Pivot about row 7, column 13

Pivot about row 5, column 9