第三章 线性规划问题的计算机求解.

Presentation on theme: "第三章 线性规划问题的计算机求解."— Presentation transcript:

1 第三章 线性规划问题的计算机求解

2 内 容 “管理运筹学”软件的操作方法 “管理运筹学”软件的输出信息分析 关于线性规划问题的求解和灵敏度分 析的信息

3 “管理运筹学”的软件包 将介绍如何使用计算机软件包求解线性规划问题
介绍与本书配套的名为“管理运筹学”的软件包,此软件 包可解决100个变量50个约束方程的管理运筹学问题。 解决线性规划问题的软件包分两种， 大规模的软件包，可以用来解决复杂的包含数千个 决策变量和数千个约束条件的大型的线性规划的问 题。 用于微机的软件包，有很好的界面，使用方便，由 科研机构和小软件公司为解决包含数百个决策变量 的线性规划问题而开发的。管理运筹学软件就是属 于这种软件，它可以解决工商管理中大量的线性规 划问题。

4 “管理运筹学”软件的操作方法 然后就根据需要选择运筹学的各个分支 从开始→程序→管理运筹学2.5，这样就打开此软件，如下图：
我们主要使用其中的6个模块，下面以线性规划为例，说明软件的使用方法

5 线性规划相关操作 以例1为例（P11） 点击“新建”按钮，输入数据。本题中共有 2 个变量、3 个约束条件、目标函数取 MAX。
点击“确定”后，在表中输入 Cj ,bi 和 aij 等 值。 点击“解决”按钮，得出计算过程（点击开 始、下一步，直至结束运算） 关闭计算过程界面，得到结果。 这个求解过程使用的就是单纯形法

6 先输入变量个数、约束个数和MAX或Min，然后点确定后，才能输入模型。
然后新建清零，下面就可以输入模型了。 先输入变量个数、约束个数和MAX或Min，然后点确定后，才能输入模型。

7 在这输入约束条件，在输入约束条件时注意清0，还要注意不等号的方向。
输入目标函数系数 在这输入约束条件，在输入约束条件时注意清0，还要注意不等号的方向。 一般地变量的非负性不必修改。

8 输完模型后就可以选择要进行的操作，如：保存、解决（求解）等。下面是例1的输入结果。
输完模型后，苦要修改模型点这里

9 解决后得到如下结果。

10 输入文件名，然后点保存即可，以后可以点打开调出模型。
如果选择保存，就弹出保存路径的对话框。 输入文件名，然后点保存即可，以后可以点打开调出模型。

11

12 输入过程注意事项 输入前先要合并同类项 输入的系数可以是整数、小数，但不能是分 数，必须把分数先化为小数再输入 系数是0时不可以省略输入
所有变量默认≥0，不必输入 当需要保存模型时，点击“保存”按钮

13 §3.2软件输出信息分析（1） 如何读懂输出结果？
1. 从上面变量、最优解、相差值一栏中，知道最优解为 生产Ⅰ产品50单位；生产Ⅱ产品250单位。 2. 相差值提供的数值表示相应的决策变量的目标系数需 要改进的数量，使得该决策变量有可能取正数值，一般 地，当决策变量已取正数值时则相差值为零。如果决策 变量取0值，则相差值可能不为0。 对例1来说： （1）x1=50，x2=250，为正值，所以它们的相差值都为零 （2）如果x1的值为0；x1 的相差值为20；则，只有当产品I 的利润再提高20元（目标系数再提高20），即达到 50+20=70元时， 产品I 才可能生产，即x1才可能大于零

14 喂！你知道什么叫相差值吗？ 我知道：如果决策变量取正数值，则相差值一般为零。则此时目标函数的系数无法再改变使目标函数值变得更好（当目标函数是求最大值时，目标函数值变得更大；而当目标函数是求最小值时，目标函数值变得更小）。 如果决策变量取0值，则相差值可能不为0（比如说相差值为正a)。则此时目标函数的系数可以在原来基础上增加a（而当目标函数是求最小值时，减少a)，则可能才能使此决策变量变为非零（即生产该种产品），才有可能使目标函数值变得更好。

15 §3.2软件输出信息分析（2） 约束条件：x1+x2≤300，（台时数） 2 x1+x2≤400，（原料A） x2≤250, （原料B）
设备 原料A 原料B 约束条件：x1+x2≤300，（台时数） 2 x1+x2≤400，（原料A） x2≤250, （原料B） 1. 设备的台时数全部使用完，每个设备台时的 对偶价格为50元，即增加了一个台时数就可使 总利润增加50元； 2.原料A还有50千克没有使用，原料A的对偶价 格当然为零，即增加1千克A原料不会使总利润 有所增加； 3.原料B全部使用完，原料B的对偶价格为50元 ，即增加一千克原料B就可使总利润增加50元 后两项对应灵敏度分析

16 §3.2软件输出信息分析（2） 松弛（剩余变量）的数值表示还有 多少资源没有被使用。如果为零， 则表示与之相对应的资源已经全部 使用。
对偶价格表示该约束对应的资源每 增加一个单位，最优值将增加多少 个单位。

17 §3.2软件输出信息分析（3） 目标函数： 50x1+100 x2=Z
c1 c2 目标函数的系数范围表示最优解不变的情况下，目标函数的决策 变量系数的变化范围。当前值是指当前的最优解中的系数取值。 上限与下限值是指目标函数的决策变量的系数（其它决策变量的 系数固定）在此范围内变化时，其线性规划的最优解不变。例如 当固定c2=100后， c1 在0于100之间变化时，最优解不变。 当c1= 80时，其最优解不变（当x1=50，x2=250时有最大利润 ）。但其最大利润增加了(最优值变了)， 变为80× ×250 =29000(元） 当c1=110元时，由于110>100，最优解可能发生变化。 当固定c1=50后，c2 在50与＋∞之间变化时，最优解不变

18 §3.2软件输出信息分析（4） 常数项是指约束条件的右端常量。 当前值是指约束条件右边值的现在取值。
设备 原料A 原料B 常数项是指约束条件的右端常量。 当前值是指约束条件右边值的现在取值。 上限值和下限值是指当约束条件的右端常量在 此范围内变化时，与其对应的约束条件的对偶 价格不变，不能保证最优解不变。 可由对偶价格判断，增加某约束条件的常数项 值是否能使目标函数值变得更好（前提条件 是其它常数项保持不变）。 当设备台时数在250→325的范围内，其对偶价格都为50元，说明增加设备台时数可使目标函数值变大，每增加1个台时数可增加利润50元。 当原料A的公斤数在350到+∞范围内，其对偶价格都为零；增加原料A对目标函数值无影响。 当原料B的千克数在200到300的范围内，其对偶价格都为50元。例如设备台时数和原料A的数量不变，即b1=300；b2=400，原料B变为280千克，由于200≤280≤300，原料B的对偶价格仍为50元，故新的最大利润值应为： ( )×50=29000元。这里50是对偶价格。

19 A B C D x1+x2≤300， （台时数） 2 x1+x2≤400 , （原料A） x2≤250, （原料B）
x1+x2+s1=300， （台时数） 2 x1+x2+s2=400 , （原料A） x2+s3=250, （原料B） 对偶价格50 对偶价格0 以第二个约束条件为例： 100 200 300 400 黄色和红色直线的交点为最优解 对偶价格不变 松弛变量s2不为0 此时最优解仍然为x1=75，x2=250，x1+x2+s1=m(m>325), s1≠0，导致约束条件1的对偶价格为0 黄色、红色和紫色三条直线的交点为最优解 b1=325 松弛变量s2为0 X2=250, x1=75 b1=250 A 松弛变量（剩余变量）不为0，对偶价格为0； 对偶价格为0，松弛变量（剩余变量）不一定为0 或不为0 x2=250, x1=0 B 250= x2 C 300= x1 + x2 325= x1 + x2 此时x2肯定<250,对于约束条件3来讲：x2+s3=250, s3≠0，导致约束条件3的对偶价格为0 250= x1 + x2 400=2 x1 + x2 D

20 常数项b2：350——∞ A B C D x1+x2+s1=300， （台时数） 2 x1+x2+s2=400 , （原料A）
100 200 300 400 常数项b2：350——∞ x1+x2+s1=300， （台时数） 2 x1+x2+s2=400 , （原料A） x2+s3=250, （原料B） A B 250= x2 C X2=250, x1=50 2 x1+x2=349（原料A） x2=250, （原料B） 300= x1 + x2 s1 ≠ 0 400=2 x1 + x2 约束条件1的对偶价格变为0 2 x1 + x2= 350 D

21 100 200 300 400 常数项b3：200——300 300= x2 250 250= x2 A B C 200= x2 300= x1 + x2 400=2 x1 + x2 D

22 §3.2软件输出信息分析（5） 注：以上计算机输出的目标函数系 数和约束条件右端值的灵敏度分析 都是在其他系数值不变，只有一个 系数变化的基础上得出的。 当有多个系数变化时，可用百分之 一百法则。 后两项对应灵敏度分析

23 百分之一百法则 百分之一百法则：对于所有变化的目标函 数决策系数ck（或约束条件右端常数值 bi），当其所有允许增加的百分比与允许 减少的百分比之和不超过100%时，最优解 不变（或对偶价格不变）。

24 百分之一百法则 以例1为例，如何用百分之一百法则对 两个目标函数系数同时变化进行灵敏 度分析。
例1中原来每件Ⅰ产品和Ⅱ产品的利润 分别为50元和100元，现在由于市场情 况的变化每件Ⅰ产品和Ⅱ产品的利润 分别变为74元和78元，最优解发生变化 吗?

25 百分之一百法则 目标函数决策变量系数（或约束条件右端常 数值bi ）的百分之一百法则：
允许增加量 = 上限 - 现在值 例：c1 的允许增加量为 = 50； b1 的允许增加量为 = 25 允许减少量 = 现在值 - 下限 例：c2 的允许减少量为 = 50； b3 的允许减少量为 = 50 允许增加的百分比 = 增加量/允许增加量 允许减少的百分比 = 减少量/允许减少量

26 百分之一百法则（目标函数决策变量系数） X1的系数的上限为100，故C1允许增加量为： 上限-现在值=100-50=50
现在值-下限=100-50=50 C1的允许增加量百分比为：(74-50)／50=48％； C2 的允许减少百分比为：(100-78)／50=44％， C1允许增加百分比与C2的允许减少百分比之和为： 48％+44％=92％。 最优解仍然为Ⅰ产品生产50件， Ⅱ产品生产250件(即x1= 50，x2=250)，此时有最大利润为: 74× 50+78× 250=3700＋19500=23200(元)。

27 百分之一百法则（约束条件右边常数项） 同样有约束条件右边常数值的百分之一百法则：对于所有变化的约束条件右边常数值，当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时，则其对偶价格不变。其中bj 的允许增加(减少)百分比的 定义同Ci 的允许增加(减少) 百分比一样：为bj 的增加 量(减少量)除以bj的允许 增加量(减少量)的值。 并不难

28 百分之一百法则（约束条件右边常数项） 若： 设备台时数： (315-300)/(325-300)=15/25=60％，
设备台时数从300台时增加为315台时， 原料A从400千克减少到390千克， 原料B从250千克减少到240千克，这样可以得到它们的允 许增加(减少)百分比。因为： 设备台时数： ( )/( )=15/25=60％， 原料A： ( )/( )=10/50=20％， 原料B： ( )/( )=10/50=20％。

29 百分之一百法则（约束条件右边常数项） 结论：
所以它们的允许增加百分比与允许减少百分 比之和为60％+20％+20％=100％，则可知 此线性规划的对偶价格不变。 因为设备台时数从300台时增加为315台时， 而原料A从400千克减少到390千克，原料B 从250千克减少到240千克，所以从对偶价格 可知，导致的利润变化数额为： 50×15-0×10-50×10= 250(元)， 则最大利润增加了250元，为27750元。

30 使用百分之一百法则注意事项 当允许增加量（允许减少量）为无穷大时， 则对任意增加量（减少量），其允许增加 （减少）百分比均看作零。
如，在表3- 4中，约束条件2的常数项变动 范围为350至+∞, 如果原料A从400增加 到410，则相当于 （ ）/（无穷大- 400)=0. 当允许增加量(减少量)为0时，则对于任一 个增加量(减少量)，其允许增加(减少)百分 比都看成无穷大（相当于该变量不能增加或 减少）。

31 使用百分之一百法则注意事项 百分之一百法则是充分条件，但非必 要条件。也就是说当其允许增加和减 少百分比之和不超过100％时，其最优 解或对偶价格不变，但是当其允许增加 和减少百分比之和超过100％时，我们 并不知道其最优解或对偶价格变还是不 变。 百分之一百法则不能用于目标函数决 策变量系数和约束条件右边常数同时 变化的情况。如同时发生变化，只能 重新求解。

32 例2 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)

33 例2 ：对偶价格分析 目标函数：min f = 2x1 + 3x2约束条件： x1 + x2 ≥ 350 两种原料的吨数，对偶价格 -4
x1 ≥ 原料A的吨数，对偶价格 0 2 x1 + x2 ≤ 加工时数，对偶价格 1 x1 , x2 ≥ 0 x1 + x2 = 351 约束条件（1）改变时， x1 + x2 = 351， 此时最优解为 2x1 + x2 = 600 x1 =249， x2 = 102，目标函数最小值为804， 总成本增加了4万。 对偶价格为负，增加常数项，导致目标函数取值变坏 约束条件（3）改变时， 2 x1 + x2 =601，最优解为x1 =251， x2 = 99，目标函数最小值为799，成本降低 对偶价格为正，增加常数项，导致目标函数取值变好

34 例2 ：目标函数系数范围分析 目标函数：min f = 2x1 + 3x2约束条件： x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0 一般情况： z = c1 x1 + c2 x2写成斜截式： x2 = − (c1 / c2 ) x1 + z / c2，则目标函数等值线的斜 率为− (c1 / c2 ) 。

35 当-1 ≤ - (c1 / c2 ) ≤ 0（*） 时，原最优解仍是最优解
例2 当-1 ≤ - (c1 / c2 ) ≤ 0（*） 时，原最优解仍是最优解 目标函数系数范围： 变量 下限 当前值 上限 X 无下限 X 无上限 100 200 300 400 500 600 x2 当固定C1=2时，C2的范围为2——∞ 当固定C2=3时，C1的范围为-∞——3 2x1 + 3 x2=1200 Q x1 (250,100)

36 例2:常数项b1（对偶价格-4） x2 x1 Q x1 + x2 ≥ 350 对偶价格 -4 x1 ≥ 125 对偶价格 0
100 200 300 400 500 600 x2 2x1 + x2=600 常数项范围： 约束 下限 当前值 上限 (125,350) x1 + x2 ≥ 对偶价格 -4 x1 ≥ 对偶价格 0 2 x1 + x2 ≤ 对偶价格 1 (250,100) Q x1 (300,0)

37 例2:常数项b2（对偶价格为0） x2 x1 Q x1 + x2 ≥ 350 对偶价格 -4 x1 ≥ 125 对偶价格 0
100 200 300 400 500 600 x2 常数项范围： 约束 下限 当前值 上限 无下限 x1 + x2 ≥ 对偶价格 -4 x1 ≥ 对偶价格 0 2 x1 + x2 ≤ 对偶价格 1 (250,100) Q x1 (300,0)

38 例2:常数项b3（对偶价格为1） x2 x1 Q x1 + x2 ≥ 350 对偶价格 -4 x1 ≥ 125 对偶价格 0
100 200 300 400 500 600 x2 常数项范围： 约束 下限 当前值 上限 x1 + x2 ≥ 对偶价格 -4 x1 ≥ 对偶价格 0 2 x1 + x2 ≤ 对偶价格 1 (125,225) Q x1 (350, 0) (300,0)

39 其它需要说明的问题 影子价格：当约束条件中的常数项增加一个 单位时，最优目标函数值增加的数量，对偶 价格对应改进的数量。
“管理运筹学”软件可以解决含有 100 个变量 50 个约束方程的线性规划问题，可以解决 工商管理中大量的问题。如果想要解决更大 规模的线性规划问题，可以使用由芝加哥大 学的 L.E.Schrage 开发的 LINDO的微型计 算机版本 LINDO/PC。 经济学上除了讲对偶价格，还常常讲影子价格，其定义为 在求目标函数最大值时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，此时影子价格等于对偶价格； 在求目标函数最小值时，改进的数量就是减少的数量，此时影子价格即为负的对偶价格。

40 本章作业 1、4、5

41 习题1 s1=0，s2=330，s3=0，s4=15 （1）最优解为 此时最优值为：500*150+400*70=103000
x1 =150 （1）最优解为 此时最优值为：500* *70=103000 (2)没用完的加工时数，即松弛变量为 （3）各约束条件的对偶价格为50,0,200,0 增加1个工时，可增加利润的数量 （4）选择第三车间，因为增加1个工时，带来的利润 最多 x2 =70 s1=0，s2=330，s3=0，s4=15

42 习题1 - (c1 / c2 ) ≤-1时，最优解不变， 即c1 / c2 ≥1 当c2=400时， c1 ≥400
没变，在上限范围内

43 习题1 （8）第一个约束条件常数项的上限为440，所以提高 到400，对偶价格不变 （400-300）*50=5000
（9）第三个约束条件的上限是460，增加量超过了上 限，对偶价格不一定如何变换，所以不能轻易的得出 结论 （10）目标函数系数同时发生变化， ( )/( )+( )/( )=3/4 最优解不发生变化 （11）( )/( )+( )/( )<1 对偶价格不发生变化