c

x1 , x 2 ,…… , x n
d xi ≥0

z x1 , x 2 , … … , x n

z
CONVEXITY
 λ x1 + (1 − λ ) x 2 ∈ S λ ∈ [0 , 1 ]
k ≥2 x1 , x 2 , … … , x k
λ 1 x1 + λ 2 x 2 + + λk xk
λ1 + λ2 + + λk = 1 λi ≥ 0 i = 1, 2 …, k
1 2,
x1 , x 2 , … … , x k
λ1 , λ 2 , , λ k ∈ ( 0 , 1)
C = {( x1 , x2 ) | x12 + x2 2 < 1}

{x ∈ n
| AX ≤ b}

{X ∈ n
| pX = k }or{X ∈ n
| p t X = k}
 ℝⁿ
H + = {X ∈ n
| ppX > k } and H − = {X ∈ n
p < k}
| pX

ℝⁿ

ℝⁿ

S ⊂ conv(S )
k k
conv ( S ) = {∑ λi xi | { x1 , x2 , , xk } ⊂ S , λi ≥ 0, ∑ λi = 1}
i =1 i =1
 x1 , x2 , , xk +1
x2 − x1 , x3 − x1 , , xk +1 − x1
conv ({ x1 , x 2 , , x k + 1 })

x ∈ conv ( S )

S1 + S2 = {x1 + x2 | x1 ∈ S1 , x2 ∈ S2 }
 v1, v2 ,…, vk

k
C = { ∑ λ i v i | λ i ≥ 0 fo r i = 1 ,22 ,, k } .
i =1

v1, v2 ,…, vk
 n
{(x1, x2 ,……, xn ) ∈ n
| ∑xi = 1 and xi ≥ 0 for i=1 2 …, n}
1,2,
i =1

.
S = {x ∈ n
| pi ⋅ x ≤ ai for i =1,2,…… ,m}
⇔ S = {x ∈ n
| A X ≤ b}
f 0 , f1 ,… , f d

∑ fi =1.1
(−1)
i =0
i
 x1 , x 2 ,… , x k

d1 , d 2 ,… , d m

x ∈ S ⇔ x = ∑ i =1 λi xi + ∑ j =1α j d j
k m

∑ λi = 1, λi , α i ≥ 0 for i = 1, 2,… , k and j = 1, 2,… , m

k
i =1
c⋅dj ≥ 0
 d1 
d = 
d2 
 x1 
x= 
 x2 
 x1   d 1   x1 + λ d 1 
⇒  +λ  =   ∈S , λ ≥0
 x2   d 2   x2 + λ d 2 
  −1 1   d1   0 
⇒    ≤   , d1 ≥ 0 , d 2 ≥ 0
 −1 2  d 2  0
 x1 + x 2 ≤ 6
x2 ≤ 3
x1 ≥ 0
x2 ≥ 0

x1 + x 2 + x 3 = 6 (1 )
x2 + x 4 = 3 (2 )
x1 ≥ 0 (3 )
⇒ x2 ≥ 0 (4 )
x3 ≥ 0 (5 )
x4 ≥ 0 (6 )
 1 1 1 0 
A= [ a1 a2 a3 a4 ] =   ,
 0 1 0 1
1 1  1 0 
and d [ a1 a2 ] =   , [ a1 a4 ] =   ,
 0 1  0 1
1 1  1 0 
[ a2 a3 ] =   , [ a2 a4 ] =   ,
1 0  1 1
1 0 
[ a3 a4 ] =   are invertible
i tibl .
 0 1
( a ) : (1) , ( 2 ) , & ( 5 ) , ( 6 )
1 1 
∵ B = [a1 a 2 ] =  
 0 1 
1 1   x1  6
⇒     =  
 0 1  x2  3 
-1
 x1  1 1   6  1 -1  6  3
⇒  x  =  0 1 3  = 0
 2      1  3  = 3
   
 x1  3 
x  3 
⇒  2 =  
 x3  0 
   
 x4  0 
( b ) : (1) , ( 2 ) & ( 4 ) , ( 5 )
1 0 
∵ B = [a1 a 4 ] =  
 0 1 
1 0   x 1  6
⇒     =  
 0 1  x4  3 
−1
 x1  1 0  6 1 0   6  6
⇒  x  =  0 1  3  =  0 1  3  =  3 
 4         
 x1  6
x  0
⇒  2 =  
 x3  0 
   
 x4  3 
( c ) : (1)
( ), ( 2 ) & (3), (5 )
1 0 
∵ B = [a 2 a4 ] =  
 1 1 
1 0  x2  6
⇒ 1  x  = 3 
 1   4  
−1
 x2  1 0  6 1 0   6  6 
⇒  x  = 1 1   3  =  -1 1   3  =  -3 
 4         
 x1  0 
x  6 
⇒  2 =  , x = − 3( )
 x3  0  4

   
 4
x  -3 
 1 1 
( d ) : B = [a 2 a 3 ] =  
 1 0 
1 1   x 2  6
⇒     =  
1 0   x 3  3 
−1
 x2  1 1  6  0 -1   6  3
⇒  x  = 1 0   3  = ( − 1)  -1 1   3  =  3 
 3         
 x1  0 
x  3 
⇒  2 =  
 x3  3 
   
 x4  0 
 1 0 
( e ) : B = [a 3 a 4 ] =  
 0 1 
1 0   x 3  6
⇒     =  
 0 1  x4  3 
−1
 x3  1 0  6 1 0   6  6
⇒  x  =  0 1  3  =  0 1  3  =  3 
 4         
 x1  0
x  0
⇒  2 =  
 x3  6
   
 x4  3 
 3  6   0   0 
 3 ,  0  ,  3  ,  0 
       
Let d = (d1 , d 2 ,…… d n ) be a direction of S
and | d1 | + | d2 | + + | dn |= d1 + d2 + + dn = 1
Hence the set D = {d | Ad ≤ 0,
Hence, 0 ∑ i =1 di = 11, di ≥ 00, i = 11, 22,…, n}
n

characterizes the set of recession directions of S.

We know that S={ X|AX≤b,X≥0}.

Let X S X +λd S,, λ≥0 AX ≤b ((1))
A(X +λd) ≤b, λ≥0 (2)
AX +Aλd≤b,, λ≥0 AX ≤b Aλd
=λ(Ad )≤0 , λ≥0 Ad≤0.
Proposition:
(i) If the set {d | Ad ≤ 0} = {0},
{0} then S is a polytope
polytope.
(ii) If S has a recession direction,
direction then the extreme
points of the polytope
D = {d | Ad ≤ 0, ∑ i=
n
d = 1, di ≥ 0, i = 1, 2,…, n}
i =1 i
is the the extreme directions of S.

Proposition: Let d1 , d 2 ,…… , d m be the extreme

directions of S.
S The LP has an optimal solution
if and only if
c⋅dj ≥ 0
 Proposition: If S is a polytope
polytope, then the LP has
an optimal solution.
solution
Proof:
Let f(X)=CX
f(X)=CX, X . Since S is a polytope
polytope, S is
convex and compact
compact. Clearly, S is connected and f
is continuous
continuous. By theorem,
theorem we have that f(S) is
compact and connected in
in

In fact,
SIMPLEX METHOD
O
GEORGE BERNARD DANTZIG
((NOVEMBER 8,, 1914 – MAY 13,, 2005))
THE JOHN VON NEUMANN THEORY PRIZE HAS BEEN AWARDED
SINCE 1975
975. THE FIRST RECIPIENT GEORGE B. DANTZIG FOR
HIS WORK ON LINEAR PROGRAMMING.
 Simplex Method

Consider the following linear programming:

Min CX Min CX
subject to AX≤b subject to AX=b
X≥0 X≥0
, Find the extreme
extreme.
Here CX = C1 X1 + C2 X 2 + + Cn X n
H
is the objective function.
function

A is the constraint matrix.

mat

The set of S={ X AX≤b , X≥0}

is called the feasible region.
region
The point X in S is called the feasible point.
point
The feasible point with the smallest objective
value is called the optimal solution
solution.
 Min CX
subject to AX=b
X≥0
,where A is an m n matrix with row rank(A)=m.

 B b
−1
Suppose that we have a feasible solution X =  
whose objective  0
 B −1b 
0 = CX = [C B N ]  = C B B −1
b,
 0
A = [B ]
where B is an m m basic matrix
and N is an m ((n-m)) nonbasic matrix.
 Let X B and X N denote the set of basic
and
d nonbasic
b i variables
i bl ffor B.
B
Then X B ≥0 and XN ≥0 ,
X 
b = A X =  B N   B  = B X B + N X N
Moreover,, X 
 N
⇒ BX B = b − NX N
⇒ X B = B − 1b − ( B − 1 N ) X N
= B − 1b − ∑
j∈ R
( B − 1a j ) X j

=b− ∑
j∈ R
yjX j

w here b = B − 1b and y j = B − 1 a j
R is a current set of indices of the nonbasic variables.
Hence,,X B = b − ∑ y j X j ((1))
j∈ R

XB 
Let  C B C N    = CB X B + CN X N
XN 
B (b − ∑ y j X j ) + ∑ C j X j
j∈ R j∈ R

B ( B −1
b) − ∑ C B y j X j + ∑ C j X j
j∈ R j∈ R

0 − ∑ (C B y j − C j ) X j
j∈ R

0 − ∑ (Z j − C j ) X j (2)
j∈ R
 Min 0 − ∑ ( Z j − C j )X j
j∈R

s.t. ∑ y j X j + X B = b
j∈R

Xj ≥ 0, j ∈ R
XB ≥ 0

( ) If Z j − C j ≤ 0 for
(1) f allll j R,
R
then the current basic solution
i the
is h optimal i l solution.
l i
solution
(2) If Zk −Ck > 0 for some k R,
then
h we can increase
i the
h value l off x k
0 Z = Z 0 − ( Z k − Ck ) X k , Z ↓ asX k ↑
 Leaving variables?
 X B   b1   y1k 
     
     
 
l
let X B =  X Br  = br −  y rk  xk (1)
     
     
 X Bm   b   y mk 
 m   
Z j − C j | j ∈ R} = Z k − C k (> 0)
(X k , X j = 0, j ≠ k )
X Br X k 0
(1 ) X Br 0
br
⇒ X k ↑ to , X Br ↓ to 0
y rk
 X Br
bi br
X k = min 1≤ i ≤ m { | yik > 0} = >0
yik y rk
⇒ X Br !
br
⇒ X Br → 0 , X k →
y rk
If w e fin d a c o rre s p o n d in g n o n b a s ic
v a r i a b le X k w i t h Z k − C k > 0 ( X j = 0 , j ≠ k )
−1 −1
th e n X B = B b − (B N )X N = B -1 b − y k X k

 B − 1b   − y k 
   
 0   0 
X     
{ X = 
B
 =  +   X k | X k ≥ 0} ∈ S
X N   0   1 
   
   
 0   0 
If y k ≤ 0 , then Z unboundness , Z → ∞
In fact
f , y k ≤ 0 iff Z unboundness.
b d
br bi
= m in
i 1≤ i ≤ m { | y ik > 0} m iinim
i all ratio
ti test.
t t
y rk y ik
(1) Xk , (2) X Br .
− yk 
 0 
 
 
If yk ≤ 0 ,   is a recession direction of feasible region S.
 1 
 
 
 0 
yk > 0 ⇒ ∃yik > 0
  − yk   − yk 
 0   0 
   
   
let d =   ⇒ C • d = [C B C N ]  
 1   1 
   
   
 0   0 
= ( − C B y k ) + C k = ( − Z k ) + C k < 0 ⇒ Z → −∞
The Simplex
p Method Algorithm
g
(Minimization Problem)
Initial Step: Choosing a starting basic feasible
solution(an extreme point of S)
Main Step:
(1)Solve BX B = b (X B =B-1b = b)
let X B = b = B −1b , X N = 0 and Z=C B X B =Z0
(2)Solve wB = CB (w = CB B −1 )
calculate wa j = c j = Z j − C j , j ∈ R
let Z k − Ck ≤ 0 , then STOP !
The current basic feasible solution is optimal.
Oth
Otherwise,
i GoG tot Step(3)
St (3) with
ith X k as the
th entering
t i variable.
i bl
(4) Let Xk enter the basis.
The
h iindex
d r off the
h variable
i bl X Br leaves
l the
h bbasis
i is
i
bi bi
determined by = min1≤i≤m{ | yik > 0}
yik yik
Update the basis B where ak replaces aBr
U d the
Update h iindex
d set R.
R
p Step(1).
Repeat p( )
Simplex Method in Tableau Format

Suppose that we have a starting basic

feasible solution X with the basis B.
B

The linear problem can be represented as follows.

follows
M in Z = C B X B + C N X N
s u b je c t to Z − C B X B − C N X N = 0
BX B + NX N = b
XB ≥ 0
XN ≥ 0
⇒ M in Z = C B X B + C N X N
s u b je c t to Z − C B X B − C N X N = 0
X B + B −1 N X N = B − 1b
X B ≥ 0
X N ≥ 0
⇒ M in
i Z = CB X B + CN X N

s u b je c t to 1 i Z + 0 i X B + (C B X B N − C N ) X N = CBb
1i X B + ( B −1 N ) X N = B − 1b = b
 −1
→ 1 0 C B B N − CN CB b
0 1 B −1 N B −1b = b

↓:
Z X Br ← ← XN → → RHS
Z 1 0 0 0 Z j − Cj Zk − Ck CB b
X B1 0 1 0 0 y1 j y1k b1

X Br 0 0 1 0 yrj yrk br

X Bm 0 0 0 1 ymj ymk bm
←:
Example :
Min x1 + x2 − 4x3 ⇒ Min x1 + x2 − 4x3 + 0x4 + 0x5 + 0x6
j to x1 + x2 + 2x3 ≤ 9
subject s.t. x1 + x2 + 2x3 + x4 =9
x1 + x2 − x3 ≤ 2 x1 + x2 − x3 + x5 =2
− x1 + x2 + x3 ≤ 4 − x1 + x2 + x3 + x6 = 4
x1 ≥0 xi ≥ 0 i = 1,2,3,4,5,6
x2 ≥0
x3 ≥ 0
 1 1 2 1 0 0
A = [ a1 a 2 a3 a 4 a5 a 6 ] =  1 1 − 1 0 1 0 
 − 1 1 1 0 0 1 
1 1 2 1 0 0 
= [ N B ] , where
h N =  1 1 − 1 , B =  0 1 0 
 − 1 1 1   0 0 1 

Z X4 X5 X6 X1 X 2 X 3 RHS
Z 1 0 0 0 −1 −1 4 0
X4 0 1 0 0 1 1 2 9
X5 0 0 1 0 1 1 −1 2
X6 0 0 0 1 −1 1 1 4
  x1   0 
x   
 2  0 
 x3   0 
Starting point :   =   X 3 eneter, X 6 leave
 x4   2 
 x  9 
 5  
 x6   4 
 4 0
 2 0
Next step,change the column of X 3 :   to be  
 −1 0
   
1 1 
 1 0 0
 
CB B = [ 0 0 0] 0 1 0 = [ 0 0 0]
−1

0 0 1
1 1 2  1 1 2 
−1   
B N = I  1 1 − 1 =  1 1 − 1 
 −1 1 1   −1 1 1 
CB B N − CN = [ 0 0 0] − [1 1 − 4] = [ −1 − 1 4]
−1
 The Two
Two--Phase Method
Phase1: Solve the following linear progam
g with the solution
starting

X = 0 and X a = b
Min 1 X a
s.t AX + X a = b
X ≥0
Xa ≥ 0
If the optimality X a ≠ 0 , then stop.
Otherwise,, let the basic and nonbasic variables to be X B and X N .
Phase2: Solve the following linear program
with feasible solution

−1
X B = B b and X N = 0
Min Z = C B X B + C N X N
−1 −1
s.t X B + B NX N = B b
XB ≥0
XN ≥ 0
E x : M in x1 − 2 x 2
s .t x1 + x2 ≥ 2
− x1 + x2 ≥ 1
x2 ≤ 3
x1 ≥ 0
x2 ≥ 0
⇒ x1 + x2 − x3 = 2
− x1 + x2 − x4 = 1
x2 + x5 = 3
x i ≥ 0 , i = 1, 2 , 3 , 4 , 5
 1 1 −1 0 0 
⇒ A = [a 1 a2 a3 a4 a 5 ] =  − 1 1 0 −1 0 

 0 1 0 0 1 
Phase1:
Starts by adding artificial variables x and x .

Min x6 + x7
s.t x1 + x2 − x3 + x6 =2
− x1 + x2 − x4 + x7 = 1
x2 + x5 =3
 1 1 − 1 0 0 1 0
 
⇒ A =  −1 1 0 − 1 0 0 1 
 0 1 0 0 1 0 0 
 Z x1 x2 x3 x4 x5 x6 x7 R .H .S
Z 1 0 0 0 0 0 -1 -1 0
x6 0 1 1 -1 0 0 1 0 2
x7 0 -1 1 0 -1 0 0 1 1
x5 0 0 1 0 0 1 0 0 3
⇓
Z x1 x2 x3 x4 x5 x6 x7 R .H .S
Z 1 0 2 -1 -1 0 -1 -1 3
x6 0 1 1 -1 0 0 1 0 2
x7 0 -11 (1 ) 0 -11 0 0 1 1
x5 0 0 1 0 0 1 0 0 3
 ⇓
Z x1 x2 x3 x4 x5 x6 x7 R .H .S
Z 1 2 0 -1 1 0 0 -2 1
x6 0 (2 ) 0 -1 1 0 1 -1 1
x7 0 -1 1 0 -1 0 0 1 1
x5 0 1 0 0 1 1 0 -1 2
⇓
Z x1 x2 x3 x4 x5 x6 x7 R .H .S
Z 1 2 0 -1 1 0 0 -2 1
x6 0 (2 ) 0 -1 1 0 1 -1 1
x7 0 -1 1 0 -1 0 0 1 1
x5 0 1 0 0 1 1 0 -1 2
 ⇓
Z x 1 x 2 x 3 x 4 x 5 x 6 x 7 R .H .S
Z 1 0 0 0 0 0 -1 -1 0
1 1 1 1 1
x 6 0 1 0 - 0 -
2 2 2 2 2
1 1 1 1 3
x 7 0 0 1 - - 0
2 2 2 2 2
1 1 1 1 3
x 5 0 0 0 1 - -
2 2 2 2 2
 1 
 2 
 x   

1
  3 
 x 2   2 
 x   0 

3
  
⇒ o p tim a l s o lu tio n :  x 4  =  0 
   

x 5
  3 
 x   2 

6
  0 
 x 7   
 0 
 
P h a s e 2 : M in Z − x1 + 2 x 2 + 0 x 3 + 0 x 4 + 0 x 5
Z x1 x 2 x 3 x 4 x 5 R . H .S
Z 1 -1 2 0 0 0 0
1 1 1
x1 0 1 0 - 0
2 2 2
1 1 3
x2 0 0 1 - - 0
2 2 2
1 1 3
x3 0 0 0 1
2 2 2
⇓
Z x1 x 2 x 3 x4 x5 R . H .S
1 3 5
Z 1 0 0 0
2 2 2
1 1 1
x1 0 1 0 - ( ) 0
2 2 2
1 1 3
x2 0 0 1 - - 0
2 2 2
1 1 3
x3 0 0 0 1
2 2 2
 ⇓
Z x1 x2 x3 x4 x5 R . H .S
Z 1 -1 0 0 0 -2 -6
x1 0 1 0 0 1 1 2
x2 0 0 1 0 0 1 3
x3 0 -1 0 1 0 1 1
 x1  0 
   
 x2  3 
⇒  x 3  = 1 
  
 x4  2 
  0 
 x 5   
⇒ x1 − 2 x 2 = 0 − 2 ( 3 ) = − 6 i s t h e m i n i m u m .
 Mi − x1 − 2 x2 + x3 − x4 − 4 x5 + 2 x6
E : Min
Ex
s.t x1 + x2 + x3 + x4 + x5 + x6 ≤ 6
2 x1 − x2 − 2 x3 + x4 ≤4
x3 + x4 + 2 x5 + x6 ≤ 4
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0
⇒ x1 + x2 + x3 + x4 + x5 + x6 + x7 =6
2 x1 − x2 − 2 x3 + x4 +x8 =4
x3 + x4 + 2 x5 + x6 + x9 = 4
xi ≥ 0, i = 1, 2, 3, 4, 5, 6, 7,8, 9
 1 1 1 1 1 1 1 0 0 
⇒ A =  2 - 1 - 2 1 0 0 0 1 0 
 0 0 1 1 2 1 0 0 1 
C = [- 1 - 2 1 - 1 - 4 2 0 0 0]
 x1  0 
  0 
 x2   
 x3  0 
   
 x4  0 
s ta r tin g b a s ic f e a s ib le s o lu tio n :  x 5  = 0 
   
 x6  0 
x  6 
 7   
 x8  4
  4
 x9   
 1 0 0 
  −1
B =  a 7 a8 a9  =  0 1 0 = B
0 0 1 


x7 x8 x9
Z 0 0 0 0
x7 1 0 0 6
x8 0 1 0 4
x9 0 0 1 4
z1 − c1 = 1, z 2 − c 2 = 2, z3 − c3 = − 1
z4 − c 4 = 1, z 5 − c 5 = 4 (* ), z6 − c6 = − 2
x7 x8 x9 x5 x7 x8 x9 x5
Z 0 0 0 0 4 Z 0 0 -2 -8 0
1
x7 1 0 0 6 1 ⇒ x7 1 0 - 4 0
2
x8 0 1 0 4 0 x8 0 1 0 4 0
1
x9 0 0 1 4 2 x9 0 0 2 1
2
Ite ra tio n 2 :
B = I 3 = B −1
x 7 x8 x 5
z 0 0 0 -8
x 7 1 0 0 4
x8 0 1 0 4
x 5 0 0 1 2
z1 − c1 = 1, z 2 − c 2 = 2 (* ), z 3 − c 3 = − 3
z 4 − c 4 = − 1, z 6 − c 6 = − 4 , z9 − c 9 = − 2
 x 1
  0 
   
 x 2   0 
 x   
 3  0
 
 x 4
  0 
    , C
N e w v e r te x :  x 5  = 
2  B =  0 0 - 2 
 x   0 
 6   
 x 7
  4 
   
 x  4
8  
 x   0 
 9 
 x7 x8 x5 x2 x7 x8 x5 x2
z 0 0 0 -8 2 z -2 0 0 -1 6 0
x7 1 0 0 4 1 ⇒ x7 1 0 0 4 1
x8 0 1 0 4 -1 x8 1 1 0 8 0
x5 0 0 1 2 0 x5 0 0 1 2 0

Ite ra tio n 3 :
−1
B = I3 = B
x2 x8 x5
z 0 0 0 -1 6
x2 1 0 0 4
x8 0 1 0 8
x5 0 0 1 2
z 1 − c 1 = − 1, z 3 − c 3 = − 4 , z 4 − c 4 = − 2
z6 − c6 = − 5, z7 − c7 = − ?, z9 − c9 = − 1
 Big-
Big
g-M Method
P: P( M ) :
Min CX Min CX + M i1i X a
s.t AX = b ⇒ s.t AX + X a = b
X ≥0 X ≥0
b≥0 Xa ≥ 0
where M is a sufficientily large positive real number.
number

(1) If ( X *, 0) is an optimal solution to problem P(M),

then
th X * mustt b be an optimal
ti l solution
l ti tot problem
bl P.
P
(2) If (X , X a ) is an optimal solution to P(M)
* *

and X a ≠0, and if M is a very large positive number,

number
then there exists no feasible solution to P.
E X : M in x1 − 2 x 2
s .t x1 + x 2 ≥ 2
− x1 + x 2 ≥ 1
x2 ≤ 3
x1 , x 2 ≥ 0
⇒ x1 + x 2 − x 3 + x6 = 2
− x1 + x 2 − x4 + x7 = 1
x2 + x5 =3
x i ≥ 0 , i = 11, 2 , 33, 4 , 5,
5 6, 7
 1 1 -1 0 0 1 0 
⇒ A =  -1 1 0 -1 0 0 1 
 0 1 0 0 1 0 0 
Min Z = x1 − 2 x2 + 0 x3 + 0 x4 + 0 x5 + Mx6 + Mx7
Z − x1 + 2 x2 + 0 x3 + 0 x4 + 0 x5 − Mx6 − Mx7
Z x1 x2 x3 x 4 x5 x6 x7 R.H.S
Z 1 -1 2 0 0 0 -M -M 0
x6 0 1 1 -1 0 0 1 0 2
x7 0 -1 1 0 -1 0 0 1 1
x5 0 0 1 0 0 1 0 0 3
⇓
Z x1 x2 x3 x4 x5 x 6 x 7 R.H.S
Z 1 -1 2M+2 -M -M 0 0 0 3M
x6 0 1 1 -11 0 0 1 0 2
x7 0 -1 (1) 0 -1 0 0 1 1
x5 0 0 1 0 0 1 0 0 3
 Z x1 x2 x3 x4 x5 x6 x7 R.H.S
Z 1 2M +1 0 -M M +2 0 0 -2M -2 M -2
x6 0 (2) 0 -1 1 0 1 -1 1
x2 0 -1 1 0 -1 0 0 1 1
x5 0 1 0 0 1 1 0 -1 2
⇓
Z x1 x 2 x3 x4 x5 x6 x7 R.H.S
1 3 1 3 5
Z 1 0 0 0 -M - -M - -
2 2 2 2 2
1 1 1 1 1
x1 0 1 0 - ( ) 0 -
2 2 2 2 2
1 1 1 1 3
x2 0 0 1 - - 0
2 2 2 2 2
1 1 3 3
x5 0 0 0 1 1 -
2 2 2 2
 Z x1 x2 x3 x4 x5 x6 x7 RHS
R.H.S
Z 1 -3 0 2 0 0 -M-2 -M -4
x4 0 2 0 -11 1 0 1 -1
1 1
x2 0 1 1 -1 0 0 1 0 2
x5 0 -1 0 (1) 0 1 -1 0 1
⇓
Z x1 x2 x3 x4 x5 x6 x7 R.H.S
Z 1 -1 0 0 0 -2 -M -M -6
x4 0 1 0 0 1 1 0 -1 2
x2 0 0 1 0 0 1 0 0 3
x3 0 -1 0 1 0 1 -1 0 1
STOP!
The cone generated by the rows of the m× n matrix A
is C = {At x | x ≥ 0}.

Def:
Let S be a nonempty subset in R n .
Then the polar cone (dual cone ) of S,
denoted by S* ,is given by { p | px ≤ 0 for all x ∈ S} ≠ ∅.

Lemma:
Let A be a m × n matrix and let C = {A t y | y ≥ 0}
Then C* = { x | Ax ≤ 0 }
 Farkas'' Lemma
Farkas

System 1:AX ≤ 0 and c X>0, t

System 2:At y = c and y ≥ 0,

0
exact one of the two systems has a solution.
if System 2 has a solution:
⇒ ∃y s.tt At y = c andd y ≥ 0 ⇒ c ∈ C.
C
if System
y 1 has a solution:
⇒ ∃x s.t Ax ≤ 0 and c x > 0 ⇒ x ∈ C ⇒ c ∉ (C ) = C
t * * *
E X : S h o w th a t th e s y s te m x1 + x 2 ≤ 0
2 x2 ≤ 0
− x1 + 4 x 2 ≤ 0
x1 , x 2 ≥ 0
x 1 + 4 x 2 is n o t fe a s ib le .

(1) AX≤0 and cX>0

A cone , System1
y X .
(2) wA=c, w≥0, w !
 1 1
 3 
 1 0   0 2  = [1 4 ]
2 
 -1 4 
3
⇔ 1 [1 1 ] + [ 0 2 ] + 0 [ -1 4 ] = [1 4 ]
2
 3 
⇒ w = 1 0  ⇒ S y s tte m (2 ) iis fe
f a s ib le
l .
 2 
by F a rk a s 's le m m a ,S y s te m (1 ) is n o t fe a s ib le .
Consider the LP problem:
Mi CX
Min where
h C is
i an n-row vector,
t
s.t. AX≥b b is an m-column vector,
X 0
X≥0 A is
i an m n matrix.
t i

The Karush
Karush--Kuhn-
Kuhn-Tucker ((KKT))
conditions for inequality constraints:

The LP problem (P) has an optimal solution X iff

c lies in the cone generated by the normal vector
(gradient) of the binding constraints at X .
ALBERT WILLIAM TUCKER
(DECEMBER 28, 1903 – FEBRUARY 8, 1957)
WITH HAROLD KUHN AND DAVID GALE, ALBERT WILLIAM
TUCKER WON THE JOHN VON NEUMANN THEORY PRIZE IN
1980.
1980 HAROLD KUHN, JOHN NASH, LLOYD
SHAPLEY DAVID GALE
HAROLD KUHN
WITH ALBERT WILLIAM TUCKER AND DAVID GALE, HAROLD KUHN
WON THE JOHN VON NEUMANN THEORY PRIZE IN 1980
980.
DAVID GALE
(DECEMBER 13, 1921 – MARCH 7, 2008)
WITH ALBERT WILLIAM TUCKER AND HAROLD KUHN, DAVID GALE
WON THE JOHN VON NEUMANN THEORY PRIZE IN 1980
980.
E X :M i n − 2 x1 + 5 x 2
s .t − 3 x 1 − 8 x 2 ≥ − 1 2
− 2 x1 − 3 x 2 ≥ − 6
x1 ≥ 0
x2 ≥ 0
 x1  3 
o p tim a l s o lu tio n :   =  
 x2  0 
3 
0 − 2 x1 − 3 x 2 = − 6 , x 2 = 0
 
 -2 -3 
⇒ [1 8 ]   = [- 2 5 ]
 0 1
  -2 3   3   -66 
2 -3  d1 
P f:( ⇒ )     =  , d irectio n  
 0 1  0  0  d2 
 -2 -3   d 1  0  d1 
su ch th a t     ≥  0  a n d [ -2 5 ]  d  < 0 .
 0 1  d2     2
b y F ark as'
as L em m a,
a
c (-2, 5) [ -2 -3 ] & [ 0 1]
 -3
3 8
-8
 -2 -3 
 d1 
d  . [0 1 0 8 ]  = [ -2 5 ]
 2  1 0
 
 0 1
 A
⇒ [w v ]   = c
I 
(KKT)
Min CX
s.t. AX ≥ b feasible X
X≥0
 A
⇔ [ w v ]   = c, w ≥ 0,, v ≥ 0.
I 
⇔ wA+v = c,w ≥ 0, v ≥ 0 and w,v:feasible.
⇒ w(AX − b) = 0, vX = 0, w ≥ 0, v ≥ 0 and w,v:feasible
⇒ (wA+v)X
(wA+v)X=cX
cX
⇒ wAX+vX=cX
  -3 -8   x1   x1 
[0 1 ]     + [0 8 ]  
 - 2 - 3   2 
x  2 
x
∵ A X -b ≥ 0 ⇒ w (A X -b ) ≥ 0
w (A X -b )= 0
 -3 x1 -8 x 2 + 1 2 
⇒ [0 1 ]   = [0 0 ]
 -2 x1 -3 x 2 + 6 
 x1 
[0 8 ]   = 0
 x2 
[w v ]⇒ w (A X -b )= 0
vX =0
X .
E X :W r i t e K K T c o n d i t i o n s f o r t h e p r o b le m :
M ax C X
s .t . A X ≤ b
X ≥ 0
⇒ M i n -C X
s .t . -A X ≥ -b X i s f e a s i b le .
X ≥ 0
 -A 
⇔  w v    = -c , w ≥ 0 ,v ≥ 0 a n d f e a s i b le .
 I 
⇔ -w A + v = -c , w ≥ 0 ,v ≥ 0
w A + v = c , w ≥ 0 ,v ≥ 0 ,
w ( A X -b b )= 0
vX =0
X ≥ 0
⇒ w ( -A X + b ) = 0
v X = 0 X i s f e a s i b le .
X ≥ 0
⇒ X X.
Duality:
((P)) Min CX ⇔ (D)
( ) Max wb
AX ≥ b wA ≤ C ⇔ At wt ≤ Ct
X≥0 w≥0

Recall: (KKT)
The LP problem
oble (P) has
ha an
a optimal
o ti al solution
ol tio X,
X
if and only if,
c lies in the cone generated by
b the normal vector
ector
(gradient) of the binding constraints at X.
By KKT condition
condition,
the optimal solution X * of ( P ) must satisfy :
(1)AX ≥ b, X ≥ 0;
A 
(2) [ w v ]   =c, w ≥ 0, v ≥ 0;
 I
(3) (AX b) 0 vX=0
(3)w(AX-b)=0, X 0

it means that w * must can be found and satisfy :

(a)wA ≤ c,
c w ≥ 0;
(b)cX * =w * AX * =w * b {(P) (D) }
p ro o f :
A 
[
(a ) B y (2 ) , S in c e
w v ]  = c
 I
⇔ w A + v= c and w ≥ 0, v ≥ 0
⇒ w A ≤ c, w ≥ 0
( b ) B y ( 3 ) , w * ( A X * -b ) = 0
A  *
a n d  w v    X = c X * a n d v * X * = 0
* *

 I
⇒ w * A X * + v * IX * = c X *
⇒ w *A X * = cX *
B y (1 ) , A X ≥ b ⇒ w A X ≥ w b , w ≥ 0
⇒ cX ≥ w A X ≥ w b, X ≥ 0
X *, w * ⇒ cX * = w *A X * = w *b
S in c e c X ≥ w A X ≥ w b , fo r w ≥ 0 , X ≥ 0
cX cX * , cX * = w *b X* (P ) .
wb w *b, cX * = w *b w *
(D ) .
Example 1:
Consider the following primal and dual problems.
( P ) Min 2x1 + 3x2 + 5 x3 + 2 x4 + 3x5
s.t. x1 + x2 + 2 x3 + x4 + 3 x5 ≥ 4
2 x1 − 2 x2 + 3 x3 + x4 + x5 ≥ 3
x1 ≥0
x2 ≥0
x3 ≥0
x4 ≥0
x5 ≥ 0
 4
(D ) M ax [ w 1 w 2 ]   = 4 w 1 + 3 w 2
3 
1 1 2 1 3 
s.t. [ w 1 w 2 ]   ≤ [2 3 5 2 3 ]
 2 -2 3 1 1 
t
1 1 2 1 3 
⇒  [w 1 w 2 ] ≤ [2 3 5 2 3 ]
t t

 2 -2 3 1 1 
1 2  2
1 -22  3 
  w   

⇒ 2 3   1
 ≤ 5 
  w 2   
1 1  2
 3 1   3 
⇒ 1w1 +2w 2 ≤ 2 ((*))
1w1 -2w 2 ≤ 3
2w1 +3w 2 ≤ 5
1w1 +2w 2 ≤ 2
3w 1 2 ≤3
3 1 +1w (*)
w1 ≥0
w2 ≥ 0
4 3
⇒ ( w1 , w 2 ) =(( , )
5 5
((run simplex
p method,, 1st 5th )
4 4 3
⇒ Max [ w1 w 2 ]   =4w1 +3w 2 =4 × +3 × =5.
3  5 5
E xam ple2 :
n , j i a ij
(P ) M in c1 x1 + + cn xn
xj j ,cj j )
s .t . a11 x1 + + a1 n x n ≥ b1

a m 1 x1 + + a m n x n ≥ bm
x1 , x 2 , , , xn ≥ 0
: i bi
(D ) M ax b1 w1 + + bm w m w i i )
s .t . a11 w1 + + a m 1 w m ≤ c1

a 1 n w1 + + amn wm ≤ cn
w1 , w 2 , , , wn ≥ 0
: j cj
Game Theory

Theory
Th off Games
G anddEEconomici
Behavior-- published in 1944 by
Behavior

John Von Neumann and Oskar

Morgenstern
JOHN VON NEUMANN
(DECEMBER 28, 1903 – FEBRUARY 8, 1957)
Game theory y is the logical
g analysis
y
of situation of conflict and
cooperation..
cooperation
Ag
game is defined to any
y situation in which

(1) There are at least two players.

players
(2) Each player has a number of possible strategies
which he or she may choose to follow.
(3) The strategies chosen by each player
determines the outcome of the game.
(4) Associated to each possible outcome
of the game is a collection of numerical payoff
payoff.
T -Person
Two-
Two P Zero
Z Sum
S G
Game

(1) There are two players.

players
(2) Th
The row player
l mustt choose
h 1 off m strategies.
t t i
Simultaneously,the column player
must choose 1 of n strategies.
strategies
(3) If the row player choose his i-th strategy
and the column player choose his j-th strategy,
then the row player receives a reward of a ij
and the column player lose an amount a ij .
N -Cooperative
Non-
Non C i G Game
 John
J h Forbes
F b Nash
N h
( John Nash won the 1994 Nobel Memorial Prize in Economic
Sciences )
won the John von Neumann Theory Prize in 1978.
1978
Two--person Zero Sum Game
Two Nash Equilibrium

min max
max min
Nash Equilibrium.
Equilibrium
(Nash Equilibrium
Zero Sum Game ((Two Persons))

Ex:
 (+2, −2) (+1.5, −1.5) 
(+1.5, −1.5) 
(+2.5, − 2.5)

(+2, −2) (+2, −2) 
(+1, 
 1 −1) (+3,
( 3 − 3)
 ((10,10) ( , 25)) 
, ) (1,
 (25,1) 
 (3,3) 
 (60, 60) (36, 70) (36, 35) 
 (70, 36) (50, 50) (30, 35) 
 
 (35,
(35 36) (35 (25, 25) 
(35, 30) (25
N-Person Cooperative Game
Def: For each subset of N={1,2,‫ڮ‬,n},
{ , , , },
the characteristic function v of a game
gives amount v(S),
th th
then thatt numbers
b off S can b
be sure off receiving
i i
if they act together and form a coaliton
coaliton.
n
If X = ( X 1 , X 2 , " , X n ) , ∑X
i =1
i = v( N )

satisfies Xi ≥ v(i) for each i‫א‬N,

then X is called an imputation (allocation
allocation).
W say th
We thatt th
the iimputation
t ti y d dominate
i t x
through a coalition S, written
y doms x, if ∑ i∈s
yi ≤ v ( S ) and yi > xi for each i ∈ S .
C
Cooperative
i Game
G
Core

Question :
Sol :
v : 2{ , , }
\ {∅} → ℜ + ∪ {0}
({ }) = 0,, v({
v({ ({ }) = 0,, v({
({ }) = 0,, v({
({ }) = 0,,
v({ , }) = 0, v({ , }) = ( 2 − p ) + ( p − 1) = 1,
( p ⇒ 1 ≤ p ≤ 2,
2 : 2 − p,
p : p − 1)
v({ , }) = ( 2 − p ) + ( p − 1) = 1
v{( , , )} = 1 ( )
( x1 , x 2 , x 3 ) ⇒ x1 + x 2 + x 3 = v{(
{( , , )} = 1
x1, x 2 ,x 3 ≥ 0
x 1 + x 2 + x 3 = v{ ( , , )} = 1
x 1 + x 2 ≥ v ({ , }) = 1
x 1 + x 3 ≥ v ({ , }) = 1
x 2 + x 3 ≥ v ({ , }) = 0
x 1 ≥ v ({ }) = 0
x 2 ≥ v ({ }) = 0
x 3 ≥ v ({ }) = 0
⇒ s o l u t i o n (1 , 0 , 0 ) :
Def: The core of an n-person game (N,v)
is the set C(
C(N,
N,vv) satisfies
∑ i∈ s
X i ≥ v ( S ), ∀ S ⊂ N , S ≠ ∅

Def: X ∈ Core( N , v) iff ∑ i∈S

X i ≥ v(S ), ∀S ⊂ N , S ≠ ∅.
n

∑X
i =1
i = v( N ), X i ≥ v(i), ∀i ∈ N ,

N = {1, 2,", n}, v : characteristic function.

Shapley
p y Value -1953
1953,, Lloyd
y Shapley
p y

S ap ey Va
Shapley Value
ue
Given any n-person game with the characteristic function v,
define v(‫׎‬
‫=)׎‬0
0, there is a unique vector X = ( x 1 , x 2 , " , x n ),
(n − k )!
w ith X i = ∑S n!
[ v ( S ) − v ( S \ {i})], k = | S |
i∈ S

1
∑
S  n −1
[ v ( S ) − v ( S ) \ {i})]
i∈ S  
 k − 1 
=
n
1
= ∑
S  n −1
[ v ( S ) − v ( S ) \ {i})], | S |= k = 1, 2, " , n .
i∈ S n 
 k − 1 
LLOYD SHAPLEY
( SHAPLEY WON THE 2012 NOBEL MEMORIAL PRIZE IN
ECONOMIC SCIENCES ). WON THE JOHN VON
NEUMANN THEORY PRIZE IN 1981
1981.
EX :
N= ={1,2}
{1 2}
v(1,2) = 1, v(2) = 0, v(1) = 0
(2 −1)!(1−1)! (2 − 2)!(2 −1)!
X1 = [v(1) − v(∅)] + [v(1,2) − v(2)]
2! 2!
1 1 1
= (0 − 0) + (1− 0) =
2 2 2
1
X2 =
2
Sol :
X = ( X B , X G , X O , X C ), N = ( B , G , O , C )
v(B,G ) = v(B,O ) = v(B,C )
= v(B,G ,O ) = v(B,G ,C )
= v(B,O , C ) = v(B, G ,O ,C )
= 1( )
h e r w iise , v ( S ) = 0
O th
XB
(4 − 2)!(2 −1)!
= {[v(B, G) − v(G)] + [v(B, O) − v(O)] + [v(B, C) − v(C)]}
4!
(4 − 3)!(3 −1)!
+ {[v(B, G, O) − v(G, O)] + [v(B, G, C) − v(G, C)] + [v(B, O, C) − v(O, C)]}
4!
(4 − 4)!(4 −1)!
+ [v(B, G, O, C) − v(G, O, C)]
4!
2 3 1
= + =
12 12 2
1
XG = XO = XC =
6
1 1 1 1
⇒ X = ( XB , XG , XO , XC ) = ( , , , )).
2 6 6 6
Ex: (Airport Pricing)
S l:
Sol
N ={ , , }
v (∅ ) = 0, v ( ) = −100, v ( ) = v ( , ) = − 150
v( ) = v( , = v( , ) = v( , , ) = −400
⇒ ϕ ( N , v ) = (ϕ (v )), ϕ (v )), ϕ (v ) )
 200 350 1850 
= − ,− ,− 
 6 6 6 
X : X : X = 4 : 7 : 37