運(yùn)籌學(xué)課件(全)全書教學(xué)教程完整版電子教案最全幻燈片

1、運(yùn)籌學(xué)Operational Research目 錄緒 論第一章 線性規(guī)劃第二章 對偶理論與靈敏度分析第三章 運(yùn)輸問題第四章 整數(shù)規(guī)劃第五章 動態(tài)規(guī)劃第六章 圖與網(wǎng)路分析第七章 隨機(jī)服務(wù)理論概述第八章 生滅服務(wù)系統(tǒng)第九章 存儲理論第十章 網(wǎng)絡(luò)計(jì)劃方法緒 論一、運(yùn)籌學(xué)的起源與發(fā)展二、運(yùn)籌學(xué)的定義和主要研究分支三、運(yùn)籌學(xué)的特點(diǎn)及研究對象四、運(yùn)籌學(xué)解決問題的方法步驟五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系一、運(yùn)籌學(xué)的起源與發(fā)展起源于二次大戰(zhàn)的一門新興交叉學(xué)科與作戰(zhàn)問題相關(guān)如雷達(dá)的設(shè)置、運(yùn)輸船隊(duì)的護(hù)航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲等英國稱為 Operational Research美國稱為

2、 Operations Research戰(zhàn)后在經(jīng)濟(jì)、管理和機(jī)關(guān)學(xué)校及科研單位繼續(xù)研究1952年，Morse 和 Kimball出版運(yùn)籌學(xué)方法1948年英國首先成立運(yùn)籌學(xué)會1952年美國成立運(yùn)籌學(xué)會1959年成立國際運(yùn)籌學(xué)聯(lián)合會(IFORS)我國于1982年加入IFORS，并于1999年8月組織了第15屆大會一、運(yùn)籌學(xué)的起源與發(fā)展1、中國運(yùn)籌學(xué)會簡介50年代中期，我國著名科學(xué)家錢學(xué)森、許國志等教授將運(yùn)籌學(xué)從西方引入國內(nèi)。1980年4月，中國數(shù)學(xué)會運(yùn)籌學(xué)分會成立。1991年，中國運(yùn)籌學(xué)會成立。歷屆學(xué)會理事長有，華羅庚、越民義，徐光輝，章祥蓀，袁亞湘，胡旭東，戴彧虹（現(xiàn)任）2、中國系統(tǒng)工程學(xué)會簡介

3、1、1979年由錢學(xué)森、宋健、關(guān)肇直、許國志等21名專家、學(xué)者共同倡議并籌備。1980年11月18日在北京正式成立。 第一屆理事會理事長關(guān)肇直，第二、三屆理事長許國志。第四、五屆理事長顧基發(fā)、第六、七屆理事長陳光亞，第八、九屆理事長汪壽陽，第十屆楊曉光（現(xiàn)任）。3、運(yùn)籌學(xué)、系 統(tǒng)工程 主要研究人員構(gòu)成1）數(shù)學(xué)：如華羅庚、越民義，徐光輝，章祥蓀，袁亞湘，許國志，顧基發(fā)，胡旭東，戴彧虹等；2）控制論：張仲俊，劉豹，陳珽，鄭維敏，吳滄浦，趙純均，陳劍等3）管理等專業(yè)相關(guān)教學(xué)、科研技術(shù)人員一、運(yùn)籌學(xué)的起源與發(fā)展4、相關(guān)研究機(jī)構(gòu)和高校1）中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院系統(tǒng)科學(xué)研究所2）中國科學(xué)院數(shù)學(xué)與系

4、統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所3）哈工大：胡運(yùn)權(quán)，黃梯云，錢國明等4）天津大學(xué)：劉豹，顧培亮，張維，杜 綱等5）西安交大：汪應(yīng)洛，席酉民等6）上海交大：張仲俊，王浣塵等7）清華大學(xué)：鄭維敏，趙純均，陳劍等；8）大連理工：王眾托，胡祥培等9）北航：顧昌耀，黃海軍等10）北理工 ：吳滄浦，吳祈宗，張強(qiáng)等7二、運(yùn)籌學(xué)的定義和主要研究分支運(yùn)籌學(xué)的定義為決策機(jī)構(gòu)對所控制的業(yè)務(wù)活動作決策時，提供以數(shù)量為基礎(chǔ)的科學(xué)方法Morse 和 Kimball運(yùn)籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個科學(xué)的系統(tǒng)模式，并運(yùn)用這種模式預(yù)測，比較各種決策及其產(chǎn)生的后果，以幫助

5、主管人員科學(xué)地決定工作方針和政策英國運(yùn)籌學(xué)會運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法對經(jīng)濟(jì)管理系統(tǒng)中人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理中國百科全書現(xiàn)代運(yùn)籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問題，稱為 Management Science8二、運(yùn)籌學(xué)的定義和主要研究分支運(yùn)籌學(xué)的分支數(shù)學(xué)規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、目標(biāo)規(guī)劃等圖論與網(wǎng)路理論隨機(jī)服務(wù)理論：排隊(duì)論存儲理論網(wǎng)絡(luò)計(jì)劃方法決策理論對策論系統(tǒng)仿真：隨機(jī)模擬技術(shù)、系統(tǒng)動力學(xué)可靠性理論金融工程9三、運(yùn)籌學(xué)的特點(diǎn)及研究對象運(yùn)籌學(xué)的特點(diǎn)：1)優(yōu)化以整體最優(yōu)為目標(biāo)，從系統(tǒng)的觀點(diǎn)出發(fā)，力圖以整個系統(tǒng)

6、最佳的方式來協(xié)調(diào)各部門之間的利害沖突，從而求出問題的最優(yōu)解。所以運(yùn)籌學(xué)可看成是一門優(yōu)化技術(shù)，為解決各類問題提供優(yōu)化方法2定量為所研究的問題提供定量的解決方案。如采用運(yùn)籌學(xué)研究資源分配問題時，其求解結(jié)果是一個定量的最優(yōu)資源分配方案。運(yùn)籌學(xué)的研究對象：來自生產(chǎn)管理過程中的具體問題，如資源分配、物資調(diào)度，生產(chǎn)計(jì)劃與控制等。10四、運(yùn)籌學(xué)解決問題的方法步驟1、理清問題、明確目標(biāo)2、建立模型討論：什么叫模型 3、求解模型。建立模型之后，需要設(shè)計(jì)相應(yīng)算法進(jìn)行求解，實(shí)際問題運(yùn)算量一般都很大，通常需要用計(jì)算機(jī)求解。 4、結(jié)果分析討論：模型計(jì)算結(jié)果與已有的經(jīng)驗(yàn)或知識進(jìn)行比較 1）模型計(jì)算結(jié)果和已有的經(jīng)驗(yàn)或知識比

7、較一致 2）模型計(jì)算結(jié)果和已有的經(jīng)驗(yàn)或知識差異較大 你喜歡那一種情況？11五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系 運(yùn)籌學(xué)目標(biāo)分析、建模、求解和結(jié)果分析需要用到很多相關(guān)學(xué)科的知識，它與如下學(xué)科的知識關(guān)系比較密切。1、數(shù)學(xué)：學(xué)習(xí)、應(yīng)用運(yùn)籌學(xué)應(yīng)該具備較廣的數(shù)學(xué)知識，許多運(yùn)籌學(xué)者來自數(shù)學(xué)專業(yè)就是這個原因，有人甚至認(rèn)為運(yùn)籌學(xué)是一門應(yīng)用數(shù)學(xué)；2、管理學(xué)：運(yùn)籌學(xué)研究對象是生產(chǎn)管理過程的具體問題，在利用運(yùn)籌學(xué)理論和方法解決具體問題時，需要的涉及管理科學(xué)的有關(guān)理論；3、計(jì)算機(jī)：運(yùn)籌學(xué)所研究的實(shí)際問題通常都是比較復(fù)雜，而且規(guī)模比較大，在求解這些問題時，必須借助計(jì)算機(jī)來完成。12第一章 線性規(guī)劃1.1 線性規(guī)劃模型1.1.1問

8、題的提出一、例1、多產(chǎn)品生產(chǎn)問題（Max, ）甲電纜乙電纜資源量銅（噸）2110鉛（噸）118價格（萬元）64需求無限制7另 問該工廠應(yīng)如何安排生產(chǎn)才能使工廠的總收入最大？一、例1、多產(chǎn)品生產(chǎn)問題（Max, ）設(shè)x1, x2 分別代表甲、乙兩種電纜的生產(chǎn)量，f(x)為工廠的總收入，則上述問題可用如下數(shù)學(xué)模型來表示其中，OBJ（Objective）表示目標(biāo)，S.t.（Subject to）表示滿足于。表示在滿足銅、鉛資源和需求等約束條件下，使工廠的總收入這一目標(biāo)達(dá)到最大。最優(yōu)解為二、例2、配料問題（min, )某混合飼料加工廠計(jì)劃從市場上購買甲、乙兩種原料生產(chǎn)一種混合飼料?；旌巷暳蠈A、VB1

9、、VB2和VD的最低含量有一定的要求。已知單位甲、乙兩種原料VA、VB1、VB2和VD的含量，單位混合飼料對VA、VB1、VB2和VD的最低含量以及甲、乙兩種原料的單位價格如下表所示。問該該加工廠應(yīng)如何搭配使用甲乙兩種原料，才能使混合飼料在滿足VA、VB1、VB2和VD的最低含量要求條件下，總成本最?。慷?、例2、配料問題（MIN, )設(shè) x1, x2分別代表混合單位飼料對甲、乙兩種原料的用量，f(x)表示單位混合飼料所需要的成本，則上述問題的線性規(guī)劃數(shù)學(xué)模型如下：該數(shù)學(xué)模型的最優(yōu)解為該問題的最優(yōu)解為x1=3.69，x2=0.77，minf(x)=1.49三、線性規(guī)劃數(shù)學(xué)模型的特征和定義1、線性

10、規(guī)劃數(shù)學(xué)模型的特征：1）有一組決策變量（x1，x2，xn）表示某一方案。這一組決策變量的具體值就代表一個具體方案；2）有一個目標(biāo)函數(shù)，該目標(biāo)函數(shù)根據(jù)其的具體性質(zhì)取最大值或最小值。當(dāng)目標(biāo)為成本型時取最小，而當(dāng)目標(biāo)為效益型時取最大。3）有一組約束方程，包括決策變量的非負(fù)約束；4）目標(biāo)函數(shù)和約束方程都是線性的。2、線性規(guī)劃數(shù)學(xué)模型的定義定義1.1 有一個目標(biāo)函數(shù)和一組約束方程，且目標(biāo)函數(shù)和約束方程都是線性的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。四、線性規(guī)劃數(shù)學(xué)模型的背景模型和思考1、線性規(guī)劃數(shù)學(xué)模型的背景模型：例1.1的多產(chǎn)品生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的背景模型。把該背景模型的條件一般化后可敘述如下

11、：用有限量的幾種資源生產(chǎn)若干種產(chǎn)品，如何安排生產(chǎn)，才能使工廠的總收入或利潤達(dá)到最大。2、背景模型的思考1）討論：什么叫背景模型能夠幫助我們理解和記住一些相對抽象和復(fù)雜問題的簡單問題模型。2）背景模型的思考利用一些相對比較簡單的問題來闡述一些相對復(fù)雜和抽象的運(yùn)籌學(xué)中的一些基礎(chǔ)概念和原理是本課程力求在教學(xué)中體現(xiàn)的第一個特點(diǎn)，希望大家用心體會。 1.1.2 線性規(guī)劃數(shù)學(xué)模型的一般表示方式19 1、和式20 2、向量式21 3、矩陣式22 1.1.3 線性規(guī)劃的圖解法f(x)=36線性規(guī)劃問題的幾個特點(diǎn)：1、線性規(guī)劃的可行域?yàn)橥辜?；討論：什么叫凸集？集合中任意兩點(diǎn)連線上的一切點(diǎn)仍然在該集合中，在平面上

12、為凸多邊形，在空間上為凸幾何體；討論：最優(yōu)解在那里取得？2、線性規(guī)劃的最優(yōu)解一定可在其凸集的某一頂點(diǎn)上達(dá)到；討論：什么情況有最優(yōu)解？最優(yōu)解的存在性條件？3、線性規(guī)劃若有可行域且其可行域有界，則一定有最優(yōu)解。上述3個結(jié)論是線性規(guī)劃的3個基礎(chǔ)定理，可以用嚴(yán)格的數(shù)學(xué)方法進(jìn)行證明。我們以簡單、直觀的圖解法方式給出，相信大家是可以接受的。1.3 線性規(guī)劃求解的基礎(chǔ)原理和單純形法1.3.1 線性規(guī)劃問題的標(biāo)準(zhǔn)形一、線性規(guī)劃模型一般形式二、求解思路1、規(guī)定一標(biāo)準(zhǔn)型線性的規(guī)劃問題數(shù)學(xué)模型；2、如何把非標(biāo)準(zhǔn)形的線性規(guī)劃問題數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形線性規(guī)劃問題數(shù)學(xué)模型？3、如何求解標(biāo)準(zhǔn)形線性規(guī)劃問題數(shù)學(xué)模型。三、線性

13、規(guī)劃問題的標(biāo)準(zhǔn)形在上述線性規(guī)劃標(biāo)準(zhǔn)形中，決策變量的個數(shù)取n+m個是習(xí)慣表示法。我們知道，對于線性規(guī)劃背景模型，有m個約束方程，且每個約束方程的不等式均為“”號。如果我們在每個約束方程的左邊加上一個大于等于0的變量，則可將各個約束方程的“”號轉(zhuǎn)變?yōu)椤?”。此時，決策變量就有n+m個。26 四、變換的方法1、目標(biāo)函數(shù)為min型，價值系數(shù)一律反號。令 g(x) = -f(x) = -CX, 有 min f(x) = - max - f(x) = - max g(x)2、第i 個約束的bi 為負(fù)值，則該行左右兩端系數(shù)同時反號，同時不等號也要反向3、第i 個約束為 型，在不等式左邊增加一個非負(fù)的變量xn

14、+i ，稱為松弛變量；同時令 cn+i = 04、第i 個約束為 型，在不等式左邊減去一個非負(fù)的變量xn+i ，稱為剩余變量；同時令 cn+i = 05、若xj 0，令 xj= -xj ，代入非標(biāo)準(zhǔn)型，則有xj 06、若xj 不限，令 xj= xj - xj， xj 0，xj 0，代入非標(biāo)準(zhǔn)型27 五、 變換舉例：1.3.2 線性規(guī)劃問題的解和基礎(chǔ)定理本章開始到現(xiàn)在已討論的內(nèi)容，相信大部分讀者都會感到比較容易理解和掌握。這一節(jié)我們將要討論關(guān)于線性規(guī)劃問題解的一些基礎(chǔ)概念和定理，與前面討論的內(nèi)容相比，線性規(guī)劃問題解的一些基礎(chǔ)概念略顯難一些，其中比較難的概念有線性規(guī)劃問題的基和基礎(chǔ)解等相關(guān)概念。為

15、了幫助大家比較容易理解這些概念，我們先從大家熟悉的兩個變量兩個線性方程組這一簡單問題入手，然后逐步過渡到我們所要討論的線性規(guī)劃問題的基和基礎(chǔ)解等相關(guān)概念。著名數(shù)學(xué)家笛卡爾曾說過，他最擅長做的兩件事是：1)第一做簡單事；2)第二是將復(fù)雜事變?yōu)楹唵问隆１菊n程將從大家熟悉的一些簡單問題入手，然后逐步過渡到運(yùn)籌學(xué)一些相對比較抽象和難的概念和原理。這是本課程教學(xué)力求的另一特點(diǎn)。一、線性方程組的解考慮如下線性方程組的解：再考慮如下線性方程組的解：一、線性方程組的解類似地，如果將方程組（3）中的變量x2或x1當(dāng)成常數(shù)，分別移到其方程的右邊后采用消元法進(jìn)行求解，則也可得到如下兩組通解及其特解：一、線性方程組的

16、解仔細(xì)觀察和思考方程組（3）的三組通解（4）、（6）和（8）或三組特解（5）、（7）和（9）是如何得到的，以及能夠得到這些通解或特解的條件是什么？根據(jù)求解線性方程組克萊姆條件可知，能夠得到方程組（3）的通解（4）或特解（5）的條件是方程組（3）中的變量x1和x2的系數(shù)矩陣行列式不等于0，即或變量x1和x2的系數(shù)矩陣B1是非奇異矩陣或變量x1和x2的系數(shù)列向量是線性無關(guān)。顯然，這三個條件是等價的。一、線性方程組的解同樣，由于方程組組（3）中的變量x1和x3的系數(shù)矩陣行列式|B2|不等于0與變量x2和x3的系數(shù)矩陣行列式|B3|不等于0，即才能得到方程組（3）的通解或特解（6）或（7）與通解或特解

17、（8）或（9）。將上面討論的方程組（3）加上一目標(biāo)函數(shù)和變量非負(fù)約束條件后就變成一標(biāo)準(zhǔn)型線性規(guī)劃。如：一、線性方程組的解對于上述標(biāo)準(zhǔn)型線性規(guī)劃（10）,稱 B1 、B2和B3為線性規(guī)劃（10）的基。因利用其中任何一個基B1 或B2或B3，都能得到線性規(guī)劃（10）的一組通解和特解（見式（4）-（9）。變量x1和x2為基變量，變量x3為非基變量，令x3=0，得解（5）為線性規(guī)劃（10）的基礎(chǔ)解，但因該基礎(chǔ)解中x1= -10，不滿足線性規(guī)劃（10）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（5）是線性規(guī)劃（10）的基礎(chǔ)非可行解。變量x1和x3為基變量，變量x2為非基變量，令x2=0，得解（7）為線性規(guī)劃（1

18、0）的基礎(chǔ)解。該基礎(chǔ)解中x1和x3均大于0，滿足線性規(guī)劃（10）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（7）是線性規(guī)劃（10）的基礎(chǔ)可行解。變量x2和x3為基變量，變量x1為非基變量，令x1=0，得解（9）為線性規(guī)劃（10）的基礎(chǔ)解.該基礎(chǔ)解中x2和x3均大于0，滿足線性規(guī)劃（10）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（9）是線性規(guī)劃（10）的基礎(chǔ)可行解。二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念標(biāo)準(zhǔn)型有 n+m 個變量， m 個約束行“基”的概念在標(biāo)準(zhǔn)型中，技術(shù)系數(shù)矩陣有 n+m 列，即 A = ( P1, P2 , , Pn+m )A中線性獨(dú)立的 m 列，構(gòu)成該標(biāo)準(zhǔn)型的一個基，即 B = ( P1 ,

19、P2 , , Pm )， | B | 0 P1 , P2 , , Pm 稱為基向量與基向量對應(yīng)的變量稱為基變量，記為 XB = ( x1 , x2 , , xm )T，其余的變量稱為非基變量，記為 XN = ( xm+1 , xm+2 , , xm+n ) T ， 故有 X = （XB ， XN ) 最多有 個基二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念可行解與非可行解滿足約束條件和非負(fù)條件的解 X 稱為可行解，不滿足約束條件或非負(fù)條件的解 X 稱為非可行解基礎(chǔ)解對應(yīng)某一基B且令其非基變量 XN = 0，求得基變量 XB的值。稱X = (XB , XN)T為基礎(chǔ)解。 其中，XB = B1 b， XN

20、= 0XB 是基礎(chǔ)解必須滿足如下條件： 1）非0分量的個數(shù) m； 2、m個基變量所對應(yīng)的系數(shù)矩陣為非奇異的； 3、滿足m個約束條件。二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念 基礎(chǔ)可行解與基礎(chǔ)非可行解基礎(chǔ)解 XB 的非零分量都 0 時，稱為基礎(chǔ)可行解，否則為基礎(chǔ)非可行解。退化解 基礎(chǔ)可行解的非零分量個數(shù) f (X(0) )=0（五）最優(yōu)檢驗(yàn)將（5）式代入(1)的目標(biāo)函數(shù)后可得 f (X)=30+x2-3x3 （6）從目標(biāo)函數(shù)（6）可知，非基變量x2的系數(shù)是正數(shù)，所以X(1)不是最優(yōu)解。（六）求另一個更好的基礎(chǔ)可行解481、確定換入變量及其值從從目標(biāo)函數(shù)（6）可知，只有非基變量x2的系數(shù)為正，所以，可確

21、定x2為換入變量。由于所以，當(dāng)另一個非基變量x3仍然為0時，由（7）式可得到換入變量x1的值為 x2=Min5/0.5，3/0.5，7/1=62、確定換出變量從（7）式可知，當(dāng)x2=6時，x4=0，所以x4為換出變量。由此得到線性規(guī)劃（1）的一個新的基B2和一組新的基變量與非基變量。B2=(P1 ,P2 ,P5 ), XB2=（x1，x2，x5)T，XN2=（x3，x4)T493、求另一個更好的基礎(chǔ)可行解將（1)約束方程中對應(yīng)于基B2的非基變量x3和x4移到方程的右邊后可得令非基變量x3=x4=0，可得另一基礎(chǔ)可行解 X(2) = (2，6，0，0，1)T此時，對應(yīng)于X(2)的目標(biāo)函數(shù)f (X

22、(2) )=6x1+4x2=36 f (X(1) )=30（七）最優(yōu)檢驗(yàn)將（8）式代入(1)的目標(biāo)函數(shù)后可得 f (X)=36-2x3-2x4 （9）從目標(biāo)函數(shù)（9）可知，非基變量x3和x4的系數(shù)都是負(fù)數(shù)，所以X(2)是最優(yōu)解。即X*= X(2) = (2，6，0，0，1)T ,f (X*)=36三、求初始基礎(chǔ)可行解（背景模型，MAX, )50設(shè)線性規(guī)劃問題為另設(shè)bi0 (i=1,2,m)。標(biāo)準(zhǔn)化后，若對xj和aij重新編號，則約束方程可化為變量x1，x2，xm作為初始基變量，其余變量作為初始非基變量，并令xm+1=xm+1=xn+m=0，則得初始本可行解四、最優(yōu)檢驗(yàn)51對于標(biāo)準(zhǔn)化線性規(guī)劃問題

23、(2)，經(jīng)過若干次迭代后，如果對xj及aij重新編號，則約束方程可化為其中，bi和aij表示經(jīng)過若干次迭代后，當(dāng)前的右端系數(shù)和技術(shù)系數(shù)，以便區(qū)別于原始的右端系數(shù)bi和技術(shù)系數(shù)aij。將上式代入（2）的目標(biāo)函數(shù)后可得機(jī)會成本52在一般情況下，目標(biāo)函數(shù)值OBJ計(jì)算公式和機(jī)會成本計(jì)算公式可寫成四、最優(yōu)檢驗(yàn)其中，I為基變量的下標(biāo)集。最優(yōu)檢驗(yàn)條件為其中，J表示非基變量的下標(biāo)集。對于基變量的檢驗(yàn)數(shù)為因?yàn)榛兞康募夹g(shù)系數(shù)滿足： aij=1, 當(dāng)i=j aij=0, 當(dāng)ij五、 求另一個更好的基礎(chǔ)可行解53若某一基礎(chǔ)可行解經(jīng)過最優(yōu)檢驗(yàn)表明不是最優(yōu)解，則需要設(shè)法求得另一個更好的基礎(chǔ)可行解。求另一個更好的基礎(chǔ)可行

24、解的主要步驟如下：1、確定換入變量；2、確定換出變量；3、通過基變換或初等變換求得另一個更好的基礎(chǔ)可行解。我們已在前面例子中說明了這種初等變換方法的基礎(chǔ)思路。下一小節(jié)我們將用單純形表進(jìn)一步說明這種初等變換方法。54 1.3.4 單純形法表及單純形法55 例 試列出下面線性規(guī)劃問題的初始單純型表單純形法步驟561、求初始基礎(chǔ)可行解 將線性規(guī)劃模型標(biāo)準(zhǔn)化，建立初始單純形表，求初始基礎(chǔ)可行解。2、最優(yōu)檢驗(yàn)：對任一基礎(chǔ)可行解X，若其所有檢驗(yàn)數(shù) j =cj zj0，jJ 則X為最優(yōu)解，即X*=X，計(jì)算最優(yōu)解所對應(yīng)的最優(yōu)目標(biāo)函數(shù)值f(X*)，算法停止。否則轉(zhuǎn)3。3、求另一個更好的基礎(chǔ)可行解1）確定入變量x

25、k 若則xk為換入變量；2）確定換出變量xl* 計(jì)算若l為空集，則為無界解，算法停止。否則與右端系數(shù)bl 同一行的基變量xl*為換出變量。轉(zhuǎn)3）3）初等變換，得到另一個更好的基礎(chǔ)可行解將入變量xk所在列k，出變量xl*所在行l(wèi)的主元技術(shù)系數(shù)al k變換為1，主元al k 所在列的其余元變換為0。更換基變量（用入變量xk替換出變量xl*）及其價值系數(shù)，得到另一個更好的基礎(chǔ)可行解。轉(zhuǎn)2。57 表1.2.4 例1.2.2 單純型表的迭代過程答：最優(yōu)解為 x1=20, x2=20, x3=0, OBJ=170058 單純型表中元素的幾點(diǎn)說明任何時候，各基變量對應(yīng)的列都構(gòu)成一個單位矩陣當(dāng)前表中的 b 列

26、表示當(dāng)前基變量的解值，通過變換 B 1 b 得到 (資源已變成產(chǎn)品)當(dāng)前非基變量對應(yīng)的向量可通過變換 B 1 AN 得到， 表示第 j 個變量對第 i 行對應(yīng)的基變量的消耗率非基變量的機(jī)會成本為591.4 單純形法的進(jìn)一步討論1.4.1 人工變量法 上一節(jié)我們涉及的線性規(guī)劃模型都是線性規(guī)劃的背景模型，即目標(biāo)函數(shù)為最大，每個約束方程都是“”型，右端系數(shù)都是大于等于0。對于這樣一類的線性規(guī)劃，每個約束方程引入一個松弛變量將其標(biāo)準(zhǔn)化后，約束方程的系數(shù)矩陣含有單位矩陣，以此單位矩陣作為初始可行基，很容易得到一個初試基礎(chǔ)可行解。但是，對于下面的線性規(guī)劃，將其標(biāo)準(zhǔn)化后，其約束方程的系數(shù)矩陣不存在單位矩陣。

27、因此無法直觀和方便地得到一個初始基礎(chǔ)可行解 例1.4.1解 令g(x)= -f(x)，第1和2個約束方程分別減去一個剩余變量x4和x5，則可將上述線性規(guī)劃轉(zhuǎn)化為如下標(biāo)準(zhǔn)形線性規(guī)劃。1.4.1 人工變量法60變量x6稱為人工變量。這樣，變量x3和x6系數(shù)矩陣可構(gòu)成一個單位矩陣，即可構(gòu)成一個初始可行基，以變量x3和x6為初始基變量，其它變量為非基變量0，則可得一初始基礎(chǔ)可行解X(0) = (0，0，4，0，0，6)T這種在約束方程中加人工變量來得到初始基礎(chǔ)可行解的方法稱為人工變量法。61我們知道，對于任何一個基礎(chǔ)可行解，非基變量都是等于0，所以，人工變量在初始基礎(chǔ)可行解中雖然不等于0，但如果在后面

28、迭代過程中，能把所有人工變量轉(zhuǎn)變?yōu)榉腔兞?，則所有人工變量都將等于0，這樣，原有的約束方程就不會被破壞。但如果在迭代過程中，已得到最優(yōu)解（即滿足最優(yōu)解檢驗(yàn)條件），而基變量中還有人工變量，或最優(yōu)解時所有人工變量不全部等于0，則原線性規(guī)劃無解，即不存在滿足所有約束方程的可行解。將人工變量從初始基礎(chǔ)可行解中轉(zhuǎn)變?yōu)榉腔兞康姆椒ㄖ饕校海?）大M法；（2）兩階段法。下面我們分別討論。1.4.1 人工變量法621.4.2 大M法 例1.4.163 表1.4.1 例1.4.1的單純型表迭代過程答：最優(yōu)解為 x1=2, x2=2, x3=0, OBJ=3664 大M法的一些說明大M法實(shí)質(zhì)上與原單純型法一樣，

29、M 可看成一個很大的常數(shù)人工變量被迭代出去后一般就不會再成為基變量當(dāng)檢驗(yàn)數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變量，說明原線性規(guī)劃問題無可行解大M法手算很不方便因此提出了二階段法計(jì)算機(jī)中常用大M法二階段法手算可能容易651.4.3 兩階段法第一階段的任務(wù)是將人工變量盡快迭代出去，從而找到一個沒有人工變量的基礎(chǔ)可行解第二階段以第一階段得到的基礎(chǔ)可行解為初始解，采用原單純型法求解若第一階段結(jié)束時，人工變量仍在基變量中，則原問題無解為了簡化計(jì)算，在第一階段重新定義價值系數(shù)如下：66 用二階段法求解例1.4.1的第一階段67 用二階段法求解例1.4.1的第二階段最優(yōu)解對應(yīng)的B1在哪？681.4.4 單純

30、型法的一些具體問題一、無界解可行區(qū)域不閉合(約束條件有問題)單純型表中入變量 xj* 對應(yīng)的列中所有69 例1.4.2 的單純型表及其迭代過程70 二、退化解退化問題的原因很復(fù)雜，當(dāng)原問題存在平衡約束時當(dāng)單純型表中同時有多個基變量可選作出變量時退化的嚴(yán)重性在于可能導(dǎo)致死循環(huán)，克服死循環(huán)的方法有“字典序”法71 三、多重解多個基礎(chǔ)可行解都是最優(yōu)解，這些解在同一個超平面上，且該平面與目標(biāo)函數(shù)等值面平行最優(yōu)單純型表中有非基變量的檢驗(yàn)數(shù)為0最優(yōu)解的線性組合仍是最優(yōu)解，即 X=aX1+bX2，a+b=172 例1.4.4 的單純型表及其迭代過程73 四、無可行解約束條件互相矛盾，無可行域單純型表達(dá)到最優(yōu)

31、解檢驗(yàn)條件時，人工變量仍在基變量中74 例1.4.5 第一階段的單純型表1.5 修正單純形法1.5.1 單純形法的矩陣描述75其中，XS=(xs 1，xs 2，xs m)為松弛變量，I為mm階單位矩陣。目標(biāo)函數(shù)中松弛變量XS的系數(shù)0是一列0矩陣。以XS對應(yīng)的系數(shù)矩陣單位陣I做為初始可行基B，對應(yīng)的松弛變量XS為初始基變量，記為XB，其余變量為初始非基變量，記為XN。令XN =0，則可得到對應(yīng)于初始可行基B（為單位陣）的初始基礎(chǔ)可行解X = (XB, XN) = (b, 0)，對應(yīng)目標(biāo)函數(shù)值為f(X)= 0。并以該初始基礎(chǔ)可行解X = (XB, XN) = (b, 0)為切入點(diǎn)開始進(jìn)行迭代運(yùn)算。

32、1.5.1 單純形法的矩陣描述76一般地，對于任一標(biāo)準(zhǔn)型線性規(guī)劃，在某一步迭代運(yùn)算中，設(shè)B是其可行基，則該標(biāo)準(zhǔn)型線性規(guī)劃可用矩陣形式表示如下：其中，X = (XB ,XN)T， C=(CB，CN） ，A=(B，AN）。由于B是可行基，B-1存在，所以，上述線性規(guī)劃的約束方程可寫成 XB = B-1(b - ANXN) 將上式XB代入上述線性規(guī)劃的目標(biāo)函數(shù)，并整理后可得， f(X) = CB B-1b+(CN - CBB-1AN)XN 令XN =0，X = (XB, XN) = (B-1b, 0)，f(X)= CBB-1b對應(yīng)某一可行基B的最優(yōu)檢驗(yàn)條件用矩陣形式可表示如下： N = (CN -

33、CBB-1AN) 0 （2）771.5.1 單純形法的矩陣描述若非基變量XN的系數(shù)向量(CN - CBB-1AN)有一些分量大于0，則取其中數(shù)值最大的一個分量k所對應(yīng)的非基變量分量xk做為換入變量分量。對于某一非最優(yōu)可行基B，確定換出變量時，可用如下矩陣形式表示：其中，Pk為標(biāo)準(zhǔn)型線性規(guī)劃（1）技術(shù)系數(shù)矩陣A中換入變量xk的系數(shù)列向量。根據(jù)公式（3）的計(jì)算結(jié)果，基變量向量XB中的第i*分量xl為換出變量。當(dāng)然，如果公式（3）的計(jì)算結(jié)果為空集，則為無界解。確定了換入變量xk和換出變量xl，就可以得到新的可行基和對應(yīng)的基變量和非基變量等，并按公式(2)進(jìn)行最優(yōu)檢驗(yàn)。781.5.2 改進(jìn)單純形法原單

34、純型法迭代所需存儲量大，原單純型法有不必要的計(jì)算量由于改進(jìn)單純形算法通過矩陣運(yùn)算求解線性規(guī)劃，其關(guān)鍵是計(jì)算某一可行基B的逆矩陣B-1。可按如下初等變換進(jìn)行： (B I) (I B-1)例1.5.1 用改進(jìn)單純形算法求解如下線性規(guī)劃79解 （一）列出技術(shù)系數(shù)矩陣A，選擇初始基、初始基變量等 （二）最優(yōu)檢驗(yàn) 由于B0是單位陣，其逆矩陣B0-1也是單位陣。XB0=（x3，x4，x5)T，XN0=（x1，x2)TC B0 =（0，0，0），C N0 =（2，3），AN0=(P1，P2)所以，初始基B0不是最優(yōu)基。由于檢驗(yàn)數(shù)向量第2個分量值最大，所以對應(yīng)初始非基變量 XN0=（x1，x2)T的第2個分量

35、x2為換入變量。即xk = x2。80（三）確定換出變量，得到新的可行基及對應(yīng)的基變量等i*=3，對應(yīng)基變量XB0=（x3，x4，x5)T的第3個分量x5為換出變量，根據(jù)換出變量x5、換入變量x2和初始基B0=( P3，P4，P5)，得到新的可行基及其基變量等B1=( P3，P4，P2)，XB1=（x3，x4，x2)T，C B1=（0，0，3），XN1=（x1，x5)T，C N1=（2，0），AN1=(P1，P5)。（四）最優(yōu)檢驗(yàn) 由于可行基B1的非基變量檢驗(yàn)數(shù)向量所以，可行基B1不是最優(yōu)基。由于檢驗(yàn)數(shù)向量第1個分量值最大，所以對應(yīng)非基變量 XN1=（x1，x5)T的第1個分量x1為換入變量。

36、81（五）確定換出變量，得到新的可行基及對應(yīng)的基變量等i*=1，對應(yīng)基變量XB1=（x3，x4，x2)T的第1個分量x3為換出變量根據(jù)換出變量x3、換入變量x1和可行基B1=( P3，P4，P2)，得到新的可行基及其基變量等B2=( P1，P4，P2)，XB2=（x1，x4，x2)T，C B2=（2，0，3），XN2=（x3，x5)T，C N2=（0，0），AN2=(P3，P5)。（六）最優(yōu)檢驗(yàn) 由于可行基B2的非基變量檢驗(yàn)數(shù)向量所以，可行基B2不是最優(yōu)基。檢驗(yàn)數(shù)向量第2個分量值最大，所以對應(yīng)非基變量 XN2=（x2，x5)T的第2個分量x5為換入變量。82（七）確定換出變量，得到新的可行基及

37、對應(yīng)的基變量等i*=2，對應(yīng)基變量XB2=（x1，x4，x2)T的第2個分量x4為換出變量，根據(jù)換出變量x4、換入變量x5和可行基B2=( P1，P4，P2)，得到新的可行基及其基變量等B3=( P1，P5，P2)，XB3=（x1，x5，x2)T，C B3=（2，0，3），XN3=（x3，x4)T，C N3=（0，0），AN3=(P3，P4)。（八）最優(yōu)檢驗(yàn) 由于可行基B3的非基變量檢驗(yàn)數(shù)向量所以，可行基B3是最優(yōu)基。對應(yīng)的最優(yōu)解為1.6 線性規(guī)劃建模案例分析1.6.1 線性規(guī)劃建?；A(chǔ)步驟83一、建模前需要考慮的問題1）所討論問題的目標(biāo)是否可用一線性函數(shù)來描述；2）所討論問題是否存在多種解決

38、方案及其相關(guān)數(shù)據(jù)；3）所要達(dá)到的目標(biāo)是在一定約束條件下可以實(shí)現(xiàn)，且這些約束條件可以線性方程來表示。二、建立線性規(guī)劃模型的基礎(chǔ)步驟1、確定一目標(biāo)；2、選擇一組決策變量；3、列出目標(biāo)函數(shù)和所有的約束方程。上面三個步驟中，步驟一和步驟二尤其重要。其中步驟一要確定一適當(dāng)?shù)哪繕?biāo)并能夠用恰當(dāng)?shù)姆绞竭M(jìn)行表示，有時直接表示問題的目標(biāo)有困難時，可用等價方式表示；步驟二要求選擇一組合理的決策變量，用這些變量能夠方便地列出步驟三的目標(biāo)函數(shù)和所有約束方程。84案例1某工廠生產(chǎn)用2單位A和1單位B混合而成的成品出售，市場無限制。A和B可在該工廠的3個車間中的任何車間生產(chǎn)，生產(chǎn)每單位的A和B在各車間消耗的工時如下表。試建

39、立使產(chǎn)品數(shù)最大的線性規(guī)劃模型。消耗工時車間1車間2車間3A2115B1215可用工時100120100解：上述問題看似比較簡單，目標(biāo)是使產(chǎn)品數(shù)最大，決策變量分別是車間1、車間2和車間3生產(chǎn)產(chǎn)品零件A和B的數(shù)量。但是，一個產(chǎn)品是由2個A零件和1個B零件組成，所以直接表示產(chǎn)品數(shù)最大有一定困難，為此，我們考慮如下等價表示方式：1）產(chǎn)品數(shù)最大等價于：零件B數(shù)最大，且零件A的總數(shù)滿足是零件B的總數(shù)兩倍；2) 產(chǎn)品數(shù)最大等價于：零件A數(shù)最大，且零件B的總數(shù)滿足是零件A的總數(shù)1/2倍85案例1解：設(shè)車間 1 生產(chǎn)x1A單位A、生產(chǎn)x1B單位B；設(shè)車間 2 生產(chǎn)x2A單位A、生產(chǎn)x2B單位B；設(shè)車間 3 生產(chǎn)

40、x3A單位A、生產(chǎn)x3B單位B；則有生產(chǎn)安排最優(yōu)化的模型如下：討論：第4個約束方程取“”好，還是取“=”好呢？86案例2某飲料工廠按照一定的配方將A、B、C三種原料配成三種飲料出售。配方規(guī)定了這三種飲料中A和C的極限成分，具體見下表，飲料品種規(guī)格每升售價（元）需求量甲（1）A60%, C20%6.801500乙（2）A15%, C60%5.703000丙（3）C50%4.50無限制A、B、C三種原料每月的供應(yīng)量和每升的價格如下表。供應(yīng)量（升/月）價格（元/升）A2000700B2500500C1200400飲料甲、乙和丙分別由不同比例的A、B、C調(diào)兌而成，設(shè)調(diào)兌后不同成分的體積不變，求最大收益

41、的生產(chǎn)方案的線性規(guī)劃模型。87案例2解：問題是要確定原料A，B和C的購買量和飲料甲、乙和丙的生產(chǎn)量，使得在滿足規(guī)定約束條件下，飲料廠的總收益最大。建立該問題的線性規(guī)劃模型的主要問題是如何選擇決策變量，如果直接選擇A，B和C的購買量和飲料甲、乙和丙的生產(chǎn)量六個變量做為決策變量，那將無法表示飲料甲、乙和丙中的A和（或）C的規(guī)格要求。為此，我們設(shè)：x1A 為飲料甲中A的總含量 (升)；x2A 為飲料乙中A的總含量 (升)；x3A 為飲料丙中A的總含量 (升)；x1B 為飲料甲中B的總含量 (升)；x2B 為飲料乙中B的總含量 (升)；x3B 為飲料丙中B的總含量 (升)；x1C 為飲料甲中C的總含量

42、 (升)；x2C 為飲料乙中C的總含量 (升)；x3C 為飲料丙中C的總含量 (升)；f(x)為飲料廠的總利潤，則該問題的線性規(guī)劃模型如下：889192939495第二章對偶理論與靈敏度分析窗含西嶺千秋雪，門泊東吳萬里船對偶是一種普遍現(xiàn)象2.1 線性規(guī)劃問題的對偶問題及其變換2.1.1 線性規(guī)劃對偶問題的提出及其經(jīng)濟(jì)意義任何線性規(guī)劃問題都有其對偶問題對偶問題有其明顯的經(jīng)濟(jì)含義96 假設(shè)有商人要向廠方購買資源A和B，問他們談判原料價格的模型是怎樣的？例 2.1.1 例2.1.1設(shè)A、B資源的出售價格分別為 y1 和 y2顯然商人希望總的收購價越小越好工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少97

43、 2.1.2 原問題與對偶問題的表達(dá)形式98 2.1.2原問題與對偶問題的表達(dá)形式99 一、標(biāo)準(zhǔn)(max,)型的對偶變換目標(biāo)函數(shù)由 max 型變?yōu)?min 型對應(yīng)原問題每個約束行有一個對偶變量 yi，i=1,2,m對偶問題約束為 型，有 n 行原問題的價值系數(shù) C 變換為對偶問題的右端項(xiàng)原問題的右端項(xiàng) b 變換為對偶問題的價值系數(shù)原問題的技術(shù)系數(shù)矩陣 A 轉(zhuǎn)置后成為對偶問題的技術(shù)系數(shù)矩陣原問題與對偶問題互為對偶對偶問題可能比原問題容易求解對偶問題還有很多理論和實(shí)際應(yīng)用的意義100 二、非標(biāo)準(zhǔn)型的對偶變換三、原問題和其線性規(guī)劃對偶問題的相互關(guān)系表約束條件的類型與非負(fù)條件對偶非標(biāo)準(zhǔn)的約束條件類型對

44、應(yīng)非正常的非負(fù)條件對偶變換是一一對應(yīng)的102103在使用上表規(guī)則寫出某一線性規(guī)劃的對偶規(guī)劃時，要注意如下一些問題：1）要看清原問題目標(biāo)函數(shù)是max問題還是min問題。如果原問題目標(biāo)函數(shù)是max，在寫其對偶問題時，應(yīng)該利用上表左側(cè)規(guī)則向右側(cè)規(guī)則變換；而如果原問題目標(biāo)函數(shù)是min，在寫其對偶問題時，則應(yīng)該利用上表右側(cè)規(guī)則向左側(cè)規(guī)則變換；2）如果原問題的約束條件不符合上表的規(guī)范要求，應(yīng)該利用等價變換規(guī)則，將約束條件變換成符合上表的規(guī)范要求。例 2.1.4 寫出如下線性規(guī)劃的對偶規(guī)劃1）第一、二約束方程可用兩個約束方程等價表示；2) 沒有給出x1 變量的約束條件，但根據(jù)第二約束方程可推得，x1 變量的

45、約束條件為x10。因此，上述線性規(guī)劃等價于如下線性規(guī)劃：1042.2 線性規(guī)劃的對偶定理1、弱對偶定理定理1 對偶問題(min)的任何可行解Y0，其目標(biāo)函數(shù)值總是不小于原問題(max)任何可行解X0的目標(biāo)函數(shù)值105 為了便于討論，下面不妨總是假設(shè)將(1)式左乘Y0，將(2)式右乘X0，立刻可得Y0b Y0AX0 CX0，證畢。 弱對偶定理推論max問題的任何可行解目標(biāo)函數(shù)值是其對偶min問題目標(biāo)函數(shù)值的下限； min問題的任何可行解目標(biāo)函數(shù)值是其對偶max問題目標(biāo)函數(shù)值的上限如果原max(min)問題為無界解，則其對偶 min (max)問題無可行解如果原max(min)問題有可行解，其對偶

46、 min (max)問題無可行解，則原問題為無界解注：存在原問題和對偶問題同時無可行解的情況106107例 2.2.1 設(shè)有如下線性規(guī)劃原問題令 X0=(x01，x02，x03，x04)T= (1，1，1，1)T，Y0=（y01，y02，y03）=（1，1，1），則顯然X0和Y0分別為原問題和對偶問題的可行解。它們對應(yīng)的目標(biāo)函數(shù)值分別為f(X0)=C X0=10，即其對偶問題目標(biāo)函數(shù)值的下限不會小于10；g(Y0)= Y0 b=140，即其原問題目標(biāo)函數(shù)值的上限不會大于140；這一結(jié)果驗(yàn)證了弱對偶定理C X0 Y0 b。108例 2.2.2 設(shè)有如下線性規(guī)劃原問題令 X0=(x01，x02)T

47、= (1，1)T，則顯然X0為原問題的可行解，即線性規(guī)劃原問題有可行解；但將對偶問題的兩個約束方程相加后可得 - y1 2，這顯然與非負(fù)約束矛盾，所以對偶問題無可行解。根據(jù)弱對偶定理推論3可以判斷原問題為無界解。事實(shí)上，利用單純形法求解原問題（見第一章例1.10）可得，原問題的確為無界解，根據(jù)弱對偶定理推論2可以判斷對偶問題無可行解2、最優(yōu)解判別定理定理2 若原問題的某個可行解X0的目標(biāo)函數(shù)值與對偶問題某個可行解Y0的目標(biāo)函數(shù)值相等，則X0, Y0分別是相應(yīng)問題的最優(yōu)解證：由弱對偶定理推論1，有 CX0 = Y0b CX, 即X0是原問題的最優(yōu)解；另有Y0b = CX0 Yb，即Y0是對偶問題

48、的最優(yōu)解；證畢。1093、主對偶定理定理3 如果原問題和對偶問題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標(biāo)函數(shù)值相等。證：由弱對偶定理推論1可知，原問題和對偶問題的目標(biāo)函數(shù)有界，故一定存在最優(yōu)解。 現(xiàn)證明定理的后一句話。 主對偶定理的證明 證：現(xiàn)證明定理的后一句話，采用反證法。 設(shè) X0 ， Y0分別為原問題和對偶問題的最優(yōu)解，且 Y0b CX0 根據(jù)最優(yōu)性檢驗(yàn)條件，非基變量的檢驗(yàn)數(shù)滿足CN CBB1N 0，而基變量的檢驗(yàn)數(shù)為0，可寫成CB CBB1B = 0，所以，包括基變量在內(nèi)的所有變量的檢驗(yàn)數(shù)滿足 C CBB1A 0。令 Y= CBB1，則有 Y A C。 另外，對應(yīng)于松馳變量，

49、有 CBB1I 0，即 Y= CBB1 0，故 Y為對偶問題的可行解。對偶問題可行解Y的目標(biāo)函數(shù)值為 g(Y)=Yb = CBB1bY0b 原問題最優(yōu)解X0的目標(biāo)函數(shù)值為 f(X0)=CX0= CBB1b=Yb 所以有CX0Y0b, 與假設(shè)矛盾。故得證，該定理的證明告訴我們一個非常重要的概念：對偶變量的最優(yōu)解等于原問題松弛變量的機(jī)會成本即對偶變量的最優(yōu)解是原問題資源的影子價格1103、互補(bǔ)松弛定理定理4 設(shè)X0, Y0分別是原問題和對偶問題的可行解，U0為原問題的松弛變量的值、V0為對偶問題剩余變量的值。X0, Y0分別是原問題和對偶問題最優(yōu)解的充分必要條件是 Y0 U0 + V0 X0 =

50、0證：由定理所設(shè)，可知有 A X0 + U0 = b X0, U0 0 (1) Y0 A V0 = C Y0, V0 0 (2)分別以Y0左乘(1)式，以X0右乘(2)式后，兩式相減，得 Y0 U0 + V0 X0 = Y0 b C X0若 Y0 U0 + V0 X0 = 0，根據(jù)最優(yōu)解判別定理， X0, Y0分別是原問題和對偶問題最優(yōu)解。反之亦然。 證畢。111112根據(jù)互補(bǔ)松弛定理和決策變量滿足非負(fù)條件可知，在最優(yōu)解時，Y0 U0 和 V0 X0同時等于0，所以有3、互補(bǔ)松弛定理上面公式稱為互補(bǔ)松弛條件。該條件表明，在最解條件下，如果知道v0j與x0j（或u0j與y0j）中的任意一個值為非

51、0時，則可推得另一個必然為0。利用這個條件，有時可大大地簡化計(jì)算過程。例 2.2.4 利用互補(bǔ)松弛定理求解如下線性規(guī)劃問題113其對偶問題引入剩余變量v1，v2，v3和v4后，可得到如下線性規(guī)劃利用圖解法可求得其最優(yōu)解為：y01=1.2，y02=0.2，Min g (Y0)=28。利用得到的對偶規(guī)劃最優(yōu)解和互補(bǔ)松弛定理，可求得原線性規(guī)劃的最優(yōu)解。具體步驟如下：1、因?yàn)閥01=1.20，根據(jù)互補(bǔ)松弛定理可得u01=0；2、因?yàn)閥02=0.20，根據(jù)互補(bǔ)松弛定理可得u02=0；3、因?yàn)閥01+ 2y02=1.61，根據(jù)對偶規(guī)劃(2.13)的第1個約束方程 可得v010，然后根據(jù)互補(bǔ)松弛定理可得x0

52、1=0；4、因?yàn)?y01+ y02=2.62，根據(jù)對偶規(guī)劃(2.13)的第2個約束方程 可得v020，然后根據(jù)互補(bǔ)松弛定理可得x02=0；5、根據(jù)上述4個步驟的結(jié)論及原線性規(guī)劃的約束方程可得如下線性方程組解得，x03=x04=4。X0 = (x01，x02，x03，x04)T=(0，0，4，4)T 2.3原問題檢驗(yàn)數(shù)與對偶問題的解在主對偶定理的證明中我們有：對偶(min型)變量的最優(yōu)解等于原問題松弛變量的機(jī)會成本，或者說原問題松弛變量檢驗(yàn)數(shù)的絕對值 可以證明，對偶問題最優(yōu)解的剩余變量解值等于原問題對應(yīng)變量的檢驗(yàn)數(shù)的絕對值由于原問題和對偶問題是相互對偶的，因此對偶問題的檢驗(yàn)數(shù)與原問題的解也有類似

53、上述關(guān)系。更一般地講，可以證明，不管原問題是否標(biāo)準(zhǔn)，在最優(yōu)解的單純型表中，都有原問題虛變量(松弛、剩余或人工變量) 的機(jī)會成本的絕對值等于其對偶問題實(shí)變量 (對偶變量)的最優(yōu)解的絕對值，原問題實(shí)變量(決策變量)的檢驗(yàn)數(shù)的絕對值等于其對偶問題虛變量 (松弛或剩余變量)的最優(yōu)解的絕對值。因此，原問題或?qū)ε紗栴}只需求解其中之一就可以了。114 例2.2.3 原問題檢驗(yàn)數(shù)與對偶問題的解1151161172.4對偶單純型法2.4.1 基本思路1、原單純型迭代要求每步都是基礎(chǔ)可行解2、達(dá)到最優(yōu)解時，檢驗(yàn)數(shù) cjzj 0 (max)3、對于(min, )型所加的剩余變量無法構(gòu)成初始基礎(chǔ)可行解4、因此通過加人

54、工變量來解決,但大M法和二階段法較繁5、對偶單純形法基本思路： 從原問題的某一個滿足最優(yōu)檢驗(yàn)條件的基本解出發(fā)，判斷該基本解是否滿足可行性條件，若是，則已得最優(yōu)解，若否，則通過迭代得到另一個滿足最優(yōu)檢驗(yàn)條件且更接近可行解的基本解。如此循環(huán)，直到找到滿足最優(yōu)檢驗(yàn)條件且可行解的基本解（即最優(yōu)解）為止。118 2.4.2對偶單純形法的步驟1、求一個滿足最優(yōu)檢驗(yàn)條件的初始基礎(chǔ)解，列出初始單純形表；2、可行性檢驗(yàn) 若所有的右端系數(shù)均大于等于0，即 bi 0，i=1,2,.,m則已得最優(yōu)解，停止運(yùn)算。否則，轉(zhuǎn)步驟3；3、求另一個滿足最優(yōu)檢驗(yàn)條件且更接近可行解的基礎(chǔ)解1）確定出變量 找非可行解中分量最小者，即

55、 min bi | bi 0，不會破壞最優(yōu)解若 aij 0 中找最大者，對應(yīng) xij 就是入變量2、以 xij 為起點(diǎn)，尋找由原基變量構(gòu)成的閉合回路該回路只在每個拐角各有一個基變量，中間允許穿越某些基變量；因此，閉合回路中必有偶數(shù)個變量(包括 xij )，且回路中每行每列只有兩個變量3、求入變量 xij 的最大值及新基變量的解從 xij出發(fā)，沿任一個方向?qū)芈饭战巧系幕兞恳来藰?biāo)“”和“+”，表示“”和“+” xij ，從而迭代后仍滿足分配的平衡標(biāo)有“”的變量中最小者就是出變量xij* ，對應(yīng) xij*的值就是所求入變量 xij 的最大值標(biāo)有“”的變量減去 xij*，標(biāo)有“+”的變量加上 xi

56、j* 4、用位勢法求新基變量的檢驗(yàn)數(shù)若所有 zij wij 0，則達(dá)到最優(yōu)，算法停止；否則返回 1159 例3.2.1 踏石法，以最低費(fèi)用法所得初始解開始160答：最優(yōu)解如上分配表，OBJ=98OBJ=121OBJ=1013.3 運(yùn)輸問題迭代中的一些具體問題 3.3.1 閉合回路的畫法從入變量xij出發(fā)，遇到某個基變量則選一個方向拐角，若不能再遇到其它基變量，則返回上一拐角，換一個方向走，采用深探法閉合回路不一定是矩形 3.3.2 產(chǎn)銷不平衡供過于求，即 ai bj ，增加一個虛收點(diǎn)Dn+1，bn+1= ai - bj , 令 wi,n+1=0, i=1,2,m供小于求，即 ai 0 中找最大

57、者，對應(yīng) xij 就是入變量2、以 xij 為起點(diǎn)，尋找由原基變量構(gòu)成的閉合回路該回路只在每個拐角各有一個基變量，中間允許穿越某些基變量；因此，閉合回路中必有偶數(shù)個變量(包括 xij )，且回路中每行每列只有兩個變量3、求入變量 xij 的最大值及新基變量的解從 xij出發(fā)，沿任一個方向?qū)芈饭战巧系幕兞恳来藰?biāo)“”和“+”，表示“”和“+” xij ，從而迭代后仍滿足分配的平衡標(biāo)有“”的變量中最小者就是出變量xij* ，對應(yīng) xij*的值就是所求入變量 xij 的最大值標(biāo)有“”的變量減去 xij*，標(biāo)有“+”的變量加上 xij* 4、用位勢法求新基變量的檢驗(yàn)數(shù)若所有 zij wij 0，則達(dá)

58、到最優(yōu)，算法停止；否則返回 1164 例3.2.1 踏石法，以最低費(fèi)用法所得初始解開始165答：最優(yōu)解如上分配表，OBJ=98OBJ=121OBJ=1013.3 運(yùn)輸問題迭代中的一些具體問題 3.3.1 閉合回路的畫法從入變量xij出發(fā)，遇到某個基變量則選一個方向拐角，若不能再遇到其它基變量，則返回上一拐角，換一個方向走，采用深探法閉合回路不一定是矩形 3.3.2 產(chǎn)銷不平衡供過于求，即 ai bj ，增加一個虛收點(diǎn)Dn+1，bn+1= ai - bj , 令 wi,n+1=0, i=1,2,m供小于求，即 ai bj ，增加一個虛發(fā)點(diǎn)Wm+1，am+1= bj - ai , 令 wm+1,j

59、=0, j=1,2,n 3.3.3 關(guān)于退化問題1、初始解退化。即所求初始基變量的個數(shù)少于 m+n1。必須補(bǔ)足基變量的個數(shù)，否則不能正常解出 m+n個 ui 和 vj所補(bǔ)基變量的值為 0 ，補(bǔ)充的原則：(1)盡量先選運(yùn)費(fèi)小的實(shí)變量；(2)補(bǔ)充后不能有某個基變量獨(dú)占一行一列166 3.3.3 關(guān)于退化問題2、迭代過程中出現(xiàn)退化閉合回路中標(biāo)有“”的基變量同時有多個達(dá)到最小變換后，有多個原基變量變?yōu)?0，選運(yùn)費(fèi)最大者為出變量，其余保留在新的基礎(chǔ)解中退化較嚴(yán)重時，可能會出現(xiàn)多次迭代只有值為 0 的基變量在轉(zhuǎn)移。此時，一要耐心，二要正確選擇出變量167踏石法迭代中需注意的問題：1、錯誤地將分配表中基變量

60、的解代入到運(yùn)費(fèi)表中2、不能正確畫閉合回路3、初始解退化，未能補(bǔ)足基變量的個數(shù)。因此在位勢法中多次令某個 ui 或 vj 為 0；4、在位勢法中只能令一個 ui 或 vj 為 0；若不能求出全部 ui和 vj ，說明基變量未選夠數(shù)或未選對168169170171第四章 整數(shù)規(guī)劃 整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃4.1 整數(shù)規(guī)劃簡介要求所有 xj 的解為整數(shù)，稱為純整數(shù)規(guī)劃要求部分 xj 的解為整數(shù)，稱為混合整數(shù)規(guī)劃對應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題整數(shù)規(guī)劃的解是可數(shù)個的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解1734.2 整數(shù)規(guī)劃的解法 4.2.1 思路與解題步