运筹学(清华大学第三版)习题集

-M521100-115/2

2M+10M+15M+1200-M0

109/513/51/51/50009

02409[16]11003/2

—M7/50-1/53/5-2/50-117/3

09-M/53M/5+10-2M/5-20-M0

1()3/2139/8003/16-1/8()00

123/209/1611/161/1600

-M1/20-43/800-7/16-3/80-11

027/8-43M/800-21/8-7M/16-5/8-3M/8-M0

所有变量的检验数均为负数或零，单纯形表“算完毕，但人工变量与仍在基变

量中，故原问题无可行解。

例6：求解下述LP问题

解.：用两阶段法求解。先将原问题化为标准型，可得:

引入人工变量，可得第一阶段的问题为：

构造单纯形表，计算如下：

000000111

16111—1001006

12-2010-10010—

100[2]-100-10010

1-3-1111000

16103/2-101/210-1/24

12-20[1]0-100102

0()01-1/200-1/2001/2—

10-5/2i1-1/2003/2

13[4]00-13/21/21-3/2-1/23/4

02-2010-10010—

01-1100-1/2-1/201/21/2—

-4001-3/2-1/205/23/2

03/4100-1/43/81/81/4-3/8-1/8

07/2001—1/2-1/41/41/21/4-1/4

07/4010-1/4-1/8-3/81/41/83/8

000000111

Q77

故'第一阶段的最优解为『二右，『5，。，。，。，。，。，。尸

第二阶段的单纯形表如下:

2-12000

03/4100-1/43/81/8

07/2001-1/2-1/41/4

07/4010-1/4-1/8-3/8

0005/4-3/8-9/8

非基变量匕的检验数为正，但其系数向量为负，故原问题为无界解。

例7：已知下述线性规划

的最优基为8*=H，46],求其最优单纯形表。

解：由8*=有工,用,可知:

故由单纯形表的行变换过程可知：

-01/401F8121001F41001/40

『3,A]=-21/211640010=400-21/21

1/2-1/80j[120

40012011/2-1/80

原问题的最优单纯形表为：

23000

241001/40

0400-21/21

32011/2-1/80

00-3/2-1/80

例8：已知某线性规划的最优单纯形表为:

23000

241001/40

0400-21/21

32011/2-1/80

00-3/2-1/80

其中，毛，%，工5为松弛变量，求该线性规划的初始单纯形表。

解.：由七,七,七为松弛变量，可知它们在约束条件中的系数矩阵为单位矩阵，故

在最优单纯形表中，它们的系数矩阵为即:

01/40102

=-21/21可得400

1/2-1/80014

由：

-1021「41001/40]「81200

BTBF,400400-21/21=1640010

4_||_2

01011/2-1/80J|_1204001

可知最初单纯形表为:

23000

0812100

01640010

0120[4]001

23000

的最优解为X*=(6,2,0)"试利用互补松弛定理，求对偶问题的最优解。

解：原问题的对偶问题为：

揩X*=(6,2,。)/代入原问题的约束条件，可得：

[6+2*2=10=y；＞0

《力(1)

[2*6+2*2=16=＞y；＞0

又由

x；>0=>），；+2y；=3

x；>0=>2y；+2y；=4(2)

x；=0=y；+y；21

将结论(1)和(2)结合起来，可解得y：=y；=l。

例已知线性规划问题

其对偶问题的最优解为y：=4、y；=l,试用对偶理论求解原问题的最优解。

解：原问题的对偶问题为：

将对偶问题的最优解代入约束条件，可得：

2*4+2*1〉2nx；=0

2*4>1=x：=0

~(1)

4+1=5x；>()

4+2*1=6nx；>0

又由

y；>0=2X；+X；+"=8(2)

72>0=>2<+2"+七*+2X4=12

将结论(1)和(2)结合起来，可得：

苫丁"不，解得卜=4

x3+2X4=12[x4=4

即原问题的最优解为X*=(0,0,4,4),O

解：先将原问题改写为：

建立单纯形表计算如下：

-2-3-400

0-3-1-2-110

0-4[-2]1-301

-2-3-400

0-10[-5/2]1/21-1/2

-221-1/23/20-1/2

0—4-10-1

-32/501-1/5-2/5V5

-211/5107/5-1/5-2/5

00-9/5-8/5-1/5

故，原问题的最优解为X*=(ll/5,2/5,0)"z*=28/5o

先用单纯形法求出最优解，再分析以下各种条件下，最优解分别有什么变化:

(1)约束条件①的右端常数由20变为30；

(2)约束条件②的右端常数由90变为85；

(3)目标函数中七的系数由13变为8；

(4)%的系数列向量由［-1,12』变为［0,5『；

(5)占和马的系数列向量由［-1，12/、［1,4/变为［0,5］T、［2,1R

(6)增力口一个约束条件③2%+3々+5元3<50；

(7)将约束条件②改变为10%+5X2+10七410°。

解：分别在约束条件①和②中引入松弛变量8和公，列单纯形表计算如下:

-551300

020-11[3]1020/3

09012410019

-551300

1330/3-1/3[1/3]11/3020

070/346/32/30-10/3135

-2/32/30-13/30

520-11310

010160-2-41

00-2-50

由此可得，原问题的最优解为X'nO)；。,。,。［。)7',z*=100o

由单纯形表可知，原问题中8一1=o

-41

(1)约束条件右端常数此时为〃=(30,90)1由

可知，单纯形表应变为:

-551300

530-11310

0-30160[-2]-41

00-2-50

5-152310[-5]3/2

1315-8012-1/2

-1600-1-1

03-23/5-1/501-3/10

1396/52/5101/10

-103/5-1/500-13/10

由此可得，最优解变为x*=（0,0,9,3,0）,，z*=117o

（2）约束条件右端常数此时为〃=（20,85尸，由

可知，最优基不变，最优解为X*=（0,20,0,0,5）7,z*=10（）o

（3）若c\变为8,则鼻的检验数变为

故最优解不变。

（4）占在原最优解中为非基变量，若』的系数列变为［=；,由

可知，检验数?由0变为一5,故最优解不变。

（5）与在原最优解中为基变量，若用和马的系数列变为有，4〕二；;，则

在约束①中引入人工变量儿，单纯形表变为:

-551300-M

-M2009[3]10120/3

0105-7-2-410

-55+2M13+3MM00

1320/302/311/301/3

070/35-17/30-10/312/3

-5-11/30-13/30-M-I3/3

故，最优解为X*=(0,0,20/3,0,70/3,0)7,z*=260/3o

（6）若引入一个约束③，单纯形表将增加一行。在约束③中引入松弛变量4,

单纯形表变为：

-5513000

520-113100

010160-2-410

050235001

520-113100

01()160-2-410

0-1050[-4]-301

00-2-500

525/211/410-5/403/4

01527/200-5/21-1/2

05/2-5/4013/40-1/4

-5/200-7/20-1/2

由此可得，最优解为X*=(0,25/2,5/2,0,15,0)1z"=95。

（7）若约束条件②变为10%+5工2+10戈3<10°，即玉、£的系数分别变为

20

b列变为〃=,则

100

由于基变量％的系数发生变化，故在约束条件①中引入人工变量4，单纯形表

变为：

-551300-M

-M20-11[3]10120/3

020141-2-410

-5-M5+M13+3MM00

1320/3-1/31/311/301/320

0100/340/3[5/3]0-10/312/320

-2/32/30-13/30-M-13/3

130-3011-1/51/5

520810-23/52/5

-600-3-2/5-M23/5

故，最优解为X*=(0,20,0,0,0,0)\z*=最"

试分析当参数，之。变化时，Z"(f)的变化，其中z”是下述线性规划的最优目标函

数值。

解.：引入松弛变量九3、&和毛，令，=0,列单纯形表计算，可得：

35000

020011/3-1/3

560101/20

32100-1/31/3

000-3/2-1

将C=(3+2，,5T)代入,可得:

3+215-1000

020011/3-1/3

5-t60101/20

3+2t2100-1/31/3

000-3/2+71/6

37

a.=——+-r<0

26Al，可知当参数，从。开始增大到9/7,即

由・

CT=-1--/<()t>--

5S32

次［0,9/7］时，检验数都保持为非正，故此时最优解保持为X*=(2,6,2,0,01,

z*(r)=36-2ro

当参数f开始超过9/7,即f>9/7时，检验数。4>0,但其他检验数仍为非

正，此时选择匕为换入变量，用单纯形表迭代计算可得:

3+2t5-t000

060031-1

5-t301-3/201/2

3+2t410100

009/2-71/20-5/2+1/2

a.=-----<0

22

由，7，可知当参数如(9/7,5］时,最优解为

5t/

c5=---1—<0/<5

X’=(4,3,0,6,0)7,z"Q)=27+5f。

当参数，开始超过5,即，>5时，检验数%〉。，但其他检验数仍为非正，

此时选择以为换入变量，用单纯形表迭代计算可得:

3+215-t000

01202010

0602-301

3+2t410100

05-t-3-2t00

E=5-r<0[/>5

由<=«可知当(5,8)时，最优解为

(T3=-3-2r<0[f>-3/2

X*=(4,0,0,12,6)"，(1)=12+8人

综述所述，可知：

例某个求最大值的线性规划问题的最优单纯形表如下，其中乙、看为松弛变量。

20-1131

41-10-10

0-30-3-1

(1)写出该问题的最优解；

(2)当Aj为何值时，其对偶问题无解?

解：(1)最优解为X*=(4,020,0)7。

(2)由最优单纯形表的检验数，可得方程组：

02+03+q=—3

<0-3%+〉=-3,可得。=(0,-4,1,0,0)o

0-c3=-l

若其对偶问题无解，则原问题为无解或无界解。当q变化时，原最优单纯形表中

只有检验数将变化，故(4,0,2,0,0)/总是原问题的可行解。因此，要使对偶问题

无解，原问题必为无界解。

由原最优单纯形表可知，马的最终列向量为负，故当q=-3+AC3〉0,

即AC3〉3时，原问题有无界解，其对偶问题无解。

例1已知线性规划

的最优单纯形表为

250101/21/2

1310001

03001-1/23/2

000-1-2

（1）写出最优基矩阵B及其逆矩阵3-

（2）写出其对偶问题；

（3）给出对偶问题的最优解；

解：（1）由最优单纯形表，可知

-21101/21/2

8==-120,B1=001

1001-1/23/2

（2）原问题的对偶问题为

（3）由原问题变量（内,工2，七，七,七）’与对偶问题变量（）1，%，%）'4,”），之间的对应

关系，以及对偶理论，可知:

即对偶问题的最优解为y*=（0,1,2,0,0）、

例2已知线性规划

的最优单纯形表为

621200

1284/31/311/30

06-250-11

-10-20-40

其中，山、.分别为第1、2个约束的松弛变量"

（1）求出最优基不变的。2变化范围；

（2）求出最优解不变的C、变化范围；

（3）在原问题中增加约束条件%+2%+2刍412,求最优解。

O-

解：由原问题的最优单纯形表，可知8-=O

-11

「]/30-1「2Q

（1）记〃=[24,4r，则由夕%=、二,〜可知，要使最优基

—11b4一24

不变，只需4—2420,即囱之24。

（2）要使最优解不变，只需保证所有检验数仍保持非正，即

6-4c3/3<0c3>9/2

2-C3/3<0,可得卜3之6,即C3N6。

-<:3/3<0c3>0

（3）在新约束条件中引入松弛变量X，在原最优单纯形表中增加一行，可得:

6212000

1284/31/311/300

06-250-110

012122001

1284/31/311/300

06-250-110

0-45/34/30[-2/3]01

-10-20-400

1261/311001/2

012-1/23001-3/2

065/2-2010-3/2

0-10000-6

故，最优解变为X*=(0,0,6,6,12,0)"£=72。

例1.用表上作业法求解下述运输问题。

甲乙丙T产量

A1067124

B161()599

C541()1()4

销量5246

解：这是一个产销平衡问题，可用表上作业法求解。

用最小元素法求得初始解：

甲乙丙T产量

A314

B459

C224

销量5246

用位势法计算U和V：

甲乙丙Tui

A(10)(12)0

B(5)(9)-3

C(5)(4)-5

vj109812

计算非基本变量的检验数:

甲乙丙Tui

A-3(6)-1⑺0

B9(16)4(10)-3

C7(10)3(10)-5

vj109812

以（A乙）作为调入格，用闭回路调整法计算（A乙）的新运量:

甲乙丙T产量

A1214

B459

C44

销量524