2021年度大學運籌學課程知識點總結

1.用圖解法求解下列線性規(guī)劃問題，并指出問題具備惟一最優(yōu)解、無窮多最優(yōu)解、無界解還是

無可行解。

maxz=%]+/

6匹+10%2(120

<5<Xj<10

3<x2<8

2.將下述線性規(guī)劃問題化成原則形式。

minz=-3%]+4x2-2x3+5x4

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

%1+%2—％3+2匕<14

（1）4

—2X1+3%2+13—%4之2

xl,x2,x3>0,"無約束

解：令z'=_z,x4=x4-x4

ttt

maxz'=31]-4x2+2x3-5x4+5x4

廣tIt

—4xj+%2—2%+%—%=2

Xj+%2—X3+2%4—2%4+￡=14

—2%|+X3—%4+%4—

3%9+=2

龍1，龍2，％3，入4，%；，%5，％620

3.分別用圖解法和單純形法求解下述線性規(guī)劃問題，并對照指出單純形表中各基可行解相應圖

解法中可行域哪個頂點。

maxz=10x)+5x2

玉+

34X2<9

<5X[+2X2<8

X],々-0

②單純形法：將原問題原則化:

maxz=10^+5x2

3x1+4X2+9=9

<5x1+2X2+x4=8

G10500相應圖解法

Bb0

cBXlX2X3X4中點

0X3934103

0X48[5]2018/5o點

010500

0X321/50U4/5J1-3/53/2

10Xi8/512/501/54c點

Gj-16010-2

5X23/2015/14-3/14

1()Xl110-1/72/7B點

Gj35/200-5/14-25/14

最優(yōu)解為(1,3/2,0,0),最優(yōu)值Z=35/2。

單純型法環(huán)節(jié)：轉化為原則線性規(guī)劃問題；找到一種初始可行解，列出

初始單純型表；最優(yōu)性檢查，求cj-zj,若所有值都不大于0,則表中

解便是最優(yōu)解，否則，找出最大值那一列，求出bi/aij,選用最小相

相應xij,作為換入基進行初等行變換，重復此環(huán)節(jié)。

4.寫出下列線性規(guī)劃問題對偶問題。

/〃，1

minz=>匯%

Z=1j=\

%/=4(i=l,…3篦)

/=1

(1)

/=]

Xjj>0。=1,…，帆;/=1,)

maxw=Z《y+tn

i=\i=\

c

yt+ym+jijG==???,?)

七,y.無約束

n

maxz=Vc：x：

JJ

j=l

n

ZauXJ-bi(i=1,…叫<m)

(2)〃

(z=m,4-1,m+2,?一,m)

s.t.<1a/j="A

Xj>00=1,???巧<〃)

x.無約束(j=%+1,???，.)

m

minw=/biyi

i=l

C/=I,2，F(xiàn)<〃)

i=l

(J=?,+1,…,〃)

s.t.\^aijyi=cj

1=1

XNO(i=1,2,…叫<加)

必無約束(i=+1,---,m)

5.給出線性規(guī)劃問題

maxz=2X]+4x24-x34-x4

x1+3X2+x4<8

2x]+x2<6

s.f.<x2+x3+x4<6

玉+x2+x3<9

Xj20(/=l,…4)

規(guī)定：Q）寫出其對偶問題；（2）己知原問題最優(yōu)解為X*=（2,2,4,0）、試依照對偶理論，直

接求出對偶問題最優(yōu)解。

解:

minw=8y+6%+6%+9J4

M+2%+%22

3y,+%+必+”24

s.t.<乃+”21

M+%之1

y.>0G=l,--4)

(2)由于%,％2，芻>0,第四個約束取等號，依照互補松弛定理得:

,M+2y2+%=2

3M+為+%+%=4

V

%+以=1

.+>4=°

求得對偶問題最優(yōu)解為：Y*1,0),最優(yōu)值minw=16。

例已知原問題

Maxz=X]+2X2+3X3+4x4

x(+2X2+2x,+3x4W20

lx,+x2+3X3+2X4W20

X[、x2>X3、x4>0

和對偶問題

Minw=20y,+20y2

+

yt2y221

2y,+y2>2

2y「3y2二3

3yi+2y2>4

yi'y2^°

已知對偶問題的最優(yōu)解y】=1.2、y2=0.2,最優(yōu)值minw=28,

求原問題的最優(yōu)解及最優(yōu)值。

可用如下方法求解：

引入將原問題和對偶問題化為標準形式。

Maxz=x{+2X2+3X3+4X4

X]+2X2+2X3+3X4+x5=20

2xj+x2+3X3+2X4+x6=20

XpX2>X3、x4>x5>x6>0

和

Minw=20y1+20y2

y1+2y2一丫3=1

2y1+y2-y4=2

2y/3y2~y5=3

3y"2y2-y6=4

y2'y3'y4、y$、y6^°

(1)yj=1.2>0,而與X5中至少有一個為零，故X5=0。

(2)同理，y2=0.2>0,所以*6=0。

(3)對偶問題的第一個約束條件在取最優(yōu)值時

y,+2y2=1.2+2X0.2=1.6>1

這就表示該約束條件的松弛變量：

y3=1.6—1=0.6>0

丫3與X]中至少有一個為零，故X[=()。

(4)同理，對于第2個約束條件在取得最優(yōu)值時

2y(+y2=2X1.2+0.2=2.6>2

y4=2.6—2=0.6>0

丫4與X2中至少有一個為零，故X2=0。

（5）同理，對于第3個約束條件在取得最優(yōu)值時

2yt+3y2=2X1.2+3X0.2=3

丫5=3-3=0

丫5與X3中至少有一個為零，故X3X）或者X3=0。

（6）對于第4個約束條件的分析也可得到x-0或者X4=00

對于（5）和（6）的分析，對于確定原問題的最優(yōu)解沒有

任何幫助。但從（1）到（4）的分析中得知，原問題取得

最優(yōu)解時：

x-=0,x6=0,X]=0,x2=0

代入原問題的約束方程組得：

2X3+3X4=20

3X^+2X4=20

解此方程組，可求得原問題的最優(yōu)解為：

X]=0,x2=0，X3=4*X4=4>x5=0,x6=0

弱對偶性推論：

（1）原問題任一可行解目的函數(shù)值是其對偶問題目的函數(shù)值下界；反之對偶問題任

一可行解a的函數(shù)值是其原問題目的函數(shù)值上界

（2）如原問題有可行解且目的函數(shù)值無界（具備無界解），則其對偶問題無可行解；

反之對偶問題有可行解且目的函數(shù)值無界，則其原問題無可行解。

注意：本點性質逆不成立，當對偶問題無可行解時，其原問題或具備無界解或無可

行解，反之亦然。

（3）若原問題有可行解而其對偶問題無可行解，則原問題目的函數(shù)值無界；反之對

偶問題有可行解而其原問題無可行解，則對偶問題目的函數(shù)值無界。

強對偶性（或稱對偶定理）

若原問題及其對偶問題均具備可行解，則兩者均具備最優(yōu)解，且它們最優(yōu)解目

的函數(shù)值相等。

互補松弛性

在線性規(guī)劃問題最優(yōu)解中，如果相應某一約束條件對偶變量值為非零，則該約

束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其相應對偶變量一定為零。

影子價格

資源市場價格是其價值客觀體現(xiàn)，相對比較穩(wěn)定，而它影子價格則有賴于資

源運用狀況，是未知數(shù)。因公司生產任務、產品構造等狀況發(fā)生變化，資源影

子價格也隨之變化。

影子價格是一種邊際價格。

資源影子價格事實上又是一種機會成本。隨著資源買進賣出，其影子價格也將

隨之發(fā)生變化，始終到影子價格與市場價格保持同等水平時，才處在平衡狀態(tài)。

生產過程中如果某種資源未得到充分運用時，該種資源影子價格為零；又當資源

影子價格不為零時，表白該種資源在生產中已耗費完畢。

影子價格反映單純形表中各個檢查數(shù)經(jīng)濟意義。

普通說對線性規(guī)劃問題求解是擬定資源最優(yōu)分派方案，而對于對偶問題求解則是擬

定對資源恰當估價，這種估價直接涉及資源最有效運用

對偶單純型法：轉化成原則線性規(guī)劃問題；擬定換入基變量，bi不大于。中最小那

一排，再求(cj-zj)/aij,且aij<0,找出最小值，這相應xi便是換入基，若所有

bi都不不大于0,則找到了最優(yōu)解

7下列表分別給出了各產地和各銷地產量和銷量，以及各產地至各銷地單位運價，試用表上作

業(yè)法求最優(yōu)解。

注意要基可行解個數(shù)一定是行列變量數(shù)減一

地

BIBB產量：

產地B234

A,41468

A212508

A337514

銷量656320

解：

(1)擬定初始方案

西北角法:

銷地

BiBBB產量

產地234

Ai628

358

A2

A3134

銷量656320

最小元素法:

銷地

BiBBB產量

產地234

A]538

A2538

A3134

銷量656320

沃格爾法:

地行罰數(shù)

BiBB,B產量

產241234

14111416

8③022

A|53

11121510

A811@

262

[_3_Lz_|_5_

A41244

331

銷量656320

12111

列

2②11

罰

311

數(shù)

41⑤

8.下表給出一種運送問題及它一種解，試問：

(1)表中給出解與否為最優(yōu)解？請用位勢法進行檢查。

(2)若價值系數(shù)C24由1變?yōu)?,所給解與否仍為最優(yōu)解？若不是，祈求出最優(yōu)解。

(3)若所有價值系數(shù)均增長1,最優(yōu)解與否變化？為什么？

(4)若所有價值系數(shù)均乘以2,最優(yōu)解與否變化？為什么？

B)B.,產量

產地B2B4

4146

Ai8

53

6

12110

A282

37514

A331

銷量856322

解：（1）

地

Bi產量Ui

產地B2B3B4

446

Ai180

53

26

11101

A282

375141

A331

銷量856322

Vi0140

空格檢查數(shù)為:

46

01

25

所有檢查數(shù)均不不大于等于零，該方案為最優(yōu)方案。

（2）若價值系數(shù)C24由1變?yōu)?,

66

-2-1

45

由于有檢查數(shù)不大于零，因此此方案不是最優(yōu)方案。

5(-2)3(+2)

8(+2)2(-2)

3(-2)1(+2)

調節(jié)為:

35

82

13

空格檢查數(shù)為:

46

12

25

所有檢查數(shù)均不大于等于零，該方案為最優(yōu)方案。

minz=3xl+5x4+8xl+2x2+lx5+3xl=43。

（3）不變化，不影響檢查數(shù)大小。

（4）不變化，不影響檢查數(shù)符號。

解最優(yōu)性檢查：

1.閉回路法：找各個非基變量閉合回路，依次加減求檢查數(shù)，是先減再

加，若所有檢查數(shù)值都全非負，那么此可行解是最優(yōu)解。

2.位勢法（對偶變量法）：增長位勢列ui和位勢行vj;計算位勢，ui+vj=

基可行解相應運費，指定其中某一值為0,算出其她幾位值，填入表中；

計算檢查數(shù)，某非基變量相應運費減相應位勢行和位勢列，若檢查數(shù)全

為非負，則為最優(yōu)解。

（檢查數(shù)都是非基變量通過解決后值，解決過程中應用是基變量）

解改進：1.以檢查數(shù)不大于Oxi為換入基（取最小那個）

2.找此xi閉合回路，以xi為始沿順逆時針方向把定點依次編號

3.在所有偶數(shù)頂點中，找出運送量至少頂點作為xi換出變量

4.將基數(shù)頂點運送量增長xj,偶數(shù)頂點運送量減少xj,重新得到

一組新方案

5.進行解最優(yōu)性檢查

9.公司決定使用1000萬元新產品開發(fā)基金開發(fā)A,B,C三種新產品。經(jīng)預測預計，開發(fā)A,B,

C三種新產品投資利潤分別為5%、7%、10%。由于新產品開發(fā)有一定風險，公司研究后擬定

了下列優(yōu)先順序目的：

第一，A產品至少投資300萬元；

第二，為分散投資風險，任何一種新產品開發(fā)投資不超過開發(fā)基金總額35%；

第三，應至少留有10%開發(fā)基金，以備急用；

第四，使總投資利潤最大。

試建立投資分派方案目的規(guī)劃模型。

解，設A,B,C三種新產品開發(fā)投資額分別為王,乙,七萬元，目的規(guī)劃模型為:

milled；,舄("；+"；+若)%,P4dA}

項+4--4*=300

X,+一玄=1000x35%

x2-d；=1000x35%

s.tA/+/-d；=1000x35%

1000-2-/-W+4-d；=1000x10%

5%否+7%X2+10%x3+惡-霖=1000x10%

+

x1,x2,x3,jr,J/>0(/=1,???,6)

PI是優(yōu)先因子，關系為I越小，則有絕對優(yōu)先性，尚有一種是相

對優(yōu)先性，用權系數(shù)來表達

目的規(guī)劃普通格式;min{pld+或dT（要明白為什么是寫d+或d-,

min里d是要取值為零，即若不等式要不不大于零時，則寫d-）;必要

要滿足絕對約束，尚有目的約束；xj>0,d+,d->0

目的規(guī)劃圖解法：先畫絕對約束可行域，然后按照優(yōu)先性優(yōu)先考慮

某個目的約束，隨著min系數(shù)中d+或者d-增大移動曲線，畫出最適當

那條，直到最后

1o.用割平面法解下列整數(shù)規(guī)劃:

maxz=xx+x2

2x,+x<6

(1)2

s,t.<4芭+5尤2420

苞之0,且為整數(shù)

解：引進松弛變量七,工4,將問題化為原則形式，用單純形法解其松弛問題。

Ci1100

0

CBXBbXlX2X3X4

0X36[2]1103

0X42045015

51100

1Xl311/21/206

0X480[3]-218/3

501/2-1/20

1X]5/3105/6-1/6

1X28/301-2/31/3

500-1/6-1/6

找出非整數(shù)解變量中分數(shù)某些最大一種基變量（x2）,并寫下這一行約束:

21仁2

---心—九二2一

~333

將上式中所有常數(shù)分寫成整數(shù)與一種正分數(shù)值之和得：

々+11+川+(0+：1卜=(2+:2

33

將上式中分數(shù)項移到等式右端，整數(shù)項移到等式左端得:

g211

X2-X3-2=-一產一產

得到割平面約束為:

11

一產_產

引入松弛變量七,得割平面方程為：

2

3

?11000

b

CBXBXlX2X3X4x5

1Xl5/3105/6-1/60

1X28/301-2/31/30

0X5-2/300[-1/3]-1/31

500-1/6-1/60

Oj/ari1/21/2

1X)0100-15/2

1X240101-2

0X320011-3

50000-1