代写COMP331、c++，Python程序代写

日期：2021-11-12 10:16

COMP331/557 – Class Test – 2021-Nov-09/10

Class Test. This is worth 15% of your grade.

Due date: Wednesday, November 10th, 2021, 12:00 noon, via SAM as a single .pdf file.

(https://sam.csc.liv.ac.uk/COMP/Submissions.pl?strModule=COMP331 or

https://sam.csc.liv.ac.uk/COMP/Submissions.pl?strModule=COMP557)

Photos of handwritten solutions are permitted as long as the submission is a .pdf file.

Explain your solutions! The use of linear programming software is not permitted.

Task 1 [20 marks]

A manufacturer has three machines that each can produce the same product, but they all use different

resources for the task:

Machine X uses 0.9 metric tons of iron and 1.5 metric tons of copper to produce 2.5 metric tons

of the product.

Machine Y uses 2 metric tons of iron and 0.5 metric tons of nickel to produce 2 metric tons of the

product.

Machine Z uses 3 metric tons of copper and 0.1 metric tons of nickel to produce 3 metric tons of

the product.

The manufacturer has 50 metric tons of iron, 50 metric tons of copper, and 50 metric tons of nickel, and

wants to maximise the production of the product.

(a) Write down the corresponding linear program in standard form.

(b) Introduce slack variables and find an initial feasible primal dictionary to run the primal simplex

algorithm, but do not actually run the algorithm!

page 1/5

COMP331/557 – Class Test – 2021-Nov-09/10

Task 2 [20 marks]

The following figure is a graphical presentation of a linear program in standard form with slack variables

x3, x4, x5, and x6. 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 ζ = ?x1, i.e., we want to find the leftmost point

in the feasible region. We use Bland’s rule as the pivoting rule. We start the simplex algorithm with

basis (1, 2, 5, 6).

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 computations, but explain everything

geometrically.

x1 = 0

x2 = 0

x3 = 0

x4 = 0

x5 = 0x6 = 0

page 2/5

COMP331/557 – Class Test – 2021-Nov-09/10

Task 3 [20 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).

Perform one pivot step of the simplex algorithm and write down the basic feasible solution after the pivot

step.

page 3/5

COMP331/557 – Class Test – 2021-Nov-09/10

Task 4 [20 marks]

Consider the following linear program:

max 4x1 ?3x2 +6x3

x1 +x2 ≤ ?4

x2 +x3 ≤ ?6

x3 ≤ 6

x1, x2, x3 ≥ 0

Write down the linear program that needs to be solved in phase 1 of the two-phase simplex algorithm

(not the dual two-phase simplex algorithm, but the first two-phase simplex algorithm we discussed).

Then take that linear program and write it in dictionary notation, perform the very first pivot step, and

in this way determine the first basic feasible solution for phase 1.

Do not solve the linear program!

page 4/5

COMP331/557 – Class Test – 2021-Nov-09/10

Task 5 [20 marks]

Determine the dual linear program for the following primal linear program:

max 12x1 ?10x2

subject to ?4x1 +3x2 ≤ 10

4x1 ?3x2 ≤ 20

x1 +4x2 ≤ 30

x1, x2 ≥ 0

Do not solve the linear program!

page 5/5