线性规划与图解法要点

运筹学(OperationsResearch)文理学院姜华2015-3Page2办公室：1C213手机：[phone]邮箱：[e-mail]绪论（1）运筹学简述（2）运筹学的主要内容（3）本课程的教材及参考书本章主要内容：Page4运筹学简述运筹学（OperationsResearch）系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(ManagementScience)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术。Page5运筹学简述运筹学的历史“运作研究(OperationalResearch)小组”:解决复杂的战略和战术问题。例如：1.如何合理运用雷达有效地对付德军德空袭2.对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；3.在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。Page6运筹学的主要内容数学规划（线性规划、目标规划、整数规划、动态规划等）图论存储论排队论对策论排序与统筹方法决策分析Page7本课程的教材及参考书选用教材《运筹学》(本科版)清华大学出版社参考教材《运筹学教程》胡运权主编（第2版）清华出版社《管理运筹学》韩伯棠主编（第2版）高等教育出版社《运筹学基础及应用》胡运权主编哈工大出版先修课：高等数学，线性代数，基础概率Chapter1线性规划(LinearProgramming)LP的数学模型图解法单纯形法单纯形法的进一步讨论－人工变量法LP模型的应用本章主要内容：Page9线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）Page10线性规划问题的数学模型例1.1如图所示，如何截取x使铁皮所围成的容积最大？xaxxav220dxdv0)2()2()2(22xaxxa6axPage11线性规划问题的数学模型例1.2某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？设备产品ABCD利润（元）甲21402乙22043有效台时1281612Page12线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2x1+3x2x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12Page13线性规划问题的数学模型2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？Page14线性规划问题的数学模型00)()((min)max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz目标函数：约束条件：3.线性规划数学模型的一般形式)21(j0)21(i)(Z(min)max11nxmbxaxcjnjijijnjjj简写为：Page15线性规划问题的数学模型矩阵形式：mnmnaaaaA1111max(min)()b0ZCXAXX其中：)(21ncccCnxxX11mbbbPage16线性规划问题的数学模型4.线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj,,2,1,,2,1,0.max11特点：(1)目标函数求最大值(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。Page17线性规划问题的数学模型（2）如何化标准形式目标函数的转换如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。jjxczmin也就是：令，可得到上式。zzmaxjjzzcx即1）若存在取值无约束的变量，可令其中：jxjjjxxx0,jjxx变量的变换Page18线性规划问题的数学模型约束方程的转换：由不等式转换为等式。ijijbxa0iniinjijxbxxa称为松弛变量ijijbxa0iniinjijxbxxa称为剩余变量2）变量的变换可令，显然0jxjjxx0jxPage19线性规划问题的数学模型例1.3将下列线性规划问题化为标准形式,0,523247532min321321321321321无约束xxxxxxxxxxxxxxxZ用替换，且解:（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以33xx3x0,33xxPage20线性规划问题的数学模型(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式；(3)第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z′=-z,得到maxz′=-z，即当z达到最小值时z′达到最大值，反之亦然;Page21线性规划问题的数学模型0,,,,,5)(252)(7)(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准形式如下：Page22线性规划问题的数学模型5.线性规划问题的解)3(,,2,1,0)2(),,2,1(.)1(max11njxmibxatsxcZjnjijijnjjjLP问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。Page23线性规划问题的数学模型可行解：满足约束条件②、③的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。Page24图解法线性规划问题的求解方法一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况——只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。Page25图解法maxZ=2X1+X2X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.5用图解法求解线性规划问题Page26图解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X220=2X1+X217.2=2X1+X211=2X1+X2Lo：0=2X1+X2（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值maxZ=17.2可行域maxZ=2X1+X2X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0Page27图解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2maxZ（3.8，4）34.2=3X1+5.7X2蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域Page28图解法006346321212121xxxxxxxx、246x1x2246无界解(无最优解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZx1x2O10203040102030405050无可行解(即无最优解)0,050305.140221212121xxxxxxxxmaxZ=3x1+4x2例1.7Page30图解法学习要点：1.通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）2.作图的关键有三点：(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动Page31LP问题的解的特点1.若LP问题存在可行域，则其可行域一定为凸集。凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。凸集凸集不是凸集顶点2.若LP问题有最优解，则一定在可行域的顶点取得。Page32练习12121212maxZ2x3xx2x84x164x12x,x0用图解法求线性规划的最优解。Page33练习将下列线性规划问题化为标准形式123123123123123m23329342225,0,0axZxxxxxxxxxxxxxxx