2011年管理运筹学总复习 (1)

学期总评=平时成绩40%+期末成绩60%

复习提纲一、模型建立 二、线性规划问题、对偶问题、对偶 理论、单纯形法及其灵敏度分析 三、运输问题 四、整数规划 五、动态规划 六、图与网络 七、矩阵对策

第一部分 模型建立掌握工商管理领域实际线性规划问 题的数学模型的建立方法和步骤，

特别是整数规划模型(重点是0,1变量)和决策问题模型的建立

(数学模型的三要素)

第二部分 线性规划问题、对偶问题、 对偶理论、单纯形法及其灵敏度分析

1、能将一般线性规划模型化为标准形式； 2、理解线性规划基本概念：可行解、可行域、 最优解、退化解、基解、基可行解、基矩阵、 可行基、最优基、基变量、非基变量、基向量、 非基向量等； 3、掌握初始基可行解的确定方法，单纯形表的 最优性检验与解类型(唯一最优解、无穷多最 优解、无界解、无可行解)的判别方法，基变 换与迭代方法；

第二部分 线性规划问题、对偶问题、 对偶理论、单纯形法及其灵敏度分析4、掌握线性规划问题的求解方法： (1)单纯形表与计算步骤； (2)处理人工变量的大M法； (3)对偶单纯性法(采用该法的前

提条件以及对偶单纯形法的步骤);

第二部分 线性规划问题、对偶问题、 对偶理论、单纯形法及其灵敏度分析5、了解单纯形法的矩阵描述； 理解对 偶问题和原问题的内在关系，特别是 从单纯形表格上找出二者解的情况； 6、能直接写出线性规划模型(对称形 和非对称形)的对偶模型 7、从单纯形表格上充分理解对偶性质 (弱对偶性、强对偶性、互补松弛性)

第二部分 线性规划问题、对偶问题、 对偶理论、单纯形法及其灵敏度分析8、结合实际问题熟练掌握单纯性表的灵 敏度分析及其经济解释： 价值系数的灵敏度分析 资源拥有量的灵敏度分析 技术系数的灵敏度分析 增加和减少产品的灵敏度分析 增加和减少约束条件的灵敏度分析 影子价格、机会成本、市场价格、吸引力

第三部分 运输问题1、理解什么是运输问题，能够建立实际运输 问题的数学模型； 2、掌握产销平衡运输问题的表上作业法； 3、能够将产销不平衡的运输问题转换为产销 平衡的运输问题进行求解。

第四部分 整数规划1、了解什么是整数规划问题； 2、理解分枝定界法，掌握分枝、定界、剪枝； 3、理解0-1型整数规划问题，会建立0-1模型

4、会用匈牙利法求解指派问题(标准和非标准)

第五部分 动态规划1、了解动态规划的基本概念 2、掌握动态规划模型的建立和求解方法； 3、理解动态规划和静态规划的关系； 4、能求解最短路线问题、资源分

配问题。

第六部分 图与网络分析1、了解图与网络的基本概念； 2、理解树、最小生成树的概念；

3、能求解最短路问题、最小树问题、最大流问题、最小费用最大流问题。

第七部分 对策论1、掌握对策问题的三要素(会建立对策模型)2、能判断矩阵对策是否存在纯策略意义下的平衡解

(鞍点),并求解；3、能求解矩阵对策的混合策略；将矩阵对策表示为

一对互为对偶的对称型线性规划问题。4、能利用优超原则化简矩阵，进而图解法求解混合 策略

管理运筹学总复习典型案例

单纯形法的灵敏度分析与对偶Cj0 CB XB CN XN N 0 XS I

XS

b

B

jCj

CB

CN

0

初 始 单 纯 形 表最 终 单 纯 形 表

CB XB

CN XN

0 XS

CB

XB j

B-1b

I0

B-1NCN- CB B-1N

B-1 - CB B-1

一、灵敏度分析典型例题佳美公司计划制造Ⅰ、Ⅱ两种产品，已知各制造一个单 位产品时，分别占用的设备A、B的台时、调试时间、 每天设备A、B的台时、调试工序可用于这两种产品的 能力及各售出一单位时的获利情况，如表所示。产品 资源 设备A(h) 设备B(h) 调试工序(h) 利润(百元) Ⅰ 0 6 1 2 Ⅱ 5 2 1 1 每天可 用能力 15 24 5

1、问应怎样组织生产才能使总利润最多？

2、如果产品Ⅰ的利润降至1.5百元/单位，而产品Ⅱ的利润增至2百元/单元时，最优生产计划有何变化？ 3、如果产品Ⅰ的利润不变，则产品Ⅱ的利润在什么范围内变化时，该公司的

最优生产计划将不发生变化？4、若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时， 分析公司最优计划的变化；

5、若设备A和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变. 6、设该公司又计划推出新产品Ⅲ,生产一单位产品Ⅲ,所需设备A、B及调

试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3百元/单位， 试分析该新产品是否值得投产；如投产对该公司的最优生产计划有何变化 。

7、若产品Ⅱ每单位需设备A、B和调试工时8小时、4小时、1

小时，该产品的利润变为3百元/单位，试重新确定该公司最优生产计划. 8、 假设产品Ⅰ、Ⅱ经调试后，还需经过一道环境试验工序， 产品Ⅰ每单位须环境试验3小时，产品Ⅱ每单位须2小时，又环 境试验工序每天生产能力为12小时，试分析增加该工序后的佳

美公司最优生产计划.9、假设产品Ⅰ、Ⅱ经调试后，还需经过一道环境试验工序， 产品Ⅰ每单位须环境试验3小时，产品Ⅱ每单位须2小时，又环 境试验工序每天生产能力至少为15小时，试分析增加该工序后 的佳美公司最优生产计划.

解：设分别表示Ⅰ、Ⅱ两种产品的生产数量，可建

立如下线性规划模型：

maxZ=2x1+x2 5x2≤15 s.t.,

maxZ=2x1+x2+0x3 +0x4 +0x5 5x2+x3 s.t. 6x1+2x2 x1+x2 +x4 =15 =24 +x5 = 5 Y1 Y2 y3

6x1+2x2 ≤24 x1+x2 ≤5 x1,x2 ≥0

x1,x2 ,x3 ,x4,x5 ≥0

CB CB0 0

2b

1 x2 5 2 1 0 0 0 1 0

0 x3 1 0 0 0 1 0 0 0

0 x4 0 1 0 -1/4 5/4 1/4 -1/4 -1/4

0 x5 0 0 1 -1/2 -15/2 -1/2 3/2 -1/2终 表 初 表

XBx3 x4

x1 0 6 1 0

15 24 5

0

x5 j 0 x3 x1 x2 j

15/2 7/2 3/2

0 1 0 0

2 1

可见原问题具有唯一最优解： x *

(7 / 2,3 / 2,15/ 2,0,0)T z * 8.5

思 考 ： 对 偶 问 题 的 最 优 解 和 最 优 值 ？

2、如果产品Ⅰ的利润降至1.5百元/单位，而产品Ⅱ的利

润增至2百元/单元时，最优生产计划有何变化？ 将产品Ⅰ、Ⅱ的利润变化直接反映到最终单纯形表中得表，CB CB 0 00 1.5 2 1 2 XB x3 b

Cj

CB

1.5 2 x1

2 1 XB x2B CB

0 X 0 x 3 N x4

CN

0XS

0 x5

j

X15/2 b0 S7/2 1

00

10

N CN

5/41/4

I -15/2

z* 9

x1 x2

-1/2

0

初 始 单 纯 形 表

最 终 0 0 0 -1/4 -1/2 X X X j 0 0B 0 -9/4 N1/8 S 单 CB -1N -1 纯 -1b X I B B B B 因非基变量的检验数大于零，故需继续用单纯形法迭 形 代计算 j -1 -1 0 CN- CB B N - CB B 表

3/2 C j

0

C1 B

0

CN -1/4

3/2 0

CB CB 0 XB x3 b

1.5 x1 0 1 0 0 6 0

2 x2 0 0 1 0 0

0 x3 1 0 0 0 4/5

0 x4

0 x5 6 14

15/2 7/2 3/2

5/4 -15/2 1/4 -1/4 1/8 1 -1/2 3/2 -9/4 -6

1.52

x1x2 j

---

0 1.5

x4x1 x2 j

23

10

01

-1/51/5

00

10

2

0

0

-1/10

0

-3/2

可见变化后的问题具有唯一最优解

X*=(2,3)T

z 9*

本文来源：https://www.bwwdw.com/article/3nu1.html