Presentation is loading. Please wait.

Presentation is loading. Please wait.

第二章 线性规划的图解法 线性规划是运筹学中最重要、最成熟的分支,也是我们这门课的重点,2~9章全部是线性规划的内容,下面我们先来学习第2章的内容.

Similar presentations


Presentation on theme: "第二章 线性规划的图解法 线性规划是运筹学中最重要、最成熟的分支,也是我们这门课的重点,2~9章全部是线性规划的内容,下面我们先来学习第2章的内容."— Presentation transcript:

1 第二章 线性规划的图解法 线性规划是运筹学中最重要、最成熟的分支,也是我们这门课的重点,2~9章全部是线性规划的内容,下面我们先来学习第2章的内容

2 主要内容 问题的提出(建模) 线性规划模型的标准化 图解法 灵敏度分析

3 线性规划(Linear Programming)
规划问题:生产和经营管理中经常提出如何合理安排,使人力、物力等各种资源得到充分利用,获得最大的效益。 线性规划是运筹学的一个重要分支。它是现代科学管理的重要手段之一,是帮助管理者作出最优决策的一个有效的方法。 (1)当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源 (如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标 (2)在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多 、利润最大.)

4 线性规划的应用 在管理中经常应用的典型的线性规划问题:
1.合理利用线材问题。现有一批长度一定的钢管,由于生产的需要,要求截出不同规格的钢管若干。试问应如何下料,既满足了生产的需要,又使得使用的原材料钢管的数量最少。 2.配料问题。用若干种不同价格不同成分含量的原料,用不同的配比混合调配出一些不同价格不同规格的产品,在原料供应量的限制和保证产品成分的含量的前提下,如何获取最大的利润。

5 线性规划的应用 4.产品生产计划。合理充分地利用厂里现有的人力、物力、财力,作出最优的产品生产计划,使得工厂获利最大。
3.投资问题。从许多不同的投资项目中选出一个投资方案,使得投资的回报为最大。 4.产品生产计划。合理充分地利用厂里现有的人力、物力、财力,作出最优的产品生产计划,使得工厂获利最大。 5.劳动力安排。某单位由于工作需要,在不同时间段需要不同数量的劳动力,在每个劳动力工作日连续工作八小时的规则下,如何安排劳动力,才能用最少的劳动力来满足工作的需要。

6 线性规划的应用 以上例子的共同点: 首先,每个例子中都要求达到某些数量上的最大化或最小化的目标。
其次,所有线性规划问题都是在一定的线性的约束条件下来追求其目标的。

7 线性规划(Linear Programming)
线性规划的模型 线性规划模型的一般形式 线性规划模型的标准形式 线性规划的图解法

8 线性规划问题的数学模型 例 如图所示,如何截取x使铁皮所围成的容积最大? x a

9 2.1 问题的提出(建模) 例1:某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,生产单位产品所需的设备台时及 A、B 两种原材料的消耗以及资源的限制,如下表所示,问:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多? 我们首先来看一个典型的线性规划解决的问题

10 如何建立模型?

11 例1完整的模型 设I、II产品分别生产x1 单位和x2单位, 目标函数:max z = 50 x1 + 100 x2
s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0 把满足所有约束条件的解称为该线性规划的可行解。把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解,此目标函数值称为最优目标函数值,简称最优值。 根据上述方法,我们尝试建立例1 的线性规划的模型

12 建模方法 线性规划的数学模型由三个要素构成 确定决策变量:用符号来表示模型要确定的未知量
确定目标函数:max f 或 min f ,是线性函数。目标函数也是评价准则。 确定约束条件:s.t. (subject to),反映客观条件的限制,是线性变量的等式或不等式 面对这样一个问题,我们该如何建模呢

13 线性规划的数学模型 怎样辨别一个模型是线性规划模型? 其特征是: (1)问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;
(2)问题的约束条件是一组多个决策变量的线性不等式或等式。

14 线性规划问题建模过程应注意的问题: 1.要正确理解所要解决的问题,要搞清在什么条件下,追求什么样的目标。
2.定义决策变量,每一个问题都用一组决策变量(X1,X2, …, Xn)的线性组合来表示;一组决策变量的具体值就代表一个具体方案,一般这些变量取值是非负的。 3.用决策变量的线性函数形式写出所要追求的目标,称之为目标函数,按问题的不同,要求目标函数实现最大化或最小化。 4.用一组决策变量的等式或不等式来表示在解决问题过程中所必须遵循的约束条件。 满足以上2、3、4三个条件的数学模型称之为线性规划的数学模型,其一般形式如下页所示。

15 线性规划模型的一般形式(推广) 简写为: 设决策变量 x1 ,x2 ,… ,xn
目标函数:max(min)z = c1x1+c2x2+…+cnxn 约束条件 s.t.:a11 x1 + a12 x2 + … + a1n xn ≤(=, ≥)b1 a21 x1 + a22 x2 + … + a2n xn ≤(=, ≥)b2 …… am1 x1 + am2 x2 + … + amn xn ≤(=, ≥)bm x1 ,x2 ,… ,xn ≥0 对例1的模型我们进行扩展,得到线性规划的一般模型 简写为:

16 线性规划模型的矩阵形式 价值系数向量或 目标函数系数向量 资源常数向量或 约束右端常数向量 技术系数或约束系数矩阵 决策变量向量

17 线性规划模型的矩阵形式 2019/4/30

18 线性规划模型的矩阵形式 决策变量:X 目标函数:max(min)z = C X 约束条件 s.t.: A X ≤(=, ≥)b
Xi ≥0 i=1,2,...,n 线性规划的模型还常常用矩阵形式描述,这里C称做效益矩阵,A叫做系数矩阵,B叫做常数向量

19 线性规划模型标准形式 一般形式: 目标函数: max(min)z = c1 x1 + c2 x2 + … + cn xn
约束条件s.t. : a11 x1 + a12 x2 + … + a1n xn ≤(=, ≥)b1 a21 x1 + a22 x2 + … + a2n xn ≤(=, ≥)b2 …… am1 x1 + am2 x2 + … + amn xn ≤(=, ≥)bm 决策变量符号: x1 ,x2 , … ,xn ≥ 0, ≤0,Free 目标函数可求最大值也可求最小值 约束条件右端符号可≥,=,或 ≤ 决策变量符号可≥ 0, ≤0或Free

20 线性规划模型的标准形式 标准化形式: 目标函数: max z = c1 x1 + c2 x2 + … + cn xn 约束条件s.t. : a11 x1 + a12 x2 + … + a1n xn =b1 a21 x1 + a22 x2 + … + a2n xn =b2 …… am1 x1 + am2 x2 + … + amn xn=bm 变量符号: x1 ,x2 , … ,xn≥ 0

21 一般形式与标准形式对比 线性规划的一般形式 目标函数 :max,min 约束条件:≥,=,≤ 变量符号:≥0, ≤0, Free
线性规划的标准形式 目标函数:max 约束条件:= 变量符号:≥0 MaxZ =CX s.t. AX=b X≥0

22 线性规划标准形的四个特点 目标函数最大化,不含常数项(本书上目标函数最小化也可); 约束为等式; 决策变量均非负; 常数项(右端项)非负。

23 标准化可能遇到的问题 极小化目标函数转化为极大化 小于等于约束条件转化为等号约束 大于等于约束条件转化为等号约束
决策变量没有符号限制(Free)的标准化 常数项小于0的标准化

24 1. 极小化目标函数转换为极大目标函数 如果是求极小值即 则:可将目标函数乘以(-1),可化为求极大值问题。 也就是:令 ,可得到上式。

25 2. 约束条件不是等式的问题 设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi,
可以引进一个新的变量 s ,使它等于约束右边与左边之差, s=bi– (ai1 x1 + ai2 x2 + … + ain xn ) 显然,s 也具有非负约束,即 s≥0, 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi

26 2. 约束条件不是等式的问题 设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≥ bi, 类似地,令
s= (ai1 x1+ai2 x2+ … +ain xn) − bi 显然,s 也具有非负约束,即 s≥0,这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn − s = bi

27 2. 约束条件不是等式的问题 如果原问题中有若干个非等式约束,则将其转化为标准形式时,必须对各个约束引进不同的松弛变量或剩余变量。
称为松弛变量 称为剩余变量 如果原问题中有若干个非等式约束,则将其转化为标准形式时,必须对各个约束引进不同的松弛变量或剩余变量。

28 3. 常数项为负值的问题 当某一个常数项为负值时,如 bi<0 则把该等式约束两端同时乘以−1,得到:
− ai1 x1 − ai2 x2− … − ain xn = −bi

29 4. 变量无符号限制的问题 在标准形式中,必须每一个变量均有非负约束。当某一个变量 xj 没有非负约束时,可以令 xj = xj'- xj“

30 模型标准化(例1) 例1:一般模型为 min z=x1+2x2-3x3 s.t. 2x1+3x2-4x3≤5 3x1-2x2+5x3≥8
x1≥0, x2:free, x3≥0 先将目标函数转化为极小化,并在约束中引进松弛变量或剩余变量,把不等式约束变为等式。 max z’=-x1-2x2+3x3 s.t x1+3x2-4x3+x =5 3x1-2x2+5x x5 =8 x1≥0, x2:free, x3, x4, x5≥0

31 max z’=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x =5 3x1-2x2+5x x5=8 x1≥0, x2:free, x3, x4, x5≥0 然后,令x2=x2’-x2”,其中x2’,x2”≥0。代入模型,消去x2 max z’=-x1-2(x’2-x”2)+3x3 s.t x1+3(x’2-x”2)-4x3+x4 =5 3x1-2(x’2-x”2)+5x x5=8 x1, x’2, x”2, x3, x4,x5≥0 整理,得到标准形式: max z’=-x1-2x’2+2x”2+3x3+0x4+0x5 s.t x1+3x’2-3x”2-4x3+x =5 3x1-2x’2+2x”2+5x x5 =8

32 模型标准化(例2) 用 替换 ,且 解:(1)因为x3无符号要求 ,即x3可能取正值也可取负值,标准型中要求变量非负, 所以

33 标准化例子 (2) 第一个约束条件是“≤”号,在“≤”左端加入松驰变量x4,x4≥0,化为等式;
(4) 第3个约束方程右端常数项为-5,方程两边同乘以(-1),将右端常数项化为正数; (5) 目标函数是最小值,为了化为求最大值,令z′=-z,得到max z′=-z,即当z达到最小值时z′达到最大值,反之亦然;

34 标准化例子 标准形式如下:

35 解的相关概念 可行解:满足所有约束条件的解称为该线性规划的可行解,对应一个方案。 最优解:使目标函数值最大(或最小)的可行解,称为最优解
最优值:最优解对应的目标函数值称为最优值。 和线性规划求解相关的有3个概念,我们首先来熟悉这些概念,接着再求解

36 2.2 图解法 什么是图解法? 线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。
求解的思路是:先将约束条件加以图解,求得满足约束条件的解的集合(即可行域),然后结合目标函数的要求从可行域中找出最优解。 图解法条件:对于只包含两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示线性规划问题的有关概念,并求解。

37 图解法步骤(例1为例) (1)分别取决策变量 x1,x2 为坐标向量建立直角坐标系。在直角坐标系里,图上任意一点的坐标代表了决策变量的一组值,每个约束条件都代表一个半平面,如下图所示

38 图解法步骤(例1为例) (2)对每个不等式(约束条件),先取其等式在坐标系中作直线,然后确定不等式所决定的半平面 例:
max z = 50 x x2 s.t x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0

39 第一个约束条件 x2 300 X1+X2=300 100 x1 100 300 X1+X2 ≤ 300

40 第二个约束条件 x2 400 2X1+X2=400 100 x1 100 300 2X1+X2 ≤ 400

41 第三个约束条件 x2 X2=250 100 x1 100 300 X2 ≤ 250

42 图解法步骤(例1为例) (3)把所有约束条件对应的图合并成一个图,取各约束条件的公共部分就是可行解的集合,称为可行域。可行域一定是凸集。

43 阴影部分的每一点(包括边界线)都是这个线性规划的可行解,而此公共部分是可行解的集合,称为可行域。
2x1+x2=400 (4)目标函数 z = 50x x2,当 z 取某一固定值时得到一条直线,直线上的每一点都具有相同的目标函数值,称之为“等值线”。平行移动等值线,当移动到 B 点时,z 在可行域内实现了最大化。 Z=27500=50x1+100x2 x2 400 B X2=250 阴影部分的每一点(包括边界线)都是这个线性规划的可行解,而此公共部分是可行解的集合,称为可行域。 100 100 300 x1 X1+X2=300 Z=0=50x1+100x2 Z=10000=50x1+100x2 B点为最优解,坐标为(50,250)

44 最优解的分析 引入 s1,s2,s3,变为标准模型: 目标函数:max z = 50 x1 + 100 x2
s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 =400 x2 + s3 = 250 x1 , x2 ≥ 0 最优解 x1 =50,x2 = 250,s1 = 0,s2 =50,s3 = 0 说明:1. 生产 50 单位Ⅰ产品和 250 单位Ⅱ产品将消耗完所有可能的设备台时数及原料 B 2.但原料 A 还剩余 50 千克。 台时数约束 原料A数量约束 原料B数量约束 松弛变量 接下来我们分析一下我们得到的最优解,首先分析一下资源消耗情况,其次分析一下解可能的几种情况

45 进一步讨论 例2:某公司为了满足生产需要,共需 A,B 两种原料至少 350 吨(A,B 两种原料有一定替代性),其中原料 A 至少购进 125 吨。但由于 A,B两种原料的规格不同,各自所需的加工时间也是不同的,加工每吨原料 A需要 2 个小时,加工每吨原料 B 需要 1 小时,而公司总共有 600 个加工小时。又知道每吨原料 A 的价格为 2 万元,每吨原料 B 的价格为 3 万元,试问在满足生产需要的前提下,在公司加工能力的范围内,如何购买 A,B 两种原料,使得购进成本最低?

46 例2 建模 解:设A、B原料分别需要购进x1和x2吨 目标函数:min f = 2x1 + 3x2 约束条件: x1 + x2 ≥ 350
例2 建模 解:设A、B原料分别需要购进x1和x2吨 目标函数:min f = 2x1 + 3x2 约束条件: x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0

47 图解法步骤 x2 x1 Q 目标函数:min f = 2x1 + 3 x2 约束条件: x1 + x2 ≥ 350 x1 ≥ 125
100 200 300 400 500 600 x2 目标函数:min f = 2x1 + 3 x2 约束条件: x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0 2x1 + 3 x2=1200 Q x1 (250,100)

48 例2 分析 最优解资源分析:Q 点(250,100)为最优解,这时x1 ≥ 125,超过量称为剩余量 购买A和B的总量为
1 · 250+1· 100=350(t) 所需要的加工时间为 2 · 250+1· 100=600(t) 原料A的购买量比最低限度多购买了 =125(t) 剩余变量

49 模型标准化 目标函数:min f = 2x1 + 3 x2+0s1+0s2+0s3 约束条件: x1 + x2 - s1= 350
剩余变量为125吨 目标函数:min f = 2x1 + 3 x2 约束条件: x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0

50 总结 图解法的步骤: 作图的关键有三点: 建立坐标系,确定比例尺; 画出各约束条件的边界,定出可行域;
画出目标函数的一根等值线,平移得出最优解; 算出目标函数最优值。 作图的关键有三点: (1) 可行解区域要画正确 (2) 目标函数增加或减少的方向不能画错 (3) 目标函数的直线怎样平行移动

51 总结:线性规划问题的解可能遇到的情况 如果线性规划有最优解,则一定有一个可行域的顶点对应一个最优解; 解的类型 无穷多个最优解 无界解
无可行解

52 无穷多个最优解 无穷多个最优 解:若将例 1 中的目标函数 变为 Max z=50x1+50x2 则线段BC上的所 有点都代表了最 优解;
400 X2=250 B C 100 100 300 x1 X1+X2=300 Z=0=50x1+50x2 Z=10000=50x1+50x2

53 无界解 目标函数: max z =x1+x2 约束条件: x1-x2≤1 - 3x1+2x2≤6 x1≥0,x2≥0
无界解。即可行域的范围延伸到无穷远,目标函数值可以无穷大或无穷小。一般来说,这说明模型有错,忽略了一些实际存在的必要的约束条件; 目标函数: max z =x1+x2 约束条件: x1-x2≤1 - 3x1+2x2≤6 x1≥0,x2≥0

54 无界解 注意啊 此题为无界解 x2 -3x1+2x2=6 Z=3=X1+X2 Z=1=X1+X2 Z=0=X1+X2 3 1 -1

55 无界解 max Z=x1+2x2 6 4 2 无界解(无最优解) 2 4 6 x2 x1 3x1+x2=6(≥) x1+x2=4(≥)
min Z x1 2 4 6

56 无可行解 x2 x1 无可行解。 若在例 1 的 数学模型中 再增加一个 约束条件 4x1+3x2≥1200, 则可行域为空域
,当然也就不存 在最优解了。 400 X2=250 100 x1 100 300 X1+X2=300 4x1+3x2=1200

57 总结:线性规划问题的解可能遇到的情况 1、唯一最优解(封闭) 2、多个最优解(封闭) 3、唯一最优解(开放) 4、多个最优解(开放)
5、目标函数无界(开放) 6、无可行解

58 总结:线性规划问题的解可能遇到的情况 可行域 最优解 空集 无最优解 有界集 唯一最优解 无界集 无穷多个最优解 没有有限最优解

59 练习 举例: 1.maxZ=2x1+ x2 5x2≤15 6x1+2x2 ≤24 x1+ x2 ≤5 x1, x2≥0 2. maxZ=x1+ x2 -2x1+x2 ≤4 x1- x2 ≤2 3.maxZ=3x1+9x2 x1+3x2 ≤22 -x1+x2 ≤4 x1, x2≥0 4.maxZ=x1+ x2 x1+x2 ≤1 2x1+2x2≥4 x1, x2≥0

60 练习 x2 12 唯一最优解 (1) 5 3 1 x1 1 5 6

61 练习 无界解 x2 (2) 6 5 3 1 x1 1 5 6

62 练习 x2 (3) 12 无穷多最优解 5 3 1 x1 -4 1 5 6 12 18 25

63 练习 x2 (4) 无解 2 1 x1 1 2 3

64 2.3 图解法的灵敏度分析 概念:在建立数学模型和求得最优解之后,研究线性规划的一个或多个参数(系数)ci , aij , bj 变化时,对最优解产生的影响。 目标函数: max z = c1 x1 + c2 x2 + … + cn xn 约束条件s.t. : a11 x1 + a12 x2 + … + a1n xn =b1 a21 x1 + a22 x2 + … + a2n xn =b2 …… am1 x1 + am2 x2 + … + amn xn=bm x1 ,x2 , … ,xn≥ 0

65 进行灵敏度分析的原因 ci , aij , bj都是估计值和预测值,不一定精确 即使在某一时刻精确, 但是会随着市场条件的变化而变化
分析灵敏度后,不必为应付变化而不断求新的最优解

66 设I、II产品分别生产x1 单位和x2单位, 目标函数:max z = 50 x1 + 100 x2 s.t. x1 + x2 ≤ 300
c1 c2 例1:某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,生产单位产品所需的设备台时及 A、B 两种原材料的消耗以及资源的限制,如下表所示,问:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多? x2=250, x1=50

67 斜率在区间1时([-1,0]),最优点在B 斜率在区间2时([-2,-1]),最优点在C 斜率在区间3时(≤-2),最优点在D 2 3 1
100 200 300 400 斜率在区间1时([-1,0]),最优点在B 斜率在区间2时([-2,-1]),最优点在C 斜率在区间3时(≤-2),最优点在D 2 3 系数变了,斜率就变了 Z= 50 x x2 1 A B 目标函数曲线 斜率为-c1/c2 C 300= x1 + x2 400= 2x1 + x2 D

68 1. 目标函数中的系数ci的灵敏度分析 一般情况,目标函数如下: z = c1 x1 + c2 x2 ,写成斜截式
x2 = − (c1 / c2 ) x1 + z / c2,则目标函数等值线的斜率为− (c1 / c2 ) 。 可见,ci 的变化只影响目标函数等值线的斜率。 当斜率范围为:在 z = x2 (x2 = z 斜率为 0) 到 z = x1 + x2 (x2 =−x1 + z 斜率为−1)之间时,原最优解 x1 = 50,x2 = 100 仍是最优解。 即:当-1 ≤ - (c1 / c2 ) ≤ 0(*) 时,原最优解仍是最优解

69 1. 目标函数中的系数ci的灵敏度分析 问题1:固定C2,问C1在什么范围内变动时,B仍为最优解?

70 1. 目标函数中的系数ci的灵敏度分析 假设产品Ⅰ、Ⅱ的利润分别变为 60 元、55 元,则 − (60 / 55) ≤ −1
− (60 / 55) ≤ −1 那么,最优解需要重新计算,即需要调整生产方案

71 2. 约束条件中常数项 bj 的灵敏度分析 当约束条件中常数项 bj 变化时,导致: 线性规划的可行域发生变化,一般会引起最优解的变化。
考虑例 1 的情况: (1)假设设备台时增加 10 个台时,即 b1 变化为 310,这时可行域扩大,见图

72 目标函数:50x1+100 x2=Z x2=250 x1=60 B’ C’ A B C 300 = x1 + x2
200 300 400 目标函数:50x1+100 x2=Z x2=250 x1=60 B’ x2=250 C’ A B 50 × × × ×250 =500 说明在一定范围内每增加(或减少)1 个台时的设备能力就可增加(或减少)50 元利润,这称为该约束条件的对偶价格。 C 300 = x1 + x2 310 = x1 + x2 400= 2x1 + x2 D

73 对偶价格 在约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格。
如例1中,设备对偶价格为50元/台时,即若增加或减少若干个台时,则总利润将增加或减少若干个50元。

74 2. 约束条件中常数项 bj 的灵敏度分析 当约束条件中的(松弛变量或者剩余变量)不为0时,对偶价格为0。
(2)假设原料 A 增加 10 千克,即 b2 变化为 410,这时可行域扩大,但最优解仍为 x2 = 250 和 x1 + x2 = 300 的交点 x1 = 50,x2 = 250。此变化只增加了A的库存,对总利润无影响,该约束条件的对偶价格为 0。 当约束条件中的(松弛变量或者剩余变量)不为0时,对偶价格为0。 

75 解释:原最优解没有把原料 A 用尽,有 50 千克的剩余,因此增加10千克只增加了库存,而不会增加利润。
100 200 300 400 不影响最优解 解释:原最优解没有把原料 A 用尽,有 50 千克的剩余,因此增加10千克只增加了库存,而不会增加利润。 因此原料A的对偶价格为0。 A B C 410= 2x1 + x2 300 = x1 + x2 400 = 2x1 + x2 D

76 2. 约束条件中常数项 bj 的灵敏度分析 (3)假设原料 B 增加 10 千克,即 b3 变化为 260,这时最优解为 x2 = 260 和 x1 + x2 = 300 的交点 x1 = 40,x2 = 260。此变化对总利润的影响为: 50 × × × ×250 =500 说明在一定范围内每增加(或减少)10千克原料B,就可增加(或减少)500元利润,则1千克对应50元,该50元即为该约束条件的对偶价格。

77 目标函数:50x1+100 x2=Z x2=260 x1=40 B’ A B C 300 = x1 + x2 D x2=260 x2=250
200 300 400 目标函数:50x1+100 x2=Z x2=260 x1=40 B’ x2=260 A B x2=250 50 × × × ×250 =500 说明在一定范围内每增加(或减少)1 0千克原料B就可增加(或减少)500元利润,这称为该约束条件的对偶价格(原料B:50元/Kg)。 C 300 = x1 + x2 400= 2x1 + x2 D

78 下面结论很重要啊! 在一定范围内,当约束条件右边常数增加一个单位时:
1)、如果对偶价格大于零,则其最优目标函数值得到改进(越来越好),即求最大值时,变得更大;求最小值时,变得更小。 2)、如果对偶价格小于零.则其最优目标函数值变坏,即求最大值时,变得小了;求最小值时变得大了。 3)、如果对偶价格等于零,则其最优目标函数值不变。 但是如果是约束条件右边常数减少一个单位时,则情况又相反了。 1)、如果对偶价格大于零,则其最优目标函数值变坏,即求最大值时,变得更小;求最小值时,变得更大。 2)、如果对偶价格小于零.则其最优目标函数值变好,即求最大值时,变得大了;求最小值时变得小了。

79 本章作业 2 (1)(2)(3)(5) 3 (3) 5 7


Download ppt "第二章 线性规划的图解法 线性规划是运筹学中最重要、最成熟的分支,也是我们这门课的重点,2~9章全部是线性规划的内容,下面我们先来学习第2章的内容."

Similar presentations


Ads by Google