__Assignment: Linear Programming, Sensitivity Analysis, Network Modelling and Integer Linear Programming (and Inventory Management) using Microsoft Excel Solver__

Total available marks: 68 + 30 + 12 = 110 marks. Marks over 100 will be rounded down to 100.

**Note 2**: You will be required to be prepared to (present and) be interviewed about the work during lab/tute/studio time – to be determined by your lecturer and tutor, currently scheduled for week 10. This is a compulsory part of your assessment – only to be re-scheduled if you have an approved application for special consideration. Students should be familiar with the special consideration policies and the process for applying.

**Note 3**: As a general rule, don’t just give a number or an answer like `Yes’ or `No’ without at least some clear and sufficient explanation. Make it easy for the person marking your work to follow your reasoning. Your .pdf should typically cross-reference the corresponding answer in your spreadsheet.

**Note 4**: As a general rule, if there is an elegant way of answering a question without unnecessarily re-running the Solver, try to do it that way. More generally, more elegant solutions are preferable. Among other things, if a problem is a linear programming (LP) problem, then it would be more elegant to solve it using the linear simplex model. In similar vein, a linking constraint (where appropriate) will be far preferable to a seemingly equivalent use of the IF() function.

**Question 1 – Many spas, many components **[6 + 6 + 2 + 2 + 1 + 1 + 2 + 2 + 2 + (1+1) + (4+1) + (4+1) + (2+3) + (3+1) + (2+1) + (3+1) + (1+1) + (3+1) + (2+1) + (2+1) + (3+1) = 6 + 6 + 2 + 2 + 1 + 1 + 2 + 2 + 2 + 2 + 5 + 5 + 5 + 4 + 3 + 4 + 2 + 4 + 3 + 3 + 4 = 68 marks]

Consider 4 types of spa tub: Aqua-Spa (or FirstSpa, or P1), Hydro-Lux (or SecondSpa, or P2), ThirdSpa (or P3) and FourthSpa (or P4), with the production of products P1, …, P4 in quantities X1, …, X4 made up of 5 components (or things) : Component1 (pumps, or thing1), Component2 (labour, or thing2), Component3 (tubing, or thing3), Component4 (or thing4, or plastic), Component5 (or thing5, or clips). (We will sometimes use the terms Pi and Xi interchangeably.) The profit for each of X1, …, X4 is c1, …, c4 shown below. Unless stated otherwise, you should not assume that the Xi are integers. We also show below the amounts of Component1, Component2, …, Component5 required to make each of P1, …, P4.

P1 | P2 | P3 | P4 | Available | |

Component1 | 1 | 1 | 1 | 1 | 400 |

Component2 | 9 | 6 | 9 | 12 | 3132 |

Component3 | 12 | 16 | 14 | 19 | 5756 |

Component4 | 10 | 12 | 18 | 22 | 6000 |

Component5 | 15 | 13 | 19 | 18 | 5992 |

Profit | 350 | 300 | 390 | 500 |

We wish to produce the number to maximise total profit.

The questions follow below:

- Formulate a Linear Programming (an LP) formulation for this problem. Save your formulation in the text-based .pdf file [
*FamilyName*–*StudentId-*

*2ndSem2018FIT5097*.pdf]. (6 marks)

- Create a spreadsheet model for this problem. Store the model in your Excel workbook [
*FamilyName*–*StudentId-2ndSem2018FIT5097*.xlsx] and name your

spreadsheet something like (e.g.) ‘ManySpas’ (6 marks)

- Solve the problem – using Microsoft Excel Solver. Generate the Sensitivity report for the problem and name your spreadsheet (e.g.) ‘Qu 1 ManySpas Sensitivity Rep’.

(2 marks)

Using the Microsoft Excel Solver sensitivity report, provide answers (in the .pdf file) to the following questions: (**You must include explanations with your answers**.)

- d) What is the optimal production plan and the associated profit? Refer to your answers to any of a), b) and/or c) above as appropriate. (2 marks)

For the remaining parts of this question, explain your answer(s), possibly referring to relevant spreadsheet entry/ies and/or specific relevant parts of spreadsheet reports.

e) | Is the solution degenerate – and why or why not? | (1 mark) |

f) | Is the solution unique – and why or why not? | (1 mark) |

g) Which constraints – if any – are binding? | (2 marks) |

- h) How much does the solution change by if we require X1, X2, X3 and X4 to be integers? What are the new values of the Xi and the objective function? (2 marks)

- i) If we no longer require X1, X2, X3 and X4 to be non-negative, what is the new

solution? What are the Xi and the objective function? (2 marks)

Unless stated otherwise, X1, X2, X3 and X4 are not required to be integers.

Regarding non-negativity, make sure to clearly state what you deem appropriate.The company is offered the possibility of buying an extra pump (Component1) or possibly as many as 100 extra pumps at a substantial discount (or bargain basement price).

Try to solve as many of the two sub-questions immediately below as possible without re-running the Solver (and only re-run the Solver if necessary).

j.i) How much should the company be willing to pay for 1 pump?

j.ii) How much should the company be willing to pay for 100 pumps?

Try to solve as many of the two sub-questions immediately above as possible without re-running the Solver (and only re-run the Solver if necessary). (1 + 1 = 2 marks)

- Changes are to be made to the number(s) and/or amount(s) of pumps, labour and thing5: 18 less pumps, 150 more hours of labour and 250 more of thing5.

Try to solve as many of the two sub-questions immediately below as possible without re-running the Solver (and only re-run the Solver if necessary).

k.i) What is the (new) optimal number of each of X1, X2, X3 and X4?

k.ii) What is the (new) optimal value of the objective function?

Try to solve as many of the two sub-questions immediately above as possible without re-running the Solver (and only re-run the Solver if necessary). (4 + 1 = 5 marks)

- l) Due to discounting, the profit on the FourthSpa is being reduced by 6%.

Try to solve as many of the two sub-questions immediately below as possible without re-running the Solver (and only re-run the Solver if necessary).

l.i) What is the (new) optimal number of each of X1, X2, X3 and X4?

l.ii) What is the (new) optimal value of the objective function?

Try to solve as many of the two sub-questions immediately above as possible without

re-running the Solver (and only re-run the Solver if necessary). (4 + 1 = 5 marks)

- m) A new spa, called FifthSpa, is being considered.

It requires 2 pumps (Component1), 10 hours of labour (Component 2), 20 ft of tubing (Component3), 10 units of thing4 (or Component4), and 10 units of thing5 (or Component5), and the plan is for it to sell it at a profit of $310.

m.i) Is it profitable to make any FifthSpas? (Explain why or why not.)

m.ii) If so, then by how much could we decrease the profit of a FifthSpa while still

having it worthwhile to make? And, if not, then by how much would we have to increase the profit of a FifthSpa for it to be profitable to make?

Try to solve as many of the two sub-questions immediately above as possible without

re-running the Solver (and only re-run the Solver if necessary). | (2 + 3 = 5 marks) | |

n) | If only three of the four types of spa are to be made, which three should they be, and | |

in what amounts, to maximise profits? What is the profit? | (3 + 1 = 4 marks) | |

o) | If only two of the four types of spa are to be made, which two should they be, and in | |

what amounts, to maximise profits? What is the profit? | (2 + 1 = 3 marks) |

- If all four types of spa may be made but we have start-up costs of 1800, 2300, 2200 and 2600 respectively (not assuming integer values),

p.i) what is the (new) optimal number of each of X1, X2, X3 and X4?

p.ii) what is the (new) optimal value of the objective function? (3 + 1 = 4 marks)

- If all four types of spa may be made but we have start-up costs of 1800, 2300, 2200 and 2600 respectively (assuming integer values),

q.i) what is the (new) optimal number of each of X1, X2, X3 and X4?

q.ii) what is the (new) optimal value of the objective function? (1 + 1 = 2 marks)

- r) If all four types of spa may be made and we have no start-up costs and we can

make a maximum of 220, 180, 140 and 100 respectively (not assuming integer values), and (for those where more than 0 is produced) we must make at least a minimum of 20, 30, 40 and 50 respectively,

r.i) what is the (new) optimal number of each of X1, X2, X3 and X4?

r.ii) what is the (new) optimal value of the objective function? (3 + 1 = 4 marks)

- If at most three types of spa may be made and we have no start-up costs and we can make a maximum of 220, 180, 140 and 100 respectively (not assuming integer values), and (for those where more than 0 is produced) we must make at least a minimum of 20, 30, 40 and 50 respectively,

s.i) what is the (new) optimal number of each of X1, X2, X3 and X4?

s.ii) what is the (new) optimal value of the objective function? (2 + 1 = 3 marks)

- If at most two types of spa may be made and we have no start-up costs and we can make a maximum of 220, 180, 140 and 100 respectively (not assuming integer values), and (for those where more than 0 is produced) we must make at least a minimum of 20, 30, 40 and 50 respectively,

t.i) what is the (new) optimal number of each of X1, X2, X3 and X4?

t.ii) what is the (new) optimal value of the objective function? (2 + 1 = 3 marks)

- Suppose at most three types of spa may be made and we have no start-up costs and we can make a maximum of 220, 180, 140 and 100 respectively (not assuming integer values), and (for those where more than 0 is produced) we must make at least a minimum of 20, 30, 40 and 50 respectively. And let us suppose further that we have the additional specific requirement that if we make a SecondSpa (Hydro-Lux) then (in that case) we would be required to also make an Aqua-Spa (FirstSpa).

u.i) What is the (new) optimal number of each of X1, X2, X3 and X4?

u.ii) and what is the (new) optimal value of the objective function? (3 + 1 = 4 marks)

__Question 2__** **(6 + 6 + 2 + 5 + 5 + 2 + 2 + 2 = 30 marks)

Consider the following network of transshipment, with various weights and maximum flows along certain edges.

We have a supply of 75 units at Arnold and 75 units at Supershelf.

We consider ways of moving this (this total of 75 + 75 = 150) through the network so that an appropriate part of it (if any) arrives at Ten, and the remaining appropriate part of it (if any) arrives at Eleven, with the total of the amounts arriving at Ten and at Eleven being 150.

To (at right) |
Thomas | Arnold to Thomas | Washburn | |||||||

excess, above 40 | ||||||||||

From (below) |
||||||||||

Arnold | Unit cost: | $5 | Unit cost: $8 | |||||||

Max flow: 40 | Max flow: 70 | |||||||||

Arnold to Thomas | Unit cost: $9 | |||||||||

excess, above 40 | Max additional | |||||||||

flow: | 70 | |||||||||

Supershelf | Unit cost: $7 | Unit cost: $4 | ||||||||

Max flow: 70 | Max flow: 70 | |||||||||

To (at right) |
Zrox | Washburn to Zrox | Hewes | |||||||

excess, above 65 | ||||||||||

From (below) |
||||||||||

Thomas | Unit cost: | $1 | Unit cost: $5 | |||||||

Max flow: 65 | Max flow: 70 | |||||||||

Washburn | Unit cost: $3 | Unit cost: $4 | ||||||||

Max flow: 65 | Max flow: 70 | |||||||||

Washburn to Zrox | Unit cost: $5 | |||||||||

excess, above 65 | Max additional | |||||||||

flow: | 70 | |||||||||

To (at right) |
Eight | Nine | ||||||||

From (below) |
||||||||||

Zrox | Unit cost: $3 | Unit cost: | $9 | |||||||

Max flow: 70 | Max flow: 70 | |||||||||

Hewes | Unit cost: $7 | Unit cost: $8 | ||||||||

Max flow: 70 | Max flow: 70 | |||||||||

To (at right) |
Ten | Nine to Ten | Eleven | |||||||

excess, above 70 | ||||||||||

From (below) |
||||||||||

Eight | Unit cost: | $6 | Unit cost: $9 | |||||||

Max flow: 70 | Max flow: 70 | |||||||||

Nine | Unit cost: $7 | Unit cost: $8 | ||||||||

Max flow: 70 | Max flow: 70 | |||||||||

Nine to Ten excess, | Unit cost: $14 | |||||||||

above 70 | Max additional | |||||||||

flow: | 70 |

Some further explanatory notes about these above tables follow on the next page.

The tables above show how flow goes from Arnold (supply 75) and Supershelf (supply 75) through to Ten and Eleven. Graphically, both Arnold and Supershelf are connected to both Thomas and Washburn; then both Thomas and Washburn are connected to both Zrox and Hewes; then both Zrox and Hewes are connected to both Eight and Nine; and then both Eight and Nine are connected to both Ten and Eleven.

In some cases, an edge has different amounts of cost, depending upon the flow along the edge. This is the case with Arnold to Thomas, it is also the case with Washburn to Zrox, and it is also the case from Nine to Ten. In these cases, we see the word `excess’ appear in the table. As an example, let us look at the flow from node Nine to node Ten, where we see the note `Nine to Ten excess, above 70’. This gives us two cases: if the flow from Nine to Ten is less than or equal to 70 (that’s the first case), and (the second case) if the flow from Nine to Ten is more than 70 (up to a maximum of 70 + 70 = 140). If the flow from node Nine to node Ten is 50, then it would cost $7 x 50 = 350. (This is because 50 is less than or equal to 70.) Now let us look at a case of flow greater than 70. If the flow from none Nine to node Ten is 100, then the cost would be $7 x 70 + $14 x (100 – 70) = $7 x $70 + $14 x 30 = $490 + $420

- $910; where this calculation sees the first 70 units of flow being costed at $7 each and the (remaining) 100 – 70 = 30 units of flow in excess of 70 being costed at $14 each.

Make sure to include your answers in the relevant .pdf file and (in various tabs) in the relevant .xls file: *FamilyName*–*StudentId-2ndSem2018FIT5097*.{pdf, xls}. Explain your answer(s), possibly referring to relevant spreadsheet entry/ies and/or specific relevant parts of spreadsheet reports in your .pdf file.

- Choose as your starting point either Arnold or Supershelf, and choose as your end point (or destination) either Ten or Eleven. Interpret `unit cost’ as meaning `length of edge’.

Documenting and explaining your working and any spreadsheet use, show the shortest path from your starting point to your destination, including its length.

Now interpret the question as it is originally worded, where `unit cost’ shall be indeed taken to mean `unit cost’ (rather than `length of edge’).

- Assuming the edges are uni-directional (that flow along an edge can only go from the first-named vertex [or node] to the second-named vertex [or node]), show the minimum cost through the network: of getting things from Arnold and Supershelf to Ten and Eleven. Show the flow(s) along edges and the minimum cost.

- Assuming the edges are uni-directional, show the maximum cost through the network. Show the flow(s) along edges and the maximum cost.

- Allowing edges to be bi-directional (so that flow along an edge can go in either direction, where flow in the reverse direction has the same unit cost as flow in the original direction), show the minimum cost through the network. Show the flow(s) along edges and the minimum cost.

- Return now to part b) above, with uni-directional flow, but now with an additional charge (or cost) of $150 for each edge that has non-zero flow, in addition to the unit costs for using that edge. This additional cost can be thought of as a start-up cost, such as opening the edge for use. Show the minimum cost through the network. Show the flow(s) along edges and the minimum cost.
- Similarly but different to part e) above, we make a variation on part c) above. With uni-directional flow, suppose we get a discount of $150 for each edge that has non-zero flow. Show the maximum cost through the network. Show the flow(s) along edges and the maximum cost.

An even number is a natural number (or positive integer) which is a multiple of 2 (e.g., 2, 4, 6, 8, …), and an number is a natural number which is not a multiple of 2 (e.g., 1, 3, 5, 7, …).

- Returning now to part e) above, suppose we require that the number of edges with non-zero flow is an even number. Show the minimum cost through the network. Show the flow(s) along edges and the minimum cost.

- Return now to part f) above, but with a discount of $25 (that’s $25, not $150) for each edge with non-zero flow. Suppose that we require the number of edges with non-zero flow is an even number. Show the maximum cost through the network. Show the flow(s) along edges and the maximum cost.

(This is the end of Question 2. Question 3 starts below.)

** Question 3** (Inventory Management) ((4+2) + (4 + 2) = 6 + 6 = 12 marks)

Consider the following Economic Production Lot Size problem.

Doing calculations with relevant formulae (from lectures) and calculator is worth 8 marks, and spreadsheet work is worth 4 marks. For part (a), the spreadsheet work requires presenting this as an optimisation problem to the Solver, and then using the Solver to solve it.

Make sure to include your answers in the relevant .pdf file and (in various tabs) in the relevant .xls file: *FamilyName*–*StudentId-2ndSem2018FIT5097*.{pdf, xls} .

The time period given below is a year, but it could equally well have been something different – such as, e.g., a decade. For the problem to follow, we will assume that the time period is 1 year.

We assume that demand occurs at a constant rate of 42,250,000 per year.

Our production facility can produce at a rate of 285,610,000 per year, but the set-up costs of starting the machine are $24 for each run.

There is a cost of $15 per item and a holding amount (or fraction, or percentage) 0.1 = 10% per item per year.

- What is the optimum value Q* of the production quantity, Q?

- If we were to change Q from Q* to 100,000, what would the resultant cost be, and how much worse would the resultant cost be when compared to Q = Q* in part (a)?

*A note about your Spreadsheet Model*

When building your model, bear in mind the goals and guidelines for good spreadsheet design as discussed in Lecture 3. Marks are given for good spreadsheet design. Marks will possibly also be given for originality. Format both your models clearly with comments (and, if possible, shading), etc. so that it is easy for the user to distinguish which cells are occupied by decision variables, LHS and RHS constraints, and the objective function. Include a textbox in each worksheet that describes the formulation in terms of cell references in your model.

*Instructions:*

You are to upload your submission on the FIT5097 Moodle site and should include the following:

- A text-based .pdf document (save as: FamilyName-StudentId-2ndSem2018FIT5097.pdf) that includes all your answers to Questions 1 and 2 and 3 (except for the Microsoft Excel Solver part of each question); and

- A Microsoft Excel workbook (save as: FamilyName-StudentId-2ndSem2018FIT5097.xlsx) that includes the following spreadsheets:

- the spreadsheet model for Question 1;
- Sensitivity Rep – the sensitivity report for the Question 1 model (and any other relevant parts);

- other relevant things for Question 1;

- relevant things for Question 2
- relevant things (including any calculations) for Question 3

- Anything else you deem sufficiently relevant.

Recall that, at the time you submit (1 and 2) to Moodle, the text-based .pdf will undergo a similarity check by Turnitin. This is done at the time you upload your assignment to Moodle.

(This ends the submission instructions. Please read them and the notes on page 1 carefully. Also recall that, as a general rule, when answering questions, don’t just give a number or an answer like `Yes’ or `No’ without at least some clear and sufficient explanation.)

Recall instructions above and notes on page 1, and please follow these carefully.