首页 >
> 详细

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

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- 代写 Lab 2: Threads 2022-05-10
- 辅导assessment 1. Present Your Client ... 2022-05-10
- 5Cce2sas辅导、Python，Java程序辅导 2022-05-10
- 代写brae Webb编程 2022-05-09
- 辅导csci 3110 Assignment 1 2022-05-09
- Mth2222 Assignment 2代写 2022-05-09
- Cse3bdc Assignment 2022辅导 2022-05-08
- 辅导cis 468、辅导java，Python编程 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- 讲解assignment 2: Databases 2022-04-25
- 辅导ait681 Static Analysis 2022-04-25
- Cse121 & Cse121l 编程辅导、辅导c++程序语言 2022-04-25
- 辅导iti1120 Bject-Oriented Programming 2022-04-25
- Cmt304语言辅导、辅导c++，Python编程 2022-04-25
- 辅导comp/Engn4528 Computer Vision 2022-04-24
- 辅导fin 2200 Bloomberg Investment Proj... 2022-04-24
- 辅导bism 7255 Uml Assignment 2022-04-23
- 讲解comp202 Programming Assignment 2022-04-23