Interactive Linear Programming


THE BASIC CERTIFICATES



When you try to solve a problem in linear optimization, one thing that you would usually like to do is to prove that your conclusions are true, i.e that your problem is really infeasible, or unbounded, or that the optimal solution that you propose is really optimal. In order to do that, the theory of linear programming provides us for some equations that are likely to prove these three possible conclusions. These equations, if we solve them (i.e find some vectors Y or U or W that satisfy them, as you will see later on) prove that our conclusions are true. They are called the basic certificates.

For the certificate of infeasibility, click here.
For the certificate of unboundedness, click here.
For the certificate of optimality, click here.

Certificate of Infeasibility

The certificate of infeasibility consists in one (1*n) row-vector Y such that:
  1. Y * A 0.
  2. Y * B > 0.
Indeed, if there existed any feasible vector X solution to the problem (i.e. a vector X such that A*X=B, X0) then for any vector Y satisfying inequality (1.), we would have:
Y*A 0
=> (Y*A)*X 0 (since X0)
=> Y*B 0 (since A*X = B)
=> no vector Y that verifies (1.) can verify (2.).

Certificate of Unboundedness

The unbondedness certificate consists in:
These two vectors are such that:
  1. A*X = B.
  2. X 0.
  3. A*W = 0.
  4. W 0.

Indeed, 1/ and 2/ guarantee that X is a feasible solution to the problem. 3/ guarantees that, for any number l>=0, X + (l*W) is still a feasible solution, since: Last, 4/ guarantees that, if we choose l large enough, we can find a feasible solution (equal to X+lW) that gives a value of the objective function as small as we want (since C * (X+lW) = (C*X) + l(C*W), with C*W < 0 and l > 0, as large as we want.

Certificate of Optimality

The certificate consists of:
These two vectors are such that:
  1. A*X = B
  2. X 0.
  3. Y*A C.
  4. [C-(Y*A)]*X = 0.

Indeed, 1/ and 2/ guarantee that X is a feasible solution to the problem. 3/ Guarantees that for any feasible solution X, then C*X Y*B (We obtain this result by multiplying 3/ by X and replacing, if X is a feasible solution, A*X by its value, i.e. B). So, Y*B is a lower bound on the value of the objective function for any feasible solution.
4/ guarantees that C*X = (Y*A)*X = Y*B = lower bound on the value of the objective function.
So, X is a feasible solution, and the value of the objective function for X is equal to the lower bound. Thus, X is an optimal solution.