運籌學(xué)的課后習(xí)題

運

籌

學(xué)

的

課

后

習(xí)

題

1.化為標(biāo)準(zhǔn)形式

預(yù)備知識

標(biāo)準(zhǔn)形式為

設(shè)“NO

maxz=g%H-----Fcx

11nn

s上.a、1%i+a1c%c+???+兄—b.

111112112InIn1

l

21i21i+Q2”2人2”2~---=久2n2n2

a.x.+acXH-----Fax=b.

mlmlm2m2mnmnml

x.N0,i=

這類題的做法：1）查看與標(biāo)準(zhǔn)型有哪些不一樣的地方，把它們

先找出來

2）然后再---化為標(biāo)準(zhǔn)形式即可（min令z=-/;

若出現(xiàn)不等式，則引入松弛變量，若金加上一個松弛變量，若

>,減去一個松弛變量;

若變量<0,貝分X：=f.帶入；若變量占無非負限制，令菁=x；-<,

0代入)

(1)引入松弛變量尤5，%(其中尤5，%N。)，令%3=M-尤;

1+

maxz=3欠5x2-4M+4乂'+2x4+0x5

2xj+6X2一乂+乂'+3X4+X5=18

%1—3^2+——2%一元6=13

-%1+4%-+3x2~5元4=9

國,々，乂，乂鼻4，n5，入6>0

(2)引入松弛變量%4，工5,令月=-》2；X3=X'3-X11令Z=-于

maxz=$+5芯+2x；-

3%一2K-4%；+4x；‘+x4=6

2%1+3芯+x；—x；+/=5

石一芯+%：-x；=9

%],，冗；,芯,工4，工5>0

(3)首先查看與標(biāo)準(zhǔn)型中有多少不一樣的

min/=3玉+/+4x3+2x4

sj.3X]+x2+4X3+2X4<1

2x1+3x2-x3-2x4W—51

3x1-2x2+2x3—x42-7

2x1+4x2-3x3+2x4=15

xl,x2>0,x4<0,注意更非負限制

分別令z=-/,有三個不等式所以引入三個松弛變量

(X5,X6,X7>0)x3=-x"?X；=-x4

maxz=-3x]-x2-+4x"+2x；

s.t.%]?。?4乂-4x；-2x；+x5=1

一2X|一3^2+x：一石—2x；—=5]

-3X|+——x；+Xy=7

2否+4%—3x；+3x"—2x：=15

r,

xi,x2,x?!,x",x4,x5,x(),x1>0,

2、圖解法

解題方法：(1)建立直角坐標(biāo)系：以決策變量xl,x2為坐標(biāo)軸。

（2）繪制可行域：

對每個約束條件（包括xi>0）,先取其為等式，并在坐

標(biāo)系中作出相應(yīng)的直線，判定不等式所決定的半平面。

若各約束半平面交出的區(qū)域存在，則其中的點稱為線性規(guī)劃的可

行解，所有可行解組成的集合稱為可行域或可行集。

若不存在，線性規(guī)劃無可行解。

（3）繪制目標(biāo)函數(shù)等值線，并移動求解

①做一條目標(biāo)函數(shù)的等值線。（最好穿過可行域）

②查看目標(biāo)函數(shù)，若求max,確定函數(shù)值增加的方向；

若求min,確定函數(shù)值減少的方向；

③最后，依據(jù)目標(biāo)函數(shù)的要求在可行域內(nèi)平移等值線

（平移到等值線與可行域的最后交點（一個或多個））

2xl-x2=6

xl=33x1+2x2=12

線性規(guī)劃解的種類：

有唯一的最優(yōu)解；有無窮多個最優(yōu)解；沒有有限的最優(yōu)解；沒有

可行解，沒有最優(yōu)解；

線性規(guī)劃的可行域與最優(yōu)解的關(guān)系：（參見22頁，圖2-5）

1.可行域為封閉的有界區(qū)域：

1＞有唯一的最優(yōu)解；

2》有無窮多個最優(yōu)解；

2.可行域為非封閉的無界區(qū)域：

1＞有唯一的最優(yōu)解；

2》有無窮多個最優(yōu)解；

3》沒有有限的最優(yōu)解;（目標(biāo)函數(shù)隨著可行域無限的增大或減少,

可以看作目標(biāo)函數(shù)與可行域的最后的交點在無窮遠處）

3.可行域為空集：

沒有可行解，沒有最優(yōu)解；

線性規(guī)劃解的性質(zhì)：

1.如何找最優(yōu)解：

在可行解中，找目標(biāo)函數(shù)值最大的；

2＞在有限個極點上，找目標(biāo)函數(shù)值最大的；（24頁）

3＞在基本可行解中，找目標(biāo)函數(shù)值最大的那個。（線性規(guī)劃的基

本定理：線性規(guī)劃的基本可行解就是可行域的極點）

三.求基（參考例2.10）

1＞先化為標(biāo)準(zhǔn)形式

maxz=2x1+x2—x3

s.t.xl+x2+2x3+x4=6

x\+4x2-x3+x5=4

xl,x2,x3,x4,x5＞0

_F1121o-

2＞A=14_]o1，任選其中的兩列

Bl=（Pl,尸2）52=（Pl,P3）B3=（Pl,尸4）B4=（P1,P5）85=（P2,尸3）

B6=（P2,尸4）B7=（P2,P5）88=（尸3,尸4）89=（尸3,尸5）filO=（P4,P5）

3》先判斷是否是基？只有基才有基變量和非基變量，才能求出基

本解。

因為忸卜0,i=l,2,…10,所以B,為線性規(guī)劃的基

對于Bl=(Pl,P2),xl,x2為用的基變量，令非基變量x3=x4=x5=Q9

則可得到x(n=(20/3-2/3000)基本解，非可行解。

對于B2=(Pl,P3),xl,x3為4的基變量，令非基變量x2="=x5=0,

則可得到產(chǎn)=(14/302/300)基本可行解，區(qū)為可行基。

同理，基本可行解有

x⑶=(40020)為基本可行解，為可行基。

'5)=(014/920/900)為基本可行解，區(qū)為可行基。

x⑹=(01050)為基本可行解，然為可行基。

產(chǎn)=(00307)為基本可行解，為為可行基。

x(,o)=(O0064)為基本可行解，為可行基。

基本解產(chǎn)=(6000-2)

x⑺=(0600-2)(

x⑻=(00-4140)

4>.求出基本可行解的目標(biāo)函數(shù)值，目標(biāo)函數(shù)值最大的那個基本

可行解為最優(yōu)解，其目標(biāo)函數(shù)值為最優(yōu)值，對應(yīng)的基為最優(yōu)基。

Z⑵=26/3Z⑶=8Z⑸=-2/3,Z⑹=1Z⑼=一3Z。。)=0

所以最優(yōu)解為x⑵=(14/302/300),最優(yōu)值為26/3,最優(yōu)基為

B2O

四，單純形法

步驟：1首先找到一個基本可行解(如標(biāo)準(zhǔn)型中有單位矩陣，選擇為

基，此時得到的基本解一定是基本可行解)，將基變量和目標(biāo)用非基

變量來表示。

2.判斷是否最優(yōu)，（目標(biāo)函數(shù)用非基變量表示以后，目標(biāo)函數(shù)中非基

變量對應(yīng)的系數(shù)稱為檢驗數(shù)），若所有的檢驗數(shù)都小于等于零，則此

時的基本可行解為最優(yōu)解，結(jié)束計算。否則，不是最優(yōu)解，轉(zhuǎn)入3

3判斷進基變量，原則上選擇檢驗數(shù)大于零中任何一個都可以，但是

為了更快的達到最優(yōu)解，一般選擇大于零中最大的那個對應(yīng)的非基變

量作為進基變量。

4.若檢驗數(shù)大于零中，某個檢驗數(shù)對應(yīng)的變量系數(shù)都小于等于零，則

線性規(guī)劃無有限的最優(yōu)解，計算結(jié)束，否則轉(zhuǎn)5

5選擇出基變量，當(dāng)進基變量從零開始增加時，查看那個基變量首先

減少為零，選擇首先降為零的那個變量為出基變量。

6.這樣得到了新的基變量、非基變量。將新基變量及目標(biāo)函數(shù)用新的

非基變量來表示，再令非基變量為零，可以得到新的基本可行解，然

后重復(fù)2-6過程，直到最終結(jié)果算出來為止。

例如

4（2）［法一］

先化為標(biāo)準(zhǔn)形式（引入松弛變量%）

maxz=x2—2x3

s.t.xl+3x2+4x3=1：Fl340

,A=

2x2-x3+x4=12|_02-11

xl,x2,x3>0

1>取可行基為8=（62），（原則上任找一個基本可行解都可以，但

是如果標(biāo)準(zhǔn)型中有單位矩陣，選單位矩陣作為基，那么得到的基

本解一定是基本可行解）。將基變量*多及Z用非基變量如馬來表

示:

z=x2-2x3

xl=12-(3x2+4x3)

%4=12-(2x2-x3)

令非基變量Xy~%2=0，則得到=(12,0,0,12),Z(0)=0?

2>判斷是否是最優(yōu)解？

因為檢驗數(shù)中l(wèi)〉0,所以”不是最優(yōu)解。

選擇進基變量，(原則上選擇檢驗數(shù)大于0中的任何一個都可以，

但為了使得達到最大值更快一些，一般選擇檢驗數(shù)中大于零里最

大的那個非基變量進基)，max{l|l>0}=lf々進基

3>查看檢驗數(shù)大于零的非基變量所對應(yīng)的約束系數(shù)是否都小于

等于零。若是，則該問題無有限的最優(yōu)解。若不是，選擇出

基變量。當(dāng)進基變量開始增加時，選擇首先降為0的基變量

作為出基變量。

1o19

min](,^]3>0,2>0}=4fxi出基

4>將新基變量%及目標(biāo)函數(shù)z用新的非基變量七,為來表示

,/211、

=4_(-§內(nèi)

令非基變量/=玉=0,則新基本可行解”=(0,4,0,4),Z⑴=4,再轉(zhuǎn)2

因為檢驗數(shù)一，￥?(),所以該解為最優(yōu)解。

[法二]

取基為8=仍舄)=￡(單位矩陣)，則建立單純形表如下：

01-20

CBXBbf0

王了2苫3%

0121[3]404*

0%1202-116

-Z001*-20

1X241/314/30

0%4-2/30-11/31

-Z-4-1/30-10/30

注意:

1X21/31%0

0X44-2/30-11/31

-Z-4a20a30

判斷為取何值時，有最優(yōu)解，唯一的最優(yōu)解，有無窮多個最優(yōu)

解，沒有有限的最優(yōu)解。

maxz=3玉+x2

s.t.

課后習(xí)題：求最優(yōu)解：%+2々+%3=4

2%+x2<4

x1,x2>0

5.利用大M法和兩階段法來求解下列模型

min/=3%+x2

-x1+x2<2

x]+x2>l

Xj,x2>0

1＞化為標(biāo)準(zhǔn)形式

maxz=-3玉-x2

s.t.-x,+x4-x=2-11100

239A=[1

Xj+x2-x4=1110-11

xpx2,x3,x4>0

_X)+超+%3=2

2》引入人工變量X5,Xj+x2—x44-x5=1

xpx2,x3,x4,x5>0

【法一］構(gòu)造新目標(biāo)函數(shù)

maxz=-3x,-x2-Mx5

CBXBbr-3-100-Me

XX

玉X23%5

0X32-111002

-MX511[1]0-111*

-zMM-3M-l*0-M0

0X31-2011-1

1X21110-11

-z1-200-11-M

所以，此問題的最優(yōu)解為(0,1,1,0,0),最優(yōu)值為T,因為“5*=0,所以

(0,1,1,0)為原問題的最優(yōu)解，原問題的最優(yōu)值為L

［法二］構(gòu)造新目標(biāo)函數(shù)

max

z=-x5

CBXBb'0000-10

占x2x3%X5

0七2-11100—

-1X51[1]10-111*

-Z11*10-10

0X33021-11

01110-11

-Z00000-1

所以此時最優(yōu)解為(1,0,3,0,0),因為因為毛*=°,所以(1,0,3,0)為原問題

的基本可行解。

CBXBbr-3-1000

百X3%

0X33021-13/2

-3x\11[1]0-11*

-Z302*0-3

0X31-2011

-1x21110-1

-z1-200-1

所以（0』,1,0）為原問題的最優(yōu)解，最優(yōu)值為1.

第二章，課后習(xí)題選解

一、如何來求對偶規(guī)劃

1.化為這種對稱形式

maxz=CTXminf=brY

s.t.AX<b=s.t.A'Y>C

X>0y>0

max匚可相互轉(zhuǎn)化mln0

模式為口工口------------------r>S工作口

si.二<

□>o'7L0>0

2、可相互轉(zhuǎn)化

原問題（對偶）<1偶問題（原問題）

目標(biāo)maxz目標(biāo)minf

約n個

變n個

J>0束j>

量/V。-一

條j<

j無非負限制件j=

約束右端目標(biāo)系數(shù)

約束右端

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

約m個變m個

束i工z>0

條i2V喳i<0

件i=i無非負限制

做這類題時，可以直接用上面的表格(這種容易出錯)；一

般是將原問題為max(min),首先化為“2),然后利用上面的表

格得到對偶問題；

min/=5%+2y2

f+為2一3

1.s.t.2%+3y225

2。

2.(P)

maxz=xl+2x2+X3

minf=Sy+6y

s.t.i2

2%一必=1

2x+毛=8

}%+2%=2

一%+X+3J=6s.t.

2233y2=1

再，馬均無非負限制%,當(dāng)均無非負限制

3.

maxz=芭+2X2-3x3+4x4

s.t.—X]+々一退一3%=5

6%+7々-&+5%-8

12%一9工2+7X3+6/410

演，/羽將后限制

Max值形式，先化為工

maxz=玉+2X2-3x3+4x4

s.t.-x}+x2-x3-3X4=5

—6斗—7%2+X3-54<—8

P12xl-9X2+7&+65<10

%，*3§S海區(qū)限制

min/=5%—8y2+10%

s.t.-yi-6y2+12y3>1

1%-7y2-9%=2

_%+>2+7%>-3

-3%-5y2+6%=4

%無非負限制,y2y3>0

4.

minf=-3%]+2x2+5x3-7x4-8x5

s[.OX]+x,一當(dāng)+3%4—4/=—6

2%]+3X-3X-X+0X>2

2345因為min,所以先將約束條

-1]+0x9+213—2%4+0%54—5

件盡量化為2

-2<%]<10

5<x2<25

minf=—3不+2x2+5x3—7x4—8x5

s/.OX]+無？—尤3+3A?4—4芯5——6

2x1+3X2—3X3—尤4+Ox5>2

%1—Ox?—2尤3+2犬4—Ox5N5

—Xj>—10

X]N—2

尤225

一%2——25

XL，%%為無非負限制，%之0

maxz=-63+2為+5%-1。、4-2y5+5%一25%

s￡2y2+%-%+為=-3

M+3y2+兒一，7V2

_%-3%_2y3=5

3%一、2+2%=-7

-4y=-8

必?zé)o非負限制，%，%加％為為20

2.判斷原問題是否有最優(yōu)解,

此類問題的知識點:

考察推論2?P⑴有可行解，若?看最優(yōu)解()傷中行解

‘'匕"其逆否：無可行解，則原問題無有限的最優(yōu)解。

minf=2yl+%

s.t.-y{-2y2>2

-

1.(0,0,0)為原問題的可行解，其對偶問題為：y,+y2>2,顯

%-％20

M，>2

然對偶問題沒有可行解，所以原問題沒有有限的最優(yōu)解。

maxz=-4^+6為

+y2<-1

2.(2,2,0)為原問題的可行解，其對偶問題為-5+2%42,

V41

弘NO,為為無非負限制

顯然(1,3)為對偶問題的可行解，所以原問題有最優(yōu)解。

maxz=5%+6%+8%+7%

%+為《1

3.s.t.<為+為準(zhǔn)形式:

maxz=5必+6y2+8%+7y4

，+%+%=1

%+%+%=1

%+%+%=1

%+%+%=1

?，%，%，,4，為，丁6，〉7，為2°

4.應(yīng)用對偶性質(zhì)，直接寫出原問題的最優(yōu)值

這里主要考察：

定理政問題有最例解有最優(yōu)解^電兩者最優(yōu)解的目標(biāo)函數(shù)值相等。

maxz=50yl

s/.5yl<10

對偶問題：一7必,4,顯然°"為"所以對偶問題的最

3環(huán)53

%20

優(yōu)解為弘=2,則對偶問題的最優(yōu)值為z*=250/3,所以由定理3.2,

3

原問題的最優(yōu)值為250/3。

5.對偶單純形法:

1.首先化為標(biāo)準(zhǔn)形式:

maxf=5%1+2x2+4x3

3否+々+2X3>4

6%]+3%2+5/>10

x1,JC2x3>0

maxz=-5x]-2x2-4x3

3%+x2+2X3-x4=4

6xj+3X2+5X3-X5=10

xpx2x3,x4,x5>0

maxz=-5%一2x2-4x3

—3X|—%2—2/+%=—4

s.t.<—6X]—3%2—513+%——10

xpx2x3,x4,x5>0

建立對偶單純形表：

min{-4,—10卜4<0,—10<0}=—10—>演出基

-5-2-4.2

min{—,—,—卜6Vo—3<0,一5<0=}---->

—6—3—53

b'

CBXB-5-2-400

xl工2X3X4X5

0X4-4-3-1-210

0XS-10-6[-3]-501

-z

0-5-2-400

min{-4,-10|-4<0,-10<0}=-10f演出基

-5-2-42

min{—,—,-----6<0—3<0,—5<0=}—>%基

-6-3-53

0X4-2/3[-1]0-1/31-1/3

-2工210/3215/30-1/3

-Z20/3-10-2/30-2/3

min{-2/3卜2/3v0}=-2/3->與出基

.—1—2/3—2/3i,濟其

mm{f—1-1<0,-2/3<0}=1fx嚴基

-JL—1J—1/J

-5X]2/3101/3-11/3

-2*2201121/3

-Z

22/300-1/3-1-1/3

所以標(biāo)準(zhǔn)型的最優(yōu)解為(2/3,2,0,0,0),),最優(yōu)值為-22/3

原問題的最優(yōu)解為(2/3,2,0,0,0)0,),最優(yōu)值為22/3

=一巧-

maxz2X2-3x3

2工1-x2+x3-x4=4

x1+x2+2X3+x5=8

2.先化為標(biāo)準(zhǔn)形式:

x2-x3+x6=2

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

一％]-

maxz=2X2-3x3

0X5601/25/2-1/210

0X6201-1001

-z20-5/2-5/2-1/200

所以標(biāo)準(zhǔn)型的最優(yōu)解為(0,2,0,0,6,2),),最優(yōu)值為-2

原問題的最優(yōu)解為(0,2,0,(),6,2),),最優(yōu)值為2

用對偶單純形法求解

minw=2xi+3x2+4x3

Xi+2x2+X3三1

2xi-X2+3x3三4

Xi,x2,X3三0

解：maxz=-2xi-3x2-4x3+0x4+0x5

z*

_Xi_2x2-X3+X4=-1

<-2xi+X2-3x3+Xs=~4

IXi,x2,x3,x4,X520

-2-3-400

CBXBbxlx2x3x4X5

0x4-1-1-2-110

0x5-4**[-2]1-301

-z0-2-3-400

min{-l,-4|-l<0,-4<0}=-4->/出基

.-2-4,-2

min{=，F(xiàn)|-2<0,-3<0}=——>x,進基

0x410-5/21/21-1/2

-2xl21-1/23/20-1/2

-z40-4-10-1

所以標(biāo)準(zhǔn)型的最優(yōu)解為(2,0,0,1,00),最優(yōu)值為-4

原問題的最優(yōu)解為(2,0,0,1,00),最優(yōu)值為4

6.初始單純形表:

b

XB

cB230000

/X2X、*4X5X6

0X312221000

0X48120100

0Z16400010

012040001

-z0230000

最優(yōu)單純形表

b

XB

CB230000

X1X2*4X6

0X30001-1-1/40

2X]410001/40

0*64000-21/21

3X220101/2-1/80

-z-14000-3/2-1/80

怎樣找初始基矩陣？只要在最優(yōu)單純形表中將基變量按順序找到

（X3,X1，X6,X2），然后按順序在初始單純形表中將這些變量對應(yīng)的系

數(shù)向量寫下來即可。

1202

0102

B=

0400

0014

怎樣找其逆矩陣？只要在初始單純形表中找到單位矩陣所在的變量

（也要注意順序）（0，*4，*5，尤6），然后按順序在最優(yōu)單純形表中將

這些變量對應(yīng)的系數(shù)向量寫下來即可。

1-1-1/40-

,001/40

Bi=

0-21/21，

01/2-1/80

設(shè)A=（4,舄，尸3,居，尸5,尸6），

-1

00

B1P=

40-2

01/2

1—1-1/40一o--1/4-

001/4001/4

…=—

0-21/2111/2

01/2-1/800-l/8_

1)G為基變量的目標(biāo)系數(shù)，則G變化會改變非基變量的檢驗

數(shù)％q,不會影響基變量的檢驗數(shù)。

Jfq+Ie1

保持最優(yōu)解不變的條件：

r

%Tq=-以+JC)B'P4=C4-C/B-'P,-ACVP4=(T4-dCB'P,=-3/2+^<0

生.仇飛_(《+加斷？=6_品用？_加，？=0_加甘卬5=_]/8+，]40

<=>Ac.<—

12°

C2為基變量的目標(biāo)系數(shù),則C2變化會改變非基變量的檢驗數(shù)

。4，，，不會影響基變量的檢驗數(shù)。

保持最優(yōu)解不變的條件：

「d=。4-爆+/C)B?=c「CWA-4”A=/一/CMA=一3/2+%40

%4G=c§-+4C)B?=05-CJB?-=%-=-1/8―組40

=——<Ac^<12

22

。2=3f弓=5,4。2=3,則

亍4=-3/2+：*2=-1<0;萬5=-1/8-：42

=-l/8-l/4*2=-5/8<0

1-1/40

001/40

B1

2)01/21

01/2-1/80

設(shè)

b—>b=

,則

-1/400

1/400

xl1

XgfNB=B-b=B(b+Ab)=XB+B

1/21叫

-1/800

一:皿

4d—Ab^

>o

4+—483

2—Ab^

83

則，—8<3-0

5）增加一個約束條件：2xt+2AX2<12,對最優(yōu)解產(chǎn)生的影響

加入到原最優(yōu)單純形表中，得到

2xx+2.4X2+x7=12,

b

XB

CB2300000

X]X2X4X5乙X1

0X30001-1-1/400

2%]410001/400

0*64000-21/210

3