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

2023年11月21日发(作者：奔驰s320报价多少钱)

(整理)《运筹学》期

末考试试题及参考答

案

------------------------------------------作者xxxx

------------------------------------------日期xxxx

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

《运筹学》试题参考答案

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

1、在线性规划问题中,称满足所有约束条件方程和非负限制的解为 可行解 。

2、在线性规划问题中，图解法适合用于处理 变量 为两个的线性规划问

题。

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

衡的标准形式 。

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

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

两种方法。

二、(每小题５分,共10分)用图解法求解下列线性规划问题：

1)max z = 6x+4x

１2

⑴

?

2x?x?10

12

?

x?x?8

?

12

?

x?7

2

?

?

?

x，x?0

12

⑵

⑶

⑷

⑸、⑹

解:此题在“”中已有，不再重复.

《运筹学》复习参考资料。doｃ

2）min ｚ ＝－3x+２x

12

⑴

⑵

⑶

⑷

⑸

⑹、⑺

?

2x?4x?22

12

?

?x?4x?10

12

?

?

?

2x?x?7

12

?

x?3x?1

21

?

?

?

x,x?0

12

解:

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

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

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

?

2x?4x?22

12

由方程组 解出x＝１1,x=0

?

１2

x?0

2

?

??

x

1

T*

∴X==(11,0)

??

??

x

??

2

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

三、(15分)某厂生产甲、乙两种产品,这两种产品均需要Ａ、B、C三种资源，每

种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备

如下表所示:

甲９4370

乙4６10120

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

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

ABC

３６0200３00

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

2)用单纯形法求该问题的最优解.（10分)

解:１)建立线性规划数学模型:

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

1212

润，则

mａx z ＝70x+120x

1２

s．t。

?

?

9x?4x?360

12

?

?

4x?6x?200

12

?

3x?10x?300

12

?

?

x，x?0

12

2）用单纯形法求最优解：

加入松弛变量ｘ,x，ｘ,得到等效的标准模型:

３45

max z =7０x＋１20x＋0 x+０ x＋0 x

１２345

s.t。

?

?

9x?4x?x?360

123

?

?

4x?6x?x?200

124

?

3x?10x?x?300

125

?

?

x?0,j?1,2,...,5

j

列表计算如下：

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

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

CBＸBb θL

0x３３60941０090

0x42００４60１01００/3

0x53０03（10)０0130

0ｘ324０39/５０１0- 2/5４00／13

0ｘ420０01 — ３/51００／11

120x２303/10 1０0 1/1010０

7012０0０0

ｘ１x２x3x4x5

00000

７０1２0↑000

(1１

/5）

３6120００12

3４↑000-12

0010x3-３9/1119/１1

100７0x1 5/11

0112０x2- 3/22 ２/1１

７０１２０0170/1130/11

000

０

186０

/1１

100/1- 3/１

１1

300/1

１

43000

11

—１7０-３０

/1１/11

1003001860

，，,0,0)∴X=(

T*

111111

10030043000

∴mａx z ＝70×＋１20×＝

111111

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

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

1２3

?

3x?x?2x?4

123

?

?

6x?3x?5x?10

123

?

x,x,x?0

?

123

解:用大Ｍ法,先化为等效的标准模型：

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

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

mａx ｚ ＝－5x－２x－4x

／

1２3

s。t。

?

3x?x?2x?x?4

1234

?

?x?106x?3x?5x

5123

?

?

y?0,j?1,2,...,5

?

j

增加人工变量ｘ、x,得到：

67

ｍax ｚ =-5x-２ｘ－４x－Ｍx－Mx

/

123６7

ｓ。t

?

3x?x?2x?x?x?4

12346

?

?x?x?106x?3x?5x

57123

?

?

x?0,j?1,2,...,7

?

j

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

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

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

CBXBb θＬ

－Ｍｘ64（３）12-1010４/3

－5－2-400-M－M

ｘ1x2x３x４x５ｘ６x7

635０-10１-Mｘ71０

－4MMＭ-M

－M－M0

-1/301/31１/32／3-5x10——

09M-5↑4Ｍ-27M-4

5／3

－9Ｍ－7Ｍ－M

０1-Mx７2111（2）－１－2

－5—M-M－5/3M

00M-１／3M-2／3-Ｍ

1１/6１/25／60-1/６0-5x１5/３

01/2（1/2)1/２１－1０x42１

－5－5/６05/60 -5/2-２５/6

00 1/2↑1/6－5/6－Ｍ-M＋5/6

10１/31-1/3x1－1１／3

01１-2１２－1x２２

-5－211/３－1－1／３

00－1/3－１－Ｍ＋1

４／

３

—Ｍ－—2M+５2Ｍ-５/

１0／3／3３

２Ｍ－-3M+5/

5/３↑３

－1／

２

１0／

３

2／

３

－1１／

3

－５

－2

22

3

-

-１/－M+1/

３３

2

∴x＝(,2,0,0,0）

T*

3

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

/

2222

33

7 / 13-------------

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

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

Ｂ B B

１23

B

4

1 2 ３

4

A1０

1

８ 7 ６

A80

2

５

Ａ1５

3

９ 1０

11 ９

8 22 １2

d

ｊ

１8

s

ｉ

1)用最小费用法求初始运输方案,并写出相应的总运费；(5分）

2)用１）得到的基本可行解，继续迭代求该问题的最优解。(10分)

解:用“表上作业法”求解。

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

费

用

产

地

销

地

Ｂ１ B2 B3 B4 Si

１２3４

87６5

91０1１9

8×2×

××182

A1 10

20×１0×

A2 20

A3 30

8 / 13-------------

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

dj8２21２

1８

6

０

60

∴初始方案：

8

B

1

AA

23

2 20

BB

32

A

1

2

B

2

18 10

BB

43

Ｚ=1×8+2×２＋6×2＋５×18＋10×２0+11×１0=424

2)①用闭回路法，求检验数:

费

用

产

地

销

地

B1 B2 Ｂ3 B4 Ｓi

12304－2

8－4657－２

91１9１10

８22dｊ１２

８××2

×１8×2

0

××2010

A1 10

A2 20

A3 ３0

6

０

1８

60

∵＝１>0,其余≤0

?

34

?

j

∴选作为入基变量迭代调整.

x

34

②用表上闭回路法进行迭代调整:

费

用

产

地

9 / 13-------------

销

地

B1 B２ B3 Ｂ4 Si

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

A１ １０

12３-１4－3

8-３７6５－1

9１09-1１１

８22dj１２

8××2

×8×１2

0

××2010

A2 2０

A3 30

１8

６0

60

调整后，从上表可看出,所有检验数≤0,已得最优解。

?

j

∴最优方案为：

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

六、（8分)有甲、乙、丙、丁四个人,要分别指派他们完成Ａ、B、Ｃ、D四项不

同的工作,每人做各项工作所消耗的时间如下表所示：

甲2１0９7

乙15４148

丙13141６11

丁４1513９

AＢCD

8

B

1

AA

23

12 20

BB

32

A

1

2

B

2

8 10

BB

44

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

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

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

解：用 “匈牙利法”求解。

效率矩阵表示为:

??

??

??

??

??

??

??

21097

154148

13141611

415139

??

0875

??

行约简

??

110104

??

2350

??

??

01195

??

列约简

标号

√

????

(0)825(0)825

????

????

11(0)5411(0)45

????

23(0)203(0)0

????

????

0124051245

**

????

**

√

√

??

??

??

??

??

??

??

06(0)3

*

13(0)54

430(0)

(0)1023

0100

1000

0010

0001

*

??

??

??

至此已得最优解：

??

??

??

??

∴使总消耗时间为最少的分配任务方案为:

甲→Ｃ，乙→B,丙→D，丁→A

此时总消耗时间W=9＋4+1１＋4=２８

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

此题在“＂中已有。

《运筹学参考综合习题》(我站搜集信息自编）.ｄoｃ

B

1

9 1

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

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

D

1

C

1

BD

3 3

4

1 4 7

A

3

4 8

5 3

BD

2 2

4

5 5

5

C

2

4

6

2

E

1

6

9

2

E

2

1

F

4

7

C

3

2

5

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

?

BD

3 3

12

7

C

3

8 7

4

1 4 7

4

2

5

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

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