清华大学运筹学对偶理论.pptxVIP

1;原来的问题：两种产品各生产多少，利润总额最大？ 生产是为赢利（取得收入）。还有别的办法赢利（取得收入） 。例如，卖出或出租设备 。 问，三种设备卖价或租价各应是多少，进项才不低于自己生产时的销售收入？;用y1、y2和y3分别表示A、 B和 C三种设备单位台时卖价或租价，则，总进项w可表示成 w=4y1 +12y2+18y3 生产两种产品消耗的设备台时的价值（或称出售或出租两种产品所用设备台时的进项）分别是 1y1 +0y2+3y3 和 0y1 +2y2+2y3 两种产品售价分别是3和5。出售或出租产品所用设备台时的进项不能低于售价。所以，应有 1y1 +0y2+3y3 ≥3;回答y1、y2和y3各是多少的问题，可表示如下 ： Min w=4y1 +12y2+18y3 s.t. y1 +3y3 ≥3 2y2 +2y3 ≥5 y1, y2, y3≥0 该问题叫做原问题(P)的对偶问题(D)。可看出，;;从该表松弛变量的检验数行得到：;二、对称的对偶问题一般形式 上面的例子叫做对称的对偶问题。三、非对称的对偶问题 请见教科书第三版第52页或第四版第53页的表。;;第二节 对偶理论基本性质;令 X = XB ，(C, 0)=(CB, CN);松弛变量Xs =(xs1, xs2, …,xsm)T的检验数是;再将(1) z=CBB-1b 、(5)和(4)写在一起：;Min w=YTb;[例] Max z=3x1+5x2;Max z=3x1+5x2 +0x3+0x4 +0x5 . x1 + x3;;bj;;对偶问题最终单纯形表;;事项;■;推论1 (P)任一可行解目标函数值 是(D)目标函数值下界。反之， (D)任一可行解目标函数值是(P)目标函数值上界。;■;3. 对偶定理。若(P)和(D)均有可行解，则均有最优解，且两者的目标函数值;■;■;第三节 影子价格;有些经济学家认为，自由的市场交易，商品成交价格能够反映其真正价值。但是，资源的现实市场价格并不反映其“真正”价值。还有些经济学家认为，影子价格是原本无交易的资源，在转为其他用途时的价格，或者说，另外再增加一个单位此种资源需要付出的价格。这个问题可以利用对偶问题的解给予某种解释。 Min w=4y1 +12y2+18y3;这就是说，三种设备每台时的价格分别是0, 3/2和1。第一种设备每台时的价格为0，这是什么意思？ 请看原问题 Max z=3x1+5x2 +0x3+0x4 +0x5;第30页/共65页;12;12;12;12;第四节 对偶单纯形法;二、对偶单纯形法计算步骤;[例1] Min w=4x1+12x2 +18x3;cj;;;第五节 灵敏度分析;实际问题的数学模型，应当避免第一种情况，因为实际中很难避免将算成。 LP问题也会遇到类似情况。其中A、b和C都是从实际中收集、归纳和整理的数字，很难保证与实际情况丝毫不差。;灵敏度分析的步骤：;可用台时;47/66;为了回答问题2，用5+Δc2表示第二种产品改变后的单价，并填入最终;若回答使最优产量不变的第一种产品单价变化范围，则用3+Δc1表示第一;二、分析b的变化;cj;三、分析增添新变量xj的情况 如果增加新产品x6 ，单价为4元，问如何生产，总收入最多。设其所需三;;四、分析技术系数aij变化时的情况如果aij对应的xj是非基变量，处理办法同“三”。如果xj是基变量，先变 换Pj， Pj‘ =B-1Pj;2;检验数均已非正，说明已经得到最优解，销售收入增加了(42- 36)/36=16.7%。;如果第二种产品用设备台时由;1;需要将x2排除在外，办法是将其视为人工变量。;;可将X*=(x1, x2, x3, x4, x5 )T=(1, 6, 0, 0, 12)T代入修改P2后的原问题检查。;五、增加约束条件;先将P1, P2将变换成单位列向量。第4行-2×第2行-2×第3行;σ4= -3/2 -;65/66