A Short Course in Linear Programming

 

Lesson 2. What is a solution?

Use the Mathematical Programming Glossary to look up terms you do not understand. 

First, lookup the following terms in my glossary:

Second, read RIOT "Basic Certificates".

Third, experiment with Virtual Duality.

Fourth, study the following table and practice formulating a variety of LP duals.
Help.

Primal Dual
Objective  minimize cx  maximize yb 
Contraint type A(i,.)x >= b(i)  y(i) >= 0  Variable type 
A(i,.)x <= b(i)  y(i) <= 0 
A(i,.)x = b(i)  y(i) free 
Variable type x(j) >= 0  yA(.,j) <= c(j)  Constraint type 
x(j) <= 0  yA(.,j) >= c(j) 
x(j) free  yA(.,j) = c(j) 
 
    Some things to note:
  1. There is a dual variable for every primal constraint; the number of them is m.
  2. There is a dual constraint for every primal variable; the number of them is n.
  3. The sense of optimization is opposite (min vs. max).
  4. The right-hand side (b) in the primal is the objective coefficient in the dual.
  5. The objective coefficient (c) in the primal is the right-hand side in the dual.
Exercises

 

  1. Consider the following LP: min x1 + x2: x1, x2 >= 0, x1 + 2x2 >= 10, 2x1 + x2 >= 10.

    2. Test each of the following points to determine if they are optimal (click on point for answer).
    (5, 0) ;  (0, 10) ;  (10/3, 10/3);  (5, 5). 
    If you have not entered my help file, you can do so now to see more about this LP.
  2. For what values of the parameter p is the following LP feasible?
    3. min 
    How about its dual?
    Solution.
  3. For what values of the paramter p is the following LP bounded?
    4. min 
    How about its dual?
    Solution.
 

Last updated: August 16, 1997