Surviving Problem price Cl C2 Cn healthy vitamin 1 a11 a12 ● ain ≥b1 ● 。 。 vitamin m aml am2 ●●●●0 amn ≥bm solution: X1 X2 Xn minimize the total price while keeping healthy
Surviving Problem c1 c2 cn a11 a12 a1n am1 am2 amn price vitamin 1 vitamin m ≥ b1 ≥ bm solution: x1 x2 xn healthy minimize the total price while keeping healthy
Surviving Problem min cTx s.t.Ax≥b x≥0 price C1 C2 Cn healthy vitamin 1 a11 a12 ain ≥b1 ● 。 vitamin m aml am2 ●●●●0 Amn ≥bm solution: X1 X2 Xn minimize the total price while keeping healthy
Surviving Problem c1 c2 cn a11 a12 a1n am1 am2 amn price vitamin 1 vitamin m ≥ b1 ≥ bm solution: x1 x2 xn healthy minimize the total price while keeping healthy min cTx s.t. Ax ≥ b x ≥ 0
LP Duality Primal: Dual: min cTx max bTy s.t.Ax≥b s.t.ATy≤c x≥0 y≥0 dual solution:price Cl C2 ●● Cn healthy yi vitamin 1 a11 a12 ●●●●● aIn ≥b1 : 。 ym vitamin m aml am2 Amn ≥bm m types of vitamin pills,design a pricing system competitive to n natural foods, max the total price
LP Duality c1 c2 cn a11 a12 a1n am1 am2 amn price vitamin 1 vitamin m ≥ b1 ≥ bm healthy min cTx s.t. Ax ≥ b x ≥ 0 Primal: Dual: max bTy s.t. y ≥ 0 ATy ≤ c y1 ym dual solution: m types of vitamin pills, design a pricing system competitive to n natural foods, max the total price
LP Duality Primal: Dual: min cTx ≥ max bTy s.t.Ax≥b S.t.ATy≤c x≥0 y≥0 ·Monogamy:dual(dual(LP》=LP 。Weak duality: v feasible primal solution x and y feasible dual solution y yTb≤yTAx≤cTx
LP Duality min cTx s.t. Ax ≥ b x ≥ 0 Primal: Dual: • Monogamy: dual(dual(LP)) = LP • Weak duality: • ∀ feasible primal solution x and ∀ feasible dual solution y y yTA x ≤ cTx Tb ≤ ≥ max bTy s.t. y ≥ 0 ATy ≤ c
LP Duality Primal: Dual: min cTx max bTy s.t.Ax≥b st.ATy≤c x≥0 y≥0 Weak Duality Theorem: V feasible primal solution x and feasible dual solution y: bTy≤cTx
LP Duality min cTx s.t. Ax ≥ b x ≥ 0 Primal: Dual: max bTy s.t. y ≥ 0 ATy ≤ c Weak Duality Theorem: ∀ feasible primal solution x and ∀ feasible dual solution y: bTy ≤ cTx