当前位置：文档库 › 《运筹学》复习参考资料

《运筹学》复习参考资料

资料加工、整理人——杨峰（函授总站高级讲师）

要求掌握的各部分知识点

第一部分线性规划问题的求解（相当于教材的第一章）

——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法

第二部分动态规划问题的求解（相当于教材的第三章）

——重要算法：图上标号法

第三部分网络分析问题的求解（相当于教材的第四章）

——重要算法：破圈法、TP标号法、寻求网络最大流的标号法

第四部分存储论简介（相当于教材的第七章）

※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。

第一部分线性规划问题的求解

一、两个变量的线性规划问题的图解法：

㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。

定义：达到目标的可行解为最优解。

㈡图解法：

图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；

2、确定可行解域；

3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；

注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。

4、确定最优解及目标函数值。

㈢参考例题：（只要求下面这些有唯一最优解的类型）

例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：

问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？

（此题也可用“单纯形法”或化“对偶问题”用大M法求解）

解：设x 1、x 2为生产甲、乙产品的数量。

max z = 70x 1+30x 2 s.t.

???????≥≤+≤+≤+0

72039450555409321212121x x x x x x x x ，

可行解域为oabcd0，最优解为b 点。由方程组

???=+=+72039450

5521

21x x x x 解出x 1=75，x 2=15 ∴X *

=???

??21x x =（75，15）

∴max z =Z *= 70×75+30×15=5700

⑴

⑵ ⑶ ⑷ ⑸、⑹

max z = 6x 1+4x 2 s.t.

???????≥≤≤+≤+0781022122121x x x x x x x ，解：

可行解域为oabcd0，最优解为b 点。由方程组

???=+=+810

121x x x x 解出x 1=2，x 2=6 ∴X *

=???

??21x x =（2，6）T

∴max z = 6×2+4×6=36

⑴

⑵ ⑶ ⑷ ⑸、⑹

min z =－3x 1+x 2 s.t.

?????

????≥≤+≥+≤≤08

2125234212

12121

x x x x x x x x ，解：

可行解域为bcdefb ，最优解为b 点。

由方程组???=+=1252421

1x x x 解出x 1=4，x 2=54

∴X *=???

??21x x =（4，54）T

∴min z =－3×4+5

4=－1151

⑴

⑵ ⑶ ⑷ ⑸ ⑹、⑺

二、标准型线性规划问题的单纯形解法：㈠一般思路：

1、用简单易行的方法获得初始基本可行解；

2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；

3、根据θL 规则确定改进解的方向；

4、根据可能改进的方向进行迭代得到新的解；

5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。

㈡具体做法（可化归标准型的情况）：

设已知

max z = c 1x 1+ c 2x 2+…+ c n x n

s.t.

????

??=≥≤+++≤+++≤+++n j x b

x a x a x a b x a x a x a b x a x a x a j m

n mn m m n n n n ，，，，...210 (2)

211222221211

1212111 对第i 个方程加入松弛变量x n+i ，i =1，2，…，m ，得到

??=≥=++++=++++=+++++++n j x b x x a x a x a b x x a x a x a b x x a x a x a j m m n n mn m m n n n n n n ，，，，...210 (22112)

222221211

11212111 列表计算，格式、算法如下：

注①： z j =c n+1 a 1j + c n+2 a 2j +…+ c n+m a mj =

∑=+m

i ij i

n a c

，（j=1，2，…，n+m ）

σj =c j －z j ,当σj ≤0时，当前解最优。

注②：由max{σj }确定所对应的行的变量为“入基变量”；

由θL =?

?>0min ik ik i i

a a

b 确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为0。

例1：用单纯形法求解（本题即是本资料P2“图解法”例1的单纯形解法；也可化“对

偶问题”求解）

max z =70x 1+30x 2 s.t.

???????≥≤+≤+≤+0

7203945055540

9321212121x x x x x x x x ，解：加入松弛变量x 3，x 4，x 5，得到等效的标准模型：

max z =70x 1+30x 2+0 x 3+0 x 4+0 x 5

s.t.

????=≥=++=++=++5,...,2,1,0720394505554093521421321j x x x x x x x x x x j 列表计算如下：

∴X *=（75，15，180，0，0）T ∴max z =70×75+30×15=5700

例2：用单纯形法求解

max z =7x 1+12x 2 s.t.

???????≥≤+≤+≤+0

300103200543604921212121x x x x x x x x ，解：加入松弛变量x 3，x 4，x 5，得到等效的标准模型：

max z =7x 1+12x 2+0 x 3+0 x 4+0 x 5 s.t.

???

?=≥=++=++=++5,...,2,1,0300103200543604952

1421321j x x x x x x x x x x j 列表计算如下：

∴X*=（20，24，84，0，0）T

∴max z =7×20+12×24=428

三、非标准型线性规划问题的解法：

1、一般地，对于约束条件组：

若为“≤”，则加松弛变量，使方程成为“＝”；

若为“≥”，则减松弛变量，使方程成为“＝”。

我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理：

由目标函数min z=

∑=n

j j

j x

c 1

变成等价的目标函数max （－z ）=

∑=-n

j j

x c 1

)(

令－z=z /，∴min z=－max z /

2、等式约束——大M 法：

通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为－M ，M 是很大的正数，从原理上理解又称为“惩罚系数”。（课本P29）

类型一：目标函数仍为max z ，约束条件组≤与＝。

例1：max z =3x 1+5x 2 s.t.

???????≥=+≤≤0

18231224212121

x x x x x x ，解：加入松弛变量x 3，x 4，得到等效的标准模型：

max z =3x 1+5x 2 s.t.

????=≥=+=+=+4,3,2,1,018231224214231j x x x x x x x j 其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量x 5，得到： max z =3x 1+5x 2－M x 5

s.t. ??

????=≥=++=+=+5,...,2,1,01823122452142

31j x x x x x x x x j

单纯形表求解过程如下：

－3/2

－M －1

∴X *=（2，6，2，0）T ∴max z =3×2+5×6=36

类型二：目标函数min z ，约束条件组≥与＝。

例2：用单纯形法求解

min z =4x 1+3x 2 s.t.

???

??≥≥+≥+0122316422

12121x x x x x x ，解：减去松弛变量x 3，x 4，并化为等效的标准模型：

max z / =－4x 1－3x 2 s.t.

???

??=≥=-+=-+4,3,2,1,01223164242

1321j x x x x x x x j

增加人工变量x 5、x 6，得到：

max z / =－4x 1－3x 2－Mx 5－Mx 6 s.t

???

??=≥=+-+=+-+6,...,2,1,012231642642

15321j x x x x x x x x x j

单纯形表求解过程如下：

∴X*=（2，3，0，0）T

∴min z =－max z/ =－（－17）=17

四、对偶问题的解法：什么是对偶问题？

1、在资源一定的条件下，作出最大的贡献；

2、完成给定的工作，所消耗的资源最少。

引例（与本资料P2例1 “图解法”、P7例1 “单纯形法”同）：某工厂生产甲、乙两种产品，这些产品均需在A 、B 、C 三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表：

问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？解：原问题——

设x 1、x 2为生产甲、乙产品的数量。

max z = 70x 1+30x 2 s.t.

???????≥≤+≤+≤+0

72039450555409321212121x x x x x x x x ，将这个原问题化为它的对偶问题——

设y 1、y 2、y 2分别为设备A 、B 、C 单位工时数的加工费。

min w = 540y 1+450y 2+720y 3 s.t.

???

??=≥≥++≥++32103035970953321321，，，i y y y y y y y i

用大M 法，先化为等效的标准模型：

max w / =－540y 1－450y 2－720y 3 s.t.

???

??=≥=-++=-++5,...,2,1,0303597095353

214321j y y y y y y y y y j

增加人工变量y 6、y 7，得到：

max z / =－540y 1－450y 2－720y 3－My 6－My 7 s.t

???

??=≥=++-++=+-++5,...,2,1,03035970953753

2164321j y y y y y y y y y y y j

大M 法单纯形表求解过程如下：

∴该对偶问题的最优解是y *

=（0，2，320

，0，0）T

最优目标函数值min w =－（－5700）=5700

五、运输规划问题：

运输规划问题的特殊解法——“表上作业法”解题步骤：

1、找出初始调运方案。即在(m×n)产销平衡表上给出m+n-1个数字格。（最小元素法）

2、（对空格）求检验数。判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。（闭回路法）

3、对方案进行改善，找出新的调运方案。（根据检验结果选择入基变量，用表上闭回路法调整——即迭代计算，得新的基本可行解）

4、重复2、3，再检验、再迭代，直到求得最优调运方案。

类型一：供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）引例：某钢铁公司有三个铁矿和四个炼铁厂，铁矿的年产矿石量分别为100万吨、80万吨和50万吨，炼铁厂年需矿石量分别为50万吨、70万吨、80万吨和30万吨，这三个铁矿与四个炼铁厂的距离如下：

问：？解：用“表上作业法”求解。

⑴先用最低费用法（最小元素法）求此问题的初始基础可行解：

∴初始方案：

Z=15×20+3×80+70×30+8×20+20×30+3×50=3550（吨.公里） ⑵对⑴的初始可行解进行迭代（表上闭回路法），求最优解：

80 B 1

B 3

A 1

B 2 20 30 30

B 1 B 3

A 2

B 2

A 3

用表上闭回路法调整后，从上表可看出，所有检验数σ＜0，已得最优解。 ∴最优方案：

Z=15×20+3×80+8×50+20×30+12×30+3×20=1960（吨.公里）

解法分析：①如何求检验数并由此确定入基变量？有数字的空格称为“基格”、打×的空格称为“空格”，标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点，出发点算0故为偶点。找出所有空格的闭回路后计算它们的检验数∑∑-=

偶点

奇点

ij ij c

c σ，必须ij σ≤0，才得到最优

解。否则，应选所有σ中正的最大者对应的变量x j 为入基变量进行迭代（调整）。②检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇点均减去奇点中的最小运量。③重复以上两步，再检验、再调整，直到求得最优运输方案。

类型二：供求不平衡的运输规划问题

80 B 1

B 3

A 1 50

B 2

B 4

A 2

B 1

B 2

A 3