效率矩阵表示为�
� 2 10 9 7 �
�
�
� 15 4 14
8�
� 13 14 16 11 �
�� �
4
15 13
9
�� �
行约简
�0
8
7
�
� 11 0 10
�2
3
5
�� �
0
11 9
5 � 列约简 �
4�
0 � 标号
5
�� �
� (0)
8
2
5�
�
�
� 11 (0) 5
4�
�2
3
(0)
0* �
�
�
18
60
费销
用 地
B1
B2
B3
B4
Si
产
地
1
2
3
�1
4
�3
A1
10
8
2
×
×
8
�3
7
�1
6
5
A2
20
×
×
12
8
9
0
10
11
�1
9
A3
30
×
20
×
10
60
dj
8
22
12
18
60
调整后�从上表可看出�所有检验数� j ≤0�已得最优解。
∴最优方案为�
第 8 页 共 11 页
8
B1
12
B3
A1
A2
2
B2
8
可行解域为 abcda�最优解为 b 点。
�2 x1 � 4 x2 � 22
由方程组 �
�
x2 � 0
∴X*=
� �� �
x1 x2
� �� �
=�11�0�T
∴min z =�3×11+2×0=�33
解出 x1=11�x2=0
三、�15 分�某厂生产甲、乙两种产品�这两种产品均需要 A、B、C 三种资源� 每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储
120
x2 300/11
0
1
0 - 3/22 2/11
43000
70
120
0
170/11 30/11
11
0
0
0
-170/11 �30/11
∴X*=� 100 � 300 � 1860 �0�0�T
11
11
11
∴max z =70× 100 +120× 300 = 43000
11
11
11
Байду номын сангаасθL
90 100/3
s.t.
�3 x1 � x2 � 2 x3 � x4
� �
6
x1
�
3x2
�
5 x3
� �
yj
�
0,
j
� 1,2,..., 5
�4 � x5 � 10
增加人工变量 x6、x7�得到�
max z/ =�5x1�2x2�4x3�Mx6�Mx7
s.t
�3 x1 � x2 � 2 x3 � x4 ��6 x1 � 3x2 � 5 x3
3
A
5
4
9 B1
5
4 3
B2 5
1
B3
7
1 C1
5
8 C2 4
6
4 4
C3
2
D1
4
2
E1 6
D2 9
E2 7
5
D3
1
F 2
解�此为动态规划之“最短路问题”�可用逆向追踪“图上标号法”解决如下�
第 10 页 共 11 页
3 14
5 A
4
14 9
B1 5
4 9
3 B2
5
1
B3
7
5 1
C1 5
8
C2 4 6
0
�5 x1 5/3
1
1/2
5/6
0 �1/6 0
1/6
10/3
0 x4 1
0
�1/2� 1/2
1 �1/2 �1
1/2
2
�5
�5/2 �25/6 0
5/6
0
�5/6
0
1/2↑ 1/6
0
�5/6 �M �M+5/6
�5 x1 2/3
1
�2 x2 2
0
0
1/3
�1 1/3
1
�1/3
1
1
2
�1 �2
1
�5 � 22
⑵ ⑶ ⑷ ⑸、⑹
解�此题在“《运筹学》复习参考资料.doc”中已有�不再重复。
2�min z =�3x1+2x2
�2 x1 � 4 x2 � 22
�
�� �
� 2
x1 x1
� �
4 x
x
2
2 � 10 �7
� �
x1
�
3x2
�1
�� x1 , x 2 � 0
⑴ ⑵ ⑶ ⑷ ⑸ ⑹、⑺
解�
第 1 页 共 11 页
学习资料分享
[公司地址]
《运筹学》试题参考答案
一、填空题�每空 2 分�共 10 分� 1、在线性规划问题中�称满足所有约束条件方程和非负限制的解为 可行解 。 2、在线性规划问题中�图解法适合用于处理 变量 为两个的线性规划问题。 3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点�化为供求平衡 的标准形式 。
�� �
1
0
1 0� �
0 0�
0 1�
0
0
�� �
∴使总消耗时间为最少的分配任务方案为�
甲→C�乙→B�丙→D�丁→A 此时总消耗时间 W=9+4+11+4=28
七、�6 分�计算下图所示的网络从 A 点到 F 点的最短路线及其长度。
此题在“《运筹学参考综合习题》�我站搜集信息自编�.doc”中已有。
11
4 4
C3
2
12
8
最佳策略为�A→B2→C1→D1→E2→F
此时的最短距离为 5+4+1+2+2=14
4
D1
4
2
6 D2
9 7
7 5
D3
7
1
E1
1
0
F 2 E2
2
第 11 页 共 11 页
�4M �7M
M
M �M �M
9M�5↑ 4M�2 7M�4 �M �M
0
0
�5 x1 4/3
1
1/3
2/3 �1/3 0
1/3
0
——
�M x7 2
0
1
1
�2� �1 �2
1
1
�5
-M�5/3 -M�10/3 -2M+5/3 M 2M�5/3 -M
0
M�1/3 M�2/3 2M�5/3↑ �M �3M+5/3
300
3
�10�
0
0
1
0
0
0
0
0
70
120↑
0
0
0
0
x3
240 39/5
0
1
0
- 2/5
0
x4
20 �11/5� 0
0
1
- 3/5
120
x2
30 3/10
1
36
120
34↑
0
0
x3 1860/11 0
0
0
0
1/10
0
0
12
0
0
�12
1
�39/11 19/11
70
x1 100/11
1
0
0
5/11 - 3/11
3
0
�2 �11/3 1
1/3
�1
�1/3
0
�1/3 �1 �1/3 �M+1 �M+1/3
∴x*=�
2 3
�2�0�0�0�T
最优目标函数值 min z =�max z/ =��� 22 �= 22
3
3
五、�15 分�给定下列运输问题��表中数据为产地 Ai 到销地 Bj 的单位运费�
第 6 页 共 11 页
B1
B2
B3
B4
si
A1
1
2
3
4
10
A2
8
7
6
5
80
A3
9
10
11
9
15
dj
8
22
12
18
1�用最小费用法求初始运输方案�并写出相应的总运费��5 分� 2�用 1�得到的基本可行解�继续迭代求该问题的最优解。�10 分� 解�用“表上作业法”求解。
1�先用最小费用法�最小元素法�求此问题的初始基本可行解�
� �
xj
�
0,
j
� 1,2,..., 7
� x6
�4
� x5
� x7 � 10
大 M 法单纯形表求解过程如下�
第 5 页 共 11 页
�5
CB XB b x1
�2
�4
0
0 �M �M
θL
x2
x3
x4
x5
x6
x7
�M x6 4 �3�
1
2
�1