运筹学基础及应用第四版胡运权主编课后练习答案

.

精品

运筹学基础及应用 习题解答

习题一 P46 1.1 (a)

该问题有无穷多最优解，即满足2

1

0664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。 (b)

用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。 1.2

(a) 约束方程组的系数矩阵

????

? ??--=1000030204180036312A

4

.

精品

最优解()T x 0,0,7,0,10,0=。 (b) 约束方程组的系数矩阵

?

??

? ??=21224

321A 最优解T

x ???

??=0,511,0,5

2。

1.3

(a)

(1) 图解法

.

精品

最优解即为???=+=+82594321

21x x x x 的解??? ??=23,1x ，最大值235=z (2)单纯形法

首先在各约束条件上添加松弛变量，将问题转化为标准形式 ???=++=+++++=825943 ..00510 max 421321

4

321x x x x x x t s x x x x z

则43,P P 组成一个基。令021==x x

得基可行解()8,9,0,0=x ，由此列出初始单纯形表

21σσ>。5839,58min =

??? ??=θ

.

精品

.

精品

02>σ，2328,1421min =???

??=θ

0,21<σσ，表明已找到问题最优解0 , 0 , 2

3 1,4321====x x x x 。最大值 235*=z (b)

(1) 图解法

最优解即为???=+=+5

24262121x x x x 的解??? ??=23,2

7x ，最大值217=z (2) 单纯形法

首先在各约束条件上添加松弛变量，将问题转化为标准形式 12345

23124125

max 2000515.. 6224

5z x x x x x x x s t x x x x x x =+++++=??++=??++=?21=+x x 2621+x x

.

精品 则3P ，4P ，5P 组成一个基。令021==x x

得基可行解()0,0,15,24,5x =，由此列出初始单纯形表

21σσ>。245min ,

,461θ??=-= ???

02>σ，1533min ,24,522θ??==

??? 新的单纯形表为

.

精品

0,21<σσ，表明已找到问题最优解11x =，2 2x =，3152x =，40x =，50x =。最大值 *172

z =

1.6 (a) 在约束条件中添加松弛变量或剩余变量，且令()0,0 ''2'2''2'22≥≥-=x x x x x ，

z z x x -=-=' ,3'3

该问题转化为

???????≥=-+-=---+=++-+++-+--=0,,,,,633824124332x ..0023' max 54'3''2'21'3''2'215'3''2'214'3''2'215

4'3''2'21x x x x x x x x x x x x x x x x x x x t s x x x x x x z

其约束系数矩阵为

????

? ??------=003113102114014332A 在A 中人为地添加两列单位向量87,P P ????

? ??------100031130110211400014332 令7654'3''2'2

10023' max Mx Mx x x x x x x z --++-+--= 得初始单纯形表

.

精品

.

精品

(b) 在约束条件中添加松弛变量或剩余变量，且令)''''''33333 0,0

x x x x x =-≥≥， 'z z =- 该问题转化为

'''123345

'''12334'''12335'''1233'''123345max '3500x 2623316.. 5510,,,,,0z x x x x x x x x x x x x x x x s t x x x x x x x x x x =--+-++?++--=?+--+=??++-=?

?≥?

其约束系数矩阵为

121110************A --?? ?=-- ? ?-??

在A 中人为地添加两列单位向量87,P P 121110102133010011550001--?? ?- ? ?-??

令'''12334567max '3500z x x x x x x Mx Mx =--+-++--

1.7

(a)解1：大M 法

在上述线性规划问题中分别减去剩余变量468,,,x x x 再加上人工变量579,,,x x x 得

.

精品

123456789max 22000z x x x x Mx x Mx x Mx =-++-+-+-

1234513672389123456789622,,20,,,,,,,,0

x x x x x x x x x s t x x x x x x x x x x x x x ++-+=??-+-+=?

?

--+=??≥?

其中M 是一个任意大的正数。据此可列出单纯形表

由单纯形表计算结果可以看出，40σ>且40(1,2,3)i a i <=，所以该线性规划问题有无界解 解2：两阶段法。

.

精品

现在上述线性规划问题的约束条件中分别减去剩余变量468,,,x x x 再加上人工变量

579,,,x x x 得第一阶段的数学模型

第一阶段求得的最优解*

T

X (,,,0,0,0,0,0,0)442

=,目标函数的最优值*

0ω=。

因人工变量5790x x x ===，所以*T 377

(,

,,0,0,0,0,0,0)442

X =

是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题

.

精品

由表中计算结果可以看出，40σ>且40(1,2,3)i a i <=，所以原线性规划问题有无界解。

(b)解1：大M 法

在上述线性规划问题中分别减去剩余变量468,,,x x x 再加上人工变量579,,,x x x 得

1234567min 2300z x x x x x Mx Mx =+++++-

123461257123456789428326,,,,,,,,,,0

x x x x x x x x x s t x x x x x x x x x ++-+=??+-+=?

?

??≥?

其中M 是一个任意大的正数。据此可列出单纯形表

由单纯形表计算结果可以看出，最优解*T (,

,0,0,0,0,0)55

X =

，目标函数的最优解值

.

精品

*49

23755

z =?

+?=。

X 存在非基变量检验数30σ=，故该线性规划问题有无穷多最优解。 解2：两阶段法。

现在上述线性规划问题的约束条件中分别减去剩余变量45,,x x 再加上人工变量67,,x x 得第一阶段的数学模型67min x x ω=+

123461257123456789428326,,,,,,,,,,0

x x x x x x x x x s t x x x x x x x x x ++-+=??+-+=?

?

??≥?

第一阶段求得的最优解*T (,

,0,0,0,0,0)55

X =

,目标函数的最优值*0ω=。 因人工变量670x x ==，所以T

49(,,0,0,0,0,0)55

是原线性规划问题的基可行解。于是可

以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的

.

精品

由单纯形表计算结果可以看出，最优解*T (,,0,0,0,0,0)55

X =，目标函数的最优解值*4923755

z =?

+?=。由于存在非基变量检验数30σ=，故该线性规划问题有无穷多最优解。

1.8

表1-23

.

精品

习题二 P76

2.1 写出对偶问题

(a)

???????≥=++≤+++≥++++=无约束

3213214321321321,0,5

34332243 ..422 min x x x x x x y x x x x x x t s x x x z 对偶问题为：???????≤≥=++≤++≤++++=无约束3213213213213

21,0,0433424322 ..532max y y y y y y y y y y y y t s y y y w (b)

???????≤≥≤++≥-+-=++++=0,0,837435522 ..365max 321321321321321x x x x x x x x x x x x t s x x x z 无约束 对偶问题为： ???????≥≤≤+-≥++=+-++=0

,0,3

32675254 ..835 min 3213213213213

21y y y y y y y y y y y y t s y y y w 无约束 2.2

(a)错误。原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。

(b)错误。线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。 (c)错误。

(d)正确。

2.6 对偶单纯形法

(a)

?????≥≥+≥+++=0,,5

22 33 ..18124 min 3

2132313

21x x x x x x x t s x x x z

.

精品 解：先将问题改写为求目标函数极大化，并化为标准形式 ()?????=≥-=+---=+--++---=5,,105

22 3 3 ..0018124'max 5324315

4321 i x x x x x x x t s x x x x x z i

最优解为T x ??? ?

?=23,1,0， 目标值39=z 。 (b)

?????≥≥++≥++++=0,,10

53642 3 ..425 min 3

213213213

21x x x x x x x x x t s x x x z 解：先将问题改写为求目标函数极大化，并化为标准形式 ()?????=≥-=+----=+---++---=5,,1010

5364 2 3 ..00425'max 532143215

4321 i x x x x x x x x x t s x x x x x z i

列单纯形表，用对偶单纯形法求解

本文来源：https://www.bwwdw.com/article/i5e4.html