運(yùn)籌學(xué)課件版

1、運(yùn) 籌 學(xué)( Operations Research )經(jīng)濟(jì)學(xué)核心課程緒 論（1）運(yùn)籌學(xué)簡(jiǎn)述（2）運(yùn)籌學(xué)的主要內(nèi)容（3）本課程的教材及參考書（4）本課程的特點(diǎn)和要求（5）本課程授課方式與考核 （6）運(yùn)籌學(xué)在工商管理中的應(yīng)用本章主要內(nèi)容：運(yùn)籌學(xué)簡(jiǎn)述運(yùn)籌學(xué)（Operations Research）系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國(guó)有人把運(yùn)籌學(xué)稱之為管理科學(xué)(Management Science)。運(yùn)籌學(xué)所研究的問題，可簡(jiǎn)單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術(shù)。運(yùn)籌學(xué)簡(jiǎn)述運(yùn)籌學(xué)的歷史“運(yùn)作研究(Operational Research)小組”:解

2、決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如：如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍德空襲對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)損失最少；在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷力等。運(yùn)籌學(xué)的主要內(nèi)容數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃等）圖論存儲(chǔ)論排隊(duì)論對(duì)策論排序與統(tǒng)籌方法決策分析本課程的教材及參考書選用教材 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用胡運(yùn)權(quán)主編 哈工大出版社參考教材運(yùn)籌學(xué)教程胡運(yùn)權(quán)主編 （第2版）清華出版社管理運(yùn)籌學(xué)韓伯棠主編 （第2版）高等教育出版社運(yùn)籌學(xué)(修訂版) 錢頌迪主編 清華出版社 本課程的特點(diǎn)和要求先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點(diǎn)：系統(tǒng)整體優(yōu)化；多學(xué)科的

3、配合；模型方法的應(yīng)用運(yùn)籌學(xué)的研究的主要步驟：真實(shí)系統(tǒng)系統(tǒng)分析問題描述模型建立與修改模型求解與檢驗(yàn)結(jié)果分析與實(shí)施數(shù)據(jù)準(zhǔn)備本課程授課方式與考核學(xué)科總成績(jī)平時(shí)成績(jī)（40）課堂考勤（50）平時(shí)作業(yè)（50）期末成績(jī)（60）講授為主，結(jié)合習(xí)題作業(yè)運(yùn)籌學(xué)在工商管理中的應(yīng)用運(yùn)籌學(xué)在工商管理中的應(yīng)用涉及幾個(gè)方面： 生產(chǎn)計(jì)劃 運(yùn)輸問題 人事管理 庫(kù)存管理 市場(chǎng)營(yíng)銷 財(cái)務(wù)和會(huì)計(jì)另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項(xiàng)目的選擇與評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)等。運(yùn)籌學(xué)在工商管理中的應(yīng)用Interface上發(fā)表的部分獲獎(jiǎng)項(xiàng)目組織應(yīng)用效果聯(lián)合航空公司在滿足乘客需求的前提下，以最低成本進(jìn)行訂票及機(jī)場(chǎng)工作班次安排每年節(jié)約成本600萬(wàn)

4、美元Citgo石油公司優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送和營(yíng)銷每年節(jié)約成本7000萬(wàn)AT&T優(yōu)化商業(yè)用戶的電話銷售中心選址每年節(jié)約成本4.06億美元，銷售額大幅增加標(biāo)準(zhǔn)品牌公司控制成本庫(kù)存（制定最優(yōu)再定購(gòu)點(diǎn)和定購(gòu)量確保安全庫(kù)存）每年節(jié)約成本380萬(wàn)美元法國(guó)國(guó)家鐵路公司制定最優(yōu)鐵路時(shí)刻表并調(diào)整鐵路日運(yùn)營(yíng)量每年節(jié)約成本1500萬(wàn)美元，年收入大幅增加。Taco Bell優(yōu)化員工安排，以最低成本服務(wù)客戶每年節(jié)約成本1300萬(wàn)美元Delta航空公司優(yōu)化配置上千個(gè)國(guó)內(nèi)航線航班來實(shí)現(xiàn)利潤(rùn)最大化每年節(jié)約成本1億美元“管理運(yùn)籌學(xué)”軟件介紹“管理運(yùn)籌學(xué)”2.0版包括：線性規(guī)劃、運(yùn)輸問題、整數(shù)規(guī)劃（0-1整數(shù)規(guī)劃、純整數(shù)

5、規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對(duì)策論、最短路徑、最小生成樹、最大流量、最小費(fèi)用最大流、關(guān)鍵路徑、存儲(chǔ)論、排隊(duì)論、決策分析、預(yù)測(cè)問題和層次分析法，共15個(gè)子模塊。Chapter1 線性規(guī)劃 (Linear Programming) LP的數(shù)學(xué)模型 圖解法 單純形法 單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用本章主要內(nèi)容：線性規(guī)劃問題的數(shù)學(xué)模型1. 規(guī)劃問題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等

6、）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤(rùn)最大.）線性規(guī)劃問題的數(shù)學(xué)模型例1.1 如圖所示，如何截取x使鐵皮所圍成的容積最大？ xa線性規(guī)劃問題的數(shù)學(xué)模型例1.2 某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤(rùn)最大？ 設(shè) 備產(chǎn) 品 A B C D利潤(rùn)（元） 甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 臺(tái) 時(shí) 12 8 16 12線性規(guī)劃問題的數(shù)學(xué)模型解：設(shè)x1、x2分別為

7、甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：max Z = 2x1 + 3x2 x1 0 , x2 0s.t. 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12線性規(guī)劃問題的數(shù)學(xué)模型2. 線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成決策變量 Decision variables 目標(biāo)函數(shù) Objective function約束條件 Constraints其特征是：（1）問題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個(gè)決策變量的線性不等式或等式。 怎樣辨別一個(gè)模型是線性規(guī)劃模型？ 線性規(guī)劃問題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：3. 線性規(guī)劃數(shù)學(xué)模

8、型的一般形式簡(jiǎn)寫為：線性規(guī)劃問題的數(shù)學(xué)模型向量形式：其中：線性規(guī)劃問題的數(shù)學(xué)模型矩陣形式：其中：線性規(guī)劃問題的數(shù)學(xué)模型3. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點(diǎn)：(1) 目標(biāo)函數(shù)求最大值（有時(shí)求最小值）(2) 約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3) 決策變量xj為非負(fù)。線性規(guī)劃問題的數(shù)學(xué)模型（2）如何化標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)的轉(zhuǎn)換 如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問題。也就是：令 ，可得到上式。即 若存在取值無約束的變量 ，可令 其中： 變量的變換線性規(guī)劃問題的數(shù)學(xué)模型 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量 變量 的變換 可令 ，顯然

9、線性規(guī)劃問題的數(shù)學(xué)模型例1.3 將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式用 替換 ，且 解:（）因?yàn)閤3無符號(hào)要求 ，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以線性規(guī)劃問題的數(shù)學(xué)模型(2) 第一個(gè)約束條件是“”號(hào)，在“”左端加入松馳變量x4，x40,化為等式；(3) 第二個(gè)約束條件是“”號(hào)，在“”左端減去剩余變量x5，x50；(4) 第3個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1),將右端常數(shù)項(xiàng)化為正數(shù)； (5) 目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到max z=-z，即當(dāng)z達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然;線性規(guī)劃問題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：線性規(guī)劃問題的數(shù)學(xué)模型4. 線

10、性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。線性規(guī)劃問題的數(shù)學(xué)模型 可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。 最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。 基：設(shè)A為約束條件的mn階系數(shù)矩陣(m04010換出行將3化為15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/52/540011單純形法的計(jì)算步驟例1.9 用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。單純形法的計(jì)算步驟cj12100i

11、cB基變量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x220 x221/3150120753017131/309022560 x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3單純形法的計(jì)算步驟學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及3個(gè)基本定理2. 熟練掌握單純形法的解題思路及求解步驟單純形法的進(jìn)一步討論人工變量法人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基

12、變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。單純形法的進(jìn)一步討論人工變量法例1.10 用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。單純形法的進(jìn)一步討論人工變量法故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。 單純形法的進(jìn)一步討論人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0

13、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/3單純形法的進(jìn)一步討論人工變量法解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線 規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢

14、驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個(gè)k0且aik（i=1，2,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri0時(shí)，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個(gè)基變量為零的基本可行解。單純形法的進(jìn)一步討論人工變量法單純性法小結(jié):建立模型個(gè) 數(shù)取 值右 端 項(xiàng)等式或不等式極大或極小新加變量系數(shù)兩個(gè)三個(gè)以上xj0 xj無約束xj 0 bi 0bi mi 時(shí)，企業(yè)愿意購(gòu)進(jìn)這種資源，單位純利為yi*mi ，則有利可圖；如果yi* mi 則購(gòu)進(jìn)資源i，可獲單位純利yi*mi 若yi* mi則轉(zhuǎn)讓資源i ，可獲單位純利

15、miyi對(duì)偶問題的經(jīng)濟(jì)解釋影子價(jià)格3）影子價(jià)格在資源利用中的應(yīng)用根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理:Y*Xs=0 , YsX*=0表明生產(chǎn)過程中如果某種資源bi未得到充分利用時(shí)，該種資源的影子價(jià)格為0；若當(dāng)資源資源的影子價(jià)格不為0時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完。對(duì)偶問題的經(jīng)濟(jì)解釋影子價(jià)格4）影子價(jià)格對(duì)單純形表計(jì)算的解釋單純形表中的檢驗(yàn)數(shù)其中cj表示第j種產(chǎn)品的價(jià)格; 表示生產(chǎn)該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和,即產(chǎn)品的隱含成本。當(dāng)產(chǎn)值大于隱含成本時(shí)，即 ，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排；否則 ，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。對(duì)偶單純形法 對(duì)偶單純形法是求解線性規(guī)劃

16、的另一個(gè)基本方法。它是根據(jù)對(duì)偶原理和單純形法原理而設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。不要簡(jiǎn)單理解為是求解對(duì)偶問題的單純形法。對(duì)偶單純形法原理對(duì)偶單純形法基本思路： 找出一個(gè)對(duì)偶問題的可行基，保持對(duì)偶問題為可行解的條件下，判斷XB是否可行（XB為非負(fù)），若否，通過變換基解，直到找到原問題基可行解（即XB為非負(fù)），這時(shí)原問題與對(duì)偶問題同時(shí)達(dá)到可行解，由定理4可得最優(yōu)解。對(duì)偶單純形法找出一個(gè)DP的可行基LP是否可行（XB 0）保持DP為可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解最優(yōu)解是否循環(huán)結(jié)束對(duì)偶單純形法例2.9 用對(duì)偶單純形法求解：解:（1）將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求出一組基本解，因

17、為對(duì)偶問題可行，即全部檢驗(yàn)數(shù)0（求max問題）。對(duì)偶單純形法cj-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-150000對(duì)偶單純形法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-342cj-9-12-15000bcB

18、xBx1x2x3x4x5x60 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/14對(duì)偶單純形法cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3原問題的最優(yōu)解為：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72 其對(duì)偶問題的最優(yōu)解為：Y*= （1/3 , 3 , 7/3）

19、，W*= 72對(duì)偶單純形法 對(duì)偶單純形法應(yīng)注意的問題： 用對(duì)偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對(duì)偶問題的最優(yōu)解 初始表中一定要滿足對(duì)偶問題可行，也就是說檢驗(yàn)數(shù)滿足最優(yōu)判別準(zhǔn)則 最小比值中 的絕對(duì)值是使得比值非負(fù)，在極小化問題j0，分母aij0 這時(shí)必須取絕對(duì)值。在極大化問題中， j0，分母aij0， 總滿足非負(fù)，這時(shí)絕對(duì)值符號(hào)不起作用，可以去掉。如在本例中將目標(biāo)函數(shù)寫成這里j 0在求k時(shí)就可以不帶絕對(duì)值符號(hào)。對(duì)偶單純形法 對(duì)偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進(jìn)基變量后確定出基變量，對(duì)偶單純形法是先確定出基變量后確定進(jìn)基變量； 普通單純形法的最小比值是

20、其目的是保證下一個(gè)原問題的基本解可行，對(duì)偶單純形法的最小比值是其目的是保證下一個(gè)對(duì)偶問題的基本解可行 對(duì)偶單純形法在確定出基變量時(shí)，若不遵循 規(guī)則，任選一個(gè)小于零的bi對(duì)應(yīng)的基變量出基，不影響計(jì)算結(jié)果，只是迭代次數(shù)可能不一樣。本章小結(jié)學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及3個(gè)基本定理2. 熟練掌握單純形法的解題思路及求解步驟Chapter3 運(yùn)輸規(guī)劃( Transportation Problem )運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型表上作業(yè)法運(yùn)輸問題的應(yīng)用 本章主要內(nèi)容：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型例3.1 某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往

21、各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？B1B2B3產(chǎn)量A1646200A2655300銷量150150200運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型解：產(chǎn)銷平衡問題：總產(chǎn)量 = 總銷量500 設(shè) xij 為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 15

22、0 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型運(yùn)輸問題的一般形式：產(chǎn)銷平衡A1、 A2、 Am 表示某物資的m個(gè)產(chǎn)地； B1、B2、Bn 表示某物質(zhì)的n個(gè)銷地；ai 表示產(chǎn)地Ai的產(chǎn)量； bj 表示銷地Bj 的銷量； cij 表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè) xij 為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型：運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型變化： 1）有時(shí)目標(biāo)函數(shù)求最大。如求利潤(rùn)最大或營(yíng)業(yè)額最大等； 2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入約束條件（等式或不等式約束)； 3）產(chǎn)銷不平衡時(shí)，可加

23、入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。定理: 設(shè)有m個(gè)產(chǎn)地n個(gè)銷地且產(chǎn)銷平衡的運(yùn)輸問題，則基變量數(shù)為m+n-1。表上作業(yè)法表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其實(shí)質(zhì)是單純形法。步驟描述方法第一步求初始基行可行解（初始調(diào)運(yùn)方案）最小元素法、元素差額法、第二步求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗(yàn)數(shù)ij全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)ij 0，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位勢(shì)法第三步調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步表上作業(yè)法例3.2 某運(yùn)輸資料如下表所示：?jiǎn)挝?銷地 運(yùn)價(jià) 產(chǎn)地產(chǎn)量311310719284741059銷

24、量3656問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。勘砩献鳂I(yè)法解：第1步 求初始方案方法1：最小元素法 基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量A17A2 4A39銷量3656311310192741058341633表上作業(yè)法總的運(yùn)輸費(fèi)(31)+(64) +(43) +(12)+(310)+(35)=86元元素差額法對(duì)最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。例如下面兩種運(yùn)輸方案。85102120151515510總運(yùn)費(fèi)是z=108+52+151=105最小

25、元素法：表上作業(yè)法85102120151551510總運(yùn)費(fèi)z=105+152+51=85后一種方案考慮到C11與C21之間的差額是82=6，如果不先調(diào)運(yùn)x21，到后來就有可能x110，這樣會(huì)使總運(yùn)費(fèi)增加較大，從而先調(diào)運(yùn)x21，再是x22，其次是x12用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。表上作業(yè)法方法2：Vogel法1）從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量行差額A177A2 41A391銷量3656列差額2513311310192741058表上作業(yè)法2）再?gòu)牟钪底畲蟮男谢蛄兄姓页鲎钚∵\(yùn)價(jià)確定供需關(guān)

26、系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列。重復(fù)1)和2)，直到找出初始解為至。B1B2B3B4產(chǎn)量行差額A177A2 41A3 91銷量3656列差額25133113101927410585表上作業(yè)法單位 銷地 運(yùn)價(jià) 產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額71135215表上作業(yè)法單位 銷地 運(yùn)價(jià) 產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額71352753表上作業(yè)法單位 銷地 運(yùn)價(jià) 產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額11351536312該方案的總運(yùn)費(fèi):(13)

27、(46)(35)(210)(18)(35)85元表上作業(yè)法第2步 最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗(yàn)數(shù)來判斷，記xij的檢驗(yàn)數(shù)為ij由第一章知，求最小值的運(yùn)輸問題的最優(yōu)判別準(zhǔn)則是：所有非基變量的檢驗(yàn)數(shù)都非負(fù)，則運(yùn)輸方案最優(yōu)求檢驗(yàn)數(shù)的方法有兩種： 閉回路法 位勢(shì)法（）表上作業(yè)法閉回路的概念為一個(gè)閉回路 ，集合中的變量稱為回路的頂點(diǎn)，相鄰兩個(gè)變量的連線為閉回路的邊。如下表表上作業(yè)法例下表中閉回路的變量集合是x11,x12,x42,x43,x23,x25,x35, x31共有8個(gè)頂點(diǎn)，這8個(gè)頂點(diǎn)間用水平或垂直線段連接起來，組成一條封閉的回路。 B1B2B3

28、B4B5A1X11X12A2X23X25A3X31X35A4X42X43 一條回路中的頂點(diǎn)數(shù)一定是偶數(shù)，回路遇到頂點(diǎn)必須轉(zhuǎn)90度與另一頂點(diǎn)連接，表33中的變量x 32及x33不是閉回路的頂點(diǎn)，只是連線的交點(diǎn)。 表上作業(yè)法閉回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如變量組 不能構(gòu)成一條閉回路，但A中包含有閉回路 變量組 變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路； 表上作業(yè)法用位勢(shì)法對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)：1）由ij=Cij-（Ui+Vj）計(jì)算位勢(shì)Ui ， Vj ，因?qū)兞慷杂衖j=0，即Cij-（Ui+Vj） = 0，令U1=02）再由ij=Cij-（Ui

29、+Vj）計(jì)算非基變量的檢驗(yàn)數(shù)ijB1B2B3B4UiA1A2A3Vj3113101927410584363130-1-531029（1）（2）（1）（-1）（10）（12）當(dāng)存在非基變量的檢驗(yàn)數(shù)kl 0，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。表上作業(yè)法當(dāng)存在非基變量的檢驗(yàn)數(shù)kl 0 且kl =minij時(shí)，令Xkl 進(jìn)基。從表中知可選X24進(jìn)基。第3步 確定換入基的變量第4步 確定換出基的變量以進(jìn)基變量xik為起點(diǎn)的閉回路中，標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量，對(duì)應(yīng)的基變量為出基變量，并打上“”以示換出作為非基變量。表上作業(yè)法B1B2B3B4UiA1A2A3Vj31131019274

30、1058436313()()()()調(diào)整步驟為：在進(jìn)基變量的閉回路中標(biāo)有正號(hào)的變量加上調(diào)整量，標(biāo)有負(fù)號(hào)的變量減去調(diào)整量，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn)。125表上作業(yè)法當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí)，則當(dāng)前調(diào)運(yùn)方案即為最優(yōu)方案，如表此時(shí)最小總運(yùn)費(fèi)：Z =(13)(46)(35)(210)(18)(35)85元B1B2B3B4UiA1A2A3Vj3113101927410585363120-2-531039（0）（2）（2）（1）（12）（9）表上作業(yè)法表上作業(yè)法的計(jì)算步驟：分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案（最小元素法或Vogel法）

31、求檢驗(yàn)數(shù)（位勢(shì)法）所有檢驗(yàn)數(shù)0找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，用閉合回路調(diào)整，得到新的調(diào)運(yùn)方案得到最優(yōu)方案，算出總運(yùn)價(jià)表上作業(yè)法表上作業(yè)法計(jì)算中的問題：（1）若運(yùn)輸問題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取ij0中最小者對(duì)應(yīng)的變量為換入變量。（2）無窮多最優(yōu)解產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的ij0，則該問題有無窮多最優(yōu)解。表上作業(yè)法 退化解： 表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證有(m+n-1)個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的任意

32、空格處加一個(gè)0即可。 利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的最小運(yùn)量（超過2個(gè)最小值）作為調(diào)整量，選擇任意一個(gè)最小運(yùn)量對(duì)應(yīng)的基變量作為出基變量，并打上“”以示作為非基變量。表上作業(yè)法 銷地產(chǎn)地B1B2B3B4產(chǎn)量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中11檢驗(yàn)數(shù)是 0，經(jīng)過調(diào)整，可得到另一個(gè)最優(yōu)解。 表上作業(yè)法 銷地產(chǎn)地B1B2B3B4產(chǎn)量A17A24A39銷量36562011443137782106341606在x12、x22、x33、x34中任選一個(gè)變量作為基變量，例如選x34例：用最小

33、元素法求初始可行解運(yùn)輸問題的應(yīng)用 求極大值問題目標(biāo)函數(shù)求利潤(rùn)最大或營(yíng)業(yè)額最大等問題。運(yùn)輸問題的應(yīng)用求解方法：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運(yùn)價(jià)表為C ，用一個(gè)較大的數(shù)M（Mmaxcij）去減每一個(gè)cij得到矩陣C，其中C=（Mcij）0,將C作為極小化問題的運(yùn)價(jià)表，用表上用業(yè)法求出最優(yōu)解。運(yùn)輸問題的應(yīng)用例3.3 下列矩陣C是Ai（I=1，2，3）到Bj的噸公里利潤(rùn),運(yùn)輸部門如何安排運(yùn)輸方案使總利潤(rùn)最大. 銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量8149運(yùn)輸問題的應(yīng)用 銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量8149得到新

34、的最小化運(yùn)輸問題，用表上作業(yè)法求解即可。運(yùn)輸問題的應(yīng)用 產(chǎn)銷不平衡的運(yùn)輸問題當(dāng)總產(chǎn)量與總銷量不相等時(shí),稱為不平衡運(yùn)輸問題.這類運(yùn)輸問題在實(shí)際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。 當(dāng)產(chǎn)大于銷時(shí)，即：數(shù)學(xué)模型為：運(yùn)輸問題的應(yīng)用由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須就地庫(kù)存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉(cāng)庫(kù)，假設(shè)該倉(cāng)庫(kù)為一個(gè)虛擬銷地Bn+1， bn+1作為一個(gè)虛設(shè)銷地Bn+1的銷量(即庫(kù)存量)。各產(chǎn)地Ai到Bn+1的運(yùn)價(jià)為零，即Ci,n+1=0,（i=1，m）。則平衡問題的數(shù)學(xué)模型為：具體求解時(shí),只在運(yùn)價(jià)表右端增加一列Bn+1，運(yùn)價(jià)為零,銷量為bn+1即可運(yùn)

35、輸問題的應(yīng)用 當(dāng)銷大于產(chǎn)時(shí)，即：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時(shí)虛設(shè)一個(gè)產(chǎn)地Am+1，產(chǎn)量為：運(yùn)輸問題的應(yīng)用銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為 ：具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)量為am+1即可。 運(yùn)輸問題的應(yīng)用例3.4 求下列表中極小化運(yùn)輸問題的最優(yōu)解。 B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160因?yàn)橛校哼\(yùn)輸問題的應(yīng)用所以是一個(gè)產(chǎn)大于銷的運(yùn)輸問題。表中A2不可達(dá)B1，用一個(gè)很大的正數(shù)M表示運(yùn)價(jià)C21。虛設(shè)一個(gè)銷量為b5=180-160=20，Ci5=0，i=1

36、,2,3,4，表的右邊增添一列 ，得到新的運(yùn)價(jià)表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180運(yùn)輸問題的應(yīng)用下表為計(jì)算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個(gè)單位沒有運(yùn)出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180運(yùn)輸問題的應(yīng)用3. 生產(chǎn)與儲(chǔ)存問題例3.5 某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需

37、儲(chǔ)存、維護(hù)等費(fèi)用0.15萬(wàn)元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。季度生產(chǎn)能力/臺(tái)單位成本/萬(wàn)元2510.83511.130111011.3運(yùn)輸問題的應(yīng)用解： 設(shè) xij為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：交貨： x11 = 10 生產(chǎn)：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第 i 個(gè)生產(chǎn)廠的產(chǎn)量；

38、把第 j 季度交貨的柴油機(jī)數(shù)目看作第 j 個(gè)銷售點(diǎn)的銷量；設(shè)cij是第i季度生產(chǎn)的第j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本，應(yīng)該等于該季度單位成本加上儲(chǔ)存、維護(hù)等費(fèi)用?？蓸?gòu)造下列產(chǎn)銷平衡問題：運(yùn)輸問題的應(yīng)用 ji產(chǎn)量10.810.9511.111.2525M11.1011.2511.4035MM11.0011.1530MMM11.3010銷量10152520 10070由于產(chǎn)大于銷，加上一個(gè)虛擬的銷地D，化為平衡問題，即可應(yīng)用表上作業(yè)法求解。運(yùn)輸問題的應(yīng)用該問題的數(shù)學(xué)模型：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.2

39、5 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 jiD產(chǎn)量10.810.9511.111.25025M11.1011.2511.40035MM11.0011.15030MMM11.30010銷量1015252030 100100運(yùn)輸問題的應(yīng)用 jiD產(chǎn)量1015025053035255301010銷量1015252030 100100最優(yōu)生產(chǎn)決策如下表，最小費(fèi)用z773萬(wàn)元。Chapter4 整數(shù)規(guī)劃( Integer Programming )整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用分支定界法分配問題與匈牙利法本章主要內(nèi)容：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃（簡(jiǎn)稱：IP）

40、要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個(gè)線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)線性規(guī)劃問題的種類： 純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃。 混合整數(shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。 0-1型整數(shù)線性規(guī)劃：決策變量只能取值0或1的整數(shù)線性規(guī)劃。整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃的典型例子例4.1 工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故需要再建一

41、家工廠。相應(yīng)的建廠方案有A3和A4兩個(gè)。這種物資的需求地有B1,B2,B3,B4四個(gè)。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)cij，見下表：B1B2B3B4年生產(chǎn)能力A12934400A28357600A37612200A44525200年需求量350400300150工廠A3或A4開工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬(wàn)或1500萬(wàn)元?，F(xiàn)要決定應(yīng)該建設(shè)工廠A3還是A4，才能使今后每年的總費(fèi)用最少。整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用解：這是一個(gè)物資運(yùn)輸問題，特點(diǎn)是事先不能確定應(yīng)該建A3還是A4中哪一個(gè)，因而不知道新廠投產(chǎn)后的實(shí)際生產(chǎn)物資。為此，引入0-1變量：再設(shè)xij為由Ai運(yùn)往B

42、j的物資數(shù)量，單位為千噸；z表示總費(fèi)用，單位萬(wàn)元。則該規(guī)劃問題的數(shù)學(xué)模型可以表示為：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用混合整數(shù)規(guī)劃問題整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用例4.2 現(xiàn)有資金總額為B?？晒┻x擇的投資項(xiàng)目有n個(gè)，項(xiàng)目j所需投資額和預(yù)期收益分別為aj和cj（j1,2,.,n），此外由于種種原因，有三個(gè)附加條件：若選擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目2。反之不一定項(xiàng)目3和4中至少選擇一個(gè)；項(xiàng)目5,6,7中恰好選擇2個(gè)。應(yīng)該怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大。整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用解：對(duì)每個(gè)投資項(xiàng)目都有被選擇和不被選擇兩種可能，因此分別用0和1表示，令xj表示第j個(gè)項(xiàng)目的決策選擇，記為：投資問題可以表示為：整數(shù)規(guī)劃的特點(diǎn)

43、及應(yīng)用例4.3 指派問題或分配問題。人事部門欲安排四人到四個(gè)不同崗位工作，每個(gè)崗位一個(gè)人。經(jīng)考核四人在不同崗位的成績(jī)（百分制）如表所示，如何安排他們的工作使總成績(jī)最好。 工作人員ABCD甲85927390乙95877895丙82837990丁86908088整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用設(shè) 數(shù)學(xué)模型如下：要求每人做一項(xiàng)工作，約束條件為：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用每項(xiàng)工作只能安排一人，約束條件為：變量約束：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃問題解的特征： 整數(shù)規(guī)劃問題的可行解集合是它松弛問題可行解集合的一個(gè)子集，任意兩個(gè)可行解的凸組合不一定滿足整數(shù)約束條件，因而不一定仍為可行解。 整數(shù)規(guī)劃問題的可行解一定是它的松弛問

44、題的可行解（反之不一定），但其最優(yōu)解的目標(biāo)函數(shù)值不會(huì)優(yōu)于后者最優(yōu)解的目標(biāo)函數(shù)值。整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用例4.3 設(shè)整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用用圖解法求出最優(yōu)解為：x13/2, x2 = 10/3，且有Z = 29/6現(xiàn)求整數(shù)解(最優(yōu)解):如用舍入取整法可得到4個(gè)點(diǎn)即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。x1x233(3/2,10/3)按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如右圖所示。其中(2,2),(3,1)點(diǎn)的目

45、標(biāo)函數(shù)值最大，即為Z=4。整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃問題的求解方法： 分支定界法和割平面法 匈牙利法（指派問題）分支定界法1）求整數(shù)規(guī)劃的松弛問題最優(yōu)解；若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉(zhuǎn)下一步；2）分支與定界：任意選一個(gè)非整數(shù)解的變量xi，在松弛問題中加上約束：xixi 和 xixi+1組成兩個(gè)新的松弛問題，稱為分枝。新的松弛問題具有特征：當(dāng)原問題是求最大值時(shí)，目標(biāo)值是分枝問題的上界；當(dāng)原問題是求最小值時(shí)，目標(biāo)值是分枝問題的下界。檢查所有分枝的解及目標(biāo)函數(shù)值，若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分枝的目標(biāo)值，則將其它分枝剪去不再計(jì)算，若還存在非整

46、數(shù)解并且目標(biāo)值大于(max)整數(shù)解的目標(biāo)值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。分支定界法的解題步驟：分支定界法例4.4 用分枝定界法求解整數(shù)規(guī)劃問題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題(原整數(shù)規(guī)劃問題的松馳問題)LPIP分支定界法用圖解法求松弛問題的最優(yōu)解，如圖所示。x1x23(18/11,40/11)21123x118/11, x2 =40/11Z=218/11(19.8)即Z 也是IP最小值的下限。對(duì)于x118/111.64，取值x1 1， x1 2對(duì)于x2 =40/11 3.64，取值x2 3 ，x2 4先將（LP）劃分為（LP1）和（LP2）,取x1 1, x1 2分支定界法

47、分支：分別求出（LP1）和（LP2）的最優(yōu)解。分支定界法先求LP1,如圖所示。此時(shí)在B點(diǎn)取得最優(yōu)解。x11, x2 =3, Z(1)16找到整數(shù)解，問題已探明，此枝停止計(jì)算。x1x233(18/11,40/11)11BAC同理求LP2,如圖所示。在C 點(diǎn)取得最優(yōu)解。即:x12, x2 =10/3, Z(2)56/318.7 Z(2) Z(1)16 原問題有比16更小的最優(yōu)解，但 x2 不是整數(shù)，故繼續(xù)分支。分支定界法在IP2中分別再加入條件： x23, x24 得下式兩支：分別求出LP21和LP22的最優(yōu)解分支定界法x1x233(18/11,40/11)11BACD先求LP21,如圖所示。此時(shí)

48、D 在點(diǎn)取得最優(yōu)解。即 x112/52.4, x2 =3, Z(21)-87/5-17.4 Z(211) 如對(duì)LP212繼續(xù)分解，其最小值也不會(huì)低于15.5 ，問題探明,剪枝。分支定界法原整數(shù)規(guī)劃問題的最優(yōu)解為: x1=2, x2 =3, Z* =17以上的求解過程可以用一個(gè)樹形圖表示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=12/5, x2=3Z(21) 17.4LP22無可行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(21

49、2) 15.5x11x12x23x24x12x13分支定界法例4.5 用分枝定界法求解解: 先求對(duì)應(yīng)的松弛問題（記為L(zhǎng)P0）用圖解法得到最優(yōu)解X(3.57,7.14),Z0=35.7,如下圖所示。分支定界法1010松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC分支定界法10 x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5分支定界法10 x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336分支定界法10 x1x2oACLP1346LP211:X=(4,6),Z21

50、1=34LP212:X=(5,5),Z212=355LP212分支定界法上述分枝過程可用下圖表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z21=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22無可行解x27小結(jié)學(xué)習(xí)要點(diǎn)： 掌握一般整數(shù)規(guī)劃問題概念及模型結(jié)構(gòu) 掌握分支定界法原理 能夠用分支定界法求解一般整數(shù)規(guī)劃問題課后練習(xí)：分配問題與匈牙利法指派問題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式：設(shè)n 個(gè)人被分配

51、去做n 件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第i個(gè)人去做第j 件工作的效率（ 時(shí)間或費(fèi)用）為Cij(i=1.2n;j=1.2n)并假設(shè)Cij 0。問應(yīng)如何分配才能使總效率（ 時(shí)間或費(fèi)用）最高？設(shè)決策變量 分配問題與匈牙利法指派問題的數(shù)學(xué)模型為：分配問題與匈牙利法克尼格定理 :如果從分配問題效率矩陣aij的每一行元素中分別減去(或加上)一個(gè)常數(shù)ui，從每一列中分別減去(或加上)一個(gè)常數(shù)vj，得到一個(gè)新的效率矩陣bij，則以bij為效率矩陣的分配問題與以aij為效率矩陣的分配問題具有相同的最優(yōu)解。分配問題與匈牙利法指派問題的求解步驟：1) 變換指派問題的系數(shù)矩陣(cij)為

52、(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即 從(cij)的每行元素都減去該行的最小元素； 再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。2) 進(jìn)行試指派，以尋求最優(yōu)解。 在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。分配問題與匈牙利法找獨(dú)立0元素，常用的步驟為： 從只有一個(gè)0元素的行開始，給該行中的0元素加圈，記作 。然后劃去 所在列的其它0元素，記作 ；這表示該列所代表的任務(wù)已指派完，不必再考慮別人了。依次進(jìn)行到最后一行。 從只有一個(gè)0元素的列開始（畫的不計(jì)在內(nèi)），給該列中的0元素

53、加圈，記作；然后劃去 所在行的0元素，記作 ，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進(jìn)行到最后一列。 若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。分配問題與匈牙利法 若 元素的數(shù)目m 等于矩陣的階數(shù)n（即：mn），那么這指派問題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。3) 用最少的直線通過所有0元素。其方法： 對(duì)沒有的行打“”； 對(duì)已打“” 的行中所有含元素的列打“” ； 再對(duì)打有“”的列中含

54、元素的行打“” ； 重復(fù)、直到得不出新的打號(hào)的行、列為止； 對(duì)沒有打號(hào)的行畫橫線，有打號(hào)的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù) l 。注：l 應(yīng)等于m，若不相等，說明試指派過程有誤，回到第2步，另行試指派；若 lm n，表示還不能確定最優(yōu)指派方案，須再變換當(dāng)前的系數(shù)矩陣，以找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第4步。分配問題與匈牙利法4) 變換矩陣(bij)以增加0元素在沒有被直線通過的所有元素中找出最小值，沒有被直線通過的所有元素減去這個(gè)最小元素；直線交點(diǎn)處的元素加上這個(gè)最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第2步。分配問題與匈牙利法例4.6 有一份中文說明書，需譯成英、日、德、俄四

55、種文字，分別記作A、B、C、D。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語(yǔ)種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？ 任務(wù)人員ABCD甲67112乙4598丙31104丁5982分配問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素。52）試指派（找獨(dú)立0元素） 找到 3 個(gè)獨(dú)立零元素 但 m = 3 n = 4分配問題與匈牙利法3）作最少的直線覆蓋所有0元素 獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)l，即lm=3n=4；4）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩陣，將沒有被直線通過的所有元素減去這個(gè)最小元素；直線交點(diǎn)處的元素加上這個(gè)最小值。得到新的矩陣，重復(fù)2）步進(jìn)

56、行試指派分配問題與匈牙利法000 0 00試指派得到4個(gè)獨(dú)立零元素， 所以最優(yōu)解矩陣為： 即完成4個(gè)任務(wù)的總時(shí)間最少為：241+8=15分配問題與匈牙利法例4.7 已知四人分別完成四項(xiàng)工作所需時(shí)間如下表，求最優(yōu)分配方案。 任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119分配問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素。2）試指派（找獨(dú)立0元素） 獨(dú)立0元素的個(gè)數(shù)為4 , 指派問題的最優(yōu)指派方案即為甲負(fù)責(zé)D工作，乙負(fù)責(zé)B工作，丙負(fù)責(zé)A工作，丁負(fù)責(zé)C工作。這樣安排能使總的工作時(shí)間最少，為4491128。分配問題與匈牙利法例4.8 已知五人分別完成五項(xiàng)工作耗費(fèi)如下表，求最

57、優(yōu)分配方案。 任務(wù)人員ABCDE甲759811乙9127119丙85468丁73696戊467511分配問題與匈牙利法-1-2解：1）變換系數(shù)矩陣，增加0元素。分配問題與匈牙利法2）試指派（找獨(dú)立0元素） 獨(dú)立0元素的個(gè)數(shù)l45，故畫直線調(diào)整矩陣。分配問題與匈牙利法選擇直線外的最小元素為1；直線外元素減1，直線交點(diǎn)元素加1，其他保持不變。分配問題與匈牙利法l =m=4 0, d-=0; 當(dāng)實(shí)際值未達(dá)到目標(biāo)值時(shí)： d+=0, d-0; 當(dāng)實(shí)際值同目標(biāo)值恰好一致時(shí)： d+=0, d-=0;故恒有d+d-=0目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型2. 統(tǒng)一處理目標(biāo)和約束。 對(duì)有嚴(yán)格限制的資源使用建立系統(tǒng)約束，數(shù)學(xué)

58、形式同線性規(guī)劃中的約束條件。如C和D設(shè)備的使用限制。 對(duì)不嚴(yán)格限制的約束，連同原線性規(guī)劃建模時(shí)的目標(biāo)，均通過目標(biāo)約束來表達(dá)。1）例如要求甲、乙兩種產(chǎn)品保持1:1的比例，系統(tǒng)約束表達(dá)為：x1=x2。由于這個(gè)比例允許有偏差，當(dāng)x1x2時(shí)，出現(xiàn)正偏差d+，即： x1-d+ =x2或x1x2-d+ =0目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型正負(fù)偏差不可能同時(shí)出現(xiàn)，故總有：x1x2+d-d+ =0 若希望甲的產(chǎn)量不低于乙的產(chǎn)量，即不希望d-0,用目標(biāo)約束可表為: 若希望甲的產(chǎn)量低于乙的產(chǎn)量，即不希望d0,用目標(biāo)約束可表為: 若希望甲的產(chǎn)量恰好等于乙的產(chǎn)量，即不希望d0,也不希望d-0用目標(biāo)約束可表為:目標(biāo)規(guī)劃問題及其

59、數(shù)學(xué)模型3）設(shè)備B必要時(shí)可加班及加班時(shí)間要控制，目標(biāo)約束表示為：2）力求使利潤(rùn)指標(biāo)不低于12元，目標(biāo)約束表示為：4）設(shè)備A既要求充分利用，又盡可能不加班，目標(biāo)約束表示為：目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型3. 目標(biāo)的優(yōu)先級(jí)與權(quán)系數(shù)在一個(gè)目標(biāo)規(guī)劃的模型中，為達(dá)到某一目標(biāo)可犧牲其他一些目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級(jí)。優(yōu)先級(jí)層次的高低可分別通過優(yōu)先因子P1,P2,表示。對(duì)于同一層次優(yōu)先級(jí)的不同目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)。權(quán)系數(shù)是一個(gè)個(gè)具體數(shù)字，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要。現(xiàn)假定： 第1優(yōu)先級(jí)P1企業(yè)利潤(rùn)； 第2優(yōu)先級(jí)P2甲乙產(chǎn)品的產(chǎn)量保持1:1的比例 第3優(yōu)先級(jí)P3設(shè)備A,B盡量

60、不超負(fù)荷工作。其中設(shè)備A的重要性比設(shè)備B大三倍。目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型上述目標(biāo)規(guī)劃模型可以表示為：目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式達(dá)成函數(shù)目標(biāo)約束其中：gk為第k個(gè)目標(biāo)約束的預(yù)期目標(biāo)值， 和 為pl 優(yōu)先因子對(duì)應(yīng)各目標(biāo)的權(quán)系數(shù)。目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型用目標(biāo)規(guī)劃求解問題的過程：明確問題，列出目標(biāo)的優(yōu)先級(jí)和權(quán)系數(shù)構(gòu)造目標(biāo)規(guī)劃模型求出滿意解滿意否？分析各項(xiàng)目標(biāo)完成情況據(jù)此制定出決策方案NY目標(biāo)規(guī)劃的圖解分析法目標(biāo)規(guī)劃的圖解法：適用兩個(gè)變量的目標(biāo)規(guī)劃問題，但其操作簡(jiǎn)單，原理一目了然。同時(shí)，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。圖解法解題步驟：1. 將所有約束條件（包括目標(biāo)約束