运筹学综合复习题

1、已知原问题为

32134max x x x Z ++=

??????

?≤≥=++≥+-≤-+无符号限制

3213213

21321,0,041632532x x x x x x x x x x x x 要求:(a) 写出其对偶问题; (b) 已知原问题最优解为()T

*=4,0,0X ,试根据对偶

理论,直接求出对偶问题的最优解。

2、分配甲、乙、丙、丁四个人去完成A 、B 、C 、D 、E 五项任务。每个人完成各项任务的时间如下表所示。

任务

人甲乙丙丁

A B C D E

2529314237393424

38

26203328403236

23

45

2742

任务E 必须完成,其他4项中可任选3项完成。试确定最优分配方案,使完成任务的总时间最少。

3、用标号法求下图中1v 到7v 的最短距离

1

v 2

v 3

v 4

v 5

v 6

v 7

v 91273

4

8

7

38

510

4、用标号算法求下图从s 到t 的最大流量及最小割。弧旁数字为()ij ij f c

运筹学综合复习题

s

t

45)

)

5、某公司拟将五台设备分配给下属的甲、乙、丙三个工厂,各工厂获得这种设备后,可以为公司带来的盈利如下表所示:

工厂

盈利设备数

0123

45

000

354710

6

9111112

1112

1311

13

问分配各工厂多少台这种设备,可以为公司带来盈利总和为最大。用动态规划方法求解。

6、一自动化工厂的组装车间从本厂的配件车间订购各种零件。估计下一年度的某种零件的需求量为20000单位,单位产品的年存储费为其价值的20%,该零件每单位价值为20元,所有订货均可及时送货。一次订货的费用是100元,车间每年工作日为250天。

(1)计算经济订货批量; (2)每年订货多少次;

(3)如从订货到交货的时间为10个工作日,产出是一致连续的,求订货点。

7、某企业要确定下一计划内产品产量。根据以往经验及市场调查,已知产品销路较好、一般和较差的概率分别为0.3、0.5和0.2,采用大批量生产时可能获得的利润分别为20万元、12万元和8万元;采用中批量生产时可能获得的利润分别为16万元、16万元和10万元;采用小批量生产时可能获得的利润分别为12万元、12万元和12万元。试用期望损失准则作出最优决策。

1.解:对偶问题为

32142min y y y W ++=

??????

?≤≥=++-≤+-≥++无符号限制

3213213

21321,0,036543132y y y y y y y y y y y y 将()T

*=4,0,0X 代入原问题的三个约束条件知,

?????=++>=+-<-=-+****

*****4

12463220532321

321321x x x x x x x x x 即对*X 而言,前两个约束为松约束,由互补松弛条件知,必有021==*

*y y ,代入对

偶问题的第3个约束得33=*y ,故对偶问题的最优解为()3,0,0=*Y 。

2解:由于任务数多于人数,所以需要有一名假想的人,设为戊。因为工作E 必须完成,故设戊完成E 的时间为M (M 为非常大的数),其余的假想时间为0,建立的效率表矩阵如下:

任务

人甲乙丙丁A B C D E

2529314237393424

38

26203328403236

23

452742

0000

M

用指派方法求解过程如下: 每行减 ???????? ??M 00004523364224324028273433202638393742312925 023272025 →???????? ??M 000022013191513107130618191217640→()()()()???????? ??M 000017013191013107806181971764004044 每列减500

04004--

→()()

()()

????????

?

?M 40041309

15101710114021419317

20001010→()()

()()()

?????

??

? ??M 50041208

14

001810

113011318318200

010

00-

故最优解为153********=====x x x x x ,其余0=ij x ,即甲-B ,乙-D ,丙-E ,丁-A ,C 放弃。最少的时间为105个小时。

3.解:

1

v 2

v 3

v 4

v 5v 6v 7

v 9

1273

4

87

38

510

1

v 2

v 3

v

4

v 5

v 6

v 7

v 9

1273

4

8

7

38

510

80

(a) (b)

1

v 2

v 3

v 4

v 5

v 6

v 7

v 9

1273

4

8

7

38

510

809

10

1

v 2

v 3

v 4

v 5

v 6

v 7

v 9

1273

4

8

73

8

510

809

(c) (d)

10

1

v 2

v 3

v 4

v 5

v 6

v 7

v 9

1273

4

8

7

3

8

510

809

11

10

1

v 2

v 3v

4

v 5

v 6

v

7v 9

12734

8

73

8

510

809

11

13

(e) (f)

4.解:找到一条从s 到t 的增广链,在图中由粗线标出

s

t

运筹学综合复习题

)

)

即t E D C B A s →→←←→→,增广链最大的调整量为1,调整后如下图所示

运筹学综合复习题

t

)

再用标号法找增广链,点A 标号后,增广链中断,表明已找不出增广链,此时网络中的可行流即为最大流,其流量为5+3+5=13。最小割为()()()(){}B A C s D s V V ,,,,,,=

5.解:将五台设备分配给三个工厂看成依次分三个阶段(用k 表示,3,2,1=k )。决策变量k x 表示第k 阶段向工厂分配的设备数;状态变量k s 表示第k 阶段到第3阶段可供分配的设备数。

允许决策集合为: (){}

k k k k k k s x x x s D ≤=的非负整数,且为不大于5

状态转移方程为:k k k x s s -=+1

用()k k x p 表示第k 阶段分配设备数为k x 时,该厂的盈利额。 基本方程为 ()()

()(){}11max

++∈+

=k k k k s D x k k s f x p s f k k k 3,2,1=k

用逆序算法,当3=k 时,()()

(){}3333333max

x p s f s D x ∈=

3x 3s ()

33x p ()

33s f *3

x 0123

45

123

45

000000

44444

6666

111111

1212

1304

6

1112

13

123

45

当2=k 时,()()

()(){}332222222max

s f x p s f s D x +=∈

2

x 2

s ()()

3322s f x p +()

22s f *2

x 012345

0123

45

0+40+60+110+120+130+0510

1416

210

1222

1或2

05+45+65+115+125+0

10+410+610+1110+011+411+611+011+411+0

11+

当1=k 时,()()

()(){}221111111max

s f x p s f s D x +=∈

1x 1

s ()()

2211s f x p +()

11s f *1

x 012345

521210+163+147+109+512+013+2

0或

最优分配方案是:分配甲厂0台、乙厂2台、丙厂3台;或分配甲厂2台、乙厂2台、丙厂1台。总盈利最大为21。

6、解:(1) 4%2020=?=P C 元/件.年;100=D C 元/次;20000=D 件

10004

20000

10022=??==

*P

D C D

C Q 件

(2) 每年订货次数=

20100020000==*

Q

D 次 (3) 10个工作日的需求量=800250

20000

10=?件,故订货点为800件。

7、解:设321,,E E E 分别表示销路较好、一般和较差,321,,S S S 分别表示大批、中批和小批,则该问题的收益矩阵为: 321

E E E

??

??

?

?????=12121210161681220321S S S A 其对应机会损失矩阵为: 32

1

E E E

????

??????=04

8

20

4

440321S S S L 三个待选方案的期望机会损失分别为:

8.22.045.043.00:1=?+?+?S 万元 6.12.025.003.04:2=?+?+?S 万元

4.42.00

5.043.08:3=?+?+?S 万元

故最优方案为方案2S ,即中批量生产。

相关推荐
相关主题
热门推荐