Linear Programming

Example
    Transportation problem
    Activity analysis problem
    Diet problem
Mathematical background
    Linear inequalities
    Solution of linear equations
Linear programming problem
    Find extreme points
    Find minimum cost feasible solution
Simplex procedure
Reference

A subclass of programming problems called Linear Programming problems.  In LP the description of the problem can be stated linearly. AX = b  with the cost function cX.

Each LP problem has:
1) no solution in terms of non-neg values of the variables
2) A non-neg soln. that yields an infinite value to cost.
3) A non-neg soln. that yields a finite value to cost.

Example

Transportation problem

assume sum a _i = sum b _j  .  Find x _ij that min cost.

m < n

given m = 2, n = 3

c_ij = 1 2 4
      3 2 1

x₁₁ x₁₂ x₁₃  5
x₂₁ x₂₂ x₂₃  10
8   5   2

---> store 1,2,3
|
v  warehouse 1,2
 

for example: the amount shipped from w1, w2 are:
x₁₁ + x₁₂ + x₁₃ = 5
x₂₁ + x₂₂ + x₂₃ = 10

the total amount of shipped to three stores
x₁₁ + x₂₁ = 8
x₁₂ + x₂₂ = 5
x₁₃ + x₂₃ = 2

Activity analysis problem

m = no. of resources
n = no. of products
a _ij = unit of resource i required to produce j
b _i = max. units of resource i available
c _j = profit per unit of product j
x _j = the amount produced of product j (level of activity)

x _j >= 0

the cost function  c _j . x _j, constraints

AX <= b

Diet problem

m = no. of nutrient
n = no. of foods.
a _ij = no. of mg of nutrient i in one unit of food j
b _i = min. of mg of nutrient i required
c _j = cost per unit of food j
x _j = no. of unit of food j to be purchased (x _i > 0)

AX >= b
with min. cX

Mathematical background

vector space

Euclidean space E_n

Convex set

C subset of E_n  is convex if  every pairs U₁ U₂ in C:
U = a₁U₁ + a₂U₂  is in C

Example   all space E _n , a circle, a cube

THM 1:  any point on the line joins between two points in En is convex combination of two points

example:  U,V are points,  W = (1-a)V + aU   0 <= a <= 1

Def:  Extreme point (xp) is U that is not a convex combination of other point in C.

Def:  Convex hull C(S) , S is set of points, is a set of every convex combination of points from S.  C(S) is the
smallest convex set that contains S.

example:  S are 8 points of a cube, C(S) is the whole cube.

If S is finite, C(S) is called convex polyhedron  (point is the xp)

Def:  Simplex is n-D convex polyhedron that has exactly n+1 vertices.  A simplex in 0-D is a point, 2-D is a triangle.

Linear Inequalities

P1, P2, P0 is column vectors

x₁P₁ + x₂P₂ >= P₀, P is a point in 5-D
Find x₁ x₂ that satisfies 1..5

The solution is convex region in n-D.
Transform inequality to equality by adding "slack variables" n - m variables.  (n varibles, m equations)

example: x1 - 2x2 + 3x3 >= 6
to  x1 - 2x2 + 3x3 - x4 = 6

Some system may not have solution:
x1 + x2 <= 1
2x1 + 2x2 >= 3.

Solution of linear equations

Gauss and Jordan elimination method: multiply by A"  ("inverse)
A" A X = A" b
X = A" b
A must be non-singular (det /= 0 )

any variable can be chosen first to be eliminated.

example
  x1 + x2 -x3  = 2   (1)
-2x1 + x2 +x3  = 3   (2)
  x1 + x2 +x3  = 6   (3)

step 1
to eliminate x1 from (1) do 2(1) + (2)
to eliminate x1 from (3) do -1(1) + (3)

  x1 + x2 -x3 = 2
      3x2 -x3 = 7
          2x3 = 4

step 2
to eliminate x2 from (1) do -1(2)/3 + (1)

  x1      -2/3 x3 = -1/3
      x2  -1/3 x3 =  7/3
             2 x3 =  4

step 3
the pivot element now is 2 (in (3))  do (3)/2 . 2/3 + (1)  and (3)/2 . 1/3  - (1).

  x1              = 1
      x2          = 3
           x3     = 2

this is equivalent to transforming
     1  1  -1
A = -2  1   1
     1  1   1

to an identity matrix
     1  0  0
I =  0  1  0
     0  0  1

both finding a solution and inversing A can be done at the same time using a matrix form

(A|I|b)
(A" A|A" I|A" b) = (I|A"|X)  X is the solution

where A" is inverse of A

example: do previous example

  1  1  -1 | 1  0  0 | 2
 -2  1   1 | 0  1  0 | 3
  1  1   1 | 0  0  1 | 6

step 1
  1  1  -1 | 1  0  0 | 2
  0  3  -1 | 2  1  0 | 7
  0  0   2 |-1  0  1 | 4

step 2
  1  0  -2/3 | 1/3  -1/3  0 | -1/3
  0  1  -1/3 | 2/3   1/3  0 |  7/3
  0  0   2   | -1     0   1 |  4

step 3
  1  0  0 | 0   -1/3  1/3 | 1
  0  1  0 | 1/2  1/3  1/6 | 3
  0  0  1 | -1/2  0   1/2 | 2

A" is
  0   -1/3  1/3
  1/2  1/3  1/6
 -1/2   0   1/2

The linear combination of P1, P2 and P3 is

1P₁ + 3P₂ + 2P₃ = P0

P₁ = (0 1/2  -1/2)'  P₂ = (-1/3 1/3 0)'  P₃ = (1/3 1/6 1/2)'  P₀ = (2 3 6)'
where ' is tranpose

A system of linear equation AX = b is said to be "homogeneous" if b = 0.  Such a system has the trivial
solution X = 0.

Linear Programming problem

x₁P₁ + x₂P₂ + .. x_nP_n = P₀

THM 2:  set of all feasible soln. to LP is a convex set.

Proof  show every convex combination of 2 feas. soln. is feasible solution.

let X₁, X₂ be the feasible soln.
AX₁ = b, AX₂ = b, X₁ >= 0 , X₂ >= 0.
let 0 <= a <= 1 and X = aX₁ + (1-a)X₂
AX = A[aX₁ + (1-a)X₂]
 = aAX₁ + (1-a)AX₂
 = ab + b - ab
 = b
therefore X is a fea.soln.  QED

Let K be convex set of soln. of LP
K is a region in En.
1) K = void  no soln.
2) K is region unbounded    min. may be infinite
3) K is convex polyhedron   min. finite

there are many soln. find one the min cX.  K is convex hull of xp of K.  Look at xp to find min.feasible soln.

THM 3  if P₁, P₂...P_m  m <= n vector is linearly independent
x₁P₁ + x₂P₂ + ... x_nP_n = P₀   x_i >= 0

then a point X (x₁,...x_m, 0..0) is xp of the convex set of fea.soln.  with n-m element is 0.

Collorary   every xp of K has m linearly independent vector from P₁, P₂...P_n.

Summary

How many xp to look at ?
combination( n,m )  = n!/(m! (n-m)!)

Find extreme points

Select one xp, look to its neighbour that has lower cost, typically looks about m to 2m points.  Can detect no finite min. soln. or no feasible.soln.

start: X = (x₁,x₂,...x_m,0,..0)
x₁P₁ + x₂P₂ + ...x_mP_m = P₀   x_i >= 0  (1)

assume next xp exists
P₁..P_m  linearly independent use as basis to express all other vectors in n
sum i = 1 to m ( x _ij P _i  ) = P _j   j = 1...n

let one vector not in the basis P _m+1 has x _i,m+1 > 0
x _1,m+1 P₁ + x _2,m+1 P₂ + ... x _m,m+1 P_m = P _m+1    (2)

(1) - Z(2)
(x₁ - Zx_1,m+1)P₁ + (x₂ -Zx _2,m+1)P₂ + ... (x_m - Zx _m,m+1)P_m + ZP _m+1 = P₀  (3)

x' = (x_i - Zx _i,m+1, ... ) be fea.soln.  x' >= 0
x_i - Zx _i,m+1  >= 0,   x _i,m+1  >= 0
x_i/ x _i,m+1   >= Z
0 < Z <= min i  x_i/ x _i,m+1

with this condition  (3) will be a feasible soln.  We want to inspect only xp which has only m independent,
must force some variable to be zero.  Assume it is the first one:
Z₀ = x₁/x _1,m+1

the soln. will be new feasible soln.
x₂'P₂ + x₃'P₃ + ... x_m'P_m + x _m+1'P _m+1 = P₀
x_i' = x_i - Z₀ x _i,m+1   i = 2..n
x _m+1' = Z₀

Possibility
x _i,m+1  > 0   can move to a new xp
x _i,m+1  <= 0  no finite min. soln.

Example of moving to another xp.

initial xp x1 = 0, x3 = 0, x4 = 7, x5 = 12, x6 = 10, in vector notation:

7P₄ + 12P₃ + 10P₆ = P₀  (1)

the basis vectors P4, P3, P6 are unit vectors.  We want to introduce P1 to obtain another xp.  P1 in terms of this basis is:

3P₄ + 2P₃ -4P₆ = P₁   (2)

that is, x₄₁ = 3, x₅₁ = 2, x₆₁ = -4
do (1) - Z(2)

(7 - 3Z)P₄ + (12 - 2Z)P₅ - (10 - 4Z)P₆ + ZP₁ = P₀  (3)

both x₄₁ = 3, and x₅₁ = 2  are positive, Z₀ is determined

Z = Z₀ = min x_i/x_i1  = 7/3

substitute Z into (3), eliminate P₄,

22/3 P₅ + 58/3 P₆ + 7/3 P₁ = P₀   (4)

this is a new xp.

If instead of P1 we try P2

-P₄ -4P₅ -3P₆ = P₂      (5)

and develop P0 in terms of P4 P5 P6 P2:

(7 + Z)P₄ + (12 + 4Z)P₅ + (10 + 3Z)P₆ + ZP₂ = P₀  (6)

from (6) any Z > 0 yields a fea.soln.  Here all x_i2 < 0, we do not obtain a new xp.

Find minimum cost feasible solution

Given  X₀ (starting point)  (x₁₀, x₂₀...x_m0) and P₁...P_m
x₁₀P₁ + x₂₀P₂ + ... x_m0P_m = P₀   (1)
x₁₀c₁ + x₂₀c₂ + ... x_m0c_m = w₀  x_i0 >= 0  (2)

other points
x_1jP₁ + x_2jP₂ + ... x_mjP_j = P_j  j = 1..n  (3)
x_1jc₁ + x_2jc₂ + ... x_mjc_j = w_j            (4)

THM 4  if w _j - c _j > 0  there is feasible soln. which w < w ₀  (can select a new basis which reduce the cost)

THM 5  at X  (x₁₀, x₂₀...x_m0) if w _j - c _j <= 0 for all j then X is a min feasible soln.

(1) - Z(3)   and (2) - Z(4)

(x₁₀ - Zx_1j)P₁ + (x₂₀ - Zx_2j)P₂ + ... (x_m0 - Zx_mj)P_m + ZP_j  = P₀  (5)
(x₁₀ - Zx_1j)c₁ + (x₂₀ - Zx_2j)c₂ + ... (x_m0 - Zx_mj)c_m + Z_cj  = w₀ - Z(w_j-c_j) (6)

mul Zc_j on both side of (6)

If every coeff of P₁...P_m, P_j >= 0 will have feasible soln. at cost w₀ - Z(w _j -c _j )
and Z > 0  if w _j- c _j > 0 then w < w₀

Simplex procedure

BX₀ = P₀
X₀ = B" P₀     X₀ = (x₁₀,...x_m0) >= 0
X_j = B" P_j     X_j = (x_1j,...x_mj) >= 0

start:   (P₀|P₁..P_m| P_m+1..P_n)
         (P₀|B|P_m+1..P_n)

mul B"
         (X₀|I_m|X_m+1...X_n)
find c _j and w _j - c _j      which j that w _j - c _j > 0  if not found,  stop at min feasible soln.

How to choose new basis?

assume select k
Z₀ = min i  x_i0/x_ik  x_ik > 0
if x_ik <= 0  the soln. has unbounded min.
select to eliminate P_l  and add P_k
new basis is   (P₁...P_l-1, P_l+1, P_m, P_k)

Example:

subject to
  x1 + 3x2 - x3       + 2x5      = 7
     - 2x2 + 4x3 + x4            = 12
     - 4x2 + 3x3      + 8x5 + x6 = 10
xi >= 0

start: select P1 P4 P6 as the basis,  the corresponding soln is X0 = (x1 x4 x6) = (7,12,10), w₀ = 0

choose  max j (w _j - c _j ) = w₃ - c₃ = 3 > 0   select P3

 Z₀ is min. of x_i0/x_i3 for x_i3 > 0 that is:

min (12/4, 10/3) = 12/4 = Z₀  hence P4 is eliminated, we obtain a new solution

X₀' = (x1 x3 x6) = (10,3,1)

and the cost is -9

step 2 choose max j (w _j ' - c _j ) = w ₂ ' - c₂ = 1/2 > 0
and Z₀ = 10/(5/2)  ,  P2 is introduced into the basis and P1 is eliminated.  A third soln. is obtained

X0'' = (x2 x3 x6) = (4,5,11)

the cost is -11,

Since max(w_j'' - c_j) = 0 this soln is a min. feasible soln.

Reference

last update  20 September 2002
P. Chongstitvatana

END