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
Linear Programming(LP) general form: matrix A={aij}mxn sets M C[m NCIn] min cTx s.t. ata bi i∈M ax≥b i∈M x1≥0 j∈N i unconstrained j∈N
Linear Programming (LP) general form: matrix A = {aij}mn sets M [m] N [n] min s.t. cT x aT i x = bi aT i x bi xj 0 xj unconstrained i M i M j N j N
Canonical Form for LP general form: canonical form: min cTx mxn matrix A S.t. afa bi i∈M ax≥bi i∈M min cTa x≥0 i∈N s.t.Ac≥b xj unconstrained i∈N ≥0 afx=bi日 ac≥b ≥0 i unconstrained ≥0 xj=xj
Canonical Form for LP min s.t. cT x aT i x = bi aT i x bi xj 0 xj unconstrained i M i M i N i N general form: canonical form: min s.t. cT x Ax b x 0 m×n matrix A aT i x = bi xj unconstrained aT i x ⇥ bi aT i x ⇥ bi x+ j 0 x j 0 xj = x+ j x j
Standard Form for LP canonical form: standard form: mxn matrix A mxn matrix A min cTx min cTa s.t.Ax >b s.t.Ax=b x≥0 x≥0 m ∑ajj≥b,日 aijj-si=bi 1=1 1=1 Si≥0 slack variable
Standard Form for LP standard form: min s.t. cT x m×n matrix A Ax = b x 0 canonical form: min s.t. cT x Ax b x 0 m×n matrix A slack variable n j=1 aijxj bi n j=1 aijxj si = bi si ⇥ 0
Convex Polytopes hyperplane: subspace of dimension n-1 》∑ajxj=b j=1 (closed)halfspace: ∑aj≥b j=1 convex polyhedron: intersection of halfspaces convex polytope: bounded convex polyhedron
Convex Polytopes hyperplane: subspace of dimension n-1 n j=1 ajxj = b (closed) halfspace: n j=1 ajxj b convex polyhedron: intersection of halfspaces convex polytope: bounded convex polyhedron
The Simplex Algorithm (Dentzig,1947) y is a neighbor ofx if 3 an edge between x and y find a vertex x; repeat: pick a neighbor y with cTy cTx; x←-y; until no such y
find a vertex x; repeat: pick a neighbor y with cTy < cTx; x ← y; until no such y. The Simplex Algorithm y is a neighbor of x if ∃ an edge between x and y (Dentzig, 1947)