《线性规划求解方法法.ppt》由会员分享，可在线阅读，更多相关《线性规划求解方法法.ppt（33页珍藏版）》请在金锄头文库上搜索。
1、线线 性性 规规 划划授课教师授课教师：王淑华运筹学课件运筹学课件可可行行区区域域与与基基本本可可行行解解 |图解法|可行域的几何结构|基本可行解与基本定理返回运筹学课件运筹学课件线性规划图图 解解 法法运筹学课件运筹学课件线性规划例例运筹学课件运筹学课件线性规划运筹学课件运筹学课件线性规划注注 释释线性规划解的的情况线性规划解的的情况：|可行域是空集（问题无解）可行域是空集（问题无解）|无界无界| 最最优优解解存存在在且且唯唯一一，则则一一定定在在可可行域顶点上达到行域顶点上达到|存存在在无无穷穷多多最最优优解解，一一定定存存在在可可行域的顶点是最优解行域的顶点是最优解注注：如如果果线线性性
2、规规划划有有最最优优解解且且最最优优解解不不唯唯一一，则则一一定定有有无无穷穷多多个个最最优解优解返回运筹学课件运筹学课件线性规划可可行行域域的的几几何何结结构构|基本假设|凸集|可行域的凸性返回运筹学课件运筹学课件线性规划基基 本本 假假 设设返回运筹学课件运筹学课件线性规划凸凸 集集返回运筹学课件运筹学课件线性规划问问 题题返回运筹学课件运筹学课件线性规划基本基本可行可行解与解与基本基本定理定理|定义|基本定理|问题返回运筹学课件运筹学课件线性规划返回运筹学课件运筹学课件线性规划基基本本可可行行解解定定义义基基本本可可行行解解定定义义运筹学课件运筹学课件线性规划返回运筹学课件运筹学课件线性
3、规划基基 本本 定定 理理返回运筹学课件运筹学课件线性规划说说明明返回运筹学课件运筹学课件线性规划 图图解法解法的灵的灵敏度敏度分析分析 灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。例:Maxz=50x1+100x2s.t.x1+x2300(A)2x1+x2400(B)x2250(C)x10(D)x20(E)得到最优解：x1=50，x2=250最优目标值z=27500x1x2z=20000=50x1+100x2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x
4、2CBADE|线性规划的标准化：线性规划的标准化：引入松驰变量（含义是资源的剩余量） 例 中引入 s1， s2， s3 模型化为目标函数：Maxz=50x1+100x2+0s1+0s2+0s3约束条件：s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s30对于最优解 x1=50x2=250，s1=0s2=50s3=0说明：生产50单位产品和250单位产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。灵敏度分析1.目标函数中的系数目标函数中的系数 ci 的灵敏度分析的灵敏度分析： ci 的变化只影响目标函数等值线的斜率的变化
5、只影响目标函数等值线的斜率，目标函数目标函数 z = 50 x1 + 100 x2 在在 250= x2 (x2 = z 斜率为斜率为0 ) 300 = x1 + x2 (x2 = -x1 + z 斜率为斜率为 -1 )之间时，原最之间时，原最优解优解 x1 = 50，x2 = 100 仍是最优解。仍是最优解。|一般情况：一般情况： z = c1 x1 + c2 x2 写成斜截式写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目标函数等值线的斜率为目标函数等值线的斜率为 - (c1 / c2 ) ， 当当 -1 - (c1 / c2 ) 0 （*） 时，原时，原最优解仍
6、是最优解。最优解仍是最优解。|假设产品假设产品的利润的利润100元不变，即元不变，即 c2 = 100，代到式（，代到式（*）并整理得）并整理得 0 c1 100 |假设产品假设产品的利润的利润 50 元不变，即元不变，即 c1 = 50 ，代到式（，代到式（*）并整理得）并整理得 50 c2 + |假若产品假若产品、的利润均改变，则可直接的利润均改变，则可直接用式（用式（*）来判断。）来判断。|假设产品假设产品、的利润分别为的利润分别为60元、元、55元，元，则则 - 2 - (60 / 55) - 1 那么，最优解为那么，最优解为 300= x1 + x2 和和 400 = 2 x1 +
7、x2 的交点的交点 x1 = 100，x2 = 200 。3 图图解法解法的灵的灵敏度敏度分析分析|假设产品假设产品的利润的利润100元不变，即元不变，即 c2 = 100，代到式（代到式（*）并整理得）并整理得 0 c1 100 |假设产品假设产品的利润的利润 50 元不变，即元不变，即 c1 = 50 ，代到式（代到式（*）并整理得）并整理得 50 c2 + |假若产品假若产品、的利润均改变，则可直接的利润均改变，则可直接用式（用式（*）来判断。）来判断。|假设产品假设产品、的利润分别为的利润分别为60元、元、55元，元，则则 - 2 - (60 / 55) - 1 那么，最优解为那么，最
8、优解为 300= x1 + x2 和和 400 = 2 x1 + x2 的交点的交点 x1 = 100，x2 =200。3 图图解法解法的灵的灵敏度敏度分析分析2约束条件中右边系数约束条件中右边系数 bj 的灵敏度分析的灵敏度分析 当约束条件中右边系数当约束条件中右边系数 bj 变化时，线性规划的可行变化时，线性规划的可行域发生变化，可能引起最优解的变化。域发生变化，可能引起最优解的变化。 考虑上考虑上例例的情况：的情况： 假设设备台时增加假设设备台时增加10个台时，即个台时，即 b1变化为变化为310，这，这时可行域扩大时可行域扩大，最优解为最优解为 x2 = 250 和和 x1 + x2
9、= 310 的交点的交点 x1 = 60，x2 = 250 。变化后的总利润变化后的总利润 - 变化前的总利润变化前的总利润 = 增加的利润增加的利润 (5060+ 100250) - (50 50+100 250) = 500 ， 500 / 10 = 50 元元 说明在一定范围内每增加（减少）说明在一定范围内每增加（减少）1个台时的个台时的设备能力就可增加（减少）设备能力就可增加（减少）50元利润，称为该约束元利润，称为该约束条件的条件的对偶价格对偶价格。假设原料假设原料 A 增加增加10 千克时，即千克时，即 b2变化为变化为410，这时可行域扩大，这时可行域扩大，但但最优解仍为最优解仍
10、为 x2 = 250 和和 x1 + x2 = 300 的的交点交点 x1 = 50，x2 = 250 。此变化对总利润无此变化对总利润无影响，该约束条件的对偶价格为影响，该约束条件的对偶价格为 0 。 解释：解释：原最优解没有把原料原最优解没有把原料 A 用尽，有用尽，有50千克的剩余，因此增加千克的剩余，因此增加10千克值增加了库存，千克值增加了库存，而不会增加利润。而不会增加利润。 在一定范围内，当约束条件右边常数增加在一定范围内，当约束条件右边常数增加1个单位时个单位时 （1）若约束条件的对偶价格大于）若约束条件的对偶价格大于0，则其最优，则其最优目标函数值得到改善（变好）；目标函数值
11、得到改善（变好）； （2）若约束条件的对偶价格小于）若约束条件的对偶价格小于0，则其最优，则其最优目标函数值受到影响（变坏）；目标函数值受到影响（变坏）； （3）若约束条件的对偶价格等于）若约束条件的对偶价格等于0，则最优目，则最优目标函数值不变。标函数值不变。注释1.对偶价格对偶价格表示其对应的资源每增加一个单位，将改进改进多少个单位的最优值。2.当约束条件中的常数项增加一个单位时，最优目标函数值增加增加的数量称之为影子价格影子价格。在求目标函数最大时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，所以影子价格等于对偶价格；在求目标函数值最小时，改进的数量就是减少的
12、数量，所以影子价格即为负的对偶价格。单纯单纯形法形法单单纯纯形形法法的的基基本本思思路路：从可行域中某一个顶点(即基本可行解)开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点(基本可行解)为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。算算 例例运筹学课件运筹学课件线性规划初初 始始 单单 纯纯 形形 表表运筹学课件运筹学课件线性规划迭迭 代代 1运筹学课件运筹学课件线性规划迭迭 代代 2运筹学课件运筹学课件线性规划返回运筹学课件运筹学课件线性规划计计算算软软件件|LinGo|matlab返回|Matlab求解线性规划基本模型函数调用格式：
