線性規(guī)劃課后題答案

P11.3(1)將下列線性規(guī)劃模型化成標(biāo)準(zhǔn)形式：

maxz=%1-3X2

一M+2X<5

s.t.<2

X)+3々=10

解：令z'=—z,2=工一%’,入2二%2-芯，代入上面的線性規(guī)劃，得標(biāo)準(zhǔn)形式

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、用圖解法求解下列線性規(guī)劃問題:

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

于是得最優(yōu)解為(4,1),最優(yōu)值為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

于是最優(yōu)解為(6,0),最優(yōu)值為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

有無窮多最優(yōu)解，都落在一個線段上，該線段的兩個端點是：

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

于是全部的最優(yōu)解可以表示成x⑴與x⑵的凸組合，即

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

最優(yōu)值都是-21。

P16:

1、解：設(shè)均表示第i臺機(jī)床加工第./類產(chǎn)品的產(chǎn)量，于是可得數(shù)學(xué)模型

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、解：設(shè),表示第，食品的采購量，于是可得數(shù)學(xué)模型

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

E1a/j>Z>,(z=1,2,-??,///)

j=\

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

P18:

9(2)將下列線性規(guī)劃問題變換成標(biāo)準(zhǔn)形式:

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)將下列線性規(guī)劃問題變換成標(biāo)準(zhǔn)形式:

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

x+y<l

2x+z=3

解：此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對值去掉。令

\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”都是非負(fù)變量。于是原規(guī)劃可以化成標(biāo)準(zhǔn)形式:

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

元=1

sr2V——z“=3

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

13、某養(yǎng)雞場有一萬只雞，用動物飼料和谷物飼料混合喂養(yǎng)，每天每只雞平均吃混合飼料

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

元。飼料公司每周只保證供應(yīng)谷物飼料21000公斤。問飼料應(yīng)怎樣混合，才能使每天的總成

本最低？試建立問題的數(shù)學(xué)模型并求解（圖解法）。

解：設(shè)養(yǎng)雞場每天用動物飼料和谷物飼料分別為玉,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

求得其最優(yōu)解為

X]=2000,x2=3000o

P19:14

解：設(shè)甲乙廠各處理七、/萬立方米/天；總費用z元/天；考慮工廠1與工廠2所在的

兩點：

工廠1：

2

<=當(dāng)二1

5001000

工廠2：

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

7001000

0.8X(+x2>1.6

顯然：玉《

042,0<x2<1.4

于是建立數(shù)學(xué)模型為：

minz=1000X1+800x2

%1>1

目標(biāo)函數(shù)

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

求得其最優(yōu)解為:

x*=(l,0.8)r

最優(yōu)值為:

Z*=1640.

P37:l

解：線性規(guī)劃問題

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)

根據(jù)上式得到與，再帶回第一個約束，整理得

51

』+產(chǎn)=5(2)

由(1)、(2)表示出項，與，帶入目標(biāo)函數(shù)，整理得

,713

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

242'

于是整理得基用=(Pi，必)對應(yīng)的典式為：

713

min/

-2-Tx2

3_3

s.t.—x2+x3=

4-2

51

王+=—

42

X1,%220

根據(jù)典式，得基坊的基可行解是

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

同樣根據(jù)典式，得基可行解x⑴的非基變量X2的檢驗數(shù)是

4=13/4.

由于;l2>。，因此X”)不是最優(yōu)解。

P37:3

證明：先化成標(biāo)準(zhǔn)形式

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)對應(yīng)的典式，注意到，

r

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

因此該線性規(guī)劃目標(biāo)值趨于負(fù)無窮，原線性規(guī)劃目標(biāo)函數(shù)趨于正無窮，即沒有最優(yōu)解。證畢。

P46:

1、用單純形法求解下列線性規(guī)劃問題:

min/=%)-x2+x3

X]+%2-2X3<2

(1)2xl+x2+x3<3

s.t.<

-Xj+x3<4

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

解：先轉(zhuǎn)化成標(biāo)準(zhǔn)形式

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

最后一個單純形表的檢驗數(shù)全部mE正，得最￡E解為

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

最優(yōu)值為

=-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

最后一個單純形表的檢驗數(shù)全部3E正，得最優(yōu)解為

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

最優(yōu)值為

f,=-3.

P63：

1.用兩階段法解下列線性規(guī)劃問題：

maxx0=%1+5X2+3$

2+2X2+x3=3

2x]—x2=4

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

解：首先化成標(biāo)準(zhǔn)形式

minx0=f-5x2-3X3

+2X24-x3=3

s.t.<2X1—x2=4

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

由于上面的規(guī)劃的系數(shù)矩陣中存在一個單位向量P3，因此只需要在添加一個人工變量乙，

構(gòu)造輔助問題：

minz=x4

x}+2X2+x3=3

一々+%4=4

>0(7=1,23,4)

選當(dāng)，匕為初始基變量組，化成典式：

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

得輔助問題的最優(yōu)解，且此時人工變量已經(jīng)出基，因此得原問題的一個初始可行基（〃3,02）

及其不完全形式的典式（去掉上表中的人工變量列乙及檢驗數(shù)行）：

minx0=-x,-5x2-3x3

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

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

根據(jù)約束條件得j,帶入目標(biāo)函數(shù)中，得典式:

X]=2+不工2

minx()=-5+2x2

5..

5元2+無3=1

1c

X]---x2-2

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

由于檢驗數(shù)%=-2<0,因此應(yīng)用得到原問題的一個最優(yōu)解

x*=（2,0,1）。

原問題的最優(yōu)值為

x；=5.

P63：

3.用兩階段法解下列線性規(guī)劃問題:

minf=22+4x2

2x1-3X2>2

s.乂-Xj+x2>3

X.>0(；=l,2)

解：先轉(zhuǎn)化成標(biāo)準(zhǔn)形式

min/=2x)+4x2

2x]-3X2-x3=2

-X]+x2-x4=3

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

然后加入人工變量，構(gòu)造輔助問題：

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

于是得到輔助問題的最優(yōu)解為：

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

最優(yōu)值為

?

z=4A.

由于z*>0,因此原問題無可行解。

P75：

1.對線性規(guī)劃問題

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轉(zhuǎn)換成w+g%=6。

3x,+2X2+x5=18轉(zhuǎn)換成3%一%+/=6,即西一g%+g/=2。

2+尤3=4轉(zhuǎn)換成/十飛匕一大七=2。

22352

目標(biāo)函數(shù)z'=-3工]—5%=—6—匕—七―30H—%|=-36H--xH—匕。于是，基8的

332643

典式為：

?一標(biāo)5?2

minz二一36H—H—毛

63

11

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

1,

W+耳光4=6

11c

+產(chǎn)—y=2

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

P76：

5(1)用單純形法求解下列線性規(guī)劃問題：

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

最后一個單純形表的檢驗數(shù)全部非正，得最優(yōu)解為x=(0,l,2)；最優(yōu)值為f=19。

P76：

5(2)用單純形法求解下列線性規(guī)劃問題：

min/=3項+4x3+50x5

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

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

解：選(%,冬)作為初始的基變量組，根據(jù)第二個約束求出色，帶入目標(biāo)函數(shù)，整理得標(biāo)準(zhǔn)

形式：

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羽

最后一個單純形未:的檢驗數(shù)4:部非正，得最優(yōu)解為

*

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

最優(yōu)值為

廠=8.

P79

牝

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

虹卜

：3+3X<2

+2X2+2。40

19對線性規(guī)劃問是不經(jīng)單純形迭代，證明

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

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

（23'）為其最優(yōu)］

3,）=匕2恚，并求出最優(yōu)解。

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

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

解：先標(biāo)準(zhǔn)化: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尸

因此對應(yīng)的基可行解為

x=(2,620,0)7

檢驗數(shù)為:

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，外）為其最優(yōu)基，%=（0,0,4,41即為最優(yōu)解。

P99第4題：

判斷下列關(guān)于對偶問題的說法是否正確：

（1）若原問題存在可行解，則其對偶問題必定存在可行解；（錯誤，因為對偶問題也可能

無可行解）

（2）若對偶問題無可行解，則原問題必定無可行解；（錯誤，因為對偶問題也可能無界解,

當(dāng)然此時對偶問題一定無最優(yōu)解）

（3）若原問題和對偶問題都有可行解，則兩者必都有最優(yōu)解。（正確）

P99第5題：

設(shè)LP有最優(yōu)解，并設(shè)（LP）、

minf-ex

s.t.Ax=d,

x>0

有可行解。試?yán)脤ε祭碚撟C明：（LP）‘必有最優(yōu)解。

證：首先根據(jù)LP有最優(yōu)解及對偶理論知：

maxg=ub

s.t.uA>c,

一定存在最優(yōu)解，因此一定有可行解。又（LP），的對偶問題是

maxg=ud

s.t.uA>c,

其約束與LP對偶規(guī)劃的約束一樣，因此根據(jù)LP的對偶存在可行解推知，其也存在可行解。

結(jié)合對偶理論和（LP），存在可行解知，（LP），必有最優(yōu)解。證畢。

P99第6題：

解：所給線性規(guī)劃問題的對偶規(guī)劃是：

ming-30M,+40M2

3M1+2U2>4

u.+2M,>3

s.tA

3M,+3M2>6

u,>0,M2>0

由于對偶規(guī)劃只有兩個決策變量，因此可以利用比單純形法更簡單的圖解法來求解。利用圖

解法求得：

OPTIMAL

SOUHION

OBJ-70.00

XI-1.00

X2-1.M

對偶問題的最優(yōu)解為：

u—(1,1).

下面利用互補(bǔ)松弛性求解原問題的最優(yōu)解。由于

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

因此它們的互補(bǔ)約束均為緊約束，即

，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

于是原問題的最優(yōu)解為：

x*=(0,10