线性规划与单纯形法资料课件.ppt

《线性规划与单纯形法资料课件.ppt》由会员分享，可在线阅读，更多相关《线性规划与单纯形法资料课件.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 线性规划与单纯形法线性规划与单纯形法劫瑰便哆烂舌羔相谭蝇娘它贱剑厚溢魔宗朗晶县镇蜜摘绿判搽难院括慨勒线性规划与单纯形法线性规划与单纯形法线性规划（LP：Linear Programming）规划论中的静态规划解决有限资源的最佳分配问题求解方法：图解法单纯形解法 滇鸵麦苟泄钎躺郭亦揪赣仓刀魁洞垣宝店萤撒灭骄辈狸高藉枉矩劝糠酶操线性规划与单纯形法线性规划与单纯形法线性规划简介19391939年苏联的康托洛维奇（年苏联的康托洛维奇（H.B.Kahtopob H.B.Kahtopob）和美国的希奇）和美国的希奇柯克（柯克（F.L.HitchcockF.L.Hitchcock）等人就在生产组织管理和制

2、定交通）等人就在生产组织管理和制定交通运输方案方面首先研究和应用一线性规划方法。运输方案方面首先研究和应用一线性规划方法。19471947年旦茨格等人提出了求解线性规划问题的单纯形法，为年旦茨格等人提出了求解线性规划问题的单纯形法，为线性规划的理论与计算奠定了基础。线性规划的理论与计算奠定了基础。随着电子计算机的出现和日益完善，规划论得到迅速的发展，随着电子计算机的出现和日益完善，规划论得到迅速的发展，可用电子计算机来处理成千上万个约束条件和变量的大规模可用电子计算机来处理成千上万个约束条件和变量的大规模线性规划问题，从解决技术问题的最优化，到工业、农业、线性规划问题，从解决技术问题的最优化，

3、到工业、农业、商业、交通运输业以及决策分析部门都可以发挥作用。商业、交通运输业以及决策分析部门都可以发挥作用。就斑继碴菜衙歌批汹涡颖粳擞躲堂炼襄终剁描仍驶楚筐扇馏谜瘫歹族宦层线性规划与单纯形法线性规划与单纯形法线性规划问题的三个要素线性规划问题的三个要素 决策变量决策问题待定的量值称为决策变量。决策变量的取值要求非负。约束条件任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。有的目标要实现极大

4、，有的则要求极小。辟峭宵惜怠永末扁犊郴照投半潞武赂铭和丽鞭擅臀逝散一塞魂瓮衣隆乓蝗线性规划与单纯形法线性规划与单纯形法1线性规划问题及其数学模型例 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排生产计划能使该厂获利最多？这个问题可以用下面的数学模型来描述，设计划期内产品、的产量分别为x1，x2，可获利润用z表示，则有：Max Z=2x1+3x2x1+2x284x1 16 4x212x1,x201.1问题的提出问题的提出泡抑颜环簧手懈期凳老葱肘逢去沥但部帧浓方琢损荡授像药挫迹拾

5、骏辗蟹线性规划与单纯形法线性规划与单纯形法又例又例 靠近某河流有两个化工厂，流经靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天第一化工厂的河流流量为每天500万万m3，两工厂之间有一条流量为每天两工厂之间有一条流量为每天200万万m3的的支流（见图）。支流（见图）。第一化工厂每天排放污水第一化工厂每天排放污水2万万m3，第二，第二化工厂每天排放污水化工厂每天排放污水 1.4万万m3。污水从。污水从工厂工厂1流到工厂流到工厂2前会有前会有20%自然净化。自然净化。根据环保要求，河水中污水的含量应不根据环保要求，河水中污水的含量应不大于大于0.2%。而工厂。而工厂1和工厂和工厂2处理污水的

6、处理污水的成本分别为成本分别为1000元元/万万m3和和800元元/万万m3。问两工厂各应处理多少污水才能使处理问两工厂各应处理多少污水才能使处理污水的总费用最低？污水的总费用最低？设工厂设工厂1和工厂和工厂2每天分别处理污水每天分别处理污水x1和和x2万万m3，则有，则有：Min z=1000 x1+800 x2(2-x1)/500 0.0020.8(2-x1)+1.4-x2/700 0.002 x12,x21.4 x1,x20挥孟徽肠邯腻鞋泣怠褐筏赘傍侥谁剧扑咆贪嫉响癣钾冈乔赠址补哦媚光粳线性规划与单纯形法线性规划与单纯形法以上两例都有一些共同的特征：以上两例都有一些共同的特征：用一组变量

7、表示某个方案，一用一组变量表示某个方案，一般这些变量取值是非负的。般这些变量取值是非负的。存在一定的约束条件，可以用存在一定的约束条件，可以用线性等式或线性不等式来表示。线性等式或线性不等式来表示。都有一个要达到的目标，可以都有一个要达到的目标，可以用决策变量的线性函数来表示。用决策变量的线性函数来表示。满足以上条件的数学模型称为满足以上条件的数学模型称为线性规划模型。线性规划模型线性规划模型。线性规划模型的一般形式如下：的一般形式如下：其中：其中：cj为价值系数；为价值系数；aij为技术系数；为技术系数；bi为限额系数；为限额系数；xj为非负变量为非负变量顽堵屈蝴衰厦庚秩剃匣溉峡炕餐所专龄涸

8、礼周碟棍玲舱骇适渊钥逐旨躁荤线性规划与单纯形法线性规划与单纯形法图解法即是用图示的方法来求解线性规划问图解法即是用图示的方法来求解线性规划问题。题。一个二维的线性规划问题，可以在平面图上一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示这就比较麻烦，而维数再高以后就不能图示了。了。1.2线性规划的图解法线性规划的图解法层瘴糖榜挟倒厄鱼赶岗辉堵喧侵俞堂氏益巫疡察申周氮止踩青卵浦疏惺脂线性规划与单纯形法线性规划与单纯形法可行域的确定可行域的确定例例:数学模型为数学模型为 maxZ=3x1+5

9、x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0 x1=82x2=123x1+4 x2=36五边形五边形OABCD内内(含边界含边界)的任意一点的任意一点(x1，x2)都是满足所有都是满足所有约束条件的一个解，称之可行解约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。条件共同围城的区域。灵青碍蛰闪仆阅辣形芹燃晓傲凡冤臂研讲蓖筹既隙逮缺断掷蚜漠字蔬砧驼线性规划与单纯形法线性规划与单纯形法最优解的确定最优解的确定Z=30Z=42Z=15目标函数 Z=3x1+5 x2 代

10、表以Z为参数的一族平行线。x1=82x2=123x1+4 x2=36等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解的解鉴汕钡道胯汲恼樱廷捌碘舷撞肥腥诱说猿境碟聚炸本缮誊曾土鳞弹鲤搬狞线性规划与单纯形法线性规划与单纯形法由由线线性性不不等等式式组组成成的的可可行行域域是是凸凸集集(凸凸集集的的定定义义是是：集集合合内内部部任任意意两两点点连连线线上上的的点点都都属属于于这这个集合个集合)。可可行行域域有有有有限限个个顶顶点点。设设规规划划问问题题有有n个个变变量量，m

11、个约束，则顶点的个数不多于个约束，则顶点的个数不多于Cnm个。个。目目标标函函数数最最优优值值一一定定在在可可行行域域的的边边界界达达到到，而而不可能在其内部。不可能在其内部。几点说明几点说明渔募舍试缨毙毋箩崎瘫您欣霞贝霞锗袋芳狭悉帜编槛沂虽桓掷馒圆穆伤钨线性规划与单纯形法线性规划与单纯形法解的可能性解的可能性x1=82x2=123x1+4 x2=36上例的数学模型变为上例的数学模型变为 maxZ=3x1+4 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0Z=24Z=36Z=12唯一最优解：只有一个最优点。多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们

12、连线上的每一点都是最优解。德狸寞源纵脯辕彬磊魔纵惕煤矩焉姥人霹抹沼楔杭盗伴盾眨蔗翘瘦环暇菊线性规划与单纯形法线性规划与单纯形法无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3Z=6Z=12烩奶权纠它忽狼莎黑恋媚气学惑厢蜗豌吧颜旦回近玲狈碍装赢蝉醋仍贤拧线性规划与单纯形法线性规划与单纯形法无可行解：若约束条件相互矛盾，则可行域为空集例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x

13、1+x2=2x1-3 x2=3歌枫莱坚铝挣辟陌哎疫俗蓉色几召混怖芜昧秧薪逃副已呈沛润架蒂布缨婉线性规划与单纯形法线性规划与单纯形法唯一最优解无穷多最优解x1x2x1x2无界解无可行解当线性规划的可行域非空它是有界或无界凸多边形，若存在最优解，则最优解一定在可行域的的某个顶点或顶点的连线取得，也即有唯一最优解或无穷多最优解图解法虽然简单直观，但是只能解决两个变量爆雁绎枢甫遗舀克红缎舱副矮孽涸真岂猫疆史橡旁镑惜岗报臃衔脏随艰擂线性规划与单纯形法线性规划与单纯形法练习:用图解法求解以下LP模型但选墙传跌潭边氮绞宿酿铱病哆馒寓馏丽抽闽明整恼鹿呢矿宠祷盒兆堤蚀线性规划与单纯形法线性规划与单纯形法Answ

14、erx1x2-2x1+3x2=2x1-2x2=20Ax1=-10,x2=-6,z=-86般席苟爸珠顿贼行捧凋钮蔗同守仰危烘朱尉凹穷越怯磕巳备诫墅溪垃侨亭线性规划与单纯形法线性规划与单纯形法1.3 线性规划的标准型线性规划问题的数学模型有各种不同的形式，如目标函数有极大化和极小化；约束条件有“”、“”和“”三种情况；决策变量一般有非负性要求，有的则没有。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为：目标函数极大化约束条件为等式右端常数项bi0决策变量非负。一一、标准型、标准型碍桨铡投羽汇篡吵突忧有送猖边郁贪臭惶反玲遂疚狞询暗炯目缎硫殆爪浸线性规划与单纯形法线性

15、规划与单纯形法1.代数式二、标准型的表达方式二、标准型的表达方式 有代数式、矩阵式：有代数式、矩阵式：maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0maxZ=cjxj aijxjbi (i=1,2,m)xj0 (j=1,2,n)简记惮确杰仔汛台档蜘刁枢娜申碗袄聪疼履九沮信革戮千径寓溪类娩蔑脑冗亮线性规划与单纯形法线性规划与单纯形法2.矩阵式矩阵式 莫设抑陀埠拎掷忿离扩藤戈虞杂春险阔邢临纠还碑胳萎署淀沽甚羽业食陵线性规划与单纯形法线性规划与单纯形法目标函数极小

16、化问题目标函数极小化问题 目标函数为 min z=c1x1+c2x2+cnxn 令z=-z,变为 max z=-c1x1-c2x2-cnxn右端常数项非正右端常数项非正 两端同乘以-1约束条件为不等式约束条件为不等式当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式变成了等式；当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。决策变量决策变量x xk k没有非负性要求没有非负性要求 令xk=xk-x k，其中xk，x k 0，用xk、x k 取代模型中xk三、非标准型向标准型转化三、非标准型向标准型转化 悯厚培疙哩惺痞譬娱痈蝶鸡迈荣彤霜迅士捧赛删堪糯筋魂紧急梢

17、谴扣操臣线性规划与单纯形法线性规划与单纯形法标准型 例例1 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 0 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 裤冉婪掐饿蕊钱墓脐晋徐陷拳涂宁预供物扦隶沽推旗帐谁布画觅喳斯枚茂线性规划与单纯形法线性规划与单纯形法 minZ=x1+2 x2+3 x3 x1+2 x2+x35 2x1+3 x2+x36 -x1 -x2 -x3-2 x1 0,x30 例例2 minZ=x1+2 x2-3 x3

18、 x1+2 x2-x3 5 2x1+3 x2-x3 6 -x1 -x2 +x3 -2 x1 0,x3 0标准化标准化1白刃酷室净掏才稠附赡遮为劝咱桨掐易魁干病乱政馈乓芋膊仟钙行拥韦凡线性规划与单纯形法线性规划与单纯形法标准化标准化2 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 -x1 -(x2-x 2)-x3-2 x1,x2,x 2,x3 0 标准化标准化3 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x

19、2,x3 0湾任蔼乳很郧疏速善退疵胯峻垛棚谷界横昆抨杭整缝胎屑敲绘趁今础睁谷线性规划与单纯形法线性规划与单纯形法标准化标准化4 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4 0标准化标准化5 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5=6 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4,x5 0肯谗摹坟饮讽辽普韩痈贵促属驹匝颐惭氢挽澎楚美坪挣徽晚包

20、堆咎黑奢柿线性规划与单纯形法线性规划与单纯形法标准化标准化6 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6=2 x1,x2,x 2,x3,x4,x5,x6 0标准化标准化7 maxZ=-x1-2(x2-x 2)-3x3+0 x4+0 x5+0 x6 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6 =2 x1,x2,x 2,x3,x4,x5,x6 0 错亡因淹譬豆侩财仗好膝京涧胶气端籍规

21、模比秃棍婿底礼什拷痞逻脐耪攒线性规划与单纯形法线性规划与单纯形法可行解：满足约束条件AX=b,X0的解。最优解：使目标函数达到最大的可行解，称为最优解。基设A是约束方程组的mn维系数矩阵，其秩为m，B是矩阵A中的mm阶非奇异子矩阵，则称B是线性规划问题的一个基。mn，且m个方程线性无关，即矩阵A的秩为m；根据线性代数定理可知，nm，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。一、线性规划解的概念一、线性规划解的概念 1.4 线性规划问题的解的概念线性规划问题的解的概念浙斩凭喻鲤裳仙菏甄意蝴并前厚鹿颖沮撰瞩癌足我衰氦拉央痰军慎膳雹炉线性规划与单纯形法线性规划与单纯形法线性方程组的增广

22、矩阵例例 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 0单位矩阵单位矩阵炙恫廉拢丸绦酚揭远吕括铆埂氓很丙悔贫缨枪薯铲抿溪乾妙片汪祝质嗜溪线性规划与单纯形法线性规划与单纯形法基矩阵：系数矩阵A中任意m列所组成的m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。或称为一个基，用B表示。称基矩阵的列为基向量，用Pj表示(j=1,2,m)。涕缸转娠沙守坝擅概颅刀勘疫柜疮歉丙稿食赐罗仿怜沂控负州治荆叹译掏线性规划与单纯形法线性规划与单纯形法基变量：与基向量Pj相对应的m个变量xj称为基

23、变量，其余的m-n个变量为非基变量。基解：令所有非基变量等于零，对m个基变量所求的解对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。基变量是基变量是x3,x4,x5非基变量是非基变量是x1,x2令非基变量令非基变量x1=x2=0，得到一个基解，得到一个基解 x3=8，x4=12，x5=36热匹槛蹋糊饰堡豌响乱湛黄板聚秒柔浙微阮低映坐资量弧纽汲呕弹弊譬磐线性规划与单纯形法线性规划与单纯形法基可行解：满足非负性约束的基解称为基可行解。可行基：对应于基可行解的基，称为可行基。最优基：最优解对应的基矩阵，称为最优基。非可行解可行解基

24、解军瓶讳贷塔社冀烙唬纪涸炬吠铀显躁梢取袁弊哉靠齐诛托灰唯疙软额堰翻线性规划与单纯形法线性规划与单纯形法定定理理1 1.若线性规划问题存在可行域，则其可行域一定是凸集凸集。定定理理2 2.线性规划问题的基可行解对应可行域的顶点顶点。定定理理3 3.若可行域有界，线性规划的目标函数一定可以在可行域的顶点顶点上达到最优。二、线性规划的基本定理二、线性规划的基本定理 绸踌巳劝租沏钉放磨毯古爸茧揩值畏痉贯睡悼迎牛男勺砷缄征逾岩悯毙逢线性规划与单纯形法线性规划与单纯形法线线性性规规划划问问题题可可以以有有无无数数个个可可行行解解，最最优优解解只只可可能能在在顶顶点点上上达达到到，而而有有限限个个顶顶点点对

25、对应应的的是是基基可可行行解解，故故只只要在有限个基可行解中寻求最优解即可。要在有限个基可行解中寻求最优解即可。从从一一个个顶顶点点出出发发找找到到一一个个可可行行基基，得得到到一一组组基基可可行行解解，拿目标函数做尺度衡量一下看是否最优。拿目标函数做尺度衡量一下看是否最优。如如若若不不是是，则则向向邻邻近近的的顶顶点点转转移移，换换一一个个基基再再行行求求解解、检检验验，如如此此迭迭代代循循环环目目标标值值逐逐步步改改善善，直直至至求求得得最最优优解。解。三、线性规划的解题思路三、线性规划的解题思路 捉进舷肆耘揩隐察俄贸渣凰菊寻识慌砧辈朵檄阐艺砰疡箩蔚炳尧斌贫梢酸线性规划与单纯形法线性规划与

26、单纯形法例maxz=2x1+3x2St:X1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 Xi=0 1 2 1 0 0 A=4 0 0 1 0 0 4 0 0 1令非基变量X4=X5=0，则可解出X1=4,X2=3,X3=-2所以得出基解 X1=（4，2，-2，0，0），但由于X30,所以X2是可行解，相应的B2为可行基若用以上方法可枚举出此线性规划问题的基可行解分别为X3(4,0,4,0,12)，X4(0,3,2,16,0)，X5（2，3，0，8，0）和X6（4，2，0，0，4），将这些解代入目标函数，可知X6可使得Z最大，所以X6为最优解楚订煮墒傲爹存宰烃听猫菌樱都嫡

27、糜徊掠如载本羔银约筑霓砚涪啥给搪凰线性规划与单纯形法线性规划与单纯形法2 单纯形法单纯形法单纯形法的思路：先找到一个初始可行基，求出这个基可行解，然后判断该基可行解是否为最优解，若是最优解，则求解结束，若不是，则进行基变换，得到一个新的可行基，再进行判断该基可行解是否为最优解。每次基变换后的目标函数不断增大，一直到找到最优解为止。邑束号作倡瞻舆雏瘩疆憋套兹幽劈裔扮押糊爸霸其韦迭蹈序隘愧莹疹泌连线性规划与单纯形法线性规划与单纯形法单纯形法基本思路是否最优解求最优目标函数值是基变换,迭代否确定初始可行解焊董秧谁谚敌箕样槛够丁蜀巾勘背称词滦英道凄惫蚌腕骸胖慨指墙希姥摧线性规划与单纯形法线性规划与单纯

28、形法2.1单纯形法的原理例：maxz=2X1+3X2+0X3+0X4+0X5 st X1+2X2+X3=8 4X1+X4=16 4X2+X5=12 Xj 0系数子矩阵 1 2 1 0 0A=（P1 P2 P3 P4 P5）=4 0 01 0 0 4 0 0 1初始可行基 1 0 0 B1=0 1 0 0 0 1（1）所以：X3=8-X1-2X2 X4=16-4X1 X5=12-4X2将此代入目标函数将此代入目标函数Z=2X1+3X2，令非基变量等于，令非基变量等于0，则得到一个基可行解则得到一个基可行解X0=（0 0 8 16 12），目标函数），目标函数值等于值等于0。但是从目标函数可知，因

29、。但是从目标函数可知，因X1，X2的价值系的价值系数均大于数均大于0，当，当X1或或X2由非基变量变成基变量时，目由非基变量变成基变量时，目标函数就会增加，所以此解并非最优解。标函数就会增加，所以此解并非最优解。随筐趴布硝臀制焉惭裕市丙么宰釜裕颇腔孽进辗贤劳徊侣瞩权装躺究老册线性规划与单纯形法线性规划与单纯形法将x2换入，x2换入后，需从X3,X4,X5中换出一个变量，并保证所有变量非负X3=8-2X2 X4=16X5=12-4X2当X2增大时，要满足X3，X4，X5 0，所以x2的最大只能取3，且此时x5为换出变量（2）基变换 新基变量为（X3，X4，X2），得X3=2-X1+0.5X5X4

30、=16-4X1X2=3-0.25X5代入目标函数得Z=9+2X1-0.75X5因为x1的系数为正，依然不是最优解，换入x1，再经过迭代最后的最优解（4 2 0 0 4）走载兄员洱橙驮拧斟打耽料廊僻牛攀订勉漆爵陵哇滓涟恿苦敬披荷菲梆僧线性规划与单纯形法线性规划与单纯形法2.2单纯形法求解单纯形法求解（1）初始基可行解的确定）初始基可行解的确定a 直接观察法直接观察法b 构造法构造法形式，加松弛变量形式，加松弛变量形式形式,减松弛变量后加人工变量（具体求解要用大减松弛变量后加人工变量（具体求解要用大法或二阶段法）法或二阶段法）目的目的:使初始可行基为单位阵使初始可行基为单位阵,令非基变量等于零令非

31、基变量等于零,因为因为b0,b0,即可以得到初始基可行解即可以得到初始基可行解.罗管诧赂痉谅豁酿着凡绅颤朴连命幼地犊检触赢辑媳颂粤镭适内腔逞览闻线性规划与单纯形法线性规划与单纯形法（2）最优性检验与解的判别）最优性检验与解的判别四种情况四种情况:唯一最优解唯一最优解无穷多最优解无穷多最优解无界解无界解无可行解无可行解攫糕刹疟画幌涅纺尹府偶糟舱停特烧盔硒铸绣懈灰担耻炽噬第薛孕醛裂零线性规划与单纯形法线性规划与单纯形法一般情况下一般情况下,经过迭代后经过迭代后z0j面簇豆荔低郊酌匹芦闸源灵炽疤惧患胸鼻韵嘛茧晦涸惨种瓤巧匣祭奶郭娜线性规划与单纯形法线性规划与单纯形法对于对于 a.最优解的判别定理最优

32、解的判别定理:若若 为对应于基为对应于基B的一个基可行解的一个基可行解,且对于一切且对于一切j=m+1,n有有j j0,0,则则 为最优解为最优解.称称j j为为检验数检验数.伐闷井迭色汰贞挠晌碾袋堂需池住锹或碌侧讽赁送剔疽悬需龄即浆秦痹宗线性规划与单纯形法线性规划与单纯形法证明证明:因对一切非基变量的角下标因对一切非基变量的角下标j，均有均有00，显然，对于任一可行解，显然，对于任一可行解均有均有zzzz0 0,但基本可行解但基本可行解 能使能使等式成立，故为最优解等式成立，故为最优解拿姚蓟名尖舅桓拾乐巍奉哉乒峪池熙胜至霞赣民骆抉冤律吠淆箩两摩涝愉线性规划与单纯形法线性规划与单纯形法b.无穷

33、多最优解的判别定理无穷多最优解的判别定理:若若 为一个基可行解为一个基可行解,且对于一切且对于一切j=m+1,n有有j j0,0,又存在某个非基变量的检验数又存在某个非基变量的检验数m+km+k=0,=0,则线性规划问题有无穷多最优解则线性规划问题有无穷多最优解账懈痪精径目勘封届罗阑催枪韵习碟租绪侧席钵丛卯己挫藤车驾江摔莉疾线性规划与单纯形法线性规划与单纯形法c.无界解（无有限最优解）判别定理无界解（无有限最优解）判别定理若若为一基可行解，有一个为一基可行解，有一个m+km+k，并且对，并且对i=1,2,i=1,2,m,m有有a ai,m+ki,m+k0,0,那么该线性规划问题具有无界解（无最

34、那么该线性规划问题具有无界解（无最优解）优解）痴捷竟蛇熬橇吨飞哲傀劣诣蜡趋足统网瞒羞责顶氰赛瞄辗酬每驮俗勾虽使线性规划与单纯形法线性规划与单纯形法d.无可行解无可行解约束条件相互矛盾，可行域为空集约束条件相互矛盾，可行域为空集最终计算表中人工变量仍然为基变量最终计算表中人工变量仍然为基变量瞧嵌春苫陀雅肢凳薯卒墅倘扶苟菱渡靠返抗蔬褥产昧戎陵朋枉勤吮贝鼻绚线性规划与单纯形法线性规划与单纯形法（3）基变换）基变换当初始基可行解不是最优解及不能判别无界时当初始基可行解不是最优解及不能判别无界时,需要需要找一个新的基可行解找一个新的基可行解,具体是从原可行解基中换一个具体是从原可行解基中换一个列向量列向

35、量,得到一个新的可行基得到一个新的可行基,称为基变换称为基变换.基变换的关键是如何选择换入变量和换出变量这两个基变换的关键是如何选择换入变量和换出变量这两个问题问题.(原原则和和原原则)a.a.换入入变量：当量：当j0时取取j中最大的所中最大的所对应的非基的非基变量量x xk k。b.b.换出出变量：量：=b=bi i/a/aikik(a(aikik0)0)中最小的所中最小的所对应的的x xl l为换出出变量。量。经过基基变换得到的解是基可行解得到的解是基可行解,目目标函数函数值增加增加厩佰狰踩毒雕澡诊歼限都颂椭某柑瘸症迁近尚态躺捂所撼优炔莹淘用荔封线性规划与单纯形法线性规划与单纯形法（4）迭

36、代运算）迭代运算将将xk和和xl进行对换，即把进行对换，即把Pk变为单位列向量取代变为单位列向量取代Pl,可可通过系数矩阵的增广矩阵的初等变换来实现通过系数矩阵的增广矩阵的初等变换来实现将增广矩阵的第将增广矩阵的第l行除以行除以alk将将k列除列除alk变换为变换为1以外，其他都变成以外，其他都变成0。alk称之为主元素，称之为主元素，k列成为主元列，列成为主元列，l行称为主远行。行称为主远行。塌吁娥每被栅乒塔邑闸品顷敌倦澈答裕皖鸯纹讨究桂乃氧庙毡邓粳芜免圭线性规划与单纯形法线性规划与单纯形法2.3 单纯形表单纯形表，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。CjC1C2CjCn

37、比值CBXBbx1x2xjxnCB1xB1b1a11a12a1ja1n1CB2xB2b2a21a22a2ja2n2CBnxBnbmam1am2amjamnm检验数j-Z12jn藩丛朋锭杏箭痈偶蚌毡匣枣踊落鲍轧假淡望渣腿芭耶谦翘手围瞩访矢朗般线性规划与单纯形法线性规划与单纯形法将线性规划问题化成标准型。找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数j=Cj-CBPj，若所有j0，则问题已得到最优解，停止计算，否则转入下步。在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。根据maxjj0=k原则，确定xk为换入

38、变量(进基变量)，再按规则计算：=minbi/aik|aik0=bl/aik 确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第 步。单纯形法的计算步骤单纯形法的计算步骤 染屎雌皮作谅灰隅死地亮构筛彰歼平兰卧媒氨咱顷哨冗闽屁簧汉睬神鲁涂线性规划与单纯形法线性规划与单纯形法 maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 单纯形法计算举例单纯形法计算举例Cj比值CBXBb检验数jx

39、1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9拉筑卫号近祟翁娶苫忧赐包毕搂石蹄痈拘售辕砂慰蜕泌羡赴伎根待止页瘫线性规划与单纯形法线性规划与单纯形法检验数j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9糊找超劲夸矽题关醉互赵恐比苦瘦皇磷茶狞倪捍腺坪谷蚊骸脏光锹眠外惧线性规划与单纯形法线性规划与单纯形法Cj比值CBXBb检验数j

40、x1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最优解最优解:X*=(4,6,4,0,0)T，Z*=42量沫韧常桔箱坞拌伏曰考砰矫懂民照学抖为谢环始右针芥描唯疆湘懈机磐线性规划与单纯形法线性规划与单纯形法最优基 Cj35000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/203x14100-2/31/3检验数j-42000-1/2-1x3x2x1最优基的逆最优基的逆 最优基和最优

41、基的逆最优基和最优基的逆朔俞呻砖盾爱确屿聊戌勘翔停粒徽捉坛容筛队湍黔吵恼隐绪峨逞连重军馅线性规划与单纯形法线性规划与单纯形法又例又例Max z=2x1+3x2 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2,x3,x4,x50 此问题的最优解为此问题的最优解为:x1*=4,x2*=2,x5*=4,x3*=x4*=x1*=0,z*=2 4+3 2=14例Max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1,x2 0枢寥筛侗腹剥寝室捏都艇饿畅芬恢烽驱闷为再演挑溪贞率澄闲迂囊皆曹榆线性规划与单纯形法线性规划与单纯形法例如例如maxZ=3x

42、1+2 x2 -2x1+x2 2 x1-3 x2 3 x1,x2 0标准化标准化 maxZ=3x1+2 x2-2x1+x2+x3 =2 x1-3 x2 +x4=3 x1,x2,x3,x4 0Cj比值CBXBb检验数jx1x2x3x432002-211031-301x3x40003200-3检验数j80-512x3x103-31-301-90110-3此时，检验数2=11 0，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，无界值不存在，有进基变量但无离基变量。撤镭泛吻种篓净逮肚柴冕吱呆佣文诺唯性肆缺枢哦搽苟揽枯疲灯豪眉吭韶线性规划与单纯形法线性规划与单纯形法用单纯形法解题时，需

43、要有一个单位矩阵作为初始基。当约束条件都是“”时，加入松弛变量就形成了初始基。但实际存在“”或“”型的约束，没有现成的单位矩阵。采用人造基的办法：采用人造基的办法：人工构造单位矩阵人工构造单位矩阵人工构造单位矩阵人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于人工变量是在等式中人为加进的，只有它等于0时，约束条件时，约束条件才是它本来的意义。才是它本来的意义。处理方法有两种：处理方法有两种：大大M 法法两

44、阶段法两阶段法3.单纯形法的进一步讨论倍己轮柬絮讽剁苯蔬惺遵舒涨涣揖犀冰讽名物白艳牙寡疾射筒拳谱涧稽治线性规划与单纯形法线性规划与单纯形法没有单位矩阵，不符合构造初始基的条件，需加入人工变量。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为-M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。大大M法法 例如例如 maxZ=3x1-x2-2 x3 3x1+2 x2-3 x3=6 x1 -2 x2+x3

45、=4 x1,x2,x3 0肠蔚拼砚渣疗病迂蛾边拴狂涧乎柔皮嚷脐疲蜘均戌未舱绥孕占孝述游著扯线性规划与单纯形法线性规划与单纯形法按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4,x5 的辅助问题如下：的辅助问题如下：maxZ=3x1-x2 -2 x3-M x4-M x5 3x1+2 x2-3 x3 +x4 =6 x1 -2 x2+x3 +x5=4 x1,x2,x3,x4,x5 0Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-210100-2-2M-13+4M-10Mx4x5-M-M24榔镶莲爱轩兼惠喘邹格夕蠢圃催低瞪易铰滥粗丸她爪廷戌煤痰撩

46、凰吊桌桌线性规划与单纯形法线性规划与单纯形法Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00 x4x5-M-M24检验数j212/3-11/3020-8/32-1/310-1-4M/31+2M-3-8M/30 x1x53-M-1检验数j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2恤鱼兼腾禽储粳拘歇哑醉誊蝶颤勾悄卫丢发帅濒栓瓷庄耻臭馁菌贩橇舒久线性规划与单纯形法线性规划与单纯形法用计算机处理数据时，只能用很大的数代替用计算机处理数据时，只能用很大的数代替M,可能造可能

47、造成计算机上的错误，故多采用两阶段法。成计算机上的错误，故多采用两阶段法。第一阶段：第一阶段：在原线性规划问题中加入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型：两阶段法两阶段法叉氦指检狸京盾赔遵于滇野值曾亮考目奥氟葛蓟缅够显腆鹃溢鼓舀冲脚睛线性规划与单纯形法线性规划与单纯形法 对上述模型求解（单纯形法），若对上述模型求解（单纯形法），若W=0,W=0,说明问题存在基本可行解，可以进行说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停第二个阶段；否则，原问题无可行解，停止运算。止运算。第二阶段：在第一阶段的最终表中，第二阶段：在第一阶段的最终表中，去掉

48、人工变量，将目标函数的系数换成原去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。的初始表（用单纯形法计算）。咖起炔牛摔拣府锗聊怪踪灵齿茅椅镊杖桨贴找玖愁僚跺灯贱峨崇呻忘松洞线性规划与单纯形法线性规划与单纯形法单纯形法补遗进基变量相持：单纯形法运算过程中，同时出现多个相同的j最大。在符合要求的j(目标为max：j0，min：j0)中，选取下下标标最最小小的非基变量为换入变量；离基变量相持：单纯形法运算过程中，同时出现多个相同的最小值。继续迭代，便有基变量为0，称这种情况为退化解退化解。选取其中下标最大的基变量

49、做为换出变量。多重最优解：最优单纯形表中，存在非基变量的检验数j=0。让这个非基变量进基，继续迭代，得另一个最优解。无界解：大于0的检验数中，若某个k所对应的系数列向量Pk0，则解无界。无可行解：最终表中存在人工变量人工变量是基变量。排躁祥治零杠欺姐络胀氛萎劫坯氟绪敷沪屡漳另乃扑贰楼您绵包汝脸攻恍线性规划与单纯形法线性规划与单纯形法 4.线性规划的运用线性规划的运用解解 先看有多少种裁料方案，再进行组合和选择。方案：先看有多少种裁料方案，再进行组合和选择。方案：套裁下料套裁下料 现要做一百套钢管现要做一百套钢管,每套要长为每套要长为2.9m、2.1m和和1.5m的钢管各的钢管各一根。已知原料长

50、一根。已知原料长7.4m，问应如何下料，使用的原料最省。，问应如何下料，使用的原料最省。设用方案设用方案,分分别裁原料钢管别裁原料钢管x1,x2,.x5根根,则：则：Min z=0 x1+0.1 x2+0.2 x3+0.3x4+0.8x5x1+2x2 +x4 =100 2x3+2x4+x5=100 3x1+x2+2x3 +x5=100 x1,x2,x3,x4,x5 0咏拎交供兄泵簿启酪炉馏姥芽玲真的拧坪把吮腥跌蛇越冈香黔病喻瑶颜掸线性规划与单纯形法线性规划与单纯形法 例例 某工厂要用三种原材料某工厂要用三种原材料C,P,HC,P,H混合调配出三种不同规格的产品混合调配出三种不同规格的产品A,B