清华大学运筹学2对偶理论教学教材.pptx

第二章 线性规划对偶理论/66第一节 线性规划对偶理论第二节 对偶问题基本性质第三节 影子价格第四节 对偶单纯形法第五节 灵敏度分析第一节 线性规划对偶理论一、对偶问题的提出[例]设备台时/件产品可用台时（千小时）产品1产品2下料设备A104机加工设备B0212焊接设备C3218产品单价3元/件5元/件/66原来的问题：两种产品各生产多少，利润总额最大？生产是为赢利（取得收入）。还有别的办法赢利（取得收入） 。例如，卖出或出租设备。问，三种设备卖价或租价各应是多少，进项才不低于自己生产时的销售收入？/66用y1、y2和y3分别表示A、 B和 C三种设备单位台时卖价或租价，则，总进项w可表示成 w=4y1 +12y2+18y3 生产两种产品消耗的设备台时的价值（或称出售或出租两种产品所用设备台时的进项）分别是 1y1 +0y2+3y3和0y1 +2y2+2y3 两种产品售价分别是3和5。出售或出租产品所用设备台时的进项不能低于售价。所以，应有 1y1 +0y2+3y3 ≥3和0y1 +2y2+2y3 ≥5从另一个角度看，w=4y1 +12y2+18y3是总消耗。/66回答y1、y2和y3各是多少的问题，可表示如下： Min w=4y1 +12y2+18y3 s.t. y1 +3y3 ≥3 2y2 +2y3 ≥5 y1, y2, y3≥0该问题叫做原问题(P)的对偶问题(D)。可看出， Max z=CX Min w=bTY(P) s.t. AX≤b (D) s.t. ATY≥CT X≥0Y≥0/66若要问对偶问题的解是什么，可以看解(P)时得到的最终单纯形表。最终单纯形表cj35000θicBxBB-1bx1x2x3x4x50x320011/3-1/35x260101/203x12100-1/31/3z36000-3/2-1σj/66从该表松弛变量的检验数行得到：σ3 =0， σ4 = -3/2，σ5 = -1，y1 =0，y2 = 3/2，y3 = 1，将其代入(D): w=4×0 +12×3/2+18×1=36 (1) 0 +3×1 =3 (2) 2×3/2+2×1 =5(3) y1, y2, y3≥0 (4)这是对偶问题有趣的一个方面。/66二、对称的对偶问题一般形式上面的例子叫做对称的对偶问题。三、非对称的对偶问题请见教科书第三版第52页或第四版第53页的表。/66事项原问题（对偶问题）对偶问题（原问题）AbC目标函数 n个决策变量 xj≥0 xj≤0 xj无约束m个决策变量yi≥0yi≤0yi无约束/66第二节 对偶理论基本性质一、对称形式单纯形法矩阵表达 Max z=CX s.t. AX≤b X≥0化成标准形式 Max z=CX+0Xs s.t. AX+IXs=b X，Xs≥0 Xs =(xs1, xs2, …,xsm)T 是松弛变量/66 Min w=YTb(D)s.t. ATY≥CT Y≥0添加剩余变量后，变成 Min w=YTb+0Ys(D)s.t. ATY-IYs=CT Y, Ys≥0 Ys =(ys1, ys2, …,ys,n-m)T 是剩余变量 /66 [例] Max z=3x1+5x2 s.t. x1 ≤4 y1 (P) 2x2 ≤12y2 3x1+2x2 ≤18 y3 x1，x2 ≥0 Min w=4y1 +12y2+18y3 s.t. y1 +3y3 ≥3x1 (D) 2y2 +2y3 ≥5x2 y1, y2, y3≥0/66 Max z=3x1+5x2 +0x3+0x4 +0x5 s.t. x1 + x3 =4 (P) 2x2+ x4 =12 3x1+2x2 + x5 =18 x1，x2 ，x3 ，x4 ，x5 ≥0 Min w=4y1 +12y2+18y3 +0y4+0y5+My6+My7 s.t. y1 +3y3 -y4 +y6 = 3 (D) 2y2 + 2y3 -y5 +y7 =5 y1, y2, y3, y4, y5, y6, y7 ≥0 /107对偶问题初始单纯形表bj4121800MMθibByBB-1Cy1y2y3y4y5y6y7My63103-1010-My750[2]20-1015/2w8M4-M12-2M18-2MMM00σjσ3应当是18-5M，但错算为18-2M，所以误选y2为换入变量。以下将错就错算下去。My6310[