Linear Programming
Linear Programming
Maximum Flow digraph:D(V,E) source:s sink:t capacity:.c:E→R+ max ∑fu u:(s,u)∈E S.t.0≤fu≤Cuw ∀(u,v)∈E ∑fuu-∑fw=0 u∈V\{s,ty w:(w,u)∈E w:(u,v)∈E
Maximum Flow digraph: D(V,E) capacity: source: s sink: t max u:(s,u)E fsu ⇥(u, v) E ⇥u V \ {s, t} w:(w,u)E fwu v:(u,v)E fuv = 0 s.t. 0 fuv cuv c : E R+
Diet Problem calories Cl C2 ●●●●● Cn healthy vitamin 1 a11 a12 ●●● aIn ≥b1 ● vitamin mn aml ☑m2 ●●●●●● amn ≥bm solution: X1 X2 Xn minimize the total calories while keeping healthy
c1 c2 cn a11 a12 a1n am1 am2 amn Diet Problem calories vitamin 1 vitamin m ≥ b1 ≥ bm solution: x1 x2 xn healthy minimize the total calories while keeping healthy
Diet Problem minimize ∑ CjTj subject to aici≥b, 1≤i≤m = x)≥0 1≤i≤m calories C1 C2 Cn healthy vitamin 1 a11 a12 ●●● ain ≥b1 。 vitamin m aml am2 ●●●●●● amn ≥bm solution: X2 Xn minimize the calories while keeping healthy
c1 c2 cn a11 a12 a1n am1 am2 amn Diet Problem calories vitamin 1 vitamin m ≥ b1 ≥ bm solution: x1 x2 xn healthy minimize the calories while keeping healthy minimize subject to n j=1 aijxj bi ⇥1 i m xj 0 ⇥1 i m n j=1 cjxj
Diet Problem minimize cTx subject to】 Ax≥b x≥0 calories Cl C2 Cn healthy vitamin 1 a11 a12 ●●● ●●● aIn ≥b1 vitamin mn aml ☑m2 amn ≥bm solution: X1 X2 Xn minimize the calories while keeping healthy
c1 c2 cn a11 a12 a1n am1 am2 amn Diet Problem calories vitamin 1 vitamin m ≥ b1 ≥ bm solution: x1 x2 xn healthy minimize the calories while keeping healthy minimize cTx subject to Ax ≥ b x ≥ 0