Linear Programming: Chapter 5 Duality

Linear programming : Chapter 5 DualityRobert J. VanderbeiOctober 17, 2007 Operations 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:minimizeb1y1+b2y2subject toa11y1+a21y2 c1a12y1+a22y2 c2a13y1+a23y2 c3y1, y2 Problem:maximizen j=1cjxjsubject ton j=1aijxj bii= 1,2.

Resource Allocation Recall the resource allocation problem (m = 2, n = 3): maximize c 1x 1 + c 2x 2 + c 3x 3 subject to a 11x 1 + a 12x 2 + a 13x 3 b 1 a 21x 1 + a 22x 2 + a 23x 3 b 2 x 1; x 2; x 3 0; where c j = pro t per unit of product j produced b i = units of raw material i on hand a ij = units raw material i required to produce 1 unit of prod j:

Tags:

  Programming, Linear programming, Linear, Duality

Information

Related search queries