运筹学基础 1.ppt

1、主讲教师：联系电话：短 号：E-mail:清华大学出版社运筹学教程（第三版）运筹学基础运筹学基础胡运权 主编教材运筹帷幄之中决胜千里之外运 筹 学 课 件第二章Linear progranming对偶理论与灵敏度分析例一 美佳公司计划制造 、 两种家电产品。已知各制造一件时分别占用的设备 A、 B的台时、调试时间及 A、 B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该公司应制造 、 两种家电备多少件 ,使获取的利润为最大。设： x1 A 产品的生产量 x2 B 产品的生产量利润 max z= 2 x1 + x2 约束条件5x2 156x1 + 2x2 24x

2、1 + x2 5x1， x2 0st .第一节 线性规划的对偶问题一、对偶问题的提出5x2 + x3 = 156x1 + 2x2 + x4 = 24x1 + x2 + x5 = 5x1， x2 ， x3 ， x4 ， x5 0约束条件 st .利润 max z= 2 x1 + x2 + 0x3 + 0x4 + 0x5 1）标准化）写出初始单纯形表（ 假设存在有单位矩阵 ）C 2 1 0 0 0 CB XB b x1 x2 x3 x4 x50 0 0x3 x4 x5152450 5 1 0 06 2 0 1 0 1 1 0 0 1 2 1 0 0 0）最优解检验（ 唯一解、无限多解、无界解和无解

3、 ）X*=(7/2,3/2,15/2,0,0) Z*= 17/2C 2 1 0 0 0 CB XB b x1 x2 x3 x4 x50 2 1x3 x1 x215/27/23/20 0 1 5/4 -15/21 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 一个问题？市场上设备 A、 设备 B和 调试工序每小时值多少钱？在什么价位时，可以出租或 去租借适当数量的资源来扩大生产规模？6y2 + y3分析设： y1 设备 A值的价值 y2 设备 B值的价值y3 调试工序值的价值 25y1 + 2y2 + y3 1z= 15 y1 + 24y2 + 5y3总

4、价值 miny1 , y2 , y3 0st .6y2 + y3 25y1 + 2y2 + y3 1z= 15 y1 + 24y2 + 5y3miny1 , y2 , y3 0st .z= -15 y1 - 24y2 - 5y3maxst .6y2 + y3 y4= 25y1 + 2y2 + y3 y 5 1=y1, y2, y3, y4, y5 = 0C -15 -24 -5 0 0 -M -M CB YB b y1 y2 y3 y4 y5 y6 y7 -M-My6y7210 6 1 -1 0 1 05 2 1 0 -1 0 1 5M-15 8M-24 2M-5 -M -M 0 0问题求解6

5、y2 + y3 25y1 + 2y2 + y3 1z= 15 y1 + 24y2 + 5y3miny1 , y2 , y3 0st .z= -15 y1 - 24y2 - 5y3maxst .6y2 + y3 y4= 25y1 + 2y2 + y3 y 5 1=y1, y2, y3, y4, y5 = 0C -15 -24 -5 0 0 CB YB b y1 y2 y3 y4 y5-24-5y2y31/41/2-5/4 1 0 -1/4 1/415/2 0 1 1/2 -3/2 -15/2 0 0 -7/2 -3/2 Y=(0, , , 0, 0) z=-17/2 z = 17/2问题求解Y*

6、=(0, , , 0, 0 )问题分析问题的解6y2 + y3 25y1 + 2y2 + y3 1z= 15y1 + 24y2 + 5y3miny1 , y2 , y3 0st .问题：？原问题：利润 max z= 2 x1 + x2 约束条件5x2 15 y16x1 + 2x2 24 y2x1 + x2 5 y3x1， x2 0st .问题的解 X*=(7/2,3/2,15/2,0,0)Z*= 17/2Z*= 17/25*3/2 = 15/2 156*7/2+2*3/2 = 24 24=7/2+3/2 = 5 5=结论两个问题的最优解的值一致两个问题的最优解的值一致最大值问题的最优解是最小值

7、问题的可行最大值问题的最优解是最小值问题的可行解解一个问题的剩余变量（松弛变量）一个问题的剩余变量（松弛变量） 不为不为 0（即有资源剩余），则对应问题的解为（即有资源剩余），则对应问题的解为 0一个决策变量不为一个决策变量不为 0，则对应的问题的约束，则对应的问题的约束条件的剩余变量条件的剩余变量 (松弛变量松弛变量 ) 为为 0(即无资源即无资源剩余剩余 )估价 影子价格（即增加单位资源所得到的贡献）Z= =CX=Yb Z/ b=(Yb) =Y二、对称形式下对偶问题的一般形式对称形式的定义 对称形式 X 0st.AX bmax z = CX其中：C=（ c1， c2, ,cn)b=（ b1

8、， b2, ,bm)T X=（ x1， x2, ,xn)TY=（ y1， y2, ,ym)TA=a11 a12 a 1na21 a22 a 2n am1 am2 anmY 0st. ATY CTmin w = YTb利润 max z= 2 x1 + x2 约束条件5x2 156x1 + 2x2 24x1 + x2 5x1， x2 0st .6y2 + y3 25y1 + 2y2 + y3 1z= 15y1 + 24y2 + 5y3miny1 , y2 , y3 0st .三、非对称形式的原对偶问题关系非 对称形式？x1 0, x 2 0, x3无约束 st.a11x1+a12x2+a13x3

9、b1a21x1+a22x2+a23x3 = b2a31x1+a32x2+a33x3 b 3max z = c1x1 + c2x2 +c3x3 x1 , x2, x3， x3“ 0st.a11x1 - a12x2 + a13x3- a13x3“ b1a21x1 - a22x2 + a23x3- a23x3“ b2-a21x1 + a22x2 _ a23x3+ a23x3“ -b2-a31x1 + a32x2 - a33x3+ a33x3“ -b3max z = c1x1 - c2x2 + c3x3 - c3x3“ y1 , y2, y2“ ， y30st.a11y1 + a21y2 a 21y2“ - a31y3 c 1-a12y1 - a22y2+ a22y2“ - a32y3-c 2a13y1 + a23y2 a 23y2“- a33y3 c 3-a13y1 - a23y2+ a23y2“+ a33y3-c 3min w = b1y1 + b2y2- b2y2“ - b3y3min w = b1y1 + b2y2 + b3y3a11y1 + a21y2 + a31y3 c 1a12y1 + a22y2 + a32y3 c2a13y1 + a23y2 + a33y3 = c3st.y10, y 2无约束 ， y3 0