[Solved] MA3231 Homework 3

1. Consider the linear program maxz = 6x₁ + 10x₂

subject to

x₁ + 2x₂ 5 x₁ 3 2x₂ 4 x₁, x₂ 0

Compare the efficiency of the implementation of the simplex algorithm if

1. You are using the largest positive coefficient for the entering variable (and the lexicographic method for the leaving)
2. You are using Blands rule

2. Consider the following linear programming problem:

maxz = 4x₁ 6x₂ + 2x₃ + 12x₄

subject to

3x₁ + 5x₂ + 4x₃ 20 2x₁ x₃ + x₄ 15 3x₂ + 2x₃ + 5x₄ 30 x₁, x₂, x₃, x₄ 0

Find the dual program to this linear program.

2

3. Consider the following dual linear programming problem:

min = 6y₁ + 2y₂ + 4y₃

subject to

2y₁ + 3y₂ y₃ 5

y₁ + 4y₃ 10

2y₁ + 4y₂ 14 3y₁ 2y₃ 7 y₁, y₂, y₃ 0

1. Rewrite the problem in standard form.
2. 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 a_ij, b_i, c_j for i = 1,,4 and j = 1,,4 (You already have the code for the primal LP given a constraint matrix A = (a_ij), objective coefficient vector f = (c₁,,c_n), and constraint vector b = (b₁,,b_m). 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?