北外奧鵬作業(yè)運(yùn)籌學(xué)講述

運(yùn)籌學(xué)作業(yè)精講第一單元某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，其單位利潤(rùn)分別為20元和30元。每生產(chǎn)一件甲產(chǎn)品需勞動(dòng)力3個(gè)，原材料2千克，設(shè)備4小時(shí)；每生產(chǎn)一件乙產(chǎn)品需勞動(dòng)力7個(gè)，原材料4千克，設(shè)備3小時(shí)。企業(yè)現(xiàn)有勞動(dòng)力240個(gè)，原材料150千克，設(shè)備可用時(shí)間為250小時(shí)。問：如何安排生產(chǎn)計(jì)劃，才能使所獲總利潤(rùn)最大？寫出線性規(guī)劃模型；化成標(biāo)準(zhǔn)形式；用圖解法進(jìn)行求解。解：設(shè)x1和x2分別表示產(chǎn)品甲和乙的產(chǎn)量，這樣可以建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Max

20x1

+30

x2約束條件：s.t.3

x1

+7

x2

≤240（勞動(dòng)力限制）2

x1

+4

x2

≤150（原材料限制）4

x1

+3

x2

≤250（設(shè)備限制）x1，x2≥0（非負(fù)約束）化為標(biāo)準(zhǔn)型：目標(biāo)函數(shù)：Max

20x1

+30

x2約束條件：s.t.

3

x1

+

7

x2

+

x3

=

2402

x1

+

4x2

+

x4

=

1504

x1

+

3

x2

+

x5

=

250x1，x2，x3，x4，x5≥

0陰影部分為可行域，虛線為目標(biāo)函數(shù)線。由圖可知最優(yōu)解為約束2和約束3的交點(diǎn)，解得坐標(biāo)為（55,10），故最優(yōu)生產(chǎn)計(jì)劃為生產(chǎn)甲產(chǎn)品55件，乙產(chǎn)品10件，最大利潤(rùn)為

20×55+30×10=1400元。第二單元·產(chǎn)品··大號(hào)·中號(hào)·小號(hào)·可用資源量資源鋁板(張)

·6·2·4·400勞力(小時(shí))·4·8·6·360機(jī)器(臺(tái))·8·4·10·420····售價(jià)(元/個(gè))

·

50

·40·30·某廠生產(chǎn)三種型號(hào)的鋁鍋，已知單耗數(shù)據(jù)如下。試制定最優(yōu)生產(chǎn)計(jì)劃使總收入最大。解：設(shè)x1、x2、x3分別表示大號(hào)、中號(hào)、小號(hào)鋁鍋的產(chǎn)量，這樣可以建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Max

50x1

+40

x2+30

x3約束條件：s.t.6x1

+2

x2+4

x3

≤400（鋁板限制）4x1

+8

x2+6

x3

≤360（勞力限制）8x1

+4

x2+10

x3

≤420

（機(jī)器限制）x1，x2，x3≥0（非負(fù)約束）化為標(biāo)準(zhǔn)型：目標(biāo)函數(shù)：Max

50x1

+40

x2+30

x3約束條件：s.t.6x1

+2x2+4

x3

+x44x1

+8

x2+

6

x3

+

x5

=

360=

4008x1

+4

x2+

10

x3

+

x6

=

420x1，x2，x3，x4，x5，x6≥

0使用單純形法求解：···

·50·40·3

·

00·0·0··BC·

X·

b’

·

x

·

x

·

x1

2

3·x

·

x

·

xB456··0·x4

·

400·6·2·4

·

1·0·0

·

200/3·0·x5

·

360·4·8·6

·

0·1·0

·

90··

-z··0

·

50

·

40

·

3·0

·

0

·

0*00·x6

·

420·(8)·4·1

·

00·0·1

·

105/2··0·

x4·85

·0·

-1

·-

·7/1

·0

·-

·3---2/40·

x5·150

·0·

(6)

·1

·0

·1

·-

·215·得到最優(yōu)解（40,25,0,110,0,0），最優(yōu)值

3000。即應(yīng)該生產(chǎn)大號(hào)鋁鍋40個(gè)，中號(hào)鋁鍋25個(gè)單位，小號(hào)鋁鍋產(chǎn)量為0（不生產(chǎn)），最大利潤(rùn)為3000元。?

???

?????

???????.

?·

cj·

CB第·

三XB單·

元b’·-5·5·13·0·0

·θi·x1·x2·x3·x4·x5··5

·x

·

202·-1·1·3·1·0··0

·x

·

105·

·16

0

-2·-4·1··

-z·5線性規(guī)劃··0·Max

z

=

–5

x1

+

5

x2

+

13

x3·

s.-1t00.

–01

2

3·

0

·

-2

·

-x

+

x

+

3

x

≤

2012

x1

+

4

x2

+

10

x3

≤

90x1,x2,x3

≥0的最優(yōu)表為：分析在下列條件下，最優(yōu)解分別有什么變化b2由90變?yōu)?0。c1由-5變?yōu)?10。增加一個(gè)約束條件4

x1

+3

x2

+6

x3

≤50。解：（1）由最優(yōu)基不變的條件Max{-bi/βir?βir>0}≤Dbr≤Min{-bi/βir?βir<0}得-10=-10/1≤Db2b2由90變?yōu)?0，超出了允許變化范圍，繼續(xù)計(jì)算或者由B-1(b+Db)=(20,-10)T可以知道最優(yōu)基發(fā)生變化，繼續(xù)迭代。c1由-5→-10，Dc1

=-5<0=-s1，不影響最優(yōu)解。·

cj·

CB·

X

·

b’B·

-5

·

5

·

13

·

0

·

0·

x

·

x

·

x

·

x

·

x1

3

52

4·

5

·

x

·

20

·

-1·

1

·

3

·

1

·

02·

0

·5x

·-10

·

16

·

0·

(-

·

-·12)

4·

0

·

0·

-z

·

-

·

-100

2

5·

-

·

0·5z*·=90x。·

5

2

1

0最優(yōu)解變?yōu)閤1

=0，·x2

=5·，x3

=·5，x·4

=0，·x5

=0，最優(yōu)值-

3/2）c1是2

非基變量的系3數(shù)，最優(yōu)解不變5的條件2

是：Dc1≤

-

s1，3·

1

·

x

·

5

·

-8

13·

0

· ·

2·

-1/24

x1

+

3

x2

+

6

x3

+

x6

=

50（3）增加一個(gè)約束條件4

x1

+3

x2

+6

x3

≤350，原最優(yōu)解不滿足這個(gè)約束?！?/p>

··

·

·

··

Ci

-5

5

1

0

0

0·引入·松弛變量，得到填入最優(yōu)單純形表，進(jìn)一步求解，得到最優(yōu)3

解為X=(0，10，10/3)T，最優(yōu)值·

··

·

·

·

·CB

XB

b

x1

x2

x

x4

x5

x6·為5

28·0/3x。·

··

·

·

··

20

-1

1

3

1

0

0·2x5

·

10

·

160··0

·

-

·

-42·1

·

0··-z·-·0·0·-·-5·0·01002·

5·

x2·20·-1·

1·3·1·

0·0·

0·

x5·10·16·

0·-·-4·

1·020·x6

·

50

·

4·3

·

6

·

0·0

·

1·0·x6

·

-

·

7·0·(-·-3·0·1103)·-z·-100·0·0·2-·-5·0·0·

5·x2·10·6·1·0·-2·0·1·

0·x5·50·34·0·0·-2·1·-/3/32/3第四單元對(duì)于以下的運(yùn)輸問題，若各個(gè)銷地少得到1個(gè)單位的產(chǎn)品，將要求得到賠償，金額分別為9、12、6、12，問如何組織運(yùn)輸，才能使總費(fèi)用最低。（建立運(yùn)輸模型，用最小元素法求初始解，并求出最優(yōu)解）解：總產(chǎn)量為99+55+110=264，總銷量44+88+88+77=297，產(chǎn)銷不平衡且供不應(yīng)求，增加一個(gè)虛擬產(chǎn)地A4，其產(chǎn)量為297-264=33。由虛擬產(chǎn)地運(yùn)往銷地的費(fèi)用即為賠償金額。因此可以建立運(yùn)輸模型如下：使使用用最最小小元元素素法法求求初始始解解說(shuō)明：每次選擇最小元素，因此依次選擇3（x33）、6（x22）、

9（x41）、12（x11）、15（x14）、21（x32）、33（x12）。）得到初始解x11=11，x12=11，x14=77，x22=55，x32=22，

x33=88，x41=33，其余運(yùn)量為0，總運(yùn)費(fèi)為3003?！ぁ?/p>

B1·B2·B3·B4·

A1··1211··3311··9：(

)··1577·30·6·18·27·

A2·(

)·55·(

)·(

)·24·21·3·30·

A3·(

)·22·88·(

)·9·12·6·12·

A4·33·(

)·(

)·(

)·

銷量·44·88·88·77·

余額·11,

0·33,·0/·0/11·產(chǎn)量·余額·99·88,11·55·0/·110·22,0/·33·0/·297···使用用位位勢(shì)勢(shì)計(jì)計(jì)算算各各非非基基變變量量檢檢驗(yàn)數(shù)數(shù)，，填填入括括號(hào)號(hào)中中：··

B1

·

B2

·

B3

·

B4

·

產(chǎn)量

·

位勢(shì)ui·

A1··1211法··3311··9(-6)··1577·99·0·30·6·18·27·

A2·(45)·55·(30)·(39)·55·-27·24·21·3·30·

A3·(24)·22·88·(27)·110·-12·9·12·6·12·

A4·33·(-18)·(-6)·(0)·33·-3·

銷量·44·88·88·77·297··

位勢(shì)vj···12·33·15·15令u1=0，由基變量滿足ui+vj=cij，依次得到各位勢(shì)v1=12，v2=33，v4=15，u4=-3，u2=-27，u3=-12，v3=15，再根據(jù)公式sij

=cij

-ui

-vj計(jì)算各非基變量檢驗(yàn)數(shù)。進(jìn)行調(diào)整：選負(fù)檢驗(yàn)數(shù)中最小的s42，那么x42為主元，作為進(jìn)基變量。以x42為起點(diǎn)找一條閉回路x42、x41、x11、x12，取偶數(shù)標(biāo)號(hào)格的最小運(yùn)量11作為調(diào)整量，調(diào)整后運(yùn)量為x42=11，x41=22，x11=22，x12=0（調(diào)整為非基變量），得到新的基本解，并重新用位勢(shì)法計(jì)算檢驗(yàn)數(shù)（令v2=0），如下表所示。14x

=77，所有有非非基基x2222==5555，，變變量量檢檢x3322==2222，，驗(yàn)數(shù)數(shù)均均非非x3333==8888，，負(fù)，，得得到到xx4411==2222，，最優(yōu)優(yōu)解解為為xx4422==1111x1111==2222，，其其余余運(yùn)運(yùn)為0，最小小的的總總運(yùn)運(yùn)費(fèi)費(fèi)為為2280055。?！ぁ1·B2·B3·B4

·產(chǎn)量·位勢(shì)ui·

A1x··1222·

33·

(18)·

9·

(12)··1577·99，·15量·

A2··30(27)·

6·

55··18(30)··27(21)·55·

6·24·21·3·30·

A3·(6)·22·88·(9)·110·21·9·12·6·12·

A4·22·11·(12)·(0)·33·12·

銷量·44·88·88·77·297··

位勢(shì)vj···-3·

0·-18·0第五單元有一個(gè)工廠要確定明年各季度的生產(chǎn)計(jì)劃，通過(guò)訂貨了解到各季度對(duì)產(chǎn)品的需求量dk分別為4000件、3000件、4000件和4000件。又知，工廠生產(chǎn)該產(chǎn)品的季度固定成本為10萬(wàn)元（但如果在某季度中，該種產(chǎn)品1件也不生產(chǎn)，則不需支付固定成本費(fèi)），單位產(chǎn)品的可變成本為50元，由于設(shè)備的能力所限，每季度最多只能生產(chǎn)5000件。若產(chǎn)品銷售不出，則每件每季度的存貯費(fèi)為8元。假設(shè)本年底無(wú)存貨轉(zhuǎn)入下年，明年末也不需要留有存貨，問每季度的生產(chǎn)計(jì)劃應(yīng)如何安排（假設(shè)生產(chǎn)產(chǎn)量以千件為單位），才能使生產(chǎn)的總費(fèi)用最省？解：首先建立動(dòng)態(tài)規(guī)劃模型（1）階段k：每個(gè)季度作為一個(gè)階段，k=1,2,3,4狀態(tài)變量sk：第k個(gè)季度初的庫(kù)存量（千件）決策變量uk：第k個(gè)季度的生產(chǎn)量（千件）狀態(tài)轉(zhuǎn)移方程：sk+1=sk+uk

-dk

(需求，千件)（即季度末庫(kù)存量=季度初庫(kù)存量+季度生產(chǎn)量-季度銷售量或需求量）階段指標(biāo)：gk

(sk,uk)=生產(chǎn)成本C(uk)+庫(kù)存成本E(sk)最優(yōu)指標(biāo)函數(shù)fk(sk)：第k個(gè)季度的狀態(tài)為sk時(shí)從該季度至計(jì)劃結(jié)束的最低總費(fèi)用（萬(wàn)元）遞推方程：fk

(sk)=min{gk

(sk,uk)+fk+1(sk+1)}終端條件：f5(s5)=0下面進(jìn)行求解，采用逆序解法。（1）k=5，f5(s5)=0，因此庫(kù)存·

s4（(說(shuō)s4)4明：第4s季度的4,u4

)為4千件+f4

5(s4

5)4需4求·（2）uk=4·，0≤·s4≤4g，(us4=4·-s4，gs(5=ss4,+uu4-)d4

·f4量不(應(yīng)s4超)過(guò)4且顯然非負(fù)，·

u5

4所以有0≤s4≤4；年底不需要有庫(kù)存，所以生產(chǎn)量u4

=4-*s4）0·

30·

30·

3008·

25.

·

25.8

·

25.806·

21.

·

21.6

·

21.60·

17.·

17.4

·

17.4·

0·

1·

2·

3·

4·4··3··2··1··0·04·

3.2·

3.2

·

3.2·

4·

3·

2·

1·

0（3）k=3，0≤s3≤5+5-4-3=3，s4=s3+u3-d3=s3+u3-4，Max(0,

4-s3)≤u3≤Min(5,

8-s3)（說(shuō)明：前兩季度總產(chǎn)量為5+5=10千件，需求量為

3+4=7千件，所以第3季度初最大庫(kù)存量=10-7=3千件；

在產(chǎn)量需求方面，為了滿足需求，至少生產(chǎn)d3-u3=4-u3，且最大產(chǎn)量為5千件，后兩個(gè)季度總需求為4+4=8千件，產(chǎn)量不應(yīng)該超過(guò)8-s3。因此有0≤s3≤3，Max(0,4-s3)≤

u3≤Min(5,8-s3)）（4）k=2，0≤s2≤5-4=1，s3=s2+u2-d2=s2+u2-3，Max(0,

3-s2)≤u2≤Min(5,11-s2)（5）k=1，s1=0，s2=s1+u1-d1=u1-4，4≤u1≤5最優(yōu)解為s1=0,u1*=5,s2=1,u2*=5,s3=3,u3*=5,s4=4，u4*=0即前3個(gè)季度均生產(chǎn)5000件，第4個(gè)季度不生產(chǎn)，最低總費(fèi)用為111.4萬(wàn)元。第六單元某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)一件甲產(chǎn)品需要使用勞動(dòng)力4小時(shí)，能

源2個(gè)單位，銷售利潤(rùn)為16萬(wàn)元；生產(chǎn)一件乙產(chǎn)品需要使用勞動(dòng)力2小時(shí)，能源4個(gè)單位，銷售利潤(rùn)為20萬(wàn)元。企業(yè)目前擁有勞動(dòng)力可用時(shí)間22小時(shí)，能源20個(gè)單位。在制定生產(chǎn)計(jì)劃時(shí)，決策者考慮下述4項(xiàng)目標(biāo)：首先，乙

產(chǎn)品的產(chǎn)量不低于甲產(chǎn)品的產(chǎn)量；其次加班費(fèi)用比較高，盡量不要加班；第三，盡可能充分利用能源，但是又不希望再購(gòu)買；最后，利潤(rùn)盡量不少于112萬(wàn)元。求決策方案。（建立目標(biāo)規(guī)劃模型并用單純形法求解）解：設(shè)x1、x2分別表示甲產(chǎn)品和乙產(chǎn)品的產(chǎn)，以建立如下的目標(biāo)規(guī)劃模型：1

1

2

2

3

3

3

4

4目標(biāo)函數(shù)：Min

f=P

d

++P

d

++P

(d

-+d

+)+P

d

-1

1約束條件：

x1

﹣

x2

+

d

-

-

d

+

=

02

24

x1

+

2x2

+

d

-﹣

d

+

=

223

32

x1

+

4x2

+

d

-﹣

d

+

=

204

416x1

+

20

x2

+

d

-﹣d

+

=112i

ix1，x2，d

-，

d

+≥

0，i

=

1,

2,

3,

4（說(shuō)明：目標(biāo)1和2是不超過(guò)目標(biāo)值，因此正偏差變量盡量??；目標(biāo)3是恰好達(dá)到目標(biāo)值，因此要求正、負(fù)偏差變量都盡量?。荒繕?biāo)4要求不少于目標(biāo)值，因此是負(fù)偏差變量盡量?。┟嬗贸鰡螁渭冃渭冃伪矸ㄟM(jìn)行，取d1-求解。、d2-d3

、d--為初

4始基變量。最小化問題轉(zhuǎn)為基變量的檢驗(yàn)數(shù)應(yīng)該為0，最大理初化問題始基本，所以可行解目標(biāo)函對(duì)應(yīng)的數(shù)系數(shù)各級(jí)檢均乘驗(yàn)數(shù)以-1；。于P1別為(P2優(yōu)0，0，級(jí)對(duì)0，-1應(yīng)目標(biāo)，0，0函數(shù)中，0，0不含di-，0，，其0；0)檢驗(yàn)數(shù)和(0，0只需取，0，系數(shù)負(fù)0，0，值，-1，0，0，0，0；0)。··x

·1x

·2d

·1d

·1d

·2d

·2d

·3d

·3d

·4d

·4R

·Hθ-+-+-+-+S········P

·1P

·2P

·30下·列0為·處·0由分0

·0

··0、0

·0

··0先-

·10

·0

·0

·、0

·0

·0

·-

·10

·0

·0

·-

·10

·0

·-

·10

·

0

·

0

·把·0

·

0

·

0·0

·

0

·

0P

·40

·0

·0

·0

·0

·0

·0

·0

·-

·10

··0d

·11

·-

·11

·-

·10

·0

·0

·0

·0

·0

··0-d

·4

·2

·0

·0

·1

·-

·0

·0

·0

·0

··2212-d

·2

·4

·0

·0

·0

·0

·1

·-

·0

·0

··2310-d

·1

·2

·0

·0

·0

·0

·0

·0

·1

·-

··146011-2P3優(yōu)先級(jí)對(duì)應(yīng)的目標(biāo)函數(shù)中含d3-，所以其檢驗(yàn)數(shù)需要把第3個(gè)約束行加P4取負(fù)優(yōu)先級(jí)值的這對(duì)應(yīng)一行上的目標(biāo)，得到函數(shù)中4(2，4含d

-，，0，0所以，0，0其檢驗(yàn)，0，-數(shù)需要2，0把第4，0；20個(gè)約束)。行加到取負(fù)值的這一行上，得到(16，20，0，0，0，0，0，0，0，-1；112

)。列目標(biāo)規(guī)劃的初始單純形表如下：···x1·x2-

·

·d1

d1·d2·d2·d3·d3·d4·d4R

·θ+-+-+-+HS·P10·

到·0·0·-1·0·0·0·0·0·0·0··P2·0·0·0·0·0·-1·0·0·0·0·0··P3·2·4·0·0·0·0·0·-2·0·0·20···P416

·2

·0

·0

·0

·0

·0

·0

·0

·

-1

·1102······d11

·-1

·1

·

-1

·0

·

0

·0

·

0

·0

·

0

·0

·

----·d24

·2

·0

·

0

·1

·

-1

·0

·

0

·0

·

0

·22

·

11-·d32

·4*

·0

·

0

·0

·

0

·1

·

-1

·0

·

0

·20

·

5-·d416

·2

·0

·

0

·0

·

0

·0

·

0

·1

·

-1

·11

·

2-028/5下面（1）進(jìn)行計(jì)k

=

1算。，在初始單純形表中基變量為（d1-，d2-，d3

，-d4

)

=-（0，22，20，112)（2）；因?yàn)镻1與P2優(yōu)先級(jí)的檢驗(yàn)數(shù)均已經(jīng)為非正，所以這個(gè)單純形表對(duì)P1與P2優(yōu)（3）先級(jí)是下面最優(yōu)單考慮P3純形表優(yōu)先級(jí)；，第二列的檢驗(yàn)數(shù)為4最大，此為進(jìn)基變量，計(jì)算相最小，于是取a32（標(biāo)應(yīng)的*號(hào)）比值bi為轉(zhuǎn)/aij

寫軸元進(jìn)在q列行矩陣。通過(guò)行變換比較，得到新得到d3的單-對(duì)應(yīng)形表的比值如下。··x

·1x

·2d

·1d

·1d

·2d

·2d

·3d

·3d

·4d

·4R

·Hθ-+-+-+-+S·P1·0·0·0·-1·0·0·0·0·0·0·0··P2·0·0·0·0·0·-1·0·0·0·0·0··P3·0·0·0·0·0·0·-1·-1·0·0·0··P4·6·0·0·0·0·0·-5純·5·0·-1·12·····d

·3

·0

·1

·-

·0

·0

·1

·-

·0

·0

·5

·11-/21/41/40/3d

·3

·0

·0

·0

·1

·-

·-

·1

·0

·0

·1

·42-11/2/22x

·1

·1

·0

·0

·0

·0

·1

·-

·0

·0

·5

·12/2/41/40d

·6

·0

·0

·0

·0

·0

·-

·5

·1

·-

·1

·24*512-優(yōu)（（4）計(jì)算下面相應(yīng)的慮P4比值b/先級(jí)a

寫，第一在q列列的檢。通過(guò)驗(yàn)數(shù)為比較，6最大得到d

-，此為對(duì)應(yīng)進(jìn)基變的比值量，最小，于是取a41（標(biāo)*i號(hào)）ij為轉(zhuǎn)軸元進(jìn)行矩陣行變換得4到新的單純形表如下?！ぁ1·x2考2·d1-·d1+·d2-·d2+·d3-·d3+·d4-·d4+·R

H

S·θ·P1·0·0·0·-1·0·0·0·0·0·0·0··P2·0·0·0·0·0·-1·0·0·0·0·0··P3·0·0·0·0·0·0·-1·-1·0·0·0··P4·0·0·0·0·0·0·0·0·-1·0·0··d1-·0·0·1·-1·0·0·3/2·-3/2·-1/4·1/4·2··d2-·0·0·0·0·1·-1·2·-2·-1/2·1/2·6··x2·0·1·0·0·0·0·2/3·-2/3·-1/12·1/12·4··x1/

6/61/前·

表·5·5）當(dāng)1

的0

單·純形0

各0

優(yōu)·先0級(jí)0級(jí)的·的檢0

驗(yàn)·

數(shù)-均·滿足5

了·

最1優(yōu)·條件-

，·

故2為·最優(yōu)單純形表。于是得到最優(yōu)解x1=2，5

x2=4。/第七單元下圖為一個(gè)交通運(yùn)輸網(wǎng)絡(luò)圖，道路（即弧）旁的權(quán)數(shù)表示該道路的容量和目前的運(yùn)輸量(cij,fij)，求出該交通運(yùn)輸網(wǎng)絡(luò)的最大運(yùn)輸能力（即網(wǎng)絡(luò)最大流）。解：第一次標(biāo)號(hào)。首先給vs標(biāo)號(hào)(0,+∞)；看vs：在弧(vs,v2)上，fs2=cs2=2，不具