Linear Program

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?