运筹学第二章(7页).doc

《运筹学第二章(7页).doc》由会员分享，可在线阅读，更多相关《运筹学第二章(7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-运筹学第二章-第 7 页第 2 次课 2学时 本次课教学重点： 线型规划模型有关概念、图解法求解线型规划模型本次课教学难点： 线型规划模型有关概念、各种解的情况分析本次课教学内容：第二章线性规划的图解法第一节问题的提出一、引例例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元问题：工厂应分别生产多少单位、产品才能使工厂获利最多？解：分析问题后可得数学模型： 目标函数： 约束条件： 这是一个线性规划模型，因为：目标函数是线性函数，

2、约束条件是一些线性的等式或不等式。若目标函数是非线性函数，或约束条件中有非线性的等式或不等式，则这样的问题称为非线性规划。二、 一般建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量，每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件三、 线性规划模型的一般形式目标函数： 约束条件： 第二节图 解 法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。 下面通过例1详细讲解其方法一、 有关概念1、 可行解：满足约束条件的解2、

3、 可行域：全体可行解的集合。3、 最优解：使得目标函数值达到最优的可行解。4、 凸集5、 松弛变量二、 图解法求解线性规划例1. 目标函数： 约束条件： 解：(1)分别取决策变量为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0x2x1X10X1=0（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2300x1+x2=3001001002002x1+x24002x1+x2=400300200300400100100x22

4、50x2=250200300200300（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1（4）目标函数，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE综上得到

5、最优解： 最优目标值 三、线性规划问题解的情况1、如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解； 2、无穷多个最优解。若将例1 中的目标函数变为，则线段BC 上的所有点都代表了最优解； 3、 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件； 4、 无可行解。若在例1 的数学模型中再增加一个约束条件，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。例2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，

6、各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？解： 目标函数： 约束条件： 采用图解法。如下图：100200300400500600100200300400600500x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200x1 x2 Q得Q点坐标（250，100）为最优解。教学组织1、课堂讲授2、多媒体

7、图形演示作业布置： 1、P23.2（1，2）第 3 次课 2学时 本次课教学重点： 化标准型、灵敏度分析本次课教学难点： 灵敏度分析本次课教学内容：第三节图解法的灵敏度分析一、线性规划模型的标准形式目标函数： 约束条件： 标准形式四个特点：1目标最大化； 2约束为等式； 3决策变量均非负； 4右端项非负。二、线性规划模型标准化1.极小化目标函数的问题： 设目标函数为 (可以)令 z -f ， 则该极小化问题与下面的极大化问题有相同的最优解，即 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即 Min f Max z2、约束条件不是等式的问题： （1）设约束条

8、件为 可以引进一个新的变量 ，使它等于约束右边与左边之差显然， 也具有非负约束，即，这时新的约束条件成为 （2）当约束条件为 时， 类似地令 显然， 也具有非负约束，即，这时新的约束条件成为3.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 ，则把该等式约束两端同时乘以-1，得到： 为了使约束由不等式成为等式而引进的变量,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。例：将以下线性规划问题转化为标准形式 约束条件： x1

9、 , x2 , x3 0解：首先,将目标函数转换成极大化： 令 次考虑约束，有2个不等式约束，引进松弛变量。 三个约束条件的右端值为负，在等式两边同时乘-1。通过以上变换，可以得到以下标准形式的线性规划问题： 约束条件： 4. 变量无符号限制的问题 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj- xj” 其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。三、 灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）变化时，对最优解产生的影响。1目标函数

10、中的系数 的灵敏度分析 的变化只影响目标函数等值线的斜率，不影响可行域。考虑例1的情况，目标函数 在 (斜率为0 ) 到 ( 斜率为 )之间时，原最优解 仍是最优解。一般情况：；写成斜截式 目标函数等值线的斜率为 ， 当 时，原最优解仍是最优解。假设产品的利润100元不变，即，代到式（*）并整理得假设产品的利润 50 元不变，即 ，代到式（*）并整理得假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则 那么，最优解为 和 的交点 。2 约束条件中右边系数的灵敏度分析 当约束条件中右边系数变化时，线性规划的可行域发生变化，可能引起最优解的变化。 考虑例1的

11、情况： （1）假设设备台时增加10个台时，即变化为310，这时可行域扩大，最优解为 和 的交点 变化后的总利润 变化前的总利润 = 增加的利润(5060+ 100250) (50 50+100 250) = 500 ，500 / 10 = 50 元 说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。 （2）假设原料 A 增加10 千克时，即 变化为410，这时可行域扩大，但最优解仍为 和 的交点 。此变化对总利润无影响，该约束条件的对偶价格为 0 。 解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。 在一定范围内，当约束条件右边常数增加1个单位时 （1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）； （2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）； （3）若约束条件的对偶价格等于0，则最优目标函数值不变。教学组织1、 课堂讲授2、 多媒体教学3、课堂练习作业布置： 1、P24.3（2，3），42、P25.6