《运筹学-第二章线性规划的对偶理论与灵敏度分析_胡运权》由会员分享，可在线阅读，更多相关《运筹学-第二章线性规划的对偶理论与灵敏度分析_胡运权（13页珍藏版）》请在金锄头文库上搜索。
1、运筹学-第二章线性规划的对偶理论与灵敏度分析_胡运权 其次章 线性规划的对偶理论与灵敏度分析 例一美佳公司方案制造、两种家电产品。已知各制造一件时分别占用的设 备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的力量、 各售出一件时的获利状况如下表所示。问该公司应制造、两种家电备多少 件.使猎取的利润为最大。 设： x1 A产品的生产量 max z= 2 x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1,x2 0 x2 B产品的生产量 利润 约束 条件 st . 一、标准化 利润 max z= 2 x1 + x2 + 0x3 + 0x4 + 0x
2、5 5x2 + x3 = 15 约束 6x1 + 2x2 + x4 = 24 st . 条件 x1 + x 2 + x5 = 5 x1,x2 ,x3 ,x4 ,x5 0 二、写出初始单纯形表(必定存在有单位矩阵)C CCB 0 0 0 2 0 1 XB b b 22 11 00xx4 3 11 00 00 00 00xx5 4 0 5/4 1 1/4 0 -1/4 00x5 0 -15/2 0-1/2 1 3/2 xx1 x2x2 x3 1 00 61 10 20 50 20 11 10 15 xx3 15/2 3 24 xx4 7/2 1 5 xx5 3/2 2 0 -1/4 0 -1/2
3、三、最优解检验(唯一解、无限多解、无界解和无解)X =(7/2,3/2,15/2,0,0)* Z = 17/2 * 四、分析 把解X=(7/2,3/2)代入原问题(由于x3、 x4、 x5为附加变量) 532=15/2 5x2 15 A有空闲 = 24 B设备已经饱和 6x1 + 24 2 2x x1 + 5 2 x 5 调试工序也已经满负荷 = x1,x2 0 约束 条件 一个问题？市场上设备A、设备B和调试工序每小时值多少钱？ 在什么价位时，才能使美佳公司情愿出让自己的资源？ 例一 设： y1 设备A值的价值 y2 设备B值的价值 y3 调试工序值的价值min z= 15 y1 + 24y
4、2 + 5y3 分 总价值 6y2 + y3 析 2 st . 5y1 + 2y2 + y3 y1 , y 2 , y3 1 0 问题求解min z= 15 y1 + 24y2 + 5y3 6y2 + y3 2 max z= -15 y1 - 24y2 - 5y3 6y2 + y3 y4 = 2 st . 5y1 + 2y2 + y3 y1 , y 2 , y3C CB -M YB y6 b 2 -15 y1 0 1 -24 y2 6 st . 5y1 + 2y2 + y3 y5 = 1 0-5 y3 1 0 y4 -1 0 y5 0 -M y6 1 y1, y 2, y3, y 4, y5
5、0 -M y7 0 -M y7 1 5 2 1 0-M -1-M 00 10 M-15 8M-24 2M-5 问题求解min z= 15 y1 + 24y2 + 5y3 6y2 + y3 2 max z= -15 y1 - 24y2 - 5y3 6y2 + y3 y4 = 2 st . 5y1 + 2y2 + y3 y1 , y 2 , y3C CB -24 YB y2 b 1/4 -15 y1 -5/4 1 -24 y2 1 st . 5y1 + 2y2 + y3 y5 = 1 0-5 y3 0 0 y4 -1/4 y1, y 2, y3, y 4, y5 0 0 y5 1/4 -5 y3
6、1/2 15/2-15/2 00 10 1/2-7/2 -3/2-3/2 Y=(0, , , 0, 0) z=-17/2 z = 17/2 问题分析问题：T T min z=Z= =C 24y2 + 5y3 15y1 + X=Y b 原问题： Z/ b=(YTb) max Tz= 2 x1 + x2 =Y 利润5x2 15 6x1 + 2x2 24 约束 条件 st . x1 + x2 5 x1,x2 0问题 的解X =(7/2,3/2,15/2,0,0) Z = 17/2* * 6y 估价影子价格 2 + y3 2 (即增加单位资源所 + y st . 5y1 + 2y2 1 3 得到的贡献
7、) y1 , y 2 , y3 0 问题 Y=(0, , , 0, 0 ) 的解Z = 17/2 两个问题的最优解的值全都 最大值 问题可行解的目标值必定不大于最* 结 论 小值问题可行解的目标值 一个问题的剩余变量(松弛变量) 不为0 (即有资源剩余),则对应问题的解为0 一个决策变量不为0,则对应的问题的约束 条件的剩余变量(松弛变量) 为0(即资源彻 底用完) 5*3/2 = 15/2 15 6*7/2+2*3/2 = 24 = 24 7/2+3/2 = 5 = 5 对偶规章 变量、约束与系数 原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件 原问题的价值
8、系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵 解的关系max z= 2 x1 + x2 5x2 15 问题变量 6x1 + 2x2 24 约束 条件 st . x1 + x2 5 x1,x2 0C CB 0 2 1 XB x3 x1 x2 -* 利润 min z= 15y1 + 24y2 + 5y3 问题剩余松弛变量 6y2 + y3 2 st . 5y1 + 2y2 + y3 1 y1 , y 2 , y30 C CB -24 YB y2 b 1/4 -15 y1 -5/4 15/2 -15/2 3/2 3/2 -24 y2 1
9、 1/4 0 3/2 0 0 -7/2 7/2 1 1/2 -5 y3 0 0 y4 -1/4 00 y5 2 b 15/2 7/2 3/2 x1 0 1 0 0 0 1 x2 0 0 1 0 0 0 x3 1 0 0 0 0 0 x4 5/4 1/4 -1/4 -1/4 1/4 x5 -15/2 -1/2 3/2 -1/2 1/2 -5 y3 1/2 X =(7/2,3/2, 15/2,0,0) Y=(0, , 15/20, 0 0 , 0 ) - 一、线性规划的对偶问题1、对偶问题定义对 称 形 式max z = CTXst. AX b X 0 其中： C=(c1,c2, b=(b1,b2
10、, X=(x1,x2, Y=(y1,y2, min w = YTb T AY C st. Y 0a11 a12 a1n a2n ,cn)T ,bm)T ,xn)T ,ym)T A= a21 a22 am1 am2 amn 利润 max z= 2 x1 + x2 5x2 15 约束 6x1 + 2x2 24 st . 条件 x1 + x2 5 x1,x2 0 min z= 15y1 + 24y2 + 5y3 6y2 + y3 st . 2 5y1 + 2y2 + y3y1 , y 2 , y3 1 0 一、线性规划的对偶问题非对称形式？max z = c1x1 + c2x2 +c3x3 a11x
11、1+a12x2+a13x3 b1 st. a21x1+a22x2+a23x3 = b2 a31x1+a32x2+a33x3 b3 st. min w = b1y1 +a11y1 + a12y1 + a13y1 + y10, b 2y2 + b3y3 x1 0, x2 0, x3无约束 a21y2 + a31y3 c1 a22y2 + a32y3 c2 a23y2 + a33y3 = c3 y2无约束，y3 0 max z = c1x1 - c2x2 + c3x3 - c3x3 a11x1 - a12x2 + a13x3- a13x3 b1 a21x1 - a22x2 + a23x3- a23x
12、3 b2 st. -a x + a x _ a x + a x -b 21 1 22 2 23 3 23 3 2 -a31x1 + a32x2 - a33x3+ a33x3 -b3 x1 , x2, x3,x3 0 min w = b1y1 + b2y2- b2y2 - b3y3 a11y1 + a21y2 a21y2 - a31y3 c1 -a12y1 - a22y2+ a22y2 - a32y3-c2 st. a13y1 + a23y2 a23y2- a33y3 c3 -a13y1 - a23y2+ a23y2+ a33y3-c3 y1 , y2, y2 ,y30 对偶规章 变量与约束对应
13、关系原问题(对偶问题)max z=CTX AX ( = ) b X ( = ) 0 或无约束 有n个决策变量 xj (j=0、2n) xj 0 对偶问题(原问题)min w=YTb T A Y ( = ) C Y ( = ) 0 或无约束 有n个约束条件 对应的约束为 变量 xj 0 xj 无约束 约束 对应的约束为 对应的约束为 = 有m个约束条件 对应的约束为 约束 对应的约束为 对应的约束为 = 有m个决策变量 yj (j=0、 2m) yj 0 变量 yj 0 yj 无约束 max Z 4x 1 3x 2 5x 1 x 2 6 7x 5x 8 1 2 x 1 3x 2 10 x 1 0,x 2 0 min w 6y 1 8y 2 10y 3 5y 1 7y 2 y 3 4 y 1 2y 2 3y 3 3 y 0,i 1, , 23 i min Z 5x 1 2x 2 3x 3 4x 1 x 2 x 3 4 x 1 7x 2 5x 3 1 x ,x ,x 0 1 2 3 max Z 4y 1 3y 2 4y
