运筹学02线性规划图解法.pptx
1例2 合理配料问题求：最低成本的原料混合方案 原料 A B 每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每单位添加剂中维生 12 14 8 素最低含量第1页/共29页2例3、运输问题 工 厂 1 2 3 库存 仓 1 2 1 3 50 2 2 2 4 30 库 3 3 4 2 10 需求 40 15 35运输单价求：运输费用最小的运输方案。第2页/共29页3(2)线性规划问题的特征：l决策变量：每个问题都用一组决策变量(X1 Xn)表示，这组决策变量的值都代表一个具体方案。l目标函数：衡量决策方案优劣的函数，它是决策变量的线性函数，根据问题不同，目标函数实现最大化或最小化。l约束条件：分为两类1）函数约束，一组决策变量的线性函数=/=/=一个给定的数（右端项）。2）决策变量约束。具备以上三个要素的问题就称为 线性规划问题。第3页/共29页4目标函数约束条件(3)线性规划模型一般形式第4页/共29页5隐含的假设隐含的假设l比例性：决策变量变化引起目标的改变量与决策变量比例性：决策变量变化引起目标的改变量与决策变量改变量成正比改变量成正比l可加性：每个决策变量对目标和约束的影响独立于其可加性：每个决策变量对目标和约束的影响独立于其它变量它变量l连续性：每个决策变量取连续值连续性：每个决策变量取连续值l确定性：线性规划中的参数确定性：线性规划中的参数aij,bi,cj为确定值为确定值第5页/共29页62.2 线性规划问题的图解法线性规划问题的图解法定义1：满足约束(2)的X=(X1 Xn)称为线性规划问题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。第6页/共29页7x1x2z=20000=50 x1+100 x2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE例1.目标函数：Max z=50 x1+100 x2 约束条件：s.t.x1+x2 300 (A)2 x1+x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)得到最优解：x1=50，x2 =250 最优目标值 z =27500第7页/共29页8直观结论直观结论若线性规划问题有解，则可行域是一个凸多边若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；形（或凸多面体）；若线性规划问题有最优解，则若线性规划问题有最优解，则唯一最优解对应于可行域的一个顶点；唯一最优解对应于可行域的一个顶点；无穷多个最优解对应于可行域的一条边；无穷多个最优解对应于可行域的一条边；若线性规划问题有可行解，但无有限最优解，若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；则可行域必然是无界的；若线性规划问题无可行解，则可行域必为空集。若线性规划问题无可行解，则可行域必为空集。第8页/共29页92.3 2.3 线性规划问题的标准形式线性规划问题的标准形式目标函数约束条件(1)线性规划模型一般形式第9页/共29页10价值系数决策变量技术系数右端常数(2)线性规划模型标准形式第10页/共29页11简记形式(3)线性规划模型其它形式第11页/共29页12矩阵形式价值向量决策向量系数矩阵右端向量第12页/共29页13价值向量决策向量右端向量向量形式列向量第13页/共29页14对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:(4)一般型向标准型的转化l目标函数l目标函数为极小化l约束条件l分两种情况：大于零和小于零l决策变量l可能存在小于零的情况第14页/共29页15(4)一般型向标准型的转化SLP的特点n（1）目标函数取极大n（2）所有约束条件均由等式表示n（3）所有决策变量取非负值n（4）每一约束的右端常数(资源向量的分量)均为非负值线性规划问题标准形式的特点第15页/共29页161.极小化目标函数的问题：设目标函数为 Min f=c1x1+c2x2+cnxn 则可以令z-f，该极小化问题与下面的极大化问题有相同的最优解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f -Max z第16页/共29页172、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之差 s=bi (ai1 x1+ai2 x2+ain xn)显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi 变量 s 称为松弛变量第17页/共29页18lMax Z=40X1+50X2 X1+2X2 30 s.t 3X1+2X2 60 引入松弛变量X3、X4、X5 2X2 24 X1,X2 0lMax Z=40X1+50X2+0 X3+0 X4+0 X5 X1+2X2+X3 30 s.t 3X1+2X2+X4 60 2X2+X5 24 X1,X5 0第18页/共29页19当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi变量s称为剩余变量第19页/共29页20Max Z=2X1+5X2+6X3+8X4 4X1+6X2+X3+2X4 12 s.t X1+X2+7X3+5X4 14 2X2+X3+3X4 8 X1,X4 0引入剩余变量：X5、X6、X7Max Z=2X1+5X2+6X3+8X4 4X1+6X2+X3+2X4-X5 12 s.t X1+X2+7X3+5X4 -X6 14 2X2+X3+3X4 -X7 8 X1,X7 0第20页/共29页213.决策变量如果某个变量的约束条件为或者可令或者代入原问题如果某个变量为自由变量（无非负限制），则可令且第21页/共29页22 X1+X2 5s.t -6 X1 10 X20令 X1=X1+6-6+6 X1+6 10+6 0 X1 16 X1+X2 11s.t X1 16 X1,X2 0第22页/共29页23 3X1+2X2 8 s.t X1-4X2 14 X20,X1 无限制 令X1=X1-X1 3 X1-3 X1 +2X2 8 s.t X1-X1 -4X2 14 X1,X1,X2 0第23页/共29页24例：将线性规划模型 Min Z=-X1+2X2-3X3 X1+X2+X3 7 s.t X1-X2+X3 2 X1，X20，X3无限制 化为标准型四个方面考虑第24页/共29页252.4 2.4 图解法的灵敏度分析图解法的灵敏度分析 灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj 变化时，对最优解产生的影响。2.4.1 目标函数中的系数 ci 的灵敏度分析 考虑例1的情况，ci 的变化只影响目标函数等值线的斜率，目标函数 z=50 x1+100 x2 在 z=x2(x2=z 斜率为0)到 z=x1+x2 (x2=-x1+z 斜率为-1)之间时，原最优解 x1=50，x2=100 仍是最优解。n一般情况：z=c1 x1+c2 x2 写成斜截式 x2=-(c1/c2)x1+z/c2 目标函数等值线的斜率为 -(c1/c2)，当 -1 -(c1/c2)0 （*）时，原最优解仍是最优解。第25页/共29页26n假设产品的利润100元不变，即 c2=100，代到式（*）并整理得 0 c1 100 n假设产品的利润 50 元不变，即 c1=50，代到式（*）并整理得 50 c2 +n假若产品、的利润均改变，则可直接用式（*）来判断。n假设产品、的利润分别为60元、55元，则 -2 -(60/55)-1 那么，最优解为 z=x1+x2 和 z=2 x1+x2 的交点 x1=100，x2=200。第26页/共29页27 2.4.2 约束条件中右边系数 bj 的灵敏度分析 当约束条件中右边系数 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况：假设设备台时增加10个台时，即 b1变化为310，这时可行域扩大，最优解为 x2=250 和 x1+x2=310 的交点 x1=60，x2=250。变化后的总利润-变化前的总利润=增加的利润 (5060+100250)-(50 50+100 250)=500，500/10=50 元 说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。第27页/共29页28 假设原料 A 增加10 千克时，即 b2变化为410，这时可行域扩大，但最优解仍为 x2=250 和 x1+x2=300 的交点 x1=50，x2=250。此变化对总利润无影响，该约束条件的对偶价格为 0。解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时 （1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。第28页/共29页29感谢您的观看！第29页/共29页
