MA 3231
Linear Programming
Assignment 3
1. Consider the linear program
max z = 6x1 + 10x2
subject to
x1 + 2x2 ≤ 5
x1 ≤ 3
2x2 ≤ 4
x1, x2 ≥ 0
Compare the efficiency of the implementation of the simplex algorithm if
a) You are using the largest positive coefficient for the entering variable (and the
lexicographic method for the leaving)
b) You are using Bland’s rule
2. Consider the following linear programming problem:
max z = 4x1 − 6x2 + 2x3 + 12x4
subject to
3x1 + 5x2 + 4x3 ≤ 20
2x1 − x3 + x4 ≤ 15
3x2 + 2x3 + 5x4 ≤ 30
x1, x2, x3, x4 ≥ 0
Find the dual program to this linear program.
2
3. Consider the following dual linear programming problem:
min ξ = 6y1 + 2y2 + 4y3
subject to
2y1 + 3y2 − y3 ≥ 5
−y1 + 4y3 ≥ 10
2y1 + 4y2 ≥ 14
3y1 − 2y3 ≥ 7
y1, y2, y3 ≥ 0
a) Rewrite the problem in standard form.
b) What is the primal problem corresponding to this dual linear program?
4. Write a MATLAB code which lets you solve both the primal and the dual linear
program for different input coefficients aij , bi
, cj
for i = 1, . . . , 4 and j = 1, . . . , 4 (You
already have the code for the primal LP given a constraint matrix A = (aij ), objective
coefficient vector f = (c1, . . . , cn), and constraint vector b = (b1, . . . , bm). So you just
have to figure out what matrices and vectors to plug into the linprog function when you
want to find the dual of this LP).
Using your MATLAB code, try solving different linear programs (and their dual LPs)
with different values for the coefficients, in order to find an answer to the following
questions:
– If both the primal and the dual problem have optimal solutions, how do they
compare?
– If the primal problem is infeasible, what is happening with the dual problem?
– If the primal problem is unbounded, what is happening with the dual problem?
– If the dual problem is infeasible, what is happening with the primal problem?
– If the dual problem is unbounded, what is happening with the primal problem?
