Coursework2-20193
IS50003C Foundations of Problem Solving Due 01 April 2019, at 23:59
1
Coursework
2
1. Consider the linear programming problem in π₯,π¦ and π§ given below. The objective is
to maximise the profit, π.
Maximise
π = 2π₯ + π¦ + 6π§
Subject to
π₯ + 2π§ β€ 24
π₯ + 2π¦ + 4π§ β€ 28
π₯ β 2π¦ + 6π§ β€ 44
and π₯ β₯ 0,π¦ β₯ 0,π§ β₯ 0.
a. By introducing slack variables to convert inequalities to equalities, display the
information given above in a simplex tableau.
[6]
b. By first identifying the pivot column at each stage, solve this linear programming
problem. You must make your method clear by also indicating the pivot row,
pivot value and stating the row operations you use.
[15]
c. State the final value of each variable (including slack variables) and of the
objective function.
[4]
[Total: 25 marks]
2. The table below shows the cost, in pounds, of transporting a television from each
warehouse π΄,π΅ and πΆ, to each supermarket π,π and π. The total cost of
transporting the televisions is to be minimized.
X Y Z Supply
π΄ 3 6 3 34
π΅ 5 8 4 57
πΆ 2 5 6 25
Demand 20 56 40
a. Is this a balanced problem? Justify your answer.
[1]
b. Use the north west corner method to obtain a transportation pattern and
calculate the total cost.
[3]
c. Show that this pattern is not optimal by calculating improvement indices. You
must clearly show your shadow costs.
IS50003C Foundations of Problem Solving Due 01 April 2019, at 23:59
2
[5]
d. Use the stepping stone method to obtain an improved solution, showing clearly
your route, entering cell, π<=> and exiting cell.
[4]
e. Show that the transportation pattern obtained in part d. is not optimal and
perform one more iteration of the stepping stone method to obtain an improved
solution. You must clearly state your shadow costs, improvement indices,
entering cell, exiting cell, π<=> and route.
[8]
f. Is your solution to part e. optimal? Justify your answer and state the cost of the
solution you found.
[4]
[Total: 25 marks]
3. There are four individual rounds in a quiz: Art (A), Literature (L), Music (M) and
Science (S). A team consists of four people, Blessing (B), Collins (C), Donnie (D) and
Elijah (E). Each of the four rounds must be answered by a different member.
The table below shows the number of points each team member is likely to score on
each individual round.
A L M S
B 18 15 21 23
C 31 24 32 35
D 19 14 20 21
E 16 10 19 22
a. Use the Hungarian algorithm to obtain an allocation that maximises the total
points scored in the four rounds. You must clearly show your working and the
state of the table after each stage.
[16]
b. Is this allocation unique? Justify your answer.
[2]
c. State the value of the maximum points scored.
[2]
[Total: 20 marks]
4.
a. Define the terms
i. Cut,
[2]
ii. Minimum cut
IS50003C Foundations of Problem Solving Due 01 April 2019, at 23:59
3
[1]
as applied to a directed network flow.
The figure below shows a capacitated, directed network. The capacity of each arc
is shown on each arc, and the numbers in circles represent an initial flow.
Figure 1
b.
i. State the value of the initial flow. You must show your working.
[2]
ii. State the capacities of cuts πΆ? and πΆ@, clearly showing your working.
[4]
In solving another network flow problem using the labelling procedure, the diagram
in the figure 2 below was created.
The arrows on each arc indicates the direction of the flow along that arc.
The arrows above and below each arc show the direction and the value of the flow
as indicated by the labelling procedure.
IS50003C Foundations of Problem Solving Due 01 April 2019, at 23:59
4
Figure 2
c.
i. Add a supersource π, and a supersink π and appropriate arcs to the
diagram above and complete the labelling procedure for these arcs.
[4]
ii. Find the value of the initial flow for the network in Figure 2.
[2]
iii. Use the initial flow and the labelling procedure to find a maximal flow
through this network. List each flow-augmenting route you use, together
with its flow.
[10]
iv. Show your flow on Figure 3 below and show that its value is 124.
[3]
v. Prove that your flow is maximal. (You must clearly identify any cut you
use by listing its arcs or indicating it on Figure 3.)
IS50003C Foundations of Problem Solving Due 01 April 2019, at 23:59
5
[2]
[Total: 30 marks]
Figure 3
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
