運(yùn)籌學(xué)課件--運(yùn)籌學(xué)完整課件

1、2022-4-24運(yùn)籌學(xué)運(yùn)運(yùn) 籌籌 學(xué)學(xué)( Operations Research )2022-4-24運(yùn)籌學(xué)（1）運(yùn)籌學(xué)簡述）運(yùn)籌學(xué)簡述（2）運(yùn)籌學(xué)的主要內(nèi)容）運(yùn)籌學(xué)的主要內(nèi)容（3）本課程的教材及參考書）本課程的教材及參考書（4）本課程的特點(diǎn)和要求）本課程的特點(diǎn)和要求（5）本課程授課方式與考核）本課程授課方式與考核 （6）運(yùn)籌學(xué)在工商管理中的應(yīng)用）運(yùn)籌學(xué)在工商管理中的應(yīng)用本章主要內(nèi)容：本章主要內(nèi)容：Page 32022-4-24運(yùn)籌學(xué)運(yùn)籌學(xué)（運(yùn)籌學(xué)（Operations Research）系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運(yùn)籌系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運(yùn)籌學(xué)稱之為

2、管理科學(xué)學(xué)稱之為管理科學(xué)(Management Science)。運(yùn)籌學(xué)所研究的。運(yùn)籌學(xué)所研究的問題，可簡單地歸結(jié)為一句話：問題，可簡單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術(shù)。故有人稱之為最優(yōu)化技術(shù)。Page 42022-4-24運(yùn)籌學(xué)運(yùn)籌學(xué)的歷史運(yùn)籌學(xué)的歷史“運(yùn)作研究運(yùn)作研究(Operational Research)小組小組”:解決復(fù)解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如：雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如：1. 如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍的空襲如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍的空襲2. 對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使

3、船隊(duì)遭受德國潛對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國潛艇攻擊時(shí)損失最少；艇攻擊時(shí)損失最少；3. 在各種情況下如何調(diào)整反潛深水炸彈的爆炸深在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對(duì)德國潛艇的殺傷力等。度，才能增加對(duì)德國潛艇的殺傷力等。Page 52022-4-24運(yùn)籌學(xué)數(shù)學(xué)規(guī)劃（數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)、動(dòng)態(tài)規(guī)劃等）規(guī)劃等）圖論圖論存儲(chǔ)論存儲(chǔ)論排隊(duì)論排隊(duì)論對(duì)策論對(duì)策論排序與統(tǒng)籌方法排序與統(tǒng)籌方法決策分析決策分析Page 62022-4-24運(yùn)籌學(xué)選用教材選用教材 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用胡運(yùn)權(quán)主編（第胡運(yùn)權(quán)主編（第5 5版）版）

4、 高等教高等教育出版社育出版社參考教材參考教材運(yùn)籌學(xué)教程運(yùn)籌學(xué)教程胡運(yùn)權(quán)主編胡運(yùn)權(quán)主編 （第（第2 2版）清華出版社版）清華出版社管理運(yùn)籌學(xué)管理運(yùn)籌學(xué)韓伯棠主編韓伯棠主編 （第（第2 2版）高等教育出版版）高等教育出版社社運(yùn)籌學(xué)運(yùn)籌學(xué)( (修訂版修訂版) ) 錢頌迪主編錢頌迪主編 清華出版社清華出版社Page 72022-4-24運(yùn)籌學(xué)先修課：先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點(diǎn)：特點(diǎn)：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用運(yùn)籌學(xué)的研究的主要步驟：運(yùn)籌學(xué)的研究的主要步驟：真實(shí)系統(tǒng)真實(shí)系統(tǒng)系統(tǒng)分析系統(tǒng)分析問題描述問題描

5、述模型建立模型建立與修改與修改模型求解模型求解與檢驗(yàn)與檢驗(yàn)結(jié)果分析與結(jié)果分析與實(shí)施實(shí)施數(shù)據(jù)準(zhǔn)備數(shù)據(jù)準(zhǔn)備Page 82022-4-24運(yùn)籌學(xué)學(xué)科總成績學(xué)科總成績平時(shí)成績平時(shí)成績（4040）課堂考勤課堂考勤（5050）平時(shí)作業(yè)平時(shí)作業(yè)（5050）期末成績期末成績（6060）講授為主，結(jié)合習(xí)題作業(yè)講授為主，結(jié)合習(xí)題作業(yè)Page 92022-4-24運(yùn)籌學(xué)運(yùn)籌學(xué)在工商管理中的應(yīng)用涉及幾個(gè)方面：運(yùn)籌學(xué)在工商管理中的應(yīng)用涉及幾個(gè)方面：1.1. 生產(chǎn)計(jì)劃生產(chǎn)計(jì)劃2.2. 運(yùn)輸問題運(yùn)輸問題3.3. 人事管理人事管理4.4. 庫存管理庫存管理5.5. 市場營銷市場營銷6.6. 財(cái)務(wù)和會(huì)計(jì)財(cái)務(wù)和會(huì)計(jì)另外，還應(yīng)用于

6、設(shè)備維修、更新和可靠性分析，項(xiàng)目的選擇另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項(xiàng)目的選擇與評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)等。與評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)等。2022-4-24運(yùn)籌學(xué)Chapter1 線性規(guī)劃線性規(guī)劃 (Linear Programming) LP的數(shù)學(xué)模型的數(shù)學(xué)模型 圖解法圖解法 單純形法單純形法 單純形法的進(jìn)一步討論人工變量法單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用模型的應(yīng)用Page 112022-4-24運(yùn)籌學(xué)1. 規(guī)劃問題規(guī)劃問題生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，物力等各種資源得到充

7、分利用，獲得最大的效益，這就是規(guī)劃問題。這就是規(guī)劃問題。（1 1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)去完成確定的任務(wù)或目標(biāo)（2 2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤最大、利潤最大. .）Page 122022-4-24運(yùn)籌學(xué)例例1.1 如圖所示，如何截取如圖所示，如何截取x使鐵皮所圍成的容積最

8、使鐵皮所圍成的容積最大？大？ x xa a xxav 220 dxdv0)2()2()2(22 xaxxa6ax Page 132022-4-24運(yùn)籌學(xué)例例1.2 某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在別要在A、B、C、D、四種不同的設(shè)備上加工。按工、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤最大？企業(yè)總的利潤最大？ 設(shè)設(shè) 備備產(chǎn)產(chǎn) 品品 A B C D利潤（元）利潤（

9、元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 臺(tái)臺(tái) 時(shí)時(shí) 12 8 16 12Page 142022-4-24運(yùn)籌學(xué)解：設(shè)解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：Page 152022-4-24運(yùn)籌學(xué)Page 162022-4-24運(yùn)籌學(xué)00 )( )( (min) max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z(min)max 11nxmbxaxcjnjijijnjjj簡寫為：簡寫為：Page 172022-4-

10、24運(yùn)籌學(xué)) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中：其中：Page 182022-4-24運(yùn)籌學(xué) mnmnaaaaA1111 0 )( (min) maxXBAXCXZ其中：其中：) (21ncccC nxxX1 mbbB1Page 192022-4-24運(yùn)籌學(xué)3. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特點(diǎn)：特點(diǎn)：(1) 目標(biāo)函數(shù)求最大值（有時(shí)求最小值）目標(biāo)函數(shù)求最大值（有時(shí)求最小值）(2) 約束條件都為等式方程，且右

11、端常數(shù)項(xiàng)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零都大于或等于零(3) 決策變量決策變量xj為非負(fù)。為非負(fù)。Page 202022-4-24運(yùn)籌學(xué) 目標(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 212022-4-24運(yùn)籌學(xué) 約束方程的轉(zhuǎn)

12、換：由不等式轉(zhuǎn)換為等式。約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。ijijbxa0iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0iniinjijxbxxa稱為剩余變量稱為剩余變量 變量變量 的變換的變換 可令可令 ，顯然，顯然0jxjjxx0 jxPage 222022-4-24運(yùn)籌學(xué)例例1.3 將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321無約束xxxxxxxxxxxxxxxZ用用 替換替換 ，且，且 解解:（）因?yàn)椋ǎ┮驗(yàn)閤3無符號(hào)要求無符號(hào)要求 ，即，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)取正值也可取負(fù)

13、值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以型中要求變量非負(fù)，所以33xx 3x0,33 xxPage 232022-4-24運(yùn)籌學(xué)(2) 第一個(gè)約束條件是第一個(gè)約束條件是“”號(hào)，在號(hào)，在“”左端加入松馳變量左端加入松馳變量x4，x40,化為等式；化為等式；(3) 第二個(gè)約束條件是第二個(gè)約束條件是“”號(hào)，在號(hào)，在“”左端減去剩余變量左端減去剩余變量x5，x50；(4) 第第3個(gè)約束方程右端常數(shù)項(xiàng)為個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以，方程兩邊同乘以(-1),將右將右端常數(shù)項(xiàng)化為正數(shù)；端常數(shù)項(xiàng)化為正數(shù)； (5) 目標(biāo)函數(shù)是最小值，為了化為求最大值，令目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到得

14、到max z=-z，即當(dāng)，即當(dāng)z達(dá)到最小值時(shí)達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然達(dá)到最大值，反之亦然;Page 242022-4-24運(yùn)籌學(xué) 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式如下：Page 252022-4-24運(yùn)籌學(xué)4. 4. 線性規(guī)劃問題的解線性規(guī)劃問題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj線性規(guī)劃問題線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件求解線性

15、規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個(gè)解，使目標(biāo)函數(shù)中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。達(dá)到最大值。Page 262022-4-24運(yùn)籌學(xué) 可行解可行解：滿足約束條件：滿足約束條件、的解為可行解。所有可行解的解為可行解。所有可行解的集合為可行域。的集合為可行域。 最優(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/

16、52/540011Page 462022-4-24運(yùn)籌學(xué)例例1.9 用單純形法求解用單純形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。可作為初始基變量，列單純形表計(jì)算。Page 472022-4-24運(yùn)籌學(xué)cj12100icB基變量基變量bx1x2x3x4x50 x4152-32100 x5201/3150112100

17、0 x42x2j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 482022-4-24運(yùn)籌學(xué)學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個(gè)基本定理個(gè)基本定理2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟Page 492022-4-24運(yùn)籌學(xué)人工變量法：人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位確定一組基可

18、行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大MM法或兩階段法求解，這種用人工變量作橋梁的求解方法稱法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。為人工變量法。Page 502022-4-24運(yùn)籌學(xué)例例1.10 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃 012210243423max3213

19、21321321321xxxxxxxxxxxxxxxZ、解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系數(shù)矩陣中不存在系數(shù)矩陣中不存在單位矩陣，無法建單位矩陣，無法建立初始單純形表。立初始單純形表。Page 512022-4-24運(yùn)籌學(xué)故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型： 7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMx

20、MxxxxZj其中：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。紹的單純形法求解該模型，計(jì)算結(jié)果見下表。 Page 522022-4-24運(yùn)籌學(xué)cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-21

21、0005-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 532022-4-24運(yùn)籌學(xué)解的判別：解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線則線 規(guī)劃具有唯一最優(yōu)解。規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)

22、解（或無窮多最優(yōu)解）。則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個(gè)）無界解判別：某個(gè)k0且且aik（i=1，2,m）則線性）則線性規(guī)劃具有無界解。規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大）無可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并單純形法計(jì)算得到最優(yōu)解并且存在且存在Ri0時(shí)，則表明原線性規(guī)劃無可行解。時(shí)，則表明原線性規(guī)劃無可行解。5）退化解的判別：）退化解的判別：存在某個(gè)基變量為零的基本可行解。存在某個(gè)基變量為零的基本可行解。Page 542022-4-24運(yùn)籌學(xué)單純性法小結(jié)單純性法小結(jié):建建立立模模型型個(gè)個(gè) 數(shù)數(shù)取取 值值右右 端端 項(xiàng)項(xiàng)等式或等式或不等式不等式

23、極大或極小極大或極小新加變量新加變量系數(shù)系數(shù)兩兩個(gè)個(gè)三個(gè)三個(gè)以上以上xj0 xj無無約束約束xj 0 bi 0bi mi 時(shí)，企業(yè)愿意時(shí)，企業(yè)愿意購進(jìn)這種資源，單位純利為購進(jìn)這種資源，單位純利為yi*mi ，則有利可圖；如果，則有利可圖；如果yi* mi 則購進(jìn)資源則購進(jìn)資源i，可獲單位純利，可獲單位純利yi*mi 若若yi* mi則轉(zhuǎn)讓資源則轉(zhuǎn)讓資源i ，可獲單位純利，可獲單位純利miyiPage 972022-4-24運(yùn)籌學(xué)3）影子價(jià)格在資源利用中的應(yīng)用）影子價(jià)格在資源利用中的應(yīng)用根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理:Y*Xs=0 , YsX*=0表明生產(chǎn)過程中如果某種

24、資源表明生產(chǎn)過程中如果某種資源bi未得到充分利用時(shí)，該種資未得到充分利用時(shí)，該種資源的影子價(jià)格為源的影子價(jià)格為0；若當(dāng)資源資源的影子價(jià)格不為；若當(dāng)資源資源的影子價(jià)格不為0時(shí)，表明時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完。該種資源在生產(chǎn)中已耗費(fèi)完。Page 982022-4-24運(yùn)籌學(xué)4）影子價(jià)格對(duì)單純形表計(jì)算的解釋）影子價(jià)格對(duì)單純形表計(jì)算的解釋單純形表中的檢驗(yàn)數(shù)單純形表中的檢驗(yàn)數(shù)miiijjjBjjyacPBCc11其中其中c cj j表示第表示第j j種產(chǎn)品的價(jià)格種產(chǎn)品的價(jià)格; ; 表示生產(chǎn)該種產(chǎn)品所表示生產(chǎn)該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和消耗的各項(xiàng)資源的影子價(jià)格的總和, ,即產(chǎn)品的隱含成本

25、。即產(chǎn)品的隱含成本。 miiijya1當(dāng)產(chǎn)值大于隱含成本時(shí)，即當(dāng)產(chǎn)值大于隱含成本時(shí)，即 ，表明生產(chǎn)該項(xiàng)產(chǎn)品有，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排；否則利，可在計(jì)劃中安排；否則 ，用這些資源生產(chǎn)別的，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。0 j 0 j Page 992022-4-24運(yùn)籌學(xué) 對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它是根據(jù)對(duì)偶原理和單純形法原理而設(shè)計(jì)出來的，因此稱為是根據(jù)對(duì)偶原理和單純形法原理而設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。不要簡單理解為是求解對(duì)偶問題的單純形對(duì)偶單純形法。不

26、要簡單理解為是求解對(duì)偶問題的單純形法。法。 找出一個(gè)對(duì)偶問題的可行基，保持對(duì)偶問題為可行解的找出一個(gè)對(duì)偶問題的可行基，保持對(duì)偶問題為可行解的條件下，判斷條件下，判斷XB是否可行（是否可行（XB為非負(fù)），若否，通過變換基為非負(fù)），若否，通過變換基解，直到找到原問題基可行解（即解，直到找到原問題基可行解（即XB為非負(fù)），這時(shí)原問題為非負(fù)），這時(shí)原問題與對(duì)偶問題同時(shí)達(dá)到可行解，由定理與對(duì)偶問題同時(shí)達(dá)到可行解，由定理4可得最優(yōu)解?？傻米顑?yōu)解。Page 1002022-4-24運(yùn)籌學(xué)找出一個(gè)找出一個(gè)DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP為可行解情況下轉(zhuǎn)移到為可行解情況下轉(zhuǎn)移到L

27、P的另一個(gè)基本解的另一個(gè)基本解最優(yōu)解最優(yōu)解是是否否循循環(huán)環(huán)結(jié)束結(jié)束Page 1012022-4-24運(yùn)籌學(xué)例例2.9 用對(duì)偶單純形法求解：用對(duì)偶單純形法求解： )3.2.1(0145 1232102215129min321321321321jxxxxxxxxxxxxxZj解解:（1）將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求出一組基本解，因?yàn)閷?duì)偶問題可行，即全部檢驗(yàn)數(shù)出一組基本解，因?yàn)閷?duì)偶問題可行，即全部檢驗(yàn)數(shù)0（求（求max問題）。問題）。Page 1022022-4-24運(yùn)籌學(xué) 014 5 12 3210 2215129max616321532

28、14321321xxxxxxxxxxxxxxxxZcj-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 1032022-4-24運(yùn)籌學(xué)cj-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-

29、12-15000bcBxBx1x2x3x4x5x60 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 1042022-4-24運(yùn)籌學(xué)cj-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 ,

30、 0），），Z* =72 其對(duì)偶問題的最優(yōu)解為：其對(duì)偶問題的最優(yōu)解為：Y*= （1/3 , 3 , 7/3），），W*= 72Page 1052022-4-24運(yùn)籌學(xué) 對(duì)偶單純形法應(yīng)注意的問題：對(duì)偶單純形法應(yīng)注意的問題： 用對(duì)偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對(duì)用對(duì)偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對(duì)偶問題的最優(yōu)解偶問題的最優(yōu)解 初始表中一定要滿足對(duì)偶問題可行，也就是說檢驗(yàn)數(shù)滿足最優(yōu)初始表中一定要滿足對(duì)偶問題可行，也就是說檢驗(yàn)數(shù)滿足最優(yōu)判別準(zhǔn)則判別準(zhǔn)則 最小比值中最小比值中 的絕對(duì)值是使得比值非負(fù)，在極小化問題的絕對(duì)值是使得比值非負(fù)，在極小化問題 j j00，分母分

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

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

33、的基變量出基，不影響計(jì)算結(jié)果，只是迭代次數(shù)可能不一樣。只是迭代次數(shù)可能不一樣。0|miniilbbbPage 1072022-4-24運(yùn)籌學(xué)學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個(gè)基本定理個(gè)基本定理2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟2022-4-24運(yùn)籌學(xué)運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型表上作業(yè)法表上作業(yè)法運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用 Page 1092022-4-24運(yùn)籌學(xué)例例3.1 某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地將物品運(yùn)往三個(gè)銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷

34、量和各產(chǎn)地運(yùn)往各銷地每件，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？??？B1B2B3產(chǎn)量產(chǎn)量A1646200A2655300銷量銷量150150200Page 1102022-4-24運(yùn)籌學(xué)解：產(chǎn)銷平衡問題：總產(chǎn)量解：產(chǎn)銷平衡問題：總產(chǎn)量 = 總銷量總銷量500 設(shè)設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量的運(yùn)輸量，得到下列運(yùn)輸量表：表：B1B2B3產(chǎn)量產(chǎn)量A1x11x12x13200A2x21x22x23300銷量銷量150150200Min C

35、 = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）Page 1112022-4-24運(yùn)籌學(xué)運(yùn)輸問題的一般形式：產(chǎn)銷平衡運(yùn)輸問題的一般形式：產(chǎn)銷平衡A1、 A2、 Am 表示某物資的表示某物資的m個(gè)產(chǎn)地；個(gè)產(chǎn)地； B1、B2、Bn 表示表示某物質(zhì)的某物質(zhì)的n個(gè)銷地；個(gè)銷地；ai 表示產(chǎn)地表示產(chǎn)地Ai的產(chǎn)量；的產(chǎn)量； bj 表示銷地表

36、示銷地Bj 的銷量；的銷量； cij 表示把物資從產(chǎn)地表示把物資從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)的單位運(yùn)價(jià)。設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型：的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型： minjijijxcz11min njmixnjbxmiaxtsijjmiijnjiij, 1;, 1, 0, 1, 1.11Page 1122022-4-24運(yùn)籌學(xué)變化：變化： 1）有時(shí)目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等；）有時(shí)目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等； 2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入）當(dāng)某些運(yùn)

37、輸線路上的能力有限制時(shí)，在模型中直接加入約束條件（等式或不等式約束約束條件（等式或不等式約束)； 3）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。地（產(chǎn)大于銷時(shí)）。定理定理: 設(shè)有設(shè)有m個(gè)產(chǎn)地個(gè)產(chǎn)地n個(gè)銷地且產(chǎn)銷平衡的運(yùn)輸問題，則基變個(gè)銷地且產(chǎn)銷平衡的運(yùn)輸問題，則基變量數(shù)為量數(shù)為m+n-1。Page 1132022-4-24運(yùn)籌學(xué)表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其實(shí)質(zhì)是單純實(shí)質(zhì)是單純形法。形法。步驟步驟描述描述方法方法第一步第一步求初始基行可行解（初始調(diào)運(yùn)方案）求初始基行可

38、行解（初始調(diào)運(yùn)方案）最小元素法、最小元素法、元素差額法、元素差額法、第二步第二步求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗(yàn)數(shù)檢驗(yàn)數(shù) ij ij全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)數(shù) ij ij 00，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位閉回路法和位勢(shì)法勢(shì)法第三步第三步調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步Page 1142022-4-24運(yùn)籌學(xué)例例3.2 3.2 某運(yùn)輸

39、資料如下表所示：某運(yùn)輸資料如下表所示：單位單位 銷地銷地 運(yùn)價(jià)運(yùn)價(jià) 產(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)運(yùn)可使總運(yùn)輸費(fèi)用最?。繂枺簯?yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。縋age 1152022-4-24運(yùn)籌學(xué)解：第解：第1步步 求初始方案求初始方案方法方法1：最小元素法：最小元素法 基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開始供應(yīng)（調(diào)基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。運(yùn)），然后次小，直到最后供完為止。B1B

40、2B3B4產(chǎn)量產(chǎn)量A17A2 4A39銷量銷量3656311310192741058341633Page 1162022-4-24運(yùn)籌學(xué)總的運(yùn)輸費(fèi)總的運(yùn)輸費(fèi)(31)+(64) +(43) +(12)+(310)+(35)=86元元元素差額法對(duì)最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷元素差額法對(duì)最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額，如果差額很大，就選地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。例如下面兩種運(yùn)輸方最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。例如下面兩種運(yùn)輸方案。案。85102120151515510總運(yùn)費(fèi)是總運(yùn)費(fèi)是z=10

41、8+52+151=105最小元素法：最小元素法：Page 1172022-4-24運(yùn)籌學(xué)85102120151551510總運(yùn)費(fèi)總運(yùn)費(fèi)z=105+152+51=85后一種方案考慮到后一種方案考慮到C11與與C21之間之間的差額是的差額是82=6，如果不先調(diào)運(yùn)，如果不先調(diào)運(yùn)x21，到后來就有可能，到后來就有可能x110，這，這樣會(huì)使總運(yùn)費(fèi)增加較大，從而先樣會(huì)使總運(yùn)費(fèi)增加較大，從而先調(diào)運(yùn)調(diào)運(yùn)x21，再是，再是x22，其次是，其次是x12用元素差額法求得的基本可行解更接近最優(yōu)解，所用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。以也稱為近似方案。Page 1182022-4-24運(yùn)籌學(xué)

42、方法方法2：Vogel法法1）從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)）從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。費(fèi)的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A39銷量銷量3656311310192741058Page 1192022-4-24運(yùn)籌學(xué)2）再從差值最大的行或列中找出最小運(yùn)價(jià)確定供需關(guān)系和）再從差值最大的行或列中找出最小運(yùn)價(jià)確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列。時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或

43、列。重復(fù)重復(fù)1)和和2)，直到找出初始解為至。，直到找出初始解為至。B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A3 9銷量銷量3656311310192741058Page 1202022-4-24運(yùn)籌學(xué)單位單位 銷地銷地 運(yùn)價(jià)運(yùn)價(jià) 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA71135215Page 1212022-4-24運(yùn)籌學(xué)單位單位 銷地銷地 運(yùn)價(jià)運(yùn)價(jià) 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA71352753Page 1222022

44、-4-24運(yùn)籌學(xué)單位單位 銷地銷地 運(yùn)價(jià)運(yùn)價(jià) 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA11351536312該方案的總運(yùn)費(fèi)該方案的總運(yùn)費(fèi):(13)(46)(35)(210)(18)(35)85元元Page 1232022-4-24運(yùn)籌學(xué)求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗(yàn)數(shù)來判斷，記驗(yàn)數(shù)來判斷，記xij的檢驗(yàn)數(shù)為的檢驗(yàn)數(shù)為ij由第一章知，求最小值的運(yùn)由第一章知，求最小值的運(yùn)輸問題的最優(yōu)判別準(zhǔn)則是：輸問題的最優(yōu)判別準(zhǔn)則是：所有非基變量的檢驗(yàn)數(shù)都非負(fù)，則運(yùn)

45、輸方案最優(yōu)所有非基變量的檢驗(yàn)數(shù)都非負(fù)，則運(yùn)輸方案最優(yōu)求檢驗(yàn)數(shù)的方法有兩種：求檢驗(yàn)數(shù)的方法有兩種： 閉回路法閉回路法 位勢(shì)法（位勢(shì)法（）Page 1242022-4-24運(yùn)籌學(xué)閉回路的概念閉回路的概念,132222111jsisjsijijijijixxxxxx稱稱集集合合),(2121互互不不相相同同；其其中中ssjjjiii為一個(gè)閉回路為一個(gè)閉回路 ，集合中的變量稱為回路的頂點(diǎn)，相鄰兩個(gè)變，集合中的變量稱為回路的頂點(diǎn)，相鄰兩個(gè)變量的連線為閉回路的邊。如下表量的連線為閉回路的邊。如下表Page 1252022-4-24運(yùn)籌學(xué)例下表中閉回路的變量集合是例下表中閉回路的變量集合是x11,x12,x

46、42,x43,x23,x25,x35, x31共共有有8個(gè)頂點(diǎn)，這個(gè)頂點(diǎn)，這8個(gè)頂點(diǎn)間用水平或垂直線段連接起來，組成個(gè)頂點(diǎn)間用水平或垂直線段連接起來，組成一條封閉的回路。一條封閉的回路。 B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43 一條回路中的頂點(diǎn)數(shù)一定是偶數(shù)，回路遇到頂點(diǎn)必須轉(zhuǎn)一條回路中的頂點(diǎn)數(shù)一定是偶數(shù)，回路遇到頂點(diǎn)必須轉(zhuǎn)90度與另一頂點(diǎn)連接，表度與另一頂點(diǎn)連接，表33中的變量中的變量x 32及及x33不是閉回路的頂不是閉回路的頂點(diǎn)，只是連線的交點(diǎn)。點(diǎn)，只是連線的交點(diǎn)。 Page 1262022-4-24運(yùn)籌學(xué)閉回路閉回路,123233434111

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

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

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

50、的變量減去調(diào)整量，其余變量不變，得到一組新的，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn)。基可行解。然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn)。Page 1302022-4-24運(yùn)籌學(xué)當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí)，則當(dāng)前調(diào)運(yùn)方案即為最當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí)，則當(dāng)前調(diào)運(yùn)方案即為最優(yōu)方案，如表此時(shí)最小總運(yùn)費(fèi)：優(yōu)方案，如表此時(shí)最小總運(yùn)費(fèi)：Z =(13)(46)(35)(210)(18)(35)85元元B1B2B3B4UiA1A2A3Vj311310192741058536312Page 1312022-4-24運(yùn)籌學(xué)表上作業(yè)法的計(jì)算步驟：表上作業(yè)法的計(jì)算步驟：分析實(shí)際問

51、題列出產(chǎn)銷平分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案（最小確定初始調(diào)運(yùn)方案（最小元素法或元素法或Vogel法）法）求檢驗(yàn)數(shù)（位勢(shì)法）求檢驗(yàn)數(shù)（位勢(shì)法）所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)0找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，用閉合找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，用閉合回路調(diào)整，得到新的調(diào)運(yùn)方案回路調(diào)整，得到新的調(diào)運(yùn)方案得到最優(yōu)方案，得到最優(yōu)方案，算出總運(yùn)價(jià)算出總運(yùn)價(jià)Page 1322022-4-24運(yùn)籌學(xué)（1）若運(yùn)輸問題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)）若運(yùn)輸問題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入

52、變量均可使目標(biāo)函數(shù)值得到改善，但通常取目標(biāo)函數(shù)值得到改善，但通常取ij0中最小者對(duì)應(yīng)的變量為中最小者對(duì)應(yīng)的變量為換入變量。換入變量。（2）無窮多最優(yōu)解）無窮多最優(yōu)解產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的ij0，則該問題有無窮多最優(yōu)解。，則該問題有無窮多最優(yōu)解。Page 1332022-4-24運(yùn)籌學(xué) 退化解：退化解： 表格中一般要有表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證，以保證有有(m+n-1)個(gè)數(shù)字格作為

53、基變量。一般可在劃去的行和列的個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個(gè)任意空格處加一個(gè)0即可。即可。 利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的最小運(yùn)量（超過最小運(yùn)量（超過2個(gè)最小值）作為調(diào)整量個(gè)最小值）作為調(diào)整量，選擇任意一個(gè)最，選擇任意一個(gè)最小運(yùn)量對(duì)應(yīng)的基變量作為出基變量，并打上小運(yùn)量對(duì)應(yīng)的基變量作為出基變量，并打上“”以示作為以示作為非基變量。非基變量。Page 1342022-4-24運(yùn)籌學(xué) 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A116A210A322銷量銷量81412141241148310295116(0)(2

54、)(9)(2)(1)(12)如下例中如下例中11檢驗(yàn)數(shù)是檢驗(yàn)數(shù)是 0，經(jīng)過調(diào)整，可得到另一個(gè)最優(yōu)解。，經(jīng)過調(diào)整，可得到另一個(gè)最優(yōu)解。 Page 1352022-4-24運(yùn)籌學(xué) 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量365620114431377821060在在x12、x22、x33、x34中任選一個(gè)變量作為基變量，例如選中任選一個(gè)變量作為基變量，例如選x34例：用最小元素法求初始可行解例：用最小元素法求初始可行解Page 1362022-4-24運(yùn)籌學(xué)2.目標(biāo)函數(shù)求利潤最大或營業(yè)額最大等問題。目標(biāo)函數(shù)求利潤最大或營業(yè)額最大等問題。 minjijijxCZ11max

55、njmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，Page 1372022-4-24運(yùn)籌學(xué)求解方法：求解方法：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運(yùn)價(jià)將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運(yùn)價(jià)表為表為C ，用一個(gè)較大的數(shù)，用一個(gè)較大的數(shù)M（Mmaxcij）去減每一個(gè)）去減每一個(gè)cij得得到矩陣到矩陣C，其中，其中C=（Mcij）0,將將C作為極小化問題的運(yùn)作為極小化問題的運(yùn)價(jià)表，用表上用業(yè)法求出最優(yōu)解。價(jià)表，用表上用業(yè)法求出最優(yōu)解。Page 1382022-4-24運(yùn)籌學(xué)例例3.3 下列矩陣下列矩陣C是是Ai（I=

56、1，2，3）到）到Bj的噸公里利潤的噸公里利潤,運(yùn)輸運(yùn)輸部門如何安排運(yùn)輸方案使總利潤最大部門如何安排運(yùn)輸方案使總利潤最大. 銷地銷地產(chǎn)地產(chǎn)地B1B2B3產(chǎn)量產(chǎn)量A1A2A3銷量銷量ijijijccccM 10,10max/22取取Page 1392022-4-24運(yùn)籌學(xué) 銷地銷地產(chǎn)地產(chǎn)地B1B2B3產(chǎn)量產(chǎn)量A1A2A3銷量銷量得到新的最小化運(yùn)輸問題，用表上作業(yè)法求解即可。得到新的最小化運(yùn)輸問題，用表上作業(yè)法求解即可。Page 1402022-4-24運(yùn)籌學(xué)3.當(dāng)總產(chǎn)量與總銷量不相等時(shí)當(dāng)總產(chǎn)量與總銷量不相等時(shí),稱為不平衡運(yùn)輸問題稱為不平衡運(yùn)輸問題.這類這類運(yùn)輸問題在實(shí)際中常常碰到運(yùn)輸問題在實(shí)際中

57、常常碰到,它的求解方法是將不平衡問題它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。化為平衡問題再按平衡問題求解。 當(dāng)產(chǎn)大于銷時(shí)，即：當(dāng)產(chǎn)大于銷時(shí)，即： minjjiba11數(shù)學(xué)模型為：數(shù)學(xué)模型為： minjijijxcZ11min njmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，Page 1412022-4-24運(yùn)籌學(xué)由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須就地庫存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉庫，假設(shè)該倉庫為一個(gè)虛擬必須就地庫存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉庫

58、，假設(shè)該倉庫為一個(gè)虛擬銷地銷地Bn+1， bn+1作為一個(gè)虛設(shè)銷地作為一個(gè)虛設(shè)銷地Bn+1的銷量的銷量(即庫存量即庫存量)。各產(chǎn)地。各產(chǎn)地Ai到到Bn+1的運(yùn)價(jià)為零，即的運(yùn)價(jià)為零，即Ci,n+1=0,（i=1，m）。則平衡問題的）。則平衡問題的數(shù)學(xué)模型為：數(shù)學(xué)模型為： minjijijxcZ11min , 2 , 1, 2 , 1, 01, 2 , 1, 2 , 1111jmixnjbxmiaxijmijijnjiij；具體求解時(shí)具體求解時(shí), ,只在只在運(yùn)價(jià)表右端增加運(yùn)價(jià)表右端增加一列一列B Bn n+1+1，運(yùn)價(jià)，運(yùn)價(jià)為零為零, ,銷量為銷量為b bn n+1+1即可即可Page 14220

59、22-4-24運(yùn)籌學(xué) 當(dāng)銷大于產(chǎn)時(shí)，即：當(dāng)銷大于產(chǎn)時(shí)，即： minjjiba11 minjijijxCZ11min , 2 , 1;, 2 , 1, 0, 2 , 1, 2 , 111jmixnjbxmiaxijmijijnjiij數(shù)學(xué)模型為：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)由于總銷量大于總產(chǎn)量量,故一定有些需求地故一定有些需求地不完全滿足不完全滿足,這時(shí)虛設(shè)這時(shí)虛設(shè)一個(gè)產(chǎn)地一個(gè)產(chǎn)地Am+1，產(chǎn)量，產(chǎn)量為：為： miinjjab11Page 1432022-4-24運(yùn)籌學(xué)銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為 ： minjijijxcZ11min njmixnjbxmi

60、axijmijijnjiji, 2 , 11, 2 , 1, 0, 2 , 11, 2 , 1111；具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)，運(yùn)價(jià)為零。產(chǎn)量為量為am+1即可。即可。 Page 1442022-4-24運(yùn)籌學(xué)例例3.4 求下列表中極小化運(yùn)輸問題的最優(yōu)解。求下列表中極小化運(yùn)輸問題的最優(yōu)解。 B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160 4141160180ijjiba因?yàn)橛校阂驗(yàn)橛校篜age 1452022-4-24運(yùn)籌學(xué)所以是一個(gè)產(chǎn)大于銷的運(yùn)輸問題。表