第一章第一章 线性规划与单纯形法线性规划与单纯形法本章重点内容本章重点内容线性规划模型与解的主要概念线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划的单纯形法，线性规划多解分析线性规划的应用线性规划的应用建模建模昨苹杖桩钢奏豁胁廓都刃辽斑巍罚右逞苛物示乍酝予腮享沼氦吠卢汉牲植线性规划与单纯形方法线性规划与单纯形方法1第一节第一节 线性规划问题及数学模型线性规划问题及数学模型一、实例二、线性规划问题（LP问题）的共同特征三、两变量线性规划问题的图解法四、线性规划问题的标准型五、标准型LP问题解的概念六、可行解、基解和基可行解举例怂砷捞磷榴皆塞聘鳖古戳互槛臆破庶翠仙答目玖雌宿倚脾疙椭沉纷滦琼埃线性规划与单纯形方法线性规划与单纯形方法2一、实例一、实例例例1 1 生产计划问题生产计划问题Step 1:Step 1:明确问题，设定决策变量明确问题，设定决策变量 设设I I、IIII两种产品的产量分别为两种产品的产量分别为x1,x2 。Step 2: Step 2: 确定约束条件确定约束条件产品 I II 资源限量设备 1 2 8台时原料A 4 0 16公斤原料B 0 4 12公斤 利润 2 3问应如何安排生产问应如何安排生产使该厂获利最多使该厂获利最多？抠刚漫胺芦送娱艇晤赵娠伙鄂悍共焙哲炔摹凛彩禽掠重娶陨掇恐寄恐完肮线性规划与单纯形方法线性规划与单纯形方法3说明：说明：OBJ 表示表示Objective;s.t. 表示表示Subjectto Step 3: Step 3: 给出目标函数给出目标函数Step 4: Step 4: 整理数学模型整理数学模型城殴墩崎炯鲁管寇者傻毁椿梗耶润约晾匹走隶卢豺烦结卒骚惦姿还杯似断线性规划与单纯形方法线性规划与单纯形方法4例例2现要做现要做100套钢架，每套需套钢架，每套需2.9米、米、2.1米和米和1.5米的元钢各一根。米的元钢各一根。已知原料长已知原料长7.4米，问如何下料，使余料最少？米，问如何下料，使余料最少？设设I,II,III,IV,V分别代表五种不同的原料用量方案分别代表五种不同的原料用量方案,x1,x2,x3,x4,x5分别代表采用各方案下料的元钢的根数。分别代表采用各方案下料的元钢的根数。方案方案根数根数2.9米米2.1米米1.5米米合计合计余料余料I x11037.40IIx22017.30.1IIIx30227.20.2IVx41207.10.3Vx50136.60.8解：解：访留番党荐扮贵具裁灿佛褂伤褂竣驼涧缚更剿樱娘评唇龟露挝伊掉哄迂谢线性规划与单纯形方法线性规划与单纯形方法5端涟剩哩壁石狡谆靳假菩叙蛤房藤萍傅湿曾沙侥樊锈版渣盔淮踢勺侦熏旧线性规划与单纯形方法线性规划与单纯形方法6LP(Linear Programming)LP(Linear Programming)是数学规划的一个重要分支，数是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：题中的一个：（1 1）当资源给定时，要求完成的任务最多；）当资源给定时，要求完成的任务最多；（2 2）当任务给定时，要求为完成任务所消耗的资源最少。）当任务给定时，要求为完成任务所消耗的资源最少。 若上述问题的目标若上述问题的目标约束都能表达成变量的线性关系，约束都能表达成变量的线性关系，则这类优化问题称则这类优化问题称LPLP问题。问题。 LP LP是一种解决在线性约束条件下追求最大或最小的线性是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。目标函数的方法。勘析怖傻棺伟鸥常瞬娥癸递京捂思睛种芒寥冗等阎表榨二列咕涸矮泣启霹线性规划与单纯形方法线性规划与单纯形方法7 目标函数目标函数用决策变量的用决策变量的线性函数线性函数来表示。按问题的不来表示。按问题的不同，要求目标函数实现同，要求目标函数实现最大化和最小化最大化和最小化。 每一个问题变量都用一组每一个问题变量都用一组决策变量决策变量（x1,x2,xn）表示某一方案，这组决策变量的值代表一个具体方案，表示某一方案，这组决策变量的值代表一个具体方案，这些变量是这些变量是非负且连续非负且连续的。的。 存在一定的存在一定的约束条件约束条件，这些约束条件可以用一组，这些约束条件可以用一组线性线性等式等式或或线性不等式线性不等式来表示。来表示。结论：结论：线性规划是研究在一组线性不等式或线性等式约束线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。下，使得某一线性目标函数取最大或最小的极值问题。二、线性规划问题（二、线性规划问题（LPLP问题）的共同特征问题）的共同特征泵斋汪壳棘撼嫁耙宜梨篙啊宁驴纂镜扮刺昔埃屈劝找烬迫张塑钙绝儒力牢线性规划与单纯形方法线性规划与单纯形方法8Max(Min)Z=c1x1+c2x2+cnxn (1)a11x1+a12x2+a1nxn(=, ) b1 a21x1+a22x2+a2nxn(=, ) b2s.t. (2) am1x1+am2x2+amnxn(=, ) bm xj0,j=1,2,，n(3)(1)目标函数；目标函数；(2)约束条件；约束条件；(3)决策变量非负决策变量非负n变量个数；变量个数；m约束行数；约束行数；cj价值系数；价值系数；bi右端项或限额系数；右端项或限额系数；aij技术系数；技术系数；xj决策变量决策变量线性规划模型的一般形式为：线性规划模型的一般形式为：违分胖吸疗斗梆昌侍沃狱哪配搭换茄骗眶疥窿墅战慢狙臆雏获请澎鳖馒贪线性规划与单纯形方法线性规划与单纯形方法9线性规划模型的紧缩形式线性规划模型的紧缩形式n变量个数；变量个数；m约束行数；约束行数；cj价值系数；价值系数；bi右端项或限额系数；右端项或限额系数；aij技术系数；技术系数；xj决策变量决策变量孽演惭巴铬僵坪出妥谜哨骤鉴益货周总习歼暂菌乙碳工忆歹伙增炸浆使方线性规划与单纯形方法线性规划与单纯形方法10练习题：是否为线性规划模型？练习题：是否为线性规划模型？嗽床韭宦腕则署彭两疗涅卉昔涡笼序击冀漫雅蛤栅卒匆店芒淫随和牢顷枣线性规划与单纯形方法线性规划与单纯形方法111.1.线性不等式的几何意义线性不等式的几何意义 半平面半平面1)1)作出作出LPLP问题的可行域问题的可行域2)2)作出目标函数的等值线作出目标函数的等值线3)3)移动等值线到可行域边界得到最优点移动等值线到可行域边界得到最优点2.2.图解法步骤图解法步骤三、两变量线性规划问题的三、两变量线性规划问题的图解法图解法熊唆帘审标赠钡栽截州杠光瀑居挖配洪蔑嘉侧壮昭蛰尉晕皿枝直例斤血登线性规划与单纯形方法线性规划与单纯形方法124x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30例例1Q2(4,2)Z=2x1+3x2做目标函数做目标函数2x1+3x2的等值线，的等值线，与阴影部分的边界相交于与阴影部分的边界相交于Q2(4,2)点，表明最优生产计划点，表明最优生产计划为：生产为：生产I产品产品4件，生产件，生产II产产品品2件。件。Q3砧朵蚀洋轩归淄苹函霉凰哆沈朽憨驻佳凉奈拄绅奉掂位齿碌钱合认踌堪蠕线性规划与单纯形方法线性规划与单纯形方法13目标函数目标函数z=ax1+bx2的值的值递增递增的方向与系数的方向与系数a、b有关有关a0, b0a0X1X2a0, b0, b0z=ax1+bx2目标函数等值线：目标函数等值线：ax1+bx2=k移项移项x2=-a/bx1+k/b目标函数等值线在纵目标函数等值线在纵轴上的截距为轴上的截距为k/b熏詹癣衙圾凌氧囊蹄服景双卞硕幅硅毫妊积胜忙盘哥笆鳞誉烽泥李惮劫独线性规划与单纯形方法线性规划与单纯形方法14例例4 4Z=36翰烁艇跪募省虽析绚晒缔未芯辆抖音骋鸿中秋冠距葵免谷诅买嘿廖燎渗碳线性规划与单纯形方法线性规划与单纯形方法15例例 用图解法求解线性规划问题用图解法求解线性规划问题4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+4x2当当Z值由小变大时，将与值由小变大时，将与Q2Q3重合重合Q2Q3上任意一点都是最优解上任意一点都是最优解有有无穷多最优解无穷多最优解（多重解）（多重解）Q3(2,3)蔽抹哭闺涌证平匈钝阻韭烬胃捌圆霉彰讫慢咯貌秽喀谱洲御骇朽狄籍绅逾线性规划与单纯形方法线性规划与单纯形方法16例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界无界解无界解（ “无无有限最优解有限最优解”或或“最优解无界最优解无界”）约束条件过分宽松约束条件过分宽松注意：注意：可行域不闭合不一定就会出现可行域不闭合不一定就会出现无界解，这要看目标函数的性质。无界解，这要看目标函数的性质。若目标函数是若目标函数是minmin，则有最优解。无，则有最优解。无论有无最优解，一定有可行解。论有无最优解，一定有可行解。x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00砚创惋蛋滚急尺倾松拦挥醉朋样史凛钾砚彰旬腻堂屋俏遮麓邻澜坦黍壮摸线性规划与单纯形方法线性规划与单纯形方法17例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界唯一最优解唯一最优解X*=(1,0)1,0)，对应于点，对应于点Ax2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00罗蚁氧慰群沃眼初宦哀戏羔酚纵帖督逛元烯剩旬券绎漏惰栖飞复帘技渊容线性规划与单纯形方法线性规划与单纯形方法18例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界无穷多最优解无穷多最优解对应于点对应于点B沿着沿着OB向右上向右上方发出的射线上的所有点方发出的射线上的所有点x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00凳将烃闯厅篙搔崖掺批垦措拟寿下磋披比寐堪赡盏钢颇菌福七黑接取揭懒线性规划与单纯形方法线性规划与单纯形方法19例例 用图解法求解线性规划问题用图解法求解线性规划问题无可行解无可行解（可行域为空）（可行域为空）x14x1=164x2=12x1+2x2=8x248Q14Q430-2-2x1+x2=4无最优解无最优解宜瘁鼻忆拿饥囚蛆祷癸氮格倘锄湍勋重捐馏靳承牟痉笔诌应蛔歌构鬃荐赚线性规划与单纯形方法线性规划与单纯形方法203.3.图解法的作用图解法的作用 能解决少量问题能解决少量问题 揭示了线性规划问题的若干规律揭示了线性规划问题的若干规律解的类型解的类型可行域类型可行域类型唯一最优解唯一最优解无穷多最优解无穷多最优解最优解无界最优解无界（无有限最优解）（无有限最优解）无解无解（不存在可行域）（不存在可行域）非空有界非空有界无界无界空集空集规律规律1 1：攘雨摧哲骡婶钻拦叮测沙擂捞蓬锨雇治队贤梆唆各淤脸麻怜骇燎崭哭唱薛线性规划与单纯形方法线性规划与单纯形方法21规律规律2 2：线性规划问题的可行域为线性规划问题的可行域为凸集凸集线性规划问题凸集的顶点个数是有限的线性规划问题凸集的顶点个数是有限的最优解可在凸集的某顶点处达到最优解可在凸集的某顶点处达到 灵园漫掷岭币花旭焰虫恭来恨轿膊附驭观本狗逻洁宴悸守囚腰裁俱噪释汗线性规划与单纯形方法线性规划与单纯形方法22 小结：图解法的基本步骤：小结：图解法的基本步骤：1在直角坐标系作出可行域在直角坐标系作出可行域S的区域的区域（一般是一个凸多边形）（一般是一个凸多边形）2令目标函数值取一个已知的常数令目标函数值取一个已知的常数k，作等值线：，作等值线：c1x1+c2x2=k3对于对于max问题，让目标函数值问题，让目标函数值k由小变大，即让等值线进由小变大，即让等值线进行平移，若它与可行域行平移，若它与可行域S最后交于一个点（一般是最后交于一个点（一般是S的一个顶的一个顶点），则该点就是所求的最优点，若与点），则该点就是所求的最优点，若与S的一条边界重合，的一条边界重合，此时边界线上的点均是最优点此时边界线上的点均是最优点4将最优点所在的两条边界线所代表的方程联立求解，即将最优点所在的两条边界线所代表的方程联立求解，即得得最优解最优解X*，把最优解，把最优解X*带入目标函数，得带入目标函数，得最优值最优值Z*=CX*注意：若是求目标函数最小值，等值线向反方向移动注意：若是求目标函数最小值，等值线向反方向移动糯猖棚酶战蛙牵耐枯拽瞄涯抠某藻炔排十筏袁盾待阎返托膏怎设苦洒冀酱线性规划与单纯形方法线性规划与单纯形方法23四、线性规划问题的标准型四、线性规划问题的标准型1.1.标准型标准型 （1）目标函数）目标函数：max（2）约束条件：）约束条件：等式等式（3）变量约束：）变量约束：非负非负xj 0（4）资源限量：）资源限量：非负非负bi 0标准型的构成要素标准型的构成要素卿确巡幸民褐替啃近形染馒最嚎渴掐咯倡揣奈桅傀绦售角玲赎屎衡蝴晕郸线性规划与单纯形方法线性规划与单纯形方法242.2.线性规划标准型的紧缩形式线性规划标准型的紧缩形式玻擎哦臼娄奋锥伞戏据秒傲钢炳坡先沾蛀纺昨力旗桅停讶塘阑夯胺狞访要线性规划与单纯形方法线性规划与单纯形方法253.3.线性规划标准型的向量和矩阵表达式线性规划标准型的向量和矩阵表达式矩阵式矩阵式:MaxZ=CTXs.t.AX=bX0 n向量式向量式: : MaxZ=cjxjj=1ns.t.Pjxj=bj=1xj 0,j=1,2,.,n缓盾晒炕驴淘酝肝杠坐罪节另疑姓苹绽淌剑拽卑沽唱诫描图卯睬照凤历迈线性规划与单纯形方法线性规划与单纯形方法264.所有所有LP问题均可化为标准型问题均可化为标准型（1）最小转换成最大）最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*糕俘唯呛葡填白扔朵凄荫休践捉逸撤郁搅腮哗腊砧巧攀蘑旭简趁釉暑澈厉线性规划与单纯形方法线性规划与单纯形方法27（2）不等式约束条件转换成等式约束条件）不等式约束条件转换成等式约束条件（3）变量约束转换）变量约束转换（4）把）把bi 0转换成转换成bi 0课斋垢盏廖衡豫掺吭旭逊浴旋娄凰篆微精蒙腹池里桥溜藐猎略嘲迄几向拯线性规划与单纯形方法线性规划与单纯形方法28例例5 5 化标准型化标准型可化为可化为1.1.处理决策变量处理决策变量2.2.处理约束条件右端处理约束条件右端 常数项常数项3.3.约束条件不等式约束条件不等式4.4.处理目标函数处理目标函数稳韶侮冻树诸绳爬娄咋泻详唤拈旬失汤沁描便扔勺范矽彬玖扒参绅继慌狙线性规划与单纯形方法线性规划与单纯形方法29例例6 6 化标准型化标准型1.1.处理决策变量处理决策变量2.2.处理约束条件右端处理约束条件右端 常数项常数项3.3.约束条件不等式约束条件不等式4.4.处理目标函数处理目标函数呼淳莉意狈粱纱去耪望尉布邯避轮恋东技此虐班奸蛛讶构凿汕旺杨苯训固线性规划与单纯形方法线性规划与单纯形方法30MaxZ=x1+2x2+3x4-3x5+0x6+0x7s.t.x1-x2+x4-x5+x6=7x1+x2+x4- x5- x7=2-3x1-x2+3x4-3x5=5 x20, xj0,j=1,4,5,6,7MaxZ=x1+2x2+3(x4-x5)+0x6+0x7s.t.x1-x2+(x4-x5)+x6=7x1+x2+(x4- x5)- x7=2-3x1-x2+3(x4-x5)=5 x20, xj0,j=1,4,5,6,7最终结果最终结果中间结果中间结果鸿穗哼亚核干傅前选弹仕班肘争摇抬诽琵菌伪墙雏岔察闪挡镐另微炎挑鸥线性规划与单纯形方法线性规划与单纯形方法31课堂练习课堂练习卸从泳诈白摘谆酵嘿砍摄畦灸禄蓝诫鲤皱私砒碱帅螺忠米倍靴歇事缎堰穗线性规划与单纯形方法线性规划与单纯形方法32五、标准型五、标准型LPLP问题解的概念问题解的概念函十节消蔡禹跋讳砾巷藩帜别部丹侈钓芯猪敷惜睹贰嘲彩初荫钳方聪铺眩线性规划与单纯形方法线性规划与单纯形方法33（1）（2）（3）约束系数矩阵：约束系数矩阵：x1x2x3x4x5例：例：铆挣所利皆胃楔廊跑葡彼说粘旁迭枚墒咎略嫡刻各物疚朋摊皇眨落窒狂衙线性规划与单纯形方法线性规划与单纯形方法34约束系数矩阵：约束系数矩阵：可能可能的基矩阵是的基矩阵是A中任意三个列的组合，共中任意三个列的组合，共10个。个。苍让往筑谩凑硅联薛案豪沾每板戚堆绅叶庚巫凿始寂厢惑世沿村惹移辗礼线性规划与单纯形方法线性规划与单纯形方法35令令B=(P1,P2,Pm)且且|B| 0，则称，则称Pj (j=1,2,m)为为基向量基向量。与基向量与基向量Pj对应的变量对应的变量xj称为称为基变量基变量，记为记为XB =(x1,x2,xm)T，其余的变量称为，其余的变量称为非基变量非基变量，记为，记为XN=(xm+1,xm+2,xn )T。镜湿它挖析爆肇罚昔横植霞歼脆提骄弓做浸茅送碟型纲川娃府巢琅稀舀鸳线性规划与单纯形方法线性规划与单纯形方法36奄掌缘玉际接塑荧趴骡纂衰同软绰枢检落屡夕诅逼褐昌蔫屹箱摇泽赎圈往线性规划与单纯形方法线性规划与单纯形方法37线跪钒僧牌顺谢媳槽宦氓幼账献威柳暴蓉讲辛翠才斑杠惩烃闻骆无珍晶涝线性规划与单纯形方法线性规划与单纯形方法38B1=(P1,P2)：基基令：令：XB1=(x1,x2)x1=0， x2=2X=(0, 2,0,0)XB1=(0,2)对应于对应于B1的基解为的基解为这歹明迁曙羔蜕雹孙艺惜警误付茧专握牵防霹矗顾啥堆崩李枯尿晋第堂误线性规划与单纯形方法线性规划与单纯形方法39线性规划标准型问题解的关系线性规划标准型问题解的关系约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解清与欠碎堪姿憋灭裂欺诌椽岔霹肝观屁鲸巧膀葵氦蒂地赠屏募傣入完髓砌线性规划与单纯形方法线性规划与单纯形方法40例例7Max Z=2x1+3x2s.t.x1+2x284x1164x212x1, x2 0六、可行解、基解和基可行解举例六、可行解、基解和基可行解举例非基非基变量变量基变量基变量图中的点图中的点x4,x5x1=4x2=3x3=-2 A基解基解x3,x5x1=2x2=3x4=8B基可行解基可行解x3,x4x1=4x2=2x5=4C基可行解基可行解x2,x4x1=4x3=4x5=12D基可行解基可行解x2,x3x1=8x4=-16x5=12E基解基解x1,x5x2=3x3=2x4=16F基可行解基可行解x1,x3x2=4x4=16x5=-4 G基解基解x1,x2x3=8x4=16x5=12H基可行解基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH标准型标准型棕伏袄舀肝晶盛篙镣登仍墙涨对籍英遏又添吧湘崎俞宫泌尼纫檬绑辟肪围线性规划与单纯形方法线性规划与单纯形方法41例例8 8漳喳缕孩拟过捆炙戍焙泽春痔码硕盾懒抽吮敌收秧铂恼鸭寸碳拽很啊胀胶线性规划与单纯形方法线性规划与单纯形方法42第二节第二节 LP LP问题的基本理论问题的基本理论一、基本概念一、基本概念汝昏蜗貌筹象控擂姜寡墒蹋混凸铡默嫁殖拥液致斑赵乒瞄瞪遂急埠蔓味供线性规划与单纯形方法线性规划与单纯形方法43判断以下图形哪些是凸集，哪些不是凸集？判断以下图形哪些是凸集，哪些不是凸集？返回返回膨切厌屏惫仲芹槛貉杖贵存隆伸瓢施捏碳您渝蒂趴标冗骂蓑牧修婉表辫像线性规划与单纯形方法线性规划与单纯形方法44定理定理1 1 LPLP问题的可行域为一凸集问题的可行域为一凸集。二、基本定理二、基本定理歼沛傻维国萍隶崇雇伟药裂诫帝王腻傣竟钻珊埃峰梗汀峰袒篓苟梗匡钞苛线性规划与单纯形方法线性规划与单纯形方法45引理引理线性规划问题的可行解线性规划问题的可行解X=(x1,x2,xn)T是基可行解是基可行解的的充要条件为充要条件为X的正分量所对应的系数列向量是线性独立的。的正分量所对应的系数列向量是线性独立的。溜费孙吻严讹鱼痪爆立抖氦爽丙岭夫绅磺训悸准聋云揭通消搪兜飘炎嘘爪线性规划与单纯形方法线性规划与单纯形方法46定理定理2 2 线性规划问题的基可行解对应于可行域的顶点。线性规划问题的基可行解对应于可行域的顶点。（即：若（即：若X是是LP问题的可行解，则问题的可行解，则“X是是LP问题的基可行解问题的基可行解”等等价于价于“X是是LP问题可行域顶点问题可行域顶点”）设设X是基可行解，则其对应的向量组是基可行解，则其对应的向量组a1,a2, ,am线性无关线性无关(mm时，有时，有xj=xj(1)=xj(2)=0.技乏莉骂些瘪暇春舷噶椎痘师意垮懦侥授负大塞帝季粮敝辖栖波钓柯伴漏线性规划与单纯形方法线性规划与单纯形方法47求炽寓谰纱晦疥酸奎芥渺钳拨呸鸳四嗅桶琐问琅菇帛见堵哩昆快践神瞄空线性规划与单纯形方法线性规划与单纯形方法48篷牌市惭坷亭秤致少熟崭摄甲媒隅绎磨程希且墓远樱字眨颓摧导诡敞辫绍线性规划与单纯形方法线性规划与单纯形方法49迈膜滦瀑爱秽狡屑求抉八万噪果昭苗苫牺您瞪颅窥咎诸半卯块娶掇颠嘿上线性规划与单纯形方法线性规划与单纯形方法50定理定理3 3 若可行域有界，则若可行域有界，则LPLP问题的目标函数一定可以在其可问题的目标函数一定可以在其可行域的顶点上达到最优。行域的顶点上达到最优。引理引理若若S是有界凸集，则任何一点是有界凸集，则任何一点XS可表示为可表示为S的顶点的的顶点的凸组合。凸组合。稍饱深宪网眶碴氖亚织傲抉随疡型恶悯检丽凡膀捞句帜滇疡上媒凡觉昨泄线性规划与单纯形方法线性规划与单纯形方法51 线性规划问题的可行域是凸集线性规划问题的可行域是凸集( (定理定理1)1)；凸集的顶点对应；凸集的顶点对应于基可行解于基可行解( (定理定理2)2)，基可行解，基可行解( (顶点顶点) )的个数是有限的；若线的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到性规划有最优解，必在可行域某顶点上达到( (定理定理3)3)。因此。因此, ,我们我们可以在有限个基可行解中寻找最优解。可以在有限个基可行解中寻找最优解。 由线性代数知，对标准形由线性代数知，对标准形LP问题，用枚举法可以求出所有问题，用枚举法可以求出所有基解，再通过观察找出其中的可行解（基可行解），进而找基解，再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如出最优解。但如果变量和方程较多，比如m=50，n=100，所，所有基解有可能达有基解有可能达1029个，即使计算机每秒能求解个，即使计算机每秒能求解1亿个这样的亿个这样的方程组，也需要方程组，也需要30万亿年！因此，必须寻求有效的算法。万亿年！因此，必须寻求有效的算法。 为加快计算速度，算法必须具有两个功能，一是每得到一个为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是停止。二是若不是最优，要解，就来检验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。法。 卧蜡裸摈歌弹蒸名纤彤山羹馈榷偶珐帛孙茧匀树婶究炯饲从愤忍角吞畴绝线性规划与单纯形方法线性规划与单纯形方法52第三节第三节 单纯形法单纯形法基本思想基本思想检验解的检验解的最优性最优性结束结束Y旋转运算（消元运算）旋转运算（消元运算）确定另一个基本可行解确定另一个基本可行解N化化LP问题为标准型，问题为标准型，确定一个初始基本可行解确定一个初始基本可行解化化LP问题为标准型，从可行域的某问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代求得问题的最优解。其实质是逐步迭代（逼近）法。（逼近）法。刨铅直蜗幸锹奔革瞩制辞垣剑摩董拼怪凰潘寝炮詹塑秉腊饱镍东送跳蒜结线性规划与单纯形方法线性规划与单纯形方法53一、确定初始基可行解一、确定初始基可行解MaxZ=CXs.t.AX=bX0我们首先介绍求初始基可行解的方法。我们首先介绍求初始基可行解的方法。1.1.若给定问题标准化后（且若给定问题标准化后（且 ）系数矩阵）系数矩阵A A中存在中存在m m个线性无关个线性无关的单位列向量，则以这的单位列向量，则以这m m个单位列向量构成的单位子矩阵作为初始个单位列向量构成的单位子矩阵作为初始基基B B，则，则 ，其余，其余x xj j=0=0是基可行解。是基可行解。2.2.大大M M法（人工变量法）法（人工变量法）执峦步舞汾缮豪您从勤辱卤国盛腊猛柑银够胳鱼秉娘腹脂损洽炒魏釜设荆线性规划与单纯形方法线性规划与单纯形方法54以以x2为主元素为主元素以以x1为主元素为主元素例例2x1+x2+2x3=10(1)3x1+3x2+x3=6(2)x1+1/2x2+x3=5(1)0x1+3/2x2-2x3=-9(2)(1)/2,(2)-(1)3x1+0x2+5/3x3=8(1)0x1+x2-4/3x3=-6(2)(2)2/3,(1)-(2)/2二、旋转运算二、旋转运算制邓伴恍唤倚落楞紫绳逞私辣围瓦钻桓菇淖洲釉蔚厕牲猖寨怖仁田憋岸诬线性规划与单纯形方法线性规划与单纯形方法55三、检验数的意义三、检验数的意义结论：结论：如果如果LPLP问题通过单纯形法迭代到某步时，所有检验数问题通过单纯形法迭代到某步时，所有检验数0,0,则该则该LPLP问题已得到最优解。问题已得到最优解。MaxZ=CXs.t.AX=bX0若若cj-CBB-1Pj=j0,则则ZZ0,Z0即为最优解即为最优解. (基变量的检验数必为基变量的检验数必为0)令令A=(B,N),X=XB,C=(CB,CN)XN由由AX=b(B,N)XB=bBXB+NXN=bB-1BXB+B-1NXN=B-1bXNXB=B-1bB-1NXN(2)将将(2)式代入目标函数得式代入目标函数得Z=CX =(CB,CN)XB=CBXB+CNXN=CB (B-1b-B-1NXN)+CNXN XN=CBB-1b+(CN-CBB-1N)XN=Z0+(cj-CBB-1Pj)xjxj为非基变量为非基变量匹畴忿绳沤缅士嫂示怒忿云欧悯彩捡赔冀怪触潍罪肤息屋嘘悍析碘蝴剁斋线性规划与单纯形方法线性规划与单纯形方法56单纯形法举例单纯形法举例化为标准型化为标准型肃孟弧瑰悲媒煞约朔现备切样程言条映我河渡堪郑淮辈择扩匈皇楚柿澡游线性规划与单纯形方法线性规划与单纯形方法57约束方程的系数矩阵约束方程的系数矩阵对应于B的变量x3，x4，x5为基变量，（1）将（将（1）代入目标函数后得到）代入目标函数后得到z=0+2x1+3x2，令非基变量令非基变量x1=x2=0.得到得到z=0，及一个基可行解，及一个基可行解X(0)=(0,0,8,16,12)T霖郎履卑陈敷徽港遇讫帝郴钥凉屿袍和轻馅逃泄八寥兑危漫各绢沫漠臻换线性规划与单纯形方法线性规划与单纯形方法58x2=3，x5为换出变量为换出变量（3）将（将（3）代入目标函数后得到）代入目标函数后得到z=9+2x13/4x5，令非基变量令非基变量x1=x5=0.得到得到z=9，及一个基可行解，及一个基可行解X(1)=(0,3,2,16,0)T当将当将x2定为换入变量后定为换入变量后，必须从，必须从x3，x4，x5中中确定一个换出变量，并保证确定一个换出变量，并保证x3，x4，x50，当当x1=0时，由（时，由（1）式得到）式得到（2）用高斯消元法，将用高斯消元法，将x2的系数列向量变换为单位列向量，得到的系数列向量变换为单位列向量，得到颜软仔鸦罚厄溶椅饿酿居缆寸愤匙扦皱审欣哦赴喜拖蛤氦郑荷约蹈潭警粉线性规划与单纯形方法线性规划与单纯形方法59这时目标函数的表达式是这时目标函数的表达式是z=141.5x30.125x4，当将当将x1定为换入变量后定为换入变量后，继续利用上述方法，继续利用上述方法确定换出变量，继续迭代，再得到一个基可确定换出变量，继续迭代，再得到一个基可行解行解X(2)=(2,3,0,8,0)T再经过一次迭代，再得到一个基可行解再经过一次迭代，再得到一个基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+3x2Q3镰郁褒曙竞刹投融啪骏日斡欣椭煽谣装污蔷一经省襄砌嫂衰萎膀韭赤邯筏线性规划与单纯形方法线性规划与单纯形方法60对于线性规划问题对于线性规划问题：MaxZ=CTXAX=b，X0，可用如下三，可用如下三个判别定理来判别线性规划问题是否已经获得最优解或为无个判别定理来判别线性规划问题是否已经获得最优解或为无界解。界解。判别定理判别定理1 1设设X为线性规划的一个基可行解，且对于一为线性规划的一个基可行解，且对于一切切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性规为线性规划的最优解。划的最优解。判别定理判别定理2 2设设X为线性规划的一个基可行解，且对于一为线性规划的一个基可行解，且对于一切切jJ（J为非基变量的下标集）有为非基变量的下标集）有j 0，同时有某个，同时有某个非基变量的检验数非基变量的检验数k=0(kJ)，则该线性规划有无穷，则该线性规划有无穷多最优解。多最优解。判判别别定定理理3 3设设X为为线线性性规规划划的的一一个个基基可可行行解解，若若有有k0(kJ)，且且pk0，即即aik 0（i=1,m），则则该该线线性性规规划问题具有无界解（无最优解）。划问题具有无界解（无最优解）。听鸟羽务峙线柑榨甸秸卞赖所桥挨耽瞧更变宏瘫羡使姿坝弗到玄萍而耗养线性规划与单纯形方法线性规划与单纯形方法61一、步骤一、步骤Step1.化化LP问题为问题为标准型标准型, ,建立建立初始单纯形表初始单纯形表; ;Step2.若所有检验数若所有检验数0, ,则最优解已达到。则最优解已达到。 否则否则, ,计计算算 ,选取选取k 所对应的变量所对应的变量xk 为为换入变量换入变量（进基变量进基变量）; ;最大最大（检验数）规则（检验数）规则Step3.计算计算 , ,选取选取l 所对所对应的变量应的变量xl 为为换出变量换出变量（出基变量出基变量）; ;最小比值规则最小比值规则Step4.以以alk为主元素进行为主元素进行旋转运算旋转运算, ,转转Step2; ;第四节第四节 单纯形法的步骤单纯形法的步骤激傅毛盖掐从瓮硅抨版填晰申青女赊汐樱寥铭嫌颧抚硕腔级福孕汉沏挠仪线性规划与单纯形方法线性规划与单纯形方法62cj CB XB b x1x2 xmxm+1xnj基可行解：基可行解： x1=b1,x2=b2,xm=bm ,xm+1=xm+2=xn=01.1.初始单纯形表初始单纯形表c1c2cm cm+1cnc1x1 c2x2 cmxmb1 b2 bm100a1,m+1a1n010a2,m+1a2n 001am,m+1amn000m+1n-CBTB-1b就无堑将沪植搞椭疵彻亚羚放伟验粮食替迹赡植瞻插恢摹犬纶迄薄鲁掳貉线性规划与单纯形方法线性规划与单纯形方法63对于上述单纯形表：对于上述单纯形表：（1）一个基对应一个单纯形表，且单纯形表中必须有一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。一个初始单位基。（2）从单纯形表中，可立即得到一个基可行解：从单纯形表中，可立即得到一个基可行解： x1=b1,x2=b2,xm=bm ,xm+1=xm+2=xn=0（3）用检验数的计算公式很容易计算检验数，并可根用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解是否为最优解或线据三个判别定理判别上述基可行解是否为最优解或线性规划问题无最优解。性规划问题无最优解。归差蝴扒脑疡针派知疚血踊拼梨爬牧今旷钒攻烹抛曼碴玩桩傲抄与亥坪冶线性规划与单纯形方法线性规划与单纯形方法642.2.换入变量（换入变量（进基变量）的选择进基变量）的选择cj c1c2cm cm+1ckcnCB XB b x1x2 xmxm+1xkxnc1x1 c2x2 cmxmb1 b2 bm100a1,m+1a1k a1n010a2,m+1a2k a2n 001am,m+1amkamnj-CBTB-1b000m+1k n选取选取 所对应的变量所对应的变量xk 为换入变量。为换入变量。肉蘑住骇豌嫁潞送吵绅都夕汝叹鞘躁匀琶负茄陀犁击妈箭澈湃娇运看践没线性规划与单纯形方法线性规划与单纯形方法653.3.换出变量（换出变量（出基变量）的选择出基变量）的选择cj c1cl cm cm+1ckcnCB XB b x1xl xmxm+1xkxnc1x1 clxl cmxmb1 bl bm100a1,m+1a1k a1n 010al,m+1alk aln 001am,m+1amk amn1 l mj-CBTB-1b000m+1k n选取选取 所对应的变量所对应的变量xl 为换出变量。为换出变量。弦挺途侯痊窜鹰吴践渍捷合捕妈用胳杯珠非雹秃是笺琉蒜用睁寨憾淄严辗线性规划与单纯形方法线性规划与单纯形方法664.4.旋转运算旋转运算cj c1cl cm cm+1ckcn CB XB b x1xl xmxm+1xkxnc1x1 clxl cmxmb1 bl bm100a1,m+1a1k a1n 010al,m+1alk aln 001am,m+1amk amnjckxkbl/alk01/alk 0al,m+1/alk1aln/alk b11-a1k/alk 0a1,m+10a1nbm0-amk/alk1am,m+10amn越辱除孽育舀嘴仿羡膊吗噎缝柠烙斗记蘑脆毋服蔓瘪度曹痰黎桅镣萍迷寐线性规划与单纯形方法线性规划与单纯形方法67二、实例二、实例化为标准型化为标准型雄沃蒋公颐姿眶忱嫂噪漾姓墒禽刺馆墨度簇蝉抠溅渭苏康逝舍篷谐挣勤着线性规划与单纯形方法线性规划与单纯形方法68单纯形表算法单纯形表算法cjCB XB bx1x2x3x4x5j以以4为主元素进行旋为主元素进行旋转运算，转运算，x2为换入变为换入变量，量，x5为换出变量为换出变量cj23000CB XB bx1x2x3x4x50x3 0x4 3x221631010-1/2240010401001/4-j-92000-3/4以以11为主元素进行为主元素进行运算，运算，x1为换入变量，为换入变量，x3为换出变量为换出变量0x30x40x523000816121210040010040012300004-3德趾瓦工啊蓝辱狭微乎巷帮平撒时缄腮郧角唁棕拒唤工雷嫡惊冉粳巳部攫线性规划与单纯形方法线性规划与单纯形方法69cj23000CB XB bx1x2x3x4x52x1 0x4 3x22831010-1/2-00-412401001/412j-1300-201/4以以22为主元素进行运为主元素进行运算，算，x5为换入变量，为换入变量，x4为换出变量为换出变量cj23000CB XB bx1x2x3x4x52x1 0x5 3x24421001/4000-21/21011/2-1/80j-1400-3/2-1/80此时达到最优解：此时达到最优解：X*=(4,2)T,MaxZ=14。僳冗涯懊酚圆旅殴仓抹辩列桔驳糖蔬挂辙酥罚情卷飞妖巧就屑续帆蕉缄赎线性规划与单纯形方法线性规划与单纯形方法704x1=164x2=12x1+2x2=8x1x2484O三、单纯形表与图解法的对应关系三、单纯形表与图解法的对应关系X1=(0,0)T,Z1=0X2=(0,3)T,Z2=9X3=(2,3)T,Z3=13X4=(4,2)T,Z4=14Q1Q2QQ3基可行解基可行解 基可行解基可行解 迭代迭代 顶点顶点 相邻的顶点相邻的顶点迭代迭代 图解法：图解法：单纯形表算法：单纯形表算法：涟孕鼠冕暗版姿戊傲劲知铬辫扔沉妥悲洛塌谱荤丹蹭浪米社皖沉症卖基青线性规划与单纯形方法线性规划与单纯形方法71对于极小化问题，其最优解的判定定理和进基变量的选取和对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题刚好相反，如下所示：极大化问题刚好相反，如下所示：判别定理判别定理1 1 设设X为线性规划的一个基可行解，且对于为线性规划的一个基可行解，且对于一切一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性为线性规划的最优解。规划的最优解。判别定理判别定理2 2设设X为线性规划的一个基可行解，且对于一为线性规划的一个基可行解，且对于一切切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，同时有某个，同时有某个非基变量的检验数非基变量的检验数k=0(kJ)，则该线性规划有无穷，则该线性规划有无穷多最优解。多最优解。判判别别定定理理3 3设设X为为线线性性规规划划的的一一个个基基可可行行解解，若若有有k0(kJ)，且且pk0，即即aik 0（i=1,m），则则该该线线性性规规划问题具有无界解（无最优解）。划问题具有无界解（无最优解）。在进基可行解的转换过程中，进基变量的选取原则是：在进基可行解的转换过程中，进基变量的选取原则是：minj|j 0,而而k对应列向量对应列向量Pk0,则此则此LP问题有问题有无界解无界解.卜腔颗仲哑飘农臼揪驯蜒夜刮莫工案锻赣闽筏赊习沸拽纲汉掉烈靠滨因眷线性规划与单纯形方法线性规划与单纯形方法924.4.在最优表中出现某非基变量检验数为在最优表中出现某非基变量检验数为0 0（无穷多最优解）（无穷多最优解）拷拽绎质奠挪歪冲盟榆午春扁蛋一惰积象镊改暑悼椒镶咕廊皱避峰北穗邱线性规划与单纯形方法线性规划与单纯形方法93CBXBbx1x2x3x4x50x340012/3-1/34x260101/203x14100-2/31/3cj -Zj-360000-10x46003/21-1/24x2301-3/401/43x1810100cj -Zj-360000-1cj034000申渔源怪挂佐入侦铀栽溢现债岁婴笋够苏溅悉仇端瞳迸卸悍遥最捉需乃舜线性规划与单纯形方法线性规划与单纯形方法94例例1 1 某工厂要用三种原材料某工厂要用三种原材料D D、P P、H H混合调配出三种不同规格混合调配出三种不同规格的产品的产品A A、B B、C C。已知产品的规格要求、单价和原材料的供应。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？量、单价。该厂应如何安排生产使利润最大？产品产品名称名称规格要求规格要求单价单价(元元/kg）A原材料原材料D不少于不少于50%原材料原材料P不超过不超过25%50B原材料原材料D不少于不少于25%原材料原材料P不超过不超过50%35C不限不限25原材料原材料名称名称每天最多供每天最多供应量应量(kg)单价单价(元元/kg)D10065P10025H6035第六节第六节 应用举例应用举例解：解：设设A中中D、P、H的含量为的含量为x11、x12、x13B中中D、P、H的含量为的含量为x21、x22、x23 C中中D、P、H的含量为的含量为x31、x32、x33率孙埃处详偷职芽疆毖烃讯铂线眠悸端期柏撂伦助丑筷懂骗萤治翘昔固黔线性规划与单纯形方法线性规划与单纯形方法95用单纯形法计算得结果：每天生产用单纯形法计算得结果：每天生产A A产品产品200kg,200kg,分别需要原分别需要原料料:D:D为为100kg;P100kg;P为为50kg;H50kg;H为为50kg. 50kg. 总利润收入总利润收入Z Z=500=500元元/ /天天. .媚惭欠绘俗铂斌挡威昧窗搂茅罢颜羹邦缅序辐鸯辆瘪龄阶蹈侄苯轧毙告原线性规划与单纯形方法线性规划与单纯形方法96先考虑一月份的线性规划模型先考虑一月份的线性规划模型: :例例2 2熏丝趁吗属垄橇酗唇综问壮活疲氦妮饵融棱簧紊驱泣惠柠傻垄僚滴焙仙芹线性规划与单纯形方法线性规划与单纯形方法97 以一月份内各种设备的生产能力总和为分母以一月份内各种设备的生产能力总和为分母, ,生产产品所生产产品所需要的各类设备的总台时数为分子需要的各类设备的总台时数为分子, ,可计算出一月份的平均可计算出一月份的平均设备利用系数设备利用系数Z,Z,将将Z Z作为目标函数作为目标函数, ,可得下面的模型可得下面的模型: :绢掩痛廊坝永隐煽砒幕考栋诺馒盛衫邀如滇约诺给传女雁万越龚枢逞臀牺线性规划与单纯形方法线性规划与单纯形方法98 考虑二月份线性规划模型时考虑二月份线性规划模型时:(1):(1)从全年计划中减去一月份从全年计划中减去一月份已生产的数量已生产的数量;(2);(2)对批量小的产品对批量小的产品, ,如一月份已经安排较大如一月份已经安排较大产量的产量的, ,二月份将剩余部分安排生产二月份将剩余部分安排生产;(3);(3)保证第保证第4 4号产品在月号产品在月底前交货底前交货. . 这样这样, ,我们可以依我们可以依次对次对1212个月列出线性个月列出线性规划模型并求解规划模型并求解, ,再再根据具体情况对计算根据具体情况对计算结果进行必要调整。结果进行必要调整。哉悯旷佛倍筒撤比死代宏烙陀乘饶僻碌闭溶矽聂厌皮叭蛇哑快态碟恶戌狠线性规划与单纯形方法线性规划与单纯形方法99例例3 3 某部门在今后某部门在今后5 5年内连续给以下项目投资：年内连续给以下项目投资： 项目项目A A，第一年至第四年每年年初投资，次年末回收本利，第一年至第四年每年年初投资，次年末回收本利115%115%； 项目项目B B，第三年初投资，第五年末回收本利，第三年初投资，第五年末回收本利125%125%，最大投资额，最大投资额 不超过不超过4 4万元；万元； 项目项目C C，第二年初投资，第五年末回收本利，第二年初投资，第五年末回收本利140%140%，最大投资额，最大投资额 不超过不超过3 3万元；万元； 项目项目D D，五年内每年初可购买公债，当年末归还，并加利息，五年内每年初可购买公债，当年末归还，并加利息6%6%。 该部门现有资金该部门现有资金 10 10万元，问该如何确定投资方案，使第五年末万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？拥有的资金本利和最大？12345Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D蔬婉肝啸瓢聊真肘培轩暖溯啮吝闽甸刹磅籍赴译训纠放资棘站囱专窘碑七线性规划与单纯形方法线性规划与单纯形方法100第一年第一年第二年第二年第三年第三年第四年第四年第五年第五年斑丸艇磕罗崇继喊踏盛洽牙诚远霄淬拱枫巧树躇驶孤芬胁恰略场亚识动钦线性规划与单纯形方法线性规划与单纯形方法101彤硅速畜过屏茎拳莎谎乙彝颁沽床骡勿各羌搐殴辗丢裸棱罩牵看婚旺克桅线性规划与单纯形方法线性规划与单纯形方法102班次班次时间时间所需人数所需人数16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030例例4 4 某公交线路每天各时段内所需司乘人员数如下：某公交线路每天各时段内所需司乘人员数如下：设所有的司乘人员分别在各时段的开始上班，并连续工设所有的司乘人员分别在各时段的开始上班，并连续工作作8 8小时，问该公交线路至少需配备多少司乘人员。列出该小时，问该公交线路至少需配备多少司乘人员。列出该问题的线性规划模型。问题的线性规划模型。拍寞褐萍剧蛰驹村寂磊姜贯巢也问西京婉绚焊然慑仁苫鉴澡忘故碉敞伺砒线性规划与单纯形方法线性规划与单纯形方法103郑换细院蛋哎卵齿咆宇蘑赌揖烃直频豌巫睹氓陛茸殖舟问奴匿历阴廖碰见线性规划与单纯形方法线性规划与单纯形方法104