29.5 The initial basic feasible solution

29.5-1

Give detailed pseudocode to implement lines 5 and 14 of $\text{INITIALIZE-SIMPLEX}$.

For line 5, first let $(N, B, A, b, c, v)$ be the result of calling $\text{PIVOT}$ on $L_{aux}$ using $x_0$ as the entering variable. Then repeatedly call $\text{PIVOT}$ until an optimal solution to $L_{aux}$ is obtained, and return this to $(N, B, A, b, c, v)$. To remove $x_0$ from the constraints, set $a_{i, 0} = 0$ for all $i \in B$, and set $N = N \backslash \{0\}$. To restore the original objective function of $L$, for each $j \in N$ and each $i \in B$, set $c_j = c_j − c_ia_{ij}$.

29.5-2

Show that when the main loop of $\text{SIMPLEX}$ is run by $\text{INITIALIZE-SIMPLEX}$, it can never return "unbounded."

In order to enter line 10 of $\text{INITIALIZE-SIMPLEX}$ and begin iterating the main loop of $\text{SIMPLEX}$, we must have recovered a basic solution which is feasible for $L_{aux}$. Since $x_0 \ge 0$ and the objective function is $−x_0$, the objective value associated to this solution (or any solution) must be negative. Since the goal is to aximize, we have an upper bound of $0$ on the objective value. By Lemma 29.2, $\text{SIMPLEX}$ correctly determines whether or not the input linear program is unbounded. Since $L_{aux}$ is not unbounded, this can never be returned by $\text{SIMPLEX}$.

29.5-3

Suppose that we are given a linear program $L$ in standard form, and suppose that for both $L$ and the dual of $L$, the basic solutions associated with the initial slack forms are feasible. Show that the optimal objective value of $L$ is $0$.

Since it is in standard form, the objective function has no constant term, it is entirely given by $\sum_{i = 1}^n c_ix_i$, which is going to be zero for any basic solution. The same thing goes for its dual. Since there is some solution which has the objective function achieve the same value both for the dual and the primal, by the corollary to the weak duality theorem, that common value must be the optimal value of the objective function.

29.5-4

Suppose that we allow strict inequalities in a linear program. Show that in this case, the fundamental theorem of linear programming does not hold.

Consider the linear program in which we wish to maximize $x_1$ subject to the constraint $x_1 < 1$ and $x_1 \ge 0$. This has no optimal solution, but it is clearly bounded and has feasible solutions. Thus, the Fundamental theorem of linear programming does not hold in the case of strict inequalities.

29.5-5

Solve the following linear program using $\text{SIMPLEX}$:

$$ \begin{array}{lrcrcrl} \text{maxmize} & x_1 & + & 3x_2 \\ \text{subject to} & \\ & x_1 & - & x_2 & \le & 8 \\ & -x_1 & - & x_2 & \le & -3 \\ & -x_1 & + & 4x_2 & \le & 2 \\ & & x_1, x_2 & & \ge & 0 & . \end{array} $$

The initial basic solution isn't feasible, so we will need to form the auxiliary linear program,

$$ \begin{array}{lrcrcrcrl} \text{maxmize} & -x_0 \\ \text{subject to} & \\ & -x_0 & + & x_1 & - & x_2 & \le & 8 \\ & -x_0 & - & x_1 & - & x_2 & \le & -3 \\ & -x_0 & - & x_1 & + & 4x_2 & \le & 2 \\ & & x_0, x_1, x_2 & & & & \ge & 0 & . \end{array} $$

Writing this linear program in slack form,

$$ \begin{array}{rcrcrcrcr} z & = & & - & x_0 \\ x_3 & = & 8 & + & x_0 & - & x_1 & + & x_2 \\ x_4 & = & -3 & + & x_0 & + & x_1 & + & x_2 \\ x_5 & = & 2 & + & x_0 & + & x_1 & - & 4x_2 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

Next we make one call to $\text{PIVOT}$ where $x_0$ is the entering variable and $x_4$ is the leaving variable.

$$ \begin{array}{rcrcrcrcr} z & = & -3 & + & x_1 & + & x_2 & - & x_4 \\ x_0 & = & 3 & - & x_1 & - & x_2 & + & x_4 \\ x_3 & = & 11 & - & 2x_1 & & & + & x_4 \\ x_5 & = & 5 & & & - & 5x_2 & + & x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

The basic solution is feasible, so we repeatedly call $\text{PIVOT}$ to get the optimal solution to $L_{aux}$. We'll choose $x_1$ to be our entering variable and $x_0$ to be the leaving variable. This gives

$$ \begin{array}{rcrcrcrcr} z & = & & & -x_0 \\ x_1 & = & 3 & - & x_0 & - & x_2 & + & x_4 \\ x_3 & = & 5 & + & 2x_0 & + & 2x_2 & - & x_4 \\ x_5 & = & 5 & & & - & 5x_2 & + & x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

The basic solution is now optimal for $L_{aux}$, so we return this slack form to $\text{SIMPLEX}$, set $x_0 = 0$, and update the objective function which yields

$$ \begin{array}{rcrcrcr} z & = & 3 & + & 2x_2 & + & x_4 \\ x_1 & = & 3 & - & x_2 & + & x_4 \\ x_3 & = & 5 & + & 2x_2 & - & x_4 \\ x_5 & = & 5 & - & 5x_2 & + & x_4 \\ x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

We'll choose $x_2$ as our entering variable, which makes $x_5$ our leaving variable. $\text{PIVOT}$ then gives,

$$ \begin{array}{rcrcrcr} z & = & 5 & + & (7 / 5)x_4 & - & (2 / 5)x_5 \\ x_1 & = & 2 & + & (1 / 5)x_4 & + & (1 / 5)x_5 \\ x_2 & = & 1 & + & (4 / 5)x_4 & - & (1 / 5)x_5 \\ x_3 & = & 7 & - & (3 / 5)x_4 & - & (2 / 5)x_5 \\ x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

We'll choose $x_4$ as our entering variable, which makes $x_3$ our leaving variable. $\text{PIVOT}$ then gives,

$$ \begin{array}{rcrcrcr} z & = & (64 / 3) & - & (7 / 3)x_3 & - & (4 / 3)x_5 \\ x_1 & = & (34 / 3) & - & (4 / 3)x_3 & - & (1 / 3)x_5 \\ x_2 & = & (10 / 3) & - & (1 / 3)x_3 & - & (1 / 3)x_5 \\ x_4 & = & (35 / 3) & - & (5 / 3)x_3 & - & (2 / 3)x_5 \\ x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

Now all coefficients in the objective function are negative, so the basic solution is the optimal solution. It is $(x_1, x_2) = (34 / 3, 10 / 3)$.

29.5-6

Solve the following linear program using $\text{SIMPLEX}$:

$$ \begin{array}{lrcrcrl} \text{maxmize} & x_1 & - & 2x_2 \\ \text{subject to} & \\ & x_1 & + & 2x_2 & \le & 4 \\ & -2x_1 & - & 6x_2 & \le & -12 \\ & & & x_2 & \le & 1 \\ & & x_1, x_2 & & \ge & 0 & . \end{array} $$

The initial basic solution isn't feasible, so we will need to form the auxiliary linear program,

$$ \begin{array}{lrcrcrcrl} \text{maxmize} & -x_0 \\ \text{subject to} & \\ & -x_0 & + & x_1 & + & 2x_2 & \le & 4 \\ & -x_0 & - & 2x_1 & - & 6x_2 & \le & -12 \\ & -x_0 & & & + & x_2 & \le & 1 \\ & & x_0, x_1, x_2 & & & & \ge & 0 & . \end{array} $$

Writing this linear program in slack form,

$$ \begin{array}{rcrcrcrcr} z & = & & - & x_0 \\ x_3 & = & 4 & + & x_0 & - & x_1 & - & 2x_2 \\ x_4 & = & -12 & + & x_0 & + & 2x_1 & + & 6x_2 \\ x_5 & = & 1 & + & x_0 & & & - & x_2 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

Next we make one call to $\text{PIVOT}$ where $x_0$ is the entering variable and $x_4$ is the leaving variable.

$$ \begin{array}{rcrcrcrcr} z & = & -12 & + & 2x_1 & + & 6x_2 & - & x_4 \\ x_0 & = & 12 & - & 2x_1 & - & 6x_2 & + & x_4 \\ x_3 & = & 16 & - & 3x_1 & - & 8x_2 & + & x_4 \\ x_5 & = & 13 & - & 2x_1 & - & 8x_2 & + & x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

The basic solution is $(x_0, x_1, x_2, x_3, x_4, x_5) = (12, 0, 0, 16, 0, 13)$ which is feasible for the auxiliary program. Now we need to run $\text{SIMPLEX}$ to find the optimal objective value to $L_{aux}$. Let $x_1$ be our next entering variable. It is most constrained by $x_3$, which will be our leaving variable. After $\text{PIVOT}$, the new linear program is

$$ \begin{array}{rcrcrcrcr} z & = & -(4 / 3) & + & (2 / 3)x_2 & - & (2 / 3)x_3 & + & (1 / 3) x_4 \\ x_0 & = & (4 / 3) & - & (2 / 3)x_2 & + & (2 / 3)x_3 & + & (1 / 3) x_4 \\ x_1 & = & (16 / 3) & - & (8 / 3)x_2 & - & (1 / 3)x_3 & + & (1 / 3) x_4 \\ x_5 & = & (7 / 3) & - & (8 / 3)x_2 & + & (2 / 3)x_3 & + & (1 / 3) x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

Every coefficient in the objective function is negative, so we take the basic solution $(x_0, x_1, x_2, x_3, x_4, x_5) = (4 / 3, 16 / 3, 0, 0, 0, 7 / 3)$ which is also optimal. Since $x_0 \ne 0$, the original linear program must be unfeasible.

29.5-7

Solve the following linear program using $\text{SIMPLEX}$:

$$ \begin{array}{lrcrcrl} \text{maxmize} & x_1 & + & 3x_2 \\ \text{subject to} & \\ & -x_1 & + & x_2 & \le & -1 \\ & -x_1 & - & x_2 & \le & -3 \\ & -x_1 & + & 4x_2 & \le & 2 \\ & & x_1, x_2 & & \ge & 0 & . \end{array} $$

The initial basic solution isn't feasible, so we will need to form the auxiliary linear program,

$$ \begin{array}{lrcrcrcrl} \text{maxmize} & -x_0 \\ \text{subject to} & \\ & -x_0 & - & x_1 & + & x_2 & \le & -1 \\ & -x_0 & - & x_1 & - & x_2 & \le & -3 \\ & -x_0 & - & x_1 & + & 4x_2 & \le & 2 \\ & & x_0, x_1, x_2 & & & & \ge & 0 & . \end{array} $$

Writing this linear program in slack form,

$$ \begin{array}{rcrcrcrcr} z & = & & - & x_0 \\ x_3 & = & -1 & + & x_0 & + & x_1 & - & x_2 \\ x_4 & = & -3 & + & x_0 & + & x_1 & + & x_2 \\ x_5 & = & 2 & + & x_0 & + & x_1 & - & 4x_2 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

Next we make one call to $\text{PIVOT}$ where $x_0$ is the entering variable and $x_4$ is the leaving variable.

$$ \begin{array}{rcrcrcrcr} z & = & -3 & + & x_1 & + & x_2 & - & x_4 \\ x_0 & = & 3 & - & x_1 & - & x_2 & + & x_4 \\ x_3 & = & 2 & & & - & 2x_2 & + & x_4 \\ x_5 & = & 5 & & & - & 5x_2 & + & x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

Let $x_1$ be our entering variable. Then $x_0$ is our leaving variable, and we have

$$ \begin{array}{rcrcrcrcr} z & = & & - & x_0 \\ x_1 & = & 3 & - & x_0 & - & x_2 & + & x_4 \\ x_3 & = & 2 & & & - & 2x_2 & + & x_4 \\ x_5 & = & 5 & & & - & 5x_2 & + & x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

The basic solution is feasible, and optimal for $L_{aux}$, so we return this and run $\text{SIMPLEX}$. Updating the objective function and setting $x_0 = 0$ gives

$$ \begin{array}{rcrcrcr} z & = & 3 & + & 2x_2 & + & x_4 \\ x_1 & = & 3 & - & x_2 & + & x_4 \\ x_3 & = & 2 & - & 2x_2 & + & x_4 \\ x_5 & = & 5 & - & 5x_2 & + & x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

We'll choose $x_2$ as our entering variable, which makes $x_3$ our leaving variable. This gives

$$ \begin{array}{rcrcrcr} z & = & 5 & - & x_3 & + & 2x_4 \\ x_1 & = & 2 & + & (1 / 2)x_3 & + & (1 / 2)x_4 \\ x_2 & = & 1 & - & (1 / 2)x_3 & + & (1 / 2)x_4 \\ x_5 & = & & & (5 / 2)x_3 & - & (3 / 2)x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

Next we use $x_4$ as our entering variable, which makes $x_5$ our leaving variable. This gives

$$ \begin{array}{rcrcrcr} z & = & 5 & + & (7 / 3)x_3 & - & (4 / 3)x_5 \\ x_1 & = & 2 & + & (4 / 3)x_3 & - & (1 / 3)x_5 \\ x_2 & = & 1 & + & (1 / 3)x_3 & - & (1 / 3)x_5 \\ x_4 & = & & & (5 / 3)x_3 & - & (2 / 3)x_5 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

Finally, we would like to choose $x_3$ as our entering variable, but every coefficient on $x_3$ is positive, so $\text{SIMPLEX}$ returns that the linear program is unbounded.

29.5-8

Solve the linear program given in $\text{(29.6)}$–$\text{(29.10)}$.

We first put the linear program in standard form,

$$ \begin{array}{lrcrcrcrcrl} \text{maxmize} & x_1 & + & x_2 & + & x_3 & + & x_4 \\ \text{subject to} & \\ & 2x_1 & - & 8x_2 & & & - & 10x_4 & \le & -50 \\ & -5x_1 & - & 2x_2 & & & & & \le & -100 \\ & -3x_1 & + & 5x_2 & - & 10x_3 & + & 2x_4 & \le & -25 \\ & & x_1, x_2, x_3, x_4 & & & & & & \ge & 0 & . \end{array} $$

The initial basic solution isn't feasible, so we will need to form the auxiliary linear program.

$$ \begin{array}{rcrcrcrcrcrrcl} z & = & & - & x_0 \\ x_5 & = & -50 & + & x_0 & - & 2x_1 & + & 8x_2 & & & + & 10x_4 \\ x_6 & = & -100 & + & x_0 & + & 5x_1 & + & 2x_2 \\ x_7 & = & -25 & + & x_0 & + & 3x_1 & - & 5x_2 & + & 10x_3 & - & 2x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7 & \ge & 0 & . \end{array} $$

The index of the minimum $b_i$ is $2$, so we take $x_0$ to be our entering variable and $x_6$ to be our leaving variable. The call to $\text{PIVOT}$ on line 8 yields

$$ \begin{array}{rcrcrcrcrcrrcl} z & = & -100 & + & 5x_1 & + & 2x_2 & & & & & - & x_6 \\ x_0 & = & 100 & - & 5x_1 & - & 2x_2 & & & & & + & x_6 \\ x_5 & = & 50 & - & 7x_1 & + & 8x_2 & & & + & 10x_4 & + & x_6 \\ x_7 & = & 75 & - & 2x_1 & - & 7x_2 & + & 10x_3 & - & 2x_4 & + & x_6 \\ x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7 & \ge & 0 & . \end{array} $$

Next we'll take $x_2$ to be our entering variable and $x_5$ to be our leaving variable. The call to $\text{PIVOT}$ yields

$$ \begin{array}{rcrcrcrcrcrcr} z & = & -225 / 2 & + & (27 / 4)x_1 & & & - & (10 / 4)x_4 & + & (1 / 4)x_5 & - & (5 / 4)x_6 \\ x_0 & = & 225 / 2 & - & (27 / 4)x_1 & & & + & (10 / 4)x_4 & - & (1 / 4)x_5 & + & (5 / 4)x_6 \\ x_2 & = & -50 / 8 & + & (7 / 8)x_1 & & & - & (10 / 8)x_4 & + & (1 / 8)x_5 & - & (1 / 8)x_6 \\ x_7 & = & 475 / 4 & - & (65 / 8)x_1 & + & 10x_3 & + & (54 / 8)x_4 & - & (7 / 8)x_5 & + & (15 / 8)x_6 \\ x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7 & \ge & 0 & . \end{array} $$

The work gets rather messy, but $\text{INITIALIZE-SIMPLEX}$ does eventually give a feasible solution to the linear program, and after running the simplex method we find that $(x_1, x_2, x_3, x_4) = (175 / 11, 225 / 22, 125 / 44, 0)$ is an optimal solution to the original linear programming problem.

29.5-9

Consider the following $1$-variable linear program, which we call $P$:

$$ \begin{array}{lrcrl} \text{maximize} & tx \\ \text{subject to} & rx & \le & s \\ & x & \ge & 0 & , \end{array} $$

where $r$, $s$, and $t$ are arbitrary real numbers. Let $D$ be the dual of $P$.

State for which values of $r$, $s$, and $t$ you can assert that

1. Both $P$ and $D$ have optimal solutions with finite objective values.
2. $P$ is feasible, but $D$ is infeasible.
3. $D$ is feasible, but $P$ is infeasible.
4. Neither $P$ nor $D$ is feasible.

1. One option is that $r = 0$, $s \ge 0$ and $t \le 0$. Suppose that $r > 0$, then, if we have that $s$ is non-negative and $t$ is non-positive, it will be as we want.
2. We will split into two cases based on $r$. If $r = 0$, then this is exactly when $t$ is non-positive and $s$ is non-negative. The other possible case is that $r$ is negative, and $t$ is positive. In which case, because $r$ is negative, we can always get $rx$ as small as we want so s doesn't matter, however, we can never make $rx$ positive so it can never be $\ge t$.
3. Again, we split into two possible cases for $r$. If $r = 0$, then it is when $t$ is nonnegative and $s$ is non-positive. The other possible case is that $r$ is positive, and $s$ is negative. Since $r$ is positive, $rx$ will always be non-negative, so it cannot be $\le s$. But since $r$ is positive, we have that we can always make $rx$ as big as we want, in particular, greater than $t$.
4. If we have that $r = 0$ and $t$ is positive and $s$ is negative. If $r$ is nonzero, then we can always either make $rx$ really big or really small depending on the sign of $r$, meaning that either the primal or the dual would be feasable.