SYS 6003

Homework #3

Problem 1:

Given the following linear program with the corresponding optimal basis, for what

range of values of the objective function for each variable (considered one at a

time) will the basis still be optimal? You must consider both the basic and non-basic

variables in your answer.

Remember, the “certificate of optimality” says that for a basis to be optimal, all

non-basic variables must have non-negative reduced cost.

For example, if you replaced the cost coefficient of variable a in the first problem

(a) with some value $, for what values of $ would this basis still be optimal? What

if you replaced the cost coefficients of b? c? d? etc.

a)

A: 1 0 5 2 b: 30

0 2 1 3 60

c: 1 1 20 50

Optimal basis: {a, b}

b)

A: 1 0 5 2 b: 30

0 2 1 3 60

c: 0 0 2 5

Optimal basis: {a, b}

SYS 6003

Homework #3

Problem 2:

Given the following linear program with the corresponding feasible basis, for what

range of value of the right-hand side for each constraint (considered one at a time)

will the basis still be feasible?

So, for example, if you replaced the right-hand side of constraint 1 in the first

problem with some value R, for what values of R would this basis still be feasible?

What if you replaced the second constraint?

a)

A: 1 0 5 2 b: 30

0 2 1 3 60

Feasible basis: {a, b}

b)

A: 1 0 5 2 b: 20

0 -2 1 3 3

Feasible basis: {a, c}

SYS 6003

Homework #3

Problem 3:

Form the dual of each of the following linear programs:

a) Min 3x + 2y – z

St: x – y > 4

2x + z > 5

x + y + z > 1

x, y, z > 0

b) Min 2x + 4z

St: x – z > 2

y > 4

x, y, z > 0

c) Hint: this Dual Problems is more challenging than it might first appear. Pay close

attention to the variable restriction constraints.

Max 2x + 3y – z

St: x = z

x + 2y > 4

x, y > 0

SYS 6003

Homework #3

Problem 4:

Consider the following primal linear program:

min a + b + c + d

St: a + 2c +4d ≥ 4 (1)

b + 3d ≥ 6 (2)

a, b, c, d ≥ 0

a) Write the dual of this linear program.

b) Please write all complementary slackness conditions for the primal and dual.

c) Using complementary slackness, prove that a=0, b=0, c=0, and d=2 is the

optimal solution to the primal problem, and please solve for the values of

the optimal dual basis.

d) Based on your solution to part c for this problem, would you be willing to pay

1 unit to relax the right-hand side of the second constraint right hand side by

1 unit? Please explain why or why not?