2024年4月21日发(作者：淦冰冰)
运筹学习题答案
第一章（39页）
1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最 优
解、无界解还是无可行解。
（1） max
z
=论
x
2
5
x
1
+10
x
2
<50
x
1
+
x
2
_ 1
x
2
_4
为，
X
2 _0
（2） min z=
x
1
+1.5
x
2
x-
i
+3
X
2
_3
x-
i
+
x
2
丄 2
x-
i
，
x
2
亠 0
（3） max z=2
x
1
+2
x
2
x-
1
-
x
2
_-1
-0.5x-
i
+
x
2
-2
x-
i
，
x
2
-0
（4） max z=
x
j
+
x
2
x-
i
-
x
2
-0
3
X
r
_
X
2
__3
x
1
，
x
2
-0
解：
（1） （图略）有唯一可行解，max z=14
（2） （图略）有唯一可行解，min z=9/4
（3） （图略）无界解
（4） （图略）无可行解
1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。
(1) min 2=-3捲+4乂
2
-2乂
3
+5乂
4
4
X
i
-
X
2
+2
X
3
-
X
4
=-2
x-
i
+
x
2
+3
x
3
- < 14 -2 x-
i
+3
x
2
-
x
3
+2
x
4
亠 2
x
-
,
X
2
,
X
3 _0
,
X
4
无约束
n m
J 二、、'
i =1 k 4
a
ik
x
ik
m
为
-X
k
= -1( =1,…,n)
k 4
x
ik
丄0 (i=1 …n; k=1,…,m)
(1)解：设 z=-z ,
X
4
=
X
5
-
X
6
,
X
5
,
X
6
_0
标准型：
Max z =3
x
1
-4
x
2
+2
x
3
-5(
x
5
-
x
6
)+0
x
7
+0
x
8
-M
x
9
-M
x
10
s. t .
-4
x
1
+
x
2
-2
x
3
+
x
5
-
x
6
+
x
10
=2
x-
i
+
x
2
+3
x
3
-
x
5
+
x
6
+
x
7
=14
-2 x-
i
+3
x
2
-
x
3
+2
x
5
-2
x
6
-
x
8
+
x
9
=2
X
,
X
2
,
X
3
,
X
5
,
X
6
,
X
7
,
X
8
,
X
9
,
-0
X
10
初始单纯形表
：
Cj T
C
B
X
B
3
b
X
-4
X
2
2
X
3
-5
X
5
5
X
6
0
X
7
0
X
8
-M
X
9
-M
e
X
10
-M
X
10
2
X
7
-4
1
1
1
-2
3
1
-1
-1
1
0
1
0
0
0
0
1
0
2
14
0
14
-M
X
9
r
2
-2
[3]
-1
2
-2
0
-1
-M
1
0
0
0
2/3
-z
4M 3-6M 4M-4 2-3M 3M-5 5-3M
0
(2)解：加入人工变量
X
i
,
X
2
,
X
3
,…
X
n
，得:
n m
Max s=(1/
p
k
)二 二
ik
x
ik
-M
x
1
-M
x
2
-…..-M
x
n
i=1 7
s.t.
m
x
+ 迟
X
ik
=1
k=4
(i=1,2,3…,n)
(i=1,2,3…n; k=1,2….,m)
x
k
兰0,
X
j
20,
C
B
M是任意正整数 初始单纯形表：
-M •
a
如/
12/
C
j
…
M M
/ P
k
/ P
k
b
…
H rn/^
/ P
k
…
a
n1/
/P
k
X
n1
a
n2/
/ P
k
…
a
mn
0i
X
B
X
1
X
2
X
n
X
11
X
12
X
1m
X
n2
X
nm
-M
-M
…
-M
-s
X
1
X
2
1
1
…
1
n
M
1 0
0 1
… …
0 0
0 0
•
…
0 1
•
0
…
…
… …
•
1 0
…
1
0
…
0
%+M
•
…
0
0
0
…
1
%+
M
•
…
0
…
X
n
•
…
… …
•
0
…
0
…
1
•
0
…
… …
•
1
…
0
%枷
陥/
/ 4
-+M
%+
M
7和
1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行 解，并代入目标函
数，确定最优解。
(1) max z=2
x
4
+3
x
2
+4
x
3
+7
x
4
2
x
4
+3
x
2
-
x
3
-4
x
4
=8
X
1
-2
X
2
+6
x
3
-7
X
4
=-3
(2) max z=5
x
1
-2
x
2
+3
x
3
-6
x
4
X
1
,
X
2
,
X
3
,
X
4
-0
x
1
+2
x
2
+3
x
3
+4
X
4
=7
2
x
1
+
x
2
+
x
3
+2
X
4
=3
x
1
x
2
x
3
x
4
_0
(1) 解：
系数矩阵A是：
2
*
3-1^
_2 6 —7 一
令 A=(
R
,
P
2
,巳,
P
4
)
P
与卩
2
线形无关，以(
R
,
P
2
)为基，捲,
X
2
为基变量。
有 2
X
!
+3
x
2
=8+
x
3
+4
x
4
x-
i
-2
x
2
=-3-6
x
3
+7
x
4
令非基变量
X
3
，
X
4
=0
解得：捲=1;
x
2
=2
基解X
=( 1, 2, 0, 0
)
为可行解
(
1
)
T
乙=8
同理，以(
P
，巳)为基，基解X
⑵
=(45/13, 0,-14/13, 0
)
是非可行解； 以(
P
, R )为基，基解
T
X=(34/5, 0, 0, 7/5
)
T
是可行解，
Z
3
=117/5； 以(
F
2
,巳)为基，基解 X
⑷
=(0, 45/16, 7/16, 0
)
是
(3)T
可行解，
Z
4
=163/16； 以(
P
2
,
P
4
)为基，基解X
⑸
=(0, 68/29, 0, -7/29
)
是非可行解；
T
以(
P
4
,巳)为基，基解X
=(0, 0, -68/31, -45/31
)
是非可行解；
(6)T
最大值为
Z
3
=117/5;最优解 X
⑶
=(34/5, 0, 0, 7/5
)
。
T
(2) 解：
系数矩阵A是：
12 3 4
$112-
令 A=（
R
,
P
2
,巳,
P
4
）
R
,
P
2
线性无关，以(
P
i
,
P
2
)为基，有:
x-
i
+2
X
2
=7-3
x
3
-4
x
4
2
X
1
+
X
2
=3-
X
3
-2
X
4
令
X
3
,
X
4
=0 得
X
-
I
=-1/3,
X
2
=11/3
基解 X
= (-1/3,11/3, 0, 0
)
为非可行解；
(1)T
同理，以(
P
,
P
j
)为基，基解 X
= (2/5, 0, 11/5, 0
)
是可行解
Z
2
=43/5;
(2)T
以(
P
, R )为基，基解X
⑶
=(-1/3, 0, 0, 11/6
)
T
是非可行解；
以(
P
2
,
P
j
)为基，基解X
⑷
=(0, 2, 1, 0
)
是可行解，
Z
4
=-1；
T
以(
P
4
,
P
j
)为基，基解 X
=(0, 0, 1, 1
)
是
Z
6
=-3
；
(6)T
最大值为
Z
2
=43/5;最优解为X⑵=(2/5, 0, 11/5, 0
)
。
T
1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步
相当于图形的哪一点。
（1） max
Z
=2
X
1
+
X
2
3
X
1
+5
X
2
乞 15
6
X
1
+2
x
2
虫24
X
1
,
X
2
-0
（2） max
Z
=2
X
1
+5
X
2
X
<^4
2
x
2
辽 12
3
X
1
+2
X
^
18
X
-
I
,
X
2
-0
解：（图略）
（1） max z=33/4 最优解是
（
15/4,3/4） 单纯形法：
标准型是 max z=2 为 +
x
2
+0
x
3
+0
x
4
s.t. 3
x
!
+5
x
2
+
x
3
=15
6捲 +2
X
2
+
x
4
=24
X
i
,
X
2
,
X
3
,沧
—0
单纯形表计算：
C
j
C
B
X
B
X
3
X
4
2
b
15
24
0
3
4
-8
3/4
15/4
-33/4
X
1
1
X
2
0
X
3
0
X
4
4
0
0
3
[6]
2
0
1
0
0
1
0
5
1
0
0
1
0
0
1/4
-1/12
-1/12
0
1
5
4
2
1
[4]
1/3
1/3
1
0
0
-z
0
2
X
3
X
1
0
-1/2
1/6
3/4
12
-z
1
2
X
2
X
1
-1/3
-1/8
5/24
-7/24
-z
解为：（15/4, 3/4, 0, 0
）
T
Max z=33/4
迭代第一步表示原点；第二步代表 C点（4, 0，3，0
）
；
T
第三步代表B点（15/4，3/4，0，0
）
。
T
（2）解：（图略）
Max z=34 此时坐标点为（2，6）
单纯形法，标准型是：
s.t.
x
1
+
x
3
=4
Max z=2
x
1
+5
x
2
+0
x
3
+0
x
4
+0
x
5
2
X
2
+
X
4
=12
3
X
-
I
+2
X
2
+
X
5
=18
X
i
,
X
2
,
X
3
,
X
4
,
X
S
-0
俵略)
最优解 X= (2, 6, 2, 0, 0
)
T
Max z=34
迭代第一步得X
(1)
= (0, 0, 4, 12, 18
)
T
表示原点，迭代第二步得X
⑵
=(0, 6,
4, 0, 6
)
T
，第三步迭代得到最优解的点。
1.5以1.4题(1)为例，具体说明当目标函数中变量的系数怎样变动时，满足约
个顶点，都可能使得目标函数值达到最优。
解：目标函数： max z=C|
X
1
+
c
2
X
2
(1) 当 C
2
=0 时
X
2
=- ( &/
c
2
)
X
1
+z/
c
2
其中，k=_G/
c
2
k
AB
=-3/5 ,
k
Bc
=-3
k「k
Bc
时，
c
1
, 9 同号。
当
C
2
・、0时，目标函数在C点有最大值
当cr 0时，目标函数在原点最大值。
k
B
C
- k-
k
A
B
时，
c
1
, $ 同号。
当
C
2
0,目标函数在B点有最大值；
当cr 0, 目标函数在原点最大值。
k
A
B
- k - 0
时，
c
1
,
c
2
同号。
当c^ 0时，目标函数在A点有最大值
当
c
2
0时，目标函数在原点最大值。
k -0时，
C
l
, °异号。
束条件的可行域的每一
当
C2,
0,
C
l
- 0时，目标函数在A点有最大值；
当
C
2
0,
C
l
0时，目标函数在C点最大值。
k=
k
AB
时，q,
C
2
同号
当
C
2
・、0时，目标函数在AB线断上任一点有最大值
当C
2
- 0,目标函数在原点最大值。
k=
k
B
C
时，
C
l
，
C
2
同号。
当
C2-
0时，目标函数在BC线断上任一点有最大值
当C
2
- 0时，目标函数在原点最大值。
k=0 时，
C
l
=0
当
C
2
・、0时，目标函数在A点有最大值
当
C
2
■ 0，目标函数在OC线断上任一点有最大值
（2）当
C
2
=0 时，max z=
C
l
x
i
C
1
-0时，目标函数在C点有最大值
C
l
0时，目标函数在OA线断上任一点有最大值
C
l
=0时，在可行域任何一点取最大值。
1.6分别用单纯形法中的大 M法和两阶段法求解下列线性问题,
解。
（1）max z=2
x
1
+3
x
2
-5
x
3
x
1
+
x
2
+
x^
- 15
2
x
1
-5
x
2
+ x<^ 24
x
1
,
x
2
亠0
(2) min z=2
x
1
+3
x
2
+
x
3
X
+4
x
2
+2
X
3
_ 8
并指出属于哪类
3 禺 +2
x
2
- 6
X
i
,
X
,
X
3
- 0
(3) max z=10
x
1
+15
x
2
+12
x
3
5
x
1
+3
x
2
+
X
3
- 9
-5x-
i
+6
X
2
+15
x
3
_ 15
2
x
1
+
x
2
+ x^ 5
X
1
,
X
2
,
X
3
-0
(4) max z=2
x
1
-
x
2
+2
x
3
x-
i
+
x
2
+
x
3
丄 6
-2 x-
i
+
x
3
亠 2
2
x
2
-
x
3
_0
X
1
,
X
2
,
X
3
-0
解：(1)解法一：大M法
化为标准型：
Max z=2
x
1
+3
x
2
-5
x
3
-M
x
4
+0
x
5
-M
x
6
s.t. x-
i
+
x
2
+
x
3
+
x
4
=7
2 x-
i
-5
x
2
+
x
3
-
x
5
+
x
6
=10
x
1
,
x
2
,
x
3
, ,
x
4
,
x^
0 M 是任意大整数。
单纯形表：
C
j
C
B
2
b
7
x
-
3
X
2
-5
X
3
-M
X
4
0
X
5
-M
X
6
0
i
X
B
X
4
-M
1 1 1 1 0 0
7
-M
X
6
10
17M
2
5
2M-10
4/7
45/7
-102/7
[2]
-5
1
2M-5
1/2
1/2
0
0
1
0
0
2/7
5/7
-1
-M
1/2
-1/2
1
0
-1/2
1/2
5
-z
-M
X
4
X
i
3M+2 3-4M
[7/2]
0
1
0
0
1
0
-5/2
4/7
-
2
-z
3
(7/2)M+8 0.5M-6
1/7
6/7
-50/7
0.5M+1 -1.5M-1
1/7
-1/7
-1/7
1/7
-M+1/7
X
2
X
i
1
0
0
2
-z
最优解是：
-M-16/7 -1/7
X= (45/7, 4/7, 0, 0, 0
)
T
目标函数最优值 max z=102/7
有唯一最优解。
解法二：
第一阶段数学模型为 min w=
x
4
+
x
6
S.t. % +
x
2
+
x
3
+
x
4
=7
2 x-
i
-5
x
2
+
x
3
-
x
5
+
x
6
=10
X
!
,
X
2
,
X
3
,
X
4
，
x
5
,
x
6
-0
(单纯形表略)
最优解
X=(45/7，4/7，0，0，0
)
T
目标函数最优值 min w=0 第二阶段单纯形表为：
3
C
j
2
C
B
X
B
X
2
X
1
-5
X
3
0
X
5
q
b
4/7
45/7
-102/7
X
1
X
2
3
2
最优解是
0
1
0
1
0
0
1/7
6/7
-50/7
1/7
-1/7
-z
-1/7
X= (45/7, 4/7, 0, 0, 0
)
T
Max z=102/7
(2) 解法一：大M法
z =-z 有 max z =-min (-
z
) =-min z
化成标准形：
Max
z
=-2 x-
i
-3
x
2
-
x
3
+0
x
4
+0
%
5
-M
x
6
-M
x
7
S.T.
捲 +4
x
2
+2
x
3
-
x
4
+
x
6
=4
3
x
-
+2
X
2
-
X
5
+
x
=6
X
!
,
X
2
,
X
3
,
X
4
,
X
5
,
x
e
,
X
7
—0
(单纯性表计算略)
线性规划最优解X=(4/5, 9/5, 0, 0, 0 , 0
)
T
目标函数最优值min z=7
非基变量
X
3
的检验数
-3
=0,所以有无穷多最优解。
两阶段法：
第一阶段最优解X=(4/5, 9/5, 0, 0, 0, 0
)
是基本可行解,min w=0
T
第二阶段最优解(4/5, 9/5, 0, 0, 0, 0
)
min z=7
T
非基变量
x
3
的检验数二
3
=0,所以有无穷多最优解
（3）解：大M法
加入人工变量，化成标准型：
Max z=10
X
!
+15
X
2
+12
X
3
+0
x
4
+0
x
5
+0
x
6
-M
x
7
s.t. 5
x
-
+3
X
2
+
X
3
+
X
4
=9
-5 捲+6
x
2
+15
x
3
+
x
5
=15
2
x
2
+
x
3
-
x
6
+
x
7
=5
X
i
,
X
2
,
X
3
,
X
4
,
0
X
5
,
X
6
,
X
7
—
单纯形表计算略
当所有非基变量为负数，人工变量
X
7
=0.5
,
所以原问题无可行解
两阶段法（略）
（4）解法一：大M法
单纯形法，（表略）非基变量
X
4
的检验数大于零，此线性规划问题有无界解
两阶段法略
1.7求下述线性规划问题目标函数 z的上界和下界;
Max z=
G
% +
c
2
x
2
a^x-
i
a
12
x
2
- b
i
a
2i
X
1 ■ 822
X
2 — b2
其中：1_
G
—3,4_g _6,8_0 _12 ,10_b
2
_14
,
-1 _a
1
^3,2_a
12
_5
,
2 _ a
21
_ 4 , 4 _ a
22
_ 6
解：
求Z的上界
Max z=3
X
-
I
+6
X
2
s.t.-论 +2
x
2
_ 12
2 为 +4
x
2
_ 14
加入松弛变量，化成标准型，用单纯形法解的，最优解
X=(0, 7/2, 5, 0
)
T
目标函数上界为z=21
存在非基变量检验数等于零，所以有无穷多最优解 求z的下界
线性规划模型：
Max Z=
X
-
I
+4
X
2
s.t. 3
X
1
+5
x
2
岂 8
4
X
1
+6
X
^10
X
2
,
X
^0
加入松弛变量，化成标准型，解得:
最优解为
X= （0, 8/5, 0, 1/5
）
T
目标函数下界是z=32/5
1.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变 量，
a1
，，，d，，为待定常数，试说明这些常数分别取何值时，以下 结论成立。
（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；
a2a3C102
（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为为，
换出变量为
x
6
基b
4
X
1
X
2
X
3
X
4
X
a
2
X
6
X
3
d
x
4
2
X
3
C
j _Zj
a
-3
-5
C
2
1
0
0
0
0
1
0
0
0
0
1
0
-1
a
3
C
1
-1
-4
-3
解：
（1） 有唯一最优解时，d—O,
c
「0,
c<
0
（2） 存在无穷多最优解时，d_0,
G
_0,
C
2
=0或d_0,
C
1
=0,
C
2_
0.
（3） 有无界解时，d_0, c$0, q、0且a$0
（4） 此时，有 d 丄0,
c<
0 并且 & _
c
2
,
a
3
> 0
, 3/
a
3
“ d/4
班次
1
2
3
4
5
6
设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公 交线
路至少配备多少司机和乘务人员。列出线型规划模型。
解：
设
X
k
（k=1 , 2, 3, 4, 5, 6）为
X
k
个司机和乘务人员第k班次开始上班
1.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下:
时间 所需人数
6点到10点
[60
10点到14点
70
14点到18点
：
60
18点到22点
50
22点到2点
”0
2点到6点
30
建立模型：
Min z= x-
i
+
x
2
+
x
3
+
x
4
+
x
5
+
x
6
s.t. x-
i
+ x^ _ 60
X
i
+
x
2
亠 70
x
2
+
x
3
亠 60
x
3
+
x
4
_50
x
4
+
x
5
_20
x
5
+
x
6
_30
X
l
,
X
2
,
X
3
,
x
4
,
X
5
,
X
6
-0
1.10某糖果公司厂用原料 A、B、C加工成三种不同牌号的糖果甲乙丙，已知各 种糖
果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单 位加工费
用及售价如表所示：
原料 甲 乙 丙
原料
成本（元/ 千
每月 限制用
量 （千克）
克）
I 2
A >60% >15% 2000
B 11.5 2500
C <20% <60% <50%
1 1200
加工费
0.5 0.4 0.3
售价
3.4 2.85 2.25
问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模 型。
解
：
解：设
X
i
，
X
2
，
X
3
是甲糖果中的A，B，C成分，
X
4
，
x
，
X
6
是乙糖果的A，
B，C成分，
X
7
，
X
8
，
X
9
是丙糖果的A，B，C成分。
线性规划模型：
Max z=0.9
X
i
+1.4
X
2
+I.9
X
3
+0.45
x
4
+0.95
x
+1.45 冷-0.05%
+0.45
X
+0.95%
79
s.t. -0.4
x
1
+0.6
x
2
+0.6
x
3
^0
-0.2 x-
i
-0.2
x
2
+0.8
x
3
_0
-0.85 沧+0.15
x
5
+0.15
x
e
_0
-O.6
x
4
-O.6
x
5
+0.4
X
6
_0
-0.7X
7
-0.5
x
+0.5X
9
岂0
x
1
+
x
4
+
x
<2000
x
2
+
x
5
+
x
<2500
8
x
3
+
x
6
+ < 1200
x
)
X
i
,
X
2
,
X
3
,
X
4
,
X
5
,
X
6
,
x
7
x
8
x
g
,
,
78
-0
1.11某厂生产三种产品I、丨【、III。每种产品经过AB两道加工程序，该厂 有
两种设备能完成A工序，他们以A,A
2
表示；有三种设备完成B工序，分别为
，
B
2
，
B
3
;产品I可以在AB任何一种设备上加工，产品丨【可以在任何规格 的A
设备上加工，但完成B工序时，只能在
B
1
设备上加工；产品III只能在
A
，
B
2
上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化
设备
I
5
7
6
产品
II
III
A
A
2
Bi
B
2
B
3
10
9
设备有效台
满负荷时的
时
设备费用
300
6000
10000
4000
321
250
783
200
12
8
11
4
7
7000
4000
原料费
单价
解：
0.25
1.25
0.35
2.00
0.5
2.8
产品1,设
A
1
,
A
2
完成A工序的产品
X
1
，
X
2
件；B工序时，
B
1
,
B
2
，
B
3
完成
B工序的
X
3
,
X
4
,
X
5
件，产品丨【，设
A
I
,
A
2
完成A工序的产品
X
6
,
X
7
件；B工 序
时，B完成B的产品为
X
8
件；产品111,
1
A
完成A工序的
X
件，B完成B
292
工序的
X
9
件；
X
1
+
X
2
=
X
3
+
X
4
+
x
5
x
7
X
6
+ =
7
X
8
8
建立数学模型：
Max z=(1.25-0.25)*(人 +
x
)+(2-0.35)*(沧 +
X
)+(2.8-0.5)
X
-(5 洛+10
79
X
e
)300/6000-(7
x
2
+9
X
+12
X
)321/10000-(6
x
3
+8 沧
)
250/4000-(4
x
4
+11
79
X
9
)783/7000-7
X
5
*200/4000
s.t
5
x
1
+10
x
6
三6000
7
X
2
+9
X
+12
X
9
乞 10000
7
6
X
3
+8
X
<4000
8
4
X
4
+11
X
< 7000
9
7
x
5
<4000
X
1
+
X
2
=
X
3
+
X
4
+
x
5
x
7
x
8
X
6
+ =
78
X
7
X X
9 “
人兀皿凶必风，,,
-0
T
最优解为 X= （1200，230，0，859，571，0，500，500，324
）
最优值
1147.
试题：
1. （2005年华南理工大学）设某种动物每天至少需要 700克蛋白质、30克矿物
质、100毫
克维生素。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价 如下
表所示：
试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模
表1—1
矿物质（克）
1
饲料
1
蛋白质（克）
3
维生素（毫克）
0.5
价格（元/公
斤）
0.2
0.5
2 2 1
3
1 0.2 0.2
4
6 2 2
5 0.5
18 0.8
解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可
0.7
0.4
0.3
0.8
解题过程：
min z = 0.2x
「
0.7x
2
0.4x
3
0.3x 0.8x
5
3% + 2x
2
+ x
3
+6x
4
+ 18x
5
K 700
x, +0.5x
2
+0.2x
3
+2x
4
+0.5卷 X 30 s.t彳
0.5x
,
+x
2
+0.2x
3
+2x
4
+0.8x
5
兰 100
X
,
,X
2
,X
3
,x
4
,X
5
X0
第二章（67页）
2.1用改进单纯形法求解以下线性规划问题。
（1） Max z= 6
x
1
-2
x
2
+3
x
3
2
x
1
-
x
2
+3
x
3
二2
为+4
x
3
乞4
人，
X
2
，
X
3
— 0
（2） min z=2
x
1
+
x
2
3
x
1
+
x
2
=3
4
X
J
+3
X
2
_6
x-
i
+2
x
2
-3
x-
i
,
x
2
-0
解：
（1）
先化成标准型：
Max z=6
x
1
-2
x
2
+3
x
3
+0
x
4
+0
x
5
s.t. 2
x
1
-
x
2
+2
x
3
+
x
4
=2
x-
i
+4
x
3
+
x
5
=4
X
l
,
X
2
,
X
3
,
X
4
,
X
5 _0
令
B
o
= (
P
4
,
P
5
)=
■
N
o
=(
P
，
P
2
，
P
3
)
=
2
-1
0
1
0
0
= (
X
4
,
X
5
)
,
C
B
=(O,O)
、
X
B
°
T
o
h
2
、
4
，
b0
，
N
=(
X
!
，
X
2
，
X
3
)
X
0
T
J
C
N
°
=
(6,-2,3)
，
B
0
=
=l4 丿
非基变量的检验数
口 _
C
N
°
'-N
。-
-
C
B
0
耳二
N
0
=
C
N
=
0
=(6,-2,3)
因为
X
i
的检验数等于6,是最大值，所以，
X
i
为换入变量,
B
A
0
b
°
=
I
0
4
」
—1
‘2
；
B
0
P
i
=
、
由二规则
得:
X
4
为换出变量
'2
0
,
X
B
-= (
X
I
,
X
5
)
T
,
C
B
, =(6,0).
B
l
=(
P
4
,
P
5
)
=
1
」
N
=(
X
4
，
X
2
，
X
3
)
N
I
=(R,
P
2
,
P
3
)
,
X
i
T
C
N
I
=
(0
,
, ,
B
i
」
-23)
0.5 0
-0.5 b
,bi =
非基变量的检验数
叫=(
-
3，
1
，-3)
因为
X
2
的检验数为
1,是正的最大数。所以
X
2
为换入变量;
B
0
P
2
=
A
-0.5
0.5
由二规则得：
=6
所以
X
5
是换出变量
B
2
=(
R
,
P
2
)
=
N
2
=(
F
4
,
P
5
,
P
3
),
-1
0
X
,
X
B
2
=
(
x
1
x
2
)
,
,
C
B
=
(6,-2)
.
2
N
2
= (
X
4
,
x
,
X
3
)
T
1
0 1
-
1
2
C
N
2
=(0
,
0, 3)，
B
2-
,
b
2
=
6
2
I
」
」
非基变量的检验数
；邛= (-2, -2,-9)
非基变量的检验数均为负数，愿问题已达最优解。
最优解X=
广4、
0
即：X= (4,6,0
)
T
目标函数最优值 max z=12
（2）
解：
Min z=2
S.T.
3 捲 +
x
2
+
x
4
=3
4 捲+3
x
2
-
X
3
+
X
5
=6
x-
i
+2
x
2
+
x
6
=3
x
2
+0
x
3
+M
x
4
+M
x
5
+0
x
6
X
6
- 0
M是任意大的正数。
（非基变量检验数计算省略）
原问题最优解是X= （0.6，1.2，0）
目标函数最优值：z=12/5
2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见
表，试将空白处数字填上。
3 5 4
C
j
0 0 0
C
B
X
B
X
2
X
5
b
8/3
14/3
X
1
X
2
X
3
X
4
X
5
X
6
5 2/3
-4/3
1
0
0
5
1/3
-2/3
0
1
0
0 0
0
X
6
C
j
-
Z
j
20/3 5/3
-1/3
0
0
.
4
4
-2/3
-5/3
0
0
1
0
X
2
15/41
-6/41
-2/41
8/41
5/41
-12/41
-10/41
4/41
15/41
X
3
X
i
C
j
-
Z
j
解:
C
j
3
b
8/3
14/3
20/3
5 4
0
X
4
0
X
5
0
X
6
C
B
X
B
X
2
X
5
X
6
C
j
-
Z
j
X
1
X
2
X
3
5
0
0
■
5
4
3
X
2
X
3
X
1
C
j
-
Z
j
80/41
50/41
44/41
0
0
1
0
1
0
0
0
0
1
0
0
15/41
-6/41
-2/41
-45/41
2.3写出下列线性规划问题的对偶问题。
(1) min z= 2
x
1
+2
x
2
+4
x
3
2 论+3
X
2
+5
x
3
_2
3
X
1
+
X
2
+7
X
3
辽3
X
-
I
+4
X
2
+6
X
3
< 5
X
i
必，
X
3 —0
(1)
解：对偶问题是：
Max w=2 y-
i
-3
y
2
-5
y
3
s.t.
2
y
i
-3
y
2
-
y
-2
3
y
i
-
y
2
-4
y^~
2 5%-7
y
2
-6
y
3
-4
y
i
,
y
2
,
y
3
-0
(2) max z=
X
-
I
+2
X
2
+3
X
3
+4
X
4
-
X
-
I
+
X
2
-
X
3
-3
X
4
=5
6 x
i
+7
X
2
+3
X
3
-5
X
4
_ 8
12
X
-
I
-9
X
2
-9
X
3
+9
X
^
20
X
i
,
X
2
一 0
；
X
3
-0
；
X
4
无约束
解：
对偶问题：
Min w=5 y-
i
+8
y
3
+20
y
4
S.t. -
y
i
+6
y
3
+i2
y
-i
y
i
+7
y
3
-9
y
-2 -
y
i
+3
y
3
-
44
9* 乞 3 -3
y
i
-5
y
3
+9 *=4
y
无约束，y
3
乞0;
m n
* -0
(3) min z二二二 qx
j
il j 4
n
' X
ij =4
j 4
m
i=1,…,m
' X
ij
=b
j
j=1,…,n
i 4
X
ij
-0
解：
m n
对偶冋题:max w=^
a
i
y
i
+送
b
j
y
m
岀
s.t.
y
i'
+y
；
卅兰q
''
''
yy
m j
,
无约束 i=1,2,….m; j=1,2,….n
⑷
n
Max z=二
c
j
x
j
jm
n
' a/ _ b , i=1,….,g _ m
j
吕
n
■-
j
a
ij
x
j
二
i=
m
1
1,m
1
- 2,..., m
b
i
,
三
X
j
-0,当 j=1 , ….,m乩
Xj
无约束，当 j=
n
「
1,..., n
解：
m
Min w八
b
j
y
i T
II
s.t.
m
' a* - C
j
i ±
j=1,2,3-
n1
、
a
j
y
；
- c
j
j=
n
+1, 口+2,….n
i
i 4
y
i
-0
n
y
m
i=1,2 ….
m
无约束，
)
=^+1, E+2….m
2.4判断下列说法是否正确，并说明为什么.
(1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。
(2) 如线性规划的对偶问题无可行解，则原问题也一定无可行解。
(3) 如果线性规划
问题的原问题和对偶问题都具有可行解， 则该线性规划
问题一定有有限最优解。
(1) 错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在；
(2) 错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解；
(3) 错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能 有
无界解；
2.5设线性规划问题1是：
n
Max
z
1
=二
C
j
为
j
旦
，i=1，2…，m
x
j
-0, j =, n
(
y
1
,..., y
m
)是其对偶冋题的最优解 又设线性规划问题2是
n
Max
Z
2 ='
C
j
X
j
jm
n
' a
j
X
j
虫
b
+
k
i
， i=1，2…，m
j
毘
x
j
-0, j = , n
其中
k
i
是给定的常数，求证：
m
max z
2
_ max
乙
+ ' k
i
y
i
i =1
解：
证明：把原问题用矩阵表示：
Max z-
i
= AX _b
X _0
b= (
D
,
b
2
...
b
m
)
T
设 可行解为
X
i
,对偶问题的最优解
Y
1
= (
y
i
,
y
…
y
m
)已知。
Max
z
2
=CX
s.t. AX mb+k
X -0
k= (
k
i
,
k
2
...
k
m
)
T
设可行解为
X
2
，对偶问题最优解是丫
2
,对偶问题是，
Min w=Y(b+k)
S.t. YA -C
Y -0
因为％是最优解，所以丫
(b+k)乞丫
1
(b+k)
2
X
是目标函数
Z
2
的可行解，A
X
2
乞b+k ； ^A%
岂丫
(b+k)岂
Y
b+Yk 原问题
222
和对偶问题的最优函数值相等，所以不等式成立，证毕。
2.6已知线性规划问题
Max z=
C
|
X-
|
c
2
x
2
c
3
x
3
X
j -
j
_ 1
，
...
，
0,5
用单纯形法求解，得到最终单纯形表如表所示，要求：
(1) 求
a
ii
，
a
i2
，
a
i3
，
a
2i
，
a
22
，
a
23
，
b
i
，
b
2
的值;
(2
)求
C
i
,C
2
,C
3
的值;
X
B
X
3
b
3/2
X
i
X
2
X
3
X
4
X
5
1 0 1
1/2 -1/2
x
C
j — Zj
2
1/2
-3
1
0
0
0
-1
2
-4
0
解：
(1) 初始单纯形表的增广矩阵是:
C
i
=
a
i3
_a
2i
1 0
0.5 1
1
a
3
1 0.5
1
0 b
i
0
1 b
2
-0.5 1.5
2 2
22
最终单纯形表的增广矩阵为
C
2
=
C
是C作初等变换得来的，将C作初等变换，使得C的第四列和第五列 的矩
2
阵成为C的单位矩阵。有：
2
an=9/2；印
2
=1;盹=4;
b
=9；
b
2
=5
由检验计算得：
C| =-3；
C
2
=
C
3
=0
2.7已知线性规划问题
Max z=2
x
1
+
x
2
+5
x
3
+6
x
4
s.t. 2
x
1
+
x
3
+
x
4
空 8
2
x
1
+2
x
2
+
x
3
+2
x^
- 12
X
j
-0, j=1,…4
a
21
=5/2；
a
22
=1；
a
23
=2；
对偶变量
y
1
,
y
2
，其对偶问题的最优解是
y
；
=4,
y
；
=1
，试应用对偶问题 的性
质，求原问题的最优解。
解：
对偶问题是：
Min w=8
y
1
+12
y
2
s.t. 2
y
1
+2
y
2
丄2
2
y
2
-1
y
i
+
y
2
-5 %+2
y
2
- 6
y
i
,
y
2
- o
互补松弛性可知，如
卞,
Y
是原问题和对偶问题的可行解，那么，
Y?X
s
=0
和
Y
S
X?=0，当且仅当
X
，
Y?
是最优解。
设X,Y是原问题和对偶问题的可行解，
Y
s
=（
y
3
，
y
，
y
，
y
）
4
有：
X
Y =0;且
Y
S
X=0
S
X
5
=
X
6
=0，原问题约束条件取等号，
X
3
=4；
X
4
=4
最优解 X=（0, 0, 4, 4
）
T
目标函数最优值为44。
2.8试用对偶单纯形法求解下列线性规划问题。
（1）min z=
x
1
+
x
2
2 为 +
x
2
_ 4
x
1
+7
x
2
_ 7
X
i
,
X
2
— 0
（2） min z=3 捲 +2
x
2
+
x
3
+4
x
4
2
x
1
+4
x
2
+5
x
3
+
x
4
- 0
3
x
1
-
x
2
+7
x
3
-2
x
4
-2
5
x
1
+2
x
2
+
x
3
+10
x
4
-15
为，X
2
, X
3
, &
解：
（1）
取w=-z，标准形式：
-0
Max w=- x-
i
-
x
2
+0
x
3
+0
x
4
s.t.
-2
X
-
-
X
2
+
X
3
=-4
-
X
-
-7
X
2
+
X
4
=-7
X
i
,
X
2
,
X
3
,
X
4
一 U
单纯形法求解(略)： 最优解：
X= (21/13, 10/13, U, U
)
T
目标函数最优值为31/13。
(2) 令：w=-z,转化为标准形式：
Max w=-3
X
1
-2
X
2
-
X
3
-4
X
4
+0
X
5
+0
X
6
+0
X
7
s.t.
-2
X
1
-4
X
2
-5
X
3
-
X
4
+
X
5
=0
-3 x-
i
+
x
2
-7
x
3
+2
x
4
+
x
6
=-2
-5 x-
i
-2
x
2
-
x
3
-6
x
4
+
x
7
=-15
X
1
，
X
2
，
X
3
，
X
4
，
X
5
，
X
6
，
X
7 .
单纯形法略 原问题最优解：
X=（3，0，0，0，6，7，0
）
T
目标函数最优值为9。
2.9现有线性规划问题
max z=- 5
x
1
+5
x
2
+13
x
3
-x-
i
+
x
2
+3
x
3
- 20
12 x-
i
+4
x
2
+10
x
3
- 90
X
1
，
X
2
，
X
3
-0
先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什
么变化？
（1
约束条件1的右端常数20变为30
(2) 约束条件2的右端常数90变为70
(3) 目标函数中
x
3
的系数变为8
(4)
x
i
的系数向量变为
1
J2丿
(5) 增加一个约束条件2
X
i
+3 « +5怡乞50
(6) 将约束条件2变为10^+5
x
2
+10
x
3
空100
解：
把原问题化成标准型的：
Max z=-5
x
1
+5
x
2
+13
X
3
+0
x
4
+0
x
s.t
-x-
i
+
x
2
+3
x
3
+
x
g
=20
12 x-
i
+4
x
2
+10
x
3
+
x
g
=90
%，
x
，
X
3
，
x
4
，
X
5
- 0
单纯形法解得：
最优解：
X= (0，20，0，0，10
)
T
目标函数最优值为100。
非基变量x-
i
的检验数等于0，原线性问题有无穷多最优解
(1) 约束条件二的右端常数变为30
有
：
^B
J
b
因此b =b「b
单纯形法解得：
最优解：
X= (0，0，9，3，0
)
T
目标函数最优值为117。
(2) 约束条件Q右端常数变为70
有 b=B‘
：
b
因此b =b 比
单纯形法解得，最优解：
X= (0，5，5，0，0
)
T
目标函数最优值为90。
(3)
X
3
的系数变成8,
X
3
是非基变量，检验数小于0,所以最优解不变
(4)
x
i
的系数向量变为
x
i
是非基变量，检验数等于-5,所以最优解不变。
(5) 解：加入约束条件
0
3
用对偶单纯形表计算得：
X= (0, 25/2, 5/2, 0, 15, 0
)
T
目标函数最优值为95。
(6) 改变约束条件，巳,巳,
P
5
没有变化, 线性规划问题的最优解不变。
2.10已知某工厂计划生产1,11」11三种产品，各产品在ABC设备上加工，数 据如
下表，
I II III
设备代号
每月设备 有效
台时
A
B
C
单位产品利润
/千兀
8
10
2
3
2
5
13
2
10
8
10
2.9
300
400
420
(1)如何充分发挥设备能力，使生产盈利最大?
(2) 如果为了增加产量，可借
用其他工厂的设备 B，每月可借用60台时，
租金为1.8万元，问借用是否合算？
(3) 若另有两种新产品IV,V ,其中IV为10台时，单位产品利润2.1千元； 新
产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利1.87 千元。
如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否划 算？
(4) 对产品工
艺重新进行设计，改进结构，改进后生产每件产品 I，需要
设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元， 问
这对原计划有何影响？
解：
(1)
设：产品三种产品的产量分别为，
X
1
,
X
2
,
X
3
，建立数学模型：
s.t.
Max z=3
x
1
+2
x
2
+2.9
X
3
8
x
4
+2
x
2
+10
x
3
乞300
10
x
1
+5
x
2
+8
x
3
- 400
2^+13
x
2
+10
x
3-
420
X
i
,
X
2
,
X
3
一0
把上述问题化为标准型，用单纯形法解得：
最优解：
X=（ 338/15, 116/5, 22/3，0，0，0
）
T
目标函数最优值为2029/15。
（2）
设备B的影子价格为4/15千元/台时，借用设备的租金为
所以，借用B设备不合算。
（3）
设备V,V生产的产量为
x
，
X
8
，系数向量分别为：
P
7
=（12,5,10）
丁
P
8
=（4,4,12）
丁
检验数二
7
=-0.06,所以生产 V不合算，
6=37/300,生产V合算。
单纯形法计算得：
最优解：
X=（ 107/4，31/2，0，0，0，0，55/4
）
T
目标函数最优值为10957/80。
（4） 改进后
，
检验数二
1
=253/300，大于零。
所以，改进技术可以带来更好的效益。
2.11分析下列参数规划中当t变化时最优解的变化情况
（1）Max
z
（
t
）
=（3-6t）捲+（2-20
X
2
+（5-5t）
X
3
（t_0）
s.t.
x-
i
+2
x
2
+
x
3
- 430
3
X
1
+2
X
3
- 460
0.3千兀每台时。
x-
i
+4
x
2
- 420
x
i
,
X
2
,
X
3
_ 0
(2) Max
z
(
t
)
=(7+2t)
x
1
+(12+t)
x
2
+(10-t)
x
3
(t 亠 0)
s.t.
x-
i
+
x
2
+
x
3
- 20
2
x
1
+2
x
2
+
x
3
- 30
X
i
,
x
,
X
3
一0
(3) Max
Z
(t)
=2
x
1
+
x
2
(0 ^t 乞25)
s.t.
X
1
- 10+2t
x-
i
+
x
2
- 25-t
x
2
- 10+2t
x-
i
,
x
2
-0
(4) Max
z
(t)
=21 x-
i
+12
x
2
+18
x
3
+15
x
4
(0 -1 - 59)
s.t.
6
x
1
+3
x
2
+6
x
3
+3 & - 30+t
6*3
x
2
+12
x
3
+6
x
4
- 78-t
9
x
1
+3
x
2
-6
x
3
+9
x
4
135-2t
人,
X
2
,
X
3
,
x
4
-0
解：
(1)化成标准形式：
Max
Z
(t)
=(3-6t)
X
1
+(2-2t)
x
?
+(5-5t)
X
3
+0
X
4
+0
X
5
+0
X
s
(t - 0)
s.t.
x-
i
+2
x
2
+
x
3
+
X
4
=430
x-
i
+4
x
2
- 420
3
x
1
+2
x
3
+
x
5
=460
x-
i
+2
x
2
+
x
3
+
X
4
=430
x-
i
+4
x
2
+
x
6
=420
X
i
,
X
2
,
X
3
,
X
4
,
X
5
,
X
6
_0
令t=0,用单纯形表计算，
3-6t
C
j
2-2t 5-5t
0
X
4
0
X
5
0
X
6
9i
C
B
X
B
X
2
X
3
X
6
B
X
1
X
2
X
3
2-2t
5-5t
0
-z
100
230
20
-1/4
3/2
2
1
0
0
0
1
0
0.5 -1/4
1/2
[1]
0
0
1
-
460
20
0
-2
t-1 2t-2
1350t -
t-4
0 0 0
1350
t增大，t大于1,首先出现二
4
，二
5
大于0,所以当0乞2 1时有最优解
X=（0，100，230，0，0，20
）
T
目标函数最优值为1350（t-1）
t=1是第一临界点
t大于1时，
X
6
是换出变量。
t 大于 1,最优解是：X=（0，0， 0, 430，460, 420
）
T
（0乞2 1）。
目标函数最优值为
Max
z
（
t
）
=0, （ t 大于 1）
（2）
化成标准型，然后令t=0,单纯形法解得：
t开始增大时，当t大于8/3时，首先出现二
大于0,所以0^2 8/3，得最 优解。
4
目标函数最优值 Max
z
（
t
）
=220,（ 0乞2 8/3）
所以，t=8/3为第一临界点。
当8/3 x 3 为换出变量，使用单纯形法 继续迭 4 代，t继续增大，当t>5,首先J大于0, 8/3 目标函数最优值为180+15t 所以，t=5为第二临界点。 , (8/3 X= (0, 15, 0, 5 ) T 当t>5时，捲是换入变量， x 为换出变量，单纯性法计算， 当t继续增大，所有检验数都非正，所以当 t>5,最优解： X=( 15，0，0，5 ) T 目标函数最优值为105+30t， t> 0 (3)化成标准型，令t=0,用单纯形法计算得： 当t开始增大，t大于5时，首先出现 b 2 小于0,当0岂M5，最优解为： X= (10+2t, 0, 10+2t, 5-t, 0 ) T 目标函数最优值为6t+30 所以t=5是第一临界点。 , (0空仁5)。 当t大于5时， X 4 是换出变量， X 5 是换入变量。用对偶单纯形法计算， 当t大于5时，最优解为： X= (10+2t, 15+t, 0, 0, t-5 ) T 目标函数最优值为35+5t。 (4) 解: 先化为标准型，令t=0,用单纯形法计算，得： 当t开始增大，当t大于6时，首先出现 b 2 小于0,当0乞仁6,有最优解： X= (0, 0, 0, 10+t/3, 0, 18-3t, 45-5t ) T 目标函数最优值为150+5t (0^2 6)。 当t大于6时，首先出现 b 2 小于0, X 是换出变量， X 2 是换入变量，使用单 纯形法计算得：t继续增大，当t大于11时， b 3 首先小于零， X 是换出变量， X 3 为换入 变量，对偶单纯形法迭代得： 当t< 59,有最优解： X= (0, t/3-2, t/8-11/8, 59/4-t/4, 0, 0, 0 ) T 目标函数最优值为 5t/2+345/2 , (11 试题： 1. (2006年西北工业大学)已知线性规划： max z = 3x ! 2x 2 —为 +2x 2 兰 4 3 洛 +2x 2 兰 12 st { | X 1 - X 2 — 3 X i , X 2 _ o （1） 用单纯形法求解该线性规划问题的最优解和最优值； （2） 写出线性规划的对偶问题； （3） 求解对偶问题的最优解和最优值。 解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。 解题过程：X二 18 3 32 IL5 5 5 0 0 maxz =12，有无穷多解。 对偶问题为： min w = 4y 1 12y 2 3y 3 -力 3y 2 y 3 一 3 st 2y 1 2y 2 -y 3 -2 .%”2”3- 0 Y - 0 1 0. * F w = z =12 T * * 2. （2005年东南大学）写出如下线性规划问题的对偶问题: max z = x 「 2x 2 x 3 st 花一 X 2 于 X 3 = 1 2 x 1 - x 2 x 3 _ 2 人一 0, X 2 岂 0 无限制 并利用弱对偶性说明 z 的最大值不大于1 解题过程：原问题的对偶问题为： min w = 2y 1 y 2 2y 3 Y 1 + Y 2 + 2y^1 4」 l-y ％ ^y - y 2 5 ^ya =1 兰 2 s.t 5 % _0,y 3 gy 2 由于（0，1, 0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的 可行解 X 都有 C X— Yb 任一 而 Yb = b 1 O] 1 =1 ，所以 z 的最大值不大于1。 第三章（86页） 3.1判断表中给出的调运方案能否作为用表上作业法求解时的最初解？为 什么？ 表3 — 1 1 2 3 4 销地 产量 1 2 3 销量 0 15 15 10 15 25 5 5 5 表3—2 1 2 15 3 15 4 10 5 产量 销 地 产 地、 1 150 2 3 4 90 5 销量 240 解： 250 200 300 250 400 500 50 300 300 100 210 410 550 80 330 20 70 表3— 1 中,有5个数字格，作为初始解，应该有m+n-1=3+4-1=6个数字格, 所以表 3-1的调运方案不能作为用表上作业法求解时的初始解。 表3-2中，有10个数字格，而作为初始解，应该有 m+n-1=9个数字格，所 以表3-2 的调运方案不能作为表上作业法的初始解。 3.2 表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表， 伏格尔法直接给出近似最优解 表3-3 销地 3 产量 1 2 产地 5 2 3 9 1 4 6 10 8 1 7 11 12 14 4 试用 1 2 3 销量 表3-4 1 销 地、 产地 '、、 1 2 3 4 销量 2 3 4 5 产量 10 5 15 20 20 2 「 20 5 15 20 3 15 14 13 30 15 2 7 M 10 9 4 15 8 25 25 30 20 30 解： (1)在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额, 填入该表的最 右列和最下列。得到： 1 2 3 行差额 、、销地 产地 4 1 8 2 2 1 1 3 3 6 [7 3 列差额 3 1 6 从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最小元素， 上表 中，第三列是最大差额列，此列中最小元素为 1,由此可以确定产地2的产 品应先供 应给销售地3,得到下表： 1 4 1 [ 5 销地 1 2 3 产量 产地 1 ] 2 3 n 销量 9 10 同时将运价表第三列数字划去，得 、^销地 1 2 11 12 14 4 11 产量 产地 1 12 2 4 14 3 6 4 | 9 10 对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入 该表的最右 列重复上面的步骤，直到求出初始解，最终结果是： 和最下列， 1 2 3 销量 5 代、销地 产地 1 [ 2 3 销量 1 2 3 产量 2 3 4 9 10 11 12 14 4 10 11 （2） 3-4分别计算出各行和各列的次最小运费和最小运费的差额，填入该 表的最右 列和最下列。从行差额或者列差额中找出最大的， 选择它所在的行或者 列中的最小 元素。（方法同3-3相同） 最终得出原问题的初始解: 2 3 4 5 销地 1 产量 产地 1 2 3 4 销量 20 25 30 20 30 30 25 20 20 10 3.3用表上作业法求给出运输问题的最优解（M是任意大正数） (1) 甲 乙 丙 丁 、销地 产地 产量 1 2 3 销量 解： 3 2 4 3 7 4 3 3 6 3 8 2 2 I' 2 5 2 3 （1） CD计算出各行和各列的次最小运费和最小运费的差额， 填入该表的最 右列和最下列。 ②从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最 小 元素，丙列中的最小元素为3,由此可以确定产地2的产品应先供应丙的需要， 而产地 2的产量等于丙地的销量，故在（2,丙）处填入0,同时将运价表中的 丙列和第二行的数字划去，得到: 、、销地 甲 乙 丙 丁 产地 产量 1 3 7 4 5 2 3 销量 2 O 对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额, 4 3 3 3 2 3 填入该标的最右列和最下行，重复步骤 O 1②，直到求出初始解为止。得到下表: 销地 产地 1 2 3 销量 甲 乙 丙 丁 产量 x 3 2 A 0 5 2 3 0 3 3 3 2 2 u i (i=1 , 使用位势法进行检验： &上表中，数字格处填入单位运价并增加一行一列，在列中填入 ii 2, 3)，在行中填入 V j (j=1，2, 3, 4)，先令 U + V = q (i，j^B，B 为基，下 同)来确定 U 和 V ，得到下表: 销地 甲 乙 ii 丙 丁 U i 产地 1 2 3 v i '、、、 3 4 3 0 -2 1 4 3 3 2 i 5 4 ②由r= Cj - ( U + V ) (i，j为非基，下同)计算所有空格的检验数，并在 每个格的右上角 i 填入单位运价，得到下表 销地 甲 产地 1 2 3 乙 丙 丁 U i 、. 0 1 0 3 5 2 4 0 7 1 4 4 3 2 0 6 3 4 0 0 2 5 0 0 -2 8 1 V i 3 2 5 4 由上表可以看出，所有的非基变量检验数》 0, 此 尤问题达到最优解。 又因为二 34 =0，此问题有无穷多最优解 总运费 min z=3*3+3*3+2*3+2*4=32 (2) 、、销地 产地 1 2 3 销量 甲 乙 丙 丁 产量 '、 10 16 5 5 6 10 4 2 7 5 10 4 M2 9 [10 6 4 9 4 解：(2 )(5 计算出各行和各列的次最小运费和最小运费的差额，填入该表 的最 右列和最下列。 ②从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最 小 元素，甲列是最大差额列，甲列的最小元素是 5,所以产地3的产品先供应甲 的需 求，同时将运价表中产地3所在行的数字划去。 5 对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入该标的最右列和最下行，重复步骤 O 1②，直到求出初始解为止。得到下表: 、、销地 甲 乙 丙 丁 产量 产地 1 2 3 销量 1 2 1 3 4 6 4 5 2 使用位势法进行检验： 9 4 4 6 &上表中，数字格处填入单位运价，并增加一行一列，在列中填入 U i (i=1， 2, 3)，在行中填入 V j (j=1，2, 3, 4)，先令 5=0，由 U + V = C j (i，产 B, B 为基， ii 下同)来确定 U 和 V . ii 5 由 Fj = Cj - ( U + V ) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入 ii 单位运价，得到下表 肖地 产地 1 2 3 、、 甲 乙 丙 丁 U i 0 8 0 10 16 5 3 6 6 10 4 8 7 7 1 5 0 10 0 4 11 12 0 9 -2 -5 6 10 V i 10 由上表可以看出，所有的非基变量检验数》 0,此问题达到最优解 此问题有唯一最优解。 总运费min z=118 (3) 甲 乙 丙 丁 戊 产量 销地 产地、 1 2 3 4 销量 10 2 1 8 4 20 10 20 6 4 5 8 7 3 6 9 30 10 7 2 10 6 4 5 4 5 ； 6 2 解：（3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售 地 己，令单位运价为0。销量为2。这样就达到了产销平衡。 用伏格尔法求初始解： CD 计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 和 最下列。 C 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 素， 产地1所在的行是最大差额行，最小元素 0,说以一产地的产品应该优先供 应己的需 要，同时划掉己列的数字。 ③对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入该标的 最右列和最下行，重复步骤 O 1②，直到求出初始解为止。得到下表: 甲 乙 丙 丁 戊 己 产量 销地 产地、、 1 3 2 5 4 2 2 6 3 2 2 4 4 3 2 9 销量 4 4 6 2 4 2 使用位势法进行检验： C 上表中，数字格处填入单位运价，并增加一行一列，在列中填入 u i （i=1， 2, 3, 4),在行中填入 V j (j=1 , 2, 3, 4, 5, 6),先令 U i =0，由 U + V = C j (i, j ii B, B为基，下同)来确定 U 和 V . ii O 由F= Cj - ( U + V ) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入 ii 单位运价。 由上表可以看出，所有的非基变量检验数》 0,此问题达到最优解。 又因为二 14 =0，此问题有无穷多最优解。 总运费min z=90 (4) 甲 乙 、、销地 产地 1 2 3 4 5 丙 29 丁 13 14 3 18 30 60 戊 产量 10 13 18 M 22 16 100 120 M 140 19 34 21 11 23 36 100 0 9 24 100 120 6 11 28 80 60 销量 80 解：(4)此问题是一个产销不平衡的问题，产大于销。增加一个假象销售 地己， 令单位运价为0。销量为40。这样就达到了产销平衡。 用伏格尔法求初始解： O 计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 和最 下行。 O 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 素， 同时划掉所在列或行的元素。 ③对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入 该标的最右列和最下行，重复步骤 O 1②，直到求出初始解为止。 并用位势法进行检验: 乙 己 甲 丙 丁 戊 销地 产 U i 地、 29 13 1 10 18 22 0 0 2 8 0 6 12 13 M 14 2 21 16 0 0 3 M-16 0 1 0 12 3 3 M -10 6 11 0 0 0 4 4 5 2 v i 0 9 0 24 0 16 11 28 0 23 7 36 3 21 0 10 5 13 18 30 M-6 19 8 34 6 16 22 17 0 -12 0 -5 12 10 由上表可以看出，所有的非基变量检验数》 0,此问题达到最优解 又因为二 31 =0，此问题有无穷多最优解。 总运费min z=5520 3.4 已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示 表1 产量 销 地 B 1 B 2 B 3 B 4 产地 A A A 3 5 10 15 25 0 10 15 5 5 15 B 1 10 B 2 1 7 14 C22 销量 表2 产地 5 销地 15 B 3 20 9 16 10 B 4 11 20 18 A A 12 2 22 A （1）A 到B的单位运价在什么范围变化时，上述最优方案不变? （2） A到B的单位运价变为何值时，有无穷多最优方案。除表 24 1中方案 外，至少写出其他两个。 解： （1） CD在对应表的数字格处（ C 22 未知）填入单位运价，并增加一行，在列中 填入 U i （i=1，2，3），在行中填入 V j （j=1，2，3，4），先令 U i =0，由 U + V = C ij ii (i, j B)来确定 U 和 V . ii O 由F= Cj - ( U + V ) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入 ii 单位运价( c 22 未知)。 最优调运方案不变，则所有非基变量的检验数都是非负。所以： C 22 -3 — 0 c 22 +10-0 10- C 22 - 0 24- C 22 - 0 18- Q 2 一 0 解得 ： 3 - C 22 - 10 单位运价在此区间变化时，最优调运方案不变。 (2 )0 在对应表的数字格处( C 22 未知)填入单位运价，并增加一行，在 列中填入 U i (i=1 , 2, 3)，在行中填入 V j (j=1，2, 3, 4)，先令 5 =0，由 U + V = q ii (i，j ， B)来确定 U 和 V . ii O 由F= Cj - ( U + V ) (i， j・ N )计算所有空格的检验数，并在每个格的右 上角填 ii 入单位运价( C 22 未知)。 有无穷多最优方案，则至少有一个非基变量的检验数为 0. 取5-17=0,所以单价变为17时，该问题 有无穷多最优调运方案。 另外的两种调运方案： 销地 产地 B 1 B 2 B 3 B 4 产量 A 15 0 0 15 10 15 25 A 2 A 3 5 5 5 10 销量 15 15 、、销地 产地 B 1 B 2 B a B 4 产量 A A 2 A 3 15 15 25 5 0 5 5 0 15 10 销量 15 15 10 3.5 某百货公司去外地采购 ABCD四种规格的服装，数量分别为： A,1500套; B, 2000套；C，3000套；D，3500套；有三个城市可以供应上述服装，分别为: I，2500套，II，2500套；III，5000套。已知下表，求预期盈利最大的采购方 案。 A B C D I 10 5 6 7 II 8 2 7 6 9 3 4 8 III 解： 因为利润表中的最大利润是10，所以令M=10，用M减去利润表上的数字, 此问题变 成一个运输问题，见下表： A B D 销地 C 产量 产地 、、 I II III 销量 0 5 2 8 1 7 1500 2000 使用伏格尔法计算初始解： 4 3 6 3000 A 4 2500 2500 5000 3500 CD 计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 和最下行。 C 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 素， 同时划掉所在列或行的元素。 C 对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入 该标的最右列和最下行，重复步骤 O 1②，直到求出初始解为止。 销地 产地 A B C D 产量 I II III 销量 1500 500 500 2500 3000 1500 使用位势法检验： 1500 2000 [3500 3500 2500 2500 5000 ①数字格处填入单位运价，并增加一行一列，在列中填入 ii u i （i=1 , 2, 3）, i 在行中填入 V j （j=1，2，3, 4），先令 u i =0，由 U + V = q （i，产B,）来确定 U 和 V . i ②由F= Cj -（ U + V ） （i，j ・ N ）计算所有空格的检验数，并在每个格的右 ii 上角填入单位运价。 如果没有得到最优解，用逼回路法进行改进 盈利最大方案： A B C D 、、销地 产 地 I 、、 II 3 III 0 V i U i 0 2 5 0 8 4 0 7 1 5 1 4 0 4 2 3 4 6 1 3 4 2 0 -1 1 1 0 此时，总运费为28000元;最大盈利为72000元。 3.6甲乙丙三个城市每年需要煤炭分别为： 320万吨、250万吨、350万吨, 由A、B两处煤矿供应。煤炭供应量分别为：A,400万吨；B,450万吨；运价如下 表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少 0~30万吨，乙 城市需要完全供应，丙城市供应不少于270万吨。试求将供应量分配完又使总运 费最 低的调运方案。 甲 乙 丙 A B 15 21 18 25 22 16 解: 此问题的供应量小于需求量，假设供应地 C,产量为70万吨。 用伏格尔法求解 得： 甲 甲‘ 乙 丙 丙‘ 供应 、销地 产 地、 A 150 250 400 B 140 30 270 10 450 C 70 70 需求 290 30 250 270 80 使用位势法检验: CD 数字格处填入单位运价，并增加一行一列，在列中填入 U i (i=1 , 2, 3), 在行中填入 V j (j=1 , 2, 3, 4),先令 U i =0,由 U + V = q (i,产B,)来确定 U 和 V . iii i C 由 Gj = Cj - ( U + V ) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入 ii 单位运价。 如果没有得到最优解，用闭回路法进行改进。 最优解时，最小运费是14650万元。 3.7某造船厂根据合同要从当年起连续三年末各提供三条规格型号相同的 大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下 表， 正常生产时间内 加班生产时间内 正常生产时的 每艘 年度 可完成的客货轮 可完成的客货轮 成本/万元 数 数 1 2 2 4 3 2 500 600 3 1 3 550 已知加班生产时，每艘客货轮的成本比正常生产高出 70万元，又知道造出 来的可货 轮如当年不交货，每艘积压一年造成积压损失 40万元，在签合同时， 该厂已经存储了 2艘客货轮，而该厂希望在第三年木完成合同后还能存储一艘备 用，问该厂如何安排每年的生产量，能够在满足上述要求的情况下，总的生产费 用加 积压损失最少？ 解： 设 A l , A , A 是三年的需求订货， B i , B 2 , B 3 是三年的正常生产能力；区, B 2 , B 3 是三年的加班能力，S是事先积压产生的供货能力。第三年的需求量是 4 艘。此问题产销不平衡，增加设想销地 A 4 ，运价0,销量7. 使用伏格尔法求初始解： 并用位势法检验： 此问题有无穷多最优解， 总运费 min z=4730万元 销地 产 地' Bi B ； 供应量 A i A 2 A 3 A 500 540 0 0 600 60 60 60 -10 B 2 B 2 0 0 B 3 550 620 B 3 0 60 -460 40 500 540 试题：（2001年上海大学 ） S 需求量 560 -60 某产品由产地A i 发往销地B j 的每吨运费如下表: 元/吨 B i B 2 A i 50 40 150 A 2 45 30 200 A 3 20 10 250 需求量 150 220 为满足各销地需求，应如何确定运输方案使总费用最小? （1） 建立此运输问题的数学模型。 （2） 将此问题化为产销平衡的运输问题，并求出一个初始基本可行解。 B 3 60 65 50 180 供应量（吨） 解：（1）设 X j 某产品为从A i 发往销地B j 的吨数，贝吐匕运输问题的数学模型为: max z =50x“ 40x 12 60x 13 - 245x 21 30x 22 65x 23 20x 31 10x 32 - 50x 33 X 1 1 ' x 12 ' x 13 = 150 ' x 23 x 31 x x ' 22 21 二 ' x 32 ' x 33 200 -250 =150 = 220 -180 st ^x 11 X 12 x 13 ' x 21 'X 22 ' X 23 X 31 ' X 32 ' X 33 -0 , i , j =1 ,2,3 、 X j (2)增加一个虚拟销地B 4 ,其需求量为50吨，各产地到虚拟销地B 4 的每吨运 费分 别为0,贝冋将此问题化为如下产销平衡的运输问题： 元/吨 A 1 A 2 B 1 50 45 B 2 40 30 B 3 60 65 r 0 B 4 0 0 供应量 150 200 250 A 3 20 10 50 需求量 150 220 180 由最小元素法可得到如下的一个初始基本可行解: 50 元/吨 B 1 B 2 A 1 A 2 A 3 需求量 120 30 150 B 3 100 80 B 4 50 供应量 150 200 250 220 220 180 50 第四章(98页) 4.1若用以下表达式作为目标规划的目标函数，试述其逻辑是否正确? (1) max= djd 1 (2) max z= df - d 1 (3) min z= d + d (4) + min z= d - d 解: (1)不正确 (2) 正确 .—.+ 1 1 ， - ， (3) 正确 (4) 正确 4.2 试用图解法找出以下目标函数的满意解; (1) min z= p (小厂+小广)+ P 2 (2d^+d^) s.t. X 1 -10 X 2 + d i-- d i =50 3 x 1 +5 x 2 + df- d 2 =20 8 x 1 +6 X 2 + d 3 ： d 3 =100 X i , X 2 , dj d 1 , d 2 , d ?— , d 3_ , d 3 一0 (2) min z= R ( d^+ d/ ) + P 2 d/+ P 3 d 2 _ + P 4 ( d 3 _ +1.5 d 4^ s.t. X - I + x 2 + d 1 ： d 1 =40 X - I + x 2 + d 2 - d 2 "=100 X + d 3 - d 3 =30 _ X 2 + d 4 - d 4 =15 X i , X 2 , d i_ , d i , d 2 , d 2_ , d 3_ , d 3 , d 「, d 4 _0 (3) min z= R ( d 「+ d i ) + R, df + P 3 d 3 s.t. X - I + X 2 + d 1 _ - d 1 =10 3 X 1 +4 X 2 + d 2- d 2 =50 8 X 1 +10 X 2 + dr - d 3 =300 X i , X 2 , d 「， d i , d 2 , d 2_ , d 3_ , d 3 —0 解 (1) 满意解是：(50, 0) (2) 满意解是：(25, 15) (3) 满意解是：(10, 0) 4.3使用单纯形法求解下列目标规划问题。 (1) min z= R d^ + F 2 d^ + P 3 (5 d^ +3 df ) + P 4 d/ s.t. X - I + x 2 + d 1 ： d 1 =80 X 1 + x 2 + d 2 _ - d 2 =90 X i +小 3 -小 3 =70 X 2 + dr - d 4 =45 X i , X 2 , d i_ , d i , d 2 , d ?— , d 3_ , d 3 ,d<^, d ； _0 (2) min z= P d^ + P d2~ + P 2 dr s.t. X i +2 x ? + d i - d i =10 10论 +12 x 2 + d 2 - - d 2 =62.4 x i +2 x 2 _8 X i , X 2 , de d i , d 2 , d 2 一 -0 (3) min z= R ( dr + d^ ) + F 2 d 3 _ s.t. X i + X 2 + d i - d i =i 2 X 1 +2 X 2 + d 2 二 d 2 =4 6 x i -4 x 2 + d 3 二 d 3 =50 X i , X 2 , d 「， d i , d 2 , d^ , dr, d； _0 解： (1)把原问题转化为： Min z= R d 2 + R d 2 _ + P 2 d 「 S.T. X +2 x 2 + d 1 _ - d 1 =10 10 x i +12 x 2 + d2" - d 2 =62.4 2 x i + x 2 + x 3 =8 X i , X 2 , X 3 , d i" , d i , d 2 , df- 0 x 3 是松弛变量 单纯形法计算得： C j 0 b X i 0 X 2 0 X 3 R 2 0 dj R dr R 2 q C B X B dr d 丈 F 2 P d i_ d 厂 X 3 10 62.4 1 10 2 -10 【2】 0 0 1 0 0 代 1 0 0 0 0 -1 0 0 0 1 0 1 0 0 0 0 -1 0 5 5.2 12 1 -12 0 P F 2 8 8 2 -1 -2 0 … 迭 原问题最优解 x 1 =0, X 2 =5.2 , 非基变量的的检验数是0,所以有多重解； 继续迭代得到： X 1 =0.6, X 2 =4.7也是满意解 （2） 使用单纯形法计算： X 1 =70, X 2 =20 （3）满意解是 X - I =1, X 2 =0 4.4有以下目标规划问题 min z= Rd i~ + F 2 + P 3 （ 5 d^ +3 df ） + P 3 （ 5 d ； +3 d 2 ） s.t. X - I + x 2 + d 1 _ - d 1 =80 X + d 2 _ - d 2 =70 X 2 + d 3 - d 3 =45 d i + d 4 - d 4 =10 _ X i , X 2 , d i - d i , d 2 , d 2" d 3 - d 3 , d 4~ , d 4— 0 （1） 用单纯形法求解 （2） 若目标函数变成 min z= p d 「+ P 3 d 4 + P 2 （5d=+3 df）+ P 2 （5 d 3 +3 d 2 ）, 问原问题的解有什么变化？ （3） 若第一个目标约束的右端改为120,原满意解有何变化？ 解： (1) 单纯形法计算得到: 人=70, X 2 =45是满意解 b列出现负数， d i ■行的系数乘以-1,重新迭代，人=75, X 2 =45是满意解； (2)实际上是对优先因子 0 P 2 , P 3 进行调换，最优解不变 (3) .ib—Brb 二 1 1 0 4.5某工厂生产两种产品，产品I每件获利10元，产品II每件获利8元。每生产 1件 产品I需要3小时，生产产品II需要2.5小时，每周的有效时间120小时， 若加班生 产，产品I每件利润少1.5元，每件产品II利润少1元，决策者希望在 允许的时间和 加班时间获取最大利润， 试建立该问题的目标规划模型，并求解？ 解：条件不足，无法建立模型。 4.6某商标的酒是用三种等级的酒兑制而成。已知道三种酒的供应量和单位成本 如下表； 设该种牌号酒有三种商标(红黄蓝)，各种商标的酒对原料酒的混合比及售价见 下表， 决策者规定：首先必须严格按规定比例兑制各种商标的酒， 其次获利最大； 再次，红商标的酒每天至少生产 2000kg，列出数学模型。 解： 设 X i1 ， X 2 ， X i3 (i=1，2, 3)表示第i种等级的兑制红黄蓝三种商标的酒的数量， 数学模型： Max z= R ( d 1~ + d 2 + d r+ d?+ d 5+ d^)+ P 2 + + P 3 d ； s.t. X 31 -0.1 ( X 11 + X 21 + X 31 ) + 1 - 1 =0 dd x 11 -0.5( x 11 + x 21 + x 31 ) + d/ - d 2 =0 X 32 -0.7 ( X 12 + X 22 + X 32 ) + d 3 - d 3 =0 x 12 -0.2 ( x 12 + x 22 + x 32 ) + d/ - d 4 =0 X 33 -0.5( X 13 + X 23 + X 33 )+ dT - d 5 =0 X 13 -0.1 ( X 13 + X 23 + X 33 )+ d 6 ： d 6 =0 x 11 + x 21 + x 31 + d 7 ^ d 7 =2000 X j -0 (i=1,2,3;j=1,2,3) 其中, z=5.5( X 〔 i + X ?i + X 31 )+5( X |2 + X 22 + X 32 )+4.8 X l3 + X 23 + X 33 ) -6( X n + X 12 + X 13 )-4.5( X 21 + X 22 + X 23 ) -3( X 31 + X 32 + X 33 )+ dL 试题： 1.某生产基地每天需从 A、B两仓库中提取原材料用于生产，需提取的原材料 有：原 材料甲不少于240件，原材料乙不少于80公斤，原材料丙不少于120 吨。已知： 从A仓库每部货车能运回生产基地甲4件，乙2公斤，丙6吨， 运费200元/ 部；从B仓库每部货车每天能运回生产基地甲 7件，乙2公斤， 丙2吨，运费 160元/部，问：为满足生产需要，生产基地每天应发往 A、B 两仓库多少部货车，并使总运费最少？ 解题过程：根据题意列出下表: 单位 运量 原 材 甲 （件） 乙 （公斤） 丙 （吨） 运费 （元 / 部） A B 需求量 4 7 240 2 2 80 6 2 200 160 120 设每天发往A，B两仓库的货车数分别为N ， X 2 部，则有 min z = 200% 160 X 2 「4% 十7屜 A 240 2% +2% 兰80 st < . 6 X 1 2 X 2 -120 [X 1 , X 2 >且 为整数 ① ② ③ ⑤ ④ 先不考虑整数约束，用图解法（如上图），得最优解为x； =10,x； =30，恰 好是整数解。故x* =（10,30）就是原问题的最优整数解，且 z * =6800 。 故生产基地每天发往A仓库10部车，发往B仓库30部车，可使总运费最 少为 6800元。 第五章答案 5.1对下列整数规划问题，问：用先解相应的线性规划，然后凑整的办法，能否 求到 最优整数解？ （1） max Z =3 X ； +2 X 2 s.t. 2 x 1 +3 x 2 乞 14.5 4捲 + x 2 三16.5 论 ， x 2 _ 0 x 1 , x 2 是整数 （1）解：将上述问题化为: Max Z =3 x 1 +2 x 2 +0 x 3 +0 x 4 s.t. 2 x 1 +3 X 2 + x 3 =14.5 4 x 1 + x 2 + x 4 =16.5 X i , X 2 , X 3 , X 4 _0 % , x 2 N 用单纯形法求解: C j C B 3 b 29/2 33/2 0 2 X 2 0 X 3 0 X 4 q X B X 3 X 4 X 1 0 0 2 【4】 3 3 1 0 0 T 0 1 29/4 33/8 1 2 -z (迭代过程略) 0 相应的线性规划问题最优解是 X = (7/2,5/2,0,0 ),目标函数的最优值z=31/2 凑整数 时， X i = (4,3,0,0 ， 是非可行解； T X 2 = (4,2,0,0 ，是非可行解； T X 3 = (3,3,0,0 ) ，是非可行解； X 4 = (3,2,0,0 T ，是可行解，z=13; 使用分支定界法解整数规划问题。 令 z =31/2， x 1 = x 2 =0是可行解。 所以 z =0，0乞 z * <31/2 把原问题分解为两个问题： (I) s.t. 2 x 1 +3 x 2 -14.5 4 x 1 + x 2 -16.5 0 一 捲—3; x 2 -0 (II) s.t. max z 2 =3 x 1 +2 x 2 max z 1 =3 x 1 +2 x 2 2 x 1 +3 X 2 _ 14.5 4 X 1 + X 2 _16.5 4 _ X 1 ; X 2 _0 将上述问题化为标准型，使用单纯形法求解： 为=3, X 2 =2是最优整数解，z=13. (2) max Z =3 X I +2 X 2 s.t. 2 X i +3 X 2 _ 14 2捲 + X 2 -9 论 ， X 2 _ 0 x 1 , X 2 是整数 (2)解： 使用图解法或者单纯形法求解此问题，线性规划问题最优解是( 目标函数最优值max z=59/4; 凑整数时， X I = (3,2) T ,是可行解，z=13; X 2 = (3,3) T ，是非可行解； X 3 = (4,2) T ，是非可行解; X 4 = (4,3) T ，是非可行解； 使用分支定界法求解原整数规划问题，令 令 z =59/4， X 1 = X 2 =0是可行解。 所以 z =0，z * <59/4； 把原问题分解为两个问题： (a)max z 1 =3 X 1 +2 X 2 s.t. 2 X 1 +3 X ^ 14 2 X 1 + X ^ 9 0込捲込3; x 2 _0 (b) max z 2 =3 x 1 +2 x 2 s.t. ，5/2)13/4 2 x 1 +3 x 2 冬 14 2 x 1 + x^ 9 4乞 X i ； X 2 -0 解得：最优整数解是 x 1 =4, x 2 =1; 目标函数是14. 5.2用分支定界法解： Max z= x 1 + x 2 s.t. 2 x 1 +9 x 2 /14 <51/14 -2 x 1 + x 2 咗 1/3 x- i , x 2 -0 x 1 x 2 都是整数 图解法解得：最优解是 B点(51/46+7/69-1/6, 51/23+14/69) 目标函数最优值为： 58/23+51/46-1/6 使用分支定界法求解， 令 z =58/23+51/46-1/6, x 1 = x 2 =0 是可行解; 因此 z=0,故 0 乞 58/23+51/46-1/6 将原问题分解为下列问题： (I) Max z 1 = x 1 + x 2 s.t. 2 x 1 +9 x 2 /14 <51/14 -2 x 1 + x 2 冬 1/3 x 2 -1 x- i ， x 2 -0 (I) Max z- i = x 1 + x 2 s.t. 2 x 1 +9 x 2 /14 <51/14 -2 x 1 + x 2 <1/3 x 2 亠2 X 1 , X 2 -0 按照以上步骤， 求解最终得到：最优解是（1, 2） 目标函数最优值z=3 5.3用Gomory切割法解如下问题： （1）max z= x 1 + x 2 s.t. 2捲 + x 2 乞6 4 x 1 +5 x 2 乞 20 论 ， x 2 _ 0 X 1 , X 2 是整数 解： 将上述问题化成标准型： max z= x 1 + x 2 +0 x 3 +0 x 4 s.t. 2 x 1 + x 2 + x 3 =6 4 x 1 +5 x 2 + x 4 =20 人 k， X 3 ， x 4 -0 X 1 , X 2 ， X 3 ， X 4 是整数 单纯形法求得最优解是：X * = 5/3,8/3,0,0，目标函数最优值13/3 T 变量之间的关系： x- i +5 x 3 /6- x 4 /6=5/3 x 2 -2 X 3 /3+ x 4 /3=8/3 把系数和常数项都分解成为整数和非负真分数 之和； 所以有： 2/3-5 x 3 /6-5 x 4 /61^0 2/3- （ x 3 + x 4 ） /3 <0 T 加入松弛变量 X 5 ，继续迭代得到最终结果：X = 0,4,2,0,0 ，目标函数最优值 4 解得：最优整数解是 x 1 =0， x 2 =4； 目标函数是4. （3） max z=3 捲- X 2 s.t. 3 x- i -2 x 2 _3 -5 x -4 x 2 冬-10 2 x 1 + x^ 5 x- i , x 2 亠 0 X i , X 2 是整数 解： 将原问题化成标准型，并使用单纯形法求解： T 最优解为X = （13/7,9/7,0,31/7,0），目标函数最优值30/7 从单纯形表可以得到变量间的关系，把系数和常数项都分解成整数和非负分数之 和，可以得知： 6/7-（ x 3 /7+2 x 5 /7）岂 0 加入松弛变量 X 7 ，把新的约束条件加入后，继续迭代，得到最终的结果： 最优解是为=1， x 2 =2 目标函数最优值1. 5.4某城市的消防总部将全市划分为11个防火区，设有四个防火站，如图所示 （ 课 本 P114）,其中①②③④是四个消防站，1, 2，…11是防火区域，根据历史资料 证实， 各个消防站可在事先规定的允许时间内对所有负责的地区的火灾予以消 灭，虚线表示 各地区是哪个消防站负责， 现在总部提出：是否可以减少消防站的 数目，仍能够负责各个地区的防火任务，如果可以，关闭哪个？ 提示：对每个消防站 定义一个0-1变量 x i ，令 1代表当某个防火区域由第i个消防站负责，0代表不是它负责。然后对每个防 火区域 列出约束条件； 解： 0 1代表当某个防火区域由第i个消防站负责，0代表不是它负责；i=1，2, 3, 4 建立数 学模型： Min z= ' x S.t. X | + x^-1 X , _1 x 1 + x 3 _1 X 3 -1 x 1 + x 3 + x^ -1 x 1 + x 4 丄 1 x 1 + x 2 + x^ -1 x 2 + x 4 -1 X 4 -1 x 3 + x 4 -1 有以上约束条件可以解得： X 1 = X 3 = & =1 继续求解 当 X 2 =0时，是可行解，目标函数是 3； 当 x 2 =1时，是可行解，目标函数是 4； * T X = 1,0,1,1 ，目标函数最优值是3. 比较可以得到，最优解是 所以，可以关闭消防站②。 5.5在有相互排斥的约束条件的问题中， 如果约束条件时乞型的，我们加 y i M ( y i 是 0-1变量，M是很大的常数)的方法统一在一个问题中。如果是 一型的，我们 将如何 利用 y i 和M呢？ 解：在m个约束条件右端分别减去 y i M( y i 是0-1变量，M是很大的常数，i=1， 2…m) m 并且 7 y i =m -1 i 4 5.6解0-1规划： (1) max z=4 x 1 +3 x 2 +2 x 3 s.t. 2x- i -5 x 2 +3 x 3 乞 4 4 捲 + x 2 +3 x 5 _ 3 x 2 + x 3 -1 论 ， X 2 , X 3 =0 或 1 解： 将(0, 0, 0) (0, 0, 1) (0, 1, 0) (1, 0, 0) (0, 1, 1) (1, 0，1) (1, 1, 0) (1,1,1)分别带入到约束条件中，可以得到：原问题的最优解是(0, 0, 1), 目标函 数最优值2. (2) min z=2 x 1 +5 x 2 +3 x 3 +4 x 4 s.t. -4 x- i + x 2 + x 3 + x 4 亠0 -2 x- i +4 x 2 +2 x 3 + x 4 -4 x- i + x 2 - x 3 + x^ - 1 % , X 2 , X 3 , X 4 =0 或 1 解： T X = 0,1,0,0 是一个可行解，目标函数数值是 4; 所以可以增加约束条件： 2 x 1 +5 x 2 +3 x 3 +4 沧込4 把可能的解(0, 0, 0, 0) (0, 0, 0, 1) - (1, 1, 1, 1)分别带入约束条件 的问题 中，得到最优解X * = 0,1,0,0 ，目标函数最优值4. T 5.7有四个工人，指派他们完成4种工作，每人做各种工作所消耗的时间如下表， 问 指派哪个人去完成哪种工作，可以使得总耗时最小？ A B C D 任务 人员 甲 乙 丙 丁 15 19 18 23 17 21 21 22 16 23 24 18 19 17 26 19 解：系数矩阵C为： 15 18 21 24 19 23 22 26 17 26 18 19 J9 21 23 17 一 ① 系数矩阵的每行元素减去该行的最小元素得矩阵 B ② B矩阵的每列元素减去该列的最小元素得到矩阵 A 此时，细数矩阵的每行每列都有元素 0. 先给 an 加圈，然后给 a 24 加圈，划掉 a 44 。给 a 32 加圈，划掉 a gs 得： 0 2 6 14 4 10 0 0 .2 3 6 9 0 3 0 一 此时，画圈的数目是3,少于4个，所以指派不成功，进入下一步， 给第四行打"号，给第四列打"号，给第二行打"号，将第一，第三行画一横线, 将第四 列画纵线，变换矩阵得到 0 2 6 10 0 3 3 10 0 0 J 2 5 0 4 0 一 给第一，第四列打 V 号，对第一，第二，第四行打 V 号，给第一，第四列画一纵 线，第三行画一横线，变换矩阵得到 甲乙丙丁 0 0 4 10 0 111 12 0 0 6 J 0 3 0 一 得到最优指派方案为： 甲一B;乙一A;丙一C; 丁一D 。 所消耗的总时间是 70. 2024年4月21日发(作者：淦冰冰) 运筹学习题答案 第一章（39页） 1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最 优 解、无界解还是无可行解。 （1） max z =论 x 2 5 x 1 +10 x 2 <50 x 1 + x 2 _ 1 x 2 _4 为， X 2 _0 （2） min z= x 1 +1.5 x 2 x- i +3 X 2 _3 x- i + x 2 丄 2 x- i ， x 2 亠 0 （3） max z=2 x 1 +2 x 2 x- 1 - x 2 _-1 -0.5x- i + x 2 -2 x- i ， x 2 -0 （4） max z= x j + x 2 x- i - x 2 -0 3 X r _ X 2 __3 x 1 ， x 2 -0 解： （1） （图略）有唯一可行解，max z=14 （2） （图略）有唯一可行解，min z=9/4 （3） （图略）无界解 （4） （图略）无可行解 1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。 (1) min 2=-3捲+4乂 2 -2乂 3 +5乂 4 4 X i - X 2 +2 X 3 - X 4 =-2 x- i + x 2 +3 x 3 - < 14 -2 x- i +3 x 2 - x 3 +2 x 4 亠 2 x - , X 2 , X 3 _0 , X 4 无约束 n m J 二、、' i =1 k 4 a ik x ik m 为 -X k = -1( =1,…,n) k 4 x ik 丄0 (i=1 …n; k=1,…,m) (1)解：设 z=-z , X 4 = X 5 - X 6 , X 5 , X 6 _0 标准型： Max z =3 x 1 -4 x 2 +2 x 3 -5( x 5 - x 6 )+0 x 7 +0 x 8 -M x 9 -M x 10 s. t . -4 x 1 + x 2 -2 x 3 + x 5 - x 6 + x 10 =2 x- i + x 2 +3 x 3 - x 5 + x 6 + x 7 =14 -2 x- i +3 x 2 - x 3 +2 x 5 -2 x 6 - x 8 + x 9 =2 X , X 2 , X 3 , X 5 , X 6 , X 7 , X 8 , X 9 , -0 X 10 初始单纯形表 ： Cj T C B X B 3 b X -4 X 2 2 X 3 -5 X 5 5 X 6 0 X 7 0 X 8 -M X 9 -M e X 10 -M X 10 2 X 7 -4 1 1 1 -2 3 1 -1 -1 1 0 1 0 0 0 0 1 0 2 14 0 14 -M X 9 r 2 -2 [3] -1 2 -2 0 -1 -M 1 0 0 0 2/3 -z 4M 3-6M 4M-4 2-3M 3M-5 5-3M 0 (2)解：加入人工变量 X i , X 2 , X 3 ,… X n ，得: n m Max s=(1/ p k )二 二 ik x ik -M x 1 -M x 2 -…..-M x n i=1 7 s.t. m x + 迟 X ik =1 k=4 (i=1,2,3…,n) (i=1,2,3…n; k=1,2….,m) x k 兰0, X j 20, C B M是任意正整数 初始单纯形表： -M • a 如/ 12/ C j … M M / P k / P k b … H rn/^ / P k … a n1/ /P k X n1 a n2/ / P k … a mn 0i X B X 1 X 2 X n X 11 X 12 X 1m X n2 X nm -M -M … -M -s X 1 X 2 1 1 … 1 n M 1 0 0 1 … … 0 0 0 0 • … 0 1 • 0 … … … … • 1 0 … 1 0 … 0 %+M • … 0 0 0 … 1 %+ M • … 0 … X n • … … … • 0 … 0 … 1 • 0 … … … • 1 … 0 %枷 陥/ / 4 -+M %+ M 7和 1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行 解，并代入目标函 数，确定最优解。 (1) max z=2 x 4 +3 x 2 +4 x 3 +7 x 4 2 x 4 +3 x 2 - x 3 -4 x 4 =8 X 1 -2 X 2 +6 x 3 -7 X 4 =-3 (2) max z=5 x 1 -2 x 2 +3 x 3 -6 x 4 X 1 , X 2 , X 3 , X 4 -0 x 1 +2 x 2 +3 x 3 +4 X 4 =7 2 x 1 + x 2 + x 3 +2 X 4 =3 x 1 x 2 x 3 x 4 _0 (1) 解： 系数矩阵A是： 2 * 3-1^ _2 6 —7 一 令 A=( R , P 2 ,巳, P 4 ) P 与卩 2 线形无关，以( R , P 2 )为基，捲, X 2 为基变量。 有 2 X ! +3 x 2 =8+ x 3 +4 x 4 x- i -2 x 2 =-3-6 x 3 +7 x 4 令非基变量 X 3 ， X 4 =0 解得：捲=1; x 2 =2 基解X =( 1, 2, 0, 0 ) 为可行解 ( 1 ) T 乙=8 同理，以( P ，巳)为基，基解X ⑵ =(45/13, 0,-14/13, 0 ) 是非可行解； 以( P , R )为基，基解 T X=(34/5, 0, 0, 7/5 ) T 是可行解， Z 3 =117/5； 以( F 2 ,巳)为基，基解 X ⑷ =(0, 45/16, 7/16, 0 ) 是 (3)T 可行解， Z 4 =163/16； 以( P 2 , P 4 )为基，基解X ⑸ =(0, 68/29, 0, -7/29 ) 是非可行解； T 以( P 4 ,巳)为基，基解X =(0, 0, -68/31, -45/31 ) 是非可行解； (6)T 最大值为 Z 3 =117/5;最优解 X ⑶ =(34/5, 0, 0, 7/5 ) 。 T (2) 解： 系数矩阵A是： 12 3 4 $112- 令 A=（ R , P 2 ,巳, P 4 ） R , P 2 线性无关，以( P i , P 2 )为基，有: x- i +2 X 2 =7-3 x 3 -4 x 4 2 X 1 + X 2 =3- X 3 -2 X 4 令 X 3 , X 4 =0 得 X - I =-1/3, X 2 =11/3 基解 X = (-1/3,11/3, 0, 0 ) 为非可行解； (1)T 同理，以( P , P j )为基，基解 X = (2/5, 0, 11/5, 0 ) 是可行解 Z 2 =43/5; (2)T 以( P , R )为基，基解X ⑶ =(-1/3, 0, 0, 11/6 ) T 是非可行解； 以( P 2 , P j )为基，基解X ⑷ =(0, 2, 1, 0 ) 是可行解， Z 4 =-1； T 以( P 4 , P j )为基，基解 X =(0, 0, 1, 1 ) 是 Z 6 =-3 ； (6)T 最大值为 Z 2 =43/5;最优解为X⑵=(2/5, 0, 11/5, 0 ) 。 T 1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步 相当于图形的哪一点。 （1） max Z =2 X 1 + X 2 3 X 1 +5 X 2 乞 15 6 X 1 +2 x 2 虫24 X 1 , X 2 -0 （2） max Z =2 X 1 +5 X 2 X <^4 2 x 2 辽 12 3 X 1 +2 X ^ 18 X - I , X 2 -0 解：（图略） （1） max z=33/4 最优解是 （ 15/4,3/4） 单纯形法： 标准型是 max z=2 为 + x 2 +0 x 3 +0 x 4 s.t. 3 x ! +5 x 2 + x 3 =15 6捲 +2 X 2 + x 4 =24 X i , X 2 , X 3 ,沧 —0 单纯形表计算： C j C B X B X 3 X 4 2 b 15 24 0 3 4 -8 3/4 15/4 -33/4 X 1 1 X 2 0 X 3 0 X 4 4 0 0 3 [6] 2 0 1 0 0 1 0 5 1 0 0 1 0 0 1/4 -1/12 -1/12 0 1 5 4 2 1 [4] 1/3 1/3 1 0 0 -z 0 2 X 3 X 1 0 -1/2 1/6 3/4 12 -z 1 2 X 2 X 1 -1/3 -1/8 5/24 -7/24 -z 解为：（15/4, 3/4, 0, 0 ） T Max z=33/4 迭代第一步表示原点；第二步代表 C点（4, 0，3，0 ） ； T 第三步代表B点（15/4，3/4，0，0 ） 。 T （2）解：（图略） Max z=34 此时坐标点为（2，6） 单纯形法，标准型是： s.t. x 1 + x 3 =4 Max z=2 x 1 +5 x 2 +0 x 3 +0 x 4 +0 x 5 2 X 2 + X 4 =12 3 X - I +2 X 2 + X 5 =18 X i , X 2 , X 3 , X 4 , X S -0 俵略) 最优解 X= (2, 6, 2, 0, 0 ) T Max z=34 迭代第一步得X (1) = (0, 0, 4, 12, 18 ) T 表示原点，迭代第二步得X ⑵ =(0, 6, 4, 0, 6 ) T ，第三步迭代得到最优解的点。 1.5以1.4题(1)为例，具体说明当目标函数中变量的系数怎样变动时，满足约 个顶点，都可能使得目标函数值达到最优。 解：目标函数： max z=C| X 1 + c 2 X 2 (1) 当 C 2 =0 时 X 2 =- ( &/ c 2 ) X 1 +z/ c 2 其中，k=_G/ c 2 k AB =-3/5 , k Bc =-3 k「k Bc 时， c 1 , 9 同号。 当 C 2 ・、0时，目标函数在C点有最大值 当cr 0时，目标函数在原点最大值。 k B C - k- k A B 时， c 1 , $ 同号。 当 C 2 0,目标函数在B点有最大值； 当cr 0, 目标函数在原点最大值。 k A B - k - 0 时， c 1 , c 2 同号。 当c^ 0时，目标函数在A点有最大值 当 c 2 0时，目标函数在原点最大值。 k -0时， C l , °异号。 束条件的可行域的每一 当 C2, 0, C l - 0时，目标函数在A点有最大值； 当 C 2 0, C l 0时，目标函数在C点最大值。 k= k AB 时，q, C 2 同号 当 C 2 ・、0时，目标函数在AB线断上任一点有最大值 当C 2 - 0,目标函数在原点最大值。 k= k B C 时， C l ， C 2 同号。 当 C2- 0时，目标函数在BC线断上任一点有最大值 当C 2 - 0时，目标函数在原点最大值。 k=0 时， C l =0 当 C 2 ・、0时，目标函数在A点有最大值 当 C 2 ■ 0，目标函数在OC线断上任一点有最大值 （2）当 C 2 =0 时，max z= C l x i C 1 -0时，目标函数在C点有最大值 C l 0时，目标函数在OA线断上任一点有最大值 C l =0时，在可行域任何一点取最大值。 1.6分别用单纯形法中的大 M法和两阶段法求解下列线性问题, 解。 （1）max z=2 x 1 +3 x 2 -5 x 3 x 1 + x 2 + x^ - 15 2 x 1 -5 x 2 + x<^ 24 x 1 , x 2 亠0 (2) min z=2 x 1 +3 x 2 + x 3 X +4 x 2 +2 X 3 _ 8 并指出属于哪类 3 禺 +2 x 2 - 6 X i , X , X 3 - 0 (3) max z=10 x 1 +15 x 2 +12 x 3 5 x 1 +3 x 2 + X 3 - 9 -5x- i +6 X 2 +15 x 3 _ 15 2 x 1 + x 2 + x^ 5 X 1 , X 2 , X 3 -0 (4) max z=2 x 1 - x 2 +2 x 3 x- i + x 2 + x 3 丄 6 -2 x- i + x 3 亠 2 2 x 2 - x 3 _0 X 1 , X 2 , X 3 -0 解：(1)解法一：大M法 化为标准型： Max z=2 x 1 +3 x 2 -5 x 3 -M x 4 +0 x 5 -M x 6 s.t. x- i + x 2 + x 3 + x 4 =7 2 x- i -5 x 2 + x 3 - x 5 + x 6 =10 x 1 , x 2 , x 3 , , x 4 , x^ 0 M 是任意大整数。 单纯形表： C j C B 2 b 7 x - 3 X 2 -5 X 3 -M X 4 0 X 5 -M X 6 0 i X B X 4 -M 1 1 1 1 0 0 7 -M X 6 10 17M 2 5 2M-10 4/7 45/7 -102/7 [2] -5 1 2M-5 1/2 1/2 0 0 1 0 0 2/7 5/7 -1 -M 1/2 -1/2 1 0 -1/2 1/2 5 -z -M X 4 X i 3M+2 3-4M [7/2] 0 1 0 0 1 0 -5/2 4/7 - 2 -z 3 (7/2)M+8 0.5M-6 1/7 6/7 -50/7 0.5M+1 -1.5M-1 1/7 -1/7 -1/7 1/7 -M+1/7 X 2 X i 1 0 0 2 -z 最优解是： -M-16/7 -1/7 X= (45/7, 4/7, 0, 0, 0 ) T 目标函数最优值 max z=102/7 有唯一最优解。 解法二： 第一阶段数学模型为 min w= x 4 + x 6 S.t. % + x 2 + x 3 + x 4 =7 2 x- i -5 x 2 + x 3 - x 5 + x 6 =10 X ! , X 2 , X 3 , X 4 ， x 5 , x 6 -0 (单纯形表略) 最优解 X=(45/7，4/7，0，0，0 ) T 目标函数最优值 min w=0 第二阶段单纯形表为： 3 C j 2 C B X B X 2 X 1 -5 X 3 0 X 5 q b 4/7 45/7 -102/7 X 1 X 2 3 2 最优解是 0 1 0 1 0 0 1/7 6/7 -50/7 1/7 -1/7 -z -1/7 X= (45/7, 4/7, 0, 0, 0 ) T Max z=102/7 (2) 解法一：大M法 z =-z 有 max z =-min (- z ) =-min z 化成标准形： Max z =-2 x- i -3 x 2 - x 3 +0 x 4 +0 % 5 -M x 6 -M x 7 S.T. 捲 +4 x 2 +2 x 3 - x 4 + x 6 =4 3 x - +2 X 2 - X 5 + x =6 X ! , X 2 , X 3 , X 4 , X 5 , x e , X 7 —0 (单纯性表计算略) 线性规划最优解X=(4/5, 9/5, 0, 0, 0 , 0 ) T 目标函数最优值min z=7 非基变量 X 3 的检验数 -3 =0,所以有无穷多最优解。 两阶段法： 第一阶段最优解X=(4/5, 9/5, 0, 0, 0, 0 ) 是基本可行解,min w=0 T 第二阶段最优解(4/5, 9/5, 0, 0, 0, 0 ) min z=7 T 非基变量 x 3 的检验数二 3 =0,所以有无穷多最优解 （3）解：大M法 加入人工变量，化成标准型： Max z=10 X ! +15 X 2 +12 X 3 +0 x 4 +0 x 5 +0 x 6 -M x 7 s.t. 5 x - +3 X 2 + X 3 + X 4 =9 -5 捲+6 x 2 +15 x 3 + x 5 =15 2 x 2 + x 3 - x 6 + x 7 =5 X i , X 2 , X 3 , X 4 , 0 X 5 , X 6 , X 7 — 单纯形表计算略 当所有非基变量为负数，人工变量 X 7 =0.5 , 所以原问题无可行解 两阶段法（略） （4）解法一：大M法 单纯形法，（表略）非基变量 X 4 的检验数大于零，此线性规划问题有无界解 两阶段法略 1.7求下述线性规划问题目标函数 z的上界和下界; Max z= G % + c 2 x 2 a^x- i a 12 x 2 - b i a 2i X 1 ■ 822 X 2 — b2 其中：1_ G —3,4_g _6,8_0 _12 ,10_b 2 _14 , -1 _a 1 ^3,2_a 12 _5 , 2 _ a 21 _ 4 , 4 _ a 22 _ 6 解： 求Z的上界 Max z=3 X - I +6 X 2 s.t.-论 +2 x 2 _ 12 2 为 +4 x 2 _ 14 加入松弛变量，化成标准型，用单纯形法解的，最优解 X=(0, 7/2, 5, 0 ) T 目标函数上界为z=21 存在非基变量检验数等于零，所以有无穷多最优解 求z的下界 线性规划模型： Max Z= X - I +4 X 2 s.t. 3 X 1 +5 x 2 岂 8 4 X 1 +6 X ^10 X 2 , X ^0 加入松弛变量，化成标准型，解得: 最优解为 X= （0, 8/5, 0, 1/5 ） T 目标函数下界是z=32/5 1.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变 量， a1 ，，，d，，为待定常数，试说明这些常数分别取何值时，以下 结论成立。 （1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解； a2a3C102 （3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为为， 换出变量为 x 6 基b 4 X 1 X 2 X 3 X 4 X a 2 X 6 X 3 d x 4 2 X 3 C j _Zj a -3 -5 C 2 1 0 0 0 0 1 0 0 0 0 1 0 -1 a 3 C 1 -1 -4 -3 解： （1） 有唯一最优解时，d—O, c 「0, c< 0 （2） 存在无穷多最优解时，d_0, G _0, C 2 =0或d_0, C 1 =0, C 2_ 0. （3） 有无界解时，d_0, c$0, q、0且a$0 （4） 此时，有 d 丄0, c< 0 并且 & _ c 2 , a 3 > 0 , 3/ a 3 “ d/4 班次 1 2 3 4 5 6 设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公 交线 路至少配备多少司机和乘务人员。列出线型规划模型。 解： 设 X k （k=1 , 2, 3, 4, 5, 6）为 X k 个司机和乘务人员第k班次开始上班 1.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下: 时间 所需人数 6点到10点 [60 10点到14点 70 14点到18点 ： 60 18点到22点 50 22点到2点 ”0 2点到6点 30 建立模型： Min z= x- i + x 2 + x 3 + x 4 + x 5 + x 6 s.t. x- i + x^ _ 60 X i + x 2 亠 70 x 2 + x 3 亠 60 x 3 + x 4 _50 x 4 + x 5 _20 x 5 + x 6 _30 X l , X 2 , X 3 , x 4 , X 5 , X 6 -0 1.10某糖果公司厂用原料 A、B、C加工成三种不同牌号的糖果甲乙丙，已知各 种糖 果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单 位加工费 用及售价如表所示： 原料 甲 乙 丙 原料 成本（元/ 千 每月 限制用 量 （千克） 克） I 2 A >60% >15% 2000 B 11.5 2500 C <20% <60% <50% 1 1200 加工费 0.5 0.4 0.3 售价 3.4 2.85 2.25 问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模 型。 解 ： 解：设 X i ， X 2 ， X 3 是甲糖果中的A，B，C成分， X 4 ， x ， X 6 是乙糖果的A， B，C成分， X 7 ， X 8 ， X 9 是丙糖果的A，B，C成分。 线性规划模型： Max z=0.9 X i +1.4 X 2 +I.9 X 3 +0.45 x 4 +0.95 x +1.45 冷-0.05% +0.45 X +0.95% 79 s.t. -0.4 x 1 +0.6 x 2 +0.6 x 3 ^0 -0.2 x- i -0.2 x 2 +0.8 x 3 _0 -0.85 沧+0.15 x 5 +0.15 x e _0 -O.6 x 4 -O.6 x 5 +0.4 X 6 _0 -0.7X 7 -0.5 x +0.5X 9 岂0 x 1 + x 4 + x <2000 x 2 + x 5 + x <2500 8 x 3 + x 6 + < 1200 x ) X i , X 2 , X 3 , X 4 , X 5 , X 6 , x 7 x 8 x g , , 78 -0 1.11某厂生产三种产品I、丨【、III。每种产品经过AB两道加工程序，该厂 有 两种设备能完成A工序，他们以A,A 2 表示；有三种设备完成B工序，分别为 ， B 2 ， B 3 ;产品I可以在AB任何一种设备上加工，产品丨【可以在任何规格 的A 设备上加工，但完成B工序时，只能在 B 1 设备上加工；产品III只能在 A ， B 2 上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化 设备 I 5 7 6 产品 II III A A 2 Bi B 2 B 3 10 9 设备有效台 满负荷时的 时 设备费用 300 6000 10000 4000 321 250 783 200 12 8 11 4 7 7000 4000 原料费 单价 解： 0.25 1.25 0.35 2.00 0.5 2.8 产品1,设 A 1 , A 2 完成A工序的产品 X 1 ， X 2 件；B工序时， B 1 , B 2 ， B 3 完成 B工序的 X 3 , X 4 , X 5 件，产品丨【，设 A I , A 2 完成A工序的产品 X 6 , X 7 件；B工 序 时，B完成B的产品为 X 8 件；产品111, 1 A 完成A工序的 X 件，B完成B 292 工序的 X 9 件； X 1 + X 2 = X 3 + X 4 + x 5 x 7 X 6 + = 7 X 8 8 建立数学模型： Max z=(1.25-0.25)*(人 + x )+(2-0.35)*(沧 + X )+(2.8-0.5) X -(5 洛+10 79 X e )300/6000-(7 x 2 +9 X +12 X )321/10000-(6 x 3 +8 沧 ) 250/4000-(4 x 4 +11 79 X 9 )783/7000-7 X 5 *200/4000 s.t 5 x 1 +10 x 6 三6000 7 X 2 +9 X +12 X 9 乞 10000 7 6 X 3 +8 X <4000 8 4 X 4 +11 X < 7000 9 7 x 5 <4000 X 1 + X 2 = X 3 + X 4 + x 5 x 7 x 8 X 6 + = 78 X 7 X X 9 “ 人兀皿凶必风，,, -0 T 最优解为 X= （1200，230，0，859，571，0，500，500，324 ） 最优值 1147. 试题： 1. （2005年华南理工大学）设某种动物每天至少需要 700克蛋白质、30克矿物 质、100毫 克维生素。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价 如下 表所示： 试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模 表1—1 矿物质（克） 1 饲料 1 蛋白质（克） 3 维生素（毫克） 0.5 价格（元/公 斤） 0.2 0.5 2 2 1 3 1 0.2 0.2 4 6 2 2 5 0.5 18 0.8 解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可 0.7 0.4 0.3 0.8 解题过程： min z = 0.2x 「 0.7x 2 0.4x 3 0.3x 0.8x 5 3% + 2x 2 + x 3 +6x 4 + 18x 5 K 700 x, +0.5x 2 +0.2x 3 +2x 4 +0.5卷 X 30 s.t彳 0.5x , +x 2 +0.2x 3 +2x 4 +0.8x 5 兰 100 X , ,X 2 ,X 3 ,x 4 ,X 5 X0 第二章（67页） 2.1用改进单纯形法求解以下线性规划问题。 （1） Max z= 6 x 1 -2 x 2 +3 x 3 2 x 1 - x 2 +3 x 3 二2 为+4 x 3 乞4 人， X 2 ， X 3 — 0 （2） min z=2 x 1 + x 2 3 x 1 + x 2 =3 4 X J +3 X 2 _6 x- i +2 x 2 -3 x- i , x 2 -0 解： （1） 先化成标准型： Max z=6 x 1 -2 x 2 +3 x 3 +0 x 4 +0 x 5 s.t. 2 x 1 - x 2 +2 x 3 + x 4 =2 x- i +4 x 3 + x 5 =4 X l , X 2 , X 3 , X 4 , X 5 _0 令 B o = ( P 4 , P 5 )= ■ N o =( P ， P 2 ， P 3 ) = 2 -1 0 1 0 0 = ( X 4 , X 5 ) , C B =(O,O) 、 X B ° T o h 2 、 4 ， b0 ， N =( X ! ， X 2 ， X 3 ) X 0 T J C N ° = (6,-2,3) ， B 0 = =l4 丿 非基变量的检验数 口 _ C N ° '-N 。- - C B 0 耳二 N 0 = C N = 0 =(6,-2,3) 因为 X i 的检验数等于6,是最大值，所以， X i 为换入变量, B A 0 b ° = I 0 4 」 —1 ‘2 ； B 0 P i = 、 由二规则 得: X 4 为换出变量 '2 0 , X B -= ( X I , X 5 ) T , C B , =(6,0). B l =( P 4 , P 5 ) = 1 」 N =( X 4 ， X 2 ， X 3 ) N I =(R, P 2 , P 3 ) , X i T C N I = (0 , , , B i 」 -23) 0.5 0 -0.5 b ,bi = 非基变量的检验数 叫=( - 3， 1 ，-3) 因为 X 2 的检验数为 1,是正的最大数。所以 X 2 为换入变量; B 0 P 2 = A -0.5 0.5 由二规则得： =6 所以 X 5 是换出变量 B 2 =( R , P 2 ) = N 2 =( F 4 , P 5 , P 3 ), -1 0 X , X B 2 = ( x 1 x 2 ) , , C B = (6,-2) . 2 N 2 = ( X 4 , x , X 3 ) T 1 0 1 - 1 2 C N 2 =(0 , 0, 3)， B 2- , b 2 = 6 2 I 」 」 非基变量的检验数 ；邛= (-2, -2,-9) 非基变量的检验数均为负数，愿问题已达最优解。 最优解X= 广4、 0 即：X= (4,6,0 ) T 目标函数最优值 max z=12 （2） 解： Min z=2 S.T. 3 捲 + x 2 + x 4 =3 4 捲+3 x 2 - X 3 + X 5 =6 x- i +2 x 2 + x 6 =3 x 2 +0 x 3 +M x 4 +M x 5 +0 x 6 X 6 - 0 M是任意大的正数。 （非基变量检验数计算省略） 原问题最优解是X= （0.6，1.2，0） 目标函数最优值：z=12/5 2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见 表，试将空白处数字填上。 3 5 4 C j 0 0 0 C B X B X 2 X 5 b 8/3 14/3 X 1 X 2 X 3 X 4 X 5 X 6 5 2/3 -4/3 1 0 0 5 1/3 -2/3 0 1 0 0 0 0 X 6 C j - Z j 20/3 5/3 -1/3 0 0 . 4 4 -2/3 -5/3 0 0 1 0 X 2 15/41 -6/41 -2/41 8/41 5/41 -12/41 -10/41 4/41 15/41 X 3 X i C j - Z j 解: C j 3 b 8/3 14/3 20/3 5 4 0 X 4 0 X 5 0 X 6 C B X B X 2 X 5 X 6 C j - Z j X 1 X 2 X 3 5 0 0 ■ 5 4 3 X 2 X 3 X 1 C j - Z j 80/41 50/41 44/41 0 0 1 0 1 0 0 0 0 1 0 0 15/41 -6/41 -2/41 -45/41 2.3写出下列线性规划问题的对偶问题。 (1) min z= 2 x 1 +2 x 2 +4 x 3 2 论+3 X 2 +5 x 3 _2 3 X 1 + X 2 +7 X 3 辽3 X - I +4 X 2 +6 X 3 < 5 X i 必， X 3 —0 (1) 解：对偶问题是： Max w=2 y- i -3 y 2 -5 y 3 s.t. 2 y i -3 y 2 - y -2 3 y i - y 2 -4 y^~ 2 5%-7 y 2 -6 y 3 -4 y i , y 2 , y 3 -0 (2) max z= X - I +2 X 2 +3 X 3 +4 X 4 - X - I + X 2 - X 3 -3 X 4 =5 6 x i +7 X 2 +3 X 3 -5 X 4 _ 8 12 X - I -9 X 2 -9 X 3 +9 X ^ 20 X i , X 2 一 0 ； X 3 -0 ； X 4 无约束 解： 对偶问题： Min w=5 y- i +8 y 3 +20 y 4 S.t. - y i +6 y 3 +i2 y -i y i +7 y 3 -9 y -2 - y i +3 y 3 - 44 9* 乞 3 -3 y i -5 y 3 +9 *=4 y 无约束，y 3 乞0; m n * -0 (3) min z二二二 qx j il j 4 n ' X ij =4 j 4 m i=1,…,m ' X ij =b j j=1,…,n i 4 X ij -0 解： m n 对偶冋题:max w=^ a i y i +送 b j y m 岀 s.t. y i' +y ； 卅兰q '' '' yy m j , 无约束 i=1,2,….m; j=1,2,….n ⑷ n Max z=二 c j x j jm n ' a/ _ b , i=1,….,g _ m j 吕 n ■- j a ij x j 二 i= m 1 1,m 1 - 2,..., m b i , 三 X j -0,当 j=1 , ….,m乩 Xj 无约束，当 j= n 「 1,..., n 解： m Min w八 b j y i T II s.t. m ' a* - C j i ± j=1,2,3- n1 、 a j y ； - c j j= n +1, 口+2,….n i i 4 y i -0 n y m i=1,2 …. m 无约束， ) =^+1, E+2….m 2.4判断下列说法是否正确，并说明为什么. (1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。 (2) 如线性规划的对偶问题无可行解，则原问题也一定无可行解。 (3) 如果线性规划 问题的原问题和对偶问题都具有可行解， 则该线性规划 问题一定有有限最优解。 (1) 错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在； (2) 错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解； (3) 错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能 有 无界解； 2.5设线性规划问题1是： n Max z 1 =二 C j 为 j 旦 ，i=1，2…，m x j -0, j =, n ( y 1 ,..., y m )是其对偶冋题的最优解 又设线性规划问题2是 n Max Z 2 =' C j X j jm n ' a j X j 虫 b + k i ， i=1，2…，m j 毘 x j -0, j = , n 其中 k i 是给定的常数，求证： m max z 2 _ max 乙 + ' k i y i i =1 解： 证明：把原问题用矩阵表示： Max z- i = AX _b X _0 b= ( D , b 2 ... b m ) T 设 可行解为 X i ,对偶问题的最优解 Y 1 = ( y i , y … y m )已知。 Max z 2 =CX s.t. AX mb+k X -0 k= ( k i , k 2 ... k m ) T 设可行解为 X 2 ，对偶问题最优解是丫 2 ,对偶问题是， Min w=Y(b+k) S.t. YA -C Y -0 因为％是最优解，所以丫 (b+k)乞丫 1 (b+k) 2 X 是目标函数 Z 2 的可行解，A X 2 乞b+k ； ^A% 岂丫 (b+k)岂 Y b+Yk 原问题 222 和对偶问题的最优函数值相等，所以不等式成立，证毕。 2.6已知线性规划问题 Max z= C | X- | c 2 x 2 c 3 x 3 X j - j _ 1 ， ... ， 0,5 用单纯形法求解，得到最终单纯形表如表所示，要求： (1) 求 a ii ， a i2 ， a i3 ， a 2i ， a 22 ， a 23 ， b i ， b 2 的值; (2 )求 C i ,C 2 ,C 3 的值; X B X 3 b 3/2 X i X 2 X 3 X 4 X 5 1 0 1 1/2 -1/2 x C j — Zj 2 1/2 -3 1 0 0 0 -1 2 -4 0 解： (1) 初始单纯形表的增广矩阵是: C i = a i3 _a 2i 1 0 0.5 1 1 a 3 1 0.5 1 0 b i 0 1 b 2 -0.5 1.5 2 2 22 最终单纯形表的增广矩阵为 C 2 = C 是C作初等变换得来的，将C作初等变换，使得C的第四列和第五列 的矩 2 阵成为C的单位矩阵。有： 2 an=9/2；印 2 =1;盹=4; b =9； b 2 =5 由检验计算得： C| =-3； C 2 = C 3 =0 2.7已知线性规划问题 Max z=2 x 1 + x 2 +5 x 3 +6 x 4 s.t. 2 x 1 + x 3 + x 4 空 8 2 x 1 +2 x 2 + x 3 +2 x^ - 12 X j -0, j=1,…4 a 21 =5/2； a 22 =1； a 23 =2； 对偶变量 y 1 , y 2 ，其对偶问题的最优解是 y ； =4, y ； =1 ，试应用对偶问题 的性 质，求原问题的最优解。 解： 对偶问题是： Min w=8 y 1 +12 y 2 s.t. 2 y 1 +2 y 2 丄2 2 y 2 -1 y i + y 2 -5 %+2 y 2 - 6 y i , y 2 - o 互补松弛性可知，如 卞, Y 是原问题和对偶问题的可行解，那么， Y?X s =0 和 Y S X?=0，当且仅当 X ， Y? 是最优解。 设X,Y是原问题和对偶问题的可行解， Y s =（ y 3 ， y ， y ， y ） 4 有： X Y =0;且 Y S X=0 S X 5 = X 6 =0，原问题约束条件取等号， X 3 =4； X 4 =4 最优解 X=（0, 0, 4, 4 ） T 目标函数最优值为44。 2.8试用对偶单纯形法求解下列线性规划问题。 （1）min z= x 1 + x 2 2 为 + x 2 _ 4 x 1 +7 x 2 _ 7 X i , X 2 — 0 （2） min z=3 捲 +2 x 2 + x 3 +4 x 4 2 x 1 +4 x 2 +5 x 3 + x 4 - 0 3 x 1 - x 2 +7 x 3 -2 x 4 -2 5 x 1 +2 x 2 + x 3 +10 x 4 -15 为，X 2 , X 3 , & 解： （1） 取w=-z，标准形式： -0 Max w=- x- i - x 2 +0 x 3 +0 x 4 s.t. -2 X - - X 2 + X 3 =-4 - X - -7 X 2 + X 4 =-7 X i , X 2 , X 3 , X 4 一 U 单纯形法求解(略)： 最优解： X= (21/13, 10/13, U, U ) T 目标函数最优值为31/13。 (2) 令：w=-z,转化为标准形式： Max w=-3 X 1 -2 X 2 - X 3 -4 X 4 +0 X 5 +0 X 6 +0 X 7 s.t. -2 X 1 -4 X 2 -5 X 3 - X 4 + X 5 =0 -3 x- i + x 2 -7 x 3 +2 x 4 + x 6 =-2 -5 x- i -2 x 2 - x 3 -6 x 4 + x 7 =-15 X 1 ， X 2 ， X 3 ， X 4 ， X 5 ， X 6 ， X 7 . 单纯形法略 原问题最优解： X=（3，0，0，0，6，7，0 ） T 目标函数最优值为9。 2.9现有线性规划问题 max z=- 5 x 1 +5 x 2 +13 x 3 -x- i + x 2 +3 x 3 - 20 12 x- i +4 x 2 +10 x 3 - 90 X 1 ， X 2 ， X 3 -0 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什 么变化？ （1 约束条件1的右端常数20变为30 (2) 约束条件2的右端常数90变为70 (3) 目标函数中 x 3 的系数变为8 (4) x i 的系数向量变为 1 J2丿 (5) 增加一个约束条件2 X i +3 « +5怡乞50 (6) 将约束条件2变为10^+5 x 2 +10 x 3 空100 解： 把原问题化成标准型的： Max z=-5 x 1 +5 x 2 +13 X 3 +0 x 4 +0 x s.t -x- i + x 2 +3 x 3 + x g =20 12 x- i +4 x 2 +10 x 3 + x g =90 %， x ， X 3 ， x 4 ， X 5 - 0 单纯形法解得： 最优解： X= (0，20，0，0，10 ) T 目标函数最优值为100。 非基变量x- i 的检验数等于0，原线性问题有无穷多最优解 (1) 约束条件二的右端常数变为30 有 ： ^B J b 因此b =b「b 单纯形法解得： 最优解： X= (0，0，9，3，0 ) T 目标函数最优值为117。 (2) 约束条件Q右端常数变为70 有 b=B‘ ： b 因此b =b 比 单纯形法解得，最优解： X= (0，5，5，0，0 ) T 目标函数最优值为90。 (3) X 3 的系数变成8, X 3 是非基变量，检验数小于0,所以最优解不变 (4) x i 的系数向量变为 x i 是非基变量，检验数等于-5,所以最优解不变。 (5) 解：加入约束条件 0 3 用对偶单纯形表计算得： X= (0, 25/2, 5/2, 0, 15, 0 ) T 目标函数最优值为95。 (6) 改变约束条件，巳,巳, P 5 没有变化, 线性规划问题的最优解不变。 2.10已知某工厂计划生产1,11」11三种产品，各产品在ABC设备上加工，数 据如 下表， I II III 设备代号 每月设备 有效 台时 A B C 单位产品利润 /千兀 8 10 2 3 2 5 13 2 10 8 10 2.9 300 400 420 (1)如何充分发挥设备能力，使生产盈利最大? (2) 如果为了增加产量，可借 用其他工厂的设备 B，每月可借用60台时， 租金为1.8万元，问借用是否合算？ (3) 若另有两种新产品IV,V ,其中IV为10台时，单位产品利润2.1千元； 新 产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利1.87 千元。 如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否划 算？ (4) 对产品工 艺重新进行设计，改进结构，改进后生产每件产品 I，需要 设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元， 问 这对原计划有何影响？ 解： (1) 设：产品三种产品的产量分别为， X 1 , X 2 , X 3 ，建立数学模型： s.t. Max z=3 x 1 +2 x 2 +2.9 X 3 8 x 4 +2 x 2 +10 x 3 乞300 10 x 1 +5 x 2 +8 x 3 - 400 2^+13 x 2 +10 x 3- 420 X i , X 2 , X 3 一0 把上述问题化为标准型，用单纯形法解得： 最优解： X=（ 338/15, 116/5, 22/3，0，0，0 ） T 目标函数最优值为2029/15。 （2） 设备B的影子价格为4/15千元/台时，借用设备的租金为 所以，借用B设备不合算。 （3） 设备V,V生产的产量为 x ， X 8 ，系数向量分别为： P 7 =（12,5,10） 丁 P 8 =（4,4,12） 丁 检验数二 7 =-0.06,所以生产 V不合算， 6=37/300,生产V合算。 单纯形法计算得： 最优解： X=（ 107/4，31/2，0，0，0，0，55/4 ） T 目标函数最优值为10957/80。 （4） 改进后 ， 检验数二 1 =253/300，大于零。 所以，改进技术可以带来更好的效益。 2.11分析下列参数规划中当t变化时最优解的变化情况 （1）Max z （ t ） =（3-6t）捲+（2-20 X 2 +（5-5t） X 3 （t_0） s.t. x- i +2 x 2 + x 3 - 430 3 X 1 +2 X 3 - 460 0.3千兀每台时。 x- i +4 x 2 - 420 x i , X 2 , X 3 _ 0 (2) Max z ( t ) =(7+2t) x 1 +(12+t) x 2 +(10-t) x 3 (t 亠 0) s.t. x- i + x 2 + x 3 - 20 2 x 1 +2 x 2 + x 3 - 30 X i , x , X 3 一0 (3) Max Z (t) =2 x 1 + x 2 (0 ^t 乞25) s.t. X 1 - 10+2t x- i + x 2 - 25-t x 2 - 10+2t x- i , x 2 -0 (4) Max z (t) =21 x- i +12 x 2 +18 x 3 +15 x 4 (0 -1 - 59) s.t. 6 x 1 +3 x 2 +6 x 3 +3 & - 30+t 6*3 x 2 +12 x 3 +6 x 4 - 78-t 9 x 1 +3 x 2 -6 x 3 +9 x 4 135-2t 人, X 2 , X 3 , x 4 -0 解： (1)化成标准形式： Max Z (t) =(3-6t) X 1 +(2-2t) x ? +(5-5t) X 3 +0 X 4 +0 X 5 +0 X s (t - 0) s.t. x- i +2 x 2 + x 3 + X 4 =430 x- i +4 x 2 - 420 3 x 1 +2 x 3 + x 5 =460 x- i +2 x 2 + x 3 + X 4 =430 x- i +4 x 2 + x 6 =420 X i , X 2 , X 3 , X 4 , X 5 , X 6 _0 令t=0,用单纯形表计算， 3-6t C j 2-2t 5-5t 0 X 4 0 X 5 0 X 6 9i C B X B X 2 X 3 X 6 B X 1 X 2 X 3 2-2t 5-5t 0 -z 100 230 20 -1/4 3/2 2 1 0 0 0 1 0 0.5 -1/4 1/2 [1] 0 0 1 - 460 20 0 -2 t-1 2t-2 1350t - t-4 0 0 0 1350 t增大，t大于1,首先出现二 4 ，二 5 大于0,所以当0乞2 1时有最优解 X=（0，100，230，0，0，20 ） T 目标函数最优值为1350（t-1） t=1是第一临界点 t大于1时， X 6 是换出变量。 t 大于 1,最优解是：X=（0，0， 0, 430，460, 420 ） T （0乞2 1）。 目标函数最优值为 Max z （ t ） =0, （ t 大于 1） （2） 化成标准型，然后令t=0,单纯形法解得： t开始增大时，当t大于8/3时，首先出现二 大于0,所以0^2 8/3，得最 优解。 4 目标函数最优值 Max z （ t ） =220,（ 0乞2 8/3） 所以，t=8/3为第一临界点。 当8/3 x 3 为换出变量，使用单纯形法 继续迭 4 代，t继续增大，当t>5,首先J大于0, 8/3 目标函数最优值为180+15t 所以，t=5为第二临界点。 , (8/3 X= (0, 15, 0, 5 ) T 当t>5时，捲是换入变量， x 为换出变量，单纯性法计算， 当t继续增大，所有检验数都非正，所以当 t>5,最优解： X=( 15，0，0，5 ) T 目标函数最优值为105+30t， t> 0 (3)化成标准型，令t=0,用单纯形法计算得： 当t开始增大，t大于5时，首先出现 b 2 小于0,当0岂M5，最优解为： X= (10+2t, 0, 10+2t, 5-t, 0 ) T 目标函数最优值为6t+30 所以t=5是第一临界点。 , (0空仁5)。 当t大于5时， X 4 是换出变量， X 5 是换入变量。用对偶单纯形法计算， 当t大于5时，最优解为： X= (10+2t, 15+t, 0, 0, t-5 ) T 目标函数最优值为35+5t。 (4) 解: 先化为标准型，令t=0,用单纯形法计算，得： 当t开始增大，当t大于6时，首先出现 b 2 小于0,当0乞仁6,有最优解： X= (0, 0, 0, 10+t/3, 0, 18-3t, 45-5t ) T 目标函数最优值为150+5t (0^2 6)。 当t大于6时，首先出现 b 2 小于0, X 是换出变量， X 2 是换入变量，使用单 纯形法计算得：t继续增大，当t大于11时， b 3 首先小于零， X 是换出变量， X 3 为换入 变量，对偶单纯形法迭代得： 当t< 59,有最优解： X= (0, t/3-2, t/8-11/8, 59/4-t/4, 0, 0, 0 ) T 目标函数最优值为 5t/2+345/2 , (11 试题： 1. (2006年西北工业大学)已知线性规划： max z = 3x ! 2x 2 —为 +2x 2 兰 4 3 洛 +2x 2 兰 12 st { | X 1 - X 2 — 3 X i , X 2 _ o （1） 用单纯形法求解该线性规划问题的最优解和最优值； （2） 写出线性规划的对偶问题； （3） 求解对偶问题的最优解和最优值。 解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。 解题过程：X二 18 3 32 IL5 5 5 0 0 maxz =12，有无穷多解。 对偶问题为： min w = 4y 1 12y 2 3y 3 -力 3y 2 y 3 一 3 st 2y 1 2y 2 -y 3 -2 .%”2”3- 0 Y - 0 1 0. * F w = z =12 T * * 2. （2005年东南大学）写出如下线性规划问题的对偶问题: max z = x 「 2x 2 x 3 st 花一 X 2 于 X 3 = 1 2 x 1 - x 2 x 3 _ 2 人一 0, X 2 岂 0 无限制 并利用弱对偶性说明 z 的最大值不大于1 解题过程：原问题的对偶问题为： min w = 2y 1 y 2 2y 3 Y 1 + Y 2 + 2y^1 4」 l-y ％ ^y - y 2 5 ^ya =1 兰 2 s.t 5 % _0,y 3 gy 2 由于（0，1, 0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的 可行解 X 都有 C X— Yb 任一 而 Yb = b 1 O] 1 =1 ，所以 z 的最大值不大于1。 第三章（86页） 3.1判断表中给出的调运方案能否作为用表上作业法求解时的最初解？为 什么？ 表3 — 1 1 2 3 4 销地 产量 1 2 3 销量 0 15 15 10 15 25 5 5 5 表3—2 1 2 15 3 15 4 10 5 产量 销 地 产 地、 1 150 2 3 4 90 5 销量 240 解： 250 200 300 250 400 500 50 300 300 100 210 410 550 80 330 20 70 表3— 1 中,有5个数字格，作为初始解，应该有m+n-1=3+4-1=6个数字格, 所以表 3-1的调运方案不能作为用表上作业法求解时的初始解。 表3-2中，有10个数字格，而作为初始解，应该有 m+n-1=9个数字格，所 以表3-2 的调运方案不能作为表上作业法的初始解。 3.2 表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表， 伏格尔法直接给出近似最优解 表3-3 销地 3 产量 1 2 产地 5 2 3 9 1 4 6 10 8 1 7 11 12 14 4 试用 1 2 3 销量 表3-4 1 销 地、 产地 '、、 1 2 3 4 销量 2 3 4 5 产量 10 5 15 20 20 2 「 20 5 15 20 3 15 14 13 30 15 2 7 M 10 9 4 15 8 25 25 30 20 30 解： (1)在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额, 填入该表的最 右列和最下列。得到： 1 2 3 行差额 、、销地 产地 4 1 8 2 2 1 1 3 3 6 [7 3 列差额 3 1 6 从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最小元素， 上表 中，第三列是最大差额列，此列中最小元素为 1,由此可以确定产地2的产 品应先供 应给销售地3,得到下表： 1 4 1 [ 5 销地 1 2 3 产量 产地 1 ] 2 3 n 销量 9 10 同时将运价表第三列数字划去，得 、^销地 1 2 11 12 14 4 11 产量 产地 1 12 2 4 14 3 6 4 | 9 10 对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入 该表的最右 列重复上面的步骤，直到求出初始解，最终结果是： 和最下列， 1 2 3 销量 5 代、销地 产地 1 [ 2 3 销量 1 2 3 产量 2 3 4 9 10 11 12 14 4 10 11 （2） 3-4分别计算出各行和各列的次最小运费和最小运费的差额，填入该 表的最右 列和最下列。从行差额或者列差额中找出最大的， 选择它所在的行或者 列中的最小 元素。（方法同3-3相同） 最终得出原问题的初始解: 2 3 4 5 销地 1 产量 产地 1 2 3 4 销量 20 25 30 20 30 30 25 20 20 10 3.3用表上作业法求给出运输问题的最优解（M是任意大正数） (1) 甲 乙 丙 丁 、销地 产地 产量 1 2 3 销量 解： 3 2 4 3 7 4 3 3 6 3 8 2 2 I' 2 5 2 3 （1） CD计算出各行和各列的次最小运费和最小运费的差额， 填入该表的最 右列和最下列。 ②从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最 小 元素，丙列中的最小元素为3,由此可以确定产地2的产品应先供应丙的需要， 而产地 2的产量等于丙地的销量，故在（2,丙）处填入0,同时将运价表中的 丙列和第二行的数字划去，得到: 、、销地 甲 乙 丙 丁 产地 产量 1 3 7 4 5 2 3 销量 2 O 对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额, 4 3 3 3 2 3 填入该标的最右列和最下行，重复步骤 O 1②，直到求出初始解为止。得到下表: 销地 产地 1 2 3 销量 甲 乙 丙 丁 产量 x 3 2 A 0 5 2 3 0 3 3 3 2 2 u i (i=1 , 使用位势法进行检验： &上表中，数字格处填入单位运价并增加一行一列，在列中填入 ii 2, 3)，在行中填入 V j (j=1，2, 3, 4)，先令 U + V = q (i，j^B，B 为基，下 同)来确定 U 和 V ，得到下表: 销地 甲 乙 ii 丙 丁 U i 产地 1 2 3 v i '、、、 3 4 3 0 -2 1 4 3 3 2 i 5 4 ②由r= Cj - ( U + V ) (i，j为非基，下同)计算所有空格的检验数，并在 每个格的右上角 i 填入单位运价，得到下表 销地 甲 产地 1 2 3 乙 丙 丁 U i 、. 0 1 0 3 5 2 4 0 7 1 4 4 3 2 0 6 3 4 0 0 2 5 0 0 -2 8 1 V i 3 2 5 4 由上表可以看出，所有的非基变量检验数》 0, 此 尤问题达到最优解。 又因为二 34 =0，此问题有无穷多最优解 总运费 min z=3*3+3*3+2*3+2*4=32 (2) 、、销地 产地 1 2 3 销量 甲 乙 丙 丁 产量 '、 10 16 5 5 6 10 4 2 7 5 10 4 M2 9 [10 6 4 9 4 解：(2 )(5 计算出各行和各列的次最小运费和最小运费的差额，填入该表 的最 右列和最下列。 ②从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最 小 元素，甲列是最大差额列，甲列的最小元素是 5,所以产地3的产品先供应甲 的需 求，同时将运价表中产地3所在行的数字划去。 5 对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入该标的最右列和最下行，重复步骤 O 1②，直到求出初始解为止。得到下表: 、、销地 甲 乙 丙 丁 产量 产地 1 2 3 销量 1 2 1 3 4 6 4 5 2 使用位势法进行检验： 9 4 4 6 &上表中，数字格处填入单位运价，并增加一行一列，在列中填入 U i (i=1， 2, 3)，在行中填入 V j (j=1，2, 3, 4)，先令 5=0，由 U + V = C j (i，产 B, B 为基， ii 下同)来确定 U 和 V . ii 5 由 Fj = Cj - ( U + V ) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入 ii 单位运价，得到下表 肖地 产地 1 2 3 、、 甲 乙 丙 丁 U i 0 8 0 10 16 5 3 6 6 10 4 8 7 7 1 5 0 10 0 4 11 12 0 9 -2 -5 6 10 V i 10 由上表可以看出，所有的非基变量检验数》 0,此问题达到最优解 此问题有唯一最优解。 总运费min z=118 (3) 甲 乙 丙 丁 戊 产量 销地 产地、 1 2 3 4 销量 10 2 1 8 4 20 10 20 6 4 5 8 7 3 6 9 30 10 7 2 10 6 4 5 4 5 ； 6 2 解：（3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售 地 己，令单位运价为0。销量为2。这样就达到了产销平衡。 用伏格尔法求初始解： CD 计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 和 最下列。 C 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 素， 产地1所在的行是最大差额行，最小元素 0,说以一产地的产品应该优先供 应己的需 要，同时划掉己列的数字。 ③对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入该标的 最右列和最下行，重复步骤 O 1②，直到求出初始解为止。得到下表: 甲 乙 丙 丁 戊 己 产量 销地 产地、、 1 3 2 5 4 2 2 6 3 2 2 4 4 3 2 9 销量 4 4 6 2 4 2 使用位势法进行检验： C 上表中，数字格处填入单位运价，并增加一行一列，在列中填入 u i （i=1， 2, 3, 4),在行中填入 V j (j=1 , 2, 3, 4, 5, 6),先令 U i =0，由 U + V = C j (i, j ii B, B为基，下同)来确定 U 和 V . ii O 由F= Cj - ( U + V ) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入 ii 单位运价。 由上表可以看出，所有的非基变量检验数》 0,此问题达到最优解。 又因为二 14 =0，此问题有无穷多最优解。 总运费min z=90 (4) 甲 乙 、、销地 产地 1 2 3 4 5 丙 29 丁 13 14 3 18 30 60 戊 产量 10 13 18 M 22 16 100 120 M 140 19 34 21 11 23 36 100 0 9 24 100 120 6 11 28 80 60 销量 80 解：(4)此问题是一个产销不平衡的问题，产大于销。增加一个假象销售 地己， 令单位运价为0。销量为40。这样就达到了产销平衡。 用伏格尔法求初始解： O 计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 和最 下行。 O 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 素， 同时划掉所在列或行的元素。 ③对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入 该标的最右列和最下行，重复步骤 O 1②，直到求出初始解为止。 并用位势法进行检验: 乙 己 甲 丙 丁 戊 销地 产 U i 地、 29 13 1 10 18 22 0 0 2 8 0 6 12 13 M 14 2 21 16 0 0 3 M-16 0 1 0 12 3 3 M -10 6 11 0 0 0 4 4 5 2 v i 0 9 0 24 0 16 11 28 0 23 7 36 3 21 0 10 5 13 18 30 M-6 19 8 34 6 16 22 17 0 -12 0 -5 12 10 由上表可以看出，所有的非基变量检验数》 0,此问题达到最优解 又因为二 31 =0，此问题有无穷多最优解。 总运费min z=5520 3.4 已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示 表1 产量 销 地 B 1 B 2 B 3 B 4 产地 A A A 3 5 10 15 25 0 10 15 5 5 15 B 1 10 B 2 1 7 14 C22 销量 表2 产地 5 销地 15 B 3 20 9 16 10 B 4 11 20 18 A A 12 2 22 A （1）A 到B的单位运价在什么范围变化时，上述最优方案不变? （2） A到B的单位运价变为何值时，有无穷多最优方案。除表 24 1中方案 外，至少写出其他两个。 解： （1） CD在对应表的数字格处（ C 22 未知）填入单位运价，并增加一行，在列中 填入 U i （i=1，2，3），在行中填入 V j （j=1，2，3，4），先令 U i =0，由 U + V = C ij ii (i, j B)来确定 U 和 V . ii O 由F= Cj - ( U + V ) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入 ii 单位运价( c 22 未知)。 最优调运方案不变，则所有非基变量的检验数都是非负。所以： C 22 -3 — 0 c 22 +10-0 10- C 22 - 0 24- C 22 - 0 18- Q 2 一 0 解得 ： 3 - C 22 - 10 单位运价在此区间变化时，最优调运方案不变。 (2 )0 在对应表的数字格处( C 22 未知)填入单位运价，并增加一行，在 列中填入 U i (i=1 , 2, 3)，在行中填入 V j (j=1，2, 3, 4)，先令 5 =0，由 U + V = q ii (i，j ， B)来确定 U 和 V . ii O 由F= Cj - ( U + V ) (i， j・ N )计算所有空格的检验数，并在每个格的右 上角填 ii 入单位运价( C 22 未知)。 有无穷多最优方案，则至少有一个非基变量的检验数为 0. 取5-17=0,所以单价变为17时，该问题 有无穷多最优调运方案。 另外的两种调运方案： 销地 产地 B 1 B 2 B 3 B 4 产量 A 15 0 0 15 10 15 25 A 2 A 3 5 5 5 10 销量 15 15 、、销地 产地 B 1 B 2 B a B 4 产量 A A 2 A 3 15 15 25 5 0 5 5 0 15 10 销量 15 15 10 3.5 某百货公司去外地采购 ABCD四种规格的服装，数量分别为： A,1500套; B, 2000套；C，3000套；D，3500套；有三个城市可以供应上述服装，分别为: I，2500套，II，2500套；III，5000套。已知下表，求预期盈利最大的采购方 案。 A B C D I 10 5 6 7 II 8 2 7 6 9 3 4 8 III 解： 因为利润表中的最大利润是10，所以令M=10，用M减去利润表上的数字, 此问题变 成一个运输问题，见下表： A B D 销地 C 产量 产地 、、 I II III 销量 0 5 2 8 1 7 1500 2000 使用伏格尔法计算初始解： 4 3 6 3000 A 4 2500 2500 5000 3500 CD 计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 和最下行。 C 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 素， 同时划掉所在列或行的元素。 C 对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入 该标的最右列和最下行，重复步骤 O 1②，直到求出初始解为止。 销地 产地 A B C D 产量 I II III 销量 1500 500 500 2500 3000 1500 使用位势法检验： 1500 2000 [3500 3500 2500 2500 5000 ①数字格处填入单位运价，并增加一行一列，在列中填入 ii u i （i=1 , 2, 3）, i 在行中填入 V j （j=1，2，3, 4），先令 u i =0，由 U + V = q （i，产B,）来确定 U 和 V . i ②由F= Cj -（ U + V ） （i，j ・ N ）计算所有空格的检验数，并在每个格的右 ii 上角填入单位运价。 如果没有得到最优解，用逼回路法进行改进 盈利最大方案： A B C D 、、销地 产 地 I 、、 II 3 III 0 V i U i 0 2 5 0 8 4 0 7 1 5 1 4 0 4 2 3 4 6 1 3 4 2 0 -1 1 1 0 此时，总运费为28000元;最大盈利为72000元。 3.6甲乙丙三个城市每年需要煤炭分别为： 320万吨、250万吨、350万吨, 由A、B两处煤矿供应。煤炭供应量分别为：A,400万吨；B,450万吨；运价如下 表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少 0~30万吨，乙 城市需要完全供应，丙城市供应不少于270万吨。试求将供应量分配完又使总运 费最 低的调运方案。 甲 乙 丙 A B 15 21 18 25 22 16 解: 此问题的供应量小于需求量，假设供应地 C,产量为70万吨。 用伏格尔法求解 得： 甲 甲‘ 乙 丙 丙‘ 供应 、销地 产 地、 A 150 250 400 B 140 30 270 10 450 C 70 70 需求 290 30 250 270 80 使用位势法检验: CD 数字格处填入单位运价，并增加一行一列，在列中填入 U i (i=1 , 2, 3), 在行中填入 V j (j=1 , 2, 3, 4),先令 U i =0,由 U + V = q (i,产B,)来确定 U 和 V . iii i C 由 Gj = Cj - ( U + V ) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入 ii 单位运价。 如果没有得到最优解，用闭回路法进行改进。 最优解时，最小运费是14650万元。 3.7某造船厂根据合同要从当年起连续三年末各提供三条规格型号相同的 大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下 表， 正常生产时间内 加班生产时间内 正常生产时的 每艘 年度 可完成的客货轮 可完成的客货轮 成本/万元 数 数 1 2 2 4 3 2 500 600 3 1 3 550 已知加班生产时，每艘客货轮的成本比正常生产高出 70万元，又知道造出 来的可货 轮如当年不交货，每艘积压一年造成积压损失 40万元，在签合同时， 该厂已经存储了 2艘客货轮，而该厂希望在第三年木完成合同后还能存储一艘备 用，问该厂如何安排每年的生产量，能够在满足上述要求的情况下，总的生产费 用加 积压损失最少？ 解： 设 A l , A , A 是三年的需求订货， B i , B 2 , B 3 是三年的正常生产能力；区, B 2 , B 3 是三年的加班能力，S是事先积压产生的供货能力。第三年的需求量是 4 艘。此问题产销不平衡，增加设想销地 A 4 ，运价0,销量7. 使用伏格尔法求初始解： 并用位势法检验： 此问题有无穷多最优解， 总运费 min z=4730万元 销地 产 地' Bi B ； 供应量 A i A 2 A 3 A 500 540 0 0 600 60 60 60 -10 B 2 B 2 0 0 B 3 550 620 B 3 0 60 -460 40 500 540 试题：（2001年上海大学 ） S 需求量 560 -60 某产品由产地A i 发往销地B j 的每吨运费如下表: 元/吨 B i B 2 A i 50 40 150 A 2 45 30 200 A 3 20 10 250 需求量 150 220 为满足各销地需求，应如何确定运输方案使总费用最小? （1） 建立此运输问题的数学模型。 （2） 将此问题化为产销平衡的运输问题，并求出一个初始基本可行解。 B 3 60 65 50 180 供应量（吨） 解：（1）设 X j 某产品为从A i 发往销地B j 的吨数，贝吐匕运输问题的数学模型为: max z =50x“ 40x 12 60x 13 - 245x 21 30x 22 65x 23 20x 31 10x 32 - 50x 33 X 1 1 ' x 12 ' x 13 = 150 ' x 23 x 31 x x ' 22 21 二 ' x 32 ' x 33 200 -250 =150 = 220 -180 st ^x 11 X 12 x 13 ' x 21 'X 22 ' X 23 X 31 ' X 32 ' X 33 -0 , i , j =1 ,2,3 、 X j (2)增加一个虚拟销地B 4 ,其需求量为50吨，各产地到虚拟销地B 4 的每吨运 费分 别为0,贝冋将此问题化为如下产销平衡的运输问题： 元/吨 A 1 A 2 B 1 50 45 B 2 40 30 B 3 60 65 r 0 B 4 0 0 供应量 150 200 250 A 3 20 10 50 需求量 150 220 180 由最小元素法可得到如下的一个初始基本可行解: 50 元/吨 B 1 B 2 A 1 A 2 A 3 需求量 120 30 150 B 3 100 80 B 4 50 供应量 150 200 250 220 220 180 50 第四章(98页) 4.1若用以下表达式作为目标规划的目标函数，试述其逻辑是否正确? (1) max= djd 1 (2) max z= df - d 1 (3) min z= d + d (4) + min z= d - d 解: (1)不正确 (2) 正确 .—.+ 1 1 ， - ， (3) 正确 (4) 正确 4.2 试用图解法找出以下目标函数的满意解; (1) min z= p (小厂+小广)+ P 2 (2d^+d^) s.t. X 1 -10 X 2 + d i-- d i =50 3 x 1 +5 x 2 + df- d 2 =20 8 x 1 +6 X 2 + d 3 ： d 3 =100 X i , X 2 , dj d 1 , d 2 , d ?— , d 3_ , d 3 一0 (2) min z= R ( d^+ d/ ) + P 2 d/+ P 3 d 2 _ + P 4 ( d 3 _ +1.5 d 4^ s.t. X - I + x 2 + d 1 ： d 1 =40 X - I + x 2 + d 2 - d 2 "=100 X + d 3 - d 3 =30 _ X 2 + d 4 - d 4 =15 X i , X 2 , d i_ , d i , d 2 , d 2_ , d 3_ , d 3 , d 「, d 4 _0 (3) min z= R ( d 「+ d i ) + R, df + P 3 d 3 s.t. X - I + X 2 + d 1 _ - d 1 =10 3 X 1 +4 X 2 + d 2- d 2 =50 8 X 1 +10 X 2 + dr - d 3 =300 X i , X 2 , d 「， d i , d 2 , d 2_ , d 3_ , d 3 —0 解 (1) 满意解是：(50, 0) (2) 满意解是：(25, 15) (3) 满意解是：(10, 0) 4.3使用单纯形法求解下列目标规划问题。 (1) min z= R d^ + F 2 d^ + P 3 (5 d^ +3 df ) + P 4 d/ s.t. X - I + x 2 + d 1 ： d 1 =80 X 1 + x 2 + d 2 _ - d 2 =90 X i +小 3 -小 3 =70 X 2 + dr - d 4 =45 X i , X 2 , d i_ , d i , d 2 , d ?— , d 3_ , d 3 ,d<^, d ； _0 (2) min z= P d^ + P d2~ + P 2 dr s.t. X i +2 x ? + d i - d i =10 10论 +12 x 2 + d 2 - - d 2 =62.4 x i +2 x 2 _8 X i , X 2 , de d i , d 2 , d 2 一 -0 (3) min z= R ( dr + d^ ) + F 2 d 3 _ s.t. X i + X 2 + d i - d i =i 2 X 1 +2 X 2 + d 2 二 d 2 =4 6 x i -4 x 2 + d 3 二 d 3 =50 X i , X 2 , d 「， d i , d 2 , d^ , dr, d； _0 解： (1)把原问题转化为： Min z= R d 2 + R d 2 _ + P 2 d 「 S.T. X +2 x 2 + d 1 _ - d 1 =10 10 x i +12 x 2 + d2" - d 2 =62.4 2 x i + x 2 + x 3 =8 X i , X 2 , X 3 , d i" , d i , d 2 , df- 0 x 3 是松弛变量 单纯形法计算得： C j 0 b X i 0 X 2 0 X 3 R 2 0 dj R dr R 2 q C B X B dr d 丈 F 2 P d i_ d 厂 X 3 10 62.4 1 10 2 -10 【2】 0 0 1 0 0 代 1 0 0 0 0 -1 0 0 0 1 0 1 0 0 0 0 -1 0 5 5.2 12 1 -12 0 P F 2 8 8 2 -1 -2 0 … 迭 原问题最优解 x 1 =0, X 2 =5.2 , 非基变量的的检验数是0,所以有多重解； 继续迭代得到： X 1 =0.6, X 2 =4.7也是满意解 （2） 使用单纯形法计算： X 1 =70, X 2 =20 （3）满意解是 X - I =1, X 2 =0 4.4有以下目标规划问题 min z= Rd i~ + F 2 + P 3 （ 5 d^ +3 df ） + P 3 （ 5 d ； +3 d 2 ） s.t. X - I + x 2 + d 1 _ - d 1 =80 X + d 2 _ - d 2 =70 X 2 + d 3 - d 3 =45 d i + d 4 - d 4 =10 _ X i , X 2 , d i - d i , d 2 , d 2" d 3 - d 3 , d 4~ , d 4— 0 （1） 用单纯形法求解 （2） 若目标函数变成 min z= p d 「+ P 3 d 4 + P 2 （5d=+3 df）+ P 2 （5 d 3 +3 d 2 ）, 问原问题的解有什么变化？ （3） 若第一个目标约束的右端改为120,原满意解有何变化？ 解： (1) 单纯形法计算得到: 人=70, X 2 =45是满意解 b列出现负数， d i ■行的系数乘以-1,重新迭代，人=75, X 2 =45是满意解； (2)实际上是对优先因子 0 P 2 , P 3 进行调换，最优解不变 (3) .ib—Brb 二 1 1 0 4.5某工厂生产两种产品，产品I每件获利10元，产品II每件获利8元。每生产 1件 产品I需要3小时，生产产品II需要2.5小时，每周的有效时间120小时， 若加班生 产，产品I每件利润少1.5元，每件产品II利润少1元，决策者希望在 允许的时间和 加班时间获取最大利润， 试建立该问题的目标规划模型，并求解？ 解：条件不足，无法建立模型。 4.6某商标的酒是用三种等级的酒兑制而成。已知道三种酒的供应量和单位成本 如下表； 设该种牌号酒有三种商标(红黄蓝)，各种商标的酒对原料酒的混合比及售价见 下表， 决策者规定：首先必须严格按规定比例兑制各种商标的酒， 其次获利最大； 再次，红商标的酒每天至少生产 2000kg，列出数学模型。 解： 设 X i1 ， X 2 ， X i3 (i=1，2, 3)表示第i种等级的兑制红黄蓝三种商标的酒的数量， 数学模型： Max z= R ( d 1~ + d 2 + d r+ d?+ d 5+ d^)+ P 2 + + P 3 d ； s.t. X 31 -0.1 ( X 11 + X 21 + X 31 ) + 1 - 1 =0 dd x 11 -0.5( x 11 + x 21 + x 31 ) + d/ - d 2 =0 X 32 -0.7 ( X 12 + X 22 + X 32 ) + d 3 - d 3 =0 x 12 -0.2 ( x 12 + x 22 + x 32 ) + d/ - d 4 =0 X 33 -0.5( X 13 + X 23 + X 33 )+ dT - d 5 =0 X 13 -0.1 ( X 13 + X 23 + X 33 )+ d 6 ： d 6 =0 x 11 + x 21 + x 31 + d 7 ^ d 7 =2000 X j -0 (i=1,2,3;j=1,2,3) 其中, z=5.5( X 〔 i + X ?i + X 31 )+5( X |2 + X 22 + X 32 )+4.8 X l3 + X 23 + X 33 ) -6( X n + X 12 + X 13 )-4.5( X 21 + X 22 + X 23 ) -3( X 31 + X 32 + X 33 )+ dL 试题： 1.某生产基地每天需从 A、B两仓库中提取原材料用于生产，需提取的原材料 有：原 材料甲不少于240件，原材料乙不少于80公斤，原材料丙不少于120 吨。已知： 从A仓库每部货车能运回生产基地甲4件，乙2公斤，丙6吨， 运费200元/ 部；从B仓库每部货车每天能运回生产基地甲 7件，乙2公斤， 丙2吨，运费 160元/部，问：为满足生产需要，生产基地每天应发往 A、B 两仓库多少部货车，并使总运费最少？ 解题过程：根据题意列出下表: 单位 运量 原 材 甲 （件） 乙 （公斤） 丙 （吨） 运费 （元 / 部） A B 需求量 4 7 240 2 2 80 6 2 200 160 120 设每天发往A，B两仓库的货车数分别为N ， X 2 部，则有 min z = 200% 160 X 2 「4% 十7屜 A 240 2% +2% 兰80 st < . 6 X 1 2 X 2 -120 [X 1 , X 2 >且 为整数 ① ② ③ ⑤ ④ 先不考虑整数约束，用图解法（如上图），得最优解为x； =10,x； =30，恰 好是整数解。故x* =（10,30）就是原问题的最优整数解，且 z * =6800 。 故生产基地每天发往A仓库10部车，发往B仓库30部车，可使总运费最 少为 6800元。 第五章答案 5.1对下列整数规划问题，问：用先解相应的线性规划，然后凑整的办法，能否 求到 最优整数解？ （1） max Z =3 X ； +2 X 2 s.t. 2 x 1 +3 x 2 乞 14.5 4捲 + x 2 三16.5 论 ， x 2 _ 0 x 1 , x 2 是整数 （1）解：将上述问题化为: Max Z =3 x 1 +2 x 2 +0 x 3 +0 x 4 s.t. 2 x 1 +3 X 2 + x 3 =14.5 4 x 1 + x 2 + x 4 =16.5 X i , X 2 , X 3 , X 4 _0 % , x 2 N 用单纯形法求解: C j C B 3 b 29/2 33/2 0 2 X 2 0 X 3 0 X 4 q X B X 3 X 4 X 1 0 0 2 【4】 3 3 1 0 0 T 0 1 29/4 33/8 1 2 -z (迭代过程略) 0 相应的线性规划问题最优解是 X = (7/2,5/2,0,0 ),目标函数的最优值z=31/2 凑整数 时， X i = (4,3,0,0 ， 是非可行解； T X 2 = (4,2,0,0 ，是非可行解； T X 3 = (3,3,0,0 ) ，是非可行解； X 4 = (3,2,0,0 T ，是可行解，z=13; 使用分支定界法解整数规划问题。 令 z =31/2， x 1 = x 2 =0是可行解。 所以 z =0，0乞 z * <31/2 把原问题分解为两个问题： (I) s.t. 2 x 1 +3 x 2 -14.5 4 x 1 + x 2 -16.5 0 一 捲—3; x 2 -0 (II) s.t. max z 2 =3 x 1 +2 x 2 max z 1 =3 x 1 +2 x 2 2 x 1 +3 X 2 _ 14.5 4 X 1 + X 2 _16.5 4 _ X 1 ; X 2 _0 将上述问题化为标准型，使用单纯形法求解： 为=3, X 2 =2是最优整数解，z=13. (2) max Z =3 X I +2 X 2 s.t. 2 X i +3 X 2 _ 14 2捲 + X 2 -9 论 ， X 2 _ 0 x 1 , X 2 是整数 (2)解： 使用图解法或者单纯形法求解此问题，线性规划问题最优解是( 目标函数最优值max z=59/4; 凑整数时， X I = (3,2) T ,是可行解，z=13; X 2 = (3,3) T ，是非可行解； X 3 = (4,2) T ，是非可行解; X 4 = (4,3) T ，是非可行解； 使用分支定界法求解原整数规划问题，令 令 z =59/4， X 1 = X 2 =0是可行解。 所以 z =0，z * <59/4； 把原问题分解为两个问题： (a)max z 1 =3 X 1 +2 X 2 s.t. 2 X 1 +3 X ^ 14 2 X 1 + X ^ 9 0込捲込3; x 2 _0 (b) max z 2 =3 x 1 +2 x 2 s.t. ，5/2)13/4 2 x 1 +3 x 2 冬 14 2 x 1 + x^ 9 4乞 X i ； X 2 -0 解得：最优整数解是 x 1 =4, x 2 =1; 目标函数是14. 5.2用分支定界法解： Max z= x 1 + x 2 s.t. 2 x 1 +9 x 2 /14 <51/14 -2 x 1 + x 2 咗 1/3 x- i , x 2 -0 x 1 x 2 都是整数 图解法解得：最优解是 B点(51/46+7/69-1/6, 51/23+14/69) 目标函数最优值为： 58/23+51/46-1/6 使用分支定界法求解， 令 z =58/23+51/46-1/6, x 1 = x 2 =0 是可行解; 因此 z=0,故 0 乞 58/23+51/46-1/6 将原问题分解为下列问题： (I) Max z 1 = x 1 + x 2 s.t. 2 x 1 +9 x 2 /14 <51/14 -2 x 1 + x 2 冬 1/3 x 2 -1 x- i ， x 2 -0 (I) Max z- i = x 1 + x 2 s.t. 2 x 1 +9 x 2 /14 <51/14 -2 x 1 + x 2 <1/3 x 2 亠2 X 1 , X 2 -0 按照以上步骤， 求解最终得到：最优解是（1, 2） 目标函数最优值z=3 5.3用Gomory切割法解如下问题： （1）max z= x 1 + x 2 s.t. 2捲 + x 2 乞6 4 x 1 +5 x 2 乞 20 论 ， x 2 _ 0 X 1 , X 2 是整数 解： 将上述问题化成标准型： max z= x 1 + x 2 +0 x 3 +0 x 4 s.t. 2 x 1 + x 2 + x 3 =6 4 x 1 +5 x 2 + x 4 =20 人 k， X 3 ， x 4 -0 X 1 , X 2 ， X 3 ， X 4 是整数 单纯形法求得最优解是：X * = 5/3,8/3,0,0，目标函数最优值13/3 T 变量之间的关系： x- i +5 x 3 /6- x 4 /6=5/3 x 2 -2 X 3 /3+ x 4 /3=8/3 把系数和常数项都分解成为整数和非负真分数 之和； 所以有： 2/3-5 x 3 /6-5 x 4 /61^0 2/3- （ x 3 + x 4 ） /3 <0 T 加入松弛变量 X 5 ，继续迭代得到最终结果：X = 0,4,2,0,0 ，目标函数最优值 4 解得：最优整数解是 x 1 =0， x 2 =4； 目标函数是4. （3） max z=3 捲- X 2 s.t. 3 x- i -2 x 2 _3 -5 x -4 x 2 冬-10 2 x 1 + x^ 5 x- i , x 2 亠 0 X i , X 2 是整数 解： 将原问题化成标准型，并使用单纯形法求解： T 最优解为X = （13/7,9/7,0,31/7,0），目标函数最优值30/7 从单纯形表可以得到变量间的关系，把系数和常数项都分解成整数和非负分数之 和，可以得知： 6/7-（ x 3 /7+2 x 5 /7）岂 0 加入松弛变量 X 7 ，把新的约束条件加入后，继续迭代，得到最终的结果： 最优解是为=1， x 2 =2 目标函数最优值1. 5.4某城市的消防总部将全市划分为11个防火区，设有四个防火站，如图所示 （ 课 本 P114）,其中①②③④是四个消防站，1, 2，…11是防火区域，根据历史资料 证实， 各个消防站可在事先规定的允许时间内对所有负责的地区的火灾予以消 灭，虚线表示 各地区是哪个消防站负责， 现在总部提出：是否可以减少消防站的 数目，仍能够负责各个地区的防火任务，如果可以，关闭哪个？ 提示：对每个消防站 定义一个0-1变量 x i ，令 1代表当某个防火区域由第i个消防站负责，0代表不是它负责。然后对每个防 火区域 列出约束条件； 解： 0 1代表当某个防火区域由第i个消防站负责，0代表不是它负责；i=1，2, 3, 4 建立数 学模型： Min z= ' x S.t. X | + x^-1 X , _1 x 1 + x 3 _1 X 3 -1 x 1 + x 3 + x^ -1 x 1 + x 4 丄 1 x 1 + x 2 + x^ -1 x 2 + x 4 -1 X 4 -1 x 3 + x 4 -1 有以上约束条件可以解得： X 1 = X 3 = & =1 继续求解 当 X 2 =0时，是可行解，目标函数是 3； 当 x 2 =1时，是可行解，目标函数是 4； * T X = 1,0,1,1 ，目标函数最优值是3. 比较可以得到，最优解是 所以，可以关闭消防站②。 5.5在有相互排斥的约束条件的问题中， 如果约束条件时乞型的，我们加 y i M ( y i 是 0-1变量，M是很大的常数)的方法统一在一个问题中。如果是 一型的，我们 将如何 利用 y i 和M呢？ 解：在m个约束条件右端分别减去 y i M( y i 是0-1变量，M是很大的常数，i=1， 2…m) m 并且 7 y i =m -1 i 4 5.6解0-1规划： (1) max z=4 x 1 +3 x 2 +2 x 3 s.t. 2x- i -5 x 2 +3 x 3 乞 4 4 捲 + x 2 +3 x 5 _ 3 x 2 + x 3 -1 论 ， X 2 , X 3 =0 或 1 解： 将(0, 0, 0) (0, 0, 1) (0, 1, 0) (1, 0, 0) (0, 1, 1) (1, 0，1) (1, 1, 0) (1,1,1)分别带入到约束条件中，可以得到：原问题的最优解是(0, 0, 1), 目标函 数最优值2. (2) min z=2 x 1 +5 x 2 +3 x 3 +4 x 4 s.t. -4 x- i + x 2 + x 3 + x 4 亠0 -2 x- i +4 x 2 +2 x 3 + x 4 -4 x- i + x 2 - x 3 + x^ - 1 % , X 2 , X 3 , X 4 =0 或 1 解： T X = 0,1,0,0 是一个可行解，目标函数数值是 4; 所以可以增加约束条件： 2 x 1 +5 x 2 +3 x 3 +4 沧込4 把可能的解(0, 0, 0, 0) (0, 0, 0, 1) - (1, 1, 1, 1)分别带入约束条件 的问题 中，得到最优解X * = 0,1,0,0 ，目标函数最优值4. T 5.7有四个工人，指派他们完成4种工作，每人做各种工作所消耗的时间如下表， 问 指派哪个人去完成哪种工作，可以使得总耗时最小？ A B C D 任务 人员 甲 乙 丙 丁 15 19 18 23 17 21 21 22 16 23 24 18 19 17 26 19 解：系数矩阵C为： 15 18 21 24 19 23 22 26 17 26 18 19 J9 21 23 17 一 ① 系数矩阵的每行元素减去该行的最小元素得矩阵 B ② B矩阵的每列元素减去该列的最小元素得到矩阵 A 此时，细数矩阵的每行每列都有元素 0. 先给 an 加圈，然后给 a 24 加圈，划掉 a 44 。给 a 32 加圈，划掉 a gs 得： 0 2 6 14 4 10 0 0 .2 3 6 9 0 3 0 一 此时，画圈的数目是3,少于4个，所以指派不成功，进入下一步， 给第四行打"号，给第四列打"号，给第二行打"号，将第一，第三行画一横线, 将第四 列画纵线，变换矩阵得到 0 2 6 10 0 3 3 10 0 0 J 2 5 0 4 0 一 给第一，第四列打 V 号，对第一，第二，第四行打 V 号，给第一，第四列画一纵 线，第三行画一横线，变换矩阵得到 甲乙丙丁 0 0 4 10 0 111 12 0 0 6 J 0 3 0 一 得到最优指派方案为： 甲一B;乙一A;丙一C; 丁一D 。 所消耗的总时间是 70.