First Homework (from the second round of homeworks)
On December 6, we mentioned that 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 of the Fundamental Theorem of Linear Programming. We asked as homework to read out this algorithmic proof.
Second Homework (from the second round of homeworks)
We asked to consider the following possible strengthening of the Fundamental Theorem just above.
We posed the following question:
Which one of (i), (ii) and (iii) does still hold?
We can easily argue that (i) does still hold as follows:
Assume given any LP problem . We know that we can put in standard form, which means that we can derive an LP problem with the property that has an optimal solution of value (or is infeasible, or is unbounded) if and only if has an optimal solution of value (or is infeasible, or is unbounded, respectively). Apply the Fundamental Theorem to .
To show that neither (ii) nor (iii) can be given for granted without the assumption of the problem <b>being in standard form</b>, just consider an LP problem in 2 dimensions whose feasible set is a line.
This will certainly be a counterexample for (ii) since the feasible set is non-empty, yet we have no vertices, hence no feasible solutions.
But to make it a counterexample to (iii) you must choose you objective function carefully. Can you propose the right objective function to make it a counterexample to (iii) as well?
Can you propose a counterexample for 3 dimensions?
I am just curious two know whether in your counterexample for 3
dimensions the feasible set was a
2-dimensional object or an 1-dimensional one.
Third Homework (from the second round of homeworks)
We finally proposed the following problem.
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?
I do not want to spoil your fun, hence I will ask you to fill in the steps in the following proof:
Step 1: please, define formally what it means for a polyhedron to contain a line;
Step 2: please, formalize the arguments in the picture to obtain a proof ( = convince yourself of the truth) of the following theorem.
Step 3: please, derive the following corollary.
Let me pose you another intriguing, this time algorithmic, question. We proposed to use the simplex method on the auxiliary problem to find a first basic feasible solution to the original problem (or detect that such problem is infeasible).
Algorithmic Problem: Can you turn the proof sketched into the above picture into a polynomial time algorithm which, starting from a feasible solution to an LP problem, produces a basic feasible solution for the same problem?
Question: If you settled the above algorithmic problem on the positive, does this mean that you can trow the two phase simplex method into the garbige can? Why not (if not)?
© Dipartimento di Matematica - Università di Trento