Back

Auxiliary problem

The simplex method requires an initial basic feasible solution. So far, we have not discussed how to obtain one. We now show how we can use the simplex method to obtain an initial basic feasible solution.

Let $A \in R^{m \times n}$ with $rank (A) = m$ . Let $b \in R^{m}$ . Assume that $b \geq 0$ . Let $(P^{'})$ denote the problem $\begin{aligned} min & x_{n + 1} + \dots + x_{n + m} \\ s.t. & [\begin{array}{c} A & I \end{array}] [\begin{array}{c} x_{1} \\ ⋮ \\ x_{n} \\ x_{n + 1} \\ ⋮ \\ x_{n + m} \end{array}] = b \\ x_{1}, \dots, x_{n + m} \geq 0 \end{aligned}$ where $I$ denotes the $m \times m$ identity matrix.

The problem $(P^{'})$ is called the auxiliary problem associated with $A x = b, x \geq 0$ .

Proposition 7.1.

The system $A x = b, x \geq 0$ has a solution if and only if the optimal value of $(P^{'})$ is $0$ .

Proof. Notice that $(P^{'})$ is not unbounded since the objective function value is never negative. It also has a feasible solution since $x_{1} = \dots = x_{n} = 0$ , $x_{n + i} = b_{i}$ for $i = 1, \dots, m$ satisfies all the constraints of $(P^{'})$ . Hence, by the Fundamental Theorem of Linear Programming, $(P^{'})$ has an optimal solution.

Observe that if the optimal value of $(P^{'})$ is 0 and if $x^{'}$ is an optimal solution, then we must have $x_{n + i}^{'} = 0$ for $i = 1 \dots, m$ . Hence, $x$ such that $x_{i} = x_{i}^{'}$ for $i = 1, \dots, n$ is a solution to $A x = b, x \geq 0$ .

Conversely, if $x$ satisfies $A x = b, x \geq 0$ , then $x^{'}$ with $x_{i}^{'} = x_{i}$ for $i = 1, \dots, n$ and $x_{n + 1}^{'} = \dots = x_{n + m}^{'} = 0$ is a feasible solution to $(P^{'})$ with objective function value $0$ and therefore is optimal.

Proposition 7.2.

Suppose that the optimal value of $(P^{'})$ is 0. If the simplex method with an anti-cycling rule is applied to $(P^{'})$ starting with the basis $B = {n + 1, \dots, n + m}$ , it will terminate with a basic feasible solution to $A x = b, x \geq 0$ after components $n + 1, \dots, n + m$ are removed.

Proof. Note that the columns of the coefficient matrix of the equations in $(P^{'})$ indexed by elements of $B = {n + 1, \dots, n + m}$ are linearly independent. Hence, $B$ is a basis. The basic solution $x^{'}$ determined by $B$ is given by $x_{1}^{'} = \dots = x_{n}^{'} = 0$ and $x_{n + i}^{'} = b_{i}$ for $i = 1, \dots, m$ . Since $b \geq 0$ by assumption, $x^{'}$ is a basic feasible solution.

Hence, the simplex method (with Bland's anti-cycling rule) can be applied to $(P^{'})$ starting with the basis $B$ and it will terminate with an optimal solution, say $x^{'}$ . As we are given that the optimal value is $0$ , ${x^{'}}_{i} = 0$ for $i = n + 1, \dots, n + m$ . Let $x \in R^{n}$ be given by $x_{i} = x_{i}^{'}$ for $i = 1, \dots, n$ . Note that we still have that the columns of $A$ corresponding to nonzero components of $x$ are linearly independent. By the result in a previous worked example, we see that $x$ is a basic feasible solution to $A x = b, x \geq 0$ .

Two-phase method

The following is an outline of the two-phase method for solving $\begin{aligned} min & c^{T} x \\ s.t. & A^{T} x = b \\ x \geq 0 \end{aligned}$ where $A \in R^{m \times n}$ is of rank $m$ , $b \in R^{m}$ , and $c \in R^{n}$ :

Solve the auxiliary problem associated with $A^{T} x = b, x \geq 0$ to obtain a basic feasible solution $x^{*}$ to $A^{T} x = b, x \geq 0$ .
Obtain a basis $B$ determining $x^{*}$ and apply the simplex method starting with the basis $B$ .

With the two-phase method, we can now solve any linear programming problem in standard form.

We end with a few words should on the efficiency of the simplex method. Computational experiments over the years suggest that the simplex method is quite efficient in practice: the number of iterations is often linear in the number of constraints. Unfortunately, in the worst case, the number of iterations that the simplex method with every popular anti-cycling rule requires is exponential in the number of variables. At the moment, there is no known variant of the simplex method that requires a polynomial number of iterations in the worst case. Finding a choice rule for the entering and leaving variables that gives a polynomial-time simplex method is still an open problem.

Worked examples

Obtain a basic feasible solution to $\begin{array}{rrcrcrcl} x_{1} & - & 2 x_{2} & - & x_{3} & = & 1 \\ x_{1} & - & x_{2} & + & x_{3} & = & 3 \\ x_{1} & , & x_{2} & , & x_{3} & \geq & 0. \end{array}$ by solving its associated auxiliary problem.
The auxiliary problem is $\begin{array}{rrcrcrcrcrcl} min & x_{4} & + & x_{5} \\ (P) s.t. & x_{1} & - & 2 x_{2} & - & x_{3} & + & x_{4} & = & 1 \\ x_{1} & - & x_{2} & + & x_{3} & + & x_{5} & = & 3 \\ x_{1} & , & x_{2} & , & x_{3} & , & x_{4} & , & x_{5} & \geq & 0. \end{array}$

We apply the revised simplex method starting with the basis $B = {4, 5}$ . Note that $B$ determines the basic feasible solution $x^{*} = [\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \\ 3 \end{matrix}]$ to the auxiliary problem.

Iteration 1
1. $N = {1, 2, 3}$ .
2. Solve $y^{T} A_{B} = c_{B}^{T}$ ; i.e. $[\begin{matrix} y_{1} & y_{2} \end{matrix}] [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] = [\begin{matrix} 1 & 1 \end{matrix}]$ . We obtain $y_{1} = 1, y_{2} = 1$ .
3. Choose $k = 1$ since $y^{T} A_{1} = 2 > 0 = c_{1}$ .
4. Find $d = [d_{1}, d_{2}, d_{3}, d_{4}, d_{5}]^{T}$ such that $d_{1} = 1$ , $d_{2} = 0$ , $d_{3} = 0$ , and $[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] [\begin{matrix} d_{4} \\ d_{5} \end{matrix}] = [\begin{matrix} - 1 \\ - 1 \end{matrix}] .$ Solving, we obtain $d_{4} = - 1$ , $d_{5} = - 1$ .
5. It is not true that $d \geq 0$ .
6. $λ = min {\frac{x_{4}^{*}}{- d_{4}}, \frac{x_{5}^{*}}{- d_{5}}} = min {\frac{1}{1}, \frac{3}{1}} = 1$ . Choose $r = 4$ .
7. New $x^{*} = [\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \\ 3 \end{matrix}] + 1 [\begin{matrix} 1 \\ 0 \\ 0 \\ - 1 \\ - 1 \end{matrix}] = [\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \\ 2 \end{matrix}]$ .
8. New $B = {1, 5}$ .
Iteration 2
1. $N = {2, 3, 4}$ .
2. Solve $y^{T} A_{B} = c_{B}^{T}$ ; i.e. $[\begin{matrix} y_{1} & y_{2} \end{matrix}] [\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}] = [\begin{matrix} 0 & 1 \end{matrix}]$ . We obtain $y_{1} = - 1, y_{2} = 1$ .
3. Choose $k = 2$ since $y^{T} A_{2} = 1 > 0 = c_{2}$ .
4. Find $d = [d_{1}, d_{2}, d_{3}, d_{4}, d_{5}]^{T}$ such that $d_{2} = 1$ , $d_{3} = 0$ , $d_{4} = 0$ , and $[\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}] [\begin{matrix} d_{1} \\ d_{5} \end{matrix}] = [\begin{matrix} 2 \\ 1 \end{matrix}] .$ Solving, we obtain $d_{1} = 2$ , $d_{5} = - 1$ .
5. It is not true that $d \geq 0$ .
6. $λ = min {\frac{x_{5}^{*}}{- d_{5}}} = min {\frac{2}{1}} = 2$ . Choose $r = 5$ .
7. New $x^{*} = [\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \\ 2 \end{matrix}] + 2 [\begin{matrix} 2 \\ 1 \\ 0 \\ 0 \\ - 1 \end{matrix}] = [\begin{matrix} 5 \\ 2 \\ 0 \\ 0 \\ 0 \end{matrix}]$
8. New $B = {1, 2}$ .
Note that $B = {1, 2}$ is a basis with respect to the original system. Hence, $x^{*} = [\begin{matrix} 5 \\ 2 \\ 0 \end{matrix}]$ is a basic feasible solution to the original system.