The LP class on December 6, 2001

Contents of the first part of the LP class on December 6, 2001

We faced the problem of obtaining a first basic feasible solution from which to start with the simplex method. To solve this problem, we have introduced the auxiliary LP problem of an LP problem in standard form. We observed that the original problem is feasible if and only if the optimal solution value for the always feasible associated auxiliary problem is zero. We have also shown how to obtain a first basic feasible solution for the auxiliary problem. (Together with the simplex method, this is already enough to consent us to test the feasibility of a given set of linear constraints). Finally, we have indicated how to obtain a first basic feasible solution to the original problem (in case it is feasible) by simply dropping the extra variable (the glue variable $x_0$) from the final $0$-valued dictionary for the auxiliary problem. Indeed, dropping a variable of value $0$ ($x_0=0$ when the objective function for the auxiliary problem, namely $-x_0$ equals $0$) can not violate feasibility. The reason why the property of ``being basic'' is also mantained while dropping $x_0$ is also due to the fact that $x_0=0$ in the solution associated with this final dictionary. Indeed, we have argued that we can always act so that $x_0$ is non-basic in this last dictionary. This actually means that in the so called ``Two Phases Simplex Method'' we can, once we reach an (optimal) $0$-valued solution to the auxiliary problem, apply right away the simplex method (second phase) to solve the original problem, simply discarding the column of coefficients associated to $x_0$.

First round of Homeworks

Solve the following LP problem by introducing the corresponding auxiliary problem and applying the Two Phases Simplex Method.

$$\begin{array}{l} \max \mbox{\ }3x_1 + x_2 \\ \left\{ \b... ...{array} \\ x_1, x_2 \geq 0 \end{array} \right. \end{array}$$

Have fun!

Contents of the second part of the LP class on Dec. 6

We have defined degeneracy and cycling. We have seen examples which show that under certain (even most reasonable) pivoting rules, cycling can actually occur. We have considered perturbation methods and in particular the lexicographic method to avoid cycling. For the lexicographic method, we argued for its success in banning the possibility of cycling. We also observed that if the simplex method does not cycle then it must terminate.

Second round of Homeworks

The Two Phases Simplex Method, implemented by employing any strategy which guarantees termination (like Bland's pivoting rule or resorting on sound perturbation methods like for example the lexicographic method) gives algorithmic proof to the following result.

Theorem 0.1 (The Fundamental Theorem of Linear Programming)   Each LP problem in standard form enjoies the following three properties:

(i)

if it has no optimal solution, then it is either infeasible or unbounded;

(ii)

if it is feasible, then it has a basic feasible solution;

(iii)

if it has an optimal solution, then it has a basic optimal solution.

Can you argue on the truth of the Fundamental Theorem of Linear Programming on the basis of the Two Phases Simplex Method and by considering its possible terminations?

Consider the following conjecture.

Conjecture 0.2 (A strengthening of the Fundamental Theorem of Linear Programming)   Each LP problem enjoies the following three properties:

(i)

if it has no optimal solution, then it is either infeasible or unbounded;

(ii)

if it is feasible, then it has a basic feasible solution;

(iii)

if it has an optimal solution, then it has a basic optimal solution.

Which one of (i), (ii) and (iii) does still hold?

Can you provide counterexamples to the remaining properties? (Think geometrically).

With the insight gained at the previous point, can you now prove the Fundamental Theorem of Linear Programming by direct arguments, without relying on the simplex method?

If you really enjoy practicing pivot, or if you have some handy tool which can do the dirty job for you, then I dare proposing you this further exercise.

In the following LP method, the quantity $\epsilon$ has been introduced as a small perturbation with the porpouse of reducing the probability of any degenearacy. Nevertheless the simplex method will encounter degeneracy and will actually cycle. Can you find under which natural pivoting rules cycling will actually occur?

$$\begin{array}{l} \max \mbox{\ }z = 10x_1 - 57x_2 - 9x_3 -2... ...1, x_2, x_3, x_4, x_5 \geq 0 \end{array} \right. \end{array}$$

Have fun!