COMP331/557 – Class Test – 2020-Nov-25/26
Class Test. This is worth 15% of your grade.
Due date: Thursday, November 26th, 2020, 12:00 noon, via SAM
(https://sam.csc.liv.ac.uk/COMP/Submissions.pl?strModule=COMP331 or
https://sam.csc.liv.ac.uk/COMP/Submissions.pl?strModule=COMP557)
Task 1 [2 marks]
A manufacturer has two machines that each can produce two different products, product A and prod-
uct B. Product A can be sold for £1000 per metric ton. Product B can be sold for £800 per metric
ton.
• Machine X can run for 40 hours per week. It takes 40 minutes for machine X to produce one metric
ton of product A. It takes 30 minutes for machine X to produce one metric ton of product B.
• Machine Y can run for 35 hours per week. It takes 35 minutes for machine Y to produce one metric
ton of product A. It takes 25 minutes for machine Y to produce one metric ton of product B.
The manufacturer wants to maximise the sales revenue for one week.
(a) Set up the corresponding linear program in standard form.
(b) Introduce slack variables and find an initial feasible primal dictionary to run the primal simplex
algorithm (do not actually run the simplex algorithm).
page 1/5
COMP331/557 – Class Test – 2020-Nov-25/26
Task 2 [2 marks]
The following figure is a graphical presentation of a linear program in standard form with slack variables
x3, x4, and x5. As in the lecture, the darker area of a black line marks the area where xi ≥ 0.
The objective function that we want to maximise is ζ = x2. We use Bland’s rule as the pivoting rule.
We start the simplex with basis (3, 4, 5).
Your task is to run the simplex algorithm and analyse its run: list the basis at each pivot step
and explain why this pivot step happens. Do not perform any calculations, but explain everything
geometrically.
x2 = 0
x1 = 0
x3 = 0
x5 = 0
x4 = 0
page 2/5
COMP331/557 – Class Test – 2020-Nov-25/26
Task 3 [2 marks]
Consider the following linear program:
max 5 +4x1 −3x2 +6x3
x4 = 4 −x1 −x2
x5 = 6 −x2 −x3
x6 = 6 −x3
x1, x2, x3, x4, x5, x6 ≥ 0
From this dictionary we see that the basic feasible solution to the basis (4, 5, 6) is
(x1, x2, x3, x4, x5, x6) = (0, 0, 0, 4, 6, 6).
What is the basic feasible solution to the basis (1, 2, 3)? Explain all your steps!
page 3/5
COMP331/557 – Class Test – 2020-Nov-25/26
Task 4 [2 marks]
Consider the following linear program:
max 4x1 −3x2 +6x3
x1 +x2 ≤ −4
x2 +x3 ≤ −6
x3 ≤ 6
x1, x2, x3 ≥ 0
We discussed two different two-phase simplex methods. For both methods, write down the linear
program that is solved in phase 1.
page 4/5
COMP331/557 – Class Test – 2020-Nov-25/26
Task 5 [2 marks]
For a linear program exactly one of the following three things is true:
• The linear program has a finite optimum.
• The linear program is unbounded.
• The linear program is infeasible.
Choose three entries from the following table and explain why they are correct.
primal LP has finite optimum primal LP unbounded primal LP infeasible
dual LP has finite optimum possible impossible impossible
dual LP unbounded impossible impossible possible
dual LP infeasible impossible possible possible
page 5/5

欢迎咨询51作业君