《运筹学》复习参考资料知识点及习题.doc

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

一、两个变量的线性规划问题的图解法：
㈠概念准备：
定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。
定义：达到目标的可行解为最优解。
㈡图解法：
图解法采用直角坐标求解：x1——横轴；x2——竖轴。
1、将约束条件（取等号）用直线绘出；
2、确定可行解域；
3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；
注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。
4、确定最优解及目标函数值。
㈢参考例题：（只要求下面这些有唯一最优解的类型）
例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：
品
产
耗
消
备
设

A B C
利润
（万元）
甲
乙
3 5 9
9 5 3
70
30
有效总工时
540 450 720
——
问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？
（此题也可用“单纯形法”或化“对偶问题”用大M法求解）
解：设x1、x2为生产甲、乙产品的数量。
⑴
max z = 70x1+30x2
⑵
s.t.
⑸、⑹
⑷
⑶

可行解域为oabcd0，最优解为b点。
由方程组
解出x1=75，x2=15
∴X*==（75，15）T
∴max z =Z*= 70×75+30×15=5700
例2：用图解法求解
⑴
max z = 6x1+4x2
⑵
s.t.
⑸、⑹
⑷
⑶

解：

可行解域为oabcd0，最优解为b点。
由方程组
解出x1=2，x2=6
∴X*==（2，6）T
∴max z = 6×2+4×6=36
例3：用图解法求解
⑴
min z =－3x1+x2
s.t.
⑵
⑶
⑷
⑸
⑹、⑺

解：

可行解域为bcdefb，最优解为b点。
由方程组 解出x1=4，x2=
∴X*==（4，）T
∴min z =－3×4+=－11
二、标准型线性规划问题的单纯形解法：
㈠一般思路：
1、用简单易行的方法获得初始基本可行解；
2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；
3、根据θL规则确定改进解的方向；
4、根据可能改进的方向进行迭代得到新的解；
5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。
㈡具体做法（可化归标准型的情况）：
设已知
max z = c1x1+ c2x2+…+ cnxn
s.t.

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

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

CB
XB
b
c1
c2
…
cn+m
θL
x1
x2
…
xn+m
cn+1
xn+1
b1
a11
a12
…
a1 n+m

c n+2
xn+2
b2
a21
a22
…
a2 n+m

.
.
.
.
.
.
.
.
.
…
…
…
…

cn+m
xn+m
bn
am1
am2
…
am n+m

z1
z2
…
zn+m

σ1
σ2
…
σn+m

注①： zj =cn+1 a1j+ cn+2 a2j +…+ cn+m amj=，（j=1，2，…，n+m）
σj =cj－zj ,当σj ≤0时，当前解最优。
注②：由max{σj}确定所对应的行的变量为“入基变量”；
由θL=确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为0。
例1：用单纯形法求解（本题即是本资料P2“图解法”例1的单纯形解法；也可化“对偶问题”求解）
max z =70x1+30x2
s.t.

解：加入松弛变量x3，x4，x5，得到等效的标准模型：
max z =70x1+30x2+0 x3+0 x4+0 x5
s.t.

列表计算如下：
CB
XB
b
70
30
0
0
0
θL
x1
x2
x3
x4
x5
0
x3
540
3
9
1
0
0
540/3 =180
0
x4
450
5
5
0
1
0
450/5 =90
0
x5
720
（9）
3
0
0
1
720/9 =80

0
0
0
0
0

70↑
30
0
0
0

0
x3
300
0
8
1
0
- 1/3
300/8 =37.5
0
x4
50
0
（10/3）
0
1
- 5/9
50/10/3 =15
70
x1
80
1
1/3
0
0
1/9
80/1/3 =240

70
70/3
0
0
70/9

0
20/3↑
0
0
－70/9

0
x3
180
0
0
1
－12/5
1

30
x2
15
0
1
0
3/10
- 1/6

70
x1
75
1
0
0
- 1/10
1/6

5700
70
30
0
2
20/3

0
0
0
-2
－20/3

∴X*=（75，15，180，0，0）T
∴max z =70×75+30×15=5700
例2：用单纯形法求解
max z =7x1+12x2
s.t.

解：加入松弛变量x3，x4，x5，得到等效的标准模型：
max z =7x1+12x2+0 x3+0 x4+0 x5
s.t.

列表计算如下：

CB
XB
b
7
12
0
0
0
θL
x1
x2
x3
x4
x5
0
x3
360
9
4
1
0
0
360/4 =90
0
x4
200
4
5
0
1
0
200/5 =40
0
x5
300
3
（10）
0
0
1
300/10 =30

0
0
0
0
0

7
12↑
0
0
0

0
x3
240
78/10
0
1
0
- 2/5
240/78/10 =2400/78
0
x4
50
（5/2）
0
0
1
- 1/2
50/5/2 =20
12
x2
30
3/10
1
0
0
1/10
30/3/10 =100

18/5
12
0
0
6/5

17/5↑
0
0
0
－6/5

0
x3
84
0
0
1
－78/25
29/25

7
x1
20
1
0
0
2/5
- 1/5

12
x2
24
0
1
0
－ 3/25
4/28

428
7
12
0
34/25
11/35

0
0
0
－34/25
－11/35

∴X*=（20，24，84，0，0）T
∴max z =7×20+12×24=428
三、非标准型线性规划问题的解法：
1、一般地，对于约束条件组：
若为“≤”，则加松弛变量，使方程成为“＝”；
若为“≥”，则减松弛变量，使方程成为“＝”。
我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理：
由目标函数min z=变成等价的目标函数max（－z）=
令－z=z/，∴min z=－max z/
2、等式约束——大M法：
通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为－M，M是很大的正数，从原理上理解又称为“惩罚系数”。（课本P29）
类型一：目标函数仍为max z，约束条件组≤与＝。
例1：max z =3x1+5x2
s.t.

解：加入松弛变量x3，x4，得到等效的标准模型：
max z =3x1+5x2
s.t.

其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量x5，得到： max z =3x1+5x2－Mx5
s.t.
单纯形表求解过程如下：
CB
XB
b
3
5
0
0
－M
θL
x1
x2
x3
x4
x5
0
x3
4
（1）
0
1
0
0
4/1 =4
0
x4
12
0
2
0
1
0
——
－M
x5
18
3
2
0
0
1
18/3 =6

－3M
－2M
0
0
－M

3M＋3↑
5＋2M
0
0
0

3
x1
4
1
0
1
0
0
——
0
x4
12
0
2
0
1
0
12/2 =6
－M
x5
6
0
（2）
－3
0
1
6/2 =3

3
－2M
3＋3M
0
－M

0
5↑
－3－3M
0
0

3
x1
4
1
0
1
0
0
4/1 =4
0
x4
6
0
0
（3）
1
－1
6/3 =2
5
x2
3
0
1
－3/2
0
1/2
3/(－2/3) =－9/2

3
5
－9/2
0
5/2

0
0
9/2↑
0
－M－5/2

3
0
5
x1
2
1
0
0
－1/3
1/3

x3
2
0
0
1
1/3
－1/3

x2
6
0
1
0
1/2
0

36
3
5
0
3/2
1

0
0
0
－3/2
－M－1

∴X*=（2，6，2，0）T
∴max z =3×2+5×6=36
类型二：目标函数min z，约束条件组≥与＝。
例2：用单纯形法求解
min z =4x1+3x2
s.t.

解：减去松弛变量x3，x4，并化为等效的标准模型：
max z/ =－4x1－3x2
s.t.

增加人工变量x5、x6，得到：
max z/ =－4x1－3x2－Mx5－Mx6
s.t

单纯形表求解过程如下：

CB
XB
b
－4

0
0
－M
－M
θL
x1
x2
x3
x4
x5
x6
－M
x5
16
2
（4）
－1
0
1
0
16/4=4
－M
x6
12
3
2
0
－1
0
1
12/2=6

－5M
－6M
M
M
－M
－M

5M－4
6M－3↑
－M
－M
0
0

－3
x2
4
1/2
1
－1/4
0
1/4
0
4/1/2=8
－M
x6
4
（2）
0
1/2
－1
－1/2
1
4/2=2

－2M－3/2
－3
3/4－M/2
M
M/2－3/4
－M

2M－5/2↑
0
M/2－3/4
－M
3/4－3M/2
0

－3
x2
3
0
1
－3/8
1/4
3/8
－1/4

－4
x1
2
1
0
1/4
－1/2
－1/4
1/2

－17
－4
－3
1/8
5/4
－1/8
－5/4

0
0
－1/8
－5/4
－M＋1/8
－M＋5/4

∴X*=（2，3，0，0）T
∴min z =－max z/ =－（－17）=17
四、对偶问题的解法：
什么是对偶问题？
1、在资源一定的条件下，作出最大的贡献；
2、完成给定的工作，所消耗的资源最少。
引例（与本资料P2例1 “图解法”、P7例1 “单纯形法”同）：某工厂生产甲、乙两种产品，这些产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表：
品
产
耗
消
备
设

A B C
利润
（万元）
甲
乙
3 5 9
9 5 3
70
30
有效总工时
540 450 720
——
问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？
解：原问题——
设x1、x2为生产甲、乙产品的数量。
max z = 70x1+30x2
s.t.

将这个原问题化为它的对偶问题——
设y1、y2、y2分别为设备A、B、C单位工时数的加工费。
min w = 540y1+450y2+720y3
s.t.

用大M法，先化为等效的标准模型：
max w/ =－540y1－450y2－720y3
s.t.

增加人工变量y6、y7，得到：
max z/ =－540y1－450y2－720y3－My6－My7
s.t

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

CB
XB
b
－540
－450
－720
0
0
－M
－M
θL
y1
y2
y3
y4
y5
y6
y7
－M
y6
70
3
5
9
－1
0
1
0
70/3
－M
y7
30
（9）
5
3
0
－1
0
1
30/9=10/3

－12M
－10M
－12M
M
M
－M
－M

12M－540↑
10M－450
12M－720
－M
－M
0
0

－M
y6
60
0
10/3
（8）
－1
1/3
1
－1/3
60/8=2.5
－540
y1
10/3
1
5/9
1/3
0
－1/9
0
1/9
10/3/1/3
=10

-300+10/3M
-8M－180
－M
－M/3+60
－M
M/3－60

0
-150+10/3M
8M-540↑
M
M/3－60
0
－M/3+60

－720
y3
15/2
0
5/12
1
－1/8
1/24
1/8
－1/24
15/2/5/12
=18
－540
y1
5/6
1
（5/12）
0
1/24
－1/8
－1/24
1/8
5/6/5/12
=2

－540
－572
－720
－135/2
475/12
－135/2
－75/2

0
125↑
0
135/2
－475/12
135/2－M
75/2－M

－720
－450
y3
20/3
－1
0
1
1/6
1/6
1/6
－1/6

y2
2
12/5
1
0
1/10
－3/10
－1/10
3/10

－5700
－360
－450
－720
75
15
－75
－15

－180
0
0
－75
－15
75－M
15－M

∴该对偶问题的最优解是y*=（0，2，，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万吨，这三个铁矿与四个炼铁厂的距离如下：
矿
铁
厂
铁
离
距
炼

B1 B2 B3 B4
A1
A2
A3
15 20 3 30
70 8 14 20
12 3 20 15
问：该公司应如何组织运输，既满足各炼铁厂需要，又使总的运输费用为最小（按吨.公里计）？
解：用“表上作业法”求解。
⑴先用最低费用法（最小元素法）求此问题的初始基础可行解：

地
产
用
费
地
销

B1
B2
B3
B4
产量
Si
A1
15

20
－67
3

30
－65
100

20

×

80

×
A2
70

8

14
44
20

80

30

20

×

30
A3
12
53
3

20
33
25
－10
50

×

50

×

×
销量
dj
50
70
80

30

230

230
∴初始方案：
B2
20
30
30
B1
B3
A2
20
80
B1
B3
A1

B2
50
A3

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

地
产
用
费
地
销

B1
B2
B3
B4
产量
Si
A1
15

20
－14
3

30
－12
100

20

×

80

×
A2
70
－53
8

14
－9
20

80

×

50

×

30
A3
12

3

20
－20
25
－10
50

30

20

×

×
销量
dj
50
70
80
30
230

230
用表上闭回路法调整后，从上表可看出，所有检验数σ＜0，已得最优解。
∴最优方案：
30
20
B1
B2
A3
50
30
B2
B4
A2
20
80
B1
B3
A1

Z=15×20+3×80+8×50+20×30+12×30+3×20=1960（吨.公里）
解法分析：①如何求检验数并由此确定入基变量？有数字的空格称为“基格”、打×的空格称为“空格”，标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点，出发点算0故为偶点。找出所有空格的闭回路后计算它们的检验数，必须≤0，才得到最优解。否则，应选所有中正的最大者对应的变量xj为入基变量进行迭代（调整）。②检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇点均减去奇点中的最小运量。③重复以上两步，再检验、再调整，直到求得最优运输方案。

类型二：供求不平衡的运输规划问题
若，则是供大于求（供过于求）问题，可设一虚销地Bn+1，令ci,n+1=0，dn+1=，转化为产销平衡问题。
若，则是供小于求（供不应求）问题，可设一虚产地Am+1，令cm+1,j=0，sm+1=，转化为产销平衡问题。
（=1，2，…，m；=1，2，…，n）
六、工作指派问题：
工作指派问题的数学模型——假定有n项工作需要完成，恰好有n个人每人可去完成其中一项工作，效果要好。
工作指派问题的特殊解法——“匈牙利法”（考！！）解题步骤：
1、使系数矩阵（效率矩阵）各行、各列出现零元素。
作法：①行约简—系数矩阵各行元素减去所在行的最小元素，②列约简—再从所得矩阵的各列减去所在列最小元素。
2、试求最优解。如能找出n个位于不同行不同列的零元素，令对应的xij= 1，其余xij = 0，得最优解，结束；否则下一步。
作法：由独立0元素的行（列）开始，独立0元素处画（ ）标记 ，在有（ ）的行列中划去（也可打*）其它0元素；再在剩余的0元素中重复此做法，直至不能标记（ ）为止。
3、作能覆盖所有0元素的最少数直线集合。
作法：① 对没有（ ）的行打√号；②对已打√号的行中所有0元素的所在列打√号；③再对打有√号的列中0元素的所在行打√号；④重复②、③直到得不出新的打√号的行(列)为止；⑤对没有打√号的行画一横线，对打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。⑥未被直线覆盖的最小元素为cij,在未被直线覆盖处减去cij,在直线交叉处加上cij。
4、重复2、3，直到求得最优解。
类型一：求极小值的匈牙利法：（重点掌握这种基本问题）
例1：有甲、乙、丙、丁四个人，要派去完成A、B、C、D四项工作，他们完成的工时如下表：
人
务
时
工
任

A B C D
甲
乙
丙
丁
6 12 13 4
10 3 12 14
7 14 13 16
8 8 12 10
试问：应如何分配任务可使总工时为最少？
解：用“匈牙利法”求解。
已知条件可用系数矩阵（效率矩阵）表示为：
列约简
行约简
（cij）=
A
B
C
D

标号
甲
乙
丙
丁

∴使总工时为最少的分配任务方案为：
甲→D，乙→B，丙→A，丁→C
此时总工时数W=4+3+7+12=26
例2：求效率矩阵
的最优解。
列约简
行约简
解：

标号
所画（）0元素少于n，未得到最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合）：
√

√
√

未被直线覆盖的最小元素为cij=1,在未被直线覆盖处减去1,在直线交叉处加上1。
标号

∴得最优解：

类型二：求极大值的匈牙利法：
min z=－max（－z）
（cij）→（M－cij）=（bij），（cij）中最大的元素为M
max z==
=－

第一部分到此结束
第二部分 动态规划
只要求掌握动态规划的最短路问题——用“图上标号法”解决：具体解题步骤请参看教材P103（这是本套资料少见的与教材完全相同的算法类型之一，务必看书掌握）
学员们只有完全理解了这种作法（思路：逆向追踪）才有可能做题，考试时数字无论如何变化都能作出正确求解！

第二部分到此结束
第三部分 网络分析
一、求最小生成树（最小支撑树、最小树）问题：
破圈法——任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。
参考例题：
例：求下图的最小生成树：
6
7
9
4
1
5
10
v2
v1
v3
v5
v4
v6
3
2
8
解：用“破圈法”求得最小生成树为：
9
4
1
5
v2
v1
v3
v5
v4
v6
2

已得最小树，此时权w=1+2+4+5+9=21为最小。

二、最短路问题：（有向图）
TP标号法（狄克斯托算法）——具体解题步骤请参看教材P125（这是本套资料少见的与教材完全相同的算法类型之一，务必看书掌握）
学员们只有完全理解了这种作法（思路：顺向追踪）才有可能做题，考试时数字无论如何变化都能作出正确求解！
参考例题：
例：教材P124图4—8的例子（略）
三、网络最大流问题：
寻求网络最大流的标号法（福特—富克尔逊算法）——具体解题步骤请参看教材P130。（教材用有序数对（fij，cij）表示（流量，容量），但我们解题算法格式按南邮要求，用大多数《运筹学》书籍中的标准格式，即用有序数对（cij，fij）表示（容量，流量）。解法本质是相同的。）
学员们只有完全理解了这种作法（思路：标号检查、迭代调整）才有可能做题，考试时数字无论如何变化都能作出正确求解！
参考例题：《运筹学参考综合习题》（我站搜集信息自编，非南邮综合练习题，仅供参考。另挂于网上）第三部分到此结束 第四部分 存储论（简介）
随机存储模型参考例题：
例：一食品店要决定每天牛奶的进货量，该店根据过去的销售经验，知道需求量的概率分布如下：
需求x（箱）
25
26
27
28
p（x）
0.1
0.3
0.5
0.1
若进货每箱80元，售价100元，又若当天不能售出因牛奶变质而全部损失，试确定每天进货量。
解法一：已知C=80， p=100，g=0，
需求x（箱）
25
26
27
28
概率p（x）
0.1
0.3
0.5
0.1
累计概率
0.1
0.4
0.9
1
根据单周期随机型存储模型
（“报童模型”）之离散型随机存储模型公式，可得
0.2
即可以确定进货26箱，获利的期望值最大。
解法二：k=100－80=20，h=80.
==0.2
∵P{x=25}=0.1＜0.2≤P{x=25}+P{x=26}=0.4
∴可以确定进货26箱，获利的期望值最大。。
注：该问题即“报童问题”（关于报童进报纸问题的数学模型），即是相当于将上题的进“牛奶”改为进“报纸”等等，解法思路是完全一致的，请注意！第四部分到此结束
第 28 页 共 28 页