Objective 1: Identify problems for which a linear program is an appropriate means of solution and formulate the linear program.
Objective 2: Given a nonbasic feasible solution to a linear program, determine a basic solution with at least as great a value of the objective function by adding a vector in the appropriate nullspace to the given nonbasic solution.
Objective 3: Solve a maximizing linear program using the simplex algorithm.
Objective 4: Demonstrate individual rules of the simplex algorithm as discussed in Section 3.3 using given simplex tableaus.
Objective 5: Recognize a degenerate basic solution, and understand how a degenerate solution arises from a tie for the minimum replacement quantity.
Objective 6: Solve a maximizing linear program having nonstandard constraints by the two-phase method.
Objective 7: Solve linear program involving unrestricted variables by expressing each unrestricted variable as the difference of two nonnegative variables.
Example 1: In this simplex tableau below, several variables are candidates to become basic in the next solution.
| x_1 | x_2 | x_3 | s_1 | s_2 | s_3 | s_4 | |
|---|---|---|---|---|---|---|---|
| 5 | 1 | 0 | 1 | 0 | 0 | -3 | 40 |
| 2 | 0 | 0 | 1/2 | 1 | 0 | 2 | 18 |
| 1/2 | 0 | 0 | -4/3 | 0 | 1 | 3 | 12 |
| 1 | 0 | 1 | 2/3 | 0 | 0 | 1/2 | 24 |
| -5 | 0 | 0 | -2 | 0 | 0 | -6 | 245 |
Which variable should be made basic in the next solution if the goal is
- For the new value of the objective function to be 285?
- For the next solution to be degenerate?
- To have s_3 be zero in the next solution?
- To achieve the greatest increase in the value of the objective function?
- To achieve the greatest increase in the objective function per unit increase in the new basic variable?
Solution: There are three non-basic variables x_1, s_1, s_4 that can be made basic.
Case 1: Choose x_1 as the entering variable. The replacement quantities are 40/5 = 8, 18/2=9, 12/(1/2) = 24, 24/1=24. The increment in x_1 is 8 (the smallest replacement quantity) and the increment in the objective function is 8\times 5 = 40(note 5 comes from row 5 col 1), which yields the new value of objective function to be 285. This answers the 1st subproblem.
Case 2: Choose s_1. The replacement quantities are 40/1 = 40, 18/(1/2) = 36, 24/(2/3) = 36. The tie among the smallest replacement quantities means that the next solution is degenerate. This answers the 2nd subproblem. The increment in s_1 is 36 and the increment in the objective function is 36\times 2=72 (note 2 comes from row 5 col 4).
Remark: A basic solution is called degenerate if at least one of the basic variables is 0. A convenient criteria for discovering a degenerate solution is to see if there is a tie among the smallest replacement quantities.
Case 3: Choose s_4. The replacement quantities are 18/2 = 9, 12/3 = 4, 24 / (1/2) = 48. The pivot is at row 3 col 7, which means s_3 is the departing variable (the basic-turned-into-nonbasic variable), and will be zero in the next solution. This answers the 3rd subproblem. The increment in s_4 is 4 and the increment in the objective function is 4\times 6 = 24.
Overall, when s_1 is made basic in the next solution, the greatest increase in the value of the objective function as well as the per unit increase in the new basic variable is achieved. This answers the last two subproblems.
Example 2: Determine the initial simplex tableau for the linear program below:
Maximize: 4x_1 + 3x_2 - x_3.
Subject to: x_1 + x_2 + x_3 = 100, 2x_1 + 2x_2 + x_3 \le 200, 4x_2 + 3x_3 \ge 50, -5x_1 + 2x_2 \ge 40, x_1 \ge 0, x_2 \ge 0, x_3 \text{ unrestricted}.
Solution: As x_3 is unrestricted, we use x_3 = w_1 - w_2, where w_1, w_2 are both nonnegative, to replace x_3. This results the new linear program:
Maximize: 4x_1 + 3x_2 - w_1 + w_2.
Subject to: x_1 + x_2 + w_1 - w_2 = 100, 2x_1 + 2x_2 + w_1 - w_2 \le 200, 4x_2 + 3w_1 - 3w_2 \ge 50, -5x_1 + 2x_2 \ge 40, x_1 \ge 0, x_2 \ge 0, w_1 \ge 0, w_2 \ge 0.
First, adding a slack variable s_2 and two surplus variables s_3, s_4, we get constraints:
x_1 + x_2 + w_1 - w_2 = 100, 2x_1 + 2x_2 + w_1 - w_2 + s_2 = 200, 4x_2 + 3w_1 - 3w_2 - s_3 = 50, -5x_1 + 2x_2 - s_4 = 40, x_1 \ge 0, x_2 \ge 0, w_1 \ge 0, w_2 \ge 0.
Adding artificial variables a_1, a_3, a_4, we get constraints:
x_1 + x_2 + w_1 - w_2 + a_1 = 100, 2x_1 + 2x_2 + w_1 - w_2 + s_2 200, 4x_2 + 3w_1 - 3w_2 - s_3 + a_3 = 50, -5x_1 + 2x_2 - s_4 + a_4 = 40, x_1 \ge 0, x_2 \ge 0, w_1 \ge 0, w_2 \ge 0.
Note that you only add artificial variables for constraints which do not have slack variables. The artificial objective function is \begin{aligned}-a_1-a_3-a_4 &= x_1 + x_2 + w_1 - w_2 - 100 + 4x_2 + 3w_1 - 3w_2 - s_3 - 50 - 5x_1 + 2x_2 - s_4 - 40 \\ &= -4x_1 + 7x_2 + 4w_1 - 4w_2 - s_3 - s_4 - 190.\end{aligned}
The initial simplex tableau for the linear program is
| x_1 | x_2 | w_1 | w_2 | s_2 | s_3 | s_4 | a_1 | a_3 | a_4 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 100 |
| 2 | 2 | 1 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 200 |
| 0 | 4 | 3 | -3 | 0 | -1 | 0 | 0 | 1 | 0 | 50 |
| -5 | 2 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 40 |
| -4 | -3 | 1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | -7 | -4 | 4 | 0 | 1 | 1 | 0 | 0 | 0 | -190 |
where the last two rows are the objective row and the artificial objective row.
More examples:
- Section 3.3 nos. 4, 5;
- Section 3.4 nos. 4, 11, 12;
- Section 3.5 nos. 4, 6 – 11;
- Section 3.6 nos. 3, 12, 15.
Note: The most important question will be a formulation problem.