Unformatted text preview:

AgendaWe’ve doneGreedy MethodDivide and ConquerDynamic ProgrammingNetwork Flows & ApplicationsNP-completenessNowLinear Programming and the Simplex MethodHung Q. Ngo (SUNY at Buffalo) CSE 531 1 / 59Linear Programming Motivation: The Diet ProblemSettingn foods (beef, apple, potato chips, pho, b´un b`o, etc.)m nutritional elements (vitamins, calories, etc.)each gram of jth food contains aijunits of nutritional element ia good meal needs biunits of nutritional element ieach gram of jth food costs cjObjectivedesign the most economical meal yet dietarily sufficient(Halliburton must solve this problem!)Hung Q. Ngo (SUNY at Buffalo) CSE 531 3 / 59The Diet Problem as a Linear ProgramLet xjbe the weight of food j in a dietarily sufficient meal.min c1x1+ c2x2+ · · · + cnxnsubject to a11x1+ a12x2+ . . . + a1nxn≥ b1a21x1+ a22x2+ . . . + a2nxn≥ b2...... . . ..........am1x1+ am2x2+ . . . + amnxn≥ bmxj≥ 0, ∀j = 1, . . . , n,Hung Q. Ngo (SUNY at Buffalo) CSE 531 4 / 59Linear Programming Motivation: The Max-Flow ProblemMaximize the value of f:val(f) =Xe=(s,v)∈EfeSubject to0 ≤ fe≤ ce, ∀e ∈ EXe=(u,v)∈Efe−Xe=(v,w)∈Efe= 0, ∀v 6= s, tHung Q. Ngo (SUNY at Buffalo) CSE 531 5 / 59Formalizing the Linear Programming ProblemLinear objective functionmax or min −83x1+ 2x2+ x3− 6x4+ x5Linear constraints, can take many formsInequality constraints3x1+ 4x5− 2x6≥ 32x1+ 2x2+ x3≤ 0Equality constraints−x2− x4+ x3= −3Non-negativity constraints (special case of inequality)x1, x5, x7≥ 0Hung Q. Ngo (SUNY at Buffalo) CSE 531 7 / 59Some notational conventionsAll vectors are column vectorsc =c1c2...cn, x =x1x2...xn, A =a11a12. . . a1na21a22. . . a2n... . . . . . ....am1am2. . . amn, b =b1b2...bm.Hung Q. Ngo (SUNY at Buffalo) CSE 531 8 / 59Linear Program: Standard Formmin / max c1x1+ c2x2+ · · · + cnxnsubject to a11x1+ a12x2+ . . . + a1nxn= b1a21x1+ a22x2+ . . . + a2nxn= b2...... . . .... =...am1x1+ am2x2+ . . . + amnxn= bmxj≥ 0, ∀j = 1, . . . , n,or, in matrix notations,min / maxcTx | Ax = b, x ≥ 0Hung Q. Ngo (SUNY at Buffalo) CSE 531 9 / 59Linear Program: Canonical Form – min Versionmin c1x1+ c2x2+ · · · + cnxnsubject to a11x1+ a12x2+ . . . + a1nxn≥ b1a21x1+ a22x2+ . . . + a2nxn≥ b2...... . . .... ≥...am1x1+ am2x2+ . . . + amnxn≥ bmxj≥ 0, ∀j = 1, . . . , n,or, in matrix notations,mincTx | Ax ≥ b, x ≥ 0Hung Q. Ngo (SUNY at Buffalo) CSE 531 10 / 59Linear Program: Canonical Form – max Versionmax c1x1+ c2x2+ · · · + cnxnsubject to a11x1+ a12x2+ . . . + a1nxn≤ b1a21x1+ a22x2+ . . . + a2nxn≤ b2...... . . .... ≤...am1x1+ am2x2+ . . . + amnxn≤ bmxj≥ 0, ∀j = 1, . . . , n,or, in matrix notations,maxcTx | Ax ≤ b, x ≥ 0Hung Q. Ngo (SUNY at Buffalo) CSE 531 11 / 59Conversions Between Forms of Linear Programsmax cTx = min(−c)TxPjaijxj= biis equivalent toPjaijxj≤ biandPjaijxj≥ bi.Pjaijxj≤ biis equivalent to −Pjaijxj≥ −biPjaijxj≤ biis equivalent toPjaijxj+ si= bi, si≥ 0. Thevariable siis called a slack variable.When xj≤ 0, replace all occurrences of xjby −x0j, and replacexj≤ 0 by x0j≥ 0.When xjis not restricted in sign, replace it by (uj− vj), anduj, vj≥ 0.Hung Q. Ngo (SUNY at Buffalo) CSE 531 12 / 59Example of Converting Linear ProgramsWritemin x1− x2+ 4x3subject to 3x1− x2= 3− x2+ 2x4≥ 4x1+ x3≤ −3x1, x2≥ 0in standard (min / max) form and canonical (min / max) form.Hung Q. Ngo (SUNY at Buffalo) CSE 531 13 / 59LP Geometry: Example 1max 2x + ysubject to −2x + y ≤ 25x + 3y ≤ 15x + y ≤ 4x ≥ 0, y ≥ 0Hung Q. Ngo (SUNY at Buffalo) CSE 531 15 / 59Example 1 – Feasible RegionHung Q. Ngo (SUNY at Buffalo) CSE 531 16 / 59Example 1 – Objective FunctionHung Q. Ngo (SUNY at Buffalo) CSE 531 17 / 59LP Geometry: Example 2max 2x + ysubject to 2x + 3y ≥ 88x + 3y ≥ 124x + 3y ≥ 24Hung Q. Ngo (SUNY at Buffalo) CSE 531 18 / 59Example 2 – Feasible RegionHung Q. Ngo (SUNY at Buffalo) CSE 531 19 / 59Example 2 – Objective FunctionHung Q. Ngo (SUNY at Buffalo) CSE 531 20 / 59Half Space and HyperplaneEach inequality aTx ≥ b defines a half-space.aaTx ≥ baTx ≤ bEach equality aTx = b defines a hyperplane.Hung Q. Ngo (SUNY at Buffalo) CSE 531 21 / 59Polyhedron, Vertices, Direction of OptimizationA polyhedron is the set of points x satisfying Ax ≤ b (or equivalentlyA0x ≥ b0)cTx = d2vertexcTx = d1moving alongthis directioncTx is improvedd2< d1cHung Q. Ngo (SUNY at Buffalo) CSE 531 22 / 59Linear Programming Duality: A Motivating Examplemax 3x1+ 2x2+ 4x3subject to x1+ x2+ 2x3≤ 42x1+ 3x3≤ 54x1+ x2+ 3x3≤ 7x1, x2, x3≥ 0.Someone claims xT=1 3 0 is optimal with cost 9.Feasibility is easy. How could we verify optimality?We ask the person for a proof!Hung Q. Ngo (SUNY at Buffalo) CSE 531 24 / 59Her Proof of the Optimali ty of x53· ( x1+ x2+ 2x3) ≤53· 40 · ( 2x1+ 3x3) ≤ 0 · 513· ( 4x1+ x2+ 3x3) ≤13· 7. . .Ma ia hii Ma ia huuMa ia hoo Ma ia haha. . .⇒ 3x1+ 2x2+ 4x3≤ 9Done!Hung Q. Ngo (SUNY at Buffalo) CSE 531 25 / 59OK, How Did . . . I do that?Beside listening to Numa Numa, find non-negative multipliersy1· ( x1+ x2+ 2x3) ≤ 4y1y2· ( 2x1+ 3x3) ≤ 5y2y3· ( 4x1+ x2+ 3x3) ≤ 7y3⇒ (y1+2y2+4y3)x1+(y1+y3)x2+(2y1+3y2+3y3)x3≤ (4y1+5y2+7y3)Want LHS to be like 3x1+ 2x2+ 4x3. Thus, as long asy1+ 2y2+ 4y3≥ 3y1+ y3≥ 22y1+ 3y2+ 3y3≥ 4y1, y2, y3≥ 0.we have3x1+ 2x2+ 4x3≤ 4y1+ 5y2+ 7y3Hung Q. Ngo (SUNY at Buffalo) CSE 531 26 / 59How to Get the Best MultipliersAnswer: minimize the upper bound.min 4y1+ 5y2+ 7y3y1+ 2y2+ 4y3≥ 3y1+ y3≥ 22y1+ 3y2+ 3y3≥ 4y1, y2, y3≥ 0.Hung Q. Ngo (SUNY at Buffalo) CSE 531 27 / 59What We Have Just ShownIf x is feasible for the Primal Programmax 3x1+ 2x2+ 4x3subject to x1+ x2+ 2x3≤ 42x1+ 3x3≤ 54x1+ x2+ 3x3≤ 7x1, x2, x3≥ 0.and y is feasible for the Dual Programmin 4y1+ 5y2+ 7y3y1+ 2y2+ 4y3≥ 3y1+ y3≥ 22y1+ 3y2+ 3y3≥ 4y1, y2, y3≥ 0.then3x1+ 2x2+ 4x3≤ 4y1+ 5y2+ 7y3Hung Q. Ngo (SUNY at Buffalo) CSE 531 28 / 59Primal-Dual Pairs - Canonical Formmin cTx (primal/dual program)subject to Ax ≥ bx ≥ 0max bTy (dual/primal program)subject to ATy ≤ cy ≥ 0.NoteThe dual of the dual is the primal!Hung Q. Ngo (SUNY at Buffalo) CSE 531 29 / 59Primal-Dual Pairs - Standard Formmin / max cTx (primal program)subject to Ax = bx ≥ 0max / min bTy (dual program)subject to ATy ≤ c no non-negativity


View Full Document

UB CSE 531 - Linear Programming Motivation- The Diet Problem

Download Linear Programming Motivation- The Diet Problem
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Linear Programming Motivation- The Diet Problem and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Linear Programming Motivation- The Diet Problem 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?