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

运筹学课件

第三章 线性规划问题的 计算机求解§1 “管理运筹学”软件的操作方法 §2 “管理运筹学”软件的输出信息分析

1

管

理

运

筹

学

运筹学课件

第三章 线性规划问题的计算机求解随书软件为“管理运筹学”2.0版 Window版 随书软件为“管理运筹学”2.0版(Window版), 是1.0版(DOS版)的升级版。它包括：线性规划、运输 1.0版 DOS版 的升级版。它包括：线性规划、 问题、整数规划( 问题、整数规划(0-1整数规划、纯整数规划和混合整 整数规划、 数规划)、目标规划、对策论、最短路径、最小生成树、 数规划)、目标规划、对策论、最短路径、最小生成树、 )、目标规划 最大流量、最小费用最大流、关键路径、存储论、 最大流量、最小费用最大流、关键路径、存储论、排队 论、决策分析、预测问题和层次分析法，共15个子模块。 决策分析、预测问题和层次分析法， 15个子模块。 个子模块

管

理

运

筹

学

运筹学课件

§1 “管理运筹学”软件的操作方法1.软件使用演示：(演示例1 1.软件使用演示：(演示例1) 软件使用演示：(演示例 第一步：点击“开始”->“程序”-> “管理运筹 第一步：点击“开始” >“程序” “管理运筹 程序 2.0”,弹出主窗口。 学2.0”,弹出主窗口。例1. 目标函数： Max z = 50 x1 + 100 x2

约束条件： s.t. x1 + 2 x1 + x2 x2 x2 x1 x2 ≤ ≤ ≤ ≥ ≥ 300 400 250 0 0 (A) (B) (C) (D) (E)3

管

理

运

筹

学

运筹学课件

§1 “管理运筹学”软件的操作方法第二步：选择所需子模块，点击主窗口中的相应按钮。 第二步：选择所需子模块，点击主窗口中的相应按钮。 本题中选用“线性规划”方法。点击按钮弹出如下界面： 本题中选用“线性规划”方法。点击按钮弹出如下界面：

4

管

理

运

筹

学

运筹学课件

§1 “管理运筹学”软件的操作方法第三步：点击“新建”按钮，输入数据。本题中共 第三步：点击“新建”按钮，输入数据。 个变量， 个约束条件 目标函数取MAX。点击 个约束条件， 有2个变量，3个约束条件，目标函数取 个变量 。 “确定”后，在表中输入Cj,bi和aij等值，并确定变量 等值， 确定” 在表中输入 的正负约束。 的正负约束。 输入数值后的界面如下。 输入数值后的界面如下。

5

管

理

运

筹

学

运筹学课件

6

管

理

运

筹

学

运筹学课件

§1 “管理运筹学”软件的操作方法第四步：点击“解决”按钮，得出计算结果。 第四步：点击“解决”按钮，得出计算结果。本题的运 行结果界面如下。 行结果界面如下。

7

管

理

运

筹

学

运筹学课件

§2 “管理运筹学”软件的输出信息分析第五步：分析运行结果。 第五步：分析运行结果。 本题中目标函数的最优值是27500,x1=50, x2=250。

, 本题中目标函数的最优值是 。 相差值表示相应的决策变量的目标系数需要改进的数 量，使得决策变量为正值，当决策变量已为正数时， 使得决策变量为正值，当决策变量已为正数时， 相差数为零。 相差数为零。

8

管

理

运

筹

学

运筹学课件

松弛/剩余变量的数值表示还有多少资源没有被使 松弛 剩余变量的数值表示还有多少资源没有被使 用。如果为零，则表示与之相对应的资源已经全部 如果为零， 用上。 用上。 对偶价格表示其对应的资源每增加一个单位， 对偶价格表示其对应的资源每增加一个单位，将增 加多少个单位的最优值。 加多少个单位的最优值。 目标函数系数范围表示最优解不变的情况下， 目标函数系数范围表示最优解不变的情况下，目标 函数的决策变量系数的变化范围。 函数的决策变量系数的变化范围。当前值是指当前 的最优解中的系数取值。 的最优解中的系数取值。9

管

理

运

筹

学

运筹学课件

常数项范围是指约束条件的右端常量。 常数项范围是指约束条件的右端常量。上限值和下 限值是指当约束条件的右端常量在此范围内变化时， 限值是指当约束条件的右端常量在此范围内变化时， 与其对应的约束条件的对偶价格不变。 与其对应的约束条件的对偶价格不变。当前值是指 现在的取值。 现在的取值。 以上计算机输出的目标函数系数和约束条件右 边值的灵敏度分析都是在其他系数值不变， 边值的灵敏度分析都是在其他系数值不变，只有一个 系数变化的基础上得出的！ 系数变化的基础上得出的！

10

管

理

运

筹

学

运筹学课件

§2 “管理运筹学”软件的输出信息分析

当有多个系数变化时， 当有多个系数变化时，需要进一步讨论百分之一百法则： 百分之一百法则：对于所有变化的目标函 数资源系数(约束条件右边常数值),当其所 数资源系数(约束条件右边常数值),当其所 ), 有允许增加的百分比与允许减少的百分比 之和不超过100%时，最优解不变(对偶价格不 时 最优解不变( 之和不超过 变，最优解仍是原来几个线性方程的解)。 最优解仍是原来几个线性方程的解)11

管

理

运

筹

学

运筹学课件

* 允许增加量 = 上限 - 现在值c1 的允许增加量为 100 - 50 = 50 b1 的允许增加量为 325 - 300 = 25 * 允许减少量 = 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50 b3 的允许减少量为 250 - 200 = 50 * 允许增加的百分比 = 增加量 / 允许增加量 * 允许减少的百分比 = 减少量 / 允许减少量12

管

理

运

筹

学

运筹学课件

§2 “管理运筹学”软件的输出信息分析例： c1 变为 74 , c2 变为 78, 则 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%,故最优解不变。 ,故最优解不变。 b1 变为

315 , b3 变为 240, 则 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%,故对偶价格不变(最优解仍是 ， 对偶价格不变( 原来几个线性方程的解) 原来几个线性方程的解)。

13

管

理

运

筹

学

运筹学课件

在使用百分之一百法则进行灵敏度分析时，要注意： 在使用百分之一百法则进行灵敏度分析时，要注意：1)当允许增加量(允许减少量)为无穷大时，则对任意增加 当允许增加量(允许减少量)为无穷大时，

量(减少量),其允许增加(减少)百分比均看作0; 减少量),其允许增加(减少)百分比均看作0 ),其允许增加 2)百分之一百法则是充分条件，但非必要条件；也就是 百分之一百法则是充分条件，但非必要条件； 说超过100%并不一定变化； 说超过100%并不一定变化； 100%并不一定变化 3)百分之一百法则不能用于目标函数决策变量系数和约 束条件右边常数值同时变化的情况。这种情况下， 束条件右边常数值同时变化的情况。这种情况下，只有 重新求解。 重新求解。

14

管

理

运

筹

学

运筹学课件

§2 “管理运筹学”软件的输出信息分析下面用“管理运筹学”软件来分析第二章的例2 下面用“管理运筹学”软件来分析第二章的例2,其 数 …… 此处隐藏：1639字，全部文档内容请下载后查看。喜欢就下载吧 ……