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)