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