Homeworks proposed on 4 December 2001
Content of the class on 4 December 2001
We have exposed how the simplex method works. While working on specific examples, we have tried to abstract from the single problem. Our exposition was based on the notion of ``dictionary'' as introduced by J. E. Strum and promoted by Chvtal. First, we used the simplex method to solve the following LP problem:
A first homework
Use the simplex method to solve the following LP:
More on the content of the class on 4 December 2001
We have also considered examples in which no optimal solution is present
because the polyhedron is unbounded.
Moreover, we have also faced the problem of finding an initial feasible
basic solution from which to start (or realize that the problem is infeasible).
Finally, we have also observed how the simplex method moves from vertex to vertex of the polyhedron of feasible solutions until it reaches an optimal solutions. But let us monitor this behaviour on a more complex example taken from the book ``Elementi di Programmazione Matematica'' of F. Maffioli.
Let us consider the following LP problem:
The polyhedron of the feasible solutions is the intersection of a finite number of halfplanes. These halfplanes are convex, hence the polyhedron is also convex. In this special case the polyhedron is also bounded, hence is a politope. We draw the politopo of feasible solutions in the following picture.
If you now try, as an exercise, to solve the above LP problem by means of the simplex method, you will have the opportunity to verify that the algorithm will lead you to visit as feasible basic solutions, the sequence of vertices as visited by the path indicated in the picture.
A second homework
During the class, the following question came about:
assume that at a given iteration of the simplex method
the reduced cost relative to a non-basic variable is negative.
Can I then conclude that
will still be non-basic when the optimal solution is reached?
As I already anticipated,
the answer to an even weaker conjecture is NO.
Moreover, exploiting the geometric view by now developed
on the way the simplex method moves about,
it should now be possible to buid up a counterexample
(even with only 2 decision variables).
© Dipartimento di Matematica - Università di Trento