Standard form of linear program Lp

min Ctx At Ai to Kit 2 i

i n
p
HEIR
where A E 112m
Ejb ti
MI Xi so use Zi as the
multiplier
ATX bi i m

use y as the multiplier to hike aixtbi

Claim linear objective
any Lp i.e an
optimization problem with
And linear Constraints

can be formulated into an

equivalent Lp in the form D

If a wax LP then we can change it into a min

Lp
linear objective
by negating the

If there is an inequality constraint a'x Ed then we can

introduce a
nonnegative variable azo and equivalently

reformulate atx ed te fait tu d Uzo

If there is a
free variable Xi Elk then we can
split
Xi At Xi where At Max o
Ail i Millo til
Hence Xi
Elk Can be split into two
nonnegative variables

KKT Conditions for P

Dfl Et
É [Link] Zi
[Link]
8 Zito tiara in

Pf AX b Xi to i i s n
h

CS Xi Zi o Dia n
Remark PF can be written into C Aty Z 3 225

Dual problem The

ordinary Lagrangian function is

Lex y Zi Ex EE Jil [Link] I Zil Xi

cTx ytlAx by Zix

The dual function is

LIL Lex y
21
dly 21

Ms ex y't Ax bl Ex

min e Ay
2 Fx t by
p if c A'y Z 8
g

by aw

so the dual problem is

Max Z
Aly ft 28
Y Z

max
Y Z by at 225 c
Ay 2 5 D
Duality Thorn
1 has
If either p or D a
finite optimal solution then
So does the other and their
one
optimal objective values
are the sand

has an unboundedobjective then

2
If either p or D

the other one is infeasible

Basic feasible solution

Def a feasible solution x

of p i 1 Ax b Rito Kit in
called basic feasible solution there is an index set
is a
if
Bex I 91,2 n n such that Bex m and Xi Vi
o
f Bix
B Ai is
nonsingular where 173411 denotes
em the

cardinality of Phi and Ai is the i th column

of A
Example If A 1 1 E 112 we m t has

then I is a basic feasible solution

of XE E Ax L X A X 20

BII 14 Bail a k o B i
nonsingular

But I Yg is feasible but not basic feasible

 Az n

o i Tx

Theorem Assume HE 112h has fun row rank

has feasible
as If Ipl a
pt then there must be a basic

feasible
pt
then at least
121 If p has a
finite optimal solution one

solution a basic solution

optimal is
optimal
Remark hot all solutions are basic
optimal

Derivation of the simplex method

Idea move from one basic feasible solution to another and

meanwhile decrease the objective value

Set let x be a basic feasible solution Then there is

up
Dex I liz i
i n as
specified in the definition
Denote Bex as B
Let us liz LY B B CAiJiep N Alien
Also let Xp Wilier An Xi
lien
Refire Cp Cn Zp and Zn Similarly
 Note Xn 5 and Ax b so B xp Nan b

Therefore Bop b Ap B'b

Choose
Zp P if x is nondegenerate then
Zp 5

From the DF Aty the C i.e

BE y
I L
By Ep C
Y B i'c

Ny ten on En en n'y en NCB i'c

Discuss where Zn 25
Case 1 if Zn 25 then the Kkt system holds at x y 21
So x is a
primal optimal solution
YZ is a dual
optimal solution
Case I if Zuko there such that co
i.e is
few 8
then perform update
choose f EN to enter the basis index set

and remove one index

p E B out from B
Recall Xi Vi
Nof o er
Increase
Aq from o to a
nonnegative number but

maintain Xi o f ie 84 and also keep the

feasibility of a new iterate at

c l
Axt b At25 until Apt for some PEP
change the basics index set Rt B 4750184

How to change Xp if Aq is increased

Suppose
Xp Agt and apt to have Axt b
xp
Then Axt Bx Nxt BestAgri b Bx

Xp x
B'Agra
Denote W B Aq
Case I 1
for then have XI 25
if wi o some i to

choose
we
Xf as

not Ii
Assume XB
i
anghin
i wi
Then XI o
Wis
and
Xp 20 Viti
Let up 731 to leave B
Case I 2
if W est claim Ipl is unbounded

How the objective value changer in Case I 1

Ext CIXI Cixi

Cixi taxi
 93 X B Agra tCqxq

Cfx 9513 Aqui squat

so c'I
I Cq 9515Aq7xqt
leg 5AqIxÉ ZqxÉ so
y
CB's y Bite T
Zn Cn Ny
Theorem If p has an the simplex method
optimal solution then
must find a basic optimal solution within finite iterations

Remark
although it is finite convergence the number of iterations
can be the
exponential about problem dimension

Procedure
of the simplex method for solving P
one
single Fap
Given a basic feasible solution x with corresponding basis
index set B then X B b 25 AN 5
1
y B'CB and Zn Cn Ny
If 2m25 then claim
optimality of x and stop

2 Select with Zac o

of EM
compute w B Ag If we 5 claim unbounded and
flop
3 At min AB
Ag Wi
Wis
I Eism

And 7 B i

71
where i agmin
i Wi o Wi
m
take the io th inde from B

4 update Xp Xp what
Ant 10 o
ft o 01

and B BUSES 574

Example min O Xi 12 X
X X

ft X 2 2 20 t
2X X E 20

Introduce 757 Razo Pt is equivalent to

Min lo Xi 12 2

74124
It X tax TX 20

Ax b
Tx Tx so
X 20 X P X
320 7470
2 1 0

Ii
Let c
A L I
b
f
o
choose as the basic feasible solution
x
Ig 25

3,44 N 1,2
13
1 N
L
9
1 Cnt
1
9 13 s L En en my I 2
15
2 Select and Z lo

fax
W B Aq A L
3 Agt At min l o
I Eisa Wis wi

i
argmin XB p
Isis Wi r Wi Compare
It to
Il
I 2
11
so
P N 4 I
4
update xp xp wot 13 I to
L
Xi so At because
LI Xpt
N
75
421
13,44
 25 80914 345 1 3

How to Start the

simplex method

Ctx St Ax 725
Yg
b
p
where HE 112m has a
full row rank

To find basic feasible solution solve

of
a Pl we

Mineta ft Axt drag sigalbi u b

Xen p
L Elem 725 use
where e
f elk drag sign
o
i

signs
and if a o
Sigala
y
if a c

Note
Y is a basic feasible solution to P
EI with B htt nth

suppose É is an
optimal basic solution of p's found

by the simplex method

Claims If hasfeasible solution then p's must

a
p
have optimal basic solution and 3
an
a
Pf Let I be a feasible solution of p
Then
I is a feasible solution of p

and the objective value

of p's at É is o

9
I is an
optimal solution of p's since Enzo
t use
Chainz t 5 then
If I p is infeasible

Claim 3
Zf p is feasible and
E É is no
degenerate

then I is basic feasible solution of

CMJ
a

all basis components are

positive
Example degenerate basic feasible solution

i t X 2
XE IRS I 70 Xa 20 X Jo
22 X o

Then
E is but degenerate
amyfigghtion
but
I
inggteaseusatin