运筹学 单纯形法课件_第1页
运筹学 单纯形法课件_第2页
运筹学 单纯形法课件_第3页
运筹学 单纯形法课件_第4页
运筹学 单纯形法课件_第5页
已阅读5页,还剩34页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、2020/8/17,运筹学 单纯形法,1,第4节 单纯形法计算步骤,2020/8/17,运筹学 单纯形法,2,Step 1 化为标准型,找出初始可行基,并列出初始单纯形表,上述初始单纯形表中,最后一行称为检验数j,2020/8/17,运筹学 单纯形法,3,2020/8/17,运筹学 单纯形法,4,Step2:检查非基变量所对应的检验数j,若所有的j0,则当前的基可行解就是最优解,当前的目标函数值就是最优值,停止计算。 否则,转入下一步。 Step3:若存在一个k0,k所对应的变量xk的系数列向量Pk0(即Pk中每一个分量aik0),则该LP无有限最优解,停止计算。 否则,转入下一步。 Step

2、4:进行可行基的迭代。 重复以上步骤,2020/8/17,运筹学 单纯形法,5,例7 用单纯形法求解例6。 max z = 2x1 + 3x2,s.t.,x1 + 2x2 +x3 =8 4x1 +x4 =16 4x2 +x5 =12 xj0,j=1,2,5,2020/8/17,运筹学 单纯形法,6,练习:,分别用图解法和单纯形法求解下列线性规划问题,并指出单纯形法迭代的每一步相当于图形上哪一个顶点。,Max Z = 10 x1+ 5x2 3x1+ 4x29 5x1+ 2x2 8 x1 ,x20,2020/8/17,运筹学 单纯形法,7,解:,j,10,5,0,0, ,3,8/5, ,x1入,x

3、4出,j,0,1,0,-2, ,x2入,x3出,3/2,4,j,0,0,-5/14,-25/14,所以:X*=(x1,x2)T=(1,3/2)T Z*=35/2, ,对应0,对应A,对应B,2020/8/17,运筹学 单纯形法,8,回顾:单纯形法求解步骤:,2020/8/17,运筹学 单纯形法,9,第5节 单纯形法的进一步讨论,2020/8/17,运筹学 单纯形法,10,第5节 单纯形法的进一步讨论,一、人工变量法(大M法) 约束条件: “” 加一个松弛变量 “” 减一个剩余变量后,再加一个人工变量 “” 加一个人工变量 目标函数: 人工变量的系数为“M”,即罚因子 若线性规划问题有最优解则人

4、工变量必为0。,2020/8/17,运筹学 单纯形法,11,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,增加人工变量后,线性规划问题中就存在一个B为单位矩阵, 后面可以根据我们前面所讲的单纯形法来进行求解。,MaxZ=-3x1+x3-Mx6-Mx7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,标准化及变形,2020/8/17,运筹学 单纯形法,12,练习:列出初始单纯形表,并求解第2小题的最优解 P55,2.2(1) 2.,2020/8

5、/17,运筹学 单纯形法,13,单纯形表,j,-3-2M,4M,1,0,0, ,3,x2入,x6出,-M,0,4,1, ,j,6M-3,0,4M+1,0,-4M, ,-,x1入,x7出,3M,0,1,1, ,j,0,0,3,0,-M-3/2, ,9,x3入,x1出,3/2,-M+1/2,3/2,-, ,j,-9/2,0,0,0,-M+3/4,-3/4,-M-1/4,所以:X*=(x1,x2,x3)T=(0,5/2, 3/2)T Z*=3/2,2020/8/17,运筹学 单纯形法,14,二、两阶段法 第一阶段暂不考虑原问题是否存在基可行解,给原问题加入人工变量,并构建一个仅含人工变量的目标函数(

6、求极小化),人工变量的价值系数一般为1,约束条件和原问题的一样。 当第一阶段中目标函数的最优值0,即人工变量0,则转入第二阶段;若第一阶段中目标函数的最优值不等于0,即人工变量不等于0,则判断原问题为无解。 第二阶段:将第一阶段计算所得的单纯形表划去人工变量所在的列,并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表,进行进一步的求解。,2020/8/17,运筹学 单纯形法,15,求解辅助问题,得到辅助问题的最优解,引进人工变量x6,x7,构造辅助问题,辅助问题的目标函数为所有人工变量之和的极小化,Max W = 0 ?,原问题没有可行解。,把辅助问题的最优解作为原问题的初始基础可行解

7、,用单纯形法求解原问题,得到原问题的最优解,否,是,两阶段法的算法流程图,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,Max W= -x6 - x7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,2020/8/17,运筹学 单纯形法,16,(第一阶段)单纯形表1,j,-2,4,0,0,0, ,3,x2入,x6出,-1,0,4,1, ,j,6,0,4,0,-4, ,x1入,x7出,3,0,1,1, ,j,0,0,0,0,-1,0,-1,所以

8、:已得最优解,且人工变量为非基变量,则可去掉人工变量,得原问题的一个即可行基。,2020/8/17,运筹学 单纯形法,17,(第二阶段)单纯形表2,j,0,0,3,0,3/2, ,-,9,3/2, ,x3入,x1出,j,-9/2,0,0,0,-3/4,所以: X*=(x1,x2,x3)T=(0,5/2, 3/2)T Z*=3/2,2020/8/17,运筹学 单纯形法,18,单纯形法小结,给定LP问题首先化为标准型,选取或构造一个单位矩阵作为基,求出初始基可行解,并列出初始单纯形表。标准化过程按第1.3节内容分7种情况:,2020/8/17,运筹学 单纯形法,19,第5节 单纯形法的进一步讨论,

9、人工变量法(大M法)和两阶段法 约束条件: “” 加一个松弛变量 “” 减一个剩余变量后,再加一个人工变量 “” 加一个人工变量 若线性规划问题有最优解则人工变量必为0。,2020/8/17,运筹学 单纯形法,20,目标函数极小化时解的最优性判别; 无可行解的判别; 无界的判别; 无穷多最优解的判别; 唯一最优解的判别.,三、单纯形法计算中的几个问题,当所有非基变量的j0时为最优解;,最优解中人工变量为非0的基变量时;,存在某个k0,且所有的aik0时;,得最优解时,有检验数为0的非基变量;,得最优解时,所有非基变量检验数为负;,2020/8/17,运筹学 单纯形法,21,j,40,45,0,

10、25,100/3,40, 3 ,x2入,x4出,j,0,0,0,-5,因为全j 0,且1=0,则有无穷多最优解。 所以:其中一个最优解为X*=(0,80/3,20,0,0) T,Z*=1700,例1:,0,-10,思考:无穷多最优解的一般形式?,2020/8/17,运筹学 单纯形法,22,j,1,1,0,0,-,50, ,x1入,x4出,j,0,2,0,-1,因为2 = 2,且ai2 全0所以:无界,例2:,2020/8/17,运筹学 单纯形法,23,例3:,下表为一极大化问题对应的单纯形表,讨论在a1,a2,a3,a4,a5,a6取何值的情况下,该表中的解为: 唯一最优解; 无穷多最优解;

11、无界; 无可行解; 非最优,继续换基: X3换入,x2换出,a40,a20, a30 a40,a50, x4或x2为人工变量,a60 ; x1为人工变量,a60 a40,a4a5;a6/a12a10 a60 a1 0,2020/8/17,运筹学 单纯形法,24,复习题:下表为一求解极大值线性规划问题的初始单纯型表及迭代后的表, 为松弛变量,试求表中aL的值及各变量下标mt的值;,2020/8/17,运筹学 单纯形法,25,第6节 应用举例,一般而言,一个经济、管理问题凡是满足以下条件时,才能建立线性规划模型。 .要求解问题的目标函数能用数值指标来反映,且为线性函数; .存在着多种方案; .要求

12、达到的目标是在一定条件下实现的,这些约束可用线性等式或不等式描述。,2020/8/17,运筹学 单纯形法,26,建模步骤:, 第一步:设置要求解的决策变量。决策变量选取得当,不仅能顺利地建立模型而且能方便地求解,否则很可能事倍功半。 第二步:找出所有的限制,即约束条件,并用决策变量的线性方程或线性不等式来表示。 第三步:明确目标要求,并用决策变量的线性函数来表示,确定对函数是取极大还是取极小的要求。 决策变量的非负要求可以根据问题的实际意义加以确定。,2020/8/17,运筹学 单纯形法,27,一般的产品计划问题举例 例1:,某工厂生产A、B两种产品,均需经过两道工序,每生产一吨产品A需要经第

13、一道工序加工2小时,第二道工序加工3小时;每生产一吨产品B需要经第一道工序加工3小时,第二道工序加工4小时。可供利用的第一道工序为12小时,第二道工序为24小时。 生产产品B的同时产出副产品C,每生产一吨产品B,可同时得到2吨产品C而毋需外加任何费用;副产品C一部分可以盈利,剩下的只能报废。 出售产品A每吨能盈利400元、产品B每吨能盈利1000元,每销售一吨副产品C能盈利300元,而剩余要报废的则每吨损失200元。经市场预测,在计划期内产品C最大销量为5吨。试列出线性规划模型,决定A、B两种产品的产量,使工厂总的利润最大。,2020/8/17,运筹学 单纯形法,28,数学模型:,设:x1产品

14、A的产量, x2产品B的产量,x3产品C的销售量,x4产品C的报废量。依题意,可得,2020/8/17,运筹学 单纯形法,29,例2 合理下料问题。 现要截取2.9米、2.1米和1.5米的圆钢各100根。而现在仅有一批长7.4米的棒料毛坯,问应如何下料,才能使所消耗的原材料最省。,解:依题意,在排除明显不合理的方案后。可以列出8种套裁方案,前5种更合理。,2020/8/17,运筹学 单纯形法,30,例3,2020/8/17,运筹学 单纯形法,31,练习1:,练习2:P57,T2.9,2020/8/17,运筹学 单纯形法,32,2020/8/17,运筹学 单纯形法,33,例4. 连续投资问题。P

15、53, 2-13,2020/8/17,运筹学 单纯形法,34,练习:,设某投资者有30 000元可供为期四年的投资,现有五个投资机会可供选择: A: 可在每年年初投资,每年每元投资可获0.2元。 B: 第一年年初或第三年年初投资,每两年每元投资可获利润0.5元,两年后获利。 C: 第一年初投资,三年后每元投资获利0.8元。这项投资最多不超过20 000元。 D: 第二年年初投资,两年后每元投资可获利0.6元。这项投资最多不超过15 000元。 E: 第一年年初投资,四年后每元获利1.7元,这项投资最多不超过20 000元。 投资者应如何投资,使他在四年后所拥有资金总额最大?,2020/8/17,运筹学 单纯形法,35,第一章 总结,基本概念: 可行解,基,基解,基可行解,可行基,凸集,顶点 基本定理: 可行域为凸集; 基可行解 顶点; 最优解一定在顶点上取得。,2020/8/17,运筹学 单纯形法,36,基本问题:,什么是线性规划问题的数学模型结构? 如何用图解法及单纯形法判断解的情况?

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论