Linear Programming: Chapter 5 Duality

← Back to document page

Linear Programming: Chapter 5DualityRobert J. VanderbeiOctober 17, 2007Operations Research and Financial EngineeringPrinceton UniversityPrinceton, NJ 08544 rvdbResource AllocationRecall the resource allocation problem (m= 2,n= 3):maximizec1x1+c2x2+c3x3subject toa11x1+a12x2+a13x3 b1a21x1+a22x2+a23x3 b2x1, x2, x3 0,wherecj=profit per unit of productjproducedbi=units of raw materialion handaij=units raw materialirequired to produce1unit of Up ShopIf we produce one unit less of productj, then we free up: a1junits of raw material1and a2junits of raw these unused raw materials fory1andy2dollars/unityieldsa1jy1+ interested if this exceeds lost profit on each productj:a1jy1+a2jy2 cj,j= 1,2, a buyer offering to purchase our entire to above constraints, buyer wants to minimize cost.

Dual-Based Phase I Method Example: Notes: Two objective functions: the true objective (on top), and a fake one (below it). For Phase I, use the fake objective|it’s dual feasible. Two right-hand sides: the real one (on the left) and a fake (on the right). Ignore the fake right-hand side|we’ll use it in another algorithm later. Phase I|First ...

  Phases, Dual, Duality