# Recitation 4

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.