Duality
maximise II
subject to AI Ek primal
I 2 I
minimise
sty
subject to Aty Z E dual
f Ze
maximise 2 it 3 2 t X
I t x z X E IO H
tz X t al z E 8 XZ
x t xz 23 E 4
Xi 2 X3 ZO
Z X f 3 2 t X s E 32 t 3 2 3 3 E 30
Iv
combination
coefficients in multiply by non
are at least coefficients in negative
objective
2 a t 3 Iz t Iz E ZX t 3 2 t X 3 E 26
, minimise
EF
puall
Subject to Atif c
0
ye
Ex sci's
cogy
Ai ly t Ar A 3,1
l
Yz
t
Y3 Z C
In general
maximise L minimize
non negative variable L S z constraint
xj
unrestricted variable xj L constraint
objective Ex RHS
L c
LHS Asc L LHS At y
RHS b L Objective bty
L
E constraint non
negative variable y
constraint L unrestricted
variably yi
, its dual is minimise
Finding the dual
of a
program ie
if it's maximise
To take the dual a program
of
11 Make sure all inequalities are the form
of
T
a I Eb l maximise leave equations as
for programs
of I I b l
for minimise programs they are the equdtoones
Make sure all variables are either non negative or unrestricted
2 Introduce a new variable Xi
for each constraint in the primal
LP
g the ith constraint is an
I inequality then Yi Zo
I the ith constraint is an then yi is unrestricted
g equation
3 set the goal to be the opposite primal goal Form the
of the
multiplying each bi Cthe RHS the corresponding
objective by yi by of
primal constraint and adding
That is the objective is bTy
4 construct dual constraints care
for earn primal value x
at the LHS the constraint to xj in the primal
of corresponding
will be j
maximise II
subject to AI Ek primal
I 2 I
minimise
sty
subject to Aty Z E dual
f Ze
maximise 2 it 3 2 t X
I t x z X E IO H
tz X t al z E 8 XZ
x t xz 23 E 4
Xi 2 X3 ZO
Z X f 3 2 t X s E 32 t 3 2 3 3 E 30
Iv
combination
coefficients in multiply by non
are at least coefficients in negative
objective
2 a t 3 Iz t Iz E ZX t 3 2 t X 3 E 26
, minimise
EF
puall
Subject to Atif c
0
ye
Ex sci's
cogy
Ai ly t Ar A 3,1
l
Yz
t
Y3 Z C
In general
maximise L minimize
non negative variable L S z constraint
xj
unrestricted variable xj L constraint
objective Ex RHS
L c
LHS Asc L LHS At y
RHS b L Objective bty
L
E constraint non
negative variable y
constraint L unrestricted
variably yi
, its dual is minimise
Finding the dual
of a
program ie
if it's maximise
To take the dual a program
of
11 Make sure all inequalities are the form
of
T
a I Eb l maximise leave equations as
for programs
of I I b l
for minimise programs they are the equdtoones
Make sure all variables are either non negative or unrestricted
2 Introduce a new variable Xi
for each constraint in the primal
LP
g the ith constraint is an
I inequality then Yi Zo
I the ith constraint is an then yi is unrestricted
g equation
3 set the goal to be the opposite primal goal Form the
of the
multiplying each bi Cthe RHS the corresponding
objective by yi by of
primal constraint and adding
That is the objective is bTy
4 construct dual constraints care
for earn primal value x
at the LHS the constraint to xj in the primal
of corresponding
will be j
