1、林齊寧林齊寧博士，教授博士，教授北京郵電大學(xué)經(jīng)濟管理學(xué)院北京郵電大學(xué)經(jīng)濟管理學(xué)院Telel_mail:E_mail: 緒緒 論論 一、運籌學(xué)的起源與發(fā)展一、運籌學(xué)的起源與發(fā)展 二、運籌學(xué)的定義和主要研究分支二、運籌學(xué)的定義和主要研究分支 三、運籌學(xué)的特點及研究對象三、運籌學(xué)的特點及研究對象 四、運籌學(xué)解決問題的方法步驟四、運籌學(xué)解決問題的方法步驟 五、五、運籌學(xué)與其他學(xué)科的關(guān)系運籌學(xué)與其他學(xué)科的關(guān)系一、運籌學(xué)的起源與發(fā)展一、運籌學(xué)的起源與發(fā)展 起源于二次大戰(zhàn)的一門新興交叉學(xué)科起源于二次大戰(zhàn)的一門新興交叉學(xué)科 與作戰(zhàn)問題相關(guān)與作戰(zhàn)問題相關(guān) 如雷

2、達(dá)的設(shè)置、運輸船隊的護(hù)航、反潛作戰(zhàn)中深水炸彈如雷達(dá)的設(shè)置、運輸船隊的護(hù)航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲等的深度、飛行員的編組、軍事物資的存儲等 英國稱為英國稱為 Operational Research 美國稱為美國稱為 Operations Research 戰(zhàn)后在經(jīng)濟、管理和機關(guān)學(xué)校及科研單戰(zhàn)后在經(jīng)濟、管理和機關(guān)學(xué)校及科研單位繼續(xù)研究位繼續(xù)研究 1952年，年，Morse 和和 Kimball出版出版運籌學(xué)方法運籌學(xué)方法 1948年英國首先成立運籌學(xué)會年英國首先成立運籌學(xué)會 1952年美國成立運籌學(xué)會年美國成立運籌學(xué)會 1959年成立國際運籌學(xué)聯(lián)合會年成立國際運籌

3、學(xué)聯(lián)合會(IFORS) 我國于我國于1982年加入年加入IFORS，并于，并于1999年年8月組織了第月組織了第15屆大會屆大會一、運籌學(xué)的起源與發(fā)展一、運籌學(xué)的起源與發(fā)展1、中國運籌學(xué)會簡介、中國運籌學(xué)會簡介50年代中期，我國著名科學(xué)家錢學(xué)森、許國志等教授將運籌學(xué)從西方引年代中期，我國著名科學(xué)家錢學(xué)森、許國志等教授將運籌學(xué)從西方引入國內(nèi)。入國內(nèi)。1980年年4月，中國數(shù)學(xué)會運籌學(xué)分會成立。月，中國數(shù)學(xué)會運籌學(xué)分會成立。1991年，中國運籌年，中國運籌學(xué)會成立學(xué)會成立。歷屆學(xué)會理事長有，華羅庚、越民義，徐光輝，。歷屆學(xué)會理事長有，華羅庚、越民義，徐光輝，章祥蓀章祥蓀，袁袁亞湘亞湘，2、中國系統(tǒng)

4、工程學(xué)會簡介、中國系統(tǒng)工程學(xué)會簡介 1、1979年由錢學(xué)森、宋健、關(guān)肇直、許國志等年由錢學(xué)森、宋健、關(guān)肇直、許國志等21名專家、學(xué)者共同倡名專家、學(xué)者共同倡議并籌備。議并籌備。1980年年11月月18日在北京正式成立。日在北京正式成立。 第一屆理事會理事長關(guān)第一屆理事會理事長關(guān)肇直，第二、三屆理事長許國志。第四、五屆理事長顧基發(fā)、第六屆理肇直，第二、三屆理事長許國志。第四、五屆理事長顧基發(fā)、第六屆理事長陳光亞。事長陳光亞。3、運籌學(xué)、系、運籌學(xué)、系 統(tǒng)工程統(tǒng)工程 主要研究人員構(gòu)成主要研究人員構(gòu)成1）數(shù)學(xué)：如華羅庚、越民義，徐光輝，）數(shù)學(xué)：如華羅庚、越民義，徐光輝，章祥蓀章祥蓀，袁亞湘袁亞湘，許

5、國志，顧，許國志，顧基發(fā)等；基發(fā)等；2）控制論：張仲俊，劉豹，陳珽，鄭維敏，趙純均，陳劍等）控制論：張仲俊，劉豹，陳珽，鄭維敏，趙純均，陳劍等3）管理等專業(yè)相關(guān)教學(xué)、科研技術(shù)人員）管理等專業(yè)相關(guān)教學(xué)、科研技術(shù)人員567一、運籌學(xué)的起源與發(fā)展一、運籌學(xué)的起源與發(fā)展4、相關(guān)研究機構(gòu)和高校、相關(guān)研究機構(gòu)和高校1）中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院系統(tǒng)科學(xué)研究所）中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院系統(tǒng)科學(xué)研究所2）中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所）中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所3）哈工大：胡運權(quán)，黃梯云，錢國明等）哈工大：胡運權(quán)，黃梯云，錢國明等4）天津大學(xué)：劉豹，顧培亮，張維，）天

6、津大學(xué)：劉豹，顧培亮，張維，杜杜 綱綱等等5）西安交大：汪應(yīng)洛，席酉民等）西安交大：汪應(yīng)洛，席酉民等6）上海交大：張仲俊，王浣塵等）上海交大：張仲俊，王浣塵等7）清華大學(xué)：鄭維敏，趙純均，陳劍等；）清華大學(xué)：鄭維敏，趙純均，陳劍等；8）大連理工：王眾托，胡祥培等）大連理工：王眾托，胡祥培等9）北航：顧昌耀，黃海軍等）北航：顧昌耀，黃海軍等10）北理工）北理工 ：吳滄浦吳滄浦，吳祈宗，張強等，吳祈宗，張強等9二、運籌學(xué)的定義和主要研究分支二、運籌學(xué)的定義和主要研究分支 運籌學(xué)的定義運籌學(xué)的定義 為決策機構(gòu)對所控制的業(yè)務(wù)活動作決策時，提供以數(shù)量為決策機構(gòu)對所控制的業(yè)務(wù)活動作決策時，提供以數(shù)量為基礎(chǔ)

7、的科學(xué)方法為基礎(chǔ)的科學(xué)方法Morse 和和 Kimball 運籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府運籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個科學(xué)的系統(tǒng)模式，并運用這種模式預(yù)測，比較各種決策科學(xué)的系統(tǒng)模式，并運用這種模式預(yù)測，比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針和政策和政策英國運籌學(xué)會英國運籌學(xué)會 運籌學(xué)是應(yīng)用分析、試驗、量化的方法對經(jīng)濟管理系統(tǒng)運籌學(xué)是應(yīng)用分析、試驗、量化的方法對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資

8、源進(jìn)行統(tǒng)籌安排，為決策者提中人力、物力、財力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理供有根據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理中國百中國百科全書科全書 現(xiàn)代運籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問題，稱為現(xiàn)代運籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問題，稱為 Management Science10二、運籌學(xué)的定義和主要研究分支二、運籌學(xué)的定義和主要研究分支 運籌學(xué)的分支運籌學(xué)的分支 數(shù)學(xué)規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)數(shù)學(xué)規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、目標(biāo)規(guī)劃等劃、目標(biāo)規(guī)劃等 圖論與網(wǎng)路理論圖論與網(wǎng)路理論 隨機服務(wù)理論：排隊論隨機服務(wù)理論：排隊論 存儲

9、理論存儲理論 網(wǎng)絡(luò)計劃方法網(wǎng)絡(luò)計劃方法 決策理論決策理論 對策論對策論 系統(tǒng)仿真：隨機模擬技術(shù)、系統(tǒng)動力學(xué)系統(tǒng)仿真：隨機模擬技術(shù)、系統(tǒng)動力學(xué) 可靠性理論可靠性理論 金融工程金融工程11三、運籌學(xué)的特點及研究對象三、運籌學(xué)的特點及研究對象運籌學(xué)的特點：運籌學(xué)的特點：1)優(yōu)化優(yōu)化以整體最優(yōu)為目標(biāo)，從系統(tǒng)的觀點出發(fā)，力圖以整個系以整體最優(yōu)為目標(biāo)，從系統(tǒng)的觀點出發(fā)，力圖以整個系統(tǒng)最佳的方式來協(xié)調(diào)各部門之間的利害沖突，從而求出統(tǒng)最佳的方式來協(xié)調(diào)各部門之間的利害沖突，從而求出問題的最優(yōu)解。所以運籌學(xué)可看成是一門優(yōu)化技術(shù)，為問題的最優(yōu)解。所以運籌學(xué)可看成是一門優(yōu)化技術(shù)，為解決各類問題提供優(yōu)化方法解決各類問題

10、提供優(yōu)化方法2定量定量為所研究的問題提供定量的解決方案。如采用運籌學(xué)研為所研究的問題提供定量的解決方案。如采用運籌學(xué)研究資源分配問題時，其求解結(jié)果是一個定量的最優(yōu)資源究資源分配問題時，其求解結(jié)果是一個定量的最優(yōu)資源分配方案。分配方案。運籌學(xué)的研究對象：運籌學(xué)的研究對象：來自生產(chǎn)管理過程中的具體問題，如資源分配、物資調(diào)來自生產(chǎn)管理過程中的具體問題，如資源分配、物資調(diào)度，生產(chǎn)計劃與控制等。度，生產(chǎn)計劃與控制等。12四、運籌學(xué)解決問題的方法步驟四、運籌學(xué)解決問題的方法步驟 1、理清問題、明確目標(biāo)、理清問題、明確目標(biāo) 2、建立模型、建立模型 討論：什么叫模型討論：什么叫模型 3、求解模型。建立模型之后

11、，、求解模型。建立模型之后，需要設(shè)計相應(yīng)算法進(jìn)需要設(shè)計相應(yīng)算法進(jìn)行求解，實際問題行求解，實際問題運算量一般都很大，通常需要用計運算量一般都很大，通常需要用計算機算機求解求解。 4、結(jié)果分析、結(jié)果分析 討論：模型計算結(jié)果與已有的經(jīng)驗或知識進(jìn)行比較討論：模型計算結(jié)果與已有的經(jīng)驗或知識進(jìn)行比較 1）模型計算結(jié)果和已有的經(jīng)驗或知識比較一致）模型計算結(jié)果和已有的經(jīng)驗或知識比較一致 2）模型計算結(jié)果和已有的經(jīng)驗或知識差異較大）模型計算結(jié)果和已有的經(jīng)驗或知識差異較大 你喜歡那一種情況？你喜歡那一種情況？13五、五、運籌學(xué)與其他學(xué)科的關(guān)系運籌學(xué)與其他學(xué)科的關(guān)系 運籌學(xué)運籌學(xué)目標(biāo)分析、目標(biāo)分析、建模建模、求解求

12、解和結(jié)果分析需要用到和結(jié)果分析需要用到很多相關(guān)學(xué)科的知識，它與如下學(xué)科的知識關(guān)系比較很多相關(guān)學(xué)科的知識，它與如下學(xué)科的知識關(guān)系比較密切。密切。 1、數(shù)學(xué)：、數(shù)學(xué)：學(xué)習(xí)、應(yīng)用運籌學(xué)應(yīng)該具備較廣的數(shù)學(xué)知識，學(xué)習(xí)、應(yīng)用運籌學(xué)應(yīng)該具備較廣的數(shù)學(xué)知識，許多運籌學(xué)者來自數(shù)學(xué)專業(yè)就是這個原因，有人甚至許多運籌學(xué)者來自數(shù)學(xué)專業(yè)就是這個原因，有人甚至認(rèn)為運籌學(xué)是一門應(yīng)用數(shù)學(xué)認(rèn)為運籌學(xué)是一門應(yīng)用數(shù)學(xué)； 2、管理學(xué)：運籌學(xué)研究對象是、管理學(xué)：運籌學(xué)研究對象是生產(chǎn)管理過程的具體問生產(chǎn)管理過程的具體問題，在利用運籌學(xué)理論和方法解決具體問題時，需要題，在利用運籌學(xué)理論和方法解決具體問題時，需要的涉及管理科學(xué)的有關(guān)理論的涉

13、及管理科學(xué)的有關(guān)理論； 3、計算機：、計算機：運籌學(xué)所研究的實際問題通常都是比較復(fù)運籌學(xué)所研究的實際問題通常都是比較復(fù)雜，而且規(guī)模比較大，在求解這些問題時，必須借助雜，而且規(guī)模比較大，在求解這些問題時，必須借助計算機來完成計算機來完成。14第一章第一章 線性規(guī)劃線性規(guī)劃1.1 線性規(guī)劃模型線性規(guī)劃模型1.1.11.1.1問題的提出問題的提出一、一、例例1 1、多產(chǎn)品生產(chǎn)問題、多產(chǎn)品生產(chǎn)問題（Max, ）甲電纜甲電纜乙電纜乙電纜資源量資源量銅（噸）銅（噸）2110鉛（噸）鉛（噸）118價格（萬元）價格（萬元）64需求需求無限制無限制7另 問該工廠應(yīng)如何安排生產(chǎn)才能使工廠的總收入最大？問該工廠應(yīng)如

14、何安排生產(chǎn)才能使工廠的總收入最大？一、一、例例1 1、多產(chǎn)品生產(chǎn)問題、多產(chǎn)品生產(chǎn)問題（Max, ） 設(shè)設(shè)x1, x2 分別代表甲、乙兩種電纜的生產(chǎn)量，分別代表甲、乙兩種電纜的生產(chǎn)量，f(x)為工廠為工廠的總收入，則上述問題可用如下數(shù)學(xué)模型來表示的總收入，則上述問題可用如下數(shù)學(xué)模型來表示其中，其中，OBJ（Objective）表示目標(biāo)，）表示目標(biāo)，S.t.（Subject to）表示滿足）表示滿足于。表示在滿足銅、鉛資源和需求等約束條件下，使工廠的總收于。表示在滿足銅、鉛資源和需求等約束條件下，使工廠的總收入這一目標(biāo)達(dá)到最大入這一目標(biāo)達(dá)到最大。最優(yōu)解為。最優(yōu)解為產(chǎn)量不允許為負(fù)值產(chǎn)量約束鉛資源約束

15、銅資源約束0,78102. .46)(max:212212121xxxxxxxtsxxxfOBJ.36)(max, 6, 221xfxx二、例二、例2、配料問題（、配料問題（min, ) )某混合飼料加工廠計劃從市場上購買甲、乙兩種原料生產(chǎn)一種某混合飼料加工廠計劃從市場上購買甲、乙兩種原料生產(chǎn)一種混合飼料?；旌巷暳蠈旌巷暳?。混合飼料對VA、VB1、VB2和和VD的最低含量有一定的最低含量有一定的要求。已知單位甲、乙兩種原料的要求。已知單位甲、乙兩種原料VA、VB1、VB2和和VD的含量，的含量，單位混合飼料對單位混合飼料對VA、VB1、VB2和和VD的最低含量以及甲、乙兩的最低含量以及甲、乙

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

17、優(yōu)解為該數(shù)學(xué)模型的最優(yōu)解為該問題的最優(yōu)解為x1=3.69，x2=0.77，minf(x)=1.490,22 . 05 . 02 . 16 . 02 . 033 . 00 . 125 . 05 . 0. .5 . 03 . 0)(min212121212121xxxxxxxxxxtsxxxf三、線性規(guī)劃數(shù)學(xué)模型的特征和定義三、線性規(guī)劃數(shù)學(xué)模型的特征和定義1、線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型的特征的特征：1）有一組決策變量（有一組決策變量（x1，x2，xn）表示某一方案。這一組）表示某一方案。這一組決策變量的具體值就代表一個具體方案；決策變量的具體值就代表一個具體方案；2）有一個目標(biāo)函數(shù)，該目標(biāo)函

18、數(shù)根據(jù)其的具體性質(zhì)取最大值有一個目標(biāo)函數(shù)，該目標(biāo)函數(shù)根據(jù)其的具體性質(zhì)取最大值或最小值。當(dāng)目標(biāo)為成本型時取最小，而當(dāng)目標(biāo)為效益型時取或最小值。當(dāng)目標(biāo)為成本型時取最小，而當(dāng)目標(biāo)為效益型時取最大。最大。3）有一組約束方程，包括決策變量的非負(fù)約束；有一組約束方程，包括決策變量的非負(fù)約束；4）目標(biāo)函數(shù)和約束方程都是線性的。目標(biāo)函數(shù)和約束方程都是線性的。2、線性規(guī)劃數(shù)學(xué)模型的定義線性規(guī)劃數(shù)學(xué)模型的定義定義定義1.1 有一個目標(biāo)函數(shù)和一組約束方程，且目標(biāo)函數(shù)和約束有一個目標(biāo)函數(shù)和一組約束方程，且目標(biāo)函數(shù)和約束方程都是線性的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。方程都是線性的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。四、線性規(guī)劃

19、數(shù)學(xué)模型的背景模型和思考四、線性規(guī)劃數(shù)學(xué)模型的背景模型和思考1、線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型的背景模型的背景模型：例例1.1的多產(chǎn)品生產(chǎn)計劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的背景模的多產(chǎn)品生產(chǎn)計劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的背景模型。把該背景模型的條件一般化后可敘述如下：用有限量的幾型。把該背景模型的條件一般化后可敘述如下：用有限量的幾種資源生產(chǎn)若干種產(chǎn)品，如何安排生產(chǎn)，才能使工廠的總收入種資源生產(chǎn)若干種產(chǎn)品，如何安排生產(chǎn)，才能使工廠的總收入或利潤達(dá)到最大。或利潤達(dá)到最大。2、背景模型的思考、背景模型的思考1）討論：什么叫背景模型）討論：什么叫背景模型能夠幫助我們理解和記住一些相對抽象和復(fù)雜問題

20、的簡單問題能夠幫助我們理解和記住一些相對抽象和復(fù)雜問題的簡單問題模型。模型。2）背景模型的思考）背景模型的思考利用一些相對比較簡單的問題來闡述一些相對復(fù)雜和抽象的運利用一些相對比較簡單的問題來闡述一些相對復(fù)雜和抽象的運籌學(xué)中的一些籌學(xué)中的一些基礎(chǔ)基礎(chǔ)概念和原理是概念和原理是本課程本課程力求在力求在教學(xué)教學(xué)中體現(xiàn)的第中體現(xiàn)的第一個特點，一個特點，希望大家希望大家用心體會用心體會。 1.1.2 1.1.2 線性規(guī)劃數(shù)學(xué)模型的一般表示方式線性規(guī)劃數(shù)學(xué)模型的一般表示方式技術(shù)系數(shù)右端項價值系數(shù)線性規(guī)劃問題的規(guī)模約束行數(shù)變量個數(shù): ;: ;: ;: ;:0,),(),(),(.)(max(min)2122

21、1122222121112121112211ijijnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf21 1、和式和式njxmibxatsxcxfjinjjijnjjj, 2 , 1 , 0, 2 , 1 ,.)(max1122 2、向量式向量式0000 ),( );,( .)(max210212121010bbbbaaaPxxxXcccC0XbxPtsCXxfmmjjjjTnnnjjj23 3、矩陣式矩陣式 00 ,00),(),();,(. .)(max212121212222111211矩陣表示，TTmTnnmnmmnnbbbx

22、xxcccaaaaaaaaatsxf0bXCA0XbAXCX24 1.1.3 線性規(guī)劃的圖解法線性規(guī)劃的圖解法1187654322x1876543O109x2A BCEDFGH123f(x)=0f(x)=12.36)(max, 6, 2:0,78102.46)(max21212212121xfxxxxxxxxxtsxxxf最優(yōu)解最優(yōu)解1187654322x1876543O109x2A BCEDFGH123f(x)=36線性規(guī)劃問題的幾個特點：線性規(guī)劃問題的幾個特點： 1、線性規(guī)劃的可行域為凸集、線性規(guī)劃的可行域為凸集； 討論：什么叫凸集？討論：什么叫凸集？ 集合中任意兩點連線上的一切點仍然在該

23、集合中，在平面上集合中任意兩點連線上的一切點仍然在該集合中，在平面上為凸多邊形，在空間上為凸幾何體；為凸多邊形，在空間上為凸幾何體； 討論：最優(yōu)解在那里取得？討論：最優(yōu)解在那里取得？ 2、線性規(guī)劃的最優(yōu)解一定可在其凸集的某一頂點上達(dá)到；、線性規(guī)劃的最優(yōu)解一定可在其凸集的某一頂點上達(dá)到； 討論：什么情況有最優(yōu)解？最優(yōu)解的存在性條件？討論：什么情況有最優(yōu)解？最優(yōu)解的存在性條件？ 3、線性規(guī)劃若有可行域且其可行域有界，則一定有最優(yōu)解。、線性規(guī)劃若有可行域且其可行域有界，則一定有最優(yōu)解。 上述上述3個結(jié)論是線性規(guī)劃的個結(jié)論是線性規(guī)劃的3個個基礎(chǔ)基礎(chǔ)定理，可以用嚴(yán)格的數(shù)學(xué)定理，可以用嚴(yán)格的數(shù)學(xué)方法進(jìn)行證

24、明方法進(jìn)行證明。我們以簡單、直觀的圖解法方式給出，相信我們以簡單、直觀的圖解法方式給出，相信大家是可以接受的。大家是可以接受的。 1.3 線性規(guī)劃求解的線性規(guī)劃求解的基礎(chǔ)基礎(chǔ)原理和單純形法原理和單純形法1.3.1 1.3.1 線性規(guī)劃問題的標(biāo)準(zhǔn)形線性規(guī)劃問題的標(biāo)準(zhǔn)形一、線性規(guī)劃模型一般形式一、線性規(guī)劃模型一般形式二、求解思路二、求解思路1 1、規(guī)定一標(biāo)準(zhǔn)型線性的規(guī)劃問題數(shù)學(xué)模型；規(guī)定一標(biāo)準(zhǔn)型線性的規(guī)劃問題數(shù)學(xué)模型；2 2、如何把非標(biāo)準(zhǔn)形的線性規(guī)劃問題數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形如何把非標(biāo)準(zhǔn)形的線性規(guī)劃問題數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形線性規(guī)劃問題數(shù)學(xué)模型？線性規(guī)劃問題數(shù)學(xué)模型？3 3、如何求解標(biāo)準(zhǔn)形線性規(guī)劃問題

25、數(shù)學(xué)模型。如何求解標(biāo)準(zhǔn)形線性規(guī)劃問題數(shù)學(xué)模型。njxmibxatsxcxfjinjjijnjjj,2 , 1 ),0(0,2 , 1 ,),(.)(max(min)11不不限限三、三、線性規(guī)劃問題的標(biāo)準(zhǔn)形線性規(guī)劃問題的標(biāo)準(zhǔn)形在上述線性規(guī)劃標(biāo)準(zhǔn)形中，決策變量的個數(shù)取在上述線性規(guī)劃標(biāo)準(zhǔn)形中，決策變量的個數(shù)取n+mn+m個是習(xí)慣表個是習(xí)慣表示法。我們知道，對于線性規(guī)劃背景模型，有示法。我們知道，對于線性規(guī)劃背景模型，有m m個約束方程，個約束方程，且每個約束方程的不等式均為且每個約束方程的不等式均為“ ”號。如果我們在每個約束號。如果我們在每個約束方程的左邊加上一個大于等于方程的左邊加上一個大于等于

26、0 0的變量，則可將各個約束方程的變量，則可將各個約束方程的的“ ”號轉(zhuǎn)變?yōu)樘栟D(zhuǎn)變?yōu)椤? =”。此時，決策變量就有。此時，決策變量就有n+mn+m個。個。njmixbmibxatsxcxfjiimnjjijmnjjj, 2 , 1 , 2 , 1 , 0, 2 , 1 ,.)(max1128 四、變換的方法變換的方法 1 1、目標(biāo)函數(shù)為、目標(biāo)函數(shù)為minmin型，價值系數(shù)一律反號。令型，價值系數(shù)一律反號。令 g(g(x x) = ) = - -f f( (x x) = -) = -CXCX, , 有有 min min f f( (x x) = - max - ) = - max - f f(

27、(x) = - x) = - max gmax g( (x)x) 2 2、第、第i i 個約束的個約束的b bi i 為負(fù)值，則該行左右兩端系數(shù)同時為負(fù)值，則該行左右兩端系數(shù)同時反號，同時不等號也要反向反號，同時不等號也要反向 3 3、第、第i i 個約束為個約束為 型，在不等式左邊增加一個非負(fù)的型，在不等式左邊增加一個非負(fù)的變量變量x xn+in+i ，稱為松弛變量；同時令稱為松弛變量；同時令 c cn+in+i = 0= 0 4 4、第、第i i 個約束為個約束為 型，在不等式左邊減去一個非負(fù)的型，在不等式左邊減去一個非負(fù)的變量變量x xn+in+i ，稱為剩余變量；同時令稱為剩余變量；同

28、時令 c cn+in+i = 0= 0 5 5、若、若x xj j 0 0，令，令 x xj j= -= -x xj j ，代入非標(biāo)準(zhǔn)型，則有，代入非標(biāo)準(zhǔn)型，則有x xj j 0 0 6 6、若、若x xj j 不限，令不限，令 x xj j= = x xj j - - x xj j ， x xj j 0 0，x xj j 0 0，代入非標(biāo)準(zhǔn)型代入非標(biāo)準(zhǔn)型29 五、五、 變換舉例：變換舉例：0, ,20040065300432. .423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限原非標(biāo)準(zhǔn)型 0,2004006653004432.0004423)(max

29、:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型1.3.2 線性規(guī)劃問題的解和線性規(guī)劃問題的解和基礎(chǔ)基礎(chǔ)定理定理本章開始到現(xiàn)在已討論的內(nèi)容，相信大部分讀者都會感到本章開始到現(xiàn)在已討論的內(nèi)容，相信大部分讀者都會感到比較容易理解和掌握。這一節(jié)我們將要討論關(guān)于線性規(guī)劃比較容易理解和掌握。這一節(jié)我們將要討論關(guān)于線性規(guī)劃問題解的一些問題解的一些基礎(chǔ)基礎(chǔ)概念和定理，與前面討論的內(nèi)容相比，概念和定理，與前面討論的內(nèi)容相比，線性規(guī)劃問題解的一些線性規(guī)劃問題解的一些基礎(chǔ)基礎(chǔ)概念略顯難一些，其中比較難概念略顯難一些，其中比較

30、難的概念有線性規(guī)劃問題的基和基礎(chǔ)解等相關(guān)概念。為了幫的概念有線性規(guī)劃問題的基和基礎(chǔ)解等相關(guān)概念。為了幫助大家比較容易理解這些概念，我們先從大家熟悉的兩個助大家比較容易理解這些概念，我們先從大家熟悉的兩個變量兩個線性方程組這一簡單問題入手，然后逐步過渡到變量兩個線性方程組這一簡單問題入手，然后逐步過渡到我們所要討論的線性規(guī)劃問題的基和基礎(chǔ)解等相關(guān)概念。我們所要討論的線性規(guī)劃問題的基和基礎(chǔ)解等相關(guān)概念。著名數(shù)學(xué)家笛卡爾曾說過，他最擅長做的兩件事是：著名數(shù)學(xué)家笛卡爾曾說過，他最擅長做的兩件事是：1)第一做簡單事；第一做簡單事；2)第二是將復(fù)雜事變?yōu)楹唵问隆５诙菍?fù)雜事變?yōu)楹唵问?。本本課程課程將從大

31、家熟悉的一些簡單問題入手，然后逐步過渡將從大家熟悉的一些簡單問題入手，然后逐步過渡到運籌學(xué)一些相對比較抽象和難的概念和原理。這是本到運籌學(xué)一些相對比較抽象和難的概念和原理。這是本課課程教學(xué)程教學(xué)力求的另一特點。力求的另一特點。一、線性方程組的解一、線性方程組的解考慮如下線性方程組的解：考慮如下線性方程組的解：(1) 852532121xxxx(2) 2121xx再考慮如下線性方程組的解：再考慮如下線性方程組的解：(3) 85253321321xxxxxx (4)221333231xxxxxx(5) 021321xxx一、線性方程組的解一、線性方程組的解類似地，如果將方程組（類似地，如果將方程組

32、（3 3）中的變量）中的變量x x2 2或或x x1 1當(dāng)成常數(shù)，分別當(dāng)成常數(shù)，分別移到其方程的右邊后采用消元法進(jìn)行求解，則也可得到如下移到其方程的右邊后采用消元法進(jìn)行求解，則也可得到如下兩組兩組通通解解及其特解及其特解：(6) 223222321xxxxxx(8) 21212123111312xxxxxx(7) 023231xxx(9) 02123132xxx一、線性方程組的解一、線性方程組的解仔細(xì)觀察和思考方程組（仔細(xì)觀察和思考方程組（3 3）的三組通解（）的三組通解（4 4）、（）、（6 6）和）和（8 8）或三組特解（）或三組特解（5 5）、（）、（7 7）和（）和（9 9）是如何得到

33、的，以）是如何得到的，以及能夠得到這些通解或特解的條件是什么？根據(jù)求解線性及能夠得到這些通解或特解的條件是什么？根據(jù)求解線性方程組克萊姆條件可知，能夠得到方程組（方程組克萊姆條件可知，能夠得到方程組（3 3）的通解（）的通解（4 4）或特解（或特解（5 5）的條件是方程組（）的條件是方程組（3 3）中的變量）中的變量x x1 1和和x x2 2的系數(shù)的系數(shù)矩陣行列式不等于矩陣行列式不等于0 0，即，即 0-15231B1或變量或變量x x1 1和和x x2 2的系數(shù)矩陣的系數(shù)矩陣B B1 1是非奇異矩陣或變量是非奇異矩陣或變量x x1 1和和x x2 2的的系數(shù)列向量是線性無關(guān)。顯然，這三個條

34、件是等價的。系數(shù)列向量是線性無關(guān)。顯然，這三個條件是等價的。一、線性方程組的解一、線性方程組的解同樣，由于方程組組（同樣，由于方程組組（3 3）中的變量）中的變量x x1 1和和x x3 3的系數(shù)矩陣行列式的系數(shù)矩陣行列式|B|B2 2| |不等于不等于0 0與與變量變量x x2 2和和x x3 3的系數(shù)矩陣行列式的系數(shù)矩陣行列式|B|B3 3| |不等于不等于0 0，即即 0-11211B2 0-11513B3才能得到方程組（才能得到方程組（3 3）的通解或特解（）的通解或特解（6 6）或（）或（7 7）與與通解或通解或特解（特解（8 8）或（）或（9 9）。將上面討論的方程組（將上面討論的

35、方程組（3 3）加上一目標(biāo)函數(shù)和變量非負(fù)約）加上一目標(biāo)函數(shù)和變量非負(fù)約束條件后就變成一標(biāo)準(zhǔn)型線性規(guī)劃。如：束條件后就變成一標(biāo)準(zhǔn)型線性規(guī)劃。如：(10) 0,0,085253.32)(321321321321xxxxxxxxxtsxxxxMaxf一、線性方程組的解一、線性方程組的解對于對于上述標(biāo)準(zhǔn)型線性規(guī)劃（上述標(biāo)準(zhǔn)型線性規(guī)劃（1010）, ,稱稱 B B1 1 、B B2 2和和B B3 3為線性規(guī)劃為線性規(guī)劃（1010）的基。因利用其中任何一個基）的基。因利用其中任何一個基B B1 1 或或B B2 2或或B B3 3，都能得到，都能得到線性規(guī)劃（線性規(guī)劃（1010）的一組通解和特解（見式（

36、）的一組通解和特解（見式（4 4）-（9 9）。）。5231 211xxB變量變量x x1 1和和x x2 2為基變量，變量為基變量，變量x x3 3為非基變量，令為非基變量，令x x3 3=0=0，得得解（解（5 5）為線性規(guī)劃（為線性規(guī)劃（1010）的基礎(chǔ)解，但）的基礎(chǔ)解，但因因該基礎(chǔ)解中該基礎(chǔ)解中x x1 1= -10= -10，不，不滿足線性規(guī)劃（滿足線性規(guī)劃（1010）的變量非負(fù)約束條件，因此，該基礎(chǔ)）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（解（5 5）是線性規(guī)劃（是線性規(guī)劃（1010）的基礎(chǔ)非可行解。）的基礎(chǔ)非可行解。1211 312xxB變量變量x x1 1和和x x3 3為基變量，

37、變量為基變量，變量x x2 2為非基變量，令為非基變量，令x x2 2=0=0，得得解（解（7 7）為線性規(guī)劃（為線性規(guī)劃（1010）的基礎(chǔ)解）的基礎(chǔ)解。該基礎(chǔ)解中該基礎(chǔ)解中x x1 1和和x x3 3均大于均大于0 0，滿，滿足線性規(guī)劃（足線性規(guī)劃（1010）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（7 7）是線性規(guī)劃（是線性規(guī)劃（1010）的基礎(chǔ)可行解。）的基礎(chǔ)可行解。1513 323xxB變量變量x x2 2和和x x3 3為基變量，變量為基變量，變量x x1 1為非基變量，令為非基變量，令x x1 1=0=0，得得解（解（9 9）為線性規(guī)劃（為線性規(guī)劃（

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

39、，構(gòu)成該標(biāo)準(zhǔn)型的一個列，構(gòu)成該標(biāo)準(zhǔn)型的一個基基，即，即 B = ( P1 , P2 , , Pm )， | B | 0 P1 , P2 , , Pm 稱為稱為基向量基向量 與與基向量基向量對應(yīng)的變量稱為對應(yīng)的變量稱為基變量基變量，記為，記為 XB = ( x1 , x2 , , xm )T，其余的變量稱為，其余的變量稱為非基變量非基變量，記為記為 XN = ( xm+1 , xm+2 , , xm+n ) T ， 故有故有 X = （XB ， XN ) 最多有最多有 個基個基mnmC二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念 可行解可行解與與非可行解非可行解 滿足約束

40、條件和非負(fù)條件的解滿足約束條件和非負(fù)條件的解 X 稱為稱為可行解可行解，不滿足約束，不滿足約束條件或非負(fù)條件的解條件或非負(fù)條件的解 X 稱為稱為非可行解非可行解 基礎(chǔ)解基礎(chǔ)解 對應(yīng)某一基對應(yīng)某一基B且令其且令其非基變量非基變量 XN = 0，求得，求得基變量基變量 XB的值。的值。稱稱X = (XB , XN)T為為基礎(chǔ)解?；A(chǔ)解。 其中其中，XB = B 1 b， XN = 0 XB 是是基礎(chǔ)解基礎(chǔ)解必須滿足如下條件：必須滿足如下條件： 1）非非0分量的個數(shù)分量的個數(shù) m； 2、m個基變量所對應(yīng)的系數(shù)矩陣為非奇異的；個基變量所對應(yīng)的系數(shù)矩陣為非奇異的； 3、滿足、滿足m個約束條件。個約束條件

41、。二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念 基礎(chǔ)可行解基礎(chǔ)可行解與與基礎(chǔ)非可行解基礎(chǔ)非可行解基礎(chǔ)解基礎(chǔ)解 X XB B 的非零分量都的非零分量都 0 0 時，稱為時，稱為基礎(chǔ)可行解基礎(chǔ)可行解，否，否則為則為基礎(chǔ)非可行解。基礎(chǔ)非可行解。退化退化解解 基礎(chǔ)可行解基礎(chǔ)可行解的非零分量個數(shù)的非零分量個數(shù) f (X(0) )=0（五五）最優(yōu)檢驗）最優(yōu)檢驗將（將（5）式代入）式代入(1)的目標(biāo)函數(shù)后可得的目標(biāo)函數(shù)后可得 f (X)=30+x2-3x3 （6）從目標(biāo)函數(shù)（從目標(biāo)函數(shù)（6）可知，非基變量）可知，非基變量x2的系數(shù)是正數(shù)，的系數(shù)是正數(shù)，所以所以X(1)不是最優(yōu)解。不是

42、最優(yōu)解。（六六）求另一個更好的）求另一個更好的基礎(chǔ)基礎(chǔ)可行解可行解501、確定換入變量及其值、確定換入變量及其值從從目標(biāo)函數(shù)（從從目標(biāo)函數(shù)（6）可知，）可知，只有只有非基變量非基變量x2的系數(shù)的系數(shù)為正為正，所以，所以，可確定可確定x2為換入變量為換入變量。由于(7) 0702121302121525324321xxxxxxxx所以，所以，當(dāng)另一個非基變量當(dāng)另一個非基變量x3仍仍然為然為0時，由時，由（7）式可得到換式可得到換入變量入變量x1的值為的值為 x2=Min10/0.5，3/0.5，7/1=62、確定換出變量、確定換出變量從（從（7）式可知，當(dāng)）式可知，當(dāng)x2=6時，時，x4=0，所

43、以，所以x4為換出變量。由此得為換出變量。由此得到線性規(guī)劃（到線性規(guī)劃（1）的一個新的基）的一個新的基B2和和一組新的基變量與非基變一組新的基變量與非基變量。量。B2=(P1 ,P2 ,P5 ), XB2=（x1，x2，x5)T，XN2=（x3，x4)T513、求另一個更好的、求另一個更好的基礎(chǔ)基礎(chǔ)可行解可行解將將（1)約束方程中對應(yīng)于基約束方程中對應(yīng)于基B2的非基變量的非基變量x3和和x4移到方程的右移到方程的右邊后可得邊后可得7810252421321xxxxxxxx(8) 21262435432431xxxxxxxxx令非基變量令非基變量x3=x4=0，可得，可得另另一一基礎(chǔ)基礎(chǔ)可行解可

44、行解 X(2) = (2，6，0，0，1)T此時，對應(yīng)于此時，對應(yīng)于X(2)的目標(biāo)函數(shù)的目標(biāo)函數(shù)f (X(2) )=6x1+4x2=36 f (X(1) )=30（七七）最優(yōu)檢驗）最優(yōu)檢驗將（將（8）式代入）式代入(1)的目標(biāo)函數(shù)后可得的目標(biāo)函數(shù)后可得 f (X)=36-2x3-2x4 （9）從目標(biāo)函數(shù)（從目標(biāo)函數(shù)（9）可）可知知，非基變量，非基變量x3和和x4的系數(shù)都是的系數(shù)都是負(fù)負(fù)數(shù)，數(shù)，所以所以X(2)是最優(yōu)解。即是最優(yōu)解。即X*= X(2) = (2，6，0，0，1)T ,f (X*)=36三、求初始基礎(chǔ)可行解（背景模型，三、求初始基礎(chǔ)可行解（背景模型，MAX, )52設(shè)線性規(guī)劃問題為

45、設(shè)線性規(guī)劃問題為 , 2 , 1 , 0, 2 , 1 ,. .)(max11njxmibxatsxcxfjinjjijnjjj ,2, 1 ,0,2, 1 ,)(max 11mnjxmibxaxxcxfjimnmjjijimnjjj另設(shè)另設(shè)bi 0 (i=1,2,m)。標(biāo)。標(biāo)準(zhǔn)化后，若對準(zhǔn)化后，若對xj和和aij重新編重新編號，則約束方程可化為號，則約束方程可化為變量變量x1，x2，xm作為初始基變量，其余變量作為初始非作為初始基變量，其余變量作為初始非基變量基變量，并，并令令xm+1=xm+1=xn+m=0，則得則得初始本可行解初始本可行解 ),0,0,.,0b., ,b ,(bTm21(

46、0)X四、最優(yōu)檢驗四、最優(yōu)檢驗53對于標(biāo)準(zhǔn)化線性規(guī)劃問題對于標(biāo)準(zhǔn)化線性規(guī)劃問題(2)，經(jīng)過若干次迭代后，如果對，經(jīng)過若干次迭代后，如果對xj及及aij重新編號，則約束方程可化為重新編號，則約束方程可化為 , 2 , 1 1mixabxmnmjjijii其中，其中，bi和和aij表示經(jīng)過若干次迭代后，當(dāng)前的右端系數(shù)和技表示經(jīng)過若干次迭代后，當(dāng)前的右端系數(shù)和技術(shù)系數(shù)，以便區(qū)別于原始的右端系數(shù)術(shù)系數(shù)，以便區(qū)別于原始的右端系數(shù)bi和技術(shù)系數(shù)和技術(shù)系數(shù)aij。將。將上上式式代入代入（2）的）的目標(biāo)函數(shù)后可得目標(biāo)函數(shù)后可得mnmjjjjjmiijimimnmjjiimnmjjjmimnmjjijiixzczxaccbcxcxabcxf10111111)( )( ) ()( 10miiibcz 1miijijacz機會成本機會成本54在一般情況下，目標(biāo)函數(shù)值在一般情況下，目標(biāo)函數(shù)值OBJ計算公式和機會成本計算計算公式和機會成本計算公式可寫成公式可寫成四、最優(yōu)檢驗四、最優(yōu)檢驗 , 10IimkkibczOBJ , 10IimkkibczOBJ , 1Iimkkjijacz Jj 0, 1Iimkkjijjjjacczc其中