运筹学复习答案(新)

2023年11月21日发(作者：2022款大众高尔夫图片)《运筹学》复习内容
一、问答题： 1、运筹学的主要内容有哪些？根据你所从事的工作或所了解的信息，说明你所学过运筹学的哪些内容、方法对你最
有用？运筹学为什么在美国被称为管理科学，此名称合理吗？ 答：运筹学应用分析、试验、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供 有决策依据的最优方案，以实现最有效的管理。运筹学的研究内容包括规划论、图与网络分析、存贮论、排队论、对 策论、决策论。规划论主要解决两大问题：如何有效利用现有的人力、物力去完成更多的任务；对于给定的任务或者 目标。用最少的人力或物力如何去完成。图与网络分析主要解决生产组织、计划管理以及工程施工中的工序安排、工 期控制、资源合理调配问题。决策论研究决策过程中方案的选择、度量和概率值选取问题。最终获得最优策略、最优 方案。
定量分析技术作为管理工具，在美国的许多企业得到广泛的应用，量化管理或者精确管理是美国企业管理的重点， 运筹学在美国被称为管理科学。合理。
2、运筹学解决实际问题的过程可分为哪几个阶段? P6
答：运筹学解决实际问题的过程可分为 5 个阶段： （1）提出并形成问题。要解问题，首先需要提出问题，明确问题的实质及关键所在，这就要求对系统进行深入的调查 和分析，确定问题的界限，选准问题的目标。 （2）建立模型。运筹学模型是一个能有效地达到一定目标（或多个目标）行动的系统，因此，目标一经认定，就要用 数学语言描述问题，建立目标函数，分析问题所处的环境，确定约束条件，探求与问题有关的决策变量等，并选用合 适的方法，建立运筹学模型。 （3）分析并求解模型。根据所建模型的性质及其数学特征，选择适当的求解方法。 （4）检验并评价模型。模型分析和计算得到结果以后，尚需按照它能否解决实际问题，主要考虑达成目标的情况，选 择合适的标准，并通过一定的方法对模型结构和一些基本参数进行评价，以检验它们是否准确无误，否则就要考虑改 换或修正模型，增减计算过程中所用到的资料或数据。
1

x0c（5）应用或实施模型的解。经过反复检查以后，最终应用或实施模型的解，就是供给决策者一套有科学依据的并为解 决问题所需要的数据、信息或方案，以辅助决策者在处理问题时作出正确的决策和行动方案。 3、试述线性规划模型建模的基本步骤及线性规划模型的构成要素的特征。 建模基本步骤：确定决策变量、确定目标函数、确定约束条件。 线性规划模型的构成要素：决策变量，是规划问题中要确

定的未知量,用来表示规划问题中用数量表示的方案措施，可 以由决策者决定和控制。目标函数，是决策变量的函数，反映决策者对于规划规划问题结果的要求。约束条件，指决 策变量取值时受到的各种资源条件的限制,通常表达为含决策变量的等式或者不等式。 4、试述线性规划与对偶规划之间存在的关系。 线性规划问题具有对偶性，即任何一个求极大值的线性规划问题，都有一个求极小值的线性规划问题与之对应，反之 亦然。如果把其中一个叫做原问题，则另一个就叫做它的对偶问题，并称这互相联系的两个问题为一对对偶问题。根 据对偶理论，在解原问题的同时，也可以得到对偶问题的解，并且还可以提供影子价格等有价值的信息。 5、什么是资源的影子价格，它同相应的市场价格之间有何区别？ 在一对对偶问题（P）和（D）中，若（P）的某个约束条件的右端常数 bi 增加 1 个单位时，所引起的目标函数最优值 Z﹡的改变量 yi﹡成为第 i 个约束条件的影子价格。如果原规划模型属于在一定资源约束条件下，按一定的生产消耗生产 一组产品并寻求总体效益（如利润）目标函数最大化问题，那么其对偶模型属于对本问题中每一资源以某种方式进行 估价以便得出与最优生产计划相一致的一个企业的最低总价值。该对偶模型中资源的估价表现为相应的资源的影子价 格。 影子价格不是市场价格，它是根据企业本身的资源情况 bi、消耗系数 aij 和产品的利润 cj 计算出来的一种价格，是新增 资源所创造的价值，是边际价格。不同的企业，即使是相同的资源，其影子价格也不一定相同。就是同一个企业，在 不同的生产周期，资源的影子价格也不完全一样。企业决策者可以将企业资源的影子价格与市场价格相比较，买卖这 种资源，使企业获利或降低成本，此时该资源的影子价格也将发生变化，直到影子价格与市场价格保持同等水平时， 才处于平衡状态。影子价格是一种机会成本。
二、建模题：（只要求建立模型）
2

x0c1、资源的合理利用问题。P7 maxZ=c1x1+c2x2+…+cnxn； 约束方程
a11x1+a12x2+…+ a1nxn≤b1； a21x1+a22x2+…+a2nxn≤b2； s.t. am1x1+am2x2+…+amnxn≤bm； xj≥0(j=1,2, …,n) 2、生产组织与计划问题。 P8
mn
minZ=∑ ∑cijxij； i=1 j=1
约束方程
n
∑aijxij≤ai（i=1，2，…，m，对机床 Ai 加工机时的限制）；
j=1
m< ∑xij≥bJ （j=1，2，…，n，对零件 Bj 的需要量必须保证）；
i=1
xij≥0 （i=1，2，…，m；j=1，2，…，n）。

3、合理配料问题。P11

minZ=x1+x2+…+xn； 约束方程

a11x1+a12x2+…+ a1nxn≥b1；

a21x1+a22x2+…+a2nxn≥b2；
<

…

am1x1+am2x2+…+amnxn≤bm；

xj≥0(j=1,2, …,n)

或


n
minZ= ∑xj； j=1
约束方程
n
∑aijxj≥bJ（i=1，2，…，m，各种成分的最低需要量必须满足）；
j=1< xj≥0 （j=1，2，…， n）。

4、运输问题。P175 设 xij 表示由产地 Ai 运往销地 Bj（i=1，2，…，m；j=1，2，…，n）的运量，则当产销平衡

m

n

（即∑ai=∑bj）时，其数学模型为

i=1

j=1

mn
minZ=∑ ∑cijxij； i=1 j=1
约束方程
n
∑xij=ai（i=1，2，…，m）；

3

x0cj=1
m< ∑xij=bj （j=1，2，…，n）；
i=1
xij≥0 （i=1，2，…，m；j=1，2，…，n）。

当产大于销

m

n

（即∑ai＞∑bj）时，其数学模型为

i=1

j=1

mn
minZ=∑ ∑cijxij； i=1 j=1

约束方程

n
∑xij≤ai（i=1，2，…，m）；
j=1

m< ∑xij=bj （j=1，2，…，n）；
i=1
xij≥0 （i=1，2，…，m；j=1，2，…，n）。

当销大于产

m

n

（即∑ai＜∑bj）时，其数学模型为

i=1

j=1

mn
minZ=∑ ∑cijxij； i=1 j=1

n
∑xij＝ai（i=1，2，…，m）；
j=1

m< ∑xij≤bj （j=1，2，…，n）；
i=1

xij≥0 （i=1，2，…，m；j=1，2，…，n）。

并假设 ai≥0，bj≥0,cij≥0（i=1，2，…，m；j=1，2，…，n）。

5、目标规划。P243，作业 1；课件例二；P221 例 3

P243，作业 1 MINZ=P1D1 一+ P2D2 一+P3D3 十 +P4(D4 一一 D4 十+ D5 一一 D5 十+D6 一一 D6 十) S.T. 560X1+650X2+800X3+ D1 一一 D1+=16000
6X1+8X2+10X3+ D2 一一 D2+=200 D2 一+ D3 一一 D3+=24 X1+ D4 一一 D4+=12 X2+ D5 一一 D5+=10 X3+ D6 一一 D6+=6
XI,DJ≥0(I=1,2，3；J=1，2，···，6)

课件例二、已知一个生产计划的线性规划模型为，其中目标函数为总利润，x1,x2 为产品 A、B 产量。现有下列目标：

1、要求总利润必须超过 2500 元；2、考虑产品受市场影响，为避免积压，A、B 的生产量不超过 60 件和 100 件；3、

由于甲资源供应比较紧张，不要超过现有量 140。试建立目标规划模型，并用图解法求解。

解：以产品

A、B

的单件利m 润比a2x.5

：Z 1

为权系数，模型如下：
30 x1 12 x2

2 x1 x2 1404 ( )

x1

60 ( )



x2 100 ( )

x0cmin

Z



P1d1



P2 (2.5d3



d

4

)



P3d

2

30

x1

2x1

12 x2 x2

d1



d

2

d1



d

2

2500 140



x1



d

3



d

3



60



x2



d

4



d

4

100

x12 0, dl , dl 0 (l 1.2.3.4)

作图：

作图：
x2
140 120 100 80 60

d

1

⑶

d

3

d

3

d1

BA

d

2

d

2

C

d

4

d

4

⑷

min Z



P1d

1



P2

(

2.5d

3



d

4

)



P3

d

2



30

x1

2 x1

12 x2 x2



d

1



d

2



d

1



d

2

2500 140



x1



d

3



d

3

60



x2



d

4



d

4

100

x1 2



0,

d

l

,

d

l

0

(l 1.2.3.4)

40

20

D

0

20 40 60 80 100

x1

⑴ ⑵

结论：C(60 ,58.3)为所求的满意解。

检验：将上述结果带入模型，因 d1 ＝ d1＝0；

d

3

＝

d

3

＝0；

d

2

＝0，d

2

存在；

d

4

＝0，d

4

存在。所以，

有下式：

minZ=P3

d


2

将 x1＝60， x2 ＝58.3 带入约束条件，得

30×60＋12×58.3＝2499.6≈2500；

2×60+58.3=178.3 > 140；

1×60＝60

1×58.3＝58.3 < 100

由上可知：若A、B的计划产量为60件和58.3件时，

所需甲资源数量将超过现有库存。在现有条件下，此

解为非可行解。为此，企业必须采取措施降低A、B产

品对甲资源的消耗量，由原来的100％降至78.5％

（140÷178.3＝0.785），才能使生产方案（60，58.3）

成为可行方案。

6、0-1 整数规划问题。P267 例 1 一般模型
n
maxZ= ∑cixi； i=1
n
∑aijxj≤bi（i=1，2，…，m）；
j=1< xj=0 ,1 （j=1，2，…， n）。
例 1 建模
12
maxZ= ∑bixi； i=1

5

x0c12
∑aixi≤ɑ；
i=1
4< ∑xi≤2；
i=1
9
∑xi≤3；
i=5
12
∑xi≤2；
i=10

xj=0 ,1,j=1，2，…，12。

三、计算题：

1、某厂准备生产 A、B、C 三种产品，它们都要消耗劳动力和原材料，已知有关数据如下表：

A

B

C

资源限制

劳动力

6

3

5

45

原材料

3

4

5

30

单件利润（元）

4

1

5

（1） 试建立线性规划模型，求使该厂获利最大的生产计划（用单纯形法）。

max Z 4x1 x2 5x3

解：（1）设决策变量

x1 ,

x2 ,

x3

分别表示

A、B、C

三种产品的产量，则此问题的数学模型为
<36xx11

3x2 4x2



5x3 5x3



45 30

x1, x2 , x3 0

引入松驰变量 x4 , x5 将问题化为标准型

max Z 4x1 x2 5x3

6x1 3x2 5x3 x4 45
<3x1 4x2 5x3 x5 30



x j 0( j 1,2,3,4,5)

选初始可行基 B0 ( p4 , p5 ) 。令非基变量 x1 x2 x3 0

得初始基可行解 X (0) (0,0,0,45,30)T 。列单纯形表

C CB XB b 0 x4 45 0 x5 30

Z

0

0 x4 15 5 x3 6

Z

-30

4 x1 5 5 x3 3

Z

-35

4

1

x1

x2

6

3

3

4

4

2

3* -1 3/5 4/5

1

-3

1

-1/3

0

1

0

-8/3

5

0

x3

x4

5

1

5* 0

5

0

0

1

1

0

0

0

0

1/3

1

-1/5

0

-1/3

0 x5 0 0
0 -1 1/5 -1 -1/3 2/5 -2/3

6

x0c由上表知，最优解为 X*=（5，0，3，0，0）T，目标函数最优值 Z*=35。即最优生产计划为：A 产品生产 5 单位， C 产品生产 3 单位，B 产品生产 0 单位。

min W 45 y1 30 y2

（2）写出此问题线性规划的对偶规划，

6 53yy11



3y2 4 y2 5y2



4 1 5

y1 , y2 0

由上表可知对偶规划的最优解为 Y*=（1/3，2/3）。根据对偶理论，对偶规划的最优解就是原规划中变量的影子价

格，劳动力和原材料的影子价格分别为 1/3，2/3。因此，原材料增加 1 个单位，按最优生产计划安排生产可以多获利

2/3 个单位。

2、长江公司在计划期内要安排生产 A、B 两种产品（假设市场销路很好）。生产单位产品的利润以及所需的劳动力、 设备台时以及原材料的的消耗资料由下表给出
资料表

劳动力 设备
原材料

产品 A 9 4 3

产品 B 4 5 10

资源限制 360 工时 200 工时 300 工时

单位产品利润

70

120

1、试求使该公司获利最大的

生产方案（用单纯形法）。

2、设备增加 1 台时，能够使最优目标函数值增加或减少多少？

解：1、设 A、B 两种产品的产量分别是 X1、X2，此生产问题的线性规划模型是：

max Z 70x1 120x2

9x1 4x2 360

s.t

34xx11

5x2 10x2



200 300

x1, x2 0

用单纯形法求解，首先引入松驰变量 x3、x4、x5，将线性规划化成标准型，取松驰变量 x3、x4、x5 为基变量，求得初始 基可行解 X=（0，0，360，200，300）。列出单纯形表，根据规则在表中求解

C

70

120

0

0

0

CB XB

b

X1

X2

X3

X4

X5

0 X3 360

9

4

1

0

0

0 X4 200

4

5

0

1

0

0 X5 300

3

10

0

0

1

Z

0

70

120

0

0

0

0 X3 240

7.8

0

1

0

-0.4

0 X4 50

2.5

0

1

1

-0.5

120 X2 30

0.3

1

0

0

0.1

Z

-3600

34

0

0

0

-12

0 X3 84

0

0

70 X1 20

1

0

120 X2 24

0

1

Z -4280 0

0

1 0 0
0

-3.12 0.4 -0.12
-13.6

1.16 -0.2 0.16
-5.2

7

x0c由于最终表中所有的检验数都已经成为负数或者零,于是得到最优解:

X (20,24,84,0,0)

目标函数最优值 Z 4280

（2）写出此问题的线性规划的对偶规划，求出对偶规划的最优解，根据对偶理论，对偶规划的最优解就是原规划中变 量的影子价格，劳动工时、设备台时和原材料的影子价格分别为 0，13.6，5.2。因此，设备每增加 1 台时，按最优计划 安排生产可以多获利 13.6 元。

4、对偶问题。作业 P136（9）（10）（11） P136（9）

已知线性规划问题

max Z 2x1 x2 3x3

s.t

.

2

x1 x1

x2 3x2

2x3 4x3

5; 12;



x

j



0

( j 1,2,3)

(1) 写出其对偶问题；（2）已知原问题的最优解为 X ( 3，2，0 )T ，试根据对偶理论，直接求出对偶问题的最优
解；（3）如果上述规划中的第一个约束为资源约束，写出这种资源的影子价格。

解：（1）原问题的对偶问题为

y1 2 y2 2

min W 5 y1 12 y2
<



y1 3y2 1 2 y1 4 y2 3

y1 0, y2无约束

（2）由于

x1

＞0，

x

2

＞0，由互补松驰定理得其对应的对偶问题的约束条件为

0，

即



y 1 y1



2

y

2



3

y

2



2 1





y 1

y

2

4 1

所以对偶问题的最优解为 y (4,1)

（3）W 8 ，第一种资源的影子价格为 4

P136（10）
已知线性规划问题

max Z x1 2x2 2x3 4x4
<2x1x12

x x

2 2

2x3 3x3

3x4 2x4



20 20



x j 0( j 1,2,3,4)

其对偶问题的最优解为 y1 1.2,

y

2



0.2 ，试根据对偶理论求出原问题的最优解。

min Z 20y1 20y2

y1 2 y2 1 (1)

解：此

LP

问题的对偶问题为

s.t.

2 y1 2 y1

y2 3y2

2 3

(2) (3)

3y1 2 y2 4 (4)



y1, y2 0

8

x0c将 y1 1.2 ,

y

2



0.2 代入对偶问题的约束条件（1）（2）为严格不等式，由互补松驰定理推知，x1



x2



0。

又因

y1



0, y2



0 。故原问题的两个约束条件应取等式，有 32xx33

3x4 2x4



20 解得 20

x

3



x

4



4 ，故

原问题

的最优解为 X （0，0，4，4），目标函数最优值为 Z max 28 Wmin
P136（11）
已知线性规划问题 min Z 8x1 6x2 3x3 6x4

x1 2x2 x4 3
<

3x1

x2 x3 x4 x3 x4 2



6



x1 x3 2

x j 0, ( j 1,2,3,4)

(1) 写出其对偶问题；（2）已知原问题的最优解为 X ( 1，1，2，0 )T 试根据对偶理论，直接求出

对偶问题的最优解。

maxW 3y1 6 y2 2 y3 2 y4

y1 3y2 y4 8

解：对偶规划为 s.t.

2 y1 y2 6 y2 y3 y4 3



y1 y2 y3 6

y j 0( j 1,2,3,4)

1 2 3

（2）将

X*=（1，1，2，0）T

代入原方程的约束条件

3



1 2

2 2

6

1 2 3 0

则最后一个约束为松约束，所以

y

* 4



0

又由于

x1



0 ， x2



0 ， x3



0

，由互补松驰定理知，其对偶问题的约束方程必为等式，即

2y1y 13

y

2

y

2



8 6



y

2



y3

3

所以有



y 1

y

2



2 2



y3



1

即对偶问题的最优解为Y （2，2，1，0）

5、运输问题。作业 P213。2（1）（2）已知运输问题的产销平衡表与单位运价表如表所示，试用表上作业法分别求最 优解（表中 M 代表充分大的正数）。（1）
9

x0c销地

产地

B1

B2

B3

B4

产量

A1

3

7

6

4

5

A2

2

4

3

2

2

A3

4

3

8

5

3

销量

3

3

2

2

解：

单位运 销

价

地

B1

B2

B3

B4

产地

产量

A1

①

◎

②

②

5，4，2，0

3

7

6

4

A2

②

×

×

×

2，0

2

4

3

2

A3

×

③

×

×

3，0

4

3

8

5

销量

3，1，0 3，0

2，0

2，0

（x22,x12,x11,x21）为一个闭回路，σ22=（4+3）-（7+2）=-2＜0 （x23,x13,x11,x21）为一个闭回路，σ23=（3+3）-（6+2）=-2＜0 （x24,x14,x11,x21）为一个闭回路，σ24=（2+3）-（4+2）=-1＜0 （x31,x11,x12,x32）为一个闭回路，σ31=（4+7）-（3+3）=5＞0 （x33,x13,x12,x32）为一个闭回路，σ33=（8+7）-（6+3）=7＞0 （x34,x14,x12,x32）为一个闭回路，σ34=（5+7）-（4+3）=5＞0

单位运 销

价

地

B1

B2

B3

B4

产地

产量

A1

③

◎

◎

②

5

3

7

6

4

A2

◎

×

②

×

2

2

4

3

2

A3

×

③

×

×

3

4

3

8

5

销量

3

3

2

2

X11*=3, X12*=0, X13*=0, X14*=2, X21*=0, X23*=2, X32*=3,其余 Xij*=0，目标函数的最优值为 Z*=3×3+0×7+0×6+2×4+0×2+2×3+3×3=32.

（2）

销地

产地

B1

A1

10

A2

16

A3

5

销量

5

解：

B2

B3

B4

产量

6

7

12

4

10

5

9

9

4

10

10

4

2

4

6

10

x0c单位运价 销地

产地

B1

B2

B3

B4

产量

A1

③

×

10

× 6

① 7

12 4，1，0

A2

×

×

16

④ 10

⑤ 5

9，5，0 9

A3

②

②

5

× 4

×

4，2，0

10

10

销量

5，3，0 2，0

4，0

6，1，0

（x12,x11,x31,x32）为一个闭回路，σ12=（6+5）-（10+4）=-3＜0 （x13,x14,x24,x32）为一个闭回路，σ13=（7+9）-（12+5）=-1＜0 （x21,x11,x14,x24）为一个闭回路，σ21=（16+12）-（10+9）=9＞0 （x22,x24,x14,x11,x31,x32）为一个闭回路，σ22=（10+12+5）-

（9+10+4）=4＞0 （x33,x23,x24,x14,x11,x31）为一个闭回路，σ33=（10+9+10）-（5+12+5）=7＞0 （x34,x14,x11,x31）为一个闭回路，σ34=（10+10）-（12+5）=3＞0

单位运价 销地

产地

B1

B2

B3

B4

产量

A1

①

②

10

× 6

①

4

7

12

A2

×

×

16

④ 10

⑤

9

5

9

A3

④

◎

5

× 4

×

4

10

10

销量

5

2

4

6

单位运 销

价

地

B1

B2

B3

B4

产地

产量

A1

①

②

10

① 6

◎

4

7

12

A2

×

×

③

16

10

⑥

9

5

9

A3

④

◎

×

×

4

5

4

10

10

销量

5

2

4

6

X11*=1, X12*=2, X13*=1, X14*=0, X23*=3, X24*=6,X31*=4, ,X32*=0 其余 Xij*=0，目标函数的最优值为 Z*=1×10+2×6+1×7+0×12+3×5+6×9+4×5+0×4=118.

6、整数规划:用匈牙利法求解分配问题。课件例二。P285、7（a）(b) 课件例二、有一份中文说明书，需译成英、日、德、俄四种文字，分别记作 A、B、C、D。现有甲、乙、丙、丁四人， 他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？
11

x0c任务 人员

A

B

C

D

甲

6

7

11 2

乙

4

5

9

8

丙

3

1

10 4

丁

5

9

8

2

求解过程如下：
第一步，变换系数矩阵：

6 7 11 2 2

(cij

)



4 3

5 1

9 10

8 4 4 1

5 9 8 2 2

第二步，试指派：
4 ◎ 2 3

4 5 9 0 0 1 5 4 2 0 9 3 3 7 6 0
－5

4 5 4 0 0 1 0 4 2 0 4 3 3 7 1 0

5 4 ◎

1 ? 4

◎ 4 3

7

1

?



找到 3 个独立零元素
但 m =3
第三步，作最少的直线覆盖所有0元素：

4 5 4 ◎ √

◎ 1 ? 4

2 ◎ 4 3

3

7

1

?



√

√

独立零元素的个数m等于最少直线数l，即l＝ m=3
第四步，变换矩阵(bij)以增加0元素：没有被直线覆 盖的所有元素中的最小元素为1，然后打√各行都减去 1；打√各列都加上1，得如下矩阵，并转第二步进行 试指派：

4 5 4 ◎ √

◎ 1 ? 4

2 ◎ 4 3

3

7

1

?



√

√

3 4 3 ◎

◎ 1 ? 5

2 ◎ 4 4

2

6

0

?



3 4 3 ◎

◎ 1 ? 5

2 ◎ 4 4

2

6

◎

?



得到4个独 立零元素， 所以最优解 矩阵为：

P285、7（a）(b) (b) 已知效益矩阵为

3 4 3 0

0 1 0 5

2 0 4 4

2

6

0

0



0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0
15

12

x0c3 8 2 10 3

872 97

（cij）= 6 4 2 7 5

842 35

解：

9 10 6 9 10

3 8 2 10 3 －2

1 6 0 8 1 04 070

8 7 2 9 7 －2

6 5 0 7 5 53

（cij）= 6 4 2 7 5 －2

4 2 0 5 3 30

8 4 2 3 5 －2

6 2 0 1 3 50

9 10 6 9 10 －6

3 4 0 3 4 22
－1－2 －1 －1

064 042 002 023

◎4 ? 7? 5 3 ◎6 4√ 3 ◎? 4 2 5 ?? ◎2 2 2 ? 23 √
√ ?4 2 7 ◎ 31 ◎ 4 2 3◎ 2 4 2 5? 2 ◎ 2 ◎? ? ? 1

04 2 7 0 31 0 4 2 30 2 4 2 50 2 0 2 00 0 0 1

此时，独立零元素的个数 m＝5。于是已求得最优解 X15*=X23*=X32*=X44*=X51*=1，其余 Xij*=0。目标函数最优值 Z﹡＝3×1+2×1+4×1+3×1+9×1＝21

B
解：

（cij）=

7 9 10 12 13 12 16 17 15 16 14 15 11 12 15 16

（cij）=

7 9 10 12 －7 13 12 16 1

7 －12 15 16 14 15 －14 11 12 15 16 －11

◎2 3 1◎ 4 4 2◎
? 14

4 4 ? 42

√
3〈 4 √

0235 1045 1201 0145
－1
◎1 2 3 2◎0 0 2 2◎ ? ?0 3 3

02 10 12 01

34 44 00 44

√
13

x0c◎1 3 4 2◎ 4 4 2 2◎ ? ?? 3 3

√ √
3〈 4 √

01 20 44 00

01 22 00 11

√√ ?1 ◎ 1 2◎ 2 2 44 ? ◎ ◎? 1 1

此时，独立零元素的个数 m＝4。于是已求得最优解 X13=X22*=X34*=X41*=1，其余 Xij*=0。目标函数最优值 Z﹡＝10×1+12×1+15×1+11×1＝48

7、动态规划：求最短路径

3

C1

1

2 B1 3

A

1 2
3

3 C2

D

4

B2 1

4

C3

解：整个计算过程分三个阶段，从最后一个阶段开始，

第一阶段（C →D）： C 有三条路线到终点 D

f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4

第二阶段（B →C）： B 到 C 有六条路线。

d( B1,C1 ) + f1 (C1 )

3+1

f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3

d( B1,C3 ) + f1 (C3 )

1+4

最短路线为 B1→C1 →D 路长 4

d( B2,C1 ) + f1 (C1 )

2+1

f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3

d( B2,C3 ) + f1 (C3 )

1+4

最短路线为 B2→C1 →D 路长 3

第三阶段（ A → B ）： A 到 B 有二条路线。

d(A, B1 )＋ f2 ( B1 )

2+4

f3 (A) = min

= min

d(A, B2 )＋ f2 ( B2 )

4+3

所以：最短路线为 A→B1→C1 →D。路长 6

4 = min 6 = 4
5
3 = min 6 = 3
5
= min｛6,7｝=6

14

x0c12

B1

2

10 14

A

5

B2 6 10

1

4

13

B3

12 11

C1 3
9 6
C2
5 8
C3 10

D1 5
E
2
D2

解：整个计算过程分四个阶段，从最后一个阶段开始，

第一阶段（D →E）： D 有二条路线到终点 E

f1 (D1 ) = 5 ； f1(D2 ) = 2 ；

第二阶段（C →D）： C 到 D 有六条路线。

d( C1,D1 ) + f1 (D1 )

3+5

f2 ( C1 ) = min

= min

d( C1,D2) + f1 (D2 )

9+2

最短路线为 C1→D1 →E 路长 8

d( C2,D1 ) + f1 (D1 )

6+5

f2 ( C2 ) = min

= min

d( C2,D2 ) + f1 (D2)

5+2

最短路线为 C2→D2 →E 路长 7

d( C3,D1 ) + f1 (D1 )

8+5

f2 ( C3 ) = min

= min

d( C3,D2 ) + f1 (D2)

10+2

最短路线为 C3→D2 →E 路长 12

第三阶段（ B → C）： B 到 C 有 9 条路线。

d(B1, C1 )＋ f2 ( C1 )

12+8

f3 (B1) = min d(B1, C2 )＋ f2 ( C2 ) = min 14+7

d(B1, C3 )＋ f2 ( C3 )

10+12

最短路线为 B1→C1→D1 →E 路长 20

d(B2, C1 )＋ f2 ( C1 )

6+8

f3 (B2) = min d(B2, C2 )＋ f2 ( C2 ) = min 10+7

d(B2, C3 )＋ f2 ( C3 ) 最短路线为 B2→C1→D1 →E 路长 14

4+12

d(B3, C1 )＋ f2 ( C1 )

13+8

f3 (B3) = min d(B3, C2 )＋ f2 ( C2 ) = min 12+7

d(B3, C3 )＋ f2 ( C3 ) 最短路线为 B3→C2→D2 →E 路长 14

13+12

第四阶段（ A → B）： A 到 B 有 3 条路线。

d(A, B1 )＋ f3 ( B1 )

2+20

f4 (A) = min d(A, B2 )＋ f3 ( B2 ) = min 5+14

d(A, B3 )＋ f3 ( B3 )

1+19

最短路线为 A→B2→C1→D1 →E 路长 19

= min = min = min
=20 =14 =19 =19

15

8 =8
11
11 =7
7
13 = 12
12

x0c16

x0c