Homework

Answer please.

1. Consider the linear program.

Maximize z = 2x1 + 3x2 + x3 + 4x4
subject to x1 每 x3 + x4 ≒ 5
每x1 + 2x2 + x4 ≒ 6
x2 + 2x3 + 0.5x4 ≒ 8
0 ≒ xj ≒ 1, j = 1, 2, 3, 4

After several pivots the simplex tableau appears as below, where x5, x6 and x7 are the slack variables for the three constraints.

a. What is the basic solution described by the tableau? Give the values of all variables and the objective function.
b. Without performing a pivot, predict the solution that would be obtained if x5 were to enter the basis. Use the usual rule to determine the leaving variable.
c. Without performing a pivot predict the solution that would be obtained if x5 were to enter the basis. Let the leaving variable be x6.
d. Write the equation described by row 3 in the tableau.
e. What variable should enter the basis to obtain the greatest total increase in the objec-tive at the next iteration?
f. Using the "most negative reduced cost" rule to determine the entering variable, what variables will enter and leave the basis at the next iteration?
g. Let x7 enter the basis and select the variable to leave the basis that assures the next solution will be feasible. Perform a pivot and show the new tableau.
1. Consider the linear program given below.

Minimize z = 2x1 + x2
subject to 每x1 + 2x2 ≒ 10
x1 每 2x2 ≒ 4
x1 + x2 ≡ 8
x1 + 2x2 ≒ 20
x1 ≡ 0, x2 ≡ 0

a. Show the equality form of the model.
b. Give an upper bound on the number of basic solutions for this problem.
c. What selection of basic variables will cause the first and third constraints to be tight? Give values to the variables for this basic solution?
d. For which set of basic variables is there no solution to the model in equality form?
e. If the two-phase method is to be used to find a solution, construct the first tableau for the computations. The tableau should be in the simplex form.


2. When solving a linear programming to optimality, how do you determine that
a) The program has a unique optimal solution






b) The problem has multiple optimal solutions