考题芸芸

工商管理05级（本）已考《运筹学》试题参考答案 ．．

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

※考试提示：可带计算器，另外建议带上铅笔、直尺、橡皮，方便绘图或分析。

一、填空题（每空2分，共10分）

1、在线性规划问题中，若存在两个最优解时，必有 相邻的顶点是 最优解。 2、树图中，任意两个顶点间有且仅有 一条链 。

3、线性规划的图解法适用于决策变量为 两个 线性规划模型。

4、在线性规划问题中，将约束条件不等式变为等式所引入的变量被称为 松弛变量 。

5、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点，化为供求平衡的标准形式 。

6、运输问题中求初始基本可行解的方法通常有 最小费用法 与 西北角法 两种方法。

7、称无圈的连通图为树，若图的顶点数为p，则其边数为 p－1 。 二、（每小题5分，共10分）用图解法求解下列线性规划问题： 1）max z = 6x1+4x2

⑴

?2x1?x2?10?x?x?8?12? x?72???x1，x2?0 ⑵ ⑶ ⑷ ⑸、⑹

解：此题在“《运筹学》复习参考资料.doc”中已有，不再重复。

第 1 页 共 26 页

2）min z =2x1+x2

⑴ ⑵ ⑶ ⑷、⑸ ⑹

??x1?4x2?24?x?x?8?12? 5?x?101???x2?0解：

从上图分析，可行解域为abcde，最优解为e点。 由方程组

?x1?x2?8? 解出x1=5，x2=3 x?5?1?x1?T

∴X=??x??=（5，3）

?2?*

∴min z =Z*= 2×5+3=13

三、（15分）一家工厂制造甲、乙、丙三种产品，需要三种资源——技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：

第 2 页 共 26 页

甲 乙 丙 资源储备量 技术服务 1 1 1 100 劳动力 10 4 5 600 行政管理 2 2 6 300 单位利润 10 6 4 1）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分） 2）用单纯形法求该问题的最优解。（10分） 解：1）建立线性规划数学模型：

设甲、乙、丙三种产品的生产数量应为x1、x2、x3，则是产品售后的总利润，则

max z =10x1+6x2+4x3

s.t.

??x1?x2?x3?100??10x1?4x2?5x3?600?2x1?2x2?6x3?300 ??x1，x2，x3?02）用单纯形法求最优解：

加入松弛变量x4，x5，x6，得到等效的标准模型：

max z =10x1+6x2+4x3+0 x4+0 x5+0 x6

s.t.

??x1?x2?x3?x4?100??10x1?4x2?5x3?x5?600?2x1?2x2?6x3?x6?300 ??xj?0,j?1,2,...,6列表计算如下：

第 3 页 共 26 页

x1、x2、x3≥0，设z

10 6 4 0 0 0 CB 0 0 0 0 XB x4 x5 x6 b 100 600 300 40 60 180 200/3 100/3 100 x1 1 （10） 2 0 10↑ 0 1 0 10 0 0 1 0 10 0 x2 1 4 2 0 6 （3/5） 2/5 6/5 4 2↑ 1 0 0 6 0 x3 1 5 6 0 4 1/2 1/2 5 5 －1 5/6 1/6 4 20/3 －8/3 x4 1 0 0 0 0 1 0 0 0 0 5/3 －2/3 －2 10/3 －10/3 x5 0 1 0 0 0 －1/10 1/10 －1/5 1 －1 －1/6 1/6 0 2/3 －2/3 x6 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 θL 100 60 150 200/3 150 150 x4 x1 x6 10 0 6 10 0 x2 x1 x6 2200 3∴X*=（

200100，，0，0，0，100）T 332002200100∴max z =10×+6×=

333

四、（10分）用大M法或对偶单纯形法求解如下线性规划模型：

min z =540x1＋450x2＋720x3

第 4 页 共 26 页

?3x1?5x2?9x3?70??9x1?5x2?3x3?30 ?x,x,x?0?123解：用大M法，先化为等效的标准模型：

max z/ =－540x1－450x2－720x3 s.t.

?3x1?5x2?9x3?x4?70??x5?30 ?9x1?5x2?3x3?y?0,j?1,2,...,5?j增加人工变量x6、x7，得到：

max z/ =－540x1－450x2－720x3－Mx6－Mx7 s.t

?3x1?5x2?9x3?x4?x6?70??x5??x7?30 ?9x1?5x2?3x3?x?0,j?1,2,...,5?j大M法单纯形表求解过程如下：

第 5 页 共 26 页

－540 －450 －720 0 0 －M －M CB XB －M －M －M －540 －720 －540 －720 －450 b 70 30 x1 3 （9） －12M x2 5 5 －10M x3 9 3 －12M x4 －1 0 x5 0 －1 x6 1 0 －M 0 1 0 －M 0 1/8 －1/24 x7 0 1 －M 0 θL 70/3 30/9=10/3 x6 x7 M M －M 1/3 －1/9 12M－540↑ 10M－450 12M－720 －M 60 10/3 15/2 5/6 0 1 0 0 1 －540 0 －1 12/5 －360 10/3 5/9 （8） 1/3 －1 0 x6 x1 －1/3 60/8=2.5 1/9 M/3－60 －M/3+60 10/3/1/3 =10 15/2/5/12 =18 5/6/5/12 =2 -300+10/3M -8M－180 －M －M/3+60 -150+10/3M 8M-540↑ M －1/8 1/24 M/3－60 x3 x1 5/12 （5/12） －572 125↑ 0 1 －450 0 *

1 0 1/24 －1/8 －1/24 1/8 20/3 2 －720 －135/2 475/12 －135/2 －75/2 0 1 0 －720 0 135/2 －475/12 135/2－M 75/2－M 1/6 1/6 1/6 －1/6 3/10 －15 15－M x3 x2 1/10 －3/10 －1/10 75 －75 15 －15 －75 75－M －5700 －180 20∴该对偶问题的最优解是x=（0，2，，0，0）T

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

第 6 页 共 26 页

五、（12分）给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）

A1 A2 A3 B1 B2 B3 B4 20 11 8 6 5 9 10 2 18 7 4 1 3 3 12 12 si 5 10 15 dj 1）用最小费用法求初始运输方案，并写出相应的总运费；（4分） 2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分） 解：用“表上作业法”求解。

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

费 用 产 地 销 地 B1 20 5 18 3 3 × 11 B2 2 × 1 3 8 B3 × × 12 12 6 2 1 B4 Si A1 A2 A3 dj ∴初始方案：

3

5 9 7 10 4 × 10 10 15 × 2 12 30 30 B1

10

1

B2

12

A1

2

A2

B2

B4

A3

2

B3 B4

第 7 页 共 26 页

Z=20×3+11×2+2×10+7×1+4×12+1×2=159 2）①用闭回路法，求检验数：

费 用 产 地 销 地 B1 20 5 18 3 3 11 B2 2 8 B3 0 × 6 2 1 B4 －1 Si A1 A2 A3 dj 5 9 7 3 10 4 12 × 10 × × 1 × 12 10 15 × 2 12 12 －1 －5 －2 30 30 ∵?21=12＞0，其余?j≤0 ∴选x21作为入基变量迭代调整。 ②用表上闭回路法进行迭代调整：

费 用 产 地 销 地 B1 20 5 18 3 2 11 B2 3 8 B3 12 × 6 2 1 B4 11 Si A1 A2 A3 dj 5 9 7 3 10 4 12 × 10 1 × －12 × × 12 9 15 × 3 12 －13 －15 －14 30 30 再选x13作为入基变量迭代调整。

第 8 页 共 26 页

费 用 产 地 销 地 B1 20 5 18 3 －12 × 11 B2 3 8 B3 2 6 2 1 B4 －1 Si A1 A2 A3 dj 5 9 7 3 10 4 12 × 10 3 × × 10 7 15 × × 5 12 －1 －5 －14 0 30 30 调整后，从上表可看出，所有检验数?j≤0，已得最优解。 ∴最优方案为：

最小运费Z=11×3+8×2+5×3+2×7+4×10+1×5=123

六、（8分）一个公司经理要分派4个推销员去4个地区推销某种商品。4个推销员各有不同的经验和能力，因而他们在每一地区能获得的利润不同，其估计值如下表所示：

甲 乙 丙 丁 D1 35 28 35 24 D2 27 34 24 32 D3 28 29 32 25 D4 37 40 33 28 3

B2

A2

3

B1

A3

10

B3

A1

2

B3

7

B4

5

B4

问：公司经理应怎样分派4个推销员才使总利润最大？ 解：用求极大值的“匈牙利法”求解。

第 9 页 共 26 页

效率矩阵表示为：

?35??28?35??24?273424322829322537??M－Cij 40? ?33M=40 ??28??5??12?5??16?13616812118153??行约简 0? ?7?12??

?2??12?0??8?10611091137?2?0?列约简 ??120? ??2?(0)标号 ??84???10611(0)680*4(0)??*0??所画（）0元素少于n（n＝4），2?4??未得到最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合）：

?2??12??(0)?8?10611(0)680*4√ (0)?√ ?*0?√ ?2? 4??未被直线覆盖的最小元素为cij=2,在未被直线覆盖处减去2，在直线交叉处加上2。

???????01008841104604?(0)?0?标号 ??100? ?*?04???86???8411（0）46(0)40*??（0）?? 4?6??

??∴得最优解：?????1000000100100??1? ?0?0??∴使总利润为最大的分配任务方案为：

甲→D1，乙→D4，丙→D3，丁→D2 此时总利润W=35+40+32+32=139

第 10 页 共 26 页

七、（6分）计算下图所示的网络从A点到M点的最短路线及其长度。

解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：

B 5 7 17 11 E 4 13 7 4 H 11 8 A D 9 G 5 M 8 9 5 9 6 C 8 F 6 I 21 B 7 5 16 17 D 9 8 C 8 18 6 11 12 E 4 13 G 7 5 4 8 H 11 26 11 0 5 M A 9 5 9 F 10 6 I 9 最佳策略为：A→C→F→G→M 此时的最短距离为8+8+5+5=26

第 11 页 共 26 页

八、（8分）用P→T标号法求下图从至的最短路。（需写出最短路线）

解：此为网络分析之“最短路问题”，可用顺向追踪“TP标号法”解决如下： 0 2 8 1 8 2 3 1 5 1 7 2 9 11 3 1 10 6 3 1 2 v2 1 6 8 5 1 v5 3 3 1 v8 7 v1 1 v6 4 6 3 1 v9 2 1 9 v11 v4 7 2 9 4 v3 v7 v 10 v2 6 v5 3 v8 7 9 v1

v4 v6 4 v9 1 4 2 v11 20 4 v3 15 v7 7 v 10 8 v1到v7的最短路线是：v1→v2→v5→v9→v8→v11，最短距离2+1+1+7+9=20。

第 12 页 共 26 页

九、（10分）用找增广链的方法求如下网络的最大流。（需写出相应的增广链）（弧旁的数字为该弧容量）

解：此为网络分析之“寻求网络最大流问题”，可用“寻求网络最大流的标号法（福

特—富克尔逊算法）”解决如下：

v1 1 4 3 3 10 3 4 v4 7 2 vs v3 4 vt 8 5 v2 v5 ㈠标号过程：

1、给vs标上（0，∞）；

2、检查vs，在弧（vs，v1）上，fs1=0，Cs1=4，fs1

4?0??4， 中?(v1)?min??(vs),(Cs1?fs1)??min???， 0，∞）（ vs 10 4 3 3 （s，4） v1 1 3 4 v4 7 2 v3 4 vt 8 5 v2 （s，10） v5 第 13 页 共 26 页

10?0??10， 同理，给v2标号(s，β(v2))，其中?(v2)?min??(vs),(Cs2?fs2)??min???，3、检查v1，在弧（v1，v3）上，f13=0，C13=3，f13

3?0??3， 中?(v3)?min??(v1),(C13?f13)??min?4， 0，∞）（ vs

（s，4） （3，3） v1 1 4 3 10 3 （1，3） 4 3 4 v4 7 2 v3 vt 8 5 v2 （s，10） v5 （2，4） 4?0??3，检查v3，同理，给v4标号(3，β(v4))，其中?(v4)?min??(v3),(C34?f34)??min?3， 4?0??4，检查v2，同理，给v5标号(2，β(v5))，其中?(v5)?min??(v2),(C25?f25)??min?10，

4、检查v4，在弧（v4，vt）上，f4t=0，C4t=7，f4t

?(vt)?min??(v4),(C4t?f4t)??min?3，7?0??3，vt得到标号，标号过程结束。

0，∞）（ vs 10 4 （s，4） （3，3） v1 1 3 3 3 （1，3） 4 4 v4 7 2 v3 vt 8 （4，3） 5 v2 （s，10） v5 （2，4） 第 14 页 共 26 页

㈡调整过程：从vt开始逆向追踪，找到增广链。 0，∞）（ vs

μ（vs，v1，v3，v4，vt），?=3，在μ上进行流量?=3的调整，得可行流f '如图所示：

去掉各点标号，从vs开始，重新标号。

（4，3） 10 4 3 3 （1，3） 4 （s，4） （3，3） v1 1 3 4 v4 7 2 v3 vt 8 （4，3） 5 v2 （s，10） v5 （2，4） v1 （1，0） （3，3） （3，0） （3，0） （4，3） v4 （7，3） （2，0） vs （10，0） v3 （4，0） vt （5，0） （8，0） v2 v5 第 15 页 共 26 页

（4，3） （3，0） （3，0） （2，3） （4，0） （s，1） （3，1） v1 （1，0） （3，3） （4，3） v4 （7，3） （2，0） 0，∞）（ vs

（10，0） v3 vt （4，1） （5，0） （8，0） v2 （s，10） v5 （2，4） vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。 （4，3） （3，0） （3，0） （2，3） （4，0） （s，1） （3，1） v1 （1，0） （3，3） （4，3） v4 （7，3） （2，0） 0，∞）（ vs

（10，0） v3 vt （4，1） （5，0） （8，0） v2 （s，10） v5 （2，4） μ（vs，v2，v3，v4，vt），?=1，在μ上进行流量?=1的调整，得可行流f '如图所示：

第 16 页 共 26 页

v1 v4 （1，0） （4，3） （3，3） （4，4） （7，4） v（3，0） s （2，0） （3，1） vvt （10，1） 3 （5，0） （8，0） v（4，0） 2 v5

去掉各点标号，从vs开始，重新标号。 （s，1） （1，1） v1 v4 （1，0） （4，3） （3，3） （4，4） （7，4） 0，∞） v（3，0） s （2，0） （3，1） vvt （10，1） （2，23 ） （5，0） （8，0） v（4，0） 2 v5 （s，9） （2，4）

vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。第 17 页 共 26 页

4，1）（（

（4，3） （3，0） （3，1） （2，2） （4，0） （s，1） （1，1） v1 （1，0） （3，3） （4，4） v4 （7，4） （2，0） 0，∞）（ vs

（10，1） v3 vt （4，1） （5，0） （8，0） v2 （s，9） v5 （2，4） μ（vs，v1，v4，vt），?=1，在μ上进行流量?=1的调整，得可行流f '如图所示：

去掉各点标号，从vs开始，重新标号。

（4，4） v1 （1，1） （3，3） （3，0） （3，1） （4，4） v4 （7，5） （2，0） vs （10，1） v3 （4，0） vt （5，0） （8，0） v2 v5 第 18 页 共 26 页

（4，4） （3，0） （3，1） （2，2） （4，0） （-3，2） （5，2） v1 （1，1） （3，3） （4，4） v4 （7，5） （2，0） 0，∞）（ vs

（10，1） v3 vt （4，2） （5，0） （8，0） v2 （s，9） v5 （2，4） vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。 （4，4） （3，0） （3，1） （2，2） （4，0） （-3，2） （5，2） v1 （1，1） （3，3） （4，4） v4 （7，5） （2，0） 0，∞）（ vs

（10，1） v3 vt （4，2） （5，0） （8，0） v2 （s，9） v5 （2，4） μ（vs，v2，v5，v4，vt），?=2，在μ上进行流量?=2的调整，得可行流f '如图所示：

第 19 页 共 26 页

v1 v4 （1，1） （4，4） （3，3） （4，4） （7，7） v（3，0） s （2，2） vt （3，1） v（10，3） 3 （5，0） （8，0） v（4，2） 2 v5

去掉各点标号，从vs开始，重新标号。 （-3，3） （-t，3） v1 v4 （1，1） （4，4） （3，3） （4，4） （7，7） 0，∞） v（3，0） s （2，2） t （3，1） vv（10，3） （s，3 3） （5，0） （8，0） v（4，2） 2 v5 （s，7） （3，3）

vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。第 20 页 共 26 页

5，3）（（

（4，4） （3，0） （3，1） （s，3） （4，2） （-3，3） （-t，3） v1 （1，1） （3，3） （4，4） v4 （7，7） （2，2） 0，∞）（ vs

（10，3） v3 vt （5，3） （5，0） （8，0） v2 （s，7） v5 （3，3） μ（vs，v3，v5，vt），?=3，在μ上进行流量?=3的调整，得可行流f '如图所示

去掉各点标号，从vs开始，重新标号。

（4，4） v1 （1，1） （3，3） （3，3） （3，1） （4，4） v4 （7，7） （2，2） vs （10，3） v3 （4，2） vt （5，3） （8，3） v2 v5 第 21 页 共 26 页

（4，4） （3，3） （3，1） （2，1） （4，2） （-3，1） （-t，1） v1 （1，1） （3，3） （4，4） v4 （7，7） （2，2） 0，∞）（ vs

（10，3） v3 vt （5，1） （5，3） （8，3） v2 （s，7） v5 （3，1） vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。 （4，4） （3，3） （3，1） （2，1） （4，2） （-3，1） （-t，1） v1 （1，1） （3，3） （4，4） v4 （7，7） （2，2） 0，∞）（ vs

（10，3） v3 vt （5，1） （5，3） （8，3） v2 （s，7） v5 （3，1） μ（vs，v2，v3，v5，vt），?=2，在μ上进行流量?=2的调整，得可行流f '如图所示：

第 22 页 共 26 页

v1 v4 （1，1） （4，4） （3，3） （4，4） （7，7） v（3，3） s （2，2） vt （3，3） v（10，5） 3 （5，5） （8，5） v（4，2） 2 v5

去掉各点标号，从vs开始，重新标号。 （-3，2） （-t，2） v1 v4 （1，1） （4，4） （3，3） （4，4） （7，7） 0，∞） v（3，3） s （2，2） t （3，3） vv（10，5） （-5，3 2） （5，5） （8，5） v（4，2） 2 v5 （s，5） （2，2）

vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。第 23 页 共 26 页

5，2）（（

（4，4） （3，3） （3，3） （-5，2） （4，2） （-3，2） （-t，2） v1 （1，1） （3，3） （4，4） v4 （7，7） （2，2） 0，∞）（ vs

（10，5） v3 vt （5，2） （5，5） （8，5） v2 （s，5） v5 （2，2） μ（vs，v2，v5，vt），?=2，在μ上进行流量?=2的调整，得可行流f '如图所示：

去掉各点标号，从vs开始，重新标号。

第 24 页 共 26 页

v1 （1，1） （4，4） （3，3） （3，3） （3，3） （4，4） v4 （7，7） （2，2） vs （10，7） v3 （4，4） vt （5，5） （8，7） v2 v5 （4，4） （3，3） （3，3） v1 （1，1） （3，3） （4，4） v4 （7，7） （2，2） 0，∞）（ vs

（10，7） v3 （4，4） vt （5，5） （8，7） v2 （s，3） v5 标号至点v2：标号过程无法进行，所以 f ' 即为最大流。 （4，4） （3，3） （3，3） v1 （1，1） （3，3） （4，4） v4 （7，7） （2，2） 0，∞）（ vs

（10，7） v3 （4，4） vt （5，5） （8，7） v2 （s，3） v5 V1={vs，v2}，V1={v1，v3，v4，v5，vt}

截集（V1，V1）={（vs，v1），（vs，v3），（v2，v3），（v2，v5）} V（ f ' ）=C（V1，V1）=4+3+3+4=14

第 25 页 共 26 页

十、（7分）某人以每份0.3元的价格买进晚报，出售价为0.4元/份，过期的报纸销价为0.2元/份。欲使平均收入最高，求最佳进货量。根据经验报纸每天的销售情况如下：

需求量x30 （份） 概率p（x） 0.05 0.08 0.15 0.20 0.30 0.12 0.07 0.03 31 32 33 34 35 36 37 解：已知C=0.3，p=0.4，g=0.2，

需求量x30 （份） 概率p（x） 累计概率 0.05 0.05 0.08 0.13 0.15 0.28 0.20 0.48 0.30 0.78 0.12 0.90 0.07 0.97 0.03 1.00 31 32 33 34 35 36 37 根据单周期随机型存储模型 （“报童模型”）之离散型随机存储模型公式，可得

p(x?Q*)?p?C?s0.4?0.3?0??0.50

p?g?s0.4?0.2?0即可以确定最佳进货量为34份，可使平均收入最高。

（2006年3月已考试题参考答案至此全部完毕，祝考试成功！）

第 26 页 共 26 页

十、（7分）某人以每份0.3元的价格买进晚报，出售价为0.4元/份，过期的报纸销价为0.2元/份。欲使平均收入最高，求最佳进货量。根据经验报纸每天的销售情况如下：

需求量x30 （份） 概率p（x） 0.05 0.08 0.15 0.20 0.30 0.12 0.07 0.03 31 32 33 34 35 36 37 解：已知C=0.3，p=0.4，g=0.2，

需求量x30 （份） 概率p（x） 累计概率 0.05 0.05 0.08 0.13 0.15 0.28 0.20 0.48 0.30 0.78 0.12 0.90 0.07 0.97 0.03 1.00 31 32 33 34 35 36 37 根据单周期随机型存储模型 （“报童模型”）之离散型随机存储模型公式，可得

p(x?Q*)?p?C?s0.4?0.3?0??0.50

p?g?s0.4?0.2?0即可以确定最佳进货量为34份，可使平均收入最高。

（2006年3月已考试题参考答案至此全部完毕，祝考试成功！）

第 26 页 共 26 页

本文来源：https://www.bwwdw.com/article/9sfo.html