[Solved] MA3231 Homework 2

1. Solve the following linear program using the simplex algorithm:

maxz = 10x₁ + 6x₂ + 4x₃

subject to

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

2. Solve the following linear program using the simplex algorithm: (careful: is this linear program in standard form?)

minz = 7x₁ 8x₂

subject to

4x₁ + x₂ 100 2x₁ 2x₂ 160 x₁ 40 x₁, x₂ 0

Draw the region of feasible solution to this problem and indicate the solution you get at each step of the simplex algorithm.

2

3. Solve the following linear program using the simplex algorithm and a suitable auxiliary program:

maxz = 2x₁ + 6x₂

subject to

x₁ x₂ 3 3x₁ + 3x₂ 3 x₁ + 2x₂ 2 x₁, x₂ 0 optional: Use the graphical method to find the region of feasible solutions.

4. Solve the following linear program using the simplex algorithm and a suitable auxiliary program: (careful: is this linear program in standard form?)

minz = 2x₁ 3x₂ 4x₃

subject to

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

5. Explain why the following dictionary cannot be the optimal dictionary for any linear programming problem in which w₁ and w₂ are the initial slack variables:

Hint: If it could, what was the original problem from which it came?