Question 1:(a)_____Every general linear programming problem can be transformed into an equivalent linear programming problem in standard form.
True or false …………………………………………………………. 10 points
No justifications needed. Mark “T” or “F”.
Points per question: 0 points if wrong; 1/2 point if no answer; 1 point if correct.
(a)_____Every general linear programming problem can be transformed into an equivalent linear programming problem in standard form.
(b)_____Every extreme point of a polyhedron P is also a basic solution of P.
(c)_____Every basic solution of a polyhedron P is also a vertex of P.
(d)_____The property of being a basic feasible solution is independent of the representation used (i.e., it depends on the polyhedron, but it is independent on the system of linear constraints used to describe the polyhedron.)
(e)_____In every linear programming problem in standard form, the set of all optimal solutions is bounded.
(f)_____If in a LP problem there are several optimal solutions, then there exist at least two vertices that are optimal.
(g)_____Let x be a point in a polyhedron P. It is possible that there exist infinitely many feasible directions at x.
1
(j)_____In the naive implementation of the simplex method the total computational effort per iteration is O(m³ + mn).
Finite number of vertices ……………………………………………… 5 points
Let P = {x ∈ Rⁿ | Ax ≤ b} be a polyhedron. Prove that P has a finite number of extreme points.
A tableau………………………………………………………………5 points
You are carrying out the full tableau implementation of the simplex method. In one iteration you obtain the following tableau:
(a) (1 point) Recover the missing labels, write the current solution and its cost.
(b) (4 points) Is the current solution optimal? If not, find an optimal solution with the full tableau implementation of the simplex method.
Your boss and two polyhedra ………………………………………… 10 points
Assume that your boss gives you two polyhedra
P = {x ∈ Rⁿ | Ax ≤ b}, Q = {x ∈ Rⁿ | Cx ≤ d}.
In particular, the (m × n)-matrix A, the m-vector b, the (p × n)-matrix C, and the p-vector d are given to you. Your boss then asks you to understand whether P ⊆ Q, or to find a vector in P that is not in Q. Using your precious knowledge gained in the course 525, you write a computer program that can solve any LP problem where a linear function has to be maximized over a polyhedron (not only in standard form).
(a) (5 points) Prove that an inequality c′x ≤ δ is satisfied by every vector in P if and only if the optimal cost of the LP problem
maximize
c′x
s.t. Ax ≤ b
is less than or equal to δ.
(b) (5 points) Using (a), explain how you can give an answer to your boss using your computer program.
Hint: You can use your computer program several times with different inputs.