運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用

1、運(yùn) 籌 學(xué)( Operations Research )夫運(yùn)籌策帷幄之中，決勝于千里之外夫運(yùn)籌策帷幄之中，決勝于千里之外 史記史記 高祖本紀(jì)高祖本紀(jì)緒 論（1）運(yùn)籌學(xué)簡(jiǎn)述）運(yùn)籌學(xué)簡(jiǎn)述（2）運(yùn)籌學(xué)的主要內(nèi)容）運(yùn)籌學(xué)的主要內(nèi)容（3）本課程的主要學(xué)習(xí)內(nèi)容）本課程的主要學(xué)習(xí)內(nèi)容（4）運(yùn)籌學(xué)的應(yīng)用）運(yùn)籌學(xué)的應(yīng)用（5）本課程的教材及參考書）本課程的教材及參考書（6）本課程授課方式與考核）本課程授課方式與考核 本章主要內(nèi)容：本章主要內(nèi)容：一、古代樸素的運(yùn)籌學(xué)思想一、古代樸素的運(yùn)籌學(xué)思想國(guó)外國(guó)外英文原名英文原名 Operations Research 簡(jiǎn)稱簡(jiǎn)稱“O.R.”直譯為：運(yùn)用研究或作業(yè)研究直譯為：運(yùn)用

2、研究或作業(yè)研究正式出現(xiàn)于正式出現(xiàn)于19381938年年7 7月英國(guó)一份關(guān)于防空作戰(zhàn)系統(tǒng)運(yùn)月英國(guó)一份關(guān)于防空作戰(zhàn)系統(tǒng)運(yùn)行的研究報(bào)告中行的研究報(bào)告中中國(guó)古代運(yùn)籌學(xué)案例中國(guó)古代運(yùn)籌學(xué)案例二、運(yùn)籌學(xué)的起源二、運(yùn)籌學(xué)的起源（一）運(yùn)籌學(xué)簡(jiǎn)述（一）運(yùn)籌學(xué)簡(jiǎn)述運(yùn)作研究運(yùn)作研究(Operational Research)小組小組”:二戰(zhàn)期間解決復(fù)二戰(zhàn)期間解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍空襲如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍空襲對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)損失最少；損失最少；在各種情況下如何調(diào)整

3、反潛深水炸彈的爆炸深度，才能在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷力等。增加對(duì)德國(guó)潛艇的殺傷力等。-二戰(zhàn)后運(yùn)籌學(xué)的發(fā)展經(jīng)歷了三個(gè)階段二戰(zhàn)后運(yùn)籌學(xué)的發(fā)展經(jīng)歷了三個(gè)階段 （1 1）19451945年到年到2020世紀(jì)世紀(jì)5050年代初年代初創(chuàng)建時(shí)期創(chuàng)建時(shí)期 （2 2）20 20 世紀(jì)世紀(jì)5050年代初到年代初到2020世紀(jì)世紀(jì)5050年代末年代末成長(zhǎng)時(shí)期成長(zhǎng)時(shí)期 （3 3） 20 20 世紀(jì)世紀(jì)6060年代以來(lái)年代以來(lái)迅速發(fā)展和普及的時(shí)期迅速發(fā)展和普及的時(shí)期 國(guó)內(nèi)國(guó)內(nèi)19561956年成立第一個(gè)運(yùn)籌學(xué)小組年成立第一個(gè)運(yùn)籌學(xué)小組19571957年從年從“夫運(yùn)籌策帷幄之中

4、，決勝于千里之外夫運(yùn)籌策帷幄之中，決勝于千里之外”中中摘取摘取“運(yùn)籌運(yùn)籌”二字，將二字，將O.R.正式翻譯為正式翻譯為“運(yùn)籌學(xué)運(yùn)籌學(xué)”三、運(yùn)籌學(xué)的定義三、運(yùn)籌學(xué)的定義研究工具：數(shù)學(xué)，計(jì)算機(jī)科學(xué)及其他相關(guān)科學(xué)研究工具：數(shù)學(xué)，計(jì)算機(jī)科學(xué)及其他相關(guān)科學(xué)研究目的：對(duì)有限資源進(jìn)行合理規(guī)劃、使用，并提供研究目的：對(duì)有限資源進(jìn)行合理規(guī)劃、使用，并提供 優(yōu)化決策方案。優(yōu)化決策方案。研究對(duì)象：復(fù)雜系統(tǒng)的組織和管理研究對(duì)象：復(fù)雜系統(tǒng)的組織和管理參考參考大英百科全書大英百科全書、辭海辭海、中國(guó)企業(yè)管理百科全書中國(guó)企業(yè)管理百科全書等。等。四、運(yùn)籌學(xué)研究的基本特點(diǎn)四、運(yùn)籌學(xué)研究的基本特點(diǎn) 系統(tǒng)的整體優(yōu)化系統(tǒng)的整體優(yōu)化

5、多學(xué)科的配合多學(xué)科的配合 模型方法的應(yīng)用模型方法的應(yīng)用五、運(yùn)籌學(xué)研究的基本步驟五、運(yùn)籌學(xué)研究的基本步驟 分析與表述問(wèn)題分析與表述問(wèn)題 建立數(shù)學(xué)模型建立數(shù)學(xué)模型 對(duì)問(wèn)題求解對(duì)問(wèn)題求解 對(duì)模型和模型導(dǎo)出的解進(jìn)行檢驗(yàn)對(duì)模型和模型導(dǎo)出的解進(jìn)行檢驗(yàn) 建立對(duì)解的有效控制建立對(duì)解的有效控制 方案的實(shí)施方案的實(shí)施（二）運(yùn)籌學(xué)的主要內(nèi)容（二）運(yùn)籌學(xué)的主要內(nèi)容數(shù)學(xué)規(guī)劃（數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃等）動(dòng)態(tài)規(guī)劃等）圖論圖論存貯論存貯論排隊(duì)論排隊(duì)論對(duì)策論（博弈論）對(duì)策論（博弈論）決策論決策論（三）運(yùn)籌學(xué)的應(yīng)用（三）運(yùn)籌學(xué)的應(yīng)用 運(yùn)籌學(xué)方法運(yùn)籌學(xué)方法 應(yīng)用例應(yīng)用例 線性規(guī)

6、劃線性規(guī)劃 生產(chǎn)結(jié)構(gòu)優(yōu)化生產(chǎn)結(jié)構(gòu)優(yōu)化 非線性規(guī)劃非線性規(guī)劃 投資組合優(yōu)化投資組合優(yōu)化 整數(shù)規(guī)劃整數(shù)規(guī)劃 選址問(wèn)題選址問(wèn)題 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 資源分配問(wèn)題資源分配問(wèn)題 網(wǎng)絡(luò)分析網(wǎng)絡(luò)分析 工程計(jì)劃優(yōu)化工程計(jì)劃優(yōu)化 排隊(duì)論排隊(duì)論 服務(wù)系統(tǒng)優(yōu)化服務(wù)系統(tǒng)優(yōu)化 存貯論存貯論 訂貨庫(kù)存管理訂貨庫(kù)存管理 決策分析決策分析 機(jī)會(huì)選擇機(jī)會(huì)選擇 運(yùn)籌學(xué)的廣泛實(shí)際背景促使其不斷發(fā)展并運(yùn)籌學(xué)的廣泛實(shí)際背景促使其不斷發(fā)展并 在經(jīng)濟(jì)管理和系在經(jīng)濟(jì)管理和系統(tǒng)工程等多領(lǐng)域中發(fā)揮著令統(tǒng)工程等多領(lǐng)域中發(fā)揮著令 人矚目的重要作用。人矚目的重要作用。 諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)從諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)從1969年首發(fā)至今的年首發(fā)至今的57 位獲獎(jiǎng)?wù)咧芯陀?/p>

7、位獲獎(jiǎng)?wù)咧芯陀卸辔皇沁\(yùn)籌學(xué)家。多位是運(yùn)籌學(xué)家。 1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授給了庫(kù)普曼和康脫羅維年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授給了庫(kù)普曼和康脫羅維 奇，以表奇，以表彰首先將線性規(guī)劃與經(jīng)濟(jì)問(wèn)題相聯(lián)系而彰首先將線性規(guī)劃與經(jīng)濟(jì)問(wèn)題相聯(lián)系而 做出的貢獻(xiàn)；做出的貢獻(xiàn)； 1994年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授給了三位博弈論專家：年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授給了三位博弈論專家： 納什、澤爾納什、澤爾騰、海薩尼。博弈論已經(jīng)成為當(dāng)代經(jīng)騰、海薩尼。博弈論已經(jīng)成為當(dāng)代經(jīng) 濟(jì)學(xué)的基石。濟(jì)學(xué)的基石。 2005年以色列經(jīng)濟(jì)學(xué)家羅伯特年以色列經(jīng)濟(jì)學(xué)家羅伯特-奧曼和美國(guó)經(jīng)濟(jì)奧曼和美國(guó)經(jīng)濟(jì) 學(xué)家托馬學(xué)家托馬斯斯-斯切林，因斯切林，因“通過(guò)博弈論分析加強(qiáng)了通過(guò)博弈

8、論分析加強(qiáng)了 我們對(duì)沖突和合作的理我們對(duì)沖突和合作的理解解”所作出的貢獻(xiàn)而獲獎(jiǎng)。所作出的貢獻(xiàn)而獲獎(jiǎng)。 發(fā)表的部分獲獎(jiǎng)項(xiàng)目組織組織應(yīng)用應(yīng)用效果效果聯(lián)合航空公司聯(lián)合航空公司在滿足乘客需求的前提下，以最低在滿足乘客需求的前提下，以最低成本進(jìn)行訂票及機(jī)場(chǎng)工作班次安排成本進(jìn)行訂票及機(jī)場(chǎng)工作班次安排每年節(jié)約成本每年節(jié)約成本600600萬(wàn)美元萬(wàn)美元CitgoCitgo石油公司石油公司優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送和優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送和營(yíng)銷營(yíng)銷每年節(jié)約成本每年節(jié)約成本70007000萬(wàn)萬(wàn)AT&TAT&T優(yōu)化商業(yè)用戶的電話銷售中心選址優(yōu)化商業(yè)用戶的電話銷售中心選址每年節(jié)約成本每年節(jié)約成本4.064.06

9、億美億美元，銷售額大幅增加元，銷售額大幅增加標(biāo)準(zhǔn)品牌公司標(biāo)準(zhǔn)品牌公司控制成本庫(kù)存（制定最優(yōu)再定購(gòu)點(diǎn)控制成本庫(kù)存（制定最優(yōu)再定購(gòu)點(diǎn)和定購(gòu)量確保安全庫(kù)存）和定購(gòu)量確保安全庫(kù)存）每年節(jié)約成本每年節(jié)約成本380380萬(wàn)美元萬(wàn)美元法國(guó)國(guó)家鐵路公司法國(guó)國(guó)家鐵路公司制定最優(yōu)鐵路時(shí)刻表并調(diào)整鐵路日制定最優(yōu)鐵路時(shí)刻表并調(diào)整鐵路日運(yùn)營(yíng)量運(yùn)營(yíng)量每年節(jié)約成本每年節(jié)約成本15001500萬(wàn)美萬(wàn)美元，年收入大幅增加。元，年收入大幅增加。Taco BellTaco Bell優(yōu)化員工安排，以最低成本服務(wù)客優(yōu)化員工安排，以最低成本服務(wù)客戶戶每年節(jié)約成本每年節(jié)約成本13001300萬(wàn)美萬(wàn)美元元DeltaDelta航空公司航空公司

10、優(yōu)化配置上千個(gè)國(guó)內(nèi)航線航班來(lái)實(shí)優(yōu)化配置上千個(gè)國(guó)內(nèi)航線航班來(lái)實(shí)現(xiàn)利潤(rùn)最大化現(xiàn)利潤(rùn)最大化每年節(jié)約成本每年節(jié)約成本1 1億美元億美元（四）本課程的教材及參考書（四）本課程的教材及參考書選用教材選用教材 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用胡運(yùn)權(quán)主編胡運(yùn)權(quán)主編 （第五版）高等教（第五版）高等教育出版社育出版社參考教材參考教材運(yùn)籌學(xué)教程運(yùn)籌學(xué)教程胡運(yùn)權(quán)主編胡運(yùn)權(quán)主編 （第（第4 4版）清華出版社版）清華出版社管理運(yùn)籌學(xué)管理運(yùn)籌學(xué)韓伯棠主編韓伯棠主編 （第（第2 2版）高等教育出版版）高等教育出版社社運(yùn)籌學(xué)運(yùn)籌學(xué)( (修訂版修訂版) ) 錢頌迪主編錢頌迪主編 清華出版社清華出版社 （五）本課程的主要學(xué)習(xí)內(nèi)容（

11、五）本課程的主要學(xué)習(xí)內(nèi)容 第一章第一章 線性規(guī)劃及單純形法線性規(guī)劃及單純形法 第二章第二章 線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 第三章第三章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 第四章第四章 整數(shù)規(guī)劃與分配問(wèn)題整數(shù)規(guī)劃與分配問(wèn)題 （六）本課程授課方式與考核（六）本課程授課方式與考核學(xué)科總成績(jī)學(xué)科總成績(jī)平時(shí)成績(jī)平時(shí)成績(jī)（3030）課堂考勤課堂考勤（1212）平時(shí)作業(yè)平時(shí)作業(yè)（1818）期末成績(jī)期末成績(jī)（7070）講授為主，結(jié)合討論、習(xí)題作業(yè)講授為主，結(jié)合討論、習(xí)題作業(yè)第一章第一章 線性規(guī)劃及單純形法線性規(guī)劃及單純形法Linear Programming and Simplex Method線性規(guī)劃-發(fā)展簡(jiǎn)史法國(guó)

12、數(shù)學(xué)家J.-B.-J.傅里葉和C.瓦萊普森分別于1832和1911年獨(dú)立地提出線性規(guī)劃的想法，但未引起注意。1939年蘇聯(lián)數(shù)學(xué)家年蘇聯(lián)數(shù)學(xué)家.康托羅維奇康托羅維奇在生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一書中提出線性規(guī)劃問(wèn)題，也未引起重視。1947年美國(guó)數(shù)學(xué)家年美國(guó)數(shù)學(xué)家G.B.丹齊克丹齊克提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問(wèn)題的通用方法單純形法單純形法，為這門學(xué)科奠定了基礎(chǔ)。1947年美國(guó)數(shù)學(xué)家年美國(guó)數(shù)學(xué)家J.von諾伊曼提出對(duì)諾伊曼提出對(duì)偶理論偶理論,開(kāi)創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。1951年美國(guó)經(jīng)濟(jì)學(xué)家年美國(guó)經(jīng)濟(jì)學(xué)家T.C.庫(kù)普曼斯庫(kù)普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)

13、域把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年年C.萊姆基提出對(duì)偶單純形法萊姆基提出對(duì)偶單純形法，1954年年S.加斯和加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問(wèn)題，和參數(shù)規(guī)劃問(wèn)題，1956年年A.塔克提出互補(bǔ)松弛定理，塔克提出互補(bǔ)松弛定理，1960年年G.B.丹齊克和丹齊克和P.沃爾夫提出分解算法沃爾夫提出分解算法等。線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問(wèn)題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出

14、現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個(gè)變量的線性規(guī)劃問(wèn)題。1979年蘇聯(lián)數(shù)學(xué)家年蘇聯(lián)數(shù)學(xué)家.哈奇揚(yáng)提出解線性規(guī)劃問(wèn)題的橢球哈奇揚(yáng)提出解線性規(guī)劃問(wèn)題的橢球算法算法，并證明它是多項(xiàng)式時(shí)間算法。1984年年美國(guó)貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問(wèn)題的新卡馬卡提出解線性規(guī)劃問(wèn)題的新的多項(xiàng)式時(shí)間算法的多項(xiàng)式時(shí)間算法-內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法。用這種方法求解線性規(guī)劃問(wèn)題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用時(shí)間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。1.1939年，前蘇聯(lián)科學(xué)家康托洛維奇年，前蘇聯(lián)科學(xué)家康托洛

15、維奇-生產(chǎn)組織與管理中的數(shù)學(xué)方法生產(chǎn)組織與管理中的數(shù)學(xué)方法是線性是線性規(guī)劃應(yīng)用于工業(yè)生產(chǎn)問(wèn)題的開(kāi)山之作規(guī)劃應(yīng)用于工業(yè)生產(chǎn)問(wèn)題的開(kāi)山之作；(LEONIDVITALIYEVICHKANTOROV(1912-1986) 2. 1947年，美國(guó)數(shù)學(xué)家喬治年，美國(guó)數(shù)學(xué)家喬治伯納德伯納德丹齊格丹齊格-單純形法，被稱為單純形法，被稱為線性規(guī)劃之父。線性規(guī)劃之父。GeorgeBernardDantzig(19142005) 丹齊格在丹齊格在1946年獲伯克利大學(xué)的博士學(xué)位。年獲伯克利大學(xué)的博士學(xué)位。1947年，年，33歲提出了解決一種最優(yōu)化問(wèn)題的單純形法歲提出了解決一種最優(yōu)化問(wèn)題的單純形法,該方法奠定了線性規(guī)

16、該方法奠定了線性規(guī)劃的基礎(chǔ)，使得經(jīng)濟(jì)學(xué)、環(huán)境科學(xué)、統(tǒng)計(jì)學(xué)應(yīng)用等學(xué)科獲得了劃的基礎(chǔ)，使得經(jīng)濟(jì)學(xué)、環(huán)境科學(xué)、統(tǒng)計(jì)學(xué)應(yīng)用等學(xué)科獲得了迅速發(fā)展。迅速發(fā)展。Dantzig也因而被譽(yù)為也因而被譽(yù)為“線性規(guī)劃之父線性規(guī)劃之父”。 1952年他年他在蘭德公司任研究數(shù)學(xué)家，在公司電腦上實(shí)行線性規(guī)劃。在蘭德公司任研究數(shù)學(xué)家，在公司電腦上實(shí)行線性規(guī)劃。1960年他被母校聘任教授計(jì)算機(jī)科學(xué)，終于當(dāng)上運(yùn)籌學(xué)中心主任。年他被母校聘任教授計(jì)算機(jī)科學(xué)，終于當(dāng)上運(yùn)籌學(xué)中心主任。1966年他在史丹福大學(xué)當(dāng)類似職位，留在那里直到年他在史丹福大學(xué)當(dāng)類似職位，留在那里直到1990年代年代退休。退休。Dantzig在運(yùn)籌學(xué)建樹(shù)極高，獲得

17、了包括在運(yùn)籌學(xué)建樹(shù)極高，獲得了包括“馮諾伊曼理論獎(jiǎng)馮諾伊曼理論獎(jiǎng)”在內(nèi)的諸多獎(jiǎng)項(xiàng)。他在在內(nèi)的諸多獎(jiǎng)項(xiàng)。他在Linear programming andextensions一一書中研究了線性編程模型，為計(jì)算機(jī)語(yǔ)言的發(fā)展做出了不可磨書中研究了線性編程模型，為計(jì)算機(jī)語(yǔ)言的發(fā)展做出了不可磨滅的貢獻(xiàn)。他除了線性規(guī)劃和單純形法的杰出工作，還推進(jìn)很滅的貢獻(xiàn)。他除了線性規(guī)劃和單純形法的杰出工作，還推進(jìn)很多領(lǐng)域的發(fā)展，有分解論、靈敏度分析、互補(bǔ)主元法、大系統(tǒng)多領(lǐng)域的發(fā)展，有分解論、靈敏度分析、互補(bǔ)主元法、大系統(tǒng)最優(yōu)化、非線性規(guī)劃和不確定規(guī)劃。最優(yōu)化、非線性規(guī)劃和不確定規(guī)劃。SIAM Journal on Opt

18、imization1991年創(chuàng)刊號(hào)是獻(xiàn)給他的。年創(chuàng)刊號(hào)是獻(xiàn)給他的。Mathematical Programming Society為表彰丹齊格，設(shè)立丹齊格獎(jiǎng)，為表彰丹齊格，設(shè)立丹齊格獎(jiǎng)，1982年起每三年頒給年起每三年頒給一至兩位在數(shù)學(xué)規(guī)劃有突出貢獻(xiàn)的人。一至兩位在數(shù)學(xué)規(guī)劃有突出貢獻(xiàn)的人。xa 2 2xxaV此為無(wú)約束的極值問(wèn)題此為無(wú)約束的極值問(wèn)題6 ax 有0 dxdV由1.1 一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1-1 1-1 問(wèn)題的提出問(wèn)題的提出例例1 1 用一塊邊長(zhǎng)為用一塊邊長(zhǎng)為a的正方形鐵皮做一個(gè)無(wú)蓋長(zhǎng)方體容的正方形鐵皮做一個(gè)無(wú)蓋長(zhǎng)方體容器，應(yīng)如何裁剪可使做成的容器的

19、容積最大？器，應(yīng)如何裁剪可使做成的容器的容積最大？)20(ax 解：如圖設(shè)四個(gè)角上減去的小正方形邊解：如圖設(shè)四個(gè)角上減去的小正方形邊長(zhǎng)為長(zhǎng)為x，則容器體積為：，則容器體積為：時(shí)，容積最大時(shí)，容積最大 例例2 2 常山機(jī)器廠生產(chǎn)常山機(jī)器廠生產(chǎn) I I、IIII 兩型產(chǎn)品。這兩型兩型產(chǎn)品。這兩型產(chǎn)品都分別要在產(chǎn)品都分別要在A A、B B、C C三種不同設(shè)備上加工。按三種不同設(shè)備上加工。按工藝規(guī)定，生產(chǎn)每件產(chǎn)品的單位利潤(rùn)、消耗三種工藝規(guī)定，生產(chǎn)每件產(chǎn)品的單位利潤(rùn)、消耗三種設(shè)備的工時(shí)以及各種設(shè)備工時(shí)的限額如下表：設(shè)備的工時(shí)以及各種設(shè)備工時(shí)的限額如下表： 單位產(chǎn)品消耗設(shè)單位產(chǎn)品消耗設(shè)備工時(shí)備工時(shí)I II

20、III設(shè)備工時(shí)限量設(shè)備工時(shí)限量（小時(shí)）（小時(shí)） 設(shè)備設(shè)備A A設(shè)備設(shè)備B B設(shè)備設(shè)備C C2 24 40 02 20 05 5121216161515單位利潤(rùn)（元）單位利潤(rùn)（元）2 23 3解：設(shè)計(jì)劃期內(nèi)兩種產(chǎn)品的數(shù)量分別為解：設(shè)計(jì)劃期內(nèi)兩種產(chǎn)品的數(shù)量分別為x x1 1，x x2 2，則總利潤(rùn)為：，則總利潤(rùn)為：maxz=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0， x2 0簡(jiǎn)記為：簡(jiǎn)記為： s.t.（約束于：）（約束于：）z=2 x1+3 x2在滿足限制條件下求在滿足限制條件下求z的最大值。的最大值。此為有約束極值問(wèn)題此為有約束極值問(wèn)題1-2 1-2 線性

21、規(guī)劃問(wèn)題的數(shù)學(xué)模型線性規(guī)劃問(wèn)題的數(shù)學(xué)模型原型原型模型模型數(shù)學(xué)模型數(shù)學(xué)模型提煉提煉數(shù)學(xué)工具數(shù)學(xué)工具1 1、原型原型：現(xiàn)實(shí)世界中人們關(guān)心、研究的實(shí)際對(duì)象。：現(xiàn)實(shí)世界中人們關(guān)心、研究的實(shí)際對(duì)象。 模型模型：將某一部分信息簡(jiǎn)縮、提煉而構(gòu)造的原型替代物。：將某一部分信息簡(jiǎn)縮、提煉而構(gòu)造的原型替代物。 數(shù)學(xué)模型數(shù)學(xué)模型：對(duì)現(xiàn)實(shí)世界的一個(gè)特定對(duì)象，為達(dá)到一定目的，：對(duì)現(xiàn)實(shí)世界的一個(gè)特定對(duì)象，為達(dá)到一定目的，根據(jù)內(nèi)在規(guī)律做出必要的簡(jiǎn)化假設(shè)根據(jù)內(nèi)在規(guī)律做出必要的簡(jiǎn)化假設(shè), ,并運(yùn)用適當(dāng)數(shù)學(xué)工具得到并運(yùn)用適當(dāng)數(shù)學(xué)工具得到的一個(gè)數(shù)學(xué)結(jié)構(gòu)。的一個(gè)數(shù)學(xué)結(jié)構(gòu)。3 3、規(guī)劃問(wèn)題數(shù)學(xué)模型的三要素、規(guī)劃問(wèn)題數(shù)學(xué)模型的三要素（2

22、 2）目標(biāo)函數(shù)目標(biāo)函數(shù)：?jiǎn)栴}要達(dá)到的目標(biāo)要求，表示為決策變量的：?jiǎn)栴}要達(dá)到的目標(biāo)要求，表示為決策變量的函數(shù)。用函數(shù)。用 z= =f( (x1 1，x2 2，xn n) )表示。表示。（1 1）決策變量決策變量：決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，：決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，是問(wèn)題中要確定的未知量。用是問(wèn)題中要確定的未知量。用x1 1，x2 2，xn n表示。表示。（3 3）約束條件約束條件：決策變量取值時(shí)受到的各種可用資源的限制，：決策變量取值時(shí)受到的各種可用資源的限制，表示為含決策變量的等式或不等式。表示為含決策變量的等式或不等式。2 2、規(guī)劃問(wèn)題、規(guī)劃問(wèn)題即求目標(biāo)函數(shù)在若干約

23、束條件下的最值。即求目標(biāo)函數(shù)在若干約束條件下的最值。4 4、線性規(guī)劃問(wèn)題（、線性規(guī)劃問(wèn)題（Linear ProgrammingLinear Programming）的數(shù)學(xué)模型）的數(shù)學(xué)模型（2 2）一般形式一般形式：（1 1）條件條件：決策變量為可控的連續(xù)變量，目標(biāo)函數(shù)和約束條：決策變量為可控的連續(xù)變量，目標(biāo)函數(shù)和約束條件都是線性的。簡(jiǎn)記為件都是線性的。簡(jiǎn)記為“L.P.” max (或或 min) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn （=，）b1 a21x1+a22x2+a2nxn （=，） b2 am1x1+am2x2+amnxn（=，） bm x1

24、 , x2, , xn0（3 3）其他形式其他形式：連加形式連加形式11max (min) z=( , ) (1,2,). . 0 (1,2, )njjjnijjijjc xa xbimstxjn 向量形式向量形式1max (min) z=( , ) . . 0 njjjCXP xbstX 12( ,)nCc cc12nxxXx12jjjmjaaPa其中 稱為價(jià)值行向量?jī)r(jià)值行向量；決策列向量決策列向量12mbbbb系數(shù)列向量系數(shù)列向量右端列向量右端列向量矩陣形式矩陣形式max (min) z=( , ) . . 0 CXAXbstX 12( ,)nCc cc12nxxXx11121212221

25、21 2 ,nnnmmmnaaaaaaAP PPaaa其中 稱為價(jià)值行向量；稱為價(jià)值行向量；決策列向量決策列向量12mbbbb右端列向量右端列向量約束矩陣或系數(shù)矩陣約束矩陣或系數(shù)矩陣1-3 1-3 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1 1、標(biāo)準(zhǔn)形式、標(biāo)準(zhǔn)形式11max z= (1,2,). . 0 (1,2, ) 0(1,2,)njjjnijjijjic xa xbimstxjnbimmax z= . . 0 0CXAXbstXb或或2 2、條件、條件目標(biāo)函數(shù)求極大值目標(biāo)函數(shù)求極大值約束條件全是等式（線性方程組）約束條件全是等式（線性方程組）決策變量全非負(fù)決策變量全非負(fù)右端常數(shù)全非負(fù)

26、右端常數(shù)全非負(fù)3 3、標(biāo)準(zhǔn)化方法、標(biāo)準(zhǔn)化方法1min z=njjjc xzz （1）若目標(biāo)函數(shù)求極小值，即）若目標(biāo)函數(shù)求極小值，即則令則令 轉(zhuǎn)化為轉(zhuǎn)化為11max z = -z = -()nnjjjjjjc xcx（2 2）若約束條件為不等式，）若約束條件為不等式，則依次引入松弛變量或剩余變量（統(tǒng)稱為松弛變量），則依次引入松弛變量或剩余變量（統(tǒng)稱為松弛變量），轉(zhuǎn)化為等式約束條件。轉(zhuǎn)化為等式約束條件。注意注意：松弛變量在目標(biāo)函數(shù)中系數(shù)全為：松弛變量在目標(biāo)函數(shù)中系數(shù)全為0。約束為約束為不等式，減去松弛變量，化為等式約束條件；不等式，減去松弛變量，化為等式約束條件；約束為約束為不等式，加上松弛變量，

27、化為等式約束條件。不等式，加上松弛變量，化為等式約束條件。多退少補(bǔ)多退少補(bǔ)例：例：max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0， x2 0 s.t.12345123142512345max 2300022 124 16 s.t. 5 15, , , , 0zxxxxxxxxxxxxxxxxx標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化0jjxx， 0jjjxxx 且jjjxxx（3 3）若決策變量）若決策變量xj0，則令，則令（4 4）若決策變量）若決策變量xj取值無(wú)限制，則令取值無(wú)限制，則令（5 5）若約束等式的右端常數(shù)）若約束等式的右端常數(shù)bi 0 0，則等式兩邊同時(shí)乘以，

28、則等式兩邊同時(shí)乘以“-1-1”。其中其中（“一分為二一分為二”）例：例：將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式。將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式。123123123123123min2329324. .32360, 0, zxxxxxxxxxstxxxxxx 取值無(wú)限制11133333 (0) (0, 0)zzxxxxxxxx 解：令12334512334123351233123345max 233002 9322 4 s.t. 3233 6, , , , 0zxxxxxxxxxxxxxxxxxxxxxxxxxx 則問(wèn)題化為標(biāo)準(zhǔn)形式：則問(wèn)題化為標(biāo)準(zhǔn)形式：并引入松弛變量并引入松弛變量x4, x5,課堂練習(xí)

29、：將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式123123123123123m in235 7 42325,0, Zxxxxxxxxxxxxxxx 無(wú) 約 束線性規(guī)劃問(wèn)題的數(shù)學(xué)模型12334512334123351233123345max23()005() 7 () 252() 5,0 Zxxxxxxxxxxxxxxxxxxxxx xxxxx標(biāo)準(zhǔn)形式如下：1-4 1-4 線性規(guī)劃問(wèn)題的解線性規(guī)劃問(wèn)題的解12max z= (1) (2). . 0 (3) 0,nCXAXbstXbAP PP其中（）11max z= (1) (1,2,) (2). . 0 (1,2, ) (3) 0(1,2,)njjjnijji

30、jjic xa xbimstxjnbim已知線性規(guī)劃的標(biāo)準(zhǔn)形式：已知線性規(guī)劃的標(biāo)準(zhǔn)形式：或或1 1、求解線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題：從滿足（從滿足（2）、（）、（3）的方程組中找出一個(gè)解使目標(biāo)函）的方程組中找出一個(gè)解使目標(biāo)函數(shù)（數(shù)（1）達(dá)到最大值。）達(dá)到最大值。2 2、可行解可行解：所有可行解的集合。所有可行解的集合。12nxxXx可行域可行域：滿足約束條件（滿足約束條件（2）、（）、（3）的解。）的解。記做記做最優(yōu)解最優(yōu)解： 使目標(biāo)函數(shù)達(dá)到最大值的可行解。使目標(biāo)函數(shù)達(dá)到最大值的可行解。（1 1）基基：設(shè)：設(shè)A A為線性規(guī)劃問(wèn)題約束條件的為線性規(guī)劃問(wèn)題約束條件的 m n 系數(shù)矩陣系數(shù)矩陣（m

31、00，有如下結(jié)論：有如下結(jié)論：(1) (1) 若對(duì)所有若對(duì)所有jm+1，有，有 j 0 0 ，則，則z（1） z （0） ，即，即z （0）為為最優(yōu)函數(shù)值，最優(yōu)函數(shù)值，X（0）為為唯一最優(yōu)解唯一最優(yōu)解；(2) (2) 若對(duì)所有若對(duì)所有j m+1 ，有有 j 0，且，且存在某個(gè)非基變量的檢驗(yàn)數(shù)存在某個(gè)非基變量的檢驗(yàn)數(shù) k=0，則將，則將Pk作為新的基向量得出新的基可行解作為新的基向量得出新的基可行解X（1 1） ，滿足，滿足z（1） = z （0） ，故，故z（1） 也也為最優(yōu)函數(shù)值，從而為最優(yōu)函數(shù)值，從而 X（1）也也為最優(yōu)解，為最優(yōu)解， X（0） 、X（1） 連線上所有點(diǎn)均為最優(yōu)解，因此該線

32、性規(guī)劃連線上所有點(diǎn)均為最優(yōu)解，因此該線性規(guī)劃模型具有模型具有無(wú)窮多最優(yōu)解無(wú)窮多最優(yōu)解；(3) (3) 若存在某個(gè)若存在某個(gè) j 0 0，但對(duì)應(yīng)的第，但對(duì)應(yīng)的第j列系數(shù)全非正，即列系數(shù)全非正，即aij 0 0，則，則當(dāng)當(dāng) + + 時(shí)，有時(shí)，有z（1） + + ， 該線性規(guī)劃模型具有該線性規(guī)劃模型具有無(wú)界解無(wú)界解。(1)(0)jzz1.4 1.4 單純形法的計(jì)算步驟單純形法的計(jì)算步驟1 1、前提：標(biāo)準(zhǔn)化的線性規(guī)劃問(wèn)題的系數(shù)矩陣含有單位子矩陣。、前提：標(biāo)準(zhǔn)化的線性規(guī)劃問(wèn)題的系數(shù)矩陣含有單位子矩陣。m n max z= s.t. 0 0CXAXbXb已知12(0)00mbbXb不妨假設(shè)不妨假設(shè)A中前中

33、前m列對(duì)應(yīng)的子矩陣是單位列對(duì)應(yīng)的子矩陣是單位矩陣，取其為基矩陣，取其為基B，得到初始基可行解，得到初始基可行解m+3行行n+4列列第第1行：價(jià)值行行：價(jià)值行 cj第第2行：變量行行：變量行 xj最后一最后一行：檢驗(yàn)數(shù)行行：檢驗(yàn)數(shù)行 j第第1列：基價(jià)值列列：基價(jià)值列 CB第第2列列：基變量列：基變量列 XB第第3列列：基解列：基解列 b最后一最后一列：列：比值比值列列 主體：系數(shù)矩陣主體：系數(shù)矩陣Amn2 2、單純形表的結(jié)構(gòu)、單純形表的結(jié)構(gòu)jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11m 1mnmmnmaaaa1,11, 110010 0miijijjacc1

34、jjjzc min0iijiijbaa3 3、初始單純形表：含初始基可行解的單純形表、初始單純形表：含初始基可行解的單純形表 最優(yōu)單純形表：含最優(yōu)解的單純形表最優(yōu)單純形表：含最優(yōu)解的單純形表4 4、單純形法（、單純形法（ ）：）： 利用單純形表求解線性規(guī)劃問(wèn)題的方法。利用單純形表求解線性規(guī)劃問(wèn)題的方法。5 5、單純形法的計(jì)算步驟、單純形法的計(jì)算步驟(1) (1) 化化 L.P.問(wèn)題為標(biāo)準(zhǔn)形式問(wèn)題為標(biāo)準(zhǔn)形式, ,建立初始單純形表；建立初始單純形表；（簡(jiǎn)稱換入變量）；的變量做為換入基所對(duì)應(yīng)的變量選取，令否則，則已經(jīng)得到最優(yōu)解，若所有檢驗(yàn)數(shù) 0|max 0 (2)BkkjjkjXx（簡(jiǎn)稱換出變量）；

35、的變量做為換出基所對(duì)應(yīng)的變量選取BlXxmin0iijiijbaa(3) (3) 計(jì)算計(jì)算 以以alk為主元素為主元素( (簡(jiǎn)稱主元，用簡(jiǎn)稱主元，用 表示表示) )，進(jìn)行線性方程組，進(jìn)行線性方程組 的的初等行變換，將主元列初等行變換，將主元列Pk化為單位向量得到新的單純形表，化為單位向量得到新的單純形表，轉(zhuǎn)入轉(zhuǎn)入(2)(2)。（最大正檢驗(yàn)數(shù)決定換入變量）（最大正檢驗(yàn)數(shù)決定換入變量）（最小比值（最小比值決定換出變量決定換出變量）例例1：用單純形法求解下列線性規(guī)劃問(wèn)題：用單純形法求解下列線性規(guī)劃問(wèn)題.max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0， x

36、2 0 s.t.12345123142512345max 2300022 124 16 s.t. 5 15, , , , 0zxxxxxxxxxxxxxxxxx解：先標(biāo)準(zhǔn)化解：先標(biāo)準(zhǔn)化Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 j 再列初始單純形表：再列初始單純形表：6-32 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 1615 2 2 1 0 0 6 4 0 0 1 0 - 0 5

37、 0 0 1 3 2 3 0 0 0 j 以以55為主元進(jìn)為主元進(jìn)行初等行變換行初等行變換Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X2 6 16 3 2 0 1 0 -2/5 3 4 0 0 1 0 4 0 1 0 0 1/5 - 2 0 0 0 -3/5x1 1為換入變量為換入變量 下面開(kāi)始單純形法迭代：下面開(kāi)始單純形法迭代：x5 5為換出變量為換出變量x2 2為換入變量為換入變量以以22為主元進(jìn)為主元進(jìn)行初等行變換行初等行變換x3 3為換出變量為換出變量主元化為主元化為1，主元列，主元列的其他元素化為的其他元素化為0Cj 2 3 0

38、0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5j 此時(shí)得到唯一最優(yōu)解此時(shí)得到唯一最優(yōu)解X*=(3,3)T, , Zmax=15=15。例例2 2 用單純形法求解下列線性規(guī)劃問(wèn)題用單純形法求解下列線性規(guī)劃問(wèn)題 0,24261553 s.t.2max21212121xxxxxxxxz 0,24 2615 53 s.t.2 max432142132121xxxxxxxxxxxxz解：先標(biāo)準(zhǔn)化解：先標(biāo)準(zhǔn)化 2 1 0 0 54 x3x400 x1 x2 x

39、3 x4bxBcB 2 1 0 0cj 2415351 06201j 0 0 x3x102 x1 x2 x3 x4bxBcB 2 1 0 0cj430141 0j1/3-1/21/61/3-1/33/412 0 0 -1/12 -7/24 x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cj15/43/4011/4-1/810 -1/125/24j唯一最優(yōu)解12max15333, , 444xxz6、單純形法中存在的問(wèn)題、單純形法中存在的問(wèn)題（1 1） 存在兩個(gè)以上的最大正檢驗(yàn)數(shù)。存在兩個(gè)以上的最大正檢驗(yàn)數(shù)。任取一個(gè)最大正檢驗(yàn)數(shù)對(duì)應(yīng)的變量作為換入變量。任取一個(gè)最大正檢驗(yàn)數(shù)對(duì)應(yīng)的變

40、量作為換入變量。（2 2） 出現(xiàn)兩個(gè)以上相同的最小值。出現(xiàn)兩個(gè)以上相同的最小值。任取一個(gè)最小任取一個(gè)最小對(duì)應(yīng)的變量作為換出變量。對(duì)應(yīng)的變量作為換出變量。此時(shí)此時(shí)L.P.問(wèn)題出現(xiàn)退化現(xiàn)象。問(wèn)題出現(xiàn)退化現(xiàn)象。12121212max24312s.t. 48,0zxxxxxxx x練習(xí)：練習(xí)：5-1 5-1 人工變量法（大人工變量法（大M法）法）1.5 單純形法的進(jìn)一步討論 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基并不含有單位矩陣，為

41、了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大量，構(gòu)成的可行基稱為人工基，用大MM法或兩階法或兩階段法求解，這種用人工變量作橋梁的求解方法稱段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。為人工變量法。12121212min23 3s.t. 24,0zxxxxxxx x例例1：用單純形法求解下列線性規(guī)劃問(wèn)題。：用單純形法求解下列線性規(guī)劃問(wèn)題。12312312123max230 3s.t. 2 4 ,0zxxx

42、xxxxxx x x 解：先標(biāo)準(zhǔn)化為解：先標(biāo)準(zhǔn)化為系數(shù)矩陣系數(shù)矩陣1231 1 1=(P,P ,P ) 1 2 0A4510P = ,P = 01 123451 1 1 1 0=(P,P ,P ,P ,P ) 1 2 0 0 1A1234125 32 40 (1,2,5)jxxxxxxxxj但是但是A中沒(méi)有單位矩陣，在中沒(méi)有單位矩陣，在A中人為的增加兩列中人為的增加兩列此時(shí)對(duì)應(yīng)的約束方程組為對(duì)應(yīng)的約束方程組為：該問(wèn)題新增加了兩個(gè)變量：x4, x5（稱為人工變量）（稱為人工變量）A有單位子矩陣，選擇這個(gè)單位矩陣作為基（稱為人工基）。有單位子矩陣，選擇這個(gè)單位矩陣作為基（稱為人工基）。為使 123

43、12123 32 4 ,0 xxxxxx x x1234125 32 40 (1,2,5)jxxxxxxxxj 必須保證在可行解中人工變量必須保證在可行解中人工變量x4=x5=0，故令故令x4，x5在目標(biāo)函數(shù)中的系數(shù)為在目標(biāo)函數(shù)中的系數(shù)為M （其中（其中M表示任意大的正數(shù)），表示任意大的正數(shù)），這種添加人工變量求解這種添加人工變量求解LP的方法稱為的方法稱為人工變量法人工變量法,計(jì)算過(guò)程中出現(xiàn)了計(jì)算過(guò)程中出現(xiàn)了M，這種方法也稱為，這種方法也稱為大大M法法。等價(jià)于于是，這個(gè)線性規(guī)劃問(wèn)題轉(zhuǎn)化為：于是，這個(gè)線性規(guī)劃問(wèn)題轉(zhuǎn)化為：123451234125max230 3s.t. 2 4 0 (1,2,5

44、)jzxxxMxMxxxxxxxxxj 以下可用單純形法繼續(xù)求解。以下可用單純形法繼續(xù)求解。Cj x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1 -2 -3 0 -M -M34x4 x5-M -Mcj - zj -2+2M-3+3M-M03/1=34/2= 21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj - zj -1/2+M/2 0 -M 0 3/2-3M/2-M -3241 0 -2 2 -1 0 1 1 -1 1x1 x221cj - zj 0 0 -1 1-M 1-M-2 -3x50唯一最優(yōu)解12max2, 1, 7xxz 故 zmi

45、n=7注意：此時(shí)人工變量x4=x5=0說(shuō)明：說(shuō)明： 若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工變量的人工變量 ，則該模，則該模型型無(wú)可行解無(wú)可行解。 采用大采用大M法求解線性規(guī)劃模型時(shí)，如果模型中法求解線性規(guī)劃模型時(shí)，如果模型中各個(gè)系數(shù)與各個(gè)系數(shù)與M的值非常接近或相差很大，若用手工計(jì)算的值非常接近或相差很大，若用手工計(jì)算不會(huì)出現(xiàn)問(wèn)題。但是若利用計(jì)算機(jī)求解，則容易引起混不會(huì)出現(xiàn)問(wèn)題。但是若利用計(jì)算機(jī)求解，則容易引起混淆，使得機(jī)器判斷出錯(cuò)，從而使大淆，使得機(jī)器判斷出錯(cuò)，從而使大M法失效。法失效。 在這種情況下，可采用下面的兩階段法進(jìn)行計(jì)算。在這種情況下，可采用下面的兩階段法

46、進(jìn)行計(jì)算。5-2 5-2 兩階段法兩階段法( (將將L.P.問(wèn)題分成兩個(gè)階段來(lái)考慮問(wèn)題分成兩個(gè)階段來(lái)考慮) ) 第一階段第一階段: : 判斷原判斷原L.P.L.P.問(wèn)題是否存在可行解。問(wèn)題是否存在可行解。 給原給原L.P.L.P.問(wèn)題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)問(wèn)題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)函數(shù)w（人工變量在人工變量在w中的系數(shù)一般取為中的系數(shù)一般取為1 1）并求）并求w的最小值；的最小值；然后用單純形法求解。若求得然后用單純形法求解。若求得wmin=0=0，則該問(wèn)題有可行解，進(jìn)，則該問(wèn)題有可行解，進(jìn)入第二階段，否則該問(wèn)題無(wú)可行解，結(jié)束。入第二階段，否則該問(wèn)題無(wú)可行解

47、，結(jié)束。 第二階段：將第第二階段：將第一一階段得到的最終表去掉人工變量，并階段得到的最終表去掉人工變量，并將目標(biāo)函數(shù)還原為原將目標(biāo)函數(shù)還原為原L.P.問(wèn)題的目標(biāo)函數(shù)（即修改最終表中問(wèn)題的目標(biāo)函數(shù)（即修改最終表中的第一行和第一列），以此作為第二階段的初始表，繼續(xù)的第一行和第一列），以此作為第二階段的初始表，繼續(xù)用單純形法求解。用單純形法求解。例：用兩階段法求解下列線性規(guī)劃問(wèn)題。例：用兩階段法求解下列線性規(guī)劃問(wèn)題。12121212min23 3s.t. 24,0zxxxxxxx x12312312123max230 3s.t. 2 4 ,0zxxxxxxxxx x x 標(biāo)準(zhǔn)化引入人工變量12345

48、1234125max230 3s.t. 2 4 0 (1,2,5)jzxxxMxMxxxxxxxxxj z451234125min 3s.t. 2 40 (1,2,5)jwxxxxxxxxxxj451234125max 3s.t. 2 40 (1,2,5)jwxxxxxxxxxxj (1) (1) 第一階段，構(gòu)造判斷是否存在可行解的模型：第一階段，構(gòu)造判斷是否存在可行解的模型： 用單純形法求解這個(gè)問(wèn)題，先標(biāo)準(zhǔn)化為；用單純形法求解這個(gè)問(wèn)題，先標(biāo)準(zhǔn)化為；Cj x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1 0 0 0 -1 -134x4 x5-1 -1cj - zj 2 3-1

49、03/1=34/2= 21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj - zj 1/2 0 -1 0 -3/2-1 0241 0 -2 2 -1 0 1 1 -1 1x1 x221cj - zj 0 0 0 -1 -10 0 x50最優(yōu)解12maxmin2, 1, 00 xxww，即本問(wèn)題有可行解，進(jìn)入第二階段 (2) (2) 第二階段第二階段 先在第一階段的最終單純形表去掉人工變量，再還原原先在第一階段的最終單純形表去掉人工變量，再還原原目標(biāo)函數(shù)，即目標(biāo)函數(shù)，即 max z=-2=-2x1 1-3-3x2 2+0+0 x3 3，繼續(xù)迭代：繼續(xù)迭代：Cj x1x

50、2x3XBbCB1 0 -2 0 1 1 -2 -3 0 21x1 x2-2 -3cj - zj 0 0-1唯一最優(yōu)解12max2, 1, 7xxz 故 zmin=7注意：兩階段法中不再出現(xiàn)大M，但需要解兩個(gè)線性規(guī)劃問(wèn)題，要注意目標(biāo)函數(shù)系數(shù)的變化。5-3 關(guān)于解的判別例例7 用單純形法解下列線性規(guī)劃用單純形法解下列線性規(guī)劃無(wú)窮多解當(dāng)所有的當(dāng)所有的 ，但某一非基變量檢驗(yàn)數(shù)，但某一非基變量檢驗(yàn)數(shù) ，存，存在無(wú)窮多最優(yōu)解的條件是在無(wú)窮多最優(yōu)解的條件是Ps列向量中至少存在一個(gè)元列向量中至少存在一個(gè)元素素 ，且能找出最優(yōu)解，且能找出最優(yōu)解.12121212max332212416. .515,0zxxx

51、xxstxx xmax z 12121212max332212416s.t. 515,0zxxxxxxxx例例8 用單純形法解下列線性規(guī)劃用單純形法解下列線性規(guī)劃無(wú)界解無(wú)界解 若存在某個(gè)若存在某個(gè) j 0 0，但對(duì)應(yīng)的第，但對(duì)應(yīng)的第j列系數(shù)全非正，即列系數(shù)全非正，即aij 0 0，則問(wèn)題的解無(wú)界，則問(wèn)題的解無(wú)界. .12112max23416s.t. ,0zxxxxx例例9 用單純形法解下列線性規(guī)劃用單純形法解下列線性規(guī)劃12121212max232212s.t. 214,0zxxxxxxx x無(wú)可行解無(wú)可行解若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工變量的人工變量 ，

52、則該模，則該模型無(wú)可行解。型無(wú)可行解。12121212max232212s.t. 214 ,0zxxxxxxxx用最終單純形表判斷線性規(guī)劃問(wèn)題解的類型：用最終單純形表判斷線性規(guī)劃問(wèn)題解的類型：解的類型解的類型最終表的特征最終表的特征無(wú)可行解無(wú)可行解有非有非0 0的人工變量的人工變量有有可可行行解解唯一最優(yōu)解唯一最優(yōu)解無(wú)無(wú)非非0 0的人的人工變量，非基變量的檢驗(yàn)工變量，非基變量的檢驗(yàn)數(shù)全為負(fù)數(shù)數(shù)全為負(fù)數(shù)無(wú)窮多最優(yōu)解無(wú)窮多最優(yōu)解無(wú)非無(wú)非0 0的人工的人工變量，非基變量的檢驗(yàn)變量，非基變量的檢驗(yàn)數(shù)全非正，且有某個(gè)非基變量的檢驗(yàn)數(shù)全非正，且有某個(gè)非基變量的檢驗(yàn)數(shù)為數(shù)為0 0無(wú)界解無(wú)界解無(wú)非無(wú)非0 0的

53、的人工變量，有某個(gè)非基變量人工變量，有某個(gè)非基變量的檢驗(yàn)數(shù)為正數(shù)，但該變量對(duì)應(yīng)的系的檢驗(yàn)數(shù)為正數(shù)，但該變量對(duì)應(yīng)的系數(shù)全為非正數(shù)數(shù)全為非正數(shù)已知線性規(guī)劃問(wèn)題形如：已知線性規(guī)劃問(wèn)題形如：5-4 單純形法計(jì)算的向量、矩陣描述11111max s.t.0zC XA XbXmax s.t.0zCXAXbX引入松弛變量xs 記記X=(XB,XN,XS)T其中，其中， XS為松弛變量，在初始表中是基變量；為松弛變量，在初始表中是基變量； XB為為最終表中基變量；最終表中基變量； XN表示表示既不是初始表的基變量又不是最終表的基變量。既不是初始表的基變量又不是最終表的基變量。 注意：注意：XS和和XB允許有公

54、共變量。允許有公共變量。（2 2）A=(B,N,I) B,N,I分別為分別為XB 、XN 、 XS在初始表中在初始表中對(duì)應(yīng)對(duì)應(yīng)的矩陣。的矩陣。則（則（1 1）C=(CB,CN,0) CB,CN,0分別為分別為XB 、XN 、 XS在目標(biāo)函數(shù)中的系數(shù)。在目標(biāo)函數(shù)中的系數(shù)。（3 3）A=(I,N,B-1) I,N,B-1分別為分別為XB 、XN 、 XS在最終表中在最終表中對(duì)應(yīng)對(duì)應(yīng)的矩陣。的矩陣。約束方程組兩端同時(shí)左乘B-1，則可得如下表達(dá)式：max 0s.t.,0BBNNSBNSBNSzC XC XXBXNXIXbXXX 111 = max 0 s.t.,0BBNNSBNSBNSbB bNB N

55、zC XC XXI XN XB XbXXX 記111max 0s.t.,0BBNNSBNSBNSzC XC XXI XB NXB XB bXXX 初始單純形表初始單純形表最終單純形表最終單純形表用單純形表表示如下：用單純形表表示如下：XS bB N IXB b I N B-1初始表初始表 X XB B X XN N X XS S cj - zj 0,0 N S =（-y1,-y2,-ym）=-YT 最終表最終表 X XB B X XN N X XS S cj - zj B N 0,0 比較得：比較得：b =B-1b N =B-1N 或者或者 Pj =B-1Pj S = -CB B-1=-YT

56、N = CN-CB B-1 N = CN-YT N或者或者 j =Cj-CBB-1 Pj其中其中B B-1-1為初始表中基變量在最終表對(duì)應(yīng)的系數(shù)矩陣，為初始表中基變量在最終表對(duì)應(yīng)的系數(shù)矩陣， B B為最終表中基變量在初始表對(duì)應(yīng)的系數(shù)矩陣。為最終表中基變量在初始表對(duì)應(yīng)的系數(shù)矩陣。例：用單純形法求解下列線性規(guī)劃問(wèn)題.max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x10， x2 0 s.t.12345123142512345max 2300022 124 16 s.t. 5 15, , , , 0zxxxxxxxxxxxxxxxxx解：先標(biāo)準(zhǔn)化Cj 2 3 0

57、0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 j 得到初始單純形表：6-3 2 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5j 最終單純形表：X4010X4010202410005B11102542151005B 11221sBbB bPB PC B 可以驗(yàn)證：三三要要素素決策變量決策變量約束條件約束

58、條件目標(biāo)函數(shù)目標(biāo)函數(shù)兩兩個(gè)個(gè)三個(gè)三個(gè)以上以上x(chóng)j0 xj無(wú)無(wú)約束約束xj 0 bi 0bi 0=maxZminZxs xa標(biāo)標(biāo)準(zhǔn)準(zhǔn)化化圖圖解解法、法、單單純純形形法法單單純純形形法法不不處處理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不處處理理約束約束條件條件兩端兩端同乘同乘以以-1加加松松弛弛變變量量xs加加人人工工變變量量xa減減去去xs加加入入xa不不處處理理令令z=- Z 0-M根據(jù)上表可以列出初始單純形表根據(jù)上表可以列出初始單純形表5-5 5-5 單純形法小結(jié)單純形法小結(jié)個(gè)數(shù)取值限制右端常數(shù)約束方向要求系數(shù)結(jié)束j求檢驗(yàn)數(shù)0 j所所有有k找出最大正檢驗(yàn)數(shù)

59、？所有0 ika計(jì)算最小的lkxx替替換換基基變變量量用用非非基基變變量量單純形表列出下一張ax變量 的人工0非是否有 0 j非非基基變變量量的的有有某某個(gè)個(gè)最最優(yōu)優(yōu)解解一一唯唯 無(wú)可行解最優(yōu)解最優(yōu)解無(wú)窮多無(wú)窮多是是否否環(huán)環(huán)循循否否否否否否是是是是是是無(wú)無(wú)界界解解列初始表列初始表1.7 應(yīng)用舉例 一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題要滿足以下條一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題要滿足以下條件，才能建立線性規(guī)劃模型：件，才能建立線性規(guī)劃模型： . .需要求解問(wèn)題的目標(biāo)能用數(shù)值指標(biāo)來(lái)反映，需要求解問(wèn)題的目標(biāo)能用數(shù)值指標(biāo)來(lái)反映，且能用線性函數(shù)來(lái)描述目標(biāo)的要求；且能用線性函數(shù)來(lái)描述目標(biāo)的要求； . .為達(dá)到這個(gè)目標(biāo)

60、存在多種方案；為達(dá)到這個(gè)目標(biāo)存在多種方案； . .要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些條件可用線性等式或不等式來(lái)描述。些條件可用線性等式或不等式來(lái)描述。（一）、混合配料問(wèn)題例：某糖果廠用原料例：某糖果廠用原料A A、B B、C C加工成三種不同牌號(hào)的糖果甲、乙、丙。已知加工成三種不同牌號(hào)的糖果甲、乙、丙。已知各種牌號(hào)糖果中各種原料的含量，原料成本，各種原料的每月限制用量，各種牌號(hào)糖果中各種原料的含量，原料成本，各種原料的每月限制用量，三種牌號(hào)糖果的單位加工費(fèi)用及售價(jià)如下表所示。問(wèn)該廠每月生產(chǎn)這三三種牌號(hào)糖果的單位加工費(fèi)用及售價(jià)如下表所示。問(wèn)該廠每月生產(chǎn)