线性规划课后题答案

P11.3(1)将下列线性规划模型化成标准形式：

maxz=%1-3X2

一M+2X<5

s.t.<2

X)+3々=10

解：令z'=—z,2=工一%’,入2二%2-芯，代入上面的线性规划，得标准形式

minz'=-x[+x[+3x2-3x；

—Xj+Xj+2%2—2%2+七=5

s“X]-X]+3%2-3X2=10

,x2,x2,x3>0

P14:

1、用图解法求解下列线性规划问题:

minf=-3x]+2x2

2%j+4X2<22

-M+4X2<10

s.t.<2xl-x2<7

Xj-3X2<1

x1>0,x2>0

利用图解法:

OPTIMAL

SOLUIION

OBJ-10.00

X1-4.00

X2-1.00

XI

于是得最优解为(4,1),最优值为70。

P15：2

maxz=6xJ-2x2

2x]+x2>2

2x,-3X>6

s.tA9

0<Xj<6

x2>0

解：利用图解法

X2Constraint:ObiectiveFunction:FeasibleArea:

OPTIMAL

SOLUHON

08J-36.00

X1-6.00

X2-0.00

1.60-

140-

120-

1.00-

0.80

060-

040-

020-

XI

于是最优解为(6,0),最优值为36。

P15.3

minx。=_7%[-2x2

2x,+7X2<21

7X]+2X2<21

X,+x2>1

X)>0,x2>0

解：利用图解法求得

Constraint:ObiectiveFunction:FeasibleArea:

OPTIMAL

SOLUTION

OBJ-21.00

X1-3.00

X2-0.00

有无穷多最优解，都落在一个线段上，该线段的两个端点是：

X⑴=(3,0),/)=(7/3,7/3)

于是全部的最优解可以表示成x⑴与x⑵的凸组合，即

x*-axa}+(l-«)x(2),0<a<1.

最优值都是-21。

P16:

1、解：设均表示第i台机床加工第./类产品的产量，于是可得数学模型

maxf=40(%1)+x2))+28(xl2+x32)+32(^3+x43)+72(xl4+x24)+64(x”+x35)+80(x16+x46)

X1]4-x12+芭34-x144-xi5+xi6<850

x2]+x24<700

s.t.<X32+七5460°

X43+”4900

xj>0,j=1,2,3,4,5,6.

P16:

2、解：设,表示第，食品的采购量，于是可得数学模型

minf=CjXj+c2x2H----1-cnxn

E1a/j>Z>,(z=1,2,­••,///)

j=\

Xj>0(7=1,2,--sn).

P18:

9(2)将下列线性规划问题变换成标准形式:

maxz=-211+x2-2x3

-Xj4-x24-x3=4

s-%1+x2-x3<6

王<0,X220,“3无符号限制

解：令M=-芭,工3=E-x；,z=-z,则得

minz=-2x}-x2+2x3-2x3

X+工2+工3一工3二4

X；+工2-％3+工3+f=6

xpx2,x3,x3,r>0

P18:

9(4)将下列线性规划问题变换成标准形式:

min{|x|+|y|+|z|)

x+y<l

2x+z=3

解：此题关键是将目标函数中的绝对值去掉。令

\x\=xr+x",x=xf-xn

\y\=y'+y",y=y-y*

|z|=z'+z”,z=z1-z"

则有

x,x>0“0,x>0

x'=,X=

[0,x<0—x,x<0

y，”o„.0,y>0

y'=<，y-

0,y<0.一y,y<Q

z9z>0I0,z>0

z1=，z”=《

0,z<0—z,z<0

因此v,x”,V,y‘,z',z”都是非负变量。于是原规划可以化成标准形式:

min{x'+x"+y'+y"+z'+z”}

元=1

sr2V——z“=3

P19Ix\，x\，八y\y/\，z\，z\，u>0

13、某养鸡场有一万只鸡，用动物饲料和谷物饲料混合喂养，每天每只鸡平均吃混合饲料

0.5公斤，其中动物饲料占的比例不得少于心。动物饲料每公斤0.2元，谷物饲料每公斤0.16

元。饲料公司每周只保证供应谷物饲料21000公斤。问饲料应怎样混合，才能使每天的总成

本最低？试建立问题的数学模型并求解（图解法）。

解：设养鸡场每天用动物饲料和谷物饲料分别为玉,X2公斤，则问题模型为

minf=0.2^+0.16x2

x}+x2-5000

%1>1000

x2<3000

$>0,x2>0.

用图解法：

Constraint:ObiectiveFunction:FeasibleArea:

5.000.00

OPTIMAL

SOLUTION

0BJ-880.00

4.500.00

X1-2.000.00

X2-X000.00

4.000.00

3.50000

3.00000

2.500.00-

2.000.00-

1.500.00-

1.00000

50000

0.00

求得其最优解为

X]=2000,x2=3000o

P19:14

解：设甲乙厂各处理七、/万立方米/天；总费用z元/天；考虑工厂1与工厂2所在的

两点：

工厂1：

2

<=当二1

5001000

工厂2：

0.8(2—X])+(1.4—%)<2

7001000

0.8X(+x2>1.6

显然：玉《

042,0<x2<1.4

于是建立数学模型为：

minz=1000X1+800x2

%1>1

目标函数

0.8x,+x2>16

0<x,<2,0<x2<1.4

利用图解法，画图

X2Constraint:ObjectiveFunction:FeasibleArea:

OPTIMAL

SOLIHION

OBJ-1,G40.00

X1-1.00

X2-0.80

Q96-

0.80-

0.64

048

求得其最优解为:

x*=(l,0.8)r

最优值为:

Z*=1640.

P37:l

解：线性规划问题

minf=4X]+2x2+x3

2玉+x2+2X3-4

s.t.<3尤1+3X2+£=3

x/0(/=1,2,3)

由第一个约束的3倍减去第二个约束的2倍，得

X

-3X2+43=6

即

33

一尸+与=5(1)

根据上式得到与，再带回第一个约束，整理得

51

』+产=5(2)

由(1)、(2)表示出项，与，带入目标函数，整理得

,713

f----------x

242'

于是整理得基用=(Pi，必)对应的典式为：

713

min/

-2-Tx2

3_3

s.t.—x2+x3=

4-2

51

王+=—

42

X1,%220

根据典式，得基坊的基可行解是

x⑴=(1/2Q3/2)7

同样根据典式，得基可行解x⑴的非基变量X2的检验数是

4=13/4.

由于;l2>。，因此X”)不是最优解。

P37:3

证明：先化成标准形式

minz'=-20X]-10x2-3x3

3xj-3X2+5尤3+x4=50

Xj4-x34-x5=10

s.t.<

X]一九2+4尤3+x6=4

尤/0()=123,4,5,6)

这个显然是可行基8=(〃4，〃5,“6)对应的典式，注意到，

r

22=10>0,p2=(-3,0-l)<0,

因此该线性规划目标值趋于负无穷，原线性规划目标函数趋于正无穷，即没有最优解。证毕。

P46:

1、用单纯形法求解下列线性规划问题:

min/=%)-x2+x3

X]+%2-2X3<2

(1)2xl+x2+x3<3

s.t.<

-Xj+x3<4

x/0(/=1,2,3)

解：先转化成标准形式

minf=$-％+匕

X]+尢2-213+工4=2

2尢]+工2++工5=3

s.t.<

-2+%+工6=4

X7>0(7=1,23,4,5,6)

选（匕,七,4）为初始的基变量组，得单纯形表

X1x2X3x4X5x6

/0-11-1000

X4211-2100

x53211010

x64-101001

/-2-201-100

X2211-2100

x51103-110

x64-101001

/-加-用00-羽如0

x2的於10羽0

X3本013卑0

-卑

x611/300V3如1

最后一个单纯形表的检验数全部mE正，得最£E解为

x*=(0,8/3,l/3)r

最优值为

=-7/3.

minf=3-3x2+x3

(2)[2^+x2-x3=1

x2+3%3+x4=7

x.>0(7=1,23,4)

解：选(F，%)为初始的基变量组，化为典式：

min/=3-3x2+x3

芭+x2/2-x3/2=1/2

s.t.<x2+3X3+X4=7

x.>00=1,2,3,4)

得单纯形表

X1x2x3X4

/303-10

X11-1/20

1

x47013

0

f0-602

20

X211-1

1

X46-204

f-3-500-1/2

x25/2皿10

1A

x33/2-V201

最后一个单纯形表的检验数全部3E正，得最优解为

x*=(0,5/2,3/2,0)7

最优值为

f,=-3.

P63：

1.用两阶段法解下列线性规划问题：

maxx0=%1+5X2+3$

2+2X2+x3=3

2x]—x2=4

Xj>0(/=1,2,3)

解：首先化成标准形式

minx0=f-5x2-3X3

+2X24-x3=3

s.t.<2X1—x2=4

Xj>0(/=1,2,3)

由于上面的规划的系数矩阵中存在一个单位向量P3，因此只需要在添加一个人工变量乙，

构造辅助问题：

minz=x4

x}+2X2+x3=3

一々+%4=4

>0(7=1,23,4)

选当，匕为初始基变量组，化成典式：

minz=4-2玉+x2

$+2尤2+刍=3

2Xj-x2+x4=4

X.>00=1,2,3,4)

于是初始单纯形表为：

X1x2x3X4

zI42-100

X331210

x44-101

Xix2x3x4

Z0000-1

x3105/21

Xi21-V20V2

得辅助问题的最优解，且此时人工变量已经出基，因此得原问题的一个初始可行基（〃3,02）

及其不完全形式的典式（去掉上表中的人工变量列乙及检验数行）：

minx0=-x,-5x2-3x3

s.t.<x]~—x2=2

Xj>0(；=1,2,3)

根据约束条件得j,带入目标函数中，得典式:

X]=2+不工2

minx()=-5+2x2

5..

5元2+无3=1

1c

X]---x2-2

Xj>0(/=1,2,3)

由于检验数%=-2<0,因此应用得到原问题的一个最优解

x*=（2,0,1）。

原问题的最优值为

x；=5.

P63：

3.用两阶段法解下列线性规划问题:

minf=22+4x2

2x1-3X2>2

s.乂-Xj+x2>3

X.>0(；=l,2)

解：先转化成标准形式

min/=2x)+4x2

2x]-3X2-x3=2

-X]+x2-x4=3

xy>0(；=1,2,34)

然后加入人工变量，构造辅助问题：

minz=x5+x6

2元]一X-2

32-X3+X5

s.t/-X]+x2-x4+x6=3

x20(/=123,4,5,6)

选（匕,/）为初始的基变量组，化成典式：

minz=5-+2x2+x3+x4

-3X2—X34-X5=2

-2+X--—3

X20(/=123,4,5,6)

得单纯形表：

Xix2x3x4x5x6

z51-2-1-100

x522-3-1010

x63-110-101

z40-1-3/20

Xi11-蕤01/20

x640-V2-V2-1V21

于是得到辅助问题的最优解为：

元*=(1,0,00,0,4)r

最优值为

♦

z=4A.

由于z*>0,因此原问题无可行解。

P75：

1.对线性规划问题

maxz=3玉+5x2

X,+x3=4

2X2+z=12

s.tA

3x)+2X2+X5=18

x.>0(j=l,2,...,5)

验证3=(P],〃2，〃3)是否为可行基？如果是，求出其典式。

解：对于8=(〃],〃2，〃3)来说，工|,%2，％3为基变量，%4，％5为非基变量。令%=/=0,

代入问题的约束中，得々=6,玉=2,七=2,于是得基解

x=(2,6,2,0,0),

由于xNO,因此3是一个可行基。

下面将问题化成基6的典式。约束条件

2X2+x4=12转换成w+g%=6。

3x,+2X2+x5=18转换成3%一%+/=6,即西一g%+g/=2。

2+尤3=4转换成/十飞匕一大七=2。

22352

目标函数z'=-3工]—5%=—6—匕—七―30H—%|=-36H--xH—匕。于是，基8的

332643

典式为：

・一标5।2

minz二一36H—H—毛

63

11

S.t,X^_~X4+不入5=2

1,

W+耳光4=6

11c

+产—y=2

X.>0(7=1,2,...,5)

P76：

5(1)用单纯形法求解下列线性规划问题：

minz—4玉+3x2+8x3

x,+x3>2

s.t.<x2+2X3>5

x.>0(j=1,2,3)

解：将模型化为

minz=4xj+3x2+8x3

X]+X3-X4=2

X

s.tAx2+23-x5=5

x.>0(j=1,2,3,4,5)

选(玉,工2)为初始的基变量组，化成典式：

minz=23-2x3+4x4+3x5

X)4--x4=2

x2+2X3-x5=5

X.>00=1,2,3,4,5)

单纯形表为：

Xix2X3X4x5

z23002-4-3

Xi210[1]-10

2

X25010-1

z19-200-2-3

x32101-10

1-2102

x2-1

最后一个单纯形表的检验数全部非正，得最优解为x=(0,l,2)；最优值为f=19。

P76：

5(2)用单纯形法求解下列线性规划问题：

min/=3项+4x3+50x5

s/.<—X|+5X3+X5=3

xz>0(j=l,2,3,4,5)

解：选(%,冬)作为初始的基变量组，根据第二个约束求出色，带入目标函数，整理得标准

形式：

69

minf=150--Xj-71x3

121。

X

2i-］々+/元3+尤4=2

33

S—Xj+—尢3+尢5=3

>00=1,2,3,4,5)

于是，得单纯形表:

x

X1x23X4Xs

f15069/207100

.加

x42V2V210

30筑01

x5芈

X1x2X3x4X5

f8-1000-14加

101

x4物-2/3如

x32V2010羽

最后一个单纯形未:的检验数4:部非正，得最优解为

*

X=(0,0,2,1,())7.

最优值为

厂=8.

P79

牝

ma）(z=%+2lx2+3X3+，

虹卜

：3+3X<2

+2X2+2。40

19对线性规划问是不经单纯形迭代，证明

<2x1+々+3火3+2X442D

XJ>0(7=1,2,3,4)

（23'）为其最优］

3,）=匕2恚，并求出最优解。

minz--X1-2x2-3x3—4x4

%+2X+2X+3X+/=20

解：先标准化:234

<2%+x2+3X3+2JC4+4=20

x7>0(J=l,2,3,4,5,6)

令B=（P3，pJ，则

2-3

-32

于是

B-'b=(4,4尸

因此对应的基可行解为

x=(2,620,0)7

检验数为:

2-3Y122310

A=csB-'A-c=(-3,-4)——-(-1,-2-3-4,0,0)

—51—32213201

=(-3/5,-3/5,0,0,-6/5,-l/6)<0

因此（P3，外）为其最优基，%=（0,0,4,41即为最优解。

P99第4题：

判断下列关于对偶问题的说法是否正确：

（1）若原问题存在可行解，则其对偶问题必定存在可行解；（错误，因为对偶问题也可能

无可行解）

（2）若对偶问题无可行解，则原问题必定无可行解；（错误，因为对偶问题也可能无界解,

当然此时对偶问题一定无最优解）

（3）若原问题和对偶问题都有可行解，则两者必都有最优解。（正确）

P99第5题：

设LP有最优解，并设（LP）、

minf-ex

s.t.Ax=d,

x>0

有可行解。试利用对偶理论证明：（LP）‘必有最优解。

证：首先根据LP有最优解及对偶理论知：

maxg=ub

s.t.uA>c,

一定存在最优解，因此一定有可行解。又（LP），的对偶问题是

maxg=ud

s.t.uA>c,

其约束与LP对偶规划的约束一样，因此根据LP的对偶存在可行解推知，其也存在可行解。

结合对偶理论和（LP），存在可行解知，（LP），必有最优解。证毕。

P99第6题：

解：所给线性规划问题的对偶规划是：

ming-30M,+40M2

3M1+2U2>4

u.+2M,>3

s.tA

3M,+3M2>6

u,>0,M2>0

由于对偶规划只有两个决策变量，因此可以利用比单纯形法更简单的图解法来求解。利用图

解法求得：

OPTIMAL

SOUHION

OBJ-70.00

XI-1.00

X2-1.M

对偶问题的最优解为：

u—(1,1).

下面利用互补松弛性求解原问题的最优解。由于

%*=1>0,〃；=1>0

因此它们的互补约束均为紧约束，即

，3x；+x；+3石=30

2x：+2x；+3x；=40

又由于

3“：+2"；=5>4

于是其对偶约束也是紧约束，即

尤：=0(2)

将(2)带入(1),得

x；+3x；=30

*

2x；+3x；=40

求解该方程得：

X；=10,X；=20/3

于是原问题的最优解为：

x*=(0,10