运筹学课件 (2)

1、OR11第一章 绪论w 1.1题解 Operations 汉语翻译工作、操作、行动、手术、运算Operations Research日本运用学 港台作业研究中国大陆运筹学Operational Research原来名称，意为军事行动研究历史渊源OR12绪论w 1.2 运筹学的历史 早期运筹思想：田忌赛马 丁渭修宫 沈括运粮 Erlang 1917 排队论 Harris 1920 存储论 Levinson 1930 零售贸易 康脱洛维奇 1939 LP OR13OR14OR15OR16OR17OR18OR19OR110绪论w 1.2运筹学的历史 军事运筹学阶段 德军空袭 防空系统 Blacket

2、t 运输船编队 空袭逃避 深水炸弹 轰炸机编队OR111绪论w 1.2运筹学的历史 管理运筹学阶段 战后人员三分:军队、大学、企业 大学：课程、专业、硕士、博士 企业：美国钢铁联合公司 英国国家煤炭局 运筹学在中国：50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题 OR1121.3学科性质应用学科Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。中国定义：运筹学是应用分析、试验、量化的方法

3、，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。OR1131.4定性与定量w 例：店主进货w 两者都是常用的决策方法w 定性是基础，定量是工具，定量为定性服务。w 定性有主观性也有有效性，定量有科学性也有局限性。管理科学的发展，定量越来越多。但定量不可替代定性。OR1141.5运筹学的模型w 模型：真实事物的模仿，主要因素、相互关系、系统结构。w 形象模型：如地球仪、沙盘、风洞w 模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。w 数学模型：用符号或数学工具描述现实系统。V=F（xi,yj,uk) G(xi,yj,uk)0OR1

4、151.6运筹学的学科体系w 规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划w 图论与网络w 存储论w 排队论w 决策论w 对策论w 计算机仿真OR1161.7运筹学的工作步骤w 确定问题w 搜集数据建立模型w 检验模型w 求解模型w 结果分析w 结果实施OR1171.8运筹学与计算机w 计算机为运筹学提供解题工具。w 本书有现成的程序可以利用w 要学会解题的思路与方法，建立模型很重要。OR118第二章 线性规划与单纯形法w 2.1 LP(linear programming)的基本概念 LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。LP有一组有

5、待决策的变量， 一个线性的目标函数， 一组线性的约束条件。 OR1192.1.1 LP的数学模型 例题1生产计划问题w 某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120OR120例题1建模w 问题：如何安排生产计划，使得获利最多？w 步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非

6、负性约束X10 X20OR121例题2配方问题w 养海狸鼠 饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求70030200OR122例题2建模w 设抓取饲料I x1kg;饲料II x2kg;饲料III x3kgw 目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5w 约束条件：3x2+2x2+x3+6x4+18x5 700营养要求： x1+0.5x2+0.2x3+2x4+0.5x5 30

7、 0.5x1+x2+0.2x3+2x4+0.8x5 =200用量要求： x1 50,x2 60,x3 50,x4 70,x5 40非负性要求：x1 0,x2 0,x3 0,x4 0,x5 0 OR123例题3：人员安排问题w 医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计： 序号时段最少人数安排人数1061060X12101470X23141860X34182250X45220220X56020630 x6OR124例题3建模w 目标函数：min Z=x1+x2+x3+x4+x5+x6w 约束条件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 2

8、0 x5+x6 30 x6+x1 60非负性约束：xj 0,j=1,2,6OR125归纳：线性规划的一般模式w 目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxnw 约束条件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bn非负性约束：x1 0,x2 0,xn 0OR1262.1.2线性规划图解法w 由中学知识可知：y=ax+b是一条直线，同理：Z=70 x1+120 x2x2=70/120 x1-Z/120也是一条直线，以Z为参数的一族等值

9、线。 9x1+4x2 360 x1 360/9-4/9x2 是直线 x1=360/9-4/9x2 下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。OR127例1图示. 90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300ABCDEFGHIZ=70 x1+120 x2OR128概念w 概念：1、可行解：满足所有约束条件的解。2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。3、基解：

10、约束条件的交点称为基解（直观）4、基可行解：基解当中的可行解。5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形OR129结论w 可行域是个凸集w 可行域有有限个顶点w 最优值在可行域的顶点上达到w 无穷多解的情形w 无界解情形w 无解情形OR1302.1.3线性规划的标准型w 代数式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,nOR131线性规划的标准型w 和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=

11、1,2,nj=1nnj=1OR132线性规划的标准型w向量式：maxZ=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn) X=(X1,X2,X3,Xn) Tnj=1OR133线性规划的标准型w 矩阵式： maxZ=CX AX=b X 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amnOR134标准型的特征w 目标函数极大化w 约束条件为等式w 决策变量非负OR135非标准型转化为标准型w 目标函数极小化转为极大化： minZ=max(Z) ，一个数的极小化等价于其相反数的极大化。w

12、 不等式约束的转化： aijxjbi 加入松弛变量 aijxjbi 减去剩余变量w 非正变量：即xk 0 则令xk = xk 自由变量：即xk无约束，令xk= xkx”kOR136非标准型转化举例之一之一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10X2 300 3X1+10X2+x5 =300 X10 X20 Xj0 j=1,2,5OR137非标准型转化举例之二之二minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9

13、 x1+x2+x3 x”3 + x4=9 -x1-2x2+x3 2 x12x2+x3 x”3 - x5= 2 3x1+x2-3x3=5 3x1+x23(x3 x”3 )=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 x40 x50 OR1382.1.4基可行解w基的概念基的概念：如前所述LP标准型和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩阵式：maxZ=CX AX=b X 0 约束方程的系数矩阵A的秩为m，且m0 =bL/ aLk 。 这时原基变量XL=0，由基变量变成非基变量，aLk处在变量转换的交叉点上，称之为枢轴元素j 0O

14、R153单纯形法解题举例单纯形表的格式： CjC1 C2 Cn i CBXBbx1 x2 . xn C1 C2 Cmx1x2xmb 1b2bma11 a12 a1na21 a22 a2n am1 am2 amn 1 2 m j 1 2 n OR154 Cj70 120 0 0 0CBXBbX1 X2 X3 X4 X5j 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.1

15、30.7620100j3600 34 0 0 0 -12070120X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16j4280 0 0 0 -13.6 -5.2OR155单纯型法的基本思路单纯型法的基本思路确确定定初初试试基基础础可可行行解解求求最最优优解解的的目目标标函函数数值值确确定定改改善善方方向向求求新新的的基基础础可可行行解解检检查查是是否否为为最最优优解解？是是否否OR156例二、试列出下面线性规划问题的初始单纯型表例二、试列出下面线性规划问题的初始单纯型表0,12023310032.244540)(max3

16、21321321321xxxxxxxxxtsxxxxfx1x2x3x4x5CBXBb404524000 x4100231100 x512033201 OBJ = 0 zj00000 cj- -zj40452400OR157关于检验数的数学解释关于检验数的数学解释w 设设 B 是初始可行基，则是初始可行基，则目标函数可写为两部分目标函数可写为两部分(1)w 约束条件也写为两部分，约束条件也写为两部分，经整理得经整理得 XB 的表达式的表达式(2)，注意注意 XB中含有非基变量中含有非基变量作参数作参数w 把把 XB 代入目标函数，整代入目标函数，整理得到理得到(3)式式w 第第 j 个非基变量的

17、机会成个非基变量的机会成本如本如(4)式式w 若有若有cj zj0, 则未达到最则未达到最优优(5) (4) ) 3 ( )()()(2) )(1) )(1jjmiijijzcaczxfxf检验数机会成本NN1BN1BNN1BNNNN1BNNBBNNBBNNXABCCbBCXAbBCXCXAbBXXAbBXbBXXAXCXCOR158标准型的单纯型算法标准型的单纯型算法1 找初试基础可行基找初试基础可行基n对于对于(max, )，松弛变量对应的列构成一个单位阵，松弛变量对应的列构成一个单位阵n若有若有 bi 0 中找最大者，选中者称为中找最大者，选中者称为入变量入变量， xj* n第第j*列称

18、为列称为主列主列4 确定确定入变量入变量的最大值和的最大值和出变量出变量n最小比例原则最小比例原则 0min*ijijiiaabOR159标准型的单纯型算法标准型的单纯型算法4 确定确定入变量入变量的最大值和的最大值和出变量出变量n设第设第 i* 行使行使 最小，则第最小，则第 i* 行对应的基变量称为行对应的基变量称为出出变量变量，第，第 i* 行称为行称为主行主行5 迭代过程迭代过程n主行主行 i* 行与行与主列主列 j* 相交的元素相交的元素ai*j* 称为称为主元主元，迭代，迭代以以主元主元为中心进行为中心进行n迭代的实质是线性变换，即要将迭代的实质是线性变换，即要将主元主元 ai*j

19、*变为变为1，主主列列上其它元素变为上其它元素变为0，变换步骤如下：，变换步骤如下：(1)变换主行变换主行nmjaaajijiji, 2 , 1*OR160标准型的单纯型算法5 迭代过程(2)变换主列变换主列除除主元主元保留为保留为1，其余都置，其余都置0(3)变换非主行、主列元素变换非主行、主列元素 aij (包括包括 bi)四角算法公式：四角算法公式：数据表示当前单纯型表中的的数据表示上一个单纯型表中 , , *ijiijijiijjiijijjiijiiiababaaaaaaabbbOR161标准型的单纯型算法标准型的单纯型算法5 、迭代过程(4)变换变换CB，XB(5)计算目标函数、机

20、会成本计算目标函数、机会成本 zj 和检验数和检验数 cj zj 6、返回步骤 2aijai*jaij*ai*j*主主行行主主列列主主元元四四角角算算法法图图示示OR162例二、例二、 单纯型表的迭代过程单纯型表的迭代过程x1x2x3x4x5序序号号CBXBb4 04 52 400bi/aij*0 x41 0 02(3 )110(3 3 .3 )0 x51 2 0332014 0 O B J = 000000I初初始始解解cj- - zj4 04 52 40045x2100/32/311/31/30500 x520(1)01 11(20) OBJ = 1500304515150IIcj- -z

21、j1009 1504 5x22 001 1 /31 2 /34 0 x12 0101 11 O B J = 1 7 0 04 04 52 551 0III最最优优解解cj- - zj00 1 5 1 0OR163单纯型表中元素的几点说明单纯型表中元素的几点说明n任何时候，基变量对应的列都构成一个单位矩阵任何时候，基变量对应的列都构成一个单位矩阵n当前表中的当前表中的 b 列表示当前基变量的解值，通过变换列表示当前基变量的解值，通过变换 B 1 b 得得到到 (资源已变成产品资源已变成产品)n当前非基变量对应的向量可通过变换当前非基变量对应的向量可通过变换 B 1 AN 得到，得到， 表示第表示

22、第 j 个变量对第个变量对第 i 行对应的基变量的消耗率行对应的基变量的消耗率n非基变量的机会成本由非基变量的机会成本由 给出给出n注意基变量所对应的行注意基变量所对应的行x1x2x3x4x5序序号号CBXBb40452400bi/aij*45x2100/32/311/31/30500 x520(1)01 11(20) OBJ = 1500304515150IIcj- -zj1009 150miijijacz1 OR164w 单纯型法举例之三：4321532infxxxxM0,412432642:.432143143214321xxxxxxxxxxxxxxxts4321532xxxxMaxZ0

23、,41232642:.765432174316432154321xxxxxxxxxxxxxxxxxxxxxtsOR165w单纯型表如下：w CB XB b 2 1 -3 5 0 0 0w X1 X2 X3 X4 X5 X6 X7 w 0 X5 6 1 2 4 -1 1 0 0w 0 X6 12 2 3 -1 1 0 1 0 w 0 X7 4 1 0 1 1 0 0 1w -z 0 2 1 -3 5 0 0 0 w 0 X5 10 2 2 5 0 1 0 1w 0 X6 8 1 3 -2 0 0 1 -1w 5 X4 4 1 0 1 1 0 0 1w -z -20 -3 1 -8 0 0 0 -

24、5 w 0 X5 14/3 4/3 0 19/3 0 1 -2/3 5/3 w 1 X2 8/3 1/3 1 -2/3 0 0 1/3 -1/3 w 5 X4 4 1 0 1 1 0 0 1w -z -68/3 -10/3 0 -22/3 0 0 -1/3 -14/3OR166用单纯型法求解线性规划问题用单纯型法求解线性规划问题w 例一例一：w Max z=3 x1+2 x2 Max z=3 x1+2 x2 0,5332:.0,5332:.4321421321212121xxxxxxxxxxt sxxxxxxt sOR167w CB XB b 3 2 0 0w X1 X2 X3 X4w 0 X

25、3 3 2 -3 1 0 1.5w 0 X4 5 -1 1 0 1 -w Z = 0 3 2 0 0w 3 X1 1.5 1 -3/2 1/2 0 w 0 X4 6.5 0 -1/2 1/2 1w z = 4.5 0 13/2 -3/2 0OR168a21与a22都小于0，原问题没有最优解OR169用单纯型法求解线性规划问题用单纯型法求解线性规划问题w 例二：例二：32122xxxMaxz0,936212:.32121321321xxxxxxxxxxxt s0,936212:.65432162153214321xxxxxxxxxxxxxxxxxt s3212xxxMaxzOR170w CB X

26、B b 1 -2 1 0 0 0w X1 X2 X3 X4 X5 X6 w 0 X4 12 1 1 1 1 0 0 12w 0 X5 6 2 1 -1 0 1 0 3w 0 X6 9 -1 3 0 0 0 1 -w z=0 1 -2 1 0 0 0 w 0 X4 9 0 1/2 3/2 1 -1/2 0 6w 1 X1 3 1 1/2 -1/2 0 1/2 0 -w 0 X6 12 0 7/2 -1/2 0 1/2 1 - w z =3 0 -5/2 3/2 0 -1/2 0 w 1 X3 6 0 1/3 1 2/3 -1/3 0 w 1 X1 6 1 2/3 0 1/3 1/3 0 w 0

27、X6 15 0 11/3 0 1/3 1/3 1 w z =12 0 -3 0 -1 0 0 Tx1500606*OR171w X5为非基变量，其检验数为为非基变量，其检验数为0，可能存在无穷多最优解可能存在无穷多最优解做进一步迭代，令做进一步迭代，令X5为进基为进基,w 得另一最优解为：得另一最优解为：w 解得无穷多最优解在端点为解得无穷多最优解在端点为 的线段上，最优解为：的线段上，最优解为：Tx91801200* TT606,120012*zOR1722.3单纯形法的进一步讨论w 一般线性规划问题的处理一般线性规划问题的处理 对于一般线性规划标准形式问题：对于一般线性规划标准形式问题：

28、考虑一般问题：考虑一般问题： bi 0 ， i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0 主要是讨论初始基本可行解不明显时，常用的方法。主要是讨论初始基本可行解不明显时，常用的方法。OR173w 引入人工变量 xn+i 0 i = 1 , , m ; 得到，s.t. a11 x1 + a12 x2 + + a1n xn +

29、xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0 显然，显然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解，对应的基是单位矩阵。OR174w 大大M法：法： 引入人工变量 xn+i 0 i = 1 , , m ; 充分大正数 M 。 得到， Max z = c1 x1 + c2 x2 + + cn xn -M xn+1 - - M xn+m s.t. a11 x1 +

30、 a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0显然，显然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解，对应的基是单位矩阵。w 结论：若得到的最优解满足结论：若得到的最优解满足 xn+i = 0 i = 1 , , m 则是原问题的最优解；否则，原问题无可行解。OR175w 两阶段法：两阶段法：引入人工变量 xn+i 0，i

31、 = 1 , , m；构造， Max z = - xn+1 - xn+2 - - xn+m s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0w 第一阶段求解上述问题：第一阶段求解上述问题：显然，显然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解，对应的基是单位矩阵。w 结论：若得到的最优解满足结论：若

32、得到的最优解满足 xn+i = 0 i = 1 , , m 则是原问题的基本可行解；否则，原问题无可行解。w 得到原问题的基本可行解后，第二阶段求解原问题。得到原问题的基本可行解后，第二阶段求解原问题。OR176例：（LP） Max z = 5 x1 + 2 x2 + 3 x3 - x4 s.t. x1 + 2 x2 + 3 x3 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 0w 大M法问题（LP - M） Max z = 5 x1 + 2 x2 + 3 x3 - x4 - M x5 - M x

33、6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 0OR177OR178 得到最优解：(25/3，10/3，0，11)T 最优目标值：112/3OR179w 两阶段法两阶段法 ：第一阶段问题（：第一阶段问题（LP - 1） Max z = - x5 - x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x

34、4 = 26 x1 , x2 , x3 , x4 , x5 , x6 0OR180第一阶段第一阶段 （LP - 1）OR181 得到原问题的基本可行解：得到原问题的基本可行解： (0，15/7，25/7，52/7)T OR182第二阶段第二阶段 把基本可行解填入表中把基本可行解填入表中OR183w 得到原问题的最优解：得到原问题的最优解：(25/3，10/3，0，11)T w 最优目标值：最优目标值：112/3OR184例例2：（一）（一）大大M法的求解过程法的求解过程0,46 2.7810)(min32132121321xxxxxxxxtsxxxxf0,46 2.7810)(min32132

35、121321xxxxxxxxtsxxxxf0,46 2. .7810)(min32132121321xxxxxxxxtsxxxxfOR185划为标准型及加入人工变量后划为标准型及加入人工变量后0,4 6 2. .)7810max()(max654321532164216321xxxxxxxxxxxxxxt sMxxxxxfOR186OR187w 答：最优解为答：最优解为 x1=2, x2=2, x3=0。OR188（二）二阶段法的求解过程（二）二阶段法的求解过程w 第一阶段的任务是将人工变量尽快迭代出第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可去，从而找到一个没有人

36、工变量的基础可行解行解w 第二阶段以第一阶段得到的基础可行解为第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解初始解，采用原单纯型法求解w 若第一阶段结束时，人工变量仍在基变量若第一阶段结束时，人工变量仍在基变量中，则原问题无解中，则原问题无解OR189用二阶段法求解例用二阶段法求解例2的第一阶段的第一阶段OR190用二阶段法求解例用二阶段法求解例2的第二阶段的第二阶段OR191LP应用举例之一w 例1合理下料问题 料长7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？关键：设变量。OR192方案如下： 方案 1 2 3 4 5 6 7 8 料型 2.9米 1

37、2 0 1 0 1 0 0 2.1米 0 0 2 2 1 1 3 0 1.5米 3 1 2 0 3 1 0 4 合计 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 残料 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4OR193应用举例之二 w 例2混合配方问题A、B、C、D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。已知产品价格和原料价格，求利润最大的配方。关键：设变量。OR194应用举例之三w 例3滚动投资问题兹有100万元闲钱，投资方向有四： 第四年第一年第二年第三年A项目110%B项目135%C项目125%D项目104%第五年各年投资什么项

38、目，使第五年末资本总额为最大？OR195应用举例之四w 例4动态生产计划问题 工厂做n个月的生产计划，第j月需求量dj、正常生产能力aj、加班生产能力bj、正常生产成本cj、加班生产成本ej、库存能力为I、库存费用hj，设期初、期末库存为零。求费用最小的生产计划。 设第月正常生产xj件，加班生产件yj，存储zj件。则： 本期生产+上期库存-本期库存=本期需求OR196第三章 对偶问题与灵敏度分析w要求： 了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析 OR1973.1 对偶问题w3.1.1 对偶问题的提出 回顾例题1： 现在

39、计划不生产A、B两产品，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？产品A产品B资源限制劳动力设备原材料 9 4 3 4 5 10 360 200 300单位利润 70 120OR198对偶模型w 设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。 出租收入不低于生产收入： 9y1+4y2+ 3y3 70 4y1+5y2+10y3 120 目标：=360y1+200y2+300y3 出租收入越多越好？至少不低于某数OR199原问题与对偶问题之比较原问题： 对偶问题：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+ 4X2360 9

40、y1+4y2+ 3y3 70 4X1+ 5X2 200 4y1+5y2+10y3 1203X1+10X2 300 y1 0, y2 0, y3 0X10 X20OR11003.1.2对偶规则原问题一般模型： 对偶问题一般模型：maxZ=CX min =Yb AX b YA C X 0 Y 0OR1101比较两形式知：比较两形式知：TmnmTnbbbbcccCyyyYxxxX),(),(),(),(21212121上上两两式式中中mnmmnnaaaaaaaaaA212222111211OR1102对偶规则w 原问题有m个约束条件，对偶问题有m个变量w 原问题有n个变量，对偶问题有n个约束条件w

41、原问题的价值系数对应对偶问题的右端项w 原问题的右端项对应对偶问题的价值系数w 原问题的技术系数矩阵转置后为对偶问题系数矩阵w 原问题的约束条件与对偶问题方向相反w 原问题与对偶问题优化方向相反OR1103标准型的对偶变换0, 15232 25322. .432max4321432143214321xxxxxxxxxxxxtsxxxxZ目目标标0,4233322212.1525min212121212121yyyyyyyyyytsyyw目标函数为：OR1104非标准型的对偶变换0,510342023.54max .2 1221212121xxxxxxxxtsxxZ不限原线性规划问题例 0, 5

42、51033420223.554max)(max, 221221221221221221xxxxxxxxxxxxxxxtsxxxZ型标准问题化为不限经整理得令32132132132132313,0,532443.51020min: yyyyyyyyytsyyywyyy0,532532443. .551020min 323121323121323121323121323121yyyyyyyyyyyyyyyytsyyyyw则应用标准型对偶变换规OR1105对偶规则. 原问题 对偶问题目标函数 max min 目标函数约束条件 = 变量无约束 变量符号 无约束 约束条件=OR1106对偶变换的规则原原

43、 问问 题题 (max, )对对 偶偶 问问 题题 (min, )技技 术术 系系 数数 矩矩 阵阵 A技技 术术 系系 数数 矩矩 阵阵AT价价 值值 系系 数数 C右右 端端 项项 b右右 端端 项项 b价价 值值 系系 数数 C第第i行行 约约 束束 条条 件件 为为 型型对对 偶偶 变变 量量 yi 0第第i行行 约约 束束 条条 件件 为为 型型对对 偶偶 变变 量量 yi 0第第i行行 约约 束束 条条 件件 为为 = 型型对对 偶偶 变变 量量 yi 不不 限限决决 策策 变变 量量 xj 0第第j行行 约约 束束 条条 件件 为为 型型决决 策策 变变 量量 xj 0第第j行行

44、 约约 束束 条条 件件 为为 型型决决 策策 变变 量量 xj 不不 限限第第j行行 约约 束束 条条 件件 为为 = 型型OR1107w 约束条件的类型与非负条件对偶约束条件的类型与非负条件对偶w 非标准的约束条件类型对应非正常的非负非标准的约束条件类型对应非正常的非负条件条件w 对偶变换是一一对应的对偶变换是一一对应的OR1108对偶规则简捷记法w原问题标准则对偶问题标准w原问题不标准则对偶问题不标准w例题2 max =7y1+4y2-2y3minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 3 2x1+x2-4x3+x4+3x5 7 y1 +3y3 2 x1+ 2x3 -x

45、4 4 -4y1+ 2y2 -6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 0 x1，x2，x3 0; 3y1 +y3=1 x4 0;x5无限制 y1 0y2 0y3 无约束 OR1109写出下列问题的对偶规划写出下列问题的对偶规划w 例例1:2153) 1 (xxMaxz0,252:.212121xxxxxxt s2125infyyM0,5232:.212121yyyyyyt sOR1110w 例2：3212xxxMaxz无符号限制， ,63282:.32132121xxxxxxxxt s2168infyyM无符号限制2122121,132212:.yyyyyyytsOR

46、1111w 例3：4321432xxxxMaxz无符号限制4231432143214321, 0,1067912857653:.xxxxxxxxxxxxxxxxtsOR1112w 答案:3211085infyyyM0,4653372971126:.321321321321321yyyyyyyyyyyyyyyts无符号限制OR1113w 例4：5432187523infxxxxxM2551025222332643:.2143143215432xxxxxxxxxxxxxtsOR1114w 变形为：5432187523infxxxxxM2551025222332643:.22114314321543

47、2xxxxxxxxxxxxxxxtsOR1115w 对偶规划为：7654321255102526yyyyyyyMaxz0,;847235232332:.754321132132176215432yyyyyyyyyyyyyyyyyyyyyts无符号限制OR1116 3.2 线性规划的对偶定理1 弱对偶定理定理 对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值 为了便于讨论，下面不妨总是假设为了便于讨论，下面不妨总是假设0XbAXCX. .max :tsZ原问题0YCYAYb. .min :tsw对偶问题#CXAXYbY0YCAY0XbAXYX

48、., :0000000000容容易易看看出出有有故故有有题题的的可可行行解解分分别别为为原原问问题题和和对对偶偶问问由由于于证证OR1117 弱弱对偶定理推论对偶定理推论w max问题的任何可行解目标函数值是其对偶问题的任何可行解目标函数值是其对偶min问题目问题目标函数值的下限；标函数值的下限； min问题的任何可行解目标函数值问题的任何可行解目标函数值是其对偶是其对偶max问题目标函数值的上限问题目标函数值的上限w 如果原如果原max(min)问题为无界解，则其对偶问题为无界解，则其对偶 min (max)问题无可行解问题无可行解w 如果原如果原max(min)问题有可行解，其对偶问题有可

49、行解，其对偶 min (max)问问题无可行解，则原问题为无界解题无可行解，则原问题为无界解w 注：存在原问题和对偶问题同时无可行解的情况注：存在原问题和对偶问题同时无可行解的情况OR11182 最优解判别最优解判别定理定理定理定理 若原问题的某个可行解若原问题的某个可行解X0的目标函数值与对偶问题的目标函数值与对偶问题某个可行解某个可行解Y0的目标函数值相等，则的目标函数值相等，则X0, Y0分别是相分别是相应问题的最优解应问题的最优解证：由弱对偶定理推论证：由弱对偶定理推论1，结论是显然的。，结论是显然的。 即即CX0 = Y0b CX, Y0b = CX0 Yb 。 证毕。证毕。3 主对

50、偶主对偶定理定理定理定理 如果原问题和对偶问题都有可行解，则它们都有最如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论证：由弱对偶定理推论1可知，原问题和对偶问题的目标可知，原问题和对偶问题的目标函数有界，故一定存在最优解。函数有界，故一定存在最优解。 现证明定理的后一句话。现证明定理的后一句话。 OR1119 主对偶主对偶定理的证明定理的证明 证：现证明定理的后一句话。证：现证明定理的后一句话。 设设 X0 为原问题的最优解，它所对应的基矩阵是为原问题的最优解，它所对应的基矩阵是 B， X0= B 1

51、 b，则其检验数满足，则其检验数满足 C CBB 1A 0 令令 Y0= CBB 1，则有，则有 Y0 A C。 显然显然Y0为对偶问题的可行解。因此有对偶问题目标函为对偶问题的可行解。因此有对偶问题目标函数值，数值， w(Y0)=Y0b= CBB 1 b 而原问题最优解的目标函数值为而原问题最优解的目标函数值为 z(X0)=CX0= CBB 1 b故由最优解判别定理可知故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。为对偶问题的最优解。证毕。n该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解对偶变量的最优解等于原问题松弛变量的机会成本等于原问题松弛变量的机会成本n即对偶变量的最

52、优解是原问题资源的影子价格影子价格OR11204 互补松弛互补松弛定理定理定理定理 设设X0, , Y0分别是原问题和对偶问题的可行解，分别是原问题和对偶问题的可行解，U0为为原问题的松弛变量的值、原问题的松弛变量的值、V0为对偶问题剩余变量的为对偶问题剩余变量的值。值。X0, , Y0分别是原问题和对偶问题最优解的充分分别是原问题和对偶问题最优解的充分必要条件是必要条件是 Y0 U0 + V0 X0 = 0证：由定理所设，可知有证：由定理所设，可知有 A X0 + U0 = b X0, U0 0 (1) Y0 A V0 = C Y0, V0 0 (2)分别以分别以Y0左乘左乘(1)式，以式，

53、以X0右乘右乘(2)式后，两式相减，得式后，两式相减，得 Y0 U0 + V0 X0 = Y0 b C X0若若 Y0 U0 + V0 X0 = 0，根据最优解判别定理，根据最优解判别定理， X0, , Y0分别分别是原问题和对偶问题最优解。反之亦然。是原问题和对偶问题最优解。反之亦然。 证毕。证毕。miuynjxviijj, 2 , 10, 2 , 100000OR11215 原问题检验数与对偶问题的解原问题检验数与对偶问题的解w 在主对偶定理的证明中我们有：对偶在主对偶定理的证明中我们有：对偶(min型型)变量的最变量的最优解等于原问题松弛变量的机会成本，或者说原问题松优解等于原问题松弛变

54、量的机会成本，或者说原问题松弛变量检验数的绝对值弛变量检验数的绝对值w 容易证明，对偶问题最优解的剩余变量解值等于原问题容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值对应变量的检验数的绝对值w 由于原问题和对偶问题是相互对偶的，因此对偶问题的由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。检验数与原问题的解也有类似上述关系。w 更一般地讲，不管原问题是否标准，在最优解的单纯型更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题表中，都有原问题虚变量虚变量(松弛或剩余松弛或剩余) 的检验数对应其的检验数对应其对偶问题对偶问

55、题实变量实变量 (对偶变量对偶变量)的最优解，原问题的最优解，原问题实变量实变量(决策变量决策变量) 的检验数对应其对偶问题的检验数对应其对偶问题虚变量虚变量 (松弛或剩松弛或剩余变量余变量)的最优解。因此，原问题或对偶问题只需求解的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。其中之一就可以了。OR11223.3 3.3 线性规划问题的进一步研究线性规划问题的进一步研究1. 对偶单纯形法对偶单纯形法w 对偶单纯形法在什么情况下使用对偶单纯形法在什么情况下使用 ： 应用前提：应用前提： 有一个基，其对应的基本解满足有一个基，其对应的基本解满足 单纯形表的检验数行全部非正（对偶可单纯形

56、表的检验数行全部非正（对偶可 行）；行）； 变量取值可有负数（非可行解）。变量取值可有负数（非可行解）。 *注：通过矩阵行变换运算，使所有相应变量注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯性表。取值均为非负数即得到最优单纯性表。OR1123w 对偶单纯形法求解线性规划问题过程：对偶单纯形法求解线性规划问题过程： 1、建立初始对偶单纯形表，对应一个基本解，所建立初始对偶单纯形表，对应一个基本解，所有检验数均非正，转有检验数均非正，转2；2、若、若 b 0 ，则得到最优解，停止；否则，若有，则得到最优解，停止；否则，若有 bk 0 则选则选 k 行的基变量为出基变量，转行的

57、基变量为出基变量，转3；3、若所有、若所有 akj 0 ( j = 1,2,n )，则原问题无可，则原问题无可行解，停止；否则，若有行解，停止；否则，若有 akj 0 则选则选 = min j/ akj akj 0 cs Min j / asj asj 0 br Min-bi / air air 0 OR1141w 例、上例最优单纯形表如下例、上例最优单纯形表如下 0 0.25 0 这里这里 B-1 = -2 0.5 1 各列分别对应各列分别对应 b1、b2、b3 的单一的单一w 0.5 -0.125 0 w 变化。因此，设变化。因此，设 b1 增加增加 4，则，则 x1 , x5 , x2

58、分别变为：分别变为：w 4 + 0*4 = 4，4 + (-2)*4 = - 4 0，2 + 0.5*4 = 4w 用对偶单纯形法进一步求解，可得：用对偶单纯形法进一步求解，可得：w x* = ( 4, 3, 2, 0, 0 )T f* = 17C i23000CBXBBX1X2X3X4X52 X141001/400 X5400-21/213 X22011/2-1/80j00-1.5-1/80OR1142w 增加一个变量增加一个变量w 增加变量 Xn+1 则有相应的 Pn+1 ， Cn+1 。那么，计算出w B-1Pn+1 n+1 =Cn+1 - Cri ari n+1 w 填入最优单纯形表，

59、若 n+1 0 则最优解不变；否则，进一步用单纯形法求解。w 例、前例增加X6，P6 = ( 2, 6, 3 )T ，C6 = 5 。计算得到Ci230005CBXBbX1X2X3X4X5X62 X141001/401.50 X5400-21/2123 X22011/2-1/800.25j00-1.5-1/801.25用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5OR1143w 增加一个约束增加一个约束w 增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入1个新的非负变量（原约束若是小于等于形式可

60、引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。w 例、前例增加3x1+ 2x215，原最优解不满足这个约束。于是Ci230005CBXBbX1X2X3X4X5X62 X141001/4000 X5400-21/2103 X22011/2-1/8000 X6-100-1-1/201j00-1.5-1/800OR1144w A中元素发生变化中元素发生变化 （只讨论 N 中某一列变化情况）w 与增加变量 xn+1 的情况类似，假设 pj 变化 。那么，重新计算出 w B-1Pj j = Cj - Cri ari j w 填入最优单纯形