管理运筹学_第二章_线性规划的图解法讲解

《管理运筹学_第二章_线性规划的图解法讲解》由会员分享，可在线阅读，更多相关《管理运筹学_第二章_线性规划的图解法讲解（24页珍藏版）》请在金锄头文库上搜索。

1、1 &线性规划是运筹学的一个重要分支，是管理者作出最优决策的一个有效的方法。 一些典型的线性规划问题： & 1合理利用线材问题。现有一批长度一定的钢管， 由于生产的需要，要求截出不同规格的钢管若干。试 问应如何下料，既满足了生产的需要，又使得使用的 原材料钢管的数量最少。 & 2产品生产计划。合理充分地利用厂里现有的人力 、物力、财力，作出最优的产品生产计划，使得工厂 获利最大。 & 3运输问题。一个公司有若干个生产单位与销售单 位，根据各生产单位的产量及销售单位的销量，如何 制定调运方案，将产品运到各销售单位而总的运费最 小。 第二章第二章 线性规划的图解法线性规划的图解法 2 4投资问题。

2、从许多不同的投资项目中选出一个 投资方案，使得投资的回报为最大。 共同特点： 首先，要求达到某些数量上的最大化或最小化。 问题1，要求使用原料钢管最少； 问题2, 要求利润最大； 问题3，要求运费最小； 问题4，要求投资回报最大。线性规划问题的目标。 其次，一定的约束条件下追求其目标。 问题1，在满足生产需要的数量、不同规格的约束下 追求原材料的最小使用量。 问题2, 在现有的人力、物力、财力的限制下来追求 最大利润。 3 &例例1 1某工厂生产某工厂生产、两种产品，已知生产单位两种产品，已知生产单位 产品所需的设备台时及产品所需的设备台时及A A，B B两种原材料的消耗，及两种原材料的消耗，

3、及 资源的限制，如下表所示。资源的限制，如下表所示。 资源限制资源限制 设备设备 1 1 1 1 300300台时台时 原料原料A A 2 2 1 1 400400千克千克 原料原料B B 0 0 1 1 250250千克千克 该厂生产单位产品该厂生产单位产品I I可获利可获利5050元，生产单位产品元，生产单位产品可获利可获利 100 100 元，问元，问该该厂应分别生产多少产品厂应分别生产多少产品和产品和产品才能获利最多才能获利最多 ? ? 2.1 问题的提出 如何建立模型？ 4 & 设工厂生产x1个产品和x2个产品,相应的利润 z=50 x1+100x2 。问题的数学模型如下： 4 目标

4、函数： max z=50x1+100x2， 约束条件： x1+x2300， 2 x1+x2400， x2250, x10, x20. &目标函数为线性函数，约束条件也为线性的，这样的 模型称之为线性规划。如果目标函数或约束条件是非 线性的则称为非线性规划。 & 满足约束条件的解称为该线性规划的可行解。使 得目标函数最大(或最小)的可行解称为该线性规划的 最优解。 台时数 原材料A 原材料B 决策变量 5 1理解问题，搞清在什么条件下，追求什么样的目标。 2定义决策变量，决策变量(X1，X2, , Xn)的每一组值 表示问题的一个解决方案； 3用决策变量表示目标函数。 4用决策变量表示达到目标必

5、须遵循的约束条件。 &线性规划的数学模型一般形式为: &线性规划问题建模过程： 目标函数： max (min) Z=c1x1+c2x2+cnxn 约束条件： a11x1+a12x2+a1nxn( =, ) b1, a21x1+a22x2+a2nxn( =, ) b2, am1x1+am2x2+amnxn( =, ) bm, x1, x2, , xn0. 6 & 只含两个决策变量的线性规划，可用图解法求解 。 & 图解法.首先把每个约束条件画在二维坐标面上。 100 300 100 300 X1+X2=300 x1 x2 2.2 图 解 法 100 400 100300 2X1+X2=400 x

6、1 x2 100 100300 X2=250 x1 x2 7 X1+X2=300 100 400 100300 x1 x2 X2=250 2x1+x2=400 Z=10000=50x1+100x2 Z=27500=50x1+100x2 B & 阴影部分的每 一点都是这个线 性规划的可行解 ，而此公共部分 是可行解的集合 ，称为可行域。 & B点为最优解 ，坐标为（50, 250 ），此时Z=27500 。 Z=0=50x1+100x2 最优生产方案是生产I产品50单位，生产产品250单位，可得 最大利润27500元。 & 问题的解： 8 松弛变量 & 最佳决策为x1=50, x2=250，此时

7、z=27500。 &约束条件中没使用的资源或能力称之为松弛量。 &用Si表示松弛量，对最优解 x1=50,x2=250来说： 约束条件 松弛变量的值 设备台时数 s1=0 原料A s2=50 原料B s3=0 资源限制 设备11300台时 原料A21400千克 原料B01250千克 资源消耗 50+250=300台时 250+250=350千克 1250=250千克 9 线性规划标准型 &加了松弛变量后例1的数学模型可写成： 目标函数：max z=50x1+100x2+0s1+0s2+0s3， 约束条件： x1+x2+s1=300, 2x1+x2+s2=400, x2+s3=250, x1,x

8、2,s1,s2,s30 & 三个特征： 一、约束条件为等式； 二、约束条件右端常数项非负； 三、所有变量非负。 称为线性规划的标准形式。 如何把模型化为 标准型？ 10 线性规划问题解的情况： & 1若有最优解，一定能在可行域的顶点取得。 & 2无穷多个最优解的情况。 比如例1中的目标函数变为max Z =50x1+50x2，则 X1+X2=300 100 400 100300 x1 x2 X2=250 2x1+x2=400 Z=10000=50x1+50x2 Z=15000=50x1+50x2 B Z=0=50x1+50x2 C 线段BC上的所有点都代表了最优解，对应的最优值相 同： 50x

9、1+50x2=15000。 11 & 3. 无界解，即无最优解的情况。对下述线性规划问题 ： 目标函数：max z =x1+x2 约束条件：x1 - x21 -3x1+2x26 x10, x20 &可行域无界，目标函数值可 以增大到无穷大，无最优解。 &原因：模型忽略了必要 的约束条件。 1 2 3 x1 1 3 -1 x2 Z=3=X1+X2 Z=1=X1+X2 Z=0=X1+X2 -3x1+2x2=6 X1-X2=1 注意啊注意啊 12 & 4无可行解的情况。 比如例1中增加一个约束条件4x1+3x21200： X1+X2=300 100 400 100300 x1 x2 X2=250 4

10、x1+3x2=1200 &可行域为空域。 原因：约束条件自相矛盾。 13 目标函数最小化的线性规划问题 &例2、某公司因生产需要，共需A, B两种原料至少350 吨，其中A原料至少125吨。每吨A原料价格2万元， 每吨B原料价格3万元。又知加工每吨A原料需2小时 ，加工每吨B原料需1小时，公司共有600个加工小时 。在满足生产需要的前提下，在公司加工能力的范围 内，如何购买A, B两种原料，能使购进成本最低? & 解：设x1为购进原料A的吨数，x2为购进原料B的吨 数。则此线性规划的数学模型如下： 目标函数： min f=2x1+3x2， 约束条件： x1+x2350， x1125， 2x1+

11、x2600, x1,x20. 14 图解法： 100 300 500 600 x1 100 300 500 x2 X1=125 2X1+X2=600 X1+X2=350 f=2x1+3x2=1200 f=2x1+3x2=800 Q 购买A原料250吨，B原料100吨，可使成本最小为800万元. & Q点为最 优解，坐标 为(250,100), 此时f=800 15 &分析: 最优决策x1=250,x2=100下购买原料A与B共 250+100=350吨，正好达到约束条件的最低限；而原料 A的购进量250吨比约束低限125吨多了125吨。所需加 工时间2250+1100=600正好用尽公司的加工

12、能力。 &线性规划中超过约束最低限的部分，称为剩余量。线性规划中超过约束最低限的部分，称为剩余量。 & 记记s s 1 1,s ,s2 2 为剩余变量，为剩余变量，s s 3 3 为松弛变量，则为松弛变量，则s s 1 1 =0, s=0, s 2 2 =125, =125, s s3 3 =0=0，加入松弛变量与剩余变量后例，加入松弛变量与剩余变量后例2 2的数学模型变为的数学模型变为 标准型：标准型： 目标函数： min f =2x1+3x2+0s1+0s2+0s3 约束条件： x1+x2-s1=350， x1-s2=125, 2x1+x2+s3=600, x1, x2, s1,s2,s3

13、0. （注意注意松弛变量符号为正，而剩余变量符号为负松弛变量符号为正，而剩余变量符号为负） ） 16 松弛变量和剩余变量看成决策变量，用Xi来表示，得到 &线性规划的标准形式: 目标函数：max(或min) Z=c1x1+c2x2+cnxn 约束条件： a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2, am1x1+am2x2+am nxn=bm. x1, x2,xn0. 其中ci为为第i个决策变变量xi在目标标函数中的系数， aij为为第i个约约束条件中第j个决策变变量xj的系数， bj(0)为为第j个约约束条件中的常数项项。 2.3图解法的灵敏度分析 17

14、 灵敏度分析 & 灵敏度分析：求得最优解之后，研究线性规划的一 些系数ci, aij, bj发生变化时，对最优解产生的影响。 &灵敏度分析的重要性： 1、ci, aij, bj这些系数可能是估计值，不一定精确； 2、这些系数会随市场条件的变化而变化。例如原 材料价格、劳动力价格的变化都会影响这些系数； 有了灵敏度分析就不必为应付这些变化而不停求 其新的最优解，也不必因系数估计的精确性而对求 得的最优解存有怀疑。 下面对例1目标函数中的系数ci以及约束条件中的常数项bj进 行灵敏度分析。 18 &例1中目标函数 max z=c1x1+c2x2= 50x1+100x2 目标中系数c1=50(生产单

15、位I产品可获利50元)， c2=100(生产单位产品可获利100元)。 最优解：x1=50， x2=250，即生产I产品50单位，产 品250单位可获最大利润。 一般地，当某一产品的单位利润增加或减少时，为获取最 大利润就应该增加或减少这一产品的产量，也就是改变最优解 。 & 如何确定使其最优解不变的利润(c1, c2)变化范围？ 一、目标函数中系数Ci的灵敏度分析 19 & c1, c2变动时，最优解的变化情况： 1、当-1 -c1/c2 0 时， 直线E的斜率 -c1/c2直线F的斜率。目标函数的直线在E与 F之间变动。故最优解仍然是B点。 2、当-2-c1/c2-1 时， 3、当-c1/c2-2 时，最优解在D点. 直线G (2X1+X2=400,斜率-2)直线E(X1+X2=300,斜率-1) 100 100300 x1 直线F(X2=250，斜率0) Z=c1x1+c2x2 =50x1+100x2=27500 B C A D 斜率为-C1/C2 300 x2 最优解仍在B点. 最优解在C点. 等号成立时 ，有无穷多 解 20 问题1：固定C2=100，则C1在什么范围内变动时，B仍为最优解 ? 固定C2=100，则 0C1100时B仍为最优解。 问题2：固定C1=50，则C2在什么范围内变动时，B仍为最优解? 固定C1=50，则