MA 3231

Linear Programming

Section E162

Assignment 2

Content: up to Section 2.12

1. Find all the values of the parameter α such that the following linear program has a

finite optimal solution:

max z = αx1 + 2×2 − x3

subject to

2×1 − x2 + 3×3 ≤ 4

−x1 + x2 − 2×3 ≤ 8

3×1 − 3×3 ≤ 2

x1, x2, x3 ≥ 0

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

program:

max z = x1 + 3×2

subject to

−x1 − x2 ≤ −3

−x1 + x2 ≤ −1

x1 + 2×2 ≤ 2

x1, x2 ≥ 0

Draw the region of feasible solution to this problem and indicate the solution you get at

each step of the simplex algorithm (only for the original problem, i.e., Phase II).

2

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

program:

max z = 2×1 + 3×2 + 4×3

subject to

−2×2 − 3×3 ≤ −5

x1 + x2 + 2×3 ≤ 4

x1 + 2×2 + 3×3 ≤ 7

x1, x2, x3 ≥ 0

4. Show that the following dictionary cannot be the optimal dictionary for any linear

programming problem in which w1 and w2 are the initial slack variables:

z = 4 −w1 −2×2

x1 = 3 −2×2

w2 = 1 +w1 −2×2

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

5. Consider the following linear programming problem:

max z = 2×1 − 3×2 + 2×3 + 12×4

subject to

4×1 + 5×2 + 2×3 ≤ 10

2×1 − x3 + x4 ≤ 30

4×2 + 2×3 + x4 ≤ 20

x1, x2, x3, x4 ≥ 0

Solve it numerically using the built-in simplex algorithm of a spreadsheet program (such

as MS Excel). Please just submit the .xlsx file as submission comment to your

homework on Canvas.

6. Reconsider the degenerate dictionary of Lecture 2.8 that led to the cycling issue:

z = x1 − 2×2 − 2×4

w1 = − 0.5×1 + 3.5×2 + 2×3 − 4×4

w2 = − 0.5×1 + x2 + 0.5×3 − 0.5×4

w3 = 1 − x1

3

Write down the corresponding linear programming problem and find the optimal

solution by using

a) the lexicographic method (comment on the choice of the entering variable).

b) Bland’s rule

8 points per problems

Problems to be discussed in the Office Hours

1. Solve the following linear program using the lexicographic method to avoid degeneracy:

max z = 2×1 + 3×2 + 4×3

subject to

4×1 − x2 ≤ 0

−x1 + x3 ≤ 0

2×2 − 3×3 ≤ 0

x1, x2, x3 ≥ 0

How about Bland’s rule?

2. Solve the following linear programming problem by initializing it with an auxiliary

program.

max z = 3×1 + 2×2

subject to

x1 − x2 ≤ −1

x1 + x2 ≤ 2

x1, x2 ≥ 0

MA 3231

# Linear Programming Section E162 Assignment 2 SOLVED

Original price was: $35.00.$30.00Current price is: $30.00.

## Reviews

There are no reviews yet.