《运筹学》期末考试试题及参考答案

《

运筹学》试题参考答案 一

、填空题�每空2分�共10分� 1、在线性规划问题中�称满足所有约束条件方程和非负限制的解为 可行解 。 2、在线性规划问题中�图解法适合用于处理 变量 为两个的线性规划问题。 3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点�化为供求平衡的

标准形式 。 4、在图论中�称 无圈的 连通图为树。 5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种

方法。 二、�每小题5分�共10分�用图解法求解下列线性规划问题� 1

�m a x z = 6x 1+4x 2

�����

�

�

������078102212

2121x x x x x x x � 解

�此题在“《运筹学》复习参考资料.d o c ”中已有�不再重复。 2

�m i n z =�3x 1+2x 2 ��

�

���

�

��

����������0,137210422422121212121x x x x x x x x x x

解

�

⑴

⑵

⑶ ⑷ ⑸

⑹、⑺

⑴

⑵

⑶ ⑷ ⑸、⑹

可

行解域为a b c d a �最优解为b 点。 由

方程组���

���02242221x

x x 解出x 1=11�x 2=0 ∴X *

=��������21x x =�11�0�T

∴

m i n z =�3×11+2×0=�33

三、�15分�某厂生产甲、乙两种产品�这两种产品均需要A 、B 、C 三种资源�每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备

如下表所示�

A

B

C

甲 9 4 3 70 乙 4 6 10 120 360 200 300

2

�用单纯形法求该问题的最优解。�10分� 解

�1�建立线性规划数学模型� 设甲、乙产品的生产数量应为x 1、x 2�则x 1、x 2≥0�设z 是产品售后的总利润

�则 m

a x z =70x 1+120x 2 s

.t . �����

��

�������030010320064360492121

2121x x x x x x x x � 2

�用单纯形法求最优解� 加

入松弛变量x 3�x 4�x 5�得到等效的标准模型� m

a x z =70x 1+120x 2+0 x 3+0 x 4+0 x 5 s

.t . �

����

�

�

���������

��5,...,2,1,030010320064360495214213

21j x x x x x x x

x x x j 列

表计算如下�

C

B X

B b

7

0 1

20 0

θ

L x

1 x

2 x

3 x

4 x

5 0

x 3 3

60 9

4

1

9

0 0 x 4 200 4 6 0 1 0 100/3 0 x 5 300 3 �10� 0 0 1 30

0 0 0 0 0 70 120↑ 0 0 0 0 x

3 240 39/5 0 1 0 - 2/5 400/13 0 x

4 20 �11/5� 0 0 1 - 3/

5 100/11 120 x 2 30 3/10 1 0 0 1/10 100

36 120 0 0 12 34↑ 0 0 0 �12 0 x

3 1

860/11 0 0 1 �39/11 19/11 70 x 1 100/11 1 0 0 5/11 - 3/11 120 x 2 300/11 0 1 0 - 3/22 2/11

1

14

3000

70 120 0 1

70/11 30/11 0 0

-170/11 �30/11 ∴

X *=�1

1100�1

1300�

1

11860�

0�0�T ∴m a x z =70×1

1100+

120×1

1300=1

14

3000

四

、�10分�用大M 法或对偶单纯形法求解如下线性规划模型� m

i n z =5x 1�2x 2�4x 3 �

��

��

�������0,,10536423321321321x x x x x x x x x

解

�用大M 法�先化为等效的标准模型� m

a x z / =�5x 1�2x 2�4x 3 s

.t . �

��

��

�������

���5,...,2,1,01053642353214

321j y x x x x

x x x x j 增

加人工变量x 6、x 7�得到� m

a x z / =�5x 1�2x 2�4x 3�M x 6�M x 7 s

.t �

��

��

����

���

�

�

���7,...,2,1,010536423753216

4

321j x x x x x x x x x x x j 大

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