運籌學(xué)PPT完整版

1、（1）運籌學(xué)簡述）運籌學(xué)簡述（2）運籌學(xué)的主要內(nèi)容）運籌學(xué)的主要內(nèi)容（3）本課程的教材及參考書）本課程的教材及參考書（4）本課程的特點和要求）本課程的特點和要求（5）本課程授課方式與考核）本課程授課方式與考核 （6）運籌學(xué)在工商管理中的應(yīng)用）運籌學(xué)在工商管理中的應(yīng)用本章主要內(nèi)容：本章主要內(nèi)容：Page 3運籌學(xué)（運籌學(xué)（Operations Research）系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運籌學(xué)稱之為管理科學(xué)籌學(xué)稱之為管理科學(xué)(Management Science)。運籌學(xué)所研究。運籌學(xué)所研究的問題，可簡單地歸結(jié)為一句話：的問題，可簡

2、單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術(shù)。故有人稱之為最優(yōu)化技術(shù)。Page 4運籌學(xué)的歷史運籌學(xué)的歷史“運作研究運作研究(Operational Research)小組小組”:解決復(fù)解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如：雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如：如何合理運用雷達(dá)有效地對付德軍德空襲如何合理運用雷達(dá)有效地對付德軍德空襲對商船如何進(jìn)行編隊護(hù)航，使船隊遭受德國潛對商船如何進(jìn)行編隊護(hù)航，使船隊遭受德國潛艇攻擊時損失最少；艇攻擊時損失最少；1. 在各種情況下如何調(diào)整反潛深水炸彈的爆炸深在各種情況下如何調(diào)整反潛深水炸彈的

3、爆炸深度，才能增加對德國潛艇的殺傷力等。度，才能增加對德國潛艇的殺傷力等。Page 5數(shù)學(xué)規(guī)劃（數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動態(tài)、動態(tài)規(guī)劃等）規(guī)劃等）圖論圖論存儲論存儲論排隊論排隊論對策論對策論排序與統(tǒng)籌方法排序與統(tǒng)籌方法決策分析決策分析Page 6選用教材選用教材 運籌學(xué)基礎(chǔ)及應(yīng)用運籌學(xué)基礎(chǔ)及應(yīng)用胡運權(quán)主編胡運權(quán)主編 哈工大出版社哈工大出版社參考教材參考教材運籌學(xué)教程運籌學(xué)教程胡運權(quán)主編胡運權(quán)主編 （第（第2 2版）清華出版社版）清華出版社管理運籌學(xué)管理運籌學(xué)韓伯棠主編韓伯棠主編 （第（第2 2版）高等教育出版版）高等教育出版社社運籌學(xué)運籌學(xué)( (修訂

4、版修訂版) ) 錢頌迪主編錢頌迪主編 清華出版社清華出版社Page 7先修課：先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點：特點：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用運籌學(xué)的研究的主要步驟：運籌學(xué)的研究的主要步驟：真實系統(tǒng)真實系統(tǒng)系統(tǒng)分析系統(tǒng)分析問題描述問題描述模型建立模型建立與修改與修改模型求解模型求解與檢驗與檢驗結(jié)果分析與結(jié)果分析與實施實施數(shù)據(jù)準(zhǔn)備數(shù)據(jù)準(zhǔn)備Page 8學(xué)科總成績學(xué)科總成績平時成績平時成績（4040）課堂考勤課堂考勤（5050）平時作業(yè)平時作業(yè)（5050）期末成績期末成績（6060）講授為主，結(jié)合習(xí)題作業(yè)

5、講授為主，結(jié)合習(xí)題作業(yè)Page 9運籌學(xué)在工商管理中的應(yīng)用涉及幾個方面：運籌學(xué)在工商管理中的應(yīng)用涉及幾個方面： 生產(chǎn)計劃生產(chǎn)計劃 運輸問題運輸問題 人事管理人事管理 庫存管理庫存管理 市場營銷市場營銷 財務(wù)和會計財務(wù)和會計1.另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項目的選另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項目的選擇與評價，工程優(yōu)化設(shè)計等。擇與評價，工程優(yōu)化設(shè)計等。Page 10Interface上發(fā)表的部分獲獎項目上發(fā)表的部分獲獎項目組織組織應(yīng)用應(yīng)用效果效果聯(lián)合航空公司聯(lián)合航空公司在滿足乘客需求的前提下，以最低成本進(jìn)在滿足乘客需求的前提下，以最低成本進(jìn)行訂票及機場工作班次安排行訂票

6、及機場工作班次安排每年節(jié)約成本每年節(jié)約成本600600萬美元萬美元CitgoCitgo石油公司石油公司優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送和營銷優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送和營銷每年節(jié)約成本每年節(jié)約成本70007000萬萬AT&TAT&T優(yōu)化商業(yè)用戶的電話銷售中心選址優(yōu)化商業(yè)用戶的電話銷售中心選址每年節(jié)約成本每年節(jié)約成本4.064.06億美元，銷億美元，銷售額大幅增加售額大幅增加標(biāo)準(zhǔn)品牌公司標(biāo)準(zhǔn)品牌公司控制成本庫存（制定最優(yōu)再定購點和定購控制成本庫存（制定最優(yōu)再定購點和定購量確保安全庫存）量確保安全庫存）每年節(jié)約成本每年節(jié)約成本380380萬美元萬美元法國國家鐵路公司法國國家鐵路公司制

7、定最優(yōu)鐵路時刻表并調(diào)整鐵路日運營量制定最優(yōu)鐵路時刻表并調(diào)整鐵路日運營量每年節(jié)約成本每年節(jié)約成本15001500萬美元，萬美元，年收入大幅增加。年收入大幅增加。Taco BellTaco Bell優(yōu)化員工安排，以最低成本服務(wù)客戶優(yōu)化員工安排，以最低成本服務(wù)客戶每年節(jié)約成本每年節(jié)約成本13001300萬美元萬美元DeltaDelta航空公司航空公司優(yōu)化配置上千個國內(nèi)航線航班來實現(xiàn)利潤優(yōu)化配置上千個國內(nèi)航線航班來實現(xiàn)利潤最大化最大化每年節(jié)約成本每年節(jié)約成本1 1億美元億美元Page 11“管理運籌學(xué)管理運籌學(xué)”2.02.0版包括：線性規(guī)劃、運輸問題、整數(shù)規(guī)劃（版包括：線性規(guī)劃、運輸問題、整數(shù)規(guī)劃（0

8、-10-1整數(shù)整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對策論、最短路徑、規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關(guān)鍵路徑、存儲論、排隊論、最小生成樹、最大流量、最小費用最大流、關(guān)鍵路徑、存儲論、排隊論、決策分析、預(yù)測問題和層次分析法，共決策分析、預(yù)測問題和層次分析法，共1515個子模塊。個子模塊。 LP的數(shù)學(xué)模型的數(shù)學(xué)模型 圖解法圖解法 單純形法單純形法 單純形法的進(jìn)一步討論人工變量法單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用模型的應(yīng)用Page 131. 規(guī)劃問題規(guī)劃問題生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、生產(chǎn)和

9、經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。這就是規(guī)劃問題。（1 1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時間等）（如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)去完成確定的任務(wù)或目標(biāo)（2 2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤最大、利潤最大. .）Pa

10、ge 14例例1.1 如圖所示，如何截取如圖所示，如何截取x使鐵皮所圍成的容積最使鐵皮所圍成的容積最大？大？ x xa a xxav 220 dxdv0)2()2()2(22 xaxxa6ax Page 15例例1.2 某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在別要在A、B、C、D、四種不同的設(shè)備上加工。按工、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺時如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使時如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)總的利潤最大？企業(yè)總的利潤最大

11、？ 設(shè)設(shè) 備備產(chǎn)產(chǎn) 品品 A B C D利潤（元）利潤（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 臺臺 時時 12 8 16 12Page 16解：設(shè)解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：Page 17Page 1800 )( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 簡寫為：簡寫為：Page 19) (21ncccC n

12、xxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中：其中：Page 20 mnmnaaaaA1111 0 )( (min) maxXBAXCXZ其中：其中：) (21ncccC nxxX1 mbbB1Page 213. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特點：特點：(1) 目標(biāo)函數(shù)求最大值（有時求最小值）目標(biāo)函數(shù)求最大值（有時求最小值）(2) 約束條件都為等式方程，且右端常數(shù)項約束條件都為等式方程，且右端常數(shù)項bi都大于或等于零都大于或等于零(3)

13、決策變量決策變量xj為非負(fù)。為非負(fù)。Page 22 目標(biāo)函數(shù)的轉(zhuǎn)換目標(biāo)函數(shù)的轉(zhuǎn)換 如果是求極小值即如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以，則可將目標(biāo)函數(shù)乘以(- (-1)1)，可化為求極大值問題。，可化為求極大值問題。 jjxczmin也就是：令也就是：令 ，可得到上式。，可得到上式。zz jjxczzmax即即 若存在取值無約束的變量若存在取值無約束的變量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx 變量的變換變量的變換Page 23 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。 ijijbxa0 iniinjijxbxxa稱為松弛變量稱為松弛變量

14、 ijijbxa0 iniinjijxbxxa稱為剩余變量稱為剩余變量 變量變量 的變換的變換 可令可令 ，顯然，顯然0 jxjjxx 0 jxPage 24例例1.3 將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321無無約約束束xxxxxxxxxxxxxxxZ用用 替換替換 ，且，且 解解:（）因為（）因為x3無符號要求無符號要求 ，即，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以型中要求變量非負(fù)，所以33xx 3x0,33 xxPage 25(2) 第一個約束條件是第一個約束條件是“”

15、號，在號，在“”左端加入松馳變量左端加入松馳變量x4，x40,化為等式；化為等式；(3) 第二個約束條件是第二個約束條件是“”號，在號，在“”左端減去剩余變量左端減去剩余變量x5，x50；(4) 第第3個約束方程右端常數(shù)項為個約束方程右端常數(shù)項為-5，方程兩邊同乘以，方程兩邊同乘以(-1),將右將右端常數(shù)項化為正數(shù)；端常數(shù)項化為正數(shù)； (5) 目標(biāo)函數(shù)是最小值，為了化為求最大值，令目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到得到max z=-z，即當(dāng)，即當(dāng)z達(dá)到最小值時達(dá)到最小值時z達(dá)到最大值，反之亦然達(dá)到最大值，反之亦然;Page 26 0,5 )(252 )( 7 )(500)(3

16、2max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式如下：Page 274. 4. 線性規(guī)劃問題的解線性規(guī)劃問題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj線性規(guī)劃問題線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個解，使目標(biāo)函數(shù)中找出一個解，使目標(biāo)函數(shù)(1)達(dá)到最大值。達(dá)到最大值。Page 28 可行解可行解：滿足約束條件：滿足約束條件、的解為可行解。所

17、有可行解的解為可行解。所有可行解的集合為可行域。的集合為可行域。 最優(yōu)解最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。：使目標(biāo)函數(shù)達(dá)到最大值的可行解。 基：基：設(shè)設(shè)A為約束條件為約束條件的的mn階系數(shù)矩陣階系數(shù)矩陣(m04010換換出出行行將將3化為化為15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 48例例1.9 用單純形法求解用單純形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： 5 , 2 ,

18、 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量，列單純形表計算?？勺鳛槌跏蓟兞浚袉渭冃伪碛嬎?。Page 49cj12100icB基變量基變量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 50學(xué)習(xí)要點：學(xué)習(xí)要點：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個基本定理個基本定理

19、2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟Page 51人工變量法：人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，

20、用大MM法或兩階段法求解，這種用人工變量作橋梁的求解方法法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。稱為人工變量法。Page 52例例1.10 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系數(shù)矩陣中不存在系數(shù)矩陣中不存在單位矩陣，無法建單位矩陣，無法建立初始單純形表。立初始單純形表。Page 53故人為添加

21、兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型： 7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。紹的單純形法求解該模型，計算結(jié)果見下表。 Page 54cj32-100-M-MCBXBbx1x2x3x4x5x6x7

22、i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j Page 55解的判別：解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線

23、則線 規(guī)劃具有唯一最優(yōu)解。規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個）無界解判別：某個k0且且aik（i=1，2,m）則線性）則線性規(guī)劃具有無界解。規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大）無可行解的判斷：當(dāng)用大M單純形法計算得到最優(yōu)解并單純形法計算得到最優(yōu)解并且存在且存在Ri0時，則表明原線性規(guī)劃無可行解。時，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。）退化解的判別

24、：存在某個基變量為零的基本可行解。Page 56單純性法小結(jié)單純性法小結(jié):建建立立模模型型個個 數(shù)數(shù)取取 值值右右 端端 項項等式或等式或不等式不等式極大或極小極大或極小新加變量新加變量系數(shù)系數(shù)兩兩個個三個三個以上以上xj0 xj無無約束約束xj 0 bi 0bi mi 時，企業(yè)愿意時，企業(yè)愿意購進(jìn)這種資源，單位純利為購進(jìn)這種資源，單位純利為yi*mi ，則有利可圖；如果，則有利可圖；如果yi* mi 則購進(jìn)資源則購進(jìn)資源i，可獲單位純利，可獲單位純利yi*mi 若若yi* mi則轉(zhuǎn)讓資源則轉(zhuǎn)讓資源i ，可獲單位純利，可獲單位純利miyiPage 993）影子價格在資源利用中的應(yīng)用）影子價格在

25、資源利用中的應(yīng)用根據(jù)對偶理論的互補松弛性定理根據(jù)對偶理論的互補松弛性定理:Y*Xs=0 , YsX*=0表明生產(chǎn)過程中如果某種資源表明生產(chǎn)過程中如果某種資源bi未得到充分利用時，該種資未得到充分利用時，該種資源的影子價格為源的影子價格為0；若當(dāng)資源資源的影子價格不為；若當(dāng)資源資源的影子價格不為0時，表明時，表明該種資源在生產(chǎn)中已耗費完。該種資源在生產(chǎn)中已耗費完。Page 1004）影子價格對單純形表計算的解釋）影子價格對單純形表計算的解釋單純形表中的檢驗數(shù)單純形表中的檢驗數(shù) miiijjjBjjyacPBCc11其中其中c cj j表示第表示第j j種產(chǎn)品的價格種產(chǎn)品的價格; ; 表示生產(chǎn)該種

26、產(chǎn)品所表示生產(chǎn)該種產(chǎn)品所消耗的各項資源的影子價格的總和消耗的各項資源的影子價格的總和, ,即產(chǎn)品的隱含成本。即產(chǎn)品的隱含成本。 miiijya1當(dāng)產(chǎn)值大于隱含成本時，即當(dāng)產(chǎn)值大于隱含成本時，即 ，表明生產(chǎn)該項產(chǎn)品有，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排；否則利，可在計劃中安排；否則 ，用這些資源生產(chǎn)別的，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。0 j 0 j Page 101 對偶單純形法是求解線性規(guī)劃的另一個基本方法。它對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法原理而設(shè)計出來的，因此稱為是根據(jù)對偶原理和單純形法原理而設(shè)

27、計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。法。 找出一個對偶問題的可行基，保持對偶問題為可行解的找出一個對偶問題的可行基，保持對偶問題為可行解的條件下，判斷條件下，判斷XB是否可行（是否可行（XB為非負(fù)），若否，通過變換基為非負(fù)），若否，通過變換基解，直到找到原問題基可行解（即解，直到找到原問題基可行解（即XB為非負(fù)），這時原問題為非負(fù)），這時原問題與對偶問題同時達(dá)到可行解，由定理與對偶問題同時達(dá)到可行解，由定理4可得最優(yōu)解。可得最優(yōu)解。Page 102找出一個找出一個DP的可行基的可行基LP是否可行是否可行（XB

28、 0）保持保持DP為可行解情況下轉(zhuǎn)移到為可行解情況下轉(zhuǎn)移到LP的另一個基本解的另一個基本解最優(yōu)解最優(yōu)解是是否否循循環(huán)環(huán)結(jié)束結(jié)束Page 103例例2.9 用對偶單純形法求解：用對偶單純形法求解： )3.2.1(0145 1232102215129min321321321321jxxxxxxxxxxxxxZj解解:（1）將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求出一組基本解，因為對偶問題可行，即全部檢驗數(shù)出一組基本解，因為對偶問題可行，即全部檢驗數(shù)0（求（求max問題）。問題）。Page 104 014 5 12 3210 2215129max616

29、32153214321321xxxxxxxxxxxxxxxxZcj-9-12-15000bcBxBx1x2x3x4x5x60 x4-2-2-1100-100 x5-2-3-1010-120 x6-1-1-5001-14(-9/-1.-12/-1. -15/-5)j-9-12-150000iPage 105cj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/5-9/5010-1/5-36/50 x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342icj-9-12-150

30、00bcBxBx1x2x3x4x5x60 x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14ij j Page 106cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3j 原問題的最優(yōu)解為：原問題的最優(yōu)解為：X*=（2 , 2 , 2 , 0 , 0 , 0），），Z* =72 其對偶問題

31、的最優(yōu)解為：其對偶問題的最優(yōu)解為：Y*= （1/3 , 3 , 7/3），），W*= 72Page 107 對偶單純形法應(yīng)注意的問題：對偶單純形法應(yīng)注意的問題： 用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解問題的最優(yōu)解 初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判別準(zhǔn)則別準(zhǔn)則 最小比值中最小比值中 的絕對值是使得比值非負(fù)，在極小化問題的絕對值是使得比值非負(fù)，在極小化問題 j j00，分母分母a aij ij0 0 這時必須取絕對值。在極大化問題中，

32、這時必須取絕對值。在極大化問題中， j j00，分母，分母a aij ij00， 總滿足非負(fù)，這時絕對值符號不起作用，可以去掉。如總滿足非負(fù)，這時絕對值符號不起作用，可以去掉。如在本例中將目標(biāo)函數(shù)寫成在本例中將目標(biāo)函數(shù)寫成ijja 這里這里 j j 0 0在求在求 k k時就可以不帶絕對值符號。時就可以不帶絕對值符號。32134maxxxxz ijja Page 108 對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進(jìn)基變量后確定出基變量，對偶單純形法是先確定出基變是先確定進(jìn)基變量后確定出基變量，對偶單純形法是先確定出基

33、變量后確定進(jìn)基變量；量后確定進(jìn)基變量； 普通單純形法的最小比值是普通單純形法的最小比值是 其目的是保證下一其目的是保證下一個原問題的基本解可行，對偶單純形法的最小比值是個原問題的基本解可行，對偶單純形法的最小比值是 0minikikiiaab其目的是保證下一個對偶問題的基本解可行其目的是保證下一個對偶問題的基本解可行 0|minljljjjaa 對偶單純形法在確定出基變量時，若不遵循對偶單純形法在確定出基變量時，若不遵循 規(guī)則，任選一個小于零的規(guī)則，任選一個小于零的b bii對應(yīng)的基變量出基，不影響計算結(jié)果，對應(yīng)的基變量出基，不影響計算結(jié)果，只是迭代次數(shù)可能不一樣。只是迭代次數(shù)可能不一樣。 0

34、|min iilbbbPage 109學(xué)習(xí)要點：學(xué)習(xí)要點：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個基本定理個基本定理2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟運輸規(guī)劃問題的數(shù)學(xué)模型運輸規(guī)劃問題的數(shù)學(xué)模型表上作業(yè)法表上作業(yè)法運輸問題的應(yīng)用運輸問題的應(yīng)用 Page 111例例3.1 某公司從兩個產(chǎn)地某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地將物品運往三個銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最物品的運費如下表所示，問

35、：應(yīng)如何調(diào)運可使總運輸費用最小？?。緽1B2B3產(chǎn)量產(chǎn)量A1646200A2655300銷量銷量150150200Page 112解：產(chǎn)銷平衡問題：總產(chǎn)量解：產(chǎn)銷平衡問題：總產(chǎn)量 = 總銷量總銷量500 設(shè)設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運往銷地運往銷地Bj的運輸量，得到下列運輸量的運輸量，得到下列運輸量表：表：B1B2B3產(chǎn)量產(chǎn)量A1x11x12x13200A2x21x22x23300銷量銷量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x1

36、1 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）Page 113運輸問題的一般形式：產(chǎn)銷平衡運輸問題的一般形式：產(chǎn)銷平衡A1、 A2、 Am 表示某物資的表示某物資的m個產(chǎn)地；個產(chǎn)地； B1、B2、Bn 表示表示某物質(zhì)的某物質(zhì)的n個銷地；個銷地；ai 表示產(chǎn)地表示產(chǎn)地Ai的產(chǎn)量；的產(chǎn)量； bj 表示銷地表示銷地Bj 的銷量；的銷量； cij 表示把物資從產(chǎn)地表示把物資從產(chǎn)地Ai運往銷地運往銷地Bj的單位運價。設(shè)的單位運價。設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運往銷地運往銷地Bj的運輸量，得到下列一般運輸

37、量問題的模型：的運輸量，得到下列一般運輸量問題的模型： minjijijxcz11min njmixnjbxmiaxtsijjmiijnjiij, 1;, 1, 0, 1, 1.11Page 114變化：變化： 1）有時目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等；）有時目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等； 2）當(dāng)某些運輸線路上的能力有限制時，在模型中直接加入）當(dāng)某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束約束條件（等式或不等式約束)； 3）產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷）產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。地（

38、產(chǎn)大于銷時）。定理定理: 設(shè)有設(shè)有m個產(chǎn)地個產(chǎn)地n個銷地且產(chǎn)銷平衡的運輸問題，則基變個銷地且產(chǎn)銷平衡的運輸問題，則基變量數(shù)為量數(shù)為m+n-1。Page 115表上作業(yè)法是一種求解運輸問題的特殊方法，其表上作業(yè)法是一種求解運輸問題的特殊方法，其實質(zhì)是單純實質(zhì)是單純形法。形法。步驟步驟描述描述方法方法第一步第一步求初始基行可行解（初始調(diào)運方案）求初始基行可行解（初始調(diào)運方案）最小元素法、最小元素法、元素差額法、元素差額法、第二步第二步求檢驗數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的求檢驗數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗數(shù)檢驗數(shù) ij ij全都非負(fù)時得到最優(yōu)解，若存在檢驗全都非負(fù)時得到最優(yōu)解，若存在檢

39、驗數(shù)數(shù) ij ij 00，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位閉回路法和位勢法勢法第三步第三步調(diào)整運量，即換基，選一個變量出基，對原運調(diào)整運量，即換基，選一個變量出基，對原運量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步Page 116例例3.2 3.2 某運輸資料如下表所示：某運輸資料如下表所示：單位單位 銷地銷地 運價運價 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量3 311113 310107 71 19 92 28 84 47 74 410105 59 9銷量銷量3 36 65 56 64321 BBBB321AAA問：應(yīng)如何調(diào)運可使總運輸費用

40、最小？問：應(yīng)如何調(diào)運可使總運輸費用最?。縋age 117解：第解：第1步步 求初始方案求初始方案方法方法1：最小元素法：最小元素法 基本思想是就近供應(yīng)，即從運價最小的地方開始供應(yīng)（調(diào)基本思想是就近供應(yīng)，即從運價最小的地方開始供應(yīng)（調(diào)運），然后次小，直到最后供完為止。運），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A39銷量銷量3656311310192741058341633Page 118總的運輸費總的運輸費(31)+(64) +(43) +(12)+(310)+(35)=86元元元素差額法對最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷元素差額法對最小元素法進(jìn)行了改進(jìn)，考慮到

41、產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方最小運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方案。案。85102120151515510總運費是總運費是z=108+52+151=105最小元素法：最小元素法：Page 11985102120151551510總運費總運費z=105+152+51=85后一種方案考慮到后一種方案考慮到C11與與C21之間之間的差額是的差額是82=6，如果不先調(diào)運，如果不先調(diào)運x21，到后來就有可能，到后來就有可能x110，這，這樣會使總運費增加

42、較大，從而先樣會使總運費增加較大，從而先調(diào)運調(diào)運x21，再是，再是x22，其次是，其次是x12用元素差額法求得的基本可行解更接近最優(yōu)解，所用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。以也稱為近似方案。Page 120方法方法2：Vogel法法1）從運價表中分別計算出各行和各列的最小運費和次最小運）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。費的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A39銷量銷量3656311310192741058Page 1212）再從差值最大的行或列中找出最小運價確定供需關(guān)系和

43、）再從差值最大的行或列中找出最小運價確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時，劃去運價表中對應(yīng)的行或列。時，劃去運價表中對應(yīng)的行或列。重復(fù)重復(fù)1)和和2)，直到找出初始解為至。，直到找出初始解為至。B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A3 9銷量銷量3656311310192741058Page 122單位單位 銷地銷地 運價運價 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA71135215Page 123單位單位 銷地銷地 運價運價

44、產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA71352753Page 124單位單位 銷地銷地 運價運價 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA11351536312該方案的總運費該方案的總運費:(13)(46)(35)(210)(18)(35)85元元Page 125求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記驗數(shù)來判斷，記xij的檢驗數(shù)為的檢驗數(shù)為ij由第一章知，求

45、最小值的運由第一章知，求最小值的運輸問題的最優(yōu)判別準(zhǔn)則是：輸問題的最優(yōu)判別準(zhǔn)則是：所有非基變量的檢驗數(shù)都非負(fù)，則運輸方案最優(yōu)所有非基變量的檢驗數(shù)都非負(fù)，則運輸方案最優(yōu)求檢驗數(shù)的方法有兩種：求檢驗數(shù)的方法有兩種： 閉回路法閉回路法 位勢法（位勢法（）Page 126閉回路的概念閉回路的概念,132222111jsisjsijijijijixxxxxx稱稱集集合合),(2121互互不不相相同同；其其中中ssjjjiii為一個閉回路為一個閉回路 ，集合中的變量稱為回路的頂點，相鄰兩個變，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表量的連線為閉回路的邊。如下表Page 127例下

46、表中閉回路的變量集合是例下表中閉回路的變量集合是x11,x12,x42,x43,x23,x25,x35, x31共共有有8個頂點，這個頂點，這8個頂點間用水平或垂直線段連接起來，組成個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。一條封閉的回路。 B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43 一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉(zhuǎn)一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉(zhuǎn)90度與另一頂點連接，表度與另一頂點連接，表33中的變量中的變量x 32及及x33不是閉回路的頂不是閉回路的頂點，只是連線的交點。點，只是連線的交點。 Page 1

47、28閉回路閉回路,123233434111xxxxxxB1B2B3A1X11X12A2A3X32X33A4X41X43例如變量組例如變量組 不能構(gòu)成一條閉回路，不能構(gòu)成一條閉回路，但但A中包含有閉回路中包含有閉回路 ,121131352521xxxxxxA ,31352521xxxx變量組變量組 變量數(shù)是奇數(shù)，顯然不是變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；閉回路，也不含有閉回路； ,2111123233xxxxxB Page 129用位勢法對初始方案進(jìn)行最優(yōu)性檢驗：用位勢法對初始方案進(jìn)行最優(yōu)性檢驗：1）由）由 ij=Cij-（Ui+Vj）計算位勢）計算位勢Ui ， Vj ，因?qū)兞慷?/p>

48、言有，因?qū)兞慷杂?ij=0，即，即Cij-（Ui+Vj） = 0，令，令U1=02）再由）再由 ij=Cij-（Ui+Vj）計算非基變量的檢驗數(shù)）計算非基變量的檢驗數(shù) ijB1B2B3B4UiA1A2A3Vj311310192741058436313當(dāng)存在非基當(dāng)存在非基變量的檢驗變量的檢驗數(shù)數(shù) kl 0，說，說明現(xiàn)行方案明現(xiàn)行方案為最優(yōu)方案，為最優(yōu)方案，否則目標(biāo)成否則目標(biāo)成本還可以進(jìn)本還可以進(jìn)一步減小。一步減小。Page 130當(dāng)存在非基變量的檢驗數(shù)當(dāng)存在非基變量的檢驗數(shù) kl 0 且且 kl =min ij時，令時，令Xkl 進(jìn)進(jìn)基。從表中知可選基。從表中知可選X24進(jìn)基。進(jìn)基。第第3

49、步步 確定換入基的變量確定換入基的變量第第4步步 確定換出基的變量確定換出基的變量以進(jìn)基變量以進(jìn)基變量xik為起點的閉回路中，標(biāo)有負(fù)號的最小運量作為為起點的閉回路中，標(biāo)有負(fù)號的最小運量作為調(diào)整量調(diào)整量，對應(yīng)的基變量為出基變量，并打上對應(yīng)的基變量為出基變量，并打上“”以示換以示換出作為非基變量。出作為非基變量。Page 131B1B2B3B4UiA1A2A3Vj311197436 13 , 1minmin14,23 xx調(diào)整步驟為：調(diào)整步驟為：在進(jìn)基變量的閉回路中標(biāo)有正號的變量加上調(diào)整量在進(jìn)基變量的閉回路中標(biāo)有正號的變量加上調(diào)整量，標(biāo)有負(fù)號的變量減去調(diào)整量，標(biāo)有負(fù)號的變量減去調(diào)整量，其余變量不變

50、，得到一組新的，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗數(shù)重新檢驗?；尚薪?。然后求所有非基變量的檢驗數(shù)重新檢驗。Page 132當(dāng)所有非基變量的檢驗數(shù)均非負(fù)時，則當(dāng)前調(diào)運方案即為最當(dāng)所有非基變量的檢驗數(shù)均非負(fù)時，則當(dāng)前調(diào)運方案即為最優(yōu)方案，如表此時最小總運費：優(yōu)方案，如表此時最小總運費：Z =(13)(46)(35)(210)(18)(35)85元元B1B2B3B4UiA1A2A3Vj311310192741058536312Page 133表上作業(yè)法的計算步驟：表上作業(yè)法的計算步驟：分析實際問題列出產(chǎn)銷平分析實際問題列出產(chǎn)銷平衡表及單位運價表衡表及單位運價表確定初始調(diào)運

51、方案（最小確定初始調(diào)運方案（最小元素法或元素法或Vogel法）法）求檢驗數(shù)（位勢法）求檢驗數(shù)（位勢法）所有檢驗數(shù)所有檢驗數(shù)0找出絕對值最大的負(fù)檢驗數(shù)，用閉合找出絕對值最大的負(fù)檢驗數(shù)，用閉合回路調(diào)整，得到新的調(diào)運方案回路調(diào)整，得到新的調(diào)運方案得到最優(yōu)方案，得到最優(yōu)方案，算出總運價算出總運價Page 134（1）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負(fù)，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使為負(fù)，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取目標(biāo)函數(shù)值得到改善，但通常取ij0中最小者對應(yīng)的變量為中最小者對

52、應(yīng)的變量為換入變量。換入變量。（2）無窮多最優(yōu)解）無窮多最優(yōu)解產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的ij0，則該問題有無窮多最優(yōu)解。，則該問題有無窮多最優(yōu)解。Page 135 退化解：退化解： 表格中一般要有表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量個數(shù)字格。但有時在分配運量時則需要同時劃去一行和一列，這時需要補一個時則需要同時劃去一行和一列，這時需要補一個0，以保證，以保證有有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個任意空格處加一個0即可。即可。 利用進(jìn)

53、基變量的閉回路對解進(jìn)行調(diào)整時，標(biāo)有負(fù)號的利用進(jìn)基變量的閉回路對解進(jìn)行調(diào)整時，標(biāo)有負(fù)號的最小運量（超過最小運量（超過2個最小值）作為調(diào)整量個最小值）作為調(diào)整量，選擇任意一個最，選擇任意一個最小運量對應(yīng)的基變量作為出基變量，并打上小運量對應(yīng)的基變量作為出基變量，并打上“”以示作為以示作為非基變量。非基變量。Page 136 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A116A210A322銷量銷量81412141241148310295116(0)(2)(9)(2)(1)(12)如下例中如下例中11檢驗數(shù)是檢驗數(shù)是 0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。 Page 137

54、 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量365620114431377821060在在x12、x22、x33、x34中任選一個變量作為基變量，例如選中任選一個變量作為基變量，例如選x34例：用最小元素法求初始可行解例：用最小元素法求初始可行解Page 138目標(biāo)函數(shù)求利潤最大或營業(yè)額最大等問題。目標(biāo)函數(shù)求利潤最大或營業(yè)額最大等問題。 minjijijxCZ11max njmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，Page 139求解方法：求解方法：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運將極

55、大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運價表為價表為C ，用一個較大的數(shù)，用一個較大的數(shù)M（Mmaxcij）去減每一個）去減每一個cij得到矩陣得到矩陣C，其中，其中C=（Mcij）0,將將C作為極小化問題的作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解。運價表，用表上用業(yè)法求出最優(yōu)解。Page 140例例3.3 下列矩陣下列矩陣C是是Ai（I=1，2，3）到）到Bj的噸公里利潤的噸公里利潤,運輸運輸部門如何安排運輸方案使總利潤最大部門如何安排運輸方案使總利潤最大. 銷地銷地產(chǎn)地產(chǎn)地B1B2B3產(chǎn)量產(chǎn)量A1A2A3銷量銷量ijijijccccM 10,10max/22取取Page 141 銷

56、地銷地產(chǎn)地產(chǎn)地B1B2B3產(chǎn)量產(chǎn)量A1A2A3銷量銷量得到新的最小化運輸問題，用表上作業(yè)法求解即可。得到新的最小化運輸問題，用表上作業(yè)法求解即可。Page 142當(dāng)總產(chǎn)量與總銷量不相等時當(dāng)總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題稱為不平衡運輸問題.這這類運輸問題在實際中常常碰到類運輸問題在實際中常常碰到,它的求解方法是將不平衡問它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。題化為平衡問題再按平衡問題求解。 當(dāng)產(chǎn)大于銷時，即：當(dāng)產(chǎn)大于銷時，即： minjjiba11數(shù)學(xué)模型為：數(shù)學(xué)模型為： minjijijxcZ11min njmixnjbxmiaxijmijijnjiij, 2 ,

57、 1;, 2 , 10, 2 , 1, 2 , 111，Page 143由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，假設(shè)該倉庫為一個虛擬必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，假設(shè)該倉庫為一個虛擬銷地銷地Bn+1， bn+1作為一個虛設(shè)銷地作為一個虛設(shè)銷地Bn+1的銷量的銷量(即庫存量即庫存量)。各產(chǎn)地。各產(chǎn)地Ai到到Bn+1的運價為零，即的運價為零，即Ci,n+1=0,（i=1，m）。則平衡問題的）。則平衡問題的數(shù)學(xué)模型為：數(shù)學(xué)模型為： minjijijxcZ11min , 2 , 1, 2

58、, 1, 01, 2 , 1, 2 , 1111jmixnjbxmiaxijmijijnjiij；具體求解時具體求解時, ,只在只在運價表右端增加運價表右端增加一列一列B Bn n+1+1，運價，運價為零為零, ,銷量為銷量為b bn n+1+1即可即可Page 144 當(dāng)銷大于產(chǎn)時，即：當(dāng)銷大于產(chǎn)時，即： minjjiba11 minjijijxCZ11min , 2 , 1;, 2 , 1, 0, 2 , 1, 2 , 111jmixnjbxmiaxijmijijnjiij數(shù)學(xué)模型為：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)由于總銷量大于總產(chǎn)量量,故一定有些需求地故一定有些需求地不完全滿足不完全滿足

59、,這時虛設(shè)這時虛設(shè)一個產(chǎn)地一個產(chǎn)地Am+1，產(chǎn)量，產(chǎn)量為：為： miinjjab11Page 145銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為 ： minjijijxcZ11min njmixnjbxmiaxijmijijnjiji, 2 , 11, 2 , 1, 0, 2 , 11, 2 , 1111；具體計算時，在運價表的下方增加一行具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)，運價為零。產(chǎn)量為量為am+1即可。即可。 Page 146例例3.4 求下列表中極小化運輸問題的最優(yōu)解。求下列表中極小化運輸問題的最優(yōu)解。 B1B2B3B4aiA1592360A2

60、-47840A3364230A448101150bj20603545180160 4141160180ijjiba因為有：因為有：Page 147所以是一個產(chǎn)大于銷的運輸問題。表中所以是一個產(chǎn)大于銷的運輸問題。表中A2不可達(dá)不可達(dá)B1，用一個，用一個很大的正數(shù)很大的正數(shù)M表示運價表示運價C21。虛設(shè)一個銷量為。虛設(shè)一個銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，表的右邊增添一列 ，得到新的運價表。，得到新的運價表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180Page 148下表為計算結(jié)