代写MAST20018、代写Java,C/C++编程

日期：2022-10-23 12:13

MAST20018 – Introduction to Discrete Mathematics and Operations Research

Assignment 4

1. Is the following tableau optimal

x1 x2 x3 x4 x5 RHS

x2 0 1 0 1/6 0 2/3

x3 2 0 1 1/2 0 10

x5 1 0 0 5/2 1 19

z 4 0 0 31 0 460

under the circumstances below? If it is optimal, also state the value of the optimal objective

function.

(a) The problem is a minimisation problem and the z-row of the tableau was initialised with

the cost vector (ct).

(b) The problem is a maximisation problem and the z-row of the tableau was initialised with

the cost vector (ct).

(c) The problem is a minimisation problem and the z-row of the tableau was initialised with

the negative of the cost vector (?ct).

(d) The problem is a maximisation problem and the z-row of the tableau was initialised with

the negative of the cost vector (?ct).

2. Consider the linear program

max 5x + y

s.t.

x + y ≤ 7

x? y ≤ 3

x, y ≥ 0

(a) Derive the dual linear program.

(b) Plot the feasible regions to both the primal and the dual problems.

(c) Solve the primal problem using the simplex method. In each iteration, indicate on the

graphs both the current primal basic feasible solution and its corresponding dual solution.

1

MAST20018 – Introduction to Discrete Mathematics and Operations Research

3. The simplex method is a typically efficient algorithm for solving linear programs. However,

there is no version of it that has been shown theoretically to solve any linear program in

polynomial time. In fact, it is much worse. In 1972, Klee and Minty came up with an example

in n dimensions that requires 2n ? 1 iterations if Dantzig’s rule1 is used to choose entering

variables. These problems are of the form

max

n∑

j=1

10n?jxj

s.t.

2

(

i?1∑

j=1

10i?jxj

)

+ xi ≤ 100i?1, i ∈ {1, 2, . . . , n}

xj ≥ 0, j ∈ {1, 2, . . . , n}.

(a) Write the problem for n = 3.

(b) Solve the problem using Dantzig-rule.

1For a maximisation problem, Dantzig’s rule asks to select as entering variable the non-basic variable with largest

reduced cost.