武汉工程大学 运筹学02-线性规划的图解法

12.1线性规划问题及其数学模型(1)线性规划问题建模例1、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源设备原料1原料2AB122101单位利润50100300台时400kg250kg2建立线性规划模型的步骤：1）根据管理层的要求确定决策目标和收集相关数据。2）确定要做出的决策，引入决策变量。3）确定对这些决策的约束条件和目标函数。3例2合理配料问题求：最低成本的原料混合方案原料ABＣ每单位成本14102261253171642538每单位添加剂中维生12148素最低含量4例3、运输问题工厂123库存仓121350222430库334210需求401535运输单价求：运输费用最小的运输方案。5(2)线性规划问题的特征：决策变量：每个问题都用一组决策变量(X1…Xn)表示，这组决策变量的值都代表一个具体方案。目标函数：衡量决策方案优劣的函数，它是决策变量的线性函数，根据问题不同，目标函数实现最大化或最小化。约束条件：分为两类1）函数约束，一组决策变量的线性函数=/=/=一个给定的数（右端项）。2）决策变量约束。具备以上三个要素的问题就称为线性规划问题。60,,,,,,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标函数约束条件(3)线性规划模型一般形式7隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,cj为确定值82.2线性规划问题的图解法20,.1XbAXtsCXZMinMax定义1：满足约束(2)的X=(X1…Xn)称为线性规划问题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。9x1x2z=20000=50x1+100x2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500ⅠⅡ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元10直观结论若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；若线性规划问题有最优解，则唯一最优解对应于可行域的一个顶点；无穷多个最优解对应于可行域的一条边；若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；若线性规划问题无可行解，则可行域必为空集。112.3线性规划问题的标准形式0,,,,,,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标函数约束条件(1)线性规划模型一般形式12价值系数决策变量技术系数右端常数0,b,,bbxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMaxm21nmnmnmmnnnnnn0,,,.21221122222121112121112211(2)线性规划模型标准形式13简记形式njxmibxatsxcZMaxjinjjijnjjj,,2,10,,2,1.11(3)线性规划模型其它形式14矩阵形式0.XbAXtsCXZMaxncccC21mnmmnnaaaaaaaaaA212222111211nxxxX21价值向量决策向量系数矩阵mbbbb21右端向量15ncccC21nxxxX21价值向量决策向量mbbbb21右端向量向量形式0.1XbxPtsCXZMaxjnjjnjjjjaaaP21列向量16对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:(4)一般型向标准型的转化目标函数目标函数为极小化约束条件分两种情况：大于零和小于零决策变量可能存在小于零的情况17(4)一般型向标准型的转化SLP的特点（1）目标函数取极大（2）所有约束条件均由等式表示（3）所有决策变量取非负值（4）每一约束的右端常数(资源向量的分量)均为非负值线性规划问题标准形式的特点181.极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+…+cnxn则可以令z＝-f，该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-…-cnxn但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Minf＝-Maxz192、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+…+ainxn≤bi可以引进一个新的变量s，使它等于约束右边与左边之差s=bi–(ai1x1+ai2x2+…+ainxn)显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+s=bi变量s称为松弛变量20MaxZ=40X1+50X2X1+2X2≤30s.t3X1+2X2≤60引入松弛变量X3、X4、X52X2≤24X1,X20MaxZ=40X1+50X2+0X3+0X4+0X5X1+2X2+X3＝30s.t3X1+2X2+X4＝602X2+X5＝24X1,…,X5021当约束条件为ai1x1+ai2x2+…+ainxn≥bi时，类似地令s=(ai1x1+ai2x2+…+ainxn)-bi显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn-s=bi变量s称为剩余变量22MaxZ=2X1+5X2+6X3+8X44X1+6X2+X3+2X4≥12s.tX1+X2+7X3+5X4≥142X2+X3+3X4≥8X1,…,X40引入剩余变量：X5、X6、X7MaxZ=2X1+5X2+6X3+8X44X1+6X2+X3+2X4-X5＝12s.tX1+X2+7X3+5X4-X6＝142X2+X3+3X4-X7＝8X1,…,X70233.决策变量如果某个变量的约束条件为jjlx或者jjlx可令jjjlxy或者jjjxly代入原问题如果某个变量为自由变量（无非负限制），则可令0,jjjjjxxxxx0jl且24X1+X25s.t-6X110X20令X1'=X1+6-6+6X1+610+60X1'16X1'+X211s.tX1'16X1',X20253X1+2X28s.tX1-4X214X20,X1无限制令X1=X1'-X1''3X1'-3X1+2X28s.tX1'-X1-4X214X1',X1,X2026例：将线性规划模型MinZ=-X1+2X2-3X3X1+X2+X37s.tX1-X2+X32X1，X20，X3无限制化为标准型四个方面考虑272.4图解法的灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。2.4.1目标函数中的系数ci的灵敏度分析考虑例1的情况，ci的变化只影响目标函数等值线的斜率，目标函数z=50x1+100x2在z=x2(x2=z斜率为0)到z=x1+x2(x2=-x1+z斜率为-1)之间时，原最优解x1=50，x2=100仍是最优解。一般情况：z=c1x1+c2x2写成斜截式x2=-(c1/c2)x1+z/c2目标函数等值线的斜率为-(c1/c2)，当-1-(c1/c2)0（*）时，原最优解仍是最优解。28假设产品Ⅱ的利润100元不变，即c2=100，代到式（*）并整理得0c1100假设产品Ⅰ的利润50元不变，即c1=50，代到式（*）并整理得50c2+假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则-2-(60/55)-1那么，最优解为z=x1+x2和z=2x1+x2的交点x1=100，x2=200。292.4.2约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况：假设设备台时增加10个台时，即b1变化为310，这时可行域扩大，最优解为x2=250和x1+x2=310的交点x1=60，x2=250。变化后的总利润-变化前的总利润=增加的利润(50×60+100×250)-(50×50+100×250)=500，500/10=50元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。30假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为x2=250和x1+x2=300的交点x1=50，x2=250。此变化对总利润无影响，该约束条件的对偶价格为0。解释：原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。