1. Consider the linear program maxz = 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:
maxz = 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?
