运筹学第二章.pdf

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

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

2、 约束条件：ts.30021 xx 400221 xx 2502x 0,021xx 这是一个 线性规划模型，因为：目标函数是线性函数，约束条件是一些线性的等式或不等式。若目标函数是非线性函数，或约束条件中有非线性的等式或不等式，则这样的问题称为非线性规划。二、一般建模过程 1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量).,(21nxxx，每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 三、线性规划模型的一般形式 目标函数：nnxcxcxcZMinMax.)(2211 约

3、束条件：ts.11212111),(.bxaxaxann 22222121),(.bxaxaxann mnmnmmbxaxaxa),(.2211 0,.,0,021nxxx 第二节 图 解 法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例 1 详细讲解其方法 一、有关概念 1、可行解：满足约束条件的解 2、可行域：全体可行解的集合。3、最优解：使得目标函数值达到最优的可行解。4、凸集 5、松弛变量 二、图解法求解线性规划 例 1.目标函数：2110050 xxZMax 约束条件：ts.30021 xx 400221 xx 2502

4、x 0,021xx 解：(1)分别取决策变量21,xx为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例 1 的每个约束条件都代表一个半平面。（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。（3）把五个图合并成一个图，取各约束条件的公共部分，如图 2-1 所示。100 100 200 2x1+x2400 2x1+x2=400 300 200 300 400 x2 x1 X20 X2=0 x2 x1 X10 X1=0 100 200 300 100 200 300 x1+x2300 x1+x2=300 100 100

5、x2250 x2=250 200 300 200 300 （4）目标函数2110050 xxZ，当 z 取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到 B 点时，z 在可行域内实现了最大化。A，B，C，D，E 是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。综上得到最优解：250,5021xx 最优目标值 27500z 三、线性规划问题解的情况 1、如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；2、无穷多个最优解。若将例 1 中的目标函数变为215050 xxZMax，则线段 BC 上的所有点都代表了最优

6、解；3、无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。x1 x2 x2=0 x1=0 x2=250 x1+x2=300 2x1+x2=400 图2-1 x1 x2 z=20000=50 x1+100 x2 图2-2 z=27500=50 x1+100 x2 z=0=50 x1+100 x2 z=10000=50 x1+100 x2 C B A D E 一般来说，这说明模型有错，忽略了一些必要的约束条件；4、无可行解。若在例 1 的数学模型中再增加一个约束条件12003421 xx，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。例 2 某公司由于生产需要，共

7、需要 A，B 两种原料至少 350 吨（A，B 两种材料有一定替代性），其中 A 原料至少购进 125 吨。但由于 A，B 两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨 A 原料需要 2 个小时，加工每吨 B 原料需要 1 小时，而公司总共有 600个加工小时。又知道每吨 A 原料的价格为 2 万元，每吨 B 原料的价格为 3 万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买 A，B 两种 原料，使得购进成本最低？解：目标函数：2132xxfMin 约束条件：ts.35021 xx 600221 xx 1251x 0,021xx 采用图解法。如下图：得 Q 点

8、坐标（250，100）为最优解。教学组织 1、课堂讲授 2、多媒体图形演示 作业布置：1、P23.2（1，2）100 200 300 400 500 600 100 200 300 400 600 500 x1=125 x1+x2=350 2x1+3x2=800 2x1+3x2=900 2x1+x2=600 2x1+3x2=1200 x1 x2 Q 第 3 次课 2 学时 本次课教学重点：化标准型、灵敏度分析 本次课教学难点：灵敏度分析 本次课教学内容：第三节 图解法的灵敏度分析 一、线性规划模型的标准形式 目标函数：nnxcxcxcZMinMax.)(2211 约束条件：ts.1121211

9、1),(.bxaxaxann 22222121),(.bxaxaxann mnmnmmbxaxaxa),(.2211 0,.,0,021nxxx 标准形式四个特点：1目标最大化；2约束为等式；3决策变量均非负；4右端项非负。二、线性规划模型标准化 1.极小化目标函数的问题：设目标函数为 nnxcxcxcfMin.2211 (可以)令 z -f，则该极小化问题与下面的极大化问题有相同的最优解，即 nnxcxcxcZMax.2211 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即 Min f Max z 2、约束条件不是等式的问题：（1）设约束条件为 inin

10、iibxaxaxa.2211 可以引进一个新的变量is，使它等于约束右边与左边之差 niniiiixaxaxabs.2211 显然，is 也具有非负约束，即0is，这时新的约束条件成为 iininiibsxaxaxa.2211 （2）当约束条件为 ininiibxaxaxa.2211时，类似地令 ininiiibxaxaxas.2211 显然，is 也具有非负约束，即0is，这时新的约束条件成为 iininiibsxaxaxa.2211 3.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 0ib，则把该等式约束两端同时乘以-1，得到：ininiib

11、xaxaxa.2211 为了使约束由不等式成为等式而引进的变量is,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。例：将以下线性规划问题转化为标准形式 321432xxxfMin 约束条件：ts.6543321xxx 8231 xx 9321xxx 0,321xxx x1,x2,x3 0 解：首先,将目标函数转换成极大化：令 321432xxxfz 次考虑约束，有 2 个不等式约束，引进松弛变量0,54xx。三个约束条件的右端值为负，在等式两边同时乘-1。通过以上变换

12、，可以得到以下标准形式的线性规划问题：321432xxxzMax 约束条件：ts.65434321xxxx 82531xxx 9321xxx 0,54321xxxxx 4.变量无符号限制的问题 在标准形式中，必须每一个变量均有非负约束。当某一个变量 xj没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然 xj的符号取决于 xj和 xj”的大小。三、灵敏度分析 灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）jijibac,变化时，对最优解产生的影响。1目标函数中的系数 ic 的灵敏度分析 ic的变化

13、只影响目标函数等值线的斜率，不影响可行域。考虑例 1 的情况，目标函数2110050 xxZ 在 2xZ (zx 2斜率为 0)到21xxZ (zxx21 斜率为 1)之间时，原最优解250,5021xx 仍是最优解。一般情况：2211xcxcZ；写成斜截式 21212czxccx 目标函数等值线的斜率为21cc ，当 (*)0121cc 时，原最优解仍是最优解。1 假设产品的利润 100 元不变，即1002c，代到式（*）并整理得 10001 c 2 假设产品的利润 50 元不变，即501c，代到式（*）并整理得 250c 假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分

14、别为 60 元、55 元，则 155602 那么，最优解为21xxZ 和 212xxZ的交点 200,10021xx。2 约束条件中右边系数jb的灵敏度分析 当约束条件中右边系数jb变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例 1 的情况：（1）假设设备台时增加 10 个台时，即1b变化为 310，这时可行域扩大，最优解为 2502x 和31021 xx 的交点250,6021xx 变化后的总利润 变化前的总利润=增加的利润(5060+100250)(50 50+100 250)=500，500/10=50 元 说明在一定范围内每增加（减少）1 个台时的设备能力就可增加（减少

15、）50 元利润，称为该约束条件的对偶价格。（2）假设原料 A 增加 10 千克时，即 2b变化为 410，这时可行域扩大，但最优解仍为 2502x 和31021 xx 的交点 250,6021xx。此变化对总利润无影响，该约束条件的对偶价格为 0。解释：原最优解没有把原料 A 用尽，有 50 千克的剩余，因此增加 10 千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加 1 个单位时 （1）若约束条件的对偶价格大于 0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于 0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于 0，则最优目标函数值不变。教学组织 1、课堂讲授 2、多媒体教学 3、课堂练习 作业布置：1、P24.3（2，3），4 2、P25.6 资源限制 设备 1 1 300 台时 原料 A 2 1 400 千克 原料 B 0 1 250 千克 单位产品获利 50 元 100 元