運籌學(xué)-總復(fù)習(xí)

1、China University of Mining and Technology運籌學(xué) 運運 籌籌 學(xué)學(xué)復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-2-運籌學(xué) 123123123123123max23 31523 18. . 3,0zxxxxxxxxxstxxxx x x 求解如下線性規(guī)劃問題求解如下線性規(guī)劃問題例例1復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-3-運籌學(xué) 123123412351236123456max23 3 1523 18. . 3,0zxxxxxxxxxxxstxxxx

2、x x x x x x解：加入松弛變量，標(biāo)準(zhǔn)化得解：加入松弛變量，標(biāo)準(zhǔn)化得123456456023100015131100018231010031110010 xxxxxxxxx建立單純形表如下：建立單純形表如下：復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-4-運籌學(xué) 1234564560231000151311001823101031110010231000 xxxxxxxxx56153625611151 0 033331021 1 044180 0 1333151001 0 0 xxx復(fù)復(fù) 習(xí)習(xí)China University of Min

3、ing and Technology-5-運籌學(xué) 2161510010040112/31/303102110 40045/34/3118002 0 10 xxx4121330101/401/451001/61/31/2 10015/121/3 1/4200005/61/31/2xxx1235,3,1max20 xxxz最優(yōu)解解畢解畢復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-6-運籌學(xué) 123123123123min23423234,0wxxxxxxxxxx x x 用對偶單純形法計算用對偶單純形法計算例例2復(fù)復(fù) 習(xí)習(xí)China Univers

4、ity of Mining and Technology-7-運籌學(xué) 解：為了便于解：為了便于尋找初始正則尋找初始正則解，將問題變解，將問題變形為：形為： 0,43232432max5432153214321321xxxxxxxxxxxxxxxxw取取x4,x5為初始正則為初始正則解，列單純形表如下：解，列單純形表如下：復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-8-運籌學(xué) -2-3-400XBbx1x2x3x4x5x4-3-1-2-110 x5-4-21-3010-2-3-4由于初始正則解有負(fù)分量，于是取由于初始正則解有負(fù)分量，于是取min-

5、3,-4=-4x5為換出變量，取為換出變量，取155124523min0min,1jjj x1為換入變量，得新基為換入變量，得新基x4,x1 ， 51= -2為主元為主元復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-9-運籌學(xué) 基變換的過程：基變換的過程：1. 主元變?yōu)橹髟優(yōu)?，即用，即用-2去除單純形表中基變量去除單純形表中基變量x5所在的行；所在的行；2. 主元所在列的其它元變?yōu)橹髟诹械钠渌優(yōu)?，消去非基變量，消去非基變量x1所在的列的所在的列的其余元其余元-1，-2；3. 得新基得新基x4,x1的單純形表的單純形表-2-3-400

6、XBbx1x2x3x4x5x4-3-1-2-110 x5-4-21-3010-2-3-4復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-10-運籌學(xué) 基變換的過程：基變換的過程：-2-3-4XBbx1x2x3x4x5x4x1-2-3-400XBbx1x2x3x4x5x4-3-1-2-110 x5-4-21-3010-2-3-421-1/23/20-1/2-10-5/21/21-1/240-4-10-1復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-11-運籌學(xué) -2-3-4XBbx1x2x3x4x5x4

7、x121-1/23/20-1/2-10-5/21/21-1/240-4-10-1可見正則解的有負(fù)分量，由于可見正則解的有負(fù)分量，由于x4=1 , 所以取所以取x4為換為換出變量，取出變量，取422212544581,4min0min jjjx2為換入變量，得新基為換入變量，得新基x2,x1 ， 42=-5/2為主元為主元復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-12-運籌學(xué) -2-3-4XBbx1x2x3x4x5x22/501-1/5-2/51/5x111/5107/5-1/5-2/528/500-3/5-8/5-1/5此時正則解是可行解，也

8、是最優(yōu)解。此時正則解是可行解，也是最優(yōu)解。 X*=(11/5，2/5，0，0，0)；z*=-28/5進行基變換，得新正則解的單純形表：進行基變換，得新正則解的單純形表：復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-13-運籌學(xué) (1)寫出下列線性規(guī)劃的對偶規(guī)劃寫出下列線性規(guī)劃的對偶規(guī)劃(2)試用對偶原理求解線性規(guī)劃問題試用對偶原理求解線性規(guī)劃問題*341255,yy 123451234512345min235232342330,1,2,3,4,5jzxxxxxxxxxxxxxxxxj 已知其對偶規(guī)劃的最優(yōu)解為已知其對偶規(guī)劃的最優(yōu)解為例例3復(fù)復(fù) 習(xí)

9、習(xí)China University of Mining and Technology-14-運籌學(xué) 解：解：該問題的對偶規(guī)劃為該問題的對偶規(guī)劃為12121212121212max432232352330,0wyyyyyyyyyyyyyy 123451234512345min235232342330,1,2,3,4,5jzxxxxxxxxxxxxxxxxj 復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-15-運籌學(xué) 利用松緊關(guān)系，利用松緊關(guān)系，代入對偶規(guī)劃的約束條件得下列約代入對偶規(guī)劃的約束條件得下列約束是松約束，束是松約束，*341255,yy

10、12121212323520,0yyyyyyyy 2341234512345000234233xxxxxxxxxxxxx 將最優(yōu)解將最優(yōu)解12121212121212max432232352330,0wyyyyyyyyyyyyyy 123451234512345min235232342330,1,2,3,4,5jzxxxxxxxxxxxxxxxxj 松約束松約束緊約束緊約束其對偶約束是緊約束其對偶約束是緊約束復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-16-運籌學(xué) 設(shè)原問題的最優(yōu)解為設(shè)原問題的最優(yōu)解為*15*1,1(1,0,0,0,1) ,5T

11、xxXz求求得得2341234512345000234233xxxxxxxxxxxxx 緊約束緊約束*12345(,) ,TXxxxxx *234*15*150;3423xxxxxxx 有有復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-17-運籌學(xué) 設(shè)某種物資有設(shè)某種物資有3個產(chǎn)地個產(chǎn)地 A1，A2，A3， 生產(chǎn)量分別為生產(chǎn)量分別為9，5，7;有有4個銷地個銷地B1，B2，B3，B4 ，銷售量分別為，銷售量分別為3，8，4，6 ;已知從已知從Ai到到Bj 物資的單位運價見下表。求總運費最小的物資的單位運價見下表。求總運費最小的調(diào)運方案。調(diào)運方案。

12、B1B2B3B4產(chǎn)量產(chǎn)量A1291079A213425A384257銷量銷量3846例例4復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-18-運籌學(xué) 存在基變量為存在基變量為0的解稱為的解稱為退化解退化解。在確定初始基可行解的過程中，如果某一步中出現(xiàn)情況：在確定初始基可行解的過程中，如果某一步中出現(xiàn)情況：當(dāng)產(chǎn)地當(dāng)產(chǎn)地Ai處的余量與銷地處的余量與銷地Bj處的需求量相等時，在格處的需求量相等時，在格(i,j)填入運量后，產(chǎn)地填入運量后，產(chǎn)地Ai處的余量與銷地處的余量與銷地Bj處的銷量同時為處的銷量同時為0,相應(yīng)地要劃去一行和一列。這時就出現(xiàn)了相應(yīng)地要

13、劃去一行和一列。這時就出現(xiàn)了退化退化。為了使基變量個數(shù)恰好有為了使基變量個數(shù)恰好有m+n-1個，應(yīng)在同時劃去的一行個，應(yīng)在同時劃去的一行或一列中的某個格中填入數(shù)字或一列中的某個格中填入數(shù)字0，表示這格中的變量是取，表示這格中的變量是取值為值為0的基變量；的基變量；復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-19-運籌學(xué) B1B2B3B4ai行差行差A(yù)1291079A213425A384257bj3846列差列差用伏格爾法尋找初始基：用伏格爾法尋找初始基：|先算出運價表中各行與各列的最小運費與次小運費的差先算出運價表中各行與各列的最小運費與次小運

14、費的差額，并填入該運價表的最右列和最下行。額，并填入該運價表的最右列和最下行。|從行差或列差中選出最大者，并選擇其所在行或列的最從行差或列差中選出最大者，并選擇其所在行或列的最小元素。小元素。A1的行差最大，而其中運價的行差最大，而其中運價c11最小最小, 令令x11為優(yōu)先運輸路線。為優(yōu)先運輸路線。5121123復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-20-運籌學(xué) B1B2B3B4ai行差行差A(yù)12910795A2134251A3842572bj3846列差列差11230303/09/6用伏格爾法尋找初始基：用伏格爾法尋找初始基：u銷地銷地

15、B1的銷量的銷量3全由產(chǎn)地全由產(chǎn)地A1供給，所以供給，所以x21=x31=0。將。將x11=3 填到調(diào)運方案表中第填到調(diào)運方案表中第1行第行第1列上。列上。u畫去運輸數(shù)據(jù)表第一列，畫去運輸數(shù)據(jù)表第一列，A1的產(chǎn)量剩余為的產(chǎn)量剩余為9-3=6。得到得到新的產(chǎn)銷平衡與單位運價表新的產(chǎn)銷平衡與單位運價表.u令令33,9min11 x復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-21-運籌學(xué) B1B2B3B4ai行差行差A(yù)1291079/65A2134251A3842572bj3/0846列差列差11230306/15/0用伏格爾法尋找初始基：用伏格爾法

16、尋找初始基：u再算出運價表中的行差與列差。再算出運價表中的行差與列差。uB4的列差最大，而其中運價的列差最大，而其中運價c24最小最小, 令令x24為優(yōu)先運輸路線。為優(yōu)先運輸路線。u產(chǎn)地產(chǎn)地A2的產(chǎn)量的產(chǎn)量2全供給銷地全供給銷地B4，所以，所以x23=x24=0。u畫去運輸數(shù)據(jù)表中第畫去運輸數(shù)據(jù)表中第2行，行，B4的銷量還要的銷量還要6-5=1。得新表。得新表。521122112233050令令5,65min24 x復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-22-運籌學(xué) B1B2B3B4ai行差行差A(yù)1291079/65A213425/01A

17、3842572bj3/0846/1列差列差11230304/07/3用伏格爾法尋找初始基：用伏格爾法尋找初始基：5211221122330505 2 21 12 2 211522833204復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-23-運籌學(xué) B1B2B3B4ai行差行差A(yù)1291079/65A213425/01A384257/32bj3/084/06/1列差列差11230308/57/3/0用伏格爾法尋找初始基：用伏格爾法尋找初始基：5211221122330505 2 21 12 2 21152283320452 2 21122 2 1

18、1 1 5 5 2 2 83 3 2 203復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-24-運籌學(xué) B1B2B3B4ai行差行差A(yù)1291079/65A213425/01A384257/32bj3/084/06/1列差列差11230308/57/3/0用伏格爾法尋找初始基：用伏格爾法尋找初始基：0500452 2 21122 2 11 1 5 5 2 2 83 3 2 203現(xiàn)在只有一個產(chǎn)地兩個銷地，故令現(xiàn)在只有一個產(chǎn)地兩個銷地，故令x12 =5 ,x14 =1為基變量，為基變量，將其分別填到調(diào)運方案表中將其分別填到調(diào)運方案表中1行行2列與列

19、與1行行4列上。列上。51得到產(chǎn)銷平衡運輸問題的一個初始方案得到產(chǎn)銷平衡運輸問題的一個初始方案復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-25-運籌學(xué) B1B2B3B4aiA1291079A213425A384257bj3846354351此方案的運費是此方案的運費是32+59+47+52+34+42=88。伏格爾法給出的初始解往往更接近于最優(yōu)解。伏格爾法給出的初始解往往更接近于最優(yōu)解。復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-26-運籌學(xué) 利用伏格爾法確定的初始解如下表所示：利用伏格爾法確定

20、的初始解如下表所示：B1B2B3B4aiA1325910179A2134525A38344257bj38461、寫出、寫出基可行解對應(yīng)的位勢方程組基可行解對應(yīng)的位勢方程組;2、并計算非基變量的檢驗數(shù)。、并計算非基變量的檢驗數(shù)。復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-27-運籌學(xué) 111214243233297242uvuvuvuvuvuv12341232,9,7,7,0,5,5vvvvuuu 求解位勢及檢驗數(shù)的過程可在一個特殊設(shè)計的表上完成，這求解位勢及檢驗數(shù)的過程可在一個特殊設(shè)計的表上完成，這個表的構(gòu)造如下：個表的構(gòu)造如下：在原單位運價表

21、增加一行與一列，在列中填入在原單位運價表增加一行與一列，在列中填入ui，在行中填，在行中填入入vj；把運價；把運價cij記在每一格的右上角，用框標(biāo)定，在基變量記在每一格的右上角，用框標(biāo)定，在基變量對應(yīng)的格中標(biāo)出對應(yīng)的格中標(biāo)出0，構(gòu)成表。，構(gòu)成表。復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-28-運籌學(xué) 由由u1+v1=2, u1+v2=9, u1+v4=7,得得v1=2, v2=9, v4=7;B1B2B3B4uiA102091007A213402A3804025vj0-5-52977位勢表：位勢表：再由再由u2+v4=2，u3+v2=4，得，

22、得u2=-5，u3=-5;最后由最后由u3+v3=2 得得v3=7.取取u1=0;復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-29-運籌學(xué) 檢驗數(shù)表：檢驗數(shù)表：(計算所有非基變量的檢驗數(shù)計算所有非基變量的檢驗數(shù))B1B2B3B4uiA102091007A213402A3804025vj0-5-52977(3)(4)(-1)(2)(11)(3)當(dāng)存在非基變量的檢驗數(shù)當(dāng)存在非基變量的檢驗數(shù) kl 0，說明現(xiàn)行方案為最優(yōu)方案，否，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進一步減小。則目標(biāo)成本還可以進一步減小。復(fù)復(fù) 習(xí)習(xí)China Universit

23、y of Mining and Technology-30-運籌學(xué) 伏格爾法的初始方案：伏格爾法的初始方案：B1B2B3B4uiA1325910170A213452-5A3834425-5vj2977(3)(4)(-1)(2)(11)(3)22min|01ijij x22為為換入變量換入變量, 從從 x22所在格出發(fā)做閉回路所在格出發(fā)做閉回路L, L中有兩個偶中有兩個偶點點x24, x12，5,min1224 xx 取取x12為為換出變量換出變量，調(diào)整量為，調(diào)整量為5.復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-31-運籌學(xué) 伏格爾法的調(diào)整方案

24、：伏格爾法的調(diào)整方案：B1B2B3B4aiA1325910179A21034525A38344257bj3486在閉回路在閉回路L上，偶點變量減上，偶點變量減5，奇點變量加，奇點變量加5.0 x22為為換入變量換入變量, 取取x12為為換出變量換出變量.065復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-32-運籌學(xué) 它所對應(yīng)的位勢與檢驗數(shù)為：它所對應(yīng)的位勢與檢驗數(shù)為：B1B2B3B4uiA13291067A2153402A3834425vj28670-5-4(1)(4)(4)(3)(10)(2)所有檢驗數(shù)都非負(fù)，迭代停止，運費為：所有檢驗數(shù)都非

25、負(fù)，迭代停止，運費為：32 + 67 + 53 + 34 + 42 = 83復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-33-運籌學(xué) P1：充分利用現(xiàn)有工時，必要時可以加班；：充分利用現(xiàn)有工時，必要時可以加班；P2：A，B，C的最低產(chǎn)量分別為的最低產(chǎn)量分別為5，5，8臺，并依單位工時臺，并依單位工時的利潤比例確定權(quán)系數(shù)；的利潤比例確定權(quán)系數(shù)；P3：生產(chǎn)線加班時每月不超過：生產(chǎn)線加班時每月不超過20小時；小時；P4：A，B，C的月銷售指標(biāo)分別定為的月銷售指標(biāo)分別定為10，12，10臺，依單位臺，依單位工時利潤比例確定權(quán)系數(shù)工時利潤比例確定權(quán)系數(shù).

26、試建立目標(biāo)規(guī)劃模型試建立目標(biāo)規(guī)劃模型. A、B、C三種計算機，在一條生產(chǎn)線上裝配。裝配時三種計算機，在一條生產(chǎn)線上裝配。裝配時間分別為間分別為5，8，12小時；利潤分別為每臺小時；利潤分別為每臺1000元，元，1440元，元，2520元。生產(chǎn)線每月正常運轉(zhuǎn)元。生產(chǎn)線每月正常運轉(zhuǎn)170小時。該廠的經(jīng)營目標(biāo)為：小時。該廠的經(jīng)營目標(biāo)為：例例5復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-34-運籌學(xué) 復(fù)復(fù) 習(xí)習(xí)10121020855170128588377266155144333222111321ddxddxddxdddddxddxddxddxxx)2

27、11820()211820(min876453432211dddpdpdddpdpzChina University of Mining and Technology-35-運籌學(xué) 在在5個地點中選個地點中選3處建生產(chǎn)同一產(chǎn)品的工廠，在這處建生產(chǎn)同一產(chǎn)品的工廠，在這5個地個地點建廠所需投資，占用農(nóng)田，建成以后的生產(chǎn)能力等數(shù)據(jù)如點建廠所需投資，占用農(nóng)田，建成以后的生產(chǎn)能力等數(shù)據(jù)如下表所示。下表所示。 地點地點12345所需投資（萬元）所需投資（萬元）320280240210180占用農(nóng)田（畝）占用農(nóng)田（畝）201815118生產(chǎn)能力（萬噸）生產(chǎn)能力（萬噸）7055422811現(xiàn)在有總投資現(xiàn)在有總

28、投資800萬元，占用農(nóng)田指標(biāo)萬元，占用農(nóng)田指標(biāo)60畝，應(yīng)如何選擇廠畝，應(yīng)如何選擇廠址，使建成后總生產(chǎn)能力最大。址，使建成后總生產(chǎn)能力最大。 例例6復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-36-運籌學(xué) 復(fù)復(fù) 習(xí)習(xí)解：設(shè)五個解：設(shè)五個01變量變量 x1，x2，x3，x4，x5，其中，其中 01iixi表示在 地不建廠表示在 地建廠i=1,2,3,4,5. 建立整數(shù)規(guī)劃模型為建立整數(shù)規(guī)劃模型為 Max z=70 x1+55x2+42x3+28x4+11x5s.t.320 x1+280 x2+240 x3+210 x4+180 x5 80020 x

29、1+18x2+15x3+11x4+8x5 60 x1+x2+x3+x4+x5=3x1， x2， x3， x4， x5=0,1China University of Mining and Technology-37-運籌學(xué) 是整數(shù)是整數(shù)2121212121,0,5 . 45 . 01432.23xmaxzxxxxxxxxtsx利用割平面算法求解下面的規(guī)劃問題利用割平面算法求解下面的規(guī)劃問題例例7復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-38-運籌學(xué) 解：將約束條件的系數(shù)化整；去掉解：將約束條件的系數(shù)化整；去掉“x1, x2是整數(shù)是整數(shù)”的條件，

30、的條件，得到一個線性規(guī)劃的標(biāo)準(zhǔn)型（得到一個線性規(guī)劃的標(biāo)準(zhǔn)型（LP1）為：）為： 0,9 214 3223max432142132121xxxxxxxxxxxxz利用單純形法求解這個線性規(guī)劃問題，得出最終單純形表：利用單純形法求解這個線性規(guī)劃問題，得出最終單純形表： 3 2 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0 1 1/2 -1/2 1 0 -1/4 3/4 j 0 0 -1/4 -5/4復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-39-運籌學(xué) 最優(yōu)解不是整數(shù)解，由最終表得到變量之間的關(guān)系：最優(yōu)解不是整數(shù)解，由最終表得

31、到變量之間的關(guān)系：2341340.50.52.50.250.753.25xxxxxx 3 2 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0 1 1/2 -1/2 1 0 -1/4 3/4 j 0 0 -1/4 -5/4將上面的約束條件當(dāng)中的變量和系數(shù)改寫成將上面的約束條件當(dāng)中的變量和系數(shù)改寫成整數(shù)整數(shù)與與非負(fù)真分非負(fù)真分?jǐn)?shù)數(shù)的和的和2341340.5( 1 0.5)20.5( 1 0.75)0.7530.25xxxxxx 把整數(shù)部分放在左邊，把整數(shù)部分放在左邊，非整數(shù)部分放在右邊。非整數(shù)部分放在右邊。China University of Mining and Techno

32、logy-40-運籌學(xué) 下面增加割平面下面增加割平面，選真分?jǐn)?shù)最大的一個選真分?jǐn)?shù)最大的一個243420.50.50.5xxxx 由于上式左端是整數(shù)，因此右端也應(yīng)是整數(shù)，由于變量都是由于上式左端是整數(shù)，因此右端也應(yīng)是整數(shù)，由于變量都是不小于不小于0的整數(shù)，所以上式右端必是一個不大于的整數(shù)，所以上式右端必是一個不大于0.5 的整數(shù)，的整數(shù)，即即042132121xx稱這個不等式為一個稱這個不等式為一個割平面。割平面。2434133420.50.50.530.750.750.25xxxxxxxx China University of Mining and Technology-41-運籌學(xué) 引入一

33、個松弛變量，化割平面為：引入一個松弛變量，化割平面為：0542132121 xxx將它作為一個新增加的約束條件加入線性規(guī)劃將它作為一個新增加的約束條件加入線性規(guī)劃LPLP1 1中得中得到一個新的到一個新的線性規(guī)劃線性規(guī)劃LPLP2 2 ；或者直接反映到或者直接反映到LPLP1 1的最終單純形表中，得的最終單純形表中，得LPLP2 2單純形表單純形表：割平面的處理割平面的處理：021212143 xx復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-42-運籌學(xué) LP2 的單純形表：的單純形表： 3 2 0 0 0 x1 x2 x3 x4 x5x2x1

34、x55/213/4-1/2 0 1 1/2 -1/2 0 1 0 -1/4 3/4 0 0 0 -1/2 -1/2 1 0 0 -1/4 -5/4 0 3 2 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0 1 1/2 -1/2 1 0 -1/4 3/4 j 0 0 -1/4 -5/4LP1 ： 0,9 214 3223max432142132121xxxxxxxxxxxxz 0, 21- 9 214 3223max54321542132142132121xxxxxxxxxxxxxxxxzLP2 ：復(fù)復(fù) 習(xí)習(xí)China University of Mining and Tec

35、hnology-43-運籌學(xué) 3 2 0 0 0 x1 x2 x3 x4 x5 j 0 0 -1/4 -5/4 0 x2x1x32 7/21 0 1 0 -1 1 1 0 0 1 -1/2 0 0 1 1 -2 j 0 0 0 -1 -1/2由于不是整數(shù)解，找出不滿足條件的基變量由于不是整數(shù)解，找出不滿足條件的基變量 x1.7114522xxx用對偶單純型法求解：用對偶單純型法求解：復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-44-運籌學(xué) 將它作為一個新增加的約束加到線性規(guī)劃將它作為一個新增加的約束加到線性規(guī)劃LP2中又得一個線性中又得一個線性

36、規(guī)劃規(guī)劃LP3 1156220 xx111455223xxxx115220 x構(gòu)造線性規(guī)劃構(gòu)造線性規(guī)劃LP2的割平面的割平面復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-45-運籌學(xué) 1212312434556123456max3223 142 9111 - - 22211 - 22,0zxxxxxxxxxxxxxxxxxxx LP3 ：LP3的單純形表：的單純形表： 3 2 0 0 0 0 x1 x2 x3 x4 x5 x6x2x1x3x6 2 7/2 1 -1/2 0 1 0 -1 1 0 1 0 0 1 -1/2 0 0 0 1 1 -2

37、0 0 0 0 0 -1/2 1 j 0 0 0 -1 0 -1復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-46-運籌學(xué) 3 2 0 0 0 0 x1 x2 x3 x4 x5 x6 j 0 0 0 -1 -1/2 0 x2x1x3x5 1 4 3 1 0 1 0 -1 0 2 1 0 0 1 0 -1 0 0 1 1 0 -4 0 0 0 0 1 -2 j 0 0 0 -1 0 -1從上表中我們可以看到，已經(jīng)找到了整數(shù)最優(yōu)解：從上表中我們可以看到，已經(jīng)找到了整數(shù)最優(yōu)解：x1=4, x2=1。故求解結(jié)束。故求解結(jié)束。用對偶單純型法求解：用對偶單純

38、型法求解：復(fù)復(fù) 習(xí)習(xí)China University of Mining and Technology-47-運籌學(xué) 有一份資料，要分別譯成四種文字，現(xiàn)有甲、乙、有一份資料，要分別譯成四種文字，現(xiàn)有甲、乙、丙、丁四人可以承擔(dān)這項工作。因為各人專長不同，他丙、丁四人可以承擔(dān)這項工作。因為各人專長不同，他們翻譯成不同文字所需要的時間用效率矩陣們翻譯成不同文字所需要的時間用效率矩陣 C 表示。應(yīng)表示。應(yīng)如何分配工作，使他們完成任務(wù)的總時間最短？如何分配工作，使他們完成任務(wù)的總時間最短？丁丙乙甲9131541116141381441579102C例例8China University of Minin

39、g and Technology-48-運籌學(xué) Step 1、先對效率矩陣進行列變換，使其各行各列中都出、先對效率矩陣進行列變換，使其各行各列中都出現(xiàn)現(xiàn) 0 元素元素.效率矩陣變換方法為：效率矩陣變換方法為：從效率矩陣從效率矩陣 C 的每行元素中的每行元素中減去該行的最小元素減去該行的最小元素,得矩陣得矩陣 B ；從矩陣；從矩陣 B 中每列元素中中每列元素中減去該列的最小元素得矩陣減去該列的最小元素得矩陣 C1 。21097 2154148 413141611 11415139 4C 0875110104235001195B min 0 0 5 01082511054230001145C Ch

40、ina University of Mining and Technology-49-運籌學(xué) Step 2、確定、確定C1中線性獨立的中線性獨立的0元素元素.從第一行開始，若該行只有一個從第一行開始，若該行只有一個0元素，就對這個元素，就對這個0元素加元素加圈，然后劃去其所在列的其它圈，然后劃去其所在列的其它0元素元素;若該行沒有其它若該行沒有其它0元素元素或有兩個以上或有兩個以上0元素（已劃去的不計），轉(zhuǎn)下一行；直到最元素（已劃去的不計），轉(zhuǎn)下一行；直到最后一行為止。后一行為止。然后然后,從第一列開始從第一列開始,若該列只有一若該列只有一個個0元素元素,就對這個就對這個0元素加圈（同元素加圈

41、（同樣不考慮已劃的）樣不考慮已劃的）,再劃去其所在再劃去其所在行的其它行的其它0元素元素;若該列沒有若該列沒有0元素元素或有兩個以上或有兩個以上0元素，則轉(zhuǎn)下列直元素，則轉(zhuǎn)下列直到最后一列為止。到最后一列為止。18251105423001145C00重復(fù)上述步驟重復(fù)上述步驟.China University of Mining and Technology-50-運籌學(xué) 上述步驟可能出現(xiàn)三種情況上述步驟可能出現(xiàn)三種情況情況一：矩陣每行都有一個打圈的情況一：矩陣每行都有一個打圈的 0 元素。元素。此時得到問題的最優(yōu)解此時得到問題的最優(yōu)解.情況二：有多于兩行或兩列存在兩個以上的未處理的情況二：有多

42、于兩行或兩列存在兩個以上的未處理的 0 元素，元素，即出現(xiàn)即出現(xiàn) 0 元素的閉回路。此時，可從中任選一個元素的閉回路。此時，可從中任選一個 0元素加圈，元素加圈，劃掉其同行同列的劃掉其同行同列的 0 元素，再重復(fù)上述兩個步驟。元素，再重復(fù)上述兩個步驟。情況三：矩陣中所有情況三：矩陣中所有 0 元素或被加圈，或被劃去，而已加圈元素或被加圈，或被劃去，而已加圈的的 0 元素元素m小于矩陣的行數(shù)小于矩陣的行數(shù)n。即矩陣中至少存在有一行不。即矩陣中至少存在有一行不含加圈的含加圈的 0 元素。轉(zhuǎn)步驟三。元素。轉(zhuǎn)步驟三。18251105423001145C00China University of Min

43、ing and Technology-51-運籌學(xué) Step 3 尋找能覆蓋尋找能覆蓋C1中所有中所有0元素的最小直線數(shù)元素的最小直線數(shù).(1)按照從上到下、從左到右的順序?qū)Π凑諒纳系较?、從左到右的順序?qū)1沒有加圈的沒有加圈的0元行元行打打號；號；(2)對已打?qū)σ汛蛱柕男兄形醇尤μ柕男兄形醇尤?元的列打元的列打號；號；(3)對已打?qū)σ汛蛱柕牧兄屑尤μ柕牧兄屑尤?元的行打元的行打號；號；(4)重復(fù)下去，直到找不出打重復(fù)下去，直到找不出打號的行、列為止。號的行、列為止。 (5)對沒打?qū)]打號的行劃一橫線，對打號的行劃一橫線，對打號的列劃一縱線，這就是覆蓋矩號的列劃一縱線，這就是覆蓋矩陣陣C1中所

44、有中所有0元素的最小直線數(shù)元素的最小直線數(shù).18251105423001145C00 China University of Mining and Technology-52-運籌學(xué) Step 4、改進、改進C1(1)尋找尋找 C1 沒有被直線覆蓋的所有元沒有被直線覆蓋的所有元素中的最小元素素中的最小元素；例中例中= 2.(2)在已打在已打號的行中減去號的行中減去；(3)在已打在已打號的列中加上號的列中加上；得到一個新矩陣得到一個新矩陣 C2。 18251105423001145C00 2C -2603-292301340054300用用 C2 代替代替 C1，返回步驟，返回步驟 2.Chin

45、a University of Mining and Technology-53-運籌學(xué) 即例題的最優(yōu)分配方案：即例題的最優(yōu)分配方案：00100100*00011000X 206031305443000923C 確定確定C2中線性獨立的中線性獨立的0元素元素.China University of Mining and Technology-54-運籌學(xué) 用用dijkstradijkstra算法求下圖從頂點算法求下圖從頂點V1V1到其到其余各點的最短路徑：余各點的最短路徑：例例9V1112921865129734136971V1V2V3V4V5V6V7V8V9V1024China Univer

46、sity of Mining and Technology-55-運籌學(xué) V1112921865129734136971V1V2V3V4V5V6V7V8V9V1024V1112921865129734136971V1V2V3V4V5V6V7V8V9V100281240China University of Mining and Technology-56-運籌學(xué) V1112921865129734136971V1V2V3V4V5V6V7V8V9V1002810124V1112921865129734136971V1V2V3V4V5V6V7V8V9V10038101224China Univer

47、sity of Mining and Technology-57-運籌學(xué) V1112921865129734136971V1V2V3V4V5V6V7V8V9V100812106512324V1112921865129734136971V1V2V3V4V5V6V7V8V9V10081210146123524China University of Mining and Technology-58-運籌學(xué) V111921865129734136971V1V2V3V4V5V6V7V8V9V100712101412356242V111921865129734136971V1V2V3V4V5V6V7V8V

48、9V10012914123567242China University of Mining and Technology-59-運籌學(xué) V111921865129734136971V1V2V3V4V5V6V7V8V9V1001210141235679242V111921865129734136971V1V2V3V4V5V6V7V8V9V1001114121056793242China University of Mining and Technology-60-運籌學(xué) V111921865129734136971V1V2V3V4V5V6V7V8V9V1001210567932411132Chi

49、na University of Mining and Technology-61-運籌學(xué) 求下圖求下圖st的最大流的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)網(wǎng) 絡(luò) 最 大 流網(wǎng) 絡(luò) 最 大 流例例10China University of Mining and Technology-62-運籌學(xué) stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)解解: (1) 在已知可行流的基礎(chǔ)上，通過標(biāo)號尋找增廣鏈。在已知可行流的基礎(chǔ)上，通過標(biāo)號尋

50、找增廣鏈。()(2)=min,6=6(6)(3)=min6,2=2(2)(t)=min2,5=2(2)網(wǎng) 絡(luò) 最 大 流網(wǎng) 絡(luò) 最 大 流China University of Mining and Technology-63-運籌學(xué) (2) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?？尚辛鳌tv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)()(6)(2)(2)22 sf223 f23 tf網(wǎng) 絡(luò) 最 大 流網(wǎng) 絡(luò) 最 大 流China Universit

51、y of Mining and Technology-64-運籌學(xué) (3) 擦除原標(biāo)號，重新搜尋增廣鏈。擦除原標(biāo)號，重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(6)(2)(2)網(wǎng) 絡(luò) 最 大 流網(wǎng) 絡(luò) 最 大 流China University of Mining and Technology-65-運籌學(xué) (4) 重新搜尋增廣鏈。重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(2)=min,4=4(4)(1)(5)=min4,1=1(3)=min1,2=1(1)(1)(t)=min1,3=1網(wǎng) 絡(luò) 最 大 流網(wǎng) 絡(luò) 最 大 流China University of Mining and Technology-66-運籌學(xué) (5) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到