北外奧鵬作業(yè)運籌學講述

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

20x1

+30

x2約束條件：s.t.3

x1

+7

x2

≤240（勞動力限制）2

x1

+4

x2

≤150（原材料限制）4

x1

+3

x2

≤250（設備限制）x1，x2≥0（非負約束）化為標準型：目標函數(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陰影部分為可行域，虛線為目標函數(shù)線。由圖可知最優(yōu)解為約束2和約束3的交點，解得坐標為（55,10），故最優(yōu)生產(chǎn)計劃為生產(chǎn)甲產(chǎn)品55件，乙產(chǎn)品10件，最大利潤為

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

·6·2·4·400勞力(小時)·4·8·6·360機器(臺)·8·4·10·420····售價(元/個)

·

50

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

（機器限制）x1，x2，x3≥0（非負約束）化為標準型：目標函數(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。即應該生產(chǎn)大號鋁鍋40個，中號鋁鍋25個單位，小號鋁鍋產(chǎn)量為0（不生產(chǎ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。增加一個約束條件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ù)計算或者由B-1(b+Db)=(20,-10)T可以知道最優(yōu)基發(fā)生變化，繼續(xù)迭代。c1由-5→-10，Dc1

=-5<0=-s1，不影響最優(yōu)解?！?/p>

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）增加一個約束條件4

x1

+3

x2

+6

x3

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

··

·

·

··

Ci

-5

5

1

0

0

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

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

··

·

·

·

·CB

XB

b

x1

x2

x

x4

x5

x6·為5

28·0/3x?！?/p>

··

·

·

··

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第四單元對于以下的運輸問題，若各個銷地少得到1個單位的產(chǎn)品，將要求得到賠償，金額分別為9、12、6、12，問如何組織運輸，才能使總費用最低。（建立運輸模型，用最小元素法求初始解，并求出最優(yōu)解）解：總產(chǎn)量為99+55+110=264，總銷量44+88+88+77=297，產(chǎn)銷不平衡且供不應求，增加一個虛擬產(chǎn)地A4，其產(chǎn)量為297-264=33。由虛擬產(chǎn)地運往銷地的費用即為賠償金額。因此可以建立運輸模型如下：使使用用最最小小元元素素法法求求初始始解解說明：每次選擇最小元素，因此依次選擇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，其余運量為0，總運費為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ù)，，填填入括括號號中中：··

B1

·

B2

·

B3

·

B4

·

產(chǎn)量

·

位勢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··

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

=cij

-ui

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

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

·產(chǎn)量·位勢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··

位勢vj···-3·

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

-dk

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

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

(sk)=min{gk

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

s4（(說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量不(應s4超)過4且顯然非負，·

u5

4所以有0≤s4≤4；年底不需要有庫存，所以生產(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)（說明：前兩季度總產(chǎn)量為5+5=10千件，需求量為

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

在產(chǎn)量需求方面，為了滿足需求，至少生產(chǎn)d3-u3=4-u3，且最大產(chǎn)量為5千件，后兩個季度總需求為4+4=8千件，產(chǎn)量不應該超過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個季度均生產(chǎn)5000件，第4個季度不生產(chǎn)，最低總費用為111.4萬元。第六單元某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)一件甲產(chǎn)品需要使用勞動力4小時，能

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

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

1

2

2

3

3

3

4

4目標函數(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（說明：目標1和2是不超過目標值，因此正偏差變量盡量??；目標3是恰好達到目標值，因此要求正、負偏差變量都盡量??；目標4要求不少于目標值，因此是負偏差變量盡量小）面用出單單純形純形表法進行，取d1-求解。、d2-d3

、d--為初

4始基變量。最小化問題轉(zhuǎn)為基變量的檢驗數(shù)應該為0，最大理初化問題始基本，所以可行解目標函對應的數(shù)系數(shù)各級檢均乘驗數(shù)以-1；。于P1別為(P2優(yōu)0，0，級對0，-1應目標，0，0函數(shù)中，0，0不含di-，0，，其0；0)檢驗數(shù)和(0，0只需取，0，系數(shù)負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)先級對應的目標函數(shù)中含d3-，所以其檢驗數(shù)需要把第3個約束行加P4取負優(yōu)先級值的這對應一行上的目標，得到函數(shù)中4(2，4含d

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

)。列目標規(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）進行計k

=

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

，-d4

)

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

寫軸元進在q列行矩陣。通過行變換比較，得到新得到d3的單-對應形表的比值如下?！ぁ

·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）計算下面相應的慮P4比值b/先級a

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

-，此為對應進基變的比值量，最小，于是取a41（標*i號）ij為轉(zhuǎn)軸元進行矩陣行變換得4到新的單純形表如下。··x1·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）當1

的0

單·純形0

各0

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

驗·

數(shù)-均·滿足5

了·

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

，·

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

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