Starting from:

$25

MA3231-Assignment 2 Solved

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

maxz = αx1 + 2x2 − x3

subject to

2x1 − x2 + 3x3 ≤ 4

−x1 + x2 − 2x3 ≤ 8 3x1 − 3x3 ≤ 2 x1, x2, x3 ≥ 0

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

maxz = x1 + 3x2

subject to

−x1 − x2 ≤−3 −x1 + x2 ≤−1 x1 + 2x2 ≤ 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).

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

maxz = 2x1 + 3x2 + 4x3

subject to

−2x2 − 3x3 ≤−5 x1 + x2 + 2x3 ≤ 4 x1 + 2x2 + 3x3 ≤ 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
−2x2
 
 
 
 
 
x1
=
3
 
−2x2
w2
=
1
+w1
−2x2
Hint: If it could, what was the original problem from whence it came?

5.    Consider the following linear programming problem:

maxz = 2x1 − 3x2 + 2x3 + 12x4

subject to

4x1 + 5x2 + 2x3 ≤ 10

2x1 − x3 + x4 ≤ 30 4x2 + 2x3 + 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

2x2

 
 
 

2x4
w1
=
 

0.5x1
+
3.5x2
+
2x3

4x4
w2
=
 

0.5x1
+
x2
+
0.5x3

0.5x4
w3
=
1

x1
 
 
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:

maxz = 2x1 + 3x2 + 4x3

subject to

4x1 − x2 ≤ 0

−x1 + x3 ≤ 0 2x2 − 3x3 ≤ 0 x1, x2, x3 ≥ 0

How about Bland’s rule?

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

maxz = 3x1 + 2x2

subject to

x1 − x2 ≤−1 x1 + x2 ≤ 2 x1, x2 ≥ 0

More products