运筹学习题答案注释(第2章).doc

运筹学习题答案及注释
2.3 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-32所示，求表中各括弧内未知数的值。
cj
3
2
2
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
0
x4
（b）
1
1
1
1
0
0
0
x5
15
（a）
1
2
0
1
0
0
x6
20
2
（c）
1
0
0
1
cj- zj
3
2
2
0
0
0

0
x4
5/4
0
0
(d)
(l)
-1/4
-1/4
3
x1
25/4
1
0
(e)
0
3/4
(i)
2
x2
5/2
0
1
(f)
0
(h)
1/2
cj- zj
0
(k)
(g)
0
-5/4
(j)
解：最后结果如下：
cj
3
2
2
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
0
x4
（10）
1
1
1
1
0
0
0
x5
15
（2）
1
2
0
1
0
0
x6
20
2
（3）
1
0
0
1
cj- zj
3
2
2
0
0
0

0
x4
5/4
0
0
(1/4)
(1)
-1/4
-1/4
3
x1
25/4
1
0
(5/4)
0
3/4
(-1/4)
2
x2
5/2
0
1
(-1/2)
0
(-1/2)
1/2
cj- zj
0
(0)
(-3/4)
0
-5/4
(-1/4)
注释：由题中初始单纯形表及、最终单纯形表，我们可以看出：在初始单纯形表中，先选x1进基，选x5出基，做变换；然后再选x2进基，选x6出基，做变换，则得到最终单纯形表。
2.7 给出线性规划问题。
max
st.
要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=（2，2，4，0），试根据对偶理论，直接求出对偶问题的最优解。
解：（1）其对偶问题为：
min
st.
（2）用单纯形法解原问题，将原问题化成标准形式如下：
max
st.
因此，可得如下单纯形表：
cj
2
4
1
1
0
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
x7
x8
0
x5
8
1
3
0
1
1
0
0
0
0
x6
6
2
1
0
0
0
1
0
0
0
x7
6
0
1
1
1
0
0
1
0
0
x8
9
1
1
1
0
0
0
0
1
cj- zj
2
4
1
1
0
0
0
0
因4≥2≥1，所以选x2进基，因8/3≤6≤9，故选x5出基，则得
cj
2
4
1
1
0
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
x7
x8
4
x2
8/3
1/3
1
0
1/3
1/3
0
0
0
0
x6
10/3
5/3
0
0
-1/3
-1/3
1
0
0
0
x7
10/3
-1/3
0
1
2/3
-1/3
0
1
0
0
x8
19/3
2/3
0
1
-1/3
-1/3
0
0
1
cj- zj
2/3
0
1
-1/3
-4/3
0
0
0
因1≥2/3，所以选x3进基，因10/3≤19/3，故选x7出基，则得
cj
2
4
1
1
0
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
x7
x8
4
x2
8/3
1/3
1
0
1/3
1/3
0
0
0
0
x6
10/3
5/3
0
0
-1/3
-1/3
1
0
0
1
x3
10/3
-1/3
0
1
2/3
-1/3
0
1
0
0
x8
3
1
0
0
-1
0
0
-1
1
cj- zj
1
0
0
-1
-1
0
-1
0
因1≥0，所以选x1进基，因（10/3）/（5/3）≤3/1≤（8/3）/（1/3），故选x6出基，则得
cj
2
4
1
1
0
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
x7
x8
4
x2
2
0
1
0
2/5
2/5
-1/5
0
0
2
x1
2
1
0
0
-1/5
-1/5
3/5
0
0
1
x3
4
0
0
1
3/5
-2/5
1/5
1
0
0
x8
1
0
0
0
-4/5
1/5
-3/5
-1
1
cj- zj
0
0
0
-4/5
-4/5
-3/5
-1
0
所以，最优解为：X*=（2，2，4，0，0，0，0，1），代入目标函数得z =16。
其对偶问题得最优解为：X*=（4/5，3/5，1，0，0，0，0，4/5），代入目标函数得w=16。
2.9 用对偶单纯形法求解下列线性规划问题。
（2）min
st.
解：先将问题改写为：
max
st.
约束条件两端乘“－1”得
max
st.
列出单纯行表，并用对偶单纯形法求解步骤进行计算，其过程如下：
cj
-5
-2
-4
0
0
CB
基
b
x1
x2
x3
x4
x5
0
x4
-4
-3
-1
-2
1
0
0
x5
-10
-6
-3
-5
0
1
cj- zj
-5
-2
-4
0
0
因-10≤-4，所以选x5出基，因2/3≤4/5≤5/6，故选x2进基，则得
cj
-5
-2
-4
0
0
CB
基
b
x1
x2
x3
x4
x5
0
x4
-2/3
-1
0
-1/3
1
-1/3
-2
x2
10/3
2
1
5/3
0
-1/3
cj- zj
-1
0
-2/3
0
-2/3
选x4出基，因1≤2，故选x1进基，则得
cj
-5
-2
-4
0
0
CB
基
b
x1
x2
x3
x4
x5
-5
x1
2/3
1
0
1/3
-1
1/3
-2
x2
2
0
1
1
2
-1
cj- zj
0
0
-1/3
-1
-1/3
将最优解代入目标函数，得目标值：min
2.10 考虑如下线性规划问题：
min
st.
要求：（1）写出其对偶问题；（2）用对偶单纯形法求解原问题；（3）用单纯形法求解其对偶问题；(4)对比（2）与（3）中每步计算得到的结果。
解：（1）其对偶问题为：
max
st.
（2）将原问题改写为：
max
st.
约束条件两端乘“－1”得
max
st.
因此，可得如下初始单纯形表：
cj
-60
-40
-80
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
0
x4
-2
-3
-2
-1
1
0
0
0
x5
-4
-4
-1
-3
0
1
0
0
x6
-3
-2
-2
-2
0
0
1
cj- zj
-60
-40
-80
0
0
0
因-4≤-3≤-2，所以选x5出基，因60/4≤80/3≤40，故选x1出基，则得
cj
-60
-40
-80
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
0
x4
1
0
-5/4
5/4
1
-3/4
0
-60
x1
1
1
1/4
3/4
0
-1/4
0
0
x6
-1
0
-3/2
-1/2
0
-1/2
1
cj- zj
0
-25
-35
0
-15
0
因-1≤0，所以选x6出基，因25/（3/2）≤30≤70，故选x2进基，则得
cj
-60
-40
-80
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
0
x4
11/6
0
0
5/3
1
-1/3
-5/6
-60
x1
5/6
1
0
2/3
0
-1/3
1/6
-40
x2
2/3
0
1
1/3
0
1/3
-2/3
cj- zj
0
-25
-80/3
0
-20/3
-50/3
（3）将其对偶问题改为：
max
st.
因此，可得如下初始单纯形表：
cj
2
4
3
0
0
0
CB
基
b
y1
y2
y3
y4
y5
y6
0
y4
60
3
4
2
1
0
0
0
y5
40
2
1
2
0
1
0
0
y6
80
1
3
2
0
0
1
cj- zj
2
4
3
0
0
0
因4≥3≥2，所以选y2进基，因60/4≤80/3≤40，故选y4出基，则得
cj
2
4
3
0
0
0
CB
基
b
y1
y2
y3
y4
y5
y6
4
y2
15
3/4
1
1/2
1/4
0
0
0
y5
25
5/4
0
3/2
-1/4
1
0
0
y6
35
-5/4
0
1/2
-3/4
0
1
cj- zj
-1
0
1
-1
0
0
因1≥0，所以选y3进基，因25/(3/2)≤30≤70，故选y5出基，则得
cj
2
4
3
0
0
0
CB
基
b
y1
y2
y3
y4
y5
y6
4
y2
20/3
1/3
1
0
1/3
-1/3
0
3
y3
50/3
5/6
0
1
-1/6
2/3
0
0
y6
80/3
-5/3
0
0
-2/3
0
1
cj- zj
-11/6
0
0
-5/6
-2/3
0
(4) 对比（2）与（3）中每步计算得到的结果可知：
（2）中cj- zj的相反数就是（3）中解；（2）中的解就是（3）中cj- zj的相反数。
2.11 已知线性规划问题：
max
st.
先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。
（1）目标函数变为 max ；
（2）约束右端项由变为；
（3）增添一个新的约束条件。
解：先将问题改写为：
max
st.
列出单纯形表，并用单纯形法求解步骤进行计算，其过程如下：
cj
2
-1
1
0
0
CB
基
b
x1
x2
x3
x4
x5
0
x4
6
1
1
1
1
0
0
x5
4
-1
2
0
0
1
cj- zj
2
-1
1
0
0
因2≥1≥0，所以选x1进基，因0≤1，故选x4出基，则得
cj
2
-1
1
0
0
CB
基
b
x1
x2
x3
x4
x5
2
x1
6
1
1
1
1
0
0
x5
10
0
3
1
1
1
cj- zj
0
-3
-1
-2
0
得最优解为：（6，0，0），代入目标函数得z = 12。
（1）目标函数变为 max 时，直接反映到最终单纯形表中得：
cj
2
3
1
0
0
CB
基
b
x1
x2
x3
x4
x5
2
x1
6
1
1
1
1
0
0
x5
10
0
3
1
1
1
cj- zj
0
1
-1
-2
0
因x2的检验数1≥0，所以原最优解已经不是新问题的最优解；选x2进基，因10/3≤6/1，故选x5出基，则得
cj
2
3
1
0
0
CB
基
b
x1
x2
x3
x4
x5
2
x1
8/3
1
0
2/3
2/3
-1/3
3
x2
10/3
0
1
1/3
1/3
1/3
cj- zj
0
0
-4/3
-7/3
-1/3
得最优解为：（8/3，10/3，0），代入目标函数得z = 46/3 。
（2）约束右端项由变为时；有＝
=
将上述结果反映到单纯形表中得：
cj
2
-1
1
0
0
CB
基
b
x1
x2
x3
x4
x5
2
x1
3
1
1
1
1
0
0
x5
7
0
3
1
1
1
cj- zj
0
-3
-1
-2
0
此时，上表中的解仍为可行解，故最优解为：（3，0，0），代入目标函数得z = 6 。
（3）增添一个新的约束条件。
将原最优解（6，0，0）代入新的约束条件。 ，得知：原最优解不满足新的约束条件，所以原最优解不是此时的最优解。
在新的约束条件。中，加松弛变量x6 ，得 ；即 ，反映到单纯形表中得：
cj
2
-1
1
0
0
0

CB
基
b
x1
x2
x3
x4
x5
x6

2
x1
6
1
1
1
1
0
0
①
0
x5
10
0
3
1
1
1
0
②
0
x6
-2
1
0
-2
0
0
1
③
cj- zj
0
-3
-1
-2
0
0

因为x1列不是单位向量，故需进行变换，得下面单纯形表。下表中④⑤行同上表中的①②行，下表中⑥行由以下初等变换得到：⑥＝③ - ①
cj
2
-1
1
0
0
0

CB
基
b
x1
x2
x3
x4
x5
x6

2
x1
6
1
1
1
1
0
0
④
0
x5
10
0
3
1
1
1
0
⑤
0
x6
-8
0
-1
-3
-1
0
1
⑥
cj- zj
0
-3
-1
-2
0
0

因-8≤0，使用对偶单纯形法求解，选x6出基，因1/3≤2≤3，故选x3进基，则得
cj
2
-1
1
0
0
0
CB
基
b
x1
x2
x3
x4
x5
x6
2
x1
10/3
1
2/3
0
2/3
0
1/3
0
x5
22/3
0
8/3
0
2/3
1
1/3
1
x3
8/3
0
1/3
1
1/3
0
-1/3
cj- zj
0
-3
-1
-2
0
0
故最优解为：（10/3，0，8/3），代入目标函数得z = 28/3 。
2.12 给出线性规划问题：
max
st.
用单纯形法求解得最终单纯形表见表2-33 。
cj
2
3
1
0
0
CB
基
b
x1
x2
x3
x4
x5
2
x1
1
1
0
-1
4
-1
3
x2
2
0
1
2
-1
1
cj- zj
0
0
-3
-5
-1
试分析下列各种条件下最优解（基）的变化：
（1）目标函数中变量x3的系数变为6 ；
（2）分别确定目标函数中变量x1和x2的系数c1、c2在什么范围内变动时最优解不变；
（3）约束右端项由变为；
（4）增加一个新的变量x6，, c6 = 7 ；
（5）增添一个新的约束。
解：（1）目标函数中变量x3的系数变为6 时，得如下单纯形表，并用单纯形法求解步骤进行计算，其过程如下：
cj
2
3
6
0
0
CB
基
b
x1
x2
x3
x4
x5
2
x1
1
1
0
-1
4
-1
3
x2
2
0
1
2
-1
1
cj- zj
0
0
2
-5
-1
因2≥0，所以选x3进基，因2≥0，故选x2出基，则得
cj
2
3
6
0
0
CB
基
b
x1
x2
x3
x4
x5
2
x1
2
1
1/2
0
7/2
-1/2
6
x3
1
0
1/2
1
-1/2
1/2
cj- zj
0
-1
0
-4
-2
得最优解为：（2，0，1），代入目标函数得z = 10 。
（2）设目标函数中变量x1和x2的系数为c1、c2 ，则由原单纯形表得如下单纯形表：
cj
c1
c2
1
0
0
CB
基
b
x1
x2
x3
x4
x5
c1
x1
1
1
0
-1
4
-1
c2
x2
2
0
1
2
-1
1
cj- zj
0
0
1+ c1- 2c2
-4c1+ c2
c1- c2
若要保持原问题最优解不变，则应有所有检验数均小于等于0；即
即
（3）约束右端项由变为；有＝
=
将上述结果反映到单纯形表中得：
cj
2
3
1
0
0
CB
基
b
x1
x2
x3
x4
x5
2
x1
5
1
0
-1
4
-1
3
x2
1
0
1
2
-1
1
cj- zj
0
0
-3
-5
-1
此时，上表中的解仍为可行解，故最优解为：（5，1，0），代入目标函数得z = 13 。
（4）增加一个新的变量x6，, c6 = 7 ；

检验数 c6- z6 = 7 - 3*2 = 1 ，将上述结果反映到单纯形表中得：
cj
2
3
1
0
0
7
CB
基
b
x1
x2
x3
x4
x5
x6
2
x1
1
1
0
-1
4
-1
3
3
x2
2
0
1
2
-1
1
0
cj- zj
0
0
-3
-5
-1
1
因x6的检验数1≥0，所以原最优解已经不是新问题的最优解；选x6进基，因3≥0，故选x1出基，则得
cj
2
3
1
0
0
7
CB
基
b
x1
x2
x3
x4
x5
x6
7
x6
1/3
1/3
0
-1/3
4/3
-1/3
1
3
x2
2
0
1
2
-1
1
0
cj- zj
-1/3
0
-8/3
-19/3
-2/3
0
故最优解为：（0，2，0，0，0，1/3），代入目标函数得z = 6 + 7/3 = 25/3 。
（5）增添一个新的约束。
将原最优解（1，2，0）代入新的约束条件 ，得知：原最优解不满足新的约束条件，所以原最优解不是此时的最优解。
在新的约束条件中，加松弛变量x6 ，得 ，反映到单纯形表中得：
cj
2
3
1
0
0
0

CB
基
b
x1
x2
x3
x4
x5
x6

2
x1
1
1
0
-1
4
-1
0
①
3
x2
2
0
1
2
-1
1
0
②
0
x6
4
1
2
1
0
0
1
③
cj- zj
0
0
-3
-5
-1
0

因为x1 、x2列不是单位向量，故需进行变换，得下面单纯形表。下表中④⑤行同上表中的①②行，下表中⑥行由以下初等变换得到：⑥＝③ - 2*② - ①
cj
2
3
1
0
0
0

CB
基
b
x1
x2
x3
x4
x5
x6

2
x1
1
1
0
-1
4
-1
0
④
3
x2
2
0
1
2
-1
1
0
⑤
0
x6
-1
0
0
-2
-2
-1
1
⑥
cj- zj
0
0
-3
-5
-1
0

因-1≤0，使用对偶单纯形法求解，选x6出基，因1≤3/2≤5/2，故选x5进基，则得
cj
2
3
1
0
0
0

CB
基
b
x1
x2
x3
x4
x5
x6

2
x1
2
1
0
1
6
0
-1

3
x2
1
0
1
0
-3
0
1

0
x5
1
0
0
2
2
1
-1

cj- zj
0
0
-3
-5
-1
0

故最优解为：（2，1，0），代入目标函数得z = 7 。
2.13 分析下列线性规划问题中，当λ变化时最优解的变化，并画出对λ的变化关系图。
（2）min
st.
解：首先用两阶段法求解λ＝0时的线性规划问题的最优解，具体过程如下：
由题意可得如下初始单纯形表：
cj
0
0
0
0
-1
-1
CB
基
b
x1
x2
x3
x4
x5
x6
-1
x5
2
1
0
1
2
1
0
-1
x6
5
2
1
0
3
0
1
cj- zj
3
1
1
5
-1
-1
因5≥3≥1，所以选x4进基，因2/2≤5/3，故选x5出基，则得
cj
0
0
0
0
-1
-1
CB
基
b
x1
x2
x3
x4
x5
x6
0
x4
1
1/2
0
1/2
1
1/2
0
-1
x6
2
1/2
1
-3/2
0
-3/2
1
cj- zj
1/2
1
-3/2
0
-7/2
-1
因1≥1/2，所以选x2进基，因1≥0，故选x6出基，则得
cj
0
0
0
0
-1
-1
CB
基
b
x1
x2
x3
x4
x5
x6
0
x4
1
1/2
0
1/2
1
1/2
0
0
x2
2
1/2
1
-3/2
0
-3/2
1
cj- zj
0
0
0
0
-2
-2
故得初始基可行解为（0，2，0，1），令λ＝0，可得如下初始单纯形表：
cj
-1
-1
0
0
CB
基
b
x1
x2
x3
x4
0
x4
1
1/2
0
1/2
1
-1
x2
2
1/2
1
-3/2
0
cj- zj
-1/2
0
-3/2
0
将反映到单纯形表中，可得如下单纯形表：
cj
-1
-1
λ
-2λ
CB
基
b
x1
x2
x3
x4
-2λ
x4
1
1/2
0
1/2
1
-1
x2
2
1/2
1
-3/2
0
cj- zj
λ-1/2
0
2λ-3/2
0
当λ≤1/2时，表中的解为最优解，且原问题目标函数值z = 2λ+2。
当λ≥1/2时，变量x1的检验数大于0，选x1进基，因2≤4，故选x4出基，则变换得如下单纯形表：
cj
-1
-1
λ
-2λ
CB
基
b
x1
x2
x3
x4
-1
x1
2
1
0
1
2
-1
x2
1
0
1
-2
-1
cj- zj
0
0
λ-1
1-2λ
当1/2≤λ≤1时，表中的解为最优解，且原问题目标函数值z = 3。
当λ>1时，变量x3的检验数大于0，选x3进基，因0≤1，故选x1出基，则变换得如下单纯形表：
cj
-1
-1
λ
-2λ
CB
基
b
x1
x2
x3
x4
λ
x3
2
1
0
1
2
-1
x2
5
2
1
0
3
cj- zj
1-λ
0
0
3-4λ
当λ>1时，表中的解为最优解，且原问题目标函数值z = 5-2λ。
当λ变化时，的变化如下面表达式：

画出关于λ的变化图如下：

运筹学习题答案及注释 第12页