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

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

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

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

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

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

6、方法 應(yīng)用例應(yīng)用例 線性規(guī)劃線性規(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ī)劃 選址問題選址問題 動態(tài)規(guī)劃動態(tài)規(guī)劃 資源分配問題資源分配問題 網(wǎng)絡(luò)分析網(wǎng)絡(luò)分析 工程計劃優(yōu)化工程計劃優(yōu)化 排隊論排隊論 服務(wù)系統(tǒng)優(yōu)化服務(wù)系統(tǒng)優(yōu)化 存貯論存貯論 訂貨庫存管理訂貨庫存管理 決策分析決策分析 機會選擇機會選擇 8 運籌學(xué)的廣泛實際背景促使其不斷發(fā)展并運籌學(xué)的廣泛實際背景促使其不斷發(fā)展并 在經(jīng)濟管理和系在經(jīng)濟管理和系統(tǒng)工程等多領(lǐng)域中發(fā)揮著令統(tǒng)工程等多領(lǐng)域中發(fā)揮著令 人矚目的重要作用。人矚目的重要作用。 諾貝爾經(jīng)濟學(xué)獎從諾貝爾經(jīng)濟學(xué)獎從1969年首發(fā)至今的年

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

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

9、中心選址每年節(jié)約成本每年節(jié)約成本4.064.06億美億美元，銷售額大幅增加元，銷售額大幅增加標(biāo)準(zhǔn)品牌公司標(biāo)準(zhǔn)品牌公司控制成本庫存（制定最優(yōu)再定購點控制成本庫存（制定最優(yōu)再定購點和定購量確保安全庫存）和定購量確保安全庫存）每年節(jié)約成本每年節(jié)約成本380380萬美元萬美元法國國家鐵路公司法國國家鐵路公司制定最優(yōu)鐵路時刻表并調(diào)整鐵路日制定最優(yōu)鐵路時刻表并調(diào)整鐵路日運營量運營量每年節(jié)約成本每年節(jié)約成本15001500萬美萬美元，年收入大幅增加。元，年收入大幅增加。taco belltaco bell優(yōu)化員工安排，以最低成本服務(wù)客優(yōu)化員工安排，以最低成本服務(wù)客戶戶每年節(jié)約成本每年節(jié)約成本13001300

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

11、 清華出版社清華出版社11 （五）本課程的主要學(xué)習(xí)內(nèi)容（五）本課程的主要學(xué)習(xí)內(nèi)容 第一章第一章 線性規(guī)劃及單純形法線性規(guī)劃及單純形法 第二章第二章 線性規(guī)劃的對偶理論線性規(guī)劃的對偶理論 第三章第三章 運輸問題運輸問題 第四章第四章 整數(shù)規(guī)劃與分配問題整數(shù)規(guī)劃與分配問題 12（六）本課程授課方式與考核（六）本課程授課方式與考核學(xué)科總成績學(xué)科總成績平時成績平時成績（3030）課堂考勤課堂考勤（1212）平時作業(yè)平時作業(yè)（1818）期末成績期末成績（7070）講授為主，結(jié)合討論、習(xí)題作業(yè)講授為主，結(jié)合討論、習(xí)題作業(yè)13第一章第一章 線性規(guī)劃及單純形法線性規(guī)劃及單純形法linear programmi

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

13、經(jīng)濟學(xué)家年美國經(jīng)濟學(xué)家t.c.庫普曼斯庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟領(lǐng)域把線性規(guī)劃應(yīng)用到經(jīng)濟領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟學(xué)獎。1550年代后對線性規(guī)劃進行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年年c.萊姆基提出對偶單純形法萊姆基提出對偶單純形法，1954年年s.加斯和加斯和t.薩迪等人解決了線性規(guī)劃的靈敏度分析薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題，和參數(shù)規(guī)劃問題，1956年年a.塔克提出互補松弛定理，塔克提出互補松弛定理，1960年年g.b.丹齊克和丹齊克和p.沃爾夫提出分解算法沃爾夫提出分解算法等。線性規(guī)劃的研究成果還直接推動了其他數(shù)學(xué)規(guī)劃問題包

14、括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計算機的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如mpsx，opheie，umpire等，可以很方便地求解幾千個變量的線性規(guī)劃問題。161979年蘇聯(lián)數(shù)學(xué)家年蘇聯(lián)數(shù)學(xué)家.哈奇揚提出解線性規(guī)劃問題的橢球哈奇揚提出解線性規(guī)劃問題的橢球算法算法，并證明它是多項式時間算法。1984年年美國貝爾電話實驗室的印度數(shù)學(xué)家n.卡馬卡提出解線性規(guī)劃問題的新卡馬卡提出解線性規(guī)劃問題的新的多項式時間算法的多項式時間算法-內(nèi)點算法內(nèi)點算法。用這種方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用時間的1/50?，F(xiàn)已形成線性規(guī)劃多項式算法理論。50年代后線性規(guī)劃的應(yīng)

15、用范圍不斷擴大。171.1939年，前蘇聯(lián)科學(xué)家康托洛維奇年，前蘇聯(lián)科學(xué)家康托洛維奇-生產(chǎn)組織與管理中的數(shù)學(xué)方法生產(chǎn)組織與管理中的數(shù)學(xué)方法是線性是線性規(guī)劃應(yīng)用于工業(yè)生產(chǎn)問題的開山之作規(guī)劃應(yīng)用于工業(yè)生產(chǎn)問題的開山之作；(leonidvitaliyevichkantorov(1912-1986) 182. 1947年，美國數(shù)學(xué)家喬治年，美國數(shù)學(xué)家喬治伯納德伯納德丹齊格丹齊格-單純形法，被稱為單純形法，被稱為線性規(guī)劃之父。線性規(guī)劃之父。georgebernarddantzig(19142005)19 丹齊格在丹齊格在1946年獲伯克利大學(xué)的博士學(xué)位。年獲伯克利大學(xué)的博士學(xué)位。1947年，年，33歲提

16、出了解決一種最優(yōu)化問題的單純形法歲提出了解決一種最優(yōu)化問題的單純形法,該方法奠定了線性規(guī)該方法奠定了線性規(guī)劃的基礎(chǔ)，使得經(jīng)濟學(xué)、環(huán)境科學(xué)、統(tǒng)計學(xué)應(yīng)用等學(xué)科獲得了劃的基礎(chǔ)，使得經(jīng)濟學(xué)、環(huán)境科學(xué)、統(tǒng)計學(xué)應(yīng)用等學(xué)科獲得了迅速發(fā)展。迅速發(fā)展。dantzig也因而被譽為也因而被譽為“線性規(guī)劃之父線性規(guī)劃之父”。 1952年年他在蘭德公司任研究數(shù)學(xué)家，在公司電腦上實行線性規(guī)劃。他在蘭德公司任研究數(shù)學(xué)家，在公司電腦上實行線性規(guī)劃。1960年他被母校聘任教授計算機科學(xué)，終于當(dāng)上運籌學(xué)中心主任。年他被母校聘任教授計算機科學(xué)，終于當(dāng)上運籌學(xué)中心主任。1966年他在史丹福大學(xué)當(dāng)類似職位，留在那里直到年他在史丹福大學(xué)

17、當(dāng)類似職位，留在那里直到1990年代年代退休。退休。dantzig在運籌學(xué)建樹極高，獲得了包括在運籌學(xué)建樹極高，獲得了包括“馮諾伊曼理論馮諾伊曼理論獎獎”在內(nèi)的諸多獎項。他在在內(nèi)的諸多獎項。他在linear programming andextensions一書中研究了線性編程模型，為計算機語言的發(fā)展做出了不一書中研究了線性編程模型，為計算機語言的發(fā)展做出了不可磨滅的貢獻(xiàn)。他除了線性規(guī)劃和單純形法的杰出工作，還推可磨滅的貢獻(xiàn)。他除了線性規(guī)劃和單純形法的杰出工作，還推進很多領(lǐng)域的發(fā)展，有分解論、靈敏度分析、互補主元法、大進很多領(lǐng)域的發(fā)展，有分解論、靈敏度分析、互補主元法、大系統(tǒng)最優(yōu)化、非線性規(guī)劃

18、和不確定規(guī)劃。系統(tǒng)最優(yōu)化、非線性規(guī)劃和不確定規(guī)劃。siam journal on optimization1991年創(chuàng)刊號是獻(xiàn)給他的。年創(chuàng)刊號是獻(xiàn)給他的。mathematical programming society為表彰丹齊格，設(shè)立丹齊格獎，為表彰丹齊格，設(shè)立丹齊格獎，1982年起每三年年起每三年頒給一至兩位在數(shù)學(xué)規(guī)劃有突出貢獻(xiàn)的人。頒給一至兩位在數(shù)學(xué)規(guī)劃有突出貢獻(xiàn)的人。20 xa 2 2xxav此為無約束的極值問題此為無約束的極值問題6 ax 有0 dxdv由1.1 一般線性規(guī)劃問題的數(shù)學(xué)模型一般線性規(guī)劃問題的數(shù)學(xué)模型1-1 1-1 問題的提出問題的提出例例1 1 用一塊邊長為用一塊邊長

19、為a的正方形鐵皮做一個無蓋長方體容的正方形鐵皮做一個無蓋長方體容器，應(yīng)如何裁剪可使做成的容器的容積最大？器，應(yīng)如何裁剪可使做成的容器的容積最大？)20(ax 解：如圖設(shè)四個角上減去的小正方形邊解：如圖設(shè)四個角上減去的小正方形邊長為長為x，則容器體積為：，則容器體積為：時，容積最大時，容積最大21 例例2 2 常山機器廠生產(chǎn)常山機器廠生產(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)品的單位利潤、消耗三種工藝規(guī)定，生產(chǎn)每件產(chǎn)品的單位利潤、消耗三種設(shè)備的工時以及各種設(shè)備工時的限額

20、如下表：設(shè)備的工時以及各種設(shè)備工時的限額如下表： 單位產(chǎn)品消耗設(shè)單位產(chǎn)品消耗設(shè)備工時備工時i iiiii設(shè)備工時限量設(shè)備工時限量（小時）（小時） 設(shè)備設(shè)備a a設(shè)備設(shè)備b b設(shè)備設(shè)備c c2 24 40 02 20 05 5121216161515單位利潤（元）單位利潤（元）2 23 322解：設(shè)計劃期內(nèi)兩種產(chǎn)品的數(shù)量分別為解：設(shè)計劃期內(nèi)兩種產(chǎn)品的數(shù)量分別為x x1 1，x x2 2，則總利潤為：，則總利潤為：maxz=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0， x2 0簡記為：簡記為： s.t.（約束于：）（約束于：）z=2 x1+3 x2在滿足限制條

21、件下求在滿足限制條件下求z的最大值。的最大值。此為有約束極值問題此為有約束極值問題231-2 1-2 線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型原型原型模型模型數(shù)學(xué)模型數(shù)學(xué)模型提煉提煉數(shù)學(xué)工具數(shù)學(xué)工具1 1、原型原型：現(xiàn)實世界中人們關(guān)心、研究的實際對象。：現(xiàn)實世界中人們關(guān)心、研究的實際對象。 模型模型：將某一部分信息簡縮、提煉而構(gòu)造的原型替代物。：將某一部分信息簡縮、提煉而構(gòu)造的原型替代物。 數(shù)學(xué)模型數(shù)學(xué)模型：對現(xiàn)實世界的一個特定對象，為達(dá)到一定目的，：對現(xiàn)實世界的一個特定對象，為達(dá)到一定目的，根據(jù)內(nèi)在規(guī)律做出必要的簡化假設(shè)根據(jù)內(nèi)在規(guī)律做出必要的簡化假設(shè), ,并運用適當(dāng)數(shù)學(xué)工具得到并運用適當(dāng)

22、數(shù)學(xué)工具得到的一個數(shù)學(xué)結(jié)構(gòu)。的一個數(shù)學(xué)結(jié)構(gòu)。243 3、規(guī)劃問題數(shù)學(xué)模型的三要素、規(guī)劃問題數(shù)學(xué)模型的三要素（2 2）目標(biāo)函數(shù)目標(biāo)函數(shù)：問題要達(dá)到的目標(biāo)要求，表示為決策變量的：問題要達(dá)到的目標(biāo)要求，表示為決策變量的函數(shù)。用函數(shù)。用 z= =f( (x1 1，x2 2，xn n) )表示。表示。（1 1）決策變量決策變量：決策者為實現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，：決策者為實現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，是問題中要確定的未知量。用是問題中要確定的未知量。用x1 1，x2 2，xn n表示。表示。（3 3）約束條件約束條件：決策變量取值時受到的各種可用資源的限制，：決策變量取值時受到的各種可用資源的限制，

23、表示為含決策變量的等式或不等式。表示為含決策變量的等式或不等式。2 2、規(guī)劃問題、規(guī)劃問題即求目標(biāo)函數(shù)在若干約束條件下的最值。即求目標(biāo)函數(shù)在若干約束條件下的最值。254 4、線性規(guī)劃問題（、線性規(guī)劃問題（linear programminglinear programming）的數(shù)學(xué)模型）的數(shù)學(xué)模型（2 2）一般形式一般形式：（1 1）條件條件：決策變量為可控的連續(xù)變量，目標(biāo)函數(shù)和約束條：決策變量為可控的連續(xù)變量，目標(biāo)函數(shù)和約束條件都是線性的。簡記為件都是線性的。簡記為“l(fā).p.” max (或或 min) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn （=，

24、）b1 a21x1+a22x2+a2nxn （=，） b2 am1x1+am2x2+amnxn（=，） bm x1 , x2, , xn026（3 3）其他形式其他形式：連加形式連加形式11max (min) z=( , ) (1,2,). . 0 (1,2, )njjjnijjijjc xa xbimstxjn 27向量形式向量形式1max (min) z=( , ) . . 0 njjjcxp xbstx 12( ,)ncc cc12nxxxx12jjjmjaapa其中 稱為價值行向量價值行向量；決策列向量決策列向量12mbbbb系數(shù)列向量系數(shù)列向量右端列向量右端列向量28矩陣形式矩陣形式

25、max (min) z=( , ) . . 0 cxaxbstx 12( ,)ncc cc12nxxxx1112121222121 2 ,nnnmmmnaaaaaaap ppaaa其中 稱為價值行向量；稱為價值行向量；決策列向量決策列向量12mbbbb右端列向量右端列向量約束矩陣或系數(shù)矩陣約束矩陣或系數(shù)矩陣291-3 1-3 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(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或或302 2、條件、條件

26、目標(biāo)函數(shù)求極大值目標(biāo)函數(shù)求極大值約束條件全是等式（線性方程組）約束條件全是等式（線性方程組）決策變量全非負(fù)決策變量全非負(fù)右端常數(shù)全非負(fù)右端常數(shù)全非負(fù)313 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 xcx32（2 2）若約束條件為不等式，）若約束條件為不等式，則依次引入松弛變量或剩余變量（統(tǒng)稱為松弛變量），則依次引入松弛變量或剩余變量（統(tǒng)稱為松弛變量），轉(zhuǎn)化為等式約束條件。轉(zhuǎn)化為等式約束條件。注意注意：松弛變量在目標(biāo)函數(shù)中系數(shù)全為：松弛變量在目標(biāo)函

27、數(shù)中系數(shù)全為0。約束為約束為不等式，減去松弛變量，化為等式約束條件；不等式，減去松弛變量，化為等式約束條件；約束為約束為不等式，加上松弛變量，化為等式約束條件。不等式，加上松弛變量，化為等式約束條件。多退少補多退少補例：例：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)化330jjxx， 0jjjxxx 且jjjxxx（3 3）若決策變量）若決策變量xj0，則令，則令（4 4

28、）若決策變量）若決策變量xj取值無限制，則令取值無限制，則令（5 5）若約束等式的右端常數(shù)）若約束等式的右端常數(shù)bi 0 0，則等式兩邊同時乘以，則等式兩邊同時乘以“-1-1”。其中其中（“一分為二一分為二”）34例：例：將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式。將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式。123123123123123min2329324. .32360, 0, zxxxxxxxxxstxxxxxx 取值無限制3511133333 (0) (0, 0)zzxxxxxxxx 解：令12334512334123351233123345max 233002 9322 4 s.t. 3233 6, , ,

29、 , 0zxxxxxxxxxxxxxxxxxxxxxxxxxx 則問題化為標(biāo)準(zhǔn)形式：則問題化為標(biāo)準(zhǔn)形式：并引入松弛變量并引入松弛變量x4, x5,36課堂練習(xí)：將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式123123123123123m in235 7 42325,0, zxxxxxxxxxxxxxxx 無 約 束37線性規(guī)劃問題的數(shù)學(xué)模型12334512334123351233123345max23()005() 7 () 252() 5,0 zxxxxxxxxxxxxxxxxxxxxx xxxxx標(biāo)準(zhǔn)形式如下：381-4 1-4 線性規(guī)劃問題的解線性規(guī)劃問題的解12max z= (1) (2). . 0

30、 (3) 0,ncxaxbstxbap pp其中（）11max z= (1) (1,2,) (2). . 0 (1,2, ) (3) 0(1,2,)njjjnijjijjic xa xbimstxjnbim已知線性規(guī)劃的標(biāo)準(zhǔn)形式：已知線性規(guī)劃的標(biāo)準(zhǔn)形式：或或1 1、求解線性規(guī)劃問題求解線性規(guī)劃問題：從滿足（從滿足（2）、（）、（3）的方程組中找出一個解使目標(biāo)函）的方程組中找出一個解使目標(biāo)函數(shù)（數(shù)（1）達(dá)到最大值。）達(dá)到最大值。392 2、可行解可行解：所有可行解的集合。所有可行解的集合。12nxxxx可行域可行域：滿足約束條件（滿足約束條件（2）、（）、（3）的解。）的解。記做記做最優(yōu)解最優(yōu)解

31、： 使目標(biāo)函數(shù)達(dá)到最大值的可行解。使目標(biāo)函數(shù)達(dá)到最大值的可行解。40（1 1）基基：設(shè)：設(shè)a a為線性規(guī)劃問題約束條件的為線性規(guī)劃問題約束條件的 m n 系數(shù)矩陣系數(shù)矩陣（m00，有如下結(jié)論：有如下結(jié)論：(1) (1) 若對所有若對所有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) 若對所有若對所有j m+1 ，有有 j 0，且，且存在某個非基變量的檢驗數(shù)存在某個非基變量的檢驗數(shù) k=0，則將，則將pk作為新的基向量得出新的基可行解作為新的基向量得出新的基可行解x（1 1） ，滿足，滿足

32、z（1） = z （0） ，故，故z（1） 也也為最優(yōu)函數(shù)值，從而為最優(yōu)函數(shù)值，從而 x（1）也也為最優(yōu)解，為最優(yōu)解， x（0） 、x（1） 連線上所有點均為最優(yōu)解，因此該線性規(guī)劃連線上所有點均為最優(yōu)解，因此該線性規(guī)劃模型具有模型具有無窮多最優(yōu)解無窮多最優(yōu)解；(3) (3) 若存在某個若存在某個 j 0 0，但對應(yīng)的第，但對應(yīng)的第j列系數(shù)全非正，即列系數(shù)全非正，即aij 0 0，則，則當(dāng)當(dāng) + + 時，有時，有z（1） + + ， 該線性規(guī)劃模型具有該線性規(guī)劃模型具有無界解無界解。(1)(0)jzz671.4 1.4 單純形法的計算步驟單純形法的計算步驟1 1、前提：標(biāo)準(zhǔn)化的線性規(guī)劃問題的系數(shù)

33、矩陣含有單位子矩陣。、前提：標(biāo)準(zhǔn)化的線性規(guī)劃問題的系數(shù)矩陣含有單位子矩陣。m n max z= s.t. 0 0cxaxbxb已知12(0)00mbbxb不妨假設(shè)不妨假設(shè)a中前中前m列對應(yīng)的子矩陣是單位列對應(yīng)的子矩陣是單位矩陣，取其為基矩陣，取其為基b，得到初始基可行解，得到初始基可行解68m+3行行n+4列列第第1行：價值行行：價值行 cj第第2行：變量行行：變量行 xj最后一最后一行：檢驗數(shù)行行：檢驗數(shù)行 j第第1列：基價值列列：基價值列 cb第第2列列：基變量列：基變量列 xb第第3列列：基解列：基解列 b最后一最后一列：列：比值比值列列 主體：系數(shù)矩陣主體：系數(shù)矩陣amn2 2、單純形

34、表的結(jié)構(gòu)、單純形表的結(jié)構(gòu)69jcnmmcccc11bcbxbmcc 1mxx 1mbb 1nmmxxxx 11m 1mnmmnmaaaa1,11, 110010 0miijijjacc1jjjzc min0iijiijbaa703 3、初始單純形表：含初始基可行解的單純形表、初始單純形表：含初始基可行解的單純形表 最優(yōu)單純形表：含最優(yōu)解的單純形表最優(yōu)單純形表：含最優(yōu)解的單純形表4 4、單純形法（、單純形法（ ）：）： 利用單純形表求解線性規(guī)劃問題的方法。利用單純形表求解線性規(guī)劃問題的方法。715 5、單純形法的計算步驟、單純形法的計算步驟(1) (1) 化化 l.p.問題為標(biāo)準(zhǔn)形式問題為標(biāo)準(zhǔn)形

35、式, ,建立初始單純形表；建立初始單純形表；（簡稱換入變量）；的變量做為換入基所對應(yīng)的變量選取，令否則，則已經(jīng)得到最優(yōu)解，若所有檢驗數(shù) 0|max 0 (2)bkkjjkjxx（簡稱換出變量）；的變量做為換出基所對應(yīng)的變量選取blxxmin0iijiijbaa(3) (3) 計算計算(4)(4) 以以alk為主元素為主元素( (簡稱主元，用簡稱主元，用 表示表示) )，進行線性方程組，進行線性方程組 的初等行變換，將主元列的初等行變換，將主元列pk化為單位向量得到新的單純形表，化為單位向量得到新的單純形表，轉(zhuǎn)入轉(zhuǎn)入(2)(2)。（最大正檢驗數(shù)決定換入變量）（最大正檢驗數(shù)決定換入變量）（最小比值

36、（最小比值決定換出變量決定換出變量）72例例1：用單純形法求解下列線性規(guī)劃問題：用單純形法求解下列線性規(guī)劃問題.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)化73cj 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 再列初始單純形表：

37、再列初始單純形表：6-32 3 0 0 074cj 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 0 0 1 3 2 3 0 0 0 j 以以55為主元進為主元進行初等行變換行初等行變換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為換入變量為換入變量 下面開始單純形法迭代：下面開始單純形法迭

38、代：x5 5為換出變量為換出變量x2 2為換入變量為換入變量以以22為主元進為主元進行初等行變換行初等行變換x3 3為換出變量為換出變量主元化為主元化為1，主元列，主元列的其他元素化為的其他元素化為075cj 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 此時得到唯一最優(yōu)解此時得到唯一最優(yōu)解x*=(3,3)t, , zmax=15=15。76例例2 2 用單純形法求解下列線性規(guī)劃問題用單純形法求解下列線性規(guī)劃問題 0,2426155

39、3 s.t.2max21212121xxxxxxxxz 0,24 2615 53 s.t.2 max432142132121xxxxxxxxxxxxz解：先標(biāo)準(zhǔn)化解：先標(biāo)準(zhǔn)化77 2 1 0 0 54 x3x400 x1 x2 x3 x4bxbcb 2 1 0 0cj 2415351 06201j78 0 0 x3x102 x1 x2 x3 x4bxbcb 2 1 0 0cj430141 0j1/3-1/21/61/3-1/33/41279 0 0 -1/12 -7/24 x2x112 x1 x2 x3 x4bxbcb 2 1 0 0cj15/43/4011/4-1/810 -1/125/24

40、j唯一最優(yōu)解12max15333, , 444xxz806、單純形法中存在的問題、單純形法中存在的問題（1 1） 存在兩個以上的最大正檢驗數(shù)。存在兩個以上的最大正檢驗數(shù)。任取一個最大正檢驗數(shù)對應(yīng)的變量作為換入變量。任取一個最大正檢驗數(shù)對應(yīng)的變量作為換入變量。（2 2） 出現(xiàn)兩個以上相同的最小值。出現(xiàn)兩個以上相同的最小值。任取一個最小任取一個最小對應(yīng)的變量作為換出變量。對應(yīng)的變量作為換出變量。此時此時l.p.問題出現(xiàn)退化現(xiàn)象。問題出現(xiàn)退化現(xiàn)象。8112121212max24312s.t. 48,0zxxxxxxx x練習(xí)：練習(xí)：825-1 5-1 人工變量法（大人工變量法（大m法）法）1.5 單

41、純形法的進一步討論 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大量，構(gòu)成的可行基稱為人工基，用大mm法或兩階法或兩階段法求解，這種用人工變量作橋梁的求解方法稱段法求解，這種用人工變量作橋梁

42、的求解方法稱為人工變量法。為人工變量法。8312121212min23 3s.t. 24,0zxxxxxxx x例例1：用單純形法求解下列線性規(guī)劃問題。：用單純形法求解下列線性規(guī)劃問題。8412312312123max230 3s.t. 2 4 ,0zxxxxxxxxx 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中沒有單位矩陣，在中沒有單位矩陣，在a中

43、人為的增加兩列中人為的增加兩列此時對應(yīng)的約束方程組為對應(yīng)的約束方程組為：該問題新增加了兩個變量：x4, x5（稱為人工變量）（稱為人工變量）a有單位子矩陣，選擇這個單位矩陣作為基（稱為人工基）。有單位子矩陣，選擇這個單位矩陣作為基（稱為人工基）。85為使 12312123 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ù)），這種添加人工變量求解這種添加人工變量求解l

44、p的方法稱為的方法稱為人工變量法人工變量法,計算過程中出現(xiàn)了計算過程中出現(xiàn)了m，這種方法也稱為，這種方法也稱為大大m法法。等價于86于是，這個線性規(guī)劃問題轉(zhuǎn)化為：于是，這個線性規(guī)劃問題轉(zhuǎn)化為：123451234125max230 3s.t. 2 4 0 (1,2,5)jzxxxmxmxxxxxxxxxj 以下可用單純形法繼續(xù)求解。以下可用單純形法繼續(xù)求解。87cj 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

45、 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 故 zmin=7注意：此時人工變量x4=x5=088說明：說明： 若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工變量的人工變量 ，則該模，則該模型型無可行解無可行解。 采用大采用大m法求解線性規(guī)劃模型時，如果模型中法求解線性規(guī)劃模型時，如果模型中各個系數(shù)與各個系數(shù)與m的值非常接近或相差很大，若用手工計算的值非常接近或相

46、差很大，若用手工計算不會出現(xiàn)問題。但是若利用計算機求解，則容易引起混不會出現(xiàn)問題。但是若利用計算機求解，則容易引起混淆，使得機器判斷出錯，從而使大淆，使得機器判斷出錯，從而使大m法失效。法失效。 在這種情況下，可采用下面的兩階段法進行計算。在這種情況下，可采用下面的兩階段法進行計算。895-2 5-2 兩階段法兩階段法( (將將l.p.問題分成兩個階段來考慮問題分成兩個階段來考慮) ) 第一階段第一階段: : 判斷原判斷原l.p.l.p.問題是否存在可行解。問題是否存在可行解。 給原給原l.p.l.p.問題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)問題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)函數(shù)

47、w（人工變量在人工變量在w中的系數(shù)一般取為中的系數(shù)一般取為1 1）并求）并求w的最小值；的最小值；然后用單純形法求解。若求得然后用單純形法求解。若求得wmin=0=0，則該問題有可行解，進，則該問題有可行解，進入第二階段，否則該問題無可行解，結(jié)束。入第二階段，否則該問題無可行解，結(jié)束。 第二階段：將第第二階段：將第一一階段得到的最終表去掉人工變量，并階段得到的最終表去掉人工變量，并將目標(biāo)函數(shù)還原為原將目標(biāo)函數(shù)還原為原l.p.問題的目標(biāo)函數(shù)（即修改最終表中問題的目標(biāo)函數(shù)（即修改最終表中的第一行和第一列），以此作為第二階段的初始表，繼續(xù)的第一行和第一列），以此作為第二階段的初始表，繼續(xù)用單純形法求

48、解。用單純形法求解。90例：用兩階段法求解下列線性規(guī)劃問題。例：用兩階段法求解下列線性規(guī)劃問題。12121212min23 3s.t. 24,0zxxxxxxx x12312312123max230 3s.t. 2 4 ,0zxxxxxxxxx x x 標(biāo)準(zhǔn)化引入人工變量123451234125max230 3s.t. 2 4 0 (1,2,5)jzxxxmxmxxxxxxxxxj z91451234125min 3s.t. 2 40 (1,2,5)jwxxxxxxxxxxj451234125max 3s.t. 2 40 (1,2,5)jwxxxxxxxxxxj (1) (1) 第一階段，構(gòu)造

49、判斷是否存在可行解的模型：第一階段，構(gòu)造判斷是否存在可行解的模型： 用單純形法求解這個問題，先標(biāo)準(zhǔn)化為；用單純形法求解這個問題，先標(biāo)準(zhǔn)化為；92cj x1x2x3x4xbbcb1 1 -1 1 0 1 2 0 0 1 0 0 0 -1 -134x4 x5-1 -1cj - zj 2 3-103/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 xxw

50、w，即本問題有可行解，進入第二階段93 (2) (2) 第二階段第二階段 先在第一階段的最終單純形表去掉人工變量，再還原原先在第一階段的最終單純形表去掉人工變量，再還原原目標(biāo)函數(shù)，即目標(biāo)函數(shù)，即 max z=-2=-2x1 1-3-3x2 2+0+0 x3 3，繼續(xù)迭代：繼續(xù)迭代：cj x1x2x3xbbcb1 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，但需要解兩個線性規(guī)劃問題，要注意目標(biāo)函數(shù)系數(shù)的變化。945-3 關(guān)于解的判別例例7 用單純形法解下列線性規(guī)劃用

51、單純形法解下列線性規(guī)劃無窮多解當(dāng)所有的當(dāng)所有的 ，但某一非基變量檢驗數(shù)，但某一非基變量檢驗數(shù) ，存，存在無窮多最優(yōu)解的條件是在無窮多最優(yōu)解的條件是ps列向量中至少存在一個元列向量中至少存在一個元素素 ，且能找出最優(yōu)解，且能找出最優(yōu)解.0j0s0isa 12121212max332212416. .515,0zxxxxxstxx xmax z 12121212max332212416s.t. 515,0zxxxxxxxx95例例8 用單純形法解下列線性規(guī)劃用單純形法解下列線性規(guī)劃無界解無界解 若存在某個若存在某個 j 0 0，但對應(yīng)的第，但對應(yīng)的第j列系數(shù)全非正，即列系數(shù)全非正，即aij 0 0

52、，則問題的解無界，則問題的解無界. .12112max23416s.t. ,0zxxxxx96例例9 用單純形法解下列線性規(guī)劃用單純形法解下列線性規(guī)劃12121212max232212s.t. 214,0zxxxxxxx x無可行解無可行解若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工變量的人工變量 ，則該模，則該模型無可行解。型無可行解。12121212max232212s.t. 214 ,0zxxxxxxxx97用最終單純形表判斷線性規(guī)劃問題解的類型：用最終單純形表判斷線性規(guī)劃問題解的類型：解的類型解的類型最終表的特征最終表的特征無可行解無可行解有非有非0 0的人工變量

53、的人工變量有有可可行行解解唯一最優(yōu)解唯一最優(yōu)解無無非非0 0的人的人工變量，非基變量的檢驗工變量，非基變量的檢驗數(shù)全為負(fù)數(shù)數(shù)全為負(fù)數(shù)無窮多最優(yōu)解無窮多最優(yōu)解無非無非0 0的人工的人工變量，非基變量的檢驗變量，非基變量的檢驗數(shù)全非正，且有某個非基變量的檢驗數(shù)全非正，且有某個非基變量的檢驗數(shù)為數(shù)為0 0無界解無界解無非無非0 0的的人工變量，有某個非基變量人工變量，有某個非基變量的檢驗數(shù)為正數(shù)，但該變量對應(yīng)的系的檢驗數(shù)為正數(shù)，但該變量對應(yīng)的系數(shù)全為非正數(shù)數(shù)全為非正數(shù)98已知線性規(guī)劃問題形如：已知線性規(guī)劃問題形如：5-4 單純形法計算的向量、矩陣描述11111max s.t.0zc xa xbxma

54、x s.t.0zcxaxbx引入松弛變量xs 記記x=(xb,xn,xs)t其中，其中， xs為松弛變量，在初始表中是基變量；為松弛變量，在初始表中是基變量； xb為為最終表中基變量；最終表中基變量； xn表示表示既不是初始表的基變量又不是最終表的基變量。既不是初始表的基變量又不是最終表的基變量。 注意：注意：xs和和xb允許有公共變量。允許有公共變量。（2 2）a=(b,n,i) b,n,i分別為分別為xb 、xn 、 xs在初始表中在初始表中對應(yīng)對應(yīng)的矩陣。的矩陣。則（則（1 1）c=(cb,cn,0) cb,cn,0分別為分別為xb 、xn 、 xs在目標(biāo)函數(shù)中的系數(shù)。在目標(biāo)函數(shù)中的系數(shù)

55、。（3 3）a=(i,n,b-1) i,n,b-1分別為分別為xb 、xn 、 xs在最終表中在最終表中對應(yīng)對應(yīng)的矩陣。的矩陣。99約束方程組兩端同時左乘b-1，則可得如下表達(dá)式：max 0s.t.,0bbnnsbnsbnszc xc xxbxnxixbxxx 111 = max 0 s.t.,0bbnnsbnsbnsbb bnb nzc xc xxi xn xb xbxxx 記111max 0s.t.,0bbnnsbnsbnszc xc xxi xb nxb xb bxxx 初始單純形表初始單純形表最終單純形表最終單純形表100用單純形表表示如下：用單純形表表示如下：xs bb n ixb

56、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 n = cn-cb b-1 n = cn-yt n或者或者 j =cj-cbb-1 pj其中其中b b-1-1為初始表中基變量在最終表對應(yīng)的系數(shù)矩陣，為初始表中基變量在最終表對應(yīng)的系數(shù)矩陣， b b為最終表中基變量在初始表對應(yīng)的系數(shù)矩陣。為最終表中基變量在初

57、始表對應(yīng)的系數(shù)矩陣。101例：用單純形法求解下列線性規(guī)劃問題.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)化102cj 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-3 2 3 0 0 0cj 2 3 0 0 0 cb xb

58、 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 可以驗證：103三三要要素素決策變量決策變量約束條件約束條件目標(biāo)函數(shù)目標(biāo)函數(shù)兩兩個個三個三個以上以上xj0 xj無無約束約束xj 0 bi 0bi 0=maxzminzxs xa標(biāo)標(biāo)準(zhǔn)準(zhǔn)化化圖圖解解法、法、單單純純形形法法單單純純形形法法不不處處理理令令xj = xj - xj xj 0 xj

59、0令令 xj =- xj不不處處理理約束約束條件條件兩端兩端同乘同乘以以-1加加松松弛弛變變量量xs加加人人工工變變量量xa減減去去xs加加入入xa不不處處理理令令z=- z 0-m根據(jù)上表可以列出初始單純形表根據(jù)上表可以列出初始單純形表5-5 5-5 單純形法小結(jié)單純形法小結(jié)個數(shù)取值限制右端常數(shù)約束方向要求系數(shù)104結(jié)束j求檢驗數(shù)0 j所所有有k找出最大正檢驗數(shù)？所有0 ika計算最小的lkxx替替換換基基變變量量用用非非基基變變量量單純形表列出下一張ax變量 的人工0非是否有 0 j非非基基變變量量的的有有某某個個最最優(yōu)優(yōu)解解一一唯唯 無可行解最優(yōu)解最優(yōu)解無窮多無窮多是是否否環(huán)環(huán)循循否否否

60、否否否是是是是是是無無界界解解列初始表列初始表1051.7 應(yīng)用舉例 一般而言，一個經(jīng)濟、管理問題要滿足以下條一般而言，一個經(jīng)濟、管理問題要滿足以下條件，才能建立線性規(guī)劃模型：件，才能建立線性規(guī)劃模型： . .需要求解問題的目標(biāo)能用數(shù)值指標(biāo)來反映，需要求解問題的目標(biāo)能用數(shù)值指標(biāo)來反映，且能用線性函數(shù)來描述目標(biāo)的要求；且能用線性函數(shù)來描述目標(biāo)的要求； . .為達(dá)到這個目標(biāo)存在多種方案；為達(dá)到這個目標(biāo)存在多種方案； . .要求達(dá)到的目標(biāo)是在一定條件下實現(xiàn)的，這要求達(dá)到的目標(biāo)是在一定條件下實現(xiàn)的，這些條件可用線性等式或不等式來描述。些條件可用線性等式或不等式來描述。106（一）、混合配料問題例：某糖果廠用原料例：某