运筹学(第五版)习题答案

运筹学习题答案

第一章(39页)

1o1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解

还是无可行解。

(1)maxz=xx+x2

5Aj+10<50

>

xi+x2>\

X2<4

xifx2>0

(2)minz二阳+1.5x2

X)+3x2>3

阳,x2>0

(3)maxz=2A)+2x2

%]-x2>-1

-0.5%]+x2<2

用,x2>0

(4)maxz=+x2

x—x2>0

3将一x2<-3

X],x2>0

解：

(1)(图咯)有唯一可行解，maxz=14

(2)(图略)有唯一可行解，minz=9/4

(3)(图略)无界解

(4)(图略)无可行解

1o2将下列线性规划问题变换成标准型，并列出初始单纯形表。

(1)minz=-3芭+4x2-2&+5,v4

4X1-x2+2-x4=~2

X1+A-2+3x3-<14

-2x,+3X,-X3+2X4>2

X),x2fx3>0,4无约束

(2)maxs=z%

2£=£2飙4

f=lA=l

m

*=l

xik>0(i=1…n;k=1,…，m)

(1)解：设Z二一z',X4=x5-x6,x5,x6>0

标准型：

,=-

Maxz3Xj-4x2+2xy—5(x5—x6)+0x7+0xs-Mx9Mx,0

-

4,+七一2七+/—X6+X10=2

内+七+3七一x5+.r6+x7=14

-2Aj+3x2-x3+2x5-2x6-/+x9=2

,工2，X3，*5,4，£,4,4,/之°

初始单纯形表：

一3-42-5500-M—Mq

X*b西x$4当不x\o

-M巧02—41-21—100012

014113-11100014

—M2-2[3]—12-20—1102/3

4M3-6M4M—42-3M3M-55-3M0-M00

(2)解：加入人工变量x2,与，…乙，得:

Maxs=(1//;A)ZZaikxjk―—Mx2--..-Mx”

1=11=1

•w

±+£/=1(i=1,2,3…，n)

&=i

xik>0,x.>0,(i=1,2,3…n;k=1,2・・・.，m)

M是生意正整数

初始单纯形表：

%

%-M•••%Cl•••"%•••%%*•••a

MM

♦•••••••••••

CBXBb王x24不X“2%

-M王110•••011••••••00•••0

-M101•••00•♦•00♦••0

•••♦••••••♦•••♦••••••♦••••••••••••♦•••••••••••♦

—MXn100♦••100•♦•0•••11♦♦*1

-snM00•••0%/p+M•••"%+M••»"%+M"%+.W•••%”

1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标

函数，确定最优解。

(1)maxz=2a+3々+4/+78

2%+3x2-X3-4X4=8

阳-2x2+6xy——7x4-——3

/，x,,x3,x4>0

(2)maxz=5x]—2x2+3J3-6x4

%)+2X2+3X3+4.V4=7

2片+4+x3+2,v4=3

x]x2x3x4>0

(1)解：

系数矩修A是：

'23-1-4一

1-26-7_

令A二(2，g,R)

4与6线形无关，以(片，舄)为基，阳，七为基变量.

有2%+3x2=8+x3+4x4

=

$-2A2^36A3+7x4

令非基变量X4=0

解得：x(=1;X2=2

基解X⑴二(1,2,0,0)"为可行解

4二8

同理，以(片，6)为基，基解X⑵二(45/13,0,-14/13,0)7是非可行解:

以(<,巴)为基，基解X⑶二(34/5,0,0,7/51是可行解,q=117/5;

7

以(R,4)为基，基解X(4)=(0,45/16,7/16,0)■是可行解,z4=163/16;

以（鸟，乙）为基，基解X⑸二（0,68/29,0,—7/29/■是非可行解；

以（鸟，乙）为基，基解X⑹二（0,0,-68/31,-45/31）,是非可行解；

最大值为z『117/5;最优解X⑶二（34/5,0,0,7/51。

（2）解:

系数矩修A是：

-1234-

2112

令A二（〃，P「A，R）

6线性无关，以"，4）为基，有：

/+2x2=7——3x3-4x4

2+x2=3——x3——2x4

令.q,=0得

X1二一1/3,x2=11/3

基解X⑴二（—1/3,11/3,0,0）丁为非可行解；

同理，以（九八）为基，基解X⑵二（2/5,0,11/5,0）71是可行解z,=43/5;

以（耳,巴）为基，基解X⑶二（一1/3,0,0,11/6）,是非可行解：

7

以（鸟，〃）为基，基解X⑷二（0,2,1,0）■是可行解，z4=—1；

以（巴，舄）为基，基解X⑹二（0,C,1,1尸是Z6=-3;

r

最大值为马二43/5;最优解为X⑵二（2/5,0,11/5,0）o

1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪

一点。

（1）maxz=2x]+x2

3%+5x2<15

6x,+2.v,<24

%i，x2>0

(2)maxz-2X)+5x2

再<4

2x2<12

3*+2x2<18

X，x2>0

解：(图略)

(1)maxz=33/4最优解是(15/4,3/4)

单纯形法：

标准型是maxz=2x]+x2+0x3+0x4

Soto3x(+5X2+X3=15

6.r,+2三+七二24

M，x2,x3,x4>0

单纯形表计算：

Cj2100Q

GXBb内x2X3儿

0与1535105

024[6]2014

-z02100

0再30[4]1—1/23/4

2411/301/612

-z-801/30—1/3

13/4011/4-1/8

215/410-1/125/24

—z—33/400-1/12-7/24

解为：(15/4,3/4,0,0)r

Maxz=33/4

迭代第一步表示原点；第二步代表C点(4,0,3,0)7;

第三步代表B点(15/4,3/4,0,0

(2)解：(图略)

Maxz=34此时坐标点为(2,6)

单纯形法，标准型是：

Maxz=2X)+5x2+0x3+0x4+0x5

Soto玉+J-4

2X2+X4=12

3*+2X2+X5=18

XitX2fXj,x4,x5>0

(表略)

最优解X=(2,6,2,0,0)T

Maxz=34

迭代第一步得X⑴二(0,0,4,12,18).表示原点，迭代第二步得X⑵二(0,6,4,0,6)\第三

步迭代得到最优解的点。

1o5以1.4题(1)为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行

域的每一个顶点，都可能使得目标函数值达到最优.

解:目标函数：maxz=qa+c2x2

(1)当C2Ho时

x2=—(q/c2)Xj+z/c2其中，k=—c1/c2

L=-3/5,kBC--3

•kY砥c时，"，"?同号。

当C^AO时，目标函数在C点有最大值

当°2Y0时，目标函数在原点最大值.

•YkY的8时，C?同号。

当C'AO,目标函数在B点有最大值；

当CzYO,目标函数在原点最大值.

•JYkY0时，。，。?同号。

当QA0时，目标函数在A点有最大值

当C；jYO时，目标函数在原点最大值。

•kA0时，。，02异号.

当c/0,GY0时，目标函数在A点有最大值；

当C2YO,GA0时，目标函数在C点最大值。

•k二断时，G,02同号

当c/0时，目标函数在AB线断上任一点有最大值

当CzYO,目标函数在原点最大值.

•k=时，G,Q同号。

当QAO时，目标函数在BC线断上任一点有最大值

当CzYO时，目标函数在原点最大值。

・k二。时，c,=0

当C^AO时，目标函数在A点有最大值

当CzYO,目标函数在0C线断上任一点有最大值

(2)当J二0时，maxz=C|x,

•C]»0时，目标函数在C点有最大值

•JYO时，目标函数在OA线断上任一点有最大值

•J二0时，在可行域任何一点取最大值。

1.6分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于哪类解。

(1)maxz=2x]+3x2-5x3

X1+x2+%,<15

2.*—5Xy+x,<24

%],x2>0

(2)minz=2xt+3x2+x3

x,+4X,+2X3>8

3*+2.r,26

玉,x2,忍20

(3)maxz=10,v1+15,v2+12x3

5*+3z+£"9

-5x}+6X,+15X3<15

2x}+x2+x3>5

再,々，£之0

(4)maxz=2xj—x2+2x3

Xi+x2+Xj>6

—2x,+.r5>2

2x2—Xy>0

%],x,,>0

解：（1）解法一：大M法

化为标准型：

Maxz-2X|+3,v2—5x3-M巴+0x5-Mx6

s.t.X]+x2+xy+x4=7

2%-5x2+xy-x5+x6=10

%],.t2,x3,x5,x4,x6>0M是任意大整数。

单纯形表：

Cj23-5-M0-M4

GXBb/x?思%/

—M71111007

-M410[2]-510—115

-z17M3M+23-4M2M-50-M0

-M20[7/2]1/211/2-1/24/7

251—5/21/20—1/21/2—

-z2M-0(7/2)0.5M000_1o

10M+8-65M+15M-1

3X24/7011/72/71/7-1/7

2xi45/7106/75/7—1/71/7

-z00-50/7—M-1/7

102/7M+1/7

16/7

最优解是：

X二(45/7,4/7,0,0,0).

目标函数最优值maxz=102/7

有唯一最优解.

解法二：

第一阶段薮学模型为minw二七+x6

S.t.再+x2+，q+X4=7

-

2公一5x2+,r3x5+x6=10

,x2,x3,x4,x5,x6>0

(单纯形表略)

最优解

X=(45/7,4/7,0,0,0)T

目标函数最优值minw=0

第二阶段单纯形表为：

ci23-500、

CBXBb,x?*3

3X24/7011/71/7

2芭45/7106/7—1/7

-z-102/700-50/7-1/7

最优解是

X=(45/7,4/7,0,0,0)T

Maxz=102/7

⑵解法一：大M法

z,=~z有maxz,=~min(-z)=­minz

化成标准形：

Maxz--2AJ-3X2-+0x4+0玉一M一Mx1

SoTo

巧+4x2+2—a+x6-4

3F+2x2-x5+&=6

王，x2,与，x4,x5,x6,x->0

(单纯性表计算略)

线性规划最优解X二(4/5,9/5,0,0,0,0/

目标函数最优值minz=7

非基变量与的检验数。3二°，所以有无穷多最优解。

两阶段法：

第一阶段最优解X=(4/5,9/5,0,0,0,0尸是基本可行解，minw=0

第二阶段最优解(4/5,9/5,0,0,0,0),minz=7

非基变量七的检验教由二0,所以有无穷多最优解。

(3)解：大M法

加入人工变量，化成标准型：

Maxz=10芭+15x2+12x3+0x4+0x5+0x6-Mx7

s.t.5xj3x2+A3+X4=9

—5x,+6x2+15巧+%二15

2*+%+&-4+5二5

X],X2,&，”4，*5，工6，-J之°

单纯形表计算喀

当所有非基变量为负数，人工变量工产0。5,所以原问题无可行解.

两阶段法(略)

(4)解法一：大M法

单纯形法，(表略)非基变量用的检脸数大于零，此线性规划问题有无界解。

两阶段法略

1o7求下述线性规划问题目标函数Z的上界和下界；

Maxz-cixi+c2x2

0西+出入2

4丙+a22X2-b2

其中：iWqW3,4<c2<6,8</?,<12,10<Z?2<14,<3,2<al2<5f2<a2l<4,4<tz22<6

解：

•求Z的上界

Maxz=3XI+6x2

Sot.一+2,r2<12

2x,+4A,<14

x2,x(>0

加入松弛变量，化成标准型，用单纯形法解的，最优解

X=(0,7/2,5,0)T

目标函数上界为z=21

存在非基变量检验数等于零，所以有无穷多最优解.

•求z的下界

线性规划模型：

MaxZ=Xj+4x2

s.to3*+5々48

4X,+6X2<10

>0

加入松弛变量，化成标准型，解得:

最优解为

X=（0,8/5,0,1/5）T

目标函数下界是z=32/5

1.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，%,七,

%,d,,2为待定常数，试说明这些常数分别取何值时，以下结论成立.

（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划

问题具有尢界解；（4）表中解非最优，对解改进，换入变量为须，换出变量为4.

基b工2&4

七d4410a20

九2—1-301—10

43%-500-41

J-ZjG00-30

解・

(1)有唯一最优解时，d>0,qYO,C?Y0

(2)存在无穷多最优解时，d>0,c.<0,c=Q^,d>0,c=0,c2<0o

(3)有无界解时，d>0,qVO,QAO且4工。

(4)此时，有dzO,qxO并且qNc2,6A0,3/%Yd/4

1.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下:

班次时间所需人数

16点到10点60

210点到14点70

314点到18点60

418点到22点50

522点到2点20

62点到6点30

设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公交线路至少配备

多少司机和乘务人员。列出线型规划模型。

解：

设々（k=1,2,3,4,5,6）为五个司机和乘务人员第k班次开始上班。

建立模型：

Minz=Xj+x2+x3+x4+xs+x6

s.toX1+.r6>60

xI+xL.之70

X2+X3>60

X3+X4>50

X4+X5>20

占+々；30

x2,x3,x4,x5,x6>0

1.10某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙，已知各种糖果中ABC含

量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示：

原料甲乙丙原料每月

成本（元/限制用量

千克）（千克）

A>60%>15%22000

B1o52500

C<20%<60%<50%11200

加工费0.50o40o3

售价3042o852.25

问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模型。

解：

解：设用,与，&是甲糖果中的A,B,C成分，x4,x5,凡是乙糖果的A,B,C成分，x7,x8,

与是丙糖果的A,B,C成分。

线性规划模型：

Maxz=0.9+1.4x2+1.9+0o45.j+0.95/+1。45x6—0。05。+0.45。"+0。95，"

Soto-0.4^+0.6X2+0O6X3<0

-0o2xt-0o2x2+0o8,V3<0

-0.85X4+0.15X5+0.15X6<0

—0o6&-0o6.勺+0。4X6<0

—0.7&-0。54+0。5工”0

$+%+<2000

x2+x5+<2500

x3+x6+^<1200

A|,x2,x3,x4,x5,x6,，玉，2>0

1.11某厂生产三种产品I、FI、III。每种产品经过AB两道加工程序，该厂有两种设备能

完成A二序，他们以A，A2表示；有三种设备完成B工序，分别为瓦，与，灰；产品I可以在AB

任何一种设备上加工，产品口可以在任何规格的A设备上加工，但完成B工序时，只能在用设

备上加工；产品III只能在4,用上加工。已知条件如下表，要求安排最优生产计划，使该厂利

润最大化.

设备产品设备有效满负荷时

IIIIII台时的设备费

用

A5106000300

%791210000321

B1684000250

/p>

用74000200

原料费0.250o350.5

单价

1.252.002O8

解：

产品1,设A，&完成A工序的产品为，看件；B工序时，用，生，4完成B工序的七,%，七

件，产品n,设A，4完成A工序的产品4,与件；B工序时，4完成B的产品为七件；产品111,

4完成A工序的2件，&完成B工序的用件；

*+x2-&+x4+x5

勺二/

人V6+

建立数学模型：

Maxz=(1.25—0.25)*(再+x2)+(2-0o35)*(x6+七)+(2。8—0.5)与一(5x,+104)

300/6000-(7±+9~+12与)321/10000—(6x.+8/)250/4000-(4x4+11/)783/7000—7

x5*200/4000

5+10x6<6000

7z+9七+12%<10000

6x:+8/<4000

4x4+11为<7000

7工§<4000

凡+X2=X3+几+A-5

入6+“7二4

$,x2,x3,x4,x5,x6,,“，/>0

最优解为X=（1200,230,0,859,571,0,500,500,324）,

最优值1147。

试题：

1.（2005年华南理工大学）设某种动物每天至少需要700克蛋白质、30克矿物质、100毫

克维生素。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价如下表所示:

试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型。

表1—1

饲料蛋白质（克）矿物质（克）维生素（毫价格（元/公

克）斤）

1310.50o2

22Oo510.7

310.2Oo20.4

46220.3

518Oo50.80o8

解题分析：这是一道较简单的效学规划模型问题，根据题意写出约束即可.

解题过程：minz=0.2X]+0.7x2+0.4A3+0.3x4+O.8x5

X

3%+2X2+Xy+64+1>7(X)

%)+().5X2+0.2M+2儿+0.5X5>3()

0.5A)++0.2/十2X4十0.8A5>100

玉,大2，七,七,七NO

第二章(67页)

2o1用改进单纯形法求解以下线性规划问题。

(1)Maxz=6Xj-2x2+3x3

2xl-x2+3xy<2

X1+4x3<4

X],x2,x3>0

(2)minz=2+x2

3X]+X2=3

4x,+3x2>6

X+2X2<3

%],x2>0

解：

(1)

先化成标准型：

Maxz=6x,—2x2+3x3+0x4+0xs

Sot.2Aj—x2+2.r3+x4=2

x,+4X3+X5=4

*，々，再，x4,x5>0

(]0、

令B。二(舄，A)[oJXk("xCLj=(0,0)

,、(2-12)/r

No~(P\,P?，伟一[]g彳，X"。一(，，2，X3)

(\0、(2、

Cy(6,-2,3),舔।二0]，为二^

非基变量的检脸数

°二，,—C凤稣一%二以二(仇一2,3)

?VO

因为内的检验数等于6,是最大值，所以，川为换入变量，

n1,(2}.(2}

B'b。二;Bn-\P=

\^/\1/

由。规则得:

。二1

S为换出变量。

(20、r

用-(匕,心)[[J,XB)-(J,,x5),%-(6,0)o

T

M二(/，P?,Pj,XN=(左，x2,x.)

C10,-2,3),B.-'=(工05：0、，4;(

(TQLJ

非基变量的检验数外、=(-3,1,-3)

因为々的检验数为1,是正的最大数。所以々为换入变量;

n1<-0.5"|

矿)P、二

0-5)

由。规则得：

e-b

所以看是换出变量。

r2-r

B=(<,p)=XRJ(x,,x)T,Q=(6,——2)o

22J°，2

T

M二(R,G，8),X,v：=(.r4,x5,X3)

CN—(0,0,3),By-,b、二

2-J2「⑹

非基变量的检脸数。/二(—2,—2,—9)

非基变量的检验数均为负数，愿问题已达最优解.

最优解X二

即:X二(4,6,0/

目标函数最优值maxz=12

(2)

解：

Minz=2$+x2+0/+M.V4+MX5+0.v6

SoT.

3*+x2+J4=3

4$+3x2-x3+x5=6

X)+2X2+X6=3

为,々，”3，七,45,“6

M是任意大的正数。

(非基变量检验数计算省略)

原问题最优解是X=(0。6,1o2,0)

目标函数最优值：z=12/5

2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数

字填上。

Cj354000

XB•%

cBb与工6

5X28/32/3101/300

0%14/3—4/305—2/310

0420/35/304—2/301

CJZj-1/304-5/300

0

0

“215/418/41

10/41

5/414/41

6/41

-2/41-12/4115/41

%—Zj

解：

%354000

CBXBb*x./%当%

5X28/3

014/3

0420/3

0

•

0

5-V280/4101015/41

4A50/41001-6/41

3当44/41100-2/41

Cj-Zj000-45/41

2O3写出下列线性规划问题的对偶问题.

(1)minz=2*+2马+4

2X1+3x2+5x,>2

311+x2+7x3<3

Xj+4.r,+6x3<5

演,x2,x3>0

(1)

解：对偶问题是：

Maxw=2y]-3y2-5%

SOto

2为一3为——》3<2

3)L为一4为42

5.v,-7y2-6yy«4

)1，8，X3-0

(2)maxz=+2x2+3.q+4x4

—xt+x,--3xd=5

6.*+79+3.r3-5x4>8

12k—9x2-9x,+9x4<20

X1,x2>0;x3<0;x4无约束

解：

对偶问题：

Minw=5))+8)\+20筋

>?4

S.to-y,+6y3+12>1

y1+7y3-9^>2

—y1+3”-9)4<3

—3y-5g+9)4=4

X无约束，y3<0;^>0

fn〃

(3)minz二工工与%

l-lJ=1

Z%=qi=1,—,m

41

产1，…，n

M

.%2。

解：

m〃

对偶问题：maxw=£《y；+£b：y，

r=lj=l

S.t。>；+晨GGy

x,%+j无约束in,2,…。m；j=1,2,­

(4)

n

Maxz=Jyc).x.)

/-I

i=1,….，叫《〃！

Zaiix)=b,,i="％+1,町+2,...,〃z

Xj>0,当j=1,…。，4<n

当无约束，当j二6+1,…,〃

解：

Minw二工鸟丫；

y=i

Z%”Cjj=1,2,3-n,

1=1

£%”CjF"+1,n'+2,,•­.n

1=1

y；20i=1,2….m{

其无约束，i二町+1,网+2…。m

2。4判断下列说法是否正确，并说明为什么。

(1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。

(2)如线性规划的对偶问题无可行解，则原问题也一定无可行解。

(3)如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题一定有有限

最优解.

(1)错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在；

(2)错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解；

(3)错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能有无界解；

2.5设线性规划问题1是：

MaxZi=£cjXj

j=i

,i=1,2…，m

7->

XjNO,j=1,2....,〃

（），；，...，）'：）是其对偶问题的最优解.

又设线性规划问题2是

Maxz2=c.x.

7-i

Z%jXj£bi+k,,i=1,2…，m

/T

%>0,j=1,2....,〃

其中勺是给定的常数，求证：

maxz2<maxz1&y；

i-l

解：

证明：把原问题用矩阵表示：

MaxZ］二CX

s.toAX<b

X>0

r

b=（A，b2.o.bm）

设可行解为X，对偶问题的最优解升二（M，为…以）已知。

Maxz2=CX

s.t.AX<b+k

X>0

k二（仁，k2...km）「

设可行解为X2,对偶问题最优解是工，对偶问题是，

Minw=Y(b+k)

S.toYA3c

Y>0

因为U是最优解，所以X[b+k)<Y,(b+k)

%2YXY

“2是目标函数z2的可行解，A<b+k；2K2<2(b+k)v^b+Yk

原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。

2.6已知线性规划问题

Maxz=c/i+c2x2+c3x3

即a\210,b1

X,+X,+

X1+()J4

生\_a22]~\_a23_

马之(Xj~1,…,5

用单纯形法求解，得到最终单纯形表也口表所示，要求：

a

(1)求61，。12,013，2\，,2，〃23,a,h2的值；

(2)求q,c2,c3的值；

b

XBx2%3%以

-b3/21011/2—1/2

21/210-12

Cj-Zj—3000—4

解:

(1)初始单纯形表的增广矩阵是:

aCl

\\\2《31°U

C产

a2301b2

最终单纯形表的增广矩阵为

101().5-0.51.5

C=

2|_0.5I0-122_

02是G作初等变换得来的，将G作初等变换，使得G的第四列和第五列的矩阵成为C?的

单位矩阵。有：

q尸9/2;«12=1;%=4;死尸5/2;a21-y;a23=2;

4=9;4=5

由检险计算得：

c=-3;c2=c3=0

2o7已知线性规划问题

Maxz=2x1+x2+5x3+6x4

Soto2^+x.+J4<8

2$+2%+凡+2儿<12

七20,j=1,-4

对偶变量,，力，其对偶问题的最优解是y；=4,)，；=i,试应用对偶问题的性质，求原问题的

最优解。

/解Tj・•

对偶问题是：

Minw=8))+12y2

Sot.2yt+2y2>2

2y2>1

)%+%之5

y,+2y2>6

))，

互补松弛性可知，如文，声是原问题和对偶问题的可行解，那么，步X5二0和

YSX=Q,当且仅当我,产是最优解.

设X,Y是原问题和对偶问题的可行解，为二（月，以，X，＞6）

有：

丫4二0；且r5x=o

x5=.v6=0,原问题约束条件取等号，占=4;5二4

最优解X二(0,0,4,4/

目标函数最优值为44.

2o8试用对偶单纯形法求解下列线性规划问题.

(1)minz=.v1+x2

2X,+X2>4

xt+7x2>7

.VI,x2>0

(2)minz=3+2x,++4x4

2XI+4.V2+5X3+X4>0

3x(-x2+7x3—2X4>2

5A^2A2+A3+10X4>15

X,x2,x3,x4>0

解：

(1)

取w=-z,标准形式：

Maxw=一/一x2+0x3+0x4

s.t.

——2七——x2+x3-——4

-&-7x2+x4--7

"l，*2，*3，14—。

单纯形法求解(略)：

最优解：

X=(21/13,10/13,0,0/

目标函数最优值为31/13o

(2)令：w=-z,转化为标准形式：

Maxw二一3为一2x2—x3-4x4+0x5+0x6+0x1

Sot.

~2々——4x,-5-x4+x5=0

—3%+x2-7&+2.j+/二—2

——5西-2x2-x3——6,r4+x7=-15

*,x2,J3,x4,x5,乙，与之0

单纯形法喀

原问题最优解：

X=(3,0,0,0,6,7,0/

目标函数最优值为9.

2o9现有线性规划问题

maxz=-5.V)+5x2+13x5

—X1+x2+3xy420

12A)+4x2+10x3W90

*,x2,x3>0

先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？

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

(2)约束条件2的右端常数90变为70

(3)目标函数中项的系数变为8

(4)』的系数向量变为

(5)增加一个约束条件2』+3/+5/工50

(6)将约束条件2变为10西+5看+10*3工100

解：

把原问题化成标准型的：

Maxz=-5X]+5x2+13x3+0,r4+0x5

Sot

-%+X2+3&+X5=20

12j,+4x2+10x3+,V5=90

X],x2,x4,x5>0

单纯形法解得：

最优解：

X=(0,20,0,0,10)r

目标函数最优值为100.

非基变量占的检验数等于0,原线性问题有无穷多最优解.

(1)约束条件。的右端常数变为30

有W=BxNb

因此b,=b+^b,

单纯形法解得：

最优解:

x=(0,0,9,3,Of

目标函数最优值为117o

(2)约束条件O,2右端常数变为70

有"=B'2

因此//=〃+&/

单纯形法解得，最优解：

X=(0,5,5,0,Or

目标函数最优值为90o

(3)七的系数变成8,七是非基变量，检验数小于0,所以最优解不变.

(4)用的系数向量变为"

X是非基变量,检验数等于一5.所以最优解不变.

(5)解：加入约束条件③

用对偶单纯形表计算得：

X=(0,25/2,5/2,0,15,0/

目标函数最优值为95.

(6)改变约束条件，0乙没有变化，

线性规划问题的最优解不变。

2.10已知某工厂计划生产I,II,III三种产品，各产品在ABC设备上加工，数据如下表,

设备代号1II111每月设备

有效台时

A8210300

B1058400

C21310420

单位产品利322.9

洞/千元

(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)设：产品三种产品的产量分别为，*，々，为，建立教学模型：

Maxz=3为+2X1+2.9/

SOtO

8内+2占+10&$300

10々+50+8.2400

2x,+13x2+10.r3<420

X1,工2,x3之0

把上述问题化为标准型，用单纯形法解得：

最优解：

(338/15,116/5,22/3,0,0,0/

目标函数最优值为2029/15o

⑵

设备B的影子价格为4/15千元/台时，借用设备的租金为0.3千元每台时。

所以，借用B设备不合笄。

(3)

设备IV,V生产的产量为M，4，系数向量分别为：

/>=(12,5,10/

4=(4,4,12)/

检脸数。尸-0.06,所以生产IV不合算，

%二37/300,生产V合算。

单纯形法计算得：

最优解：

X=(107/4,31/2,0,0,0,0,55/4)r

目标函数最优值为10957/80o

(4)改进后，检验数b：=253/300,大于零。

所以，改进技术可以带来更好的效益.

2o11分析下列参数规划中当t变化时最优解的变化情况。

(1)Maxz(/)=(3—6t)X1+(2—2t)x2+(5-5t)x3(t>0)

s.t.

x,+2x2+xyW430

31+2M<460

X.+4X24420

M,x2,>0

(2)Maxz⑴=(7+2t)x,+(12+t)x2+(10-t)、(t>0)

Sot.

A,+X;+X3工20

2+2x2+x3«30