1、第一部分線性規(guī)劃問(wèn)題的求解一、兩個(gè)變量的線性規(guī)劃問(wèn)題的圖解法：概念準(zhǔn)備： 定義：滿足所有約束條件的解為可行解；可行解的全體稱(chēng)為可行（解）域。定義：達(dá)到目標(biāo)的可行解為最優(yōu)解。圖解法：圖解法采用直角坐標(biāo)求解：x1橫軸； x2豎軸。 1、將約束條件（取等號(hào)）用直線繪出；2、確定可行解域；3、繪出目標(biāo)函數(shù)的圖形（等值線） ，確定它向最優(yōu)解的移動(dòng)方向；注：求極大值沿價(jià)值系數(shù)向量的正向移動(dòng)；求極小值沿價(jià)值系數(shù)向量的反向移動(dòng)。4、確定最優(yōu)解及目標(biāo)函數(shù)值。參考例題：（只要求下面這些有唯一最優(yōu)解的類(lèi)型）例 1：某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需在a、b、c 三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工所需

2、的工時(shí)不同，這些產(chǎn)品銷(xiāo)售后所能獲得利潤(rùn)以及這三種加工設(shè)備因各種條件限制所能使用的有效加工總時(shí)數(shù)如下表所示：a b c 利潤(rùn)（萬(wàn)元）甲乙3 5 9 9 5 3 70 30 有效總工時(shí)540 450 720 問(wèn)：該廠應(yīng)如何組織生產(chǎn)， 即生產(chǎn)多少甲、 乙產(chǎn)品使得該廠的總利潤(rùn)為最大？（此題也可用“ 單純形法 ”或化“ 對(duì)偶問(wèn)題 ”用大 m 法求解）設(shè)備消耗產(chǎn)品精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁(yè)

3、，共 27 頁(yè) - - - - - - - - -解：設(shè) x1、x2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。max z = 70 x1+30 x2s.t. 072039450555409321212121xxxxxxxx，可行解域?yàn)?oabcd0，最優(yōu)解為 b 點(diǎn)。由方程組72039450552121xxxx解出 x1=75，x2=15 x*=21xx=（75，15）t max z =z*= 70 75+30 15=5700 、精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f -

4、- - - - - - - - - - - - - 第 2 頁(yè)，共 27 頁(yè) - - - - - - - - -例 2：用圖解法求解max z = 6x1+4x2s.t. 0781022122121xxxxxxx，解：可行解域?yàn)?oabcd0 ，最優(yōu)解為 b 點(diǎn)。由方程組81022121xxxx解出 x1=2，x2=6 x*=21xx=（2，6）tmax z = 6 2+4 6=36 、精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - -

5、 - - - - - - 第 3 頁(yè)，共 27 頁(yè) - - - - - - - - -例 3：用圖解法求解min z =3x1+x2s.t. 08212523421212121xxxxxxxx，解：可行解域?yàn)?bcdefb，最優(yōu)解為 b 點(diǎn)。由方程組12524211xxx解出 x1=4，x2=54x*=21xx=（4，54）tmin z =3 4+54=1151、精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - -

6、 第 4 頁(yè)，共 27 頁(yè) - - - - - - - - -二、標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題的單純形解法：一般思路：1、用簡(jiǎn)單易行的方法獲得初始基本可行解；2、對(duì)上述解進(jìn)行檢驗(yàn)，檢驗(yàn)其是否為最優(yōu)解，若是，停止迭代，否則轉(zhuǎn)入3；3、根據(jù) l規(guī)則確定改進(jìn)解的方向；4、根據(jù)可能改進(jìn)的方向進(jìn)行迭代得到新的解；5、根據(jù)檢驗(yàn)規(guī)則對(duì)新解進(jìn)行檢驗(yàn)，若是最優(yōu)解，則停止迭代，否則轉(zhuǎn)入3，直至最優(yōu)解。具體做法（可化歸 標(biāo)準(zhǔn)型 的情況） ：設(shè)已知max z = c1x1+ c2x2+ cnxns.t. njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn，.210.22112222212111212111對(duì)

7、第 i 個(gè)方程加入松弛變量xn+i，i =1，2，m，得到njxbxxaxaxabxxaxaxabxxaxaxajmmnnmnmmnnnnnn，.210.2211222222121111212111列表計(jì)算，格式、算法如下：精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁(yè)，共 27 頁(yè) - - - - - - - - -cbxbb c1c2cn+mlx1x2xn+mcn+1xn+1b1a11a12a

8、1 n+mc n+2xn+2b2a21a22a2 n+m. . . . . . . . cn+mxn+mbnam1am2am n+mz1z2zn+m12n+m注：zj =cn+1a1j+ cn+2a2j+ cn+mamj=miijinac1， （j=1，2，n+m）j =cjzj ,當(dāng)j 0 時(shí)，當(dāng)前解最優(yōu)。注：由 maxj 確定所對(duì)應(yīng)的行的變量為“入基變量”；由l=0minikikiiaab確定所對(duì)應(yīng)的行的變量為“出基變量”，行、列交叉處為主元素，迭代時(shí)要求將主元素變?yōu)?，此列其余元素變?yōu)?。例 1：用單純形法求解（本題即是本資料p2“圖解法 ”例 1 的單純形解法 ；也可化“ 對(duì)偶問(wèn)題 ”

9、求解）max z =70 x1+30 x2s.t. 072039450555409321212121xxxxxxxx，解：加入松弛變量x3，x4，x5，得到等效的標(biāo)準(zhǔn)模型：max z =70 x1+30 x2+0 x3+0 x4+0 x5精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁(yè)，共 27 頁(yè) - - - - - - - - -s.t. 5,.,2, 1,0720394505554093521

10、421321jxxxxxxxxxxj列表計(jì)算如下：cbxbb 70 30 0 0 0 lx1x2x3x4x50 x3540 3 9 1 0 0 540/3 =180 0 x4450 5 5 0 1 0 450/5 =90 0 x5720 （9）3 0 0 1 720/9 =80 0 0 0 0 0 7030 0 0 0 0 x3300 0 8 1 0 - 1/3 300/8 =37.5 0 x450 0 （10/3 ）0 1 - 5/9 50/10/3 =15 70 x180 1 1/3 0 0 1/9 80/1/3 =240 70 70/3 0 0 70/9 0 20/30 0 70/90

11、x3180 0 0 1 12/51 30 x215 0 1 0 3/10 - 1/6 70 x175 1 0 0 - 1/10 1/6 5700 70 30 0 2 20/3 0 0 0 -2 20/3x*=（75，15，180，0，0）tmax z =7075+3015=5700精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁(yè)，共 27 頁(yè) - - - - - - - - -例 2：用單純形法求解

12、max z =7x1+12x2s.t. 0300103200543604921212121xxxxxxxx，解：加入松弛變量x3，x4，x5，得到等效的標(biāo)準(zhǔn)模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t. 5,.,2 , 1, 03001032005436049521421321jxxxxxxxxxxj列表計(jì)算如下：精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁(yè)，共 27

13、 頁(yè) - - - - - - - - -cbxbb 7 12 0 0 0 lx1x2x3x4x50 x3360 9 4 1 0 0 360/4 =90 0 x4200 4 5 0 1 0 200/5 =40 0 x5300 3 （10）0 0 1 300/10 =30 0 0 0 0 0 7 120 0 0 0 x3240 78/10 0 1 0 - 2/5 240/78/10 =2400/78 0 x450 （5/2 ）00 1 - 1/2 50/5/2 =20 12 x230 3/1010 0 1/10 30/3/10 =100 18/5 12 0 0 6/5 17/500 0 6/50

14、x384 0 0 1 78/2529/25 7 x120 1 00 2/5 - 1/5 12 x224 0 1 0 3/25 4/28 428 7 12 0 34/25 11/35 0 0 0 34/25 11/35x*=（20，24，84，0，0）t max z =720+1224=428三、非標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題的解法：1、一般地，對(duì)于約束條件組：若為“”，則加松弛變量，使方程成為“” ；若為“”，則減松弛變量，使方程成為“” 。我們?cè)谇懊鏄?biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。如果在實(shí)際問(wèn)題中遇到的是求極小值，則為 非標(biāo)準(zhǔn)型 ?？勺魅缦绿幚恚壕穼W(xué)習(xí)資料 可選擇p d f - - - - - -

15、- - - - - - - - 第 9 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁(yè)，共 27 頁(yè) - - - - - - - - -由目標(biāo)函數(shù) min z=njjjxc1變成等價(jià)的目標(biāo)函數(shù)max（z）=njjjxc1)(令z=z/，min z=max z/2、等式約束大m 法：通過(guò)加人工變量的方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。人工變量的價(jià)值系數(shù)為 m，m 是很大的正數(shù)， 從原理上理解又稱(chēng)為 “懲罰系數(shù)”。 （課本 p29）類(lèi)型一：目標(biāo)函數(shù)仍為 max z，約束條件組與。例 1：max

16、 z =3x1+5x2s.t. 018231224212121xxxxxx，解：加入松弛變量x3，x4，得到等效的標(biāo)準(zhǔn)模型：max z =3x1+5x2s.t. 4, 3 ,2, 1, 018231224214231jxxxxxxxj其中第三個(gè)約束條件雖然是等式，但因無(wú)初始解，所以增加一個(gè)人工變量x5，得到：max z =3x1+5x2mx5s.t. 5, . . . ,2, 1,0182312245214231jxxxxxxxxj單純形表求解過(guò)程如下：精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 10 頁(yè)，共 27 頁(yè) - - - - - - -

17、 - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 10 頁(yè)，共 27 頁(yè) - - - - - - - - -cbxbb 3 5 0 0 mlx1x2x3x4x50 x34 （1）0 1 0 0 4/1 =4 0 x412 0 2 0 1 0 mx518 3 2 0 0 1 18/3 =6 3m2m0 0 m3m352m0 0 0 3 x14 10 1 0 0 0 x412 020 1 0 12/2 =6 mx56 0（2）3 0 1 6/2 =3 3 2m33m0 m0 533m0 0 3 x14 1 0 1 0 0 4/1 =4 0 x46

18、00（3）1 1 6/3 =2 5 x23 0 13/2 0 1/2 3/(2/3) =9/2 3 5 9/2 0 5/2 0 0 9/2 0 m5/2 3 0 5 x12 1 0 0 1/3 1/3x32 0 0 11/3 1/3 x26 0 1 0 1/2 0 36 3 5 0 3/2 1 0 0 0 3/2 m1x*=（2，6，2，0）t精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 11 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 11 頁(yè)，共

19、 27 頁(yè) - - - - - - - - -max z =32+56=36類(lèi)型二：目標(biāo)函數(shù) min z，約束條件組與。例 2：用單純形法求解min z =4x1+3x2s.t. 012231642212121xxxxxx，解：減去松弛變量x3，x4，并化為等效的 標(biāo)準(zhǔn)模型：max z/ =4x13x2s.t. 4,3 ,2, 1,012231642421321jxxxxxxxj增加人工變量 x5、x6，得到：max z/ =4x13x2mx5mx6s.t 6,.,2, 1, 01223164264215321jxxxxxxxxxj單純形表求解過(guò)程如下：精品學(xué)習(xí)資料 可選擇p d f - -

20、- - - - - - - - - - - - 第 12 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 12 頁(yè)，共 27 頁(yè) - - - - - - - - -cbxbb 4 0 0 mmlx1x2x3x4x5x6mx516 2 （4）1 0 1 0 16/4=4 mx612 32 0 1 0 1 12/2=6 5m6mmmmm5m4 6m3mm0 0 3 x24 1/2 1 1/4 0 1/4 0 4/1/2=8 mx64 （2）0 1/2 1 1/2 1 4/2=2 2m3/23 3/4m/

21、2mm/23/4m2m5/20 m/23/4m3/43m/20 3 x23 0 1 3/8 1/4 3/8 1/4 4 x12 1 0 1/4 1/2 1/4 1/2 17 4 3 1/8 5/4 1/8 5/4 0 0 1/8 5/4 m1/8 m5/4 x*=（2，3，0，0）tmin z =max z/ =（ 17）=17 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 13 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 13 頁(yè)，共 27 頁(yè) -

22、 - - - - - - - -四、對(duì)偶問(wèn)題的解法：什么是對(duì)偶問(wèn)題？1、在資源一定的條件下，作出最大的貢獻(xiàn)；2、完成給定的工作，所消耗的資源最少。引例（與本資料 p2 例 1 “圖解法” 、p7 例 1 “單純形法 ”同）：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品均需在a、b、c 三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工時(shí)需要不同的工時(shí)，這些產(chǎn)品售后所能獲得的利潤(rùn)值以及這三種加工設(shè)備因各種條件下所能使用的有效總工時(shí)數(shù)如下表：a b c 利潤(rùn)（萬(wàn)元）甲乙3 5 9 9 5 3 70 30 有效總工時(shí)540 450 720 問(wèn)：該廠應(yīng)如何組織生產(chǎn)， 即生產(chǎn)多少甲、 乙產(chǎn)品使得該廠的總利潤(rùn)為最大？解

23、：原問(wèn)題設(shè) x1、x2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。max z = 70 x1+30 x2s.t. 072039450555409321212121xxxxxxxx，將這個(gè)原問(wèn)題化為它的對(duì)偶問(wèn)題設(shè)備消耗產(chǎn)品精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 14 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 14 頁(yè)，共 27 頁(yè) - - - - - - - - -設(shè) y1、y2、y2分別為設(shè)備 a、b、c 單位工時(shí)數(shù)的加工費(fèi)。min w = 540y1+450y

24、2+720y3s.t. 32103035970953321321，iyyyyyyyi用大 m 法，先化為等效的 標(biāo)準(zhǔn)模型：max w/ =540y1450y2720y3s.t. 5,.,2, 1,0303597095353214321jyyyyyyyyyj增加人工變量 y6、y7，得到：max z/ =540y1450y2720y3my6my7s.t 5,.,2, 1,030359709537532164321jyyyyyyyyyyyj大 m 法單純形表求解過(guò)程如下：精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 15 頁(yè)，共 27 頁(yè) - - -

25、- - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 15 頁(yè)，共 27 頁(yè) - - - - - - - - -cbxbb 540 450 720 0 0 mmly1y2y3y4y5y6y7my670 3 5 9 1 0 1 0 70/3 my730 （9）5 3 0 1 0 1 30/9=10/3 12m10m12mmmmm12m54010m45012m720mm0 0 my660 0 10/3 （8）1 1/3 1 1/3 60/8=2.5 540 y110/3 1 5/9 1/3 0 1/9 0 1/9 10/3/1/3 =10

26、 -300+10/3 m-8 m180mm/3+6 0mm/3600 -150+10/3 m 8m-540mm/3 600 m/3+6 0720 y315/2 0 5/12 1 1/8 1/24 1/8 1/24 15/2/5/12 =18 540 y15/6 1 （5/12 ）0 1/24 1/8 1/24 1/8 5/6/5/12 =2 540 572 720 135/2 475/12 135/2 75/20 1250 135/2 475/12 135/2 m75/2m720 450 y320/3 1 0 1 1/6 1/6 1/6 1/6y22 12/5 1 0 1/10 3/10 1/

27、10 3/105700 360 450 720 75 15 75 15 180 0 0 75 15 75m15m該對(duì)偶問(wèn)題的最優(yōu)解是y*=（0，2，320，0，0）t最優(yōu)目標(biāo)函數(shù)值min w =（ 5700）=5700 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 16 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 16 頁(yè)，共 27 頁(yè) - - - - - - - - -五、運(yùn)輸規(guī)劃問(wèn)題：運(yùn)輸規(guī)劃問(wèn)題的特殊解法“表上作業(yè)法” 解題步驟：1、找出初始調(diào)

28、運(yùn)方案。即在(mn)產(chǎn)銷(xiāo)平衡表上給出m+n-1 個(gè)數(shù)字格。 （最小元素法）2、 （對(duì)空格）求檢驗(yàn)數(shù)。判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。 （閉回路法）3、對(duì)方案進(jìn)行改善，找出新的調(diào)運(yùn)方案。 （根據(jù)檢驗(yàn)結(jié)果選擇入基變量，用表上閉回路法 調(diào)整即迭代計(jì)算，得新的基本可行解）4、重復(fù) 2、3，再檢驗(yàn)、再迭代，直到求得最優(yōu)調(diào)運(yùn)方案。類(lèi)型一：供求平衡的運(yùn)輸規(guī)劃問(wèn)題（又稱(chēng)“供需平衡”、 “產(chǎn)銷(xiāo)平衡”）引例：某鋼鐵公司有三個(gè)鐵礦和四個(gè)煉鐵廠，鐵礦的年產(chǎn)礦石量分別為100萬(wàn)噸、80 萬(wàn)噸和 50 萬(wàn)噸，煉鐵廠年需礦石量分別為50 萬(wàn)噸、70 萬(wàn)噸、80 萬(wàn)噸和 30萬(wàn)噸，這三個(gè)鐵礦與四

29、個(gè)煉鐵廠的距離如下：b1b2b3b4a1a2a315 20 3 30 70 8 14 20 12 3 20 15 問(wèn)： 該公司應(yīng)如何組織運(yùn)輸， 既滿足各煉鐵廠需要， 又使總的運(yùn)輸費(fèi)用為最小 （按噸.公里計(jì)）？解：用“表上作業(yè)法”求解。先用最低費(fèi)用法（最小元素法）求此問(wèn)題的初始基礎(chǔ)可行解：煉鐵距離鐵礦廠精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 17 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 17 頁(yè)，共 27 頁(yè) - - - - - - - -

30、-b1b2b3b4產(chǎn)量sia1152067330 65 1002080a27081444 2080302030a31253 32033 25 10 5050銷(xiāo)量dj50708030 230 230 初始方案：z=1520+380+7030+820+2030+350=3550（噸.公里）對(duì)的初始可行解進(jìn)行迭代（表上閉回路法），求最優(yōu)解：銷(xiāo)地費(fèi)用產(chǎn)地20 80 b1b3a1b220 30 30 b1b3a2b250 a3精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 18 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f

31、 - - - - - - - - - - - - - - 第 18 頁(yè)，共 27 頁(yè) - - - - - - - - -b1b2b3b4產(chǎn)量sia1152014 330 12 1002080a27053 8149 208050 30a312320 20 25 10 5030 20 銷(xiāo)量dj50708030230 230 用表上閉回路法調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)0，已得最優(yōu)解。最優(yōu)方案：z=1520+380+850+2030+1230+320=1960（噸.公里）解法分析：如何求檢驗(yàn)數(shù)并由此確定入基變量？有數(shù)字的空格稱(chēng)為“基格”、打的空格稱(chēng)為“空格” ，標(biāo)號(hào)為偶數(shù)的頂點(diǎn)稱(chēng)為偶點(diǎn)、 標(biāo)號(hào)為奇

32、數(shù)的頂點(diǎn)稱(chēng)為奇點(diǎn)， 出發(fā)點(diǎn)算 0 故為偶點(diǎn)。找出所有空格的閉回路后計(jì)算它們的檢驗(yàn)數(shù)偶點(diǎn)奇點(diǎn)ijijijcc，必須ij0，才得到最優(yōu)解。否則，應(yīng)選所有中正的最大者對(duì)應(yīng)的變量xj為入基變量進(jìn)行迭代（調(diào)整） 。檢驗(yàn)后調(diào)整運(yùn)輸方案的辦法是：在空格的閉回路中所有的偶點(diǎn)均加上奇點(diǎn)中的最小運(yùn)量，所有的奇點(diǎn)均減去奇點(diǎn)中的最小運(yùn)量。重復(fù)以上兩步，再檢驗(yàn)、再調(diào)整，直到求得最優(yōu)運(yùn)輸方案。類(lèi)型二：供求不平衡的運(yùn)輸規(guī)劃問(wèn)題銷(xiāo)地費(fèi)用產(chǎn)地20 80 b1b3a150 30 b2b4a230 20 b1b2a3精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 19 頁(yè)，共 27 頁(yè)

33、- - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 19 頁(yè)，共 27 頁(yè) - - - - - - - - -若njjmiids11，則是供大于求（供過(guò)于求）問(wèn)題，可設(shè)一虛銷(xiāo)地bn+1，令ci,n+1=0，dn+1=njjmiids11，轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題。若njjmiids11，則是供小于求（供不應(yīng)求）問(wèn)題，可設(shè)一虛產(chǎn)地am+1，令cm+1,j=0，sm+1=miinjjsd11，轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題。（，2， m ； ，2， n）六、工作指派問(wèn)題：工作指派問(wèn)題的數(shù)學(xué)模型假定有 n 項(xiàng)工作需要完成，恰好有n 個(gè)人每人可去

34、完成其中一項(xiàng)工作，效果要好。工作指派問(wèn)題的特殊解法“匈牙利法 ” （考！ ！ ）解題步驟：1、使系數(shù)矩陣（效率矩陣）各行、各列出現(xiàn)零元素。作法：行約簡(jiǎn) 系數(shù)矩陣各行元素減去所在行的最小元素，列約簡(jiǎn)再?gòu)乃镁仃嚨母髁袦p去所在列最小元素。2、試求最優(yōu)解。如能找出n 個(gè)位于不同行不同列的零元素，令對(duì)應(yīng)的xij= 1，其余xij= 0，得最優(yōu)解，結(jié)束；否則下一步。作法：由獨(dú)立 0 元素的行（列）開(kāi)始，獨(dú)立0 元素處畫(huà) （）標(biāo)記 ，在有（）的行列中劃去（也可打 *）其它 0 元素；再在剩余的 0 元素中重復(fù)此做法， 直至不能標(biāo)記 （）為止。3、作能覆蓋所有0 元素的最少數(shù)直線集合。作法：對(duì)沒(méi)有 （）的行

35、打號(hào)；對(duì)已打號(hào)的行中所有0 元素的所在列打號(hào)；再對(duì)打有號(hào)的列中0 元素的所在行打號(hào)； 重復(fù)、直到得不出新的打號(hào)的行(列)為止；對(duì)沒(méi)有打號(hào)的行畫(huà)一橫線，對(duì)打號(hào)的列畫(huà)一縱線，這就得到覆蓋所有0 元素的最少直線數(shù)。未被直線覆蓋的最小元素為cij,在未被直線覆蓋處減去cij,在直線交叉處加上cij。4、重復(fù) 2、3，直到求得最優(yōu)解。類(lèi)型一：求極小值的匈牙利法： （重點(diǎn)掌握這種基本問(wèn)題）精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 20 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - -

36、 - - - - 第 20 頁(yè)，共 27 頁(yè) - - - - - - - - -例 1：有甲、乙、丙、丁四個(gè)人，要派去完成a、b、c、d 四項(xiàng)工作，他們完成的工時(shí)如下表：a b c d 甲乙丙丁6 12 13 4 10 3 12 14 7 14 13 16 8 8 12 10 試問(wèn)：應(yīng)如何分配任務(wù)可使總工時(shí)為最少？解：用“匈牙利法”求解。已知條件可用系數(shù)矩陣（效率矩陣）表示為：（cij）=1012881613147141231041312624009670119070982200092701150705822)0(00927)0(115)0(7)0(582*使總工時(shí)為最少的分配任務(wù)方案為：甲d

37、，乙b，丙a，丁 c 此時(shí)總工時(shí)數(shù) w=4+3+7+12=26 例 2：求效率矩陣列約簡(jiǎn)任務(wù)工時(shí)人行約簡(jiǎn)標(biāo)號(hào)甲乙丙丁a b c d 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 21 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 21 頁(yè)，共 27 頁(yè) - - - - - - - - -54325645778587910的最優(yōu)解。解：5432564577858791032101201223010232210020112300023221002)0(11

38、23)0(0)0(23*所畫(huà)（） 0 元素少于 n，未得到最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有 0 元素的最少數(shù)直線集合）：221002)0(1123)0(0)0(23*未被直線覆蓋的最小元素為cij=1,在未被直線覆蓋處減去1,在直線交叉處加上1。110002020120002411000202012)0(0)0(24*）（）（得最優(yōu)解：0010100000010100類(lèi)型二：求極大值的匈牙利法：min z=max（z）標(biāo)號(hào)列約簡(jiǎn)行約簡(jiǎn)標(biāo)號(hào)精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 22 頁(yè)，共 27 頁(yè) - - - - - - - - -精

39、品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 22 頁(yè)，共 27 頁(yè) - - - - - - - - -（cij）（mcij）=（bij） ， （cij）中最大的元素為m max z=jijijixc=jijijixcm)(=jijijixcm)(jijijixc第一部分到此結(jié)束精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 23 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 23 頁(yè)，共 27 頁(yè) - - -

40、 - - - - - -第二部分動(dòng)態(tài)規(guī)劃只要求掌握動(dòng)態(tài)規(guī)劃的最短路問(wèn)題用“ 圖上標(biāo)號(hào)法 ”解決：具體解題步驟請(qǐng)參看教材p103（這是本套資料少見(jiàn)的與教材完全相同的算法類(lèi)型之一，務(wù)必看書(shū)掌握）學(xué)員們只有完全理解了這種作法（思路：逆向追蹤）才有可能做題，考試時(shí)數(shù)字無(wú)論如何變化都能作出正確求解！第二部分到此結(jié)束精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 24 頁(yè)，共 27 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 24 頁(yè)，共 27 頁(yè) - - - - - - - - -第三部分網(wǎng)絡(luò)分析一、求最小生成樹(shù)（最小支撐樹(shù)、最小樹(shù)）問(wèn)題：破圈法任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個(gè)步驟，直到得到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹(shù)。參考例題：例：求下圖的最小生成樹(shù)：6 7 9 4 1 5 10 v2v1v3v5v4v63 2 8 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2