最新(整理)《运筹学》期末考试试题及参考答案

(整理)《运筹学》期末考试试题及参考答

案

------------------------------------------作者xxxx ------------------------------------------日期xxxx

……………………………………………………………最新资料推荐…………………………………………………

《运筹学》试题参考答案

一、填空题(每空2分,共10分）

1、在线性规划问题中,称满足所有约束条件方程和非负限制的解为 可行解 。 2、在线性规划问题中，图解法适合用于处理 变量 为两个的线性规划问题。

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

4、在图论中,称 无圈的 连通图为树。

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

二、(每小题５分,共10分)用图解法求解下列线性规划问题： 1)max z = 6x１+4x2

⑴

2x1x210xx812 x72x1，x20 ⑵ ⑶ ⑷ ⑸、⑹

解:此题在“《运筹学》复习参考资料。doｃ”中已有，不再重复. 2）min ｚ ＝－3x1+２x2

⑴ ⑵ ⑶ ⑷ ⑸ ⑹、⑺

2x14x222x4x10122x1x27 x3x121x1,x20解:

2 / 13-------------

……………………………………………………………最新资料推荐…………………………………………………

可行解域为abｃda,最优解为b点。

2x14x222由方程组 解出x１＝１1,x2=0

x02x1T

∴X=x=(11,0)

2*

∴mｉn z =－3×1１+2×０=-33

三、(15分)某厂生产甲、乙两种产品,这两种产品均需要Ａ、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示:

甲 乙

１）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分)

3 / 13-------------

A ９ 4 ３６0 B 4 ６ 200 C 3 10 ３00 70 120 ……………………………………………………………最新资料推荐…………………………………………………

2)用单纯形法求该问题的最优解.（10分) 解:１)建立线性规划数学模型:

设甲、乙产品的生产数量应为x1、x2,则x1、x2≥0，设ｚ是产品售后的总利润，则

mａx z ＝70x1+120x２

s．t。

9x14x23604x16x22003x110x2300 x1，x202）用单纯形法求最优解：

加入松弛变量ｘ３,x4，ｘ5,得到等效的标准模型:max z =7０x１＋１20x２＋0 x3+０ s.t。

9x14x2x33604x16x2x42003x110x2x5300 xj0,j1,2,...,5列表计算如下：

4 / 13-------------

x4＋0 x5

……………………………………………………………最新资料推荐…………………………………………………

CB 0 0 0 ＸB x３ x4 x5 b ３60 2００ 3０0 0 0 120 ｘ3 ｘ4 x２ 24０ 20 30 70 12０ ｘ１ x２ 9 4 ４ 6 3 （10) 0 0 ７０ 1２0↑ 39/５ ０ (1１０ /5） 3/10 1 ３6 120 3４↑ 0 0 1 0 ７０ 0 0 0 1 １２０ 0 0 x3 1 0 ０ 0 0 １ 0 ０ ０ 0 1 0 ０ 0 0 ０ x4 ０ １ 0 0 0 0 1 0 ０ 0 0 x5 0 0 1 0 0 - 2/5 θL 90 1００/3 30 ４00／13 — ３/5 1００／11 1/10 12 -12 10０ 0 ７0 12０ x3 x1 x2 186０/1１ 100/1１ 300/1１ 43000 11-３9/11 19/１1 5/11 - 3/１1 - 3/22 ２/1１ 170/11 30/11 —１7０-３０/1１ /11 1003001860，，,0,0)T 11111110030043000∴mａx z ＝70×＋１20×＝

111111∴X*=(

四、(１０分)用大M法或对偶单纯形法求解如下线性规划模型:

mｉn z =5x1＋２x２＋4x3

3x1x22x346x13x25x310 x,x,x0123解:用大Ｍ法,先化为等效的标准模型：

5 / 13-------------

……………………………………………………………最新资料推荐…………………………………………………

mａx ｚ／ ＝－5x1－２x２－4x3 s。t。

3x1x22x3x44x510 6x13x25x3y0,j1,2,...,5j增加人工变量ｘ6、x7,得到：

ｍax ｚ/ =-5x1-２ｘ2－４x3－Ｍx６－Mx7 ｓ。t

3x1x22x3x4x64x5x710 6x13x25x3x0,j1,2,...,7j大M法单纯形表求解过程如下：

6 / 13-------------

……………………………………………………………最新资料推荐…………………………………………………

CB XB －Ｍ ｘ6 b 4 －5 ｘ1 （３） 6 －2 x2 1 3 －4M -4 x３ 2 5 0 x４ -1 ０ M －M -1/3 0 x５ 0 -1 Ｍ －M 0 -M ｘ６ 1 0 －M x7 0 １ -M 0 θＬ ４/3 -M ｘ7 1０ 5／3 －9Ｍ －7Ｍ －M 0 1/3 9M-5↑ 1 ０ －5 0 1 0 －5 0 1 0 -5 0 4Ｍ-2 １/3 1 7M-4 2／3 ４／３ -M x７ 2 -5 x1 0 1 —M 0 １/6 1/2 －5/６ —— 1 1 （2） －１ －2 —Ｍ－—2M+５2Ｍ-５/-M－5/3 M １0／3 ／3 ３ ２Ｍ－-3M+5/M-１／3 M-2／3 -Ｍ 5/３↑ ３ １/2 （1/2) 5／6 1/２ 0 １ 0 0 -1/６ －1／２ 5/6 0 －1 0 -5 x１ 5/３ ０ x4 １0／３ 2 １ 2／３ -5/2 -２５/6 1/2↑ 0 1 －2 0 1/6 １/3 １ －1１／3 －1/3 －5/6 －Ｍ -M＋5/6 1 -2 -1/3 １ －５ －2 x1 －1 １／3 ２ 1 －１ －1 1/３ x２ ２ 22 3－1 －1／３ --１/－M+1/－Ｍ＋1 ３ ３ 2∴x＝(,2,0,0,0）T

3*

最优目标函数值ｍin ｚ =－maｘ z/ ＝－(-

2222）＝ 337 / 13-------------

……………………………………………………………最新资料推荐…………………………………………………

五、(15分)给定下列运输问题:(表中数据为产地Ai到销地Bj的单位运费)

Ｂ１ B2 B3 B4 1 2 ３ 4 A1 ８ 7 ６ A2 ５ Ａ3 ９ 1０ 11 ９ 8 22 １2 dｊ １8 sｉ 1０ 80 1５ 1)用最小费用法求初始运输方案,并写出相应的总运费；(5分） 2)用１）得到的基本可行解，继续迭代求该问题的最优解。(10分) 解:用“表上作业法”求解。

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

费 用 产 地 销 地 Ｂ１ １ 8 9 8 × B2 ２ 7 1０ B3 3 ６ 1１ × B4 ４ 5 9 Si A1 2 × 20 × 18 10 A2 2 20 A3 × １0 × 30 8 / 13-------------

……………………………………………………………最新资料推荐…………………………………………………

dj 8 ２2 1２ 1８ 6０ 60 ∴初始方案：

8

B1

A2

2

B3

A3

20

B2

A1

2

B2

18

B4

10

B3

Ｚ=1×8+2×２＋6×2＋５×18＋10×２0+11×１0=424 2)①用闭回路法，求检验数:

费 用 产 地 销 地 B1 1 8 9 ８ ８ －4 × 0 × 2 B2 Ｂ3 3 6 1１ 0 × B4 4 5 9 Ｓi －2 × １8 １ × A1 7 10 22 2 －２ × 20 10 A2 2 20 A3 10 ３0 6０ dｊ １２ 1８ 60 ∵34＝１>0,其余j≤0 ∴选x34作为入基变量迭代调整. ②用表上闭回路法进行迭代调整:

费 用 产 地 9 / 13-------------

销 地 B1 B２ B3 Ｂ4 Si ……………………………………………………………最新资料推荐…………………………………………………

A１ 1 8 9 ８ 8 -３ × 0 × 2 ７ １0 22 ３ 6 -１ × 4 ５ 9 －3 × 8 2 －1 × １０ A2 １2 -1 × 2０ A3 １１ 20 10 １8 30 ６0 dj １２ 60 调整后，从上表可看出,所有检验数j≤0,已得最优解。 ∴最优方案为：

最小运费Z=１×8+2×2＋6×12+5×8＋10×20＋９×10=414

六、（8分)有甲、乙、丙、丁四个人,要分别指派他们完成Ａ、B、Ｃ、D四项不同的工作,每人做各项工作所消耗的时间如下表所示：

甲 乙 丙 丁 A 2 15 13 ４ Ｂ １0 ４ 14 15 C ９ 14 1６ 13 D 7 8 11 ９ 8

B1

A2

12

B3

A3

20

B2

A1

2

B2

8

B4

10

B4

问:应该如何指派，才能使总的消耗时间为最少?

10 / 13-------------

……………………………………………………………最新资料推荐…………………………………………………

解：用 “匈牙利法”求解。 效率矩阵表示为:

21513410941414161513708行约简 11 2110980311710595 列约简4 0 标号5

√ (0)1120*8(0)31225(0)45(0)411 20*0*58(0)3124 (0)0*4√ 525√ 5

0*134(0)6(0)3100100(0)50*2100034 (0)300 1000至此已得最优解：01∴使总消耗时间为最少的分配任务方案为:

甲→Ｃ，乙→B,丙→D，丁→A 此时总消耗时间W=9＋4+1１＋4=２８

七、(6分）计算下图所示的网络从A点到F点的最短路线及其长度。 此题在“《运筹学参考综合习题》(我站搜集信息自编）.ｄoｃ＂中已有。

B1 9 1

11 / 13-------------

……………………………………………………………最新资料推荐………………………………………………… D1 C1

B3 4 1 A 3 4 5 B2 4 5 8 3 5 4 C2 4 6 5 2 E1 6 D2 9 2 E2 7 1 F 4 7 C3 2 D3 5 解：此为动态规划之“最短路问题”,可用逆向追踪“图上标号法”解决如下： ﻬ B3 12 7 C3 8 4 1 4 4 2 D3 7 7 5 2 3 9 5 B2 3 5 C2 114 A 14 B1 5 4 8 4 6 D2 7 E2 9 5 C1 1 5 4 D1 2 6 9 2 4 1 E1 1 0 F 最佳策略为:A→B2→C1→D1→E２→F 此时的最短距离为5+4＋1+2+２=１４

12 / 13-------------

……………………………………………………………最新资料推荐…………………………………………………

13 / 13-------------