天大運(yùn)籌學(xué)課件1(線性規(guī)劃,運(yùn)輸問題等)

1、天津大學(xué)管理與經(jīng)濟(jì)學(xué)部天津大學(xué)管理與經(jīng)濟(jì)學(xué)部教師簡介張小濤，博士，副教授 研究方向： 計(jì)算實(shí)驗(yàn)金融，中小企業(yè)融資 Email： 什么是運(yùn)籌學(xué)什么是運(yùn)籌學(xué)? ?運(yùn)籌學(xué)的簡史運(yùn)籌學(xué)的簡史運(yùn)籌學(xué)的分支有哪些運(yùn)籌學(xué)的分支有哪些? ?運(yùn)籌學(xué)研究的一般程序運(yùn)籌學(xué)研究的一般程序課程要求課程要求2022-7-5田忌賽馬：田忌與齊王多次賽馬，屢戰(zhàn)屢敗，田忌賽馬：田忌與齊王多次賽馬，屢戰(zhàn)屢敗，田忌的一位謀士比較了六種對策后建議田忌的一位謀士比較了六種對策后建議 十萬個為什么十萬個為什么. .數(shù)學(xué)分冊數(shù)學(xué)分冊P.312P.312最早記載的最早記載的對策論對策論范例。范例。2022-7-5123456上上上中中下下下

2、中中下上下中上上下下中下上上中中齊王田忌祥符中祥符中, ,禁火。時禁火。時丁晉公丁晉公主營復(fù)宮室主營復(fù)宮室, ,患取土遠(yuǎn)患取土遠(yuǎn), ,公乃令鑿?fù)ㄡ楣肆铊復(fù)ㄡ槿⊥寥⊥? ,不日皆不日皆成巨塹。乃決汴水入塹中成巨塹。乃決汴水入塹中, ,引諸道竹木引諸道竹木排筏及船運(yùn)雜材排筏及船運(yùn)雜材, ,盡自塹中入至宮門。盡自塹中入至宮門。事畢事畢, ,卻以斥卻以斥棄瓦礫灰壤實(shí)于塹棄瓦礫灰壤實(shí)于塹中中, ,復(fù)復(fù)為街衢。一舉而三役濟(jì)為街衢。一舉而三役濟(jì), ,計(jì)計(jì)省費(fèi)省費(fèi)以億萬以億萬計(jì)。計(jì)。 沈括沈括夢溪筆談夢溪筆談. .補(bǔ)筆談卷二補(bǔ)筆談卷二. .權(quán)智權(quán)智2022-7-5據(jù)據(jù)史記史記記載：漢高祖劉邦稱贊張良：記載：

3、漢高祖劉邦稱贊張良：策帷策帷帳中，決勝千里外，子房功也。帳中，決勝千里外，子房功也。 司馬遷司馬遷史記史記留侯世家留侯世家“籌籌”是古代比算盤還早的計(jì)算工具之一。是古代比算盤還早的計(jì)算工具之一?！斑\(yùn)籌運(yùn)籌”是計(jì)劃、安排、比較、決策優(yōu)化的一個過程。是計(jì)劃、安排、比較、決策優(yōu)化的一個過程。英文名：英文名：, ,港臺地區(qū)譯為：港臺地區(qū)譯為：作業(yè)研究作業(yè)研究、運(yùn)作研究運(yùn)作研究。五十年代末華羅庚。五十年代末華羅庚等人介紹國外這一門新興學(xué)科時就建議定名為：運(yùn)等人介紹國外這一門新興學(xué)科時就建議定名為：運(yùn)籌學(xué)。近幾十年來隨著計(jì)算機(jī)的普及它的應(yīng)用越來籌學(xué)。近幾十年來隨著計(jì)算機(jī)的普及它的應(yīng)用越來越廣泛。其作用越來

4、越被人們所認(rèn)識。越廣泛。其作用越來越被人們所認(rèn)識。大學(xué)里為什么要開設(shè)大學(xué)里為什么要開設(shè)運(yùn)籌學(xué)運(yùn)籌學(xué)呢呢? ?請自己考慮。請自己考慮。2022-7-5運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法（如分析、試驗(yàn)、運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法（如分析、試驗(yàn)、量化等）來決定如何最佳地運(yùn)營和設(shè)計(jì)各量化等）來決定如何最佳地運(yùn)營和設(shè)計(jì)各種系統(tǒng)的一門學(xué)科。運(yùn)籌學(xué)對經(jīng)濟(jì)管理系種系統(tǒng)的一門學(xué)科。運(yùn)籌學(xué)對經(jīng)濟(jì)管理系統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。以實(shí)現(xiàn)最有效的管理。 2022-7-5:經(jīng)濟(jì)、工商管理；經(jīng)濟(jì)、工商管

5、理；:計(jì)算機(jī)算法的設(shè)計(jì)；計(jì)算機(jī)算法的設(shè)計(jì)；:數(shù)學(xué)理論；數(shù)學(xué)理論；:軍事；軍事；:工業(yè)；農(nóng)、林、牧、漁業(yè)工業(yè)；農(nóng)、林、牧、漁業(yè); ;:醫(yī)學(xué)、生物、理化、遺傳；醫(yī)學(xué)、生物、理化、遺傳；:工程計(jì)劃、安排等工程計(jì)劃、安排等“優(yōu)化優(yōu)化”; ;:學(xué)習(xí)、日常生活、旅游等。學(xué)習(xí)、日常生活、旅游等。2022-7-5運(yùn)籌學(xué)的發(fā)展：三個來源 軍 事 管 理 經(jīng) 濟(jì) 軍事：運(yùn)籌學(xué)的主要發(fā)源地古代軍事運(yùn)籌學(xué)思想中國古代的“孫子兵法”在質(zhì)的論斷中滲透著量的分析（1981年美國軍事運(yùn)籌學(xué)會出版了一本書，書中第一句話就是說孫武子是世界上第一個軍事運(yùn)籌學(xué)的實(shí)踐家），中國古代運(yùn)籌學(xué)思想的例子還有：田忌賽馬、圍魏救趙、行軍運(yùn)糧，等

6、等。國外歷史上的阿基米德、伽利略研究過作戰(zhàn)問題；第一次世界大戰(zhàn)時，英國的蘭徹斯特（Lanchester）提出了戰(zhàn)斗方程，指出了數(shù)量優(yōu)勢、火力和勝負(fù)的動態(tài)關(guān)系；美國的愛迪生為美國海軍咨詢委員會研究了潛艇攻擊和潛艇回避攻擊的問題。通通過研究使原先平均擊落一架敵過研究使原先平均擊落一架敵機(jī)要發(fā)機(jī)要發(fā)2000020000發(fā)炮彈改善為只要發(fā)炮彈改善為只要40004000發(fā)炮彈。發(fā)炮彈。 管理泰勒的時間動作研究、甘特的用于生產(chǎn)計(jì)劃與控制的“甘特圖”、吉爾布雷思夫婦的動作研究等愛爾朗（Erlong）的排隊(duì)論公式19091920年間，丹麥哥本哈根電話公司工程師愛爾朗陸續(xù)發(fā)表了關(guān)于電話通路數(shù)量等方面的分析與計(jì)算

7、公式。尤其是1909年的論文“概率與電話通話理論”，開創(chuàng)了運(yùn)籌學(xué)的重要分支排隊(duì)論。經(jīng)濟(jì)（數(shù)理經(jīng)濟(jì)學(xué)）Von Neumann 與對策論1932年，Von Neumann提出一個廣義經(jīng)濟(jì)平衡模型；1939年，提出了一個屬于宏觀經(jīng)濟(jì)優(yōu)化的控制論模型；1944年，與Morgenstern共著的對策論與經(jīng)濟(jì)行為開創(chuàng)了對策論分支?？低新寰S奇與“生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法”30年代，蘇聯(lián)數(shù)理經(jīng)濟(jì)學(xué)家康托洛維奇從事生產(chǎn)組織與管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪稱運(yùn)籌學(xué)的先驅(qū)著作生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法，其思想和模型被歸入線性規(guī)劃范疇。19571957年起中科院一批數(shù)學(xué)家作了許多令

8、國際年起中科院一批數(shù)學(xué)家作了許多令國際同行稱道的工作：如物資調(diào)運(yùn)問題。同行稱道的工作：如物資調(diào)運(yùn)問題。2020世紀(jì)世紀(jì)7070年代華羅庚先生在中國大力創(chuàng)導(dǎo)推年代華羅庚先生在中國大力創(chuàng)導(dǎo)推廣廣“統(tǒng)籌學(xué)統(tǒng)籌學(xué)”當(dāng)時就獲得第一代領(lǐng)導(dǎo)人的首當(dāng)時就獲得第一代領(lǐng)導(dǎo)人的首肯，在國際數(shù)學(xué)界被稱為是全世界最大而有肯，在國際數(shù)學(xué)界被稱為是全世界最大而有成果的一次普及數(shù)學(xué)的創(chuàng)舉。成果的一次普及數(shù)學(xué)的創(chuàng)舉。凡是講圖論的優(yōu)化的教科書，多半有專門的凡是講圖論的優(yōu)化的教科書，多半有專門的一章名：一章名：C Chinese hinese P Postman ostman P Problems,roblems,其中無其中無一例

9、外的要提到管梅谷先生的杰出工作：一例外的要提到管梅谷先生的杰出工作：2022-7-5運(yùn)籌學(xué)在實(shí)踐中運(yùn)籌學(xué)在實(shí)踐中的一些應(yīng)用效果的一些應(yīng)用效果組織組織應(yīng)用應(yīng)用年年每年節(jié)約開支（美元）每年節(jié)約開支（美元）聯(lián)合航空公司聯(lián)合航空公司為滿足乘客需求的以最底為滿足乘客需求的以最底的成本進(jìn)行訂票出和機(jī)場的成本進(jìn)行訂票出和機(jī)場的工作班次排程的工作班次排程19861986600600萬萬CitgoCitgo石油公司石油公司優(yōu)化煉油運(yùn)作以及產(chǎn)品的優(yōu)化煉油運(yùn)作以及產(chǎn)品的供應(yīng)配送和營銷供應(yīng)配送和營銷1987198770007000萬萬舊金山警署舊金山警署用計(jì)算機(jī)系統(tǒng)最優(yōu)排程和用計(jì)算機(jī)系統(tǒng)最優(yōu)排程和巡警設(shè)置巡警設(shè)置19

10、89198911001100萬萬IBMIBM整合備件庫存的全國網(wǎng)絡(luò)整合備件庫存的全國網(wǎng)絡(luò)以改進(jìn)服務(wù)支持以改進(jìn)服務(wù)支持1990199020002000萬萬施樂公司施樂公司維修用戶機(jī)器的戰(zhàn)略修正維修用戶機(jī)器的戰(zhàn)略修正以縮短反應(yīng)時間和改進(jìn)維以縮短反應(yīng)時間和改進(jìn)維修人員生產(chǎn)率修人員生產(chǎn)率19751975生產(chǎn)率提高生產(chǎn)率提高50%50%寶潔公司寶潔公司重新設(shè)計(jì)北美生產(chǎn)和分銷重新設(shè)計(jì)北美生產(chǎn)和分銷系統(tǒng)以降低成本、改進(jìn)市系統(tǒng)以降低成本、改進(jìn)市場進(jìn)入速度場進(jìn)入速度199719972 2億億中國中國為滿足國家未來能源需求為滿足國家未來能源需求的大型項(xiàng)目的優(yōu)選和排程的大型項(xiàng)目的優(yōu)選和排程199519954.254

11、.25億億美洲航空公司美洲航空公司為機(jī)組人員和服務(wù)人員優(yōu)為機(jī)組人員和服務(wù)人員優(yōu)化配置航行支線的順序化配置航行支線的順序1991199120002000萬萬IBMIBM重組它的全球供應(yīng)鏈，在重組它的全球供應(yīng)鏈，在保持最小庫存的同時更快保持最小庫存的同時更快滿足顧客滿足顧客20002000第一年第一年7.57.5億億美洲航空公司美洲航空公司設(shè)計(jì)票價結(jié)構(gòu)、訂票和協(xié)設(shè)計(jì)票價結(jié)構(gòu)、訂票和協(xié)調(diào)航班的系統(tǒng)來增加收入調(diào)航班的系統(tǒng)來增加收入199219925 5億，更多收入億，更多收入管理管理運(yùn)籌學(xué)運(yùn)籌學(xué)的工作程序的工作程序明確問題明確問題問題分類問題分類建立數(shù)學(xué)模型建立數(shù)學(xué)模型求解數(shù)學(xué)模型求解數(shù)學(xué)模型結(jié)果分析

12、結(jié)果分析實(shí)施實(shí)施:規(guī)劃論規(guī)劃論( (分線性、非線性、整數(shù)、目標(biāo)、動分線性、非線性、整數(shù)、目標(biāo)、動態(tài)及隨機(jī)規(guī)劃等態(tài)及隨機(jī)規(guī)劃等) ):圖論與網(wǎng)絡(luò)優(yōu)化；圖論與網(wǎng)絡(luò)優(yōu)化；:排隊(duì)論、存儲論、搜索論；排隊(duì)論、存儲論、搜索論；:對策論對策論( (博弈論博弈論) )、；、；:可靠性理論可靠性理論; ;:全面質(zhì)量管理全面質(zhì)量管理(TQC);(TQC);:計(jì)劃評審、維修更新理論等。計(jì)劃評審、維修更新理論等。課程教材：課程教材：吳育華吳育華,杜綱杜綱. 管理科學(xué)基礎(chǔ)管理科學(xué)基礎(chǔ)，天津大學(xué)出版社，天津大學(xué)出版社， 主要參考書：主要參考書：胡運(yùn)權(quán)，運(yùn)籌學(xué)教程，北京：清華大學(xué)出版社，胡運(yùn)權(quán)，運(yùn)籌學(xué)教程，北京：清華大學(xué)出

13、版社，2007；錢頌迪等，運(yùn)籌學(xué)，北京：清華大學(xué)出版社，錢頌迪等，運(yùn)籌學(xué)，北京：清華大學(xué)出版社，1990；美美弗雷德里克弗雷德里克S希利爾（希利爾（Frederick S Hillier）,任建標(biāo)譯任建標(biāo)譯,數(shù)據(jù)、數(shù)據(jù)、模型與決策（原書名模型與決策（原書名 Introduction to Management Science），北），北京：中國財(cái)政經(jīng)濟(jì)出版社，京：中國財(cái)政經(jīng)濟(jì)出版社，2004；謝金星，謝金星， 優(yōu)化建模優(yōu)化建模LINDO/LINGO軟件，清華大學(xué)出版社軟件，清華大學(xué)出版社 丁以中主編，管理科學(xué)丁以中主編，管理科學(xué)-運(yùn)用運(yùn)用Spreadsheet建模和求解，北京：建模和求解，北京

14、：清華大學(xué)出版社，清華大學(xué)出版社，2003； 主要授課內(nèi)容：主要授課內(nèi)容： 線性規(guī)劃線性規(guī)劃:模型與圖解法，單純形法，模型與圖解法，單純形法，對偶與靈敏度分析，運(yùn)輸問題，線性對偶與靈敏度分析，運(yùn)輸問題，線性整數(shù)規(guī)劃整數(shù)規(guī)劃 圖論與網(wǎng)絡(luò)分析圖論與網(wǎng)絡(luò)分析 網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃動態(tài)規(guī)劃動態(tài)規(guī)劃 風(fēng)險型決策風(fēng)險型決策 排隊(duì)論排隊(duì)論隨機(jī)模擬隨機(jī)模擬課程基本要求掌握好基本概念、主要模型形式及其特點(diǎn)、適當(dāng)掌握好基本概念、主要模型形式及其特點(diǎn)、適當(dāng)?shù)慕Ｄ芰?，必要的算法原理及簡單的?jì)算的建模能力，必要的算法原理及簡單的計(jì)算具備計(jì)算機(jī)解題的基本能力具備計(jì)算機(jī)解題的基本能力認(rèn)真聽課，勤于思考，多看書認(rèn)真聽課，勤于思

15、考，多看書每周三交作業(yè)，獨(dú)立完成每周三交作業(yè)，獨(dú)立完成閉卷考試閉卷考試有問題請有問題請EmailEmail聯(lián)系聯(lián)系第一章第一章 線性規(guī)劃線性規(guī)劃（Linear Programming，簡稱，簡稱LP）1 線性規(guī)劃的模型與圖解法線性規(guī)劃的模型與圖解法一、一、LP問題及其數(shù)學(xué)模型問題及其數(shù)學(xué)模型例例1 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源，有關(guān)單耗數(shù)據(jù)如表，試擬定使總收入油三種資源，有關(guān)單耗數(shù)據(jù)如表，試擬定使總收入最大的生產(chǎn)計(jì)劃。最大的生產(chǎn)計(jì)劃。127單價單價300103油油20054電電36049煤煤資源限制資源限制乙乙甲甲產(chǎn)品產(chǎn)品資源資

16、源甲甲乙乙資源限制資源限制煤煤94360電電45200油油310300單價單價712產(chǎn)品產(chǎn)品資源資源線性規(guī)劃模型三要素：線性規(guī)劃模型三要素：（1）決策變量）決策變量 設(shè)甲產(chǎn)品生產(chǎn)設(shè)甲產(chǎn)品生產(chǎn)x1，乙產(chǎn)品生產(chǎn)，乙產(chǎn)品生產(chǎn)x2（2）目標(biāo)函數(shù)）目標(biāo)函數(shù) Max Z=7 x1 +12x2（3）約束條件）約束條件9 x1 +4x23604x1 +5x2 2003 x1 +10 x2 300 x1 , x20s.t.返回Subject To， 意為意為“使其滿使其滿足足”Max （Min） Z = c1 x1 + c2 x2 + + cn xn a11 x1 + a12 x2 + + a1n xn （ =

17、, ）b1 am1 x1 + am2 x2 + + amn xn （ =, ）bmx1 ，x2 ， ，xn 0s.t. LP模型的一般形式模型的一般形式矩陣表示矩陣表示Max Z = CXAX bX 0s.t.其中其中: X= (x1,x2, , xn) T 為決策變量為決策變量 C=(c1,c2, , cn) 稱為稱為價格系數(shù)價格系數(shù)A=(aij)mn 稱為稱為技術(shù)系數(shù)技術(shù)系數(shù)b= (b1,b2, , bm) T 稱為稱為資源系數(shù)資源系數(shù)例2 某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應(yīng)量見下表：要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安

18、排各住宅多少m2)，求建造方案。水泥水泥(公斤公斤/m2)4000(千工日千工日)147000(千塊千塊)150000(噸噸)20000(噸噸)110000(千元千元)資源限量資源限量3.518025120大模住宅大模住宅3.019030135壁板住宅壁板住宅4.521011012105磚混住宅磚混住宅人工人工(工日工日/m2)磚磚(塊塊/m2)鋼材鋼材(公斤公斤/m2)造價造價(元元/m2) 資源資源住宅體系住宅體系 解: 設(shè)今年計(jì)劃修建磚混、壁板、大模住宅各為 x1,x2,x3 m2, z為總面積,則本問題的數(shù)學(xué)模型為:0,40000035. 0003. 00045. 0147000210

19、. 0150000180. 0190. 0110. 020000025. 0030. 0012. 0110000120. 0135. 0105. 0.3213211321321321xxxxxxxxxxxxxxxxts321xxxMaxz 前蘇聯(lián)的尼古拉也夫斯克城住宅興建計(jì)劃采用了上述模型，共用了前蘇聯(lián)的尼古拉也夫斯克城住宅興建計(jì)劃采用了上述模型，共用了12個變量，個變量，10個約束條件。個約束條件。課堂練習(xí)課堂練習(xí) 某蓄場每日要為每頭牲畜購買飼料，以使其某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的獲取所需的A、B、C、D四種養(yǎng)分。有關(guān)數(shù)據(jù)四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的如

20、下表，現(xiàn)飼料可從市場上出售的M、N兩種飼兩種飼料中選擇，試決定總花費(fèi)最小的購買方案。料中選擇，試決定總花費(fèi)最小的購買方案。（列出模型）（列出模型）ABCD價格價格M0.50.20.30300N0.10.30.40.2200每頭每頭日需日需10587養(yǎng)分養(yǎng)分飼料飼料課堂練習(xí)課堂練習(xí) 某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選兩種飼料中選擇，試決定總花費(fèi)最小的購買方案。（列出模型）擇，試決定總花費(fèi)最小的購買方案。（列出

21、模型）ABCD價格價格M0.50.20.30300N0.10.30.40.2200每頭日需每頭日需10587養(yǎng)分養(yǎng)分飼料飼料答案：答案：設(shè)購買設(shè)購買M飼料飼料x1，N飼料飼料x20.5 x1 +0.1x2100.2x1 +0.3x2 50.3x1 +0.4x2 8 0.2x2 7x1 , x20s.t.Min Z=300 x1 +200 x2思考題思考題二、線性規(guī)劃的圖解法二、線性規(guī)劃的圖解法1. 步驟步驟（1）作約束的圖形）作約束的圖形可行域可行域可行解的集合可行解的集合先作非負(fù)約束先作非負(fù)約束再作資源約束再作資源約束9x1+4x2=3604x1+5x2=2003x1+10 x2=300公共

22、部分，即為可行域公共部分，即為可行域例：煤電油例例：煤電油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10 x2 300 x1 , x20s.t.x1x240206080100204060801000（2）作目標(biāo)函數(shù)的等值線）作目標(biāo)函數(shù)的等值線給給z不同的值，作相應(yīng)直線，判斷出不同的值，作相應(yīng)直線，判斷出z增大時，直線的移動方向增大時，直線的移動方向?qū)⒅本€向增大方向移動，直至可行域?qū)⒅本€向增大方向移動，直至可行域邊界，交點(diǎn)邊界，交點(diǎn)X*即為最優(yōu)解。即為最優(yōu)解。7x1+12x2=847x1+12x2=168如：令如：令7 x1 +12x2=84

23、7 x1 +12x2=1689x1+4x2=3604x1+5x2=2003x1+10 x2=300 x1x240206080100204060801000X*=（20，24），），Z*=428最優(yōu)解：最優(yōu)解： x1 = 0， x2 = 1 最優(yōu)目標(biāo)值最優(yōu)目標(biāo)值 z = 3課堂練習(xí)課堂練習(xí)圖解法求解線性規(guī)劃圖解法求解線性規(guī)劃 0,)3(22)2(22)1(432min2121212121xxxxxxxxstxxz0 01 12 23 34 41 12 23 34 4x1x2O O-1-1-2-2(1)(2)(3)2. LP 解的幾種情況解的幾種情況（1）唯一解）唯一解（2）多重最優(yōu)解）多重最優(yōu)解

24、（3）無可行解）無可行解注：出現(xiàn)（注：出現(xiàn)（3）、（）、（4）情況時，建模有問題）情況時，建模有問題（4）無有限最優(yōu)解）無有限最優(yōu)解補(bǔ)充知識：凸集凸集：在點(diǎn)集中任取兩點(diǎn)，則其連線仍在其中。即沒有凹入的部分；沒有空洞。在凸集中，點(diǎn)A，B，C，D稱為極點(diǎn)（或頂點(diǎn)）。ABCD從圖解法中我們了解到以下事實(shí)：若LP問題的可行域存在，則可行域一定是凸集。若LP問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無窮多最優(yōu)解的話）一定是可行域凸集的某個極點(diǎn)（頂點(diǎn)）。思路：最優(yōu)解先在可行域中找。（可行域?yàn)榭占?，則無可行解，故無最優(yōu)解。）最優(yōu)解在可行域的極點(diǎn)中找。極點(diǎn)是有限個，若兩個極點(diǎn)都是最優(yōu)解，則兩個極點(diǎn)所連線段

25、上的所有點(diǎn)均是最優(yōu)解）定義：LP問題的可行域的極點(diǎn)（頂點(diǎn)）稱為基本可行解。第二節(jié) 單純形法 單純形法是求解線性規(guī)劃的主要算法，單純形法是求解線性規(guī)劃的主要算法，19471947年由美國斯坦福大學(xué)教授丹捷格（年由美國斯坦福大學(xué)教授丹捷格（G.B.DanzigG.B.Danzig）提出。提出。 盡管在其后的幾十年中，又有一些算法問世，盡管在其后的幾十年中，又有一些算法問世，但單純形法以其簡單實(shí)用的特色始終保持著絕對但單純形法以其簡單實(shí)用的特色始終保持著絕對的的“市場市場”占有率。占有率。1.1.線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型 用單純形法求解線性規(guī)劃的前提是先將模用單純形法求解線性規(guī)劃的前提是先將

26、模型化為標(biāo)準(zhǔn)型：型化為標(biāo)準(zhǔn)型：0. .XbAXtsCXMaxz 標(biāo)準(zhǔn)型的特征：標(biāo)準(zhǔn)型的特征：MaxMax型、等式約束、非負(fù)約束型、等式約束、非負(fù)約束一、單純形法的預(yù)備知識一、單純形法的預(yù)備知識。）（的秩為其中，0,bnmmAnm非標(biāo)準(zhǔn)形式如何化為標(biāo)準(zhǔn)非標(biāo)準(zhǔn)形式如何化為標(biāo)準(zhǔn)1) 1) MinMin型化為型化為MaxMax型型 CXMinzCXMaxz/加負(fù)號加負(fù)號 因?yàn)?，求一個函數(shù)因?yàn)椋笠粋€函數(shù)的極小點(diǎn)，等價于求該的極小點(diǎn)，等價于求該函數(shù)的負(fù)函數(shù)的極大點(diǎn)。函數(shù)的負(fù)函數(shù)的極大點(diǎn)。)(xf)(xf*x注意：注意： MinMin型化為型化為MaxMax型求解后，最優(yōu)解不變，但最優(yōu)值差負(fù)號。型求解后，

27、最優(yōu)解不變，但最優(yōu)值差負(fù)號。 2) 不等式約束化為等式約束不等式約束化為等式約束分析：分析：以例以例1中煤的約束為例中煤的約束為例3604921 xx之所以之所以“不等不等”是因?yàn)樽笥覂蛇呌幸粋€差額，稱為是因?yàn)樽笥覂蛇呌幸粋€差額，稱為“松松弛量弛量”，若在左邊加上這個松弛量，則化為等式。而這，若在左邊加上這個松弛量，則化為等式。而這個松弛量也是變量，記為個松弛量也是變量，記為X X3 3 ，則有，則有36049321xxxX X3 3稱為松弛變量。問題：稱為松弛變量。問題：它的實(shí)際意義是什么？它的實(shí)際意義是什么？ 煤資源的煤資源的“剩余剩余”。練習(xí)：請將例練習(xí)：請將例1的約束化為標(biāo)準(zhǔn)型的約束化

28、為標(biāo)準(zhǔn)型0,3001032005436049.21212121xxxxxxxxts解：增加松弛變量解：增加松弛變量則約束化為則約束化為,543xxx0,300 10320054360 49.54321521421321xxxxxxxxxxxxxxts易見，增加的松弛變量的系數(shù)恰構(gòu)成一個單位陣易見，增加的松弛變量的系數(shù)恰構(gòu)成一個單位陣I I。一般地，記松弛變量的向量為一般地，記松弛變量的向量為 Xs，則，則0. .XbAXts0,. .ssXXbIXAXts0. .XbAXts0,. .ssXXbIXAXts問題：松弛變量在目標(biāo)中的系數(shù)為何？問題：松弛變量在目標(biāo)中的系數(shù)為何？ 0 0。 3) 3

29、) 當(dāng)模型中有某變量當(dāng)模型中有某變量 x xk k 沒有非負(fù)要求，沒有非負(fù)要求，稱稱為自由變量為自由變量, , 則可令則可令 0,/kkkkkxxxxx化為標(biāo)準(zhǔn)型。化為標(biāo)準(zhǔn)型。復(fù)習(xí)：非齊次線性方程組解例：解非齊次線性方程組5242615552142132xxxxxxxx增廣矩陣（1）51001124010261500150A1x2x3x4x5xb若線性方程組沒有現(xiàn)成的基，可利用增廣矩陣的行初等變換法找到一組基。為基變量。稱,3x,4x5x其變量個數(shù)=3)()(ArAr此方程組的解為2152142352624515xxxxxxxx其中,1x2x為任意實(shí)數(shù)。為非基變量，或自由變量。2x,1x稱稱非

30、基變量,1x2x為0的解（15，24，5，0，0）叫基解。TX)5 ,24,15, 0 , 0(0若對（1）式中的變量再加上非負(fù)限制2152142352624515xxxxxxxx5 , 105242615552142132ixxxxxxxxxi其解為5 , 105262451521521423ixxxxxxxxxi由的非負(fù)性知：,3x,4x5x（2）04531x2x5 , 100502624051521521423ixxxxxxxxxi05152 x50521xx0262421xx從而,1x2x解域?yàn)樽⒁猓捍藭r的,1x2x已經(jīng)不是任意實(shí)數(shù)。不是自由變量了。而對于帶有非負(fù)約束的方程組解的每個分

31、量都是非負(fù)數(shù)，就叫做可行解。如果基解是可行的，就叫基可行解?；尚薪馑鶎?yīng)的基稱為可行基。 非基可行 最優(yōu)基基 非 可 行 基四種形式的基之間的關(guān)系為：基與解的對應(yīng)關(guān)系： 非可行解可行 基本解 可行解 基本解解與解之間的關(guān)系為：基解基可行基基可行解最優(yōu)基基最優(yōu)解5 , 100502624051521521423ixxxxxxxxxi, 11x22x所對應(yīng)的解例如T)2,14,10,2, 1(是可行解。,01x02x所對應(yīng)的解T)5,24,15,0,0(是基解。也是可行解，故而是基本可行解。2.基本概念（1）可行解與最優(yōu)解）可行解與最優(yōu)解；的解，記為可行解：滿足全體約束X。，有解則對任可行的，記

32、為最優(yōu)解：可行解中最優(yōu)* ,CXCXXX直觀上，直觀上，可行解是可行域中的點(diǎn)，是一個可行的方案；可行解是可行域中的點(diǎn)，是一個可行的方案； 最優(yōu)解是可行域的角點(diǎn)，是一個最優(yōu)的方案。最優(yōu)解是可行域的角點(diǎn)，是一個最優(yōu)的方案。（2）基矩陣與基變量基矩陣基矩陣(簡稱基簡稱基)：系數(shù)陣系數(shù)陣A中的中的m階可逆子陣，記階可逆子陣，記 為為B；其余部分稱為非基矩陣，記為；其余部分稱為非基矩陣，記為N?；蛄浚夯蛄浚夯鵅中的列；其余稱非基向量。中的列；其余稱非基向量?；兞浚夯兞浚号c基向量與基向量Pj對應(yīng)的決策變量對應(yīng)的決策變量xj，記其組成的記其組成的 向量為向量為XB；與非基向量對應(yīng)的變量稱非基；與非

33、基向量對應(yīng)的變量稱非基變變 量，記其組成的向量為量，記其組成的向量為XN。1231241432 12 3,0 xxxxxxxx例 ：下面為某線性規(guī)劃的約束請例舉出其基矩陣和相應(yīng)的基向量、基變量。1231241432123,0 xxxxxxxx例 ：下面為某線性規(guī)劃的約束請例舉出其基矩陣和相應(yīng)的基向量、基變量。階可逆子陣有中的，解：本例中，210011221AA 6 6個。個。一般地，一般地，m mn n 階矩陣階矩陣A A中基的個數(shù)最多有多少個？中基的個數(shù)最多有多少個？個。mnC;,100143434311xxXxxPPBB，基變量為，其相應(yīng)的基向量為?；兞繛槠湎鄳?yīng)的基向量為21212122

34、,1221xxXxxPPBB問題：本例的問題：本例的A A中一共有幾個基？中一共有幾個基？（3）基本解與基本可行解）基本解與基本可行解.0,0, ,1111bBXbBXXNXBbBXbXXNBbAXXXXNBAmABBABkkBkBTkB時，有當(dāng)取即可表示為約束中的相應(yīng)地）（列，則可記中的前表示取定后，不妨設(shè)中的基當(dāng)解；為線性規(guī)劃的一個基本的解稱0NbBXbAX可見：一個基本解是由一個基決定的?？梢姡阂粋€基本解是由一個基決定的。注意：基本解僅是資源約束的解，并未要求其非負(fù)，因此其未必可行。注意：基本解僅是資源約束的解，并未要求其非負(fù)，因此其未必可行。稱非負(fù)的基本解為稱非負(fù)的基本解為基本可行解基

35、本可行解（簡稱基可行解）。（簡稱基可行解）。例例4：在上例中：在上例中0,321241421321xxxxxxxx 求相應(yīng)于基求相應(yīng)于基B1和和B2的基本解，它們是否基本可行解？的基本解，它們是否基本可行解？,31311001,1001,1001111bBBBNN解：是基本可行解。的基本解為相應(yīng)于基,)3 ,1 ,0 ,0(NTXB,51-573151-525251,51-525251,1-221112bBBBOO不是基本可行解。的基本解為相應(yīng)于基,0,0)51,-57(2TXB上二組概念間的聯(lián)系：系數(shù)陣系數(shù)陣A中可找出若干個基中可找出若干個基B每個基每個基B都對應(yīng)于一個基本解都對應(yīng)于一個基本

36、解非負(fù)的基本解就是基本可行解非負(fù)的基本解就是基本可行解幾種解之間的關(guān)系：幾種解之間的關(guān)系：可行解可行解基本解基本解非可行解非可行解基本可行解基本可行解問題：基本可行解是可行域中的哪些點(diǎn)？問題：基本可行解是可行域中的哪些點(diǎn)？3.基本定理（1 1）線性規(guī)劃的可行域是一個凸多面體。）線性規(guī)劃的可行域是一個凸多面體。（2 2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行 域的角點(diǎn)獲得。域的角點(diǎn)獲得。（3 3）線性規(guī)劃可行域的角點(diǎn)與基本可行解一一對應(yīng)。）線性規(guī)劃可行域的角點(diǎn)與基本可行解一一對應(yīng)。二、單純形法的步驟確定一個初始基可行解確定一個初始基可行解檢驗(yàn)這個基可行

37、解是否最優(yōu)檢驗(yàn)這個基可行解是否最優(yōu)尋找一個更好的基可行解尋找一個更好的基可行解否否是是停停止止 Dantzig Dantzig的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解（即可行的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解（即可行域頂點(diǎn)）中。域頂點(diǎn)）中。 其基本思路是從一個初始的基本可行解出發(fā)，尋找一條達(dá)到其基本思路是從一個初始的基本可行解出發(fā)，尋找一條達(dá)到 最優(yōu)基本可行解的最佳途徑。最優(yōu)基本可行解的最佳途徑。 單純形法的一般步驟如下：單純形法的一般步驟如下： （1 1）尋找一個初始的基本可行解。）尋找一個初始的基本可行解。 （2 2）檢查現(xiàn)行的基本可行解）檢查現(xiàn)行的基本可行解是否最優(yōu)是否最優(yōu)，如

38、果為最優(yōu)，如果為最優(yōu)， 則停止迭代則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。，已找到最優(yōu)解，否則轉(zhuǎn)一步。 （3 3）移至目標(biāo)函數(shù)值有所）移至目標(biāo)函數(shù)值有所改善改善的另一個基本可行解，然后轉(zhuǎn)會到步的另一個基本可行解，然后轉(zhuǎn)會到步驟（驟（2 2）。）。 1.確定初始基可行解 由于基可行解是由一個可行基決定的，因此，由于基可行解是由一個可行基決定的，因此，確定初始基可行解確定初始基可行解X X0 0相當(dāng)于確定一個初始可行基相當(dāng)于確定一個初始可行基B B0 0。方法：方法：若若A中含中含I，則，則B0=I； 若若A中不含中不含I，則可用人工變量法構(gòu)，則可用人工變量法構(gòu) 造一個造一個I。問題：若問題：若B0

39、=I，則，則X0=？可行。,000NMMbbBX2. 最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)問題：用什么檢驗(yàn)？問題：用什么檢驗(yàn)？ 目標(biāo)。目標(biāo)。kBkBkkkBkbkBXNBCCbBCXCNXBbBCXXCCCXz)(NN)()(11而目標(biāo)優(yōu)。時，當(dāng)前基可行解為最，則當(dāng)記 01NBCCBk非最優(yōu)。則當(dāng)前解為最優(yōu)；否則若的檢驗(yàn)數(shù)方法：計(jì)算每個變量0, ,1jjBjjjPBCcx問題：非最優(yōu)的特征為何？問題：非最優(yōu)的特征為何？。至少有某個檢驗(yàn)數(shù)0kn判斷現(xiàn)行的基本可行解是否最優(yōu)判斷現(xiàn)行的基本可行解是否最優(yōu) 假如已求得一個基本可行解假如已求得一個基本可行解將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值將這一基本可

40、行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值其中分別表示基變量和其中分別表示基變量和非基變量所對應(yīng)的價值系數(shù)子向量。非基變量所對應(yīng)的價值系數(shù)子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c )要判定是否已經(jīng)達(dá)到最大值，只需將要判定是否已經(jīng)達(dá)到最大值，只需將代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非基變量基變量表示，即：表示，即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中其中 稱為非基變量稱為非基變量N N的檢驗(yàn)向量，它的各個分量稱為

41、檢驗(yàn)數(shù)。若的檢驗(yàn)向量，它的各個分量稱為檢驗(yàn)數(shù)。若N N的每一個檢驗(yàn)數(shù)均小的每一個檢驗(yàn)數(shù)均小于等于于等于0 0，即，即N N00，那么現(xiàn)在的基本可行解就是最優(yōu)解。，那么現(xiàn)在的基本可行解就是最優(yōu)解。-1-1BNX=B b-B NX-1BZ=C B b-1NNBm+1m+1n=C -C B N=(,)BBNN-1-1BBNNBNNN-1-1BNBNXZ=CX=(C C )X=C X +C X =C (B b-B NX )+C X=C B b+(C -C B N)X定理定理1 1：最優(yōu)解判別定理：最優(yōu)解判別定理 對于線性規(guī)劃問題對于線性規(guī)劃問題若某個基本可行解所對應(yīng)的檢驗(yàn)向量，若某個基本可行解所對應(yīng)的

42、檢驗(yàn)向量，則這個基本可行解就是最優(yōu)解。則這個基本可行解就是最優(yōu)解。定理定理2 2：無窮多最優(yōu)解判別定理：無窮多最優(yōu)解判別定理 若是一個基本可行解，所對應(yīng)的檢驗(yàn)向量若是一個基本可行解，所對應(yīng)的檢驗(yàn)向量，其中存在一個檢驗(yàn)數(shù)，其中存在一個檢驗(yàn)數(shù)m+km+k=0=0，則線性規(guī)劃問題有無窮多最優(yōu)解。則線性規(guī)劃問題有無窮多最優(yōu)解。nmaxZ=CX, D= XR /AX=b,X0-1NNB=C -C B N01B bX=0-1NNB=C -C B N0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )xn 基本可行解的改進(jìn)基本可行解的改進(jìn) 如果現(xiàn)行的基本可行解不是最優(yōu)解，即在檢驗(yàn)向量如果現(xiàn)行的基

43、本可行解不是最優(yōu)解，即在檢驗(yàn)向量 中存在正的檢驗(yàn)數(shù)，則需在原基本可行解的基中存在正的檢驗(yàn)數(shù)，則需在原基本可行解的基礎(chǔ)上尋找一個新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體礎(chǔ)上尋找一個新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：做法是： 先從檢驗(yàn)數(shù)為正的非基變量中確定一個換入變量，使它從非基先從檢驗(yàn)數(shù)為正的非基變量中確定一個換入變量，使它從非基變量變成基變量（將它的值從零增至正值），變量變成基變量（將它的值從零增至正值）， 再從原來的基變量中確定一個換出變量，使它從基變量變成非再從原來的基變量中確定一個換出變量，使它從基變量變成非基變量（將它的值從正值減至零）?；兞浚▽⑺闹祻恼禍p至

44、零）。由此可得一個新的基本可行解，由由此可得一個新的基本可行解，由 可知，這樣的變換一定能使目標(biāo)函數(shù)值有所增加?？芍?，這樣的變換一定能使目標(biāo)函數(shù)值有所增加。-1NNB=C -C B Nm+1m+2-1Bm+1,m+1,nnxxZC B b+( )x 換入變量和換出變量的確定換入變量和換出變量的確定：l換入變量的確定換入變量的確定 最大增加原則最大增加原則 假設(shè)檢驗(yàn)向量假設(shè)檢驗(yàn)向量 ， 若其中有兩個以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快若其中有兩個以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快些，通常要用些，通常要用“最大增加原則最大增加原則”，即選取最大正檢驗(yàn)數(shù)所對應(yīng)的非基，即選取最大

45、正檢驗(yàn)數(shù)所對應(yīng)的非基變量為換入變量，即若變量為換入變量，即若 則選取對應(yīng)的則選取對應(yīng)的 為換入變量，為換入變量， 由于且為最大，由于且為最大， 因此當(dāng)由零增至正值，因此當(dāng)由零增至正值，可使目標(biāo)函數(shù)值可使目標(biāo)函數(shù)值 最大限度的增加。最大限度的增加。-1NNBm+1m+2n=C -C B N=(,)jjm+kmax | 0,m+1jn = m+kxm+kxm+k0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )xl 換出變量的確定換出變量的確定 最小比值原則最小比值原則 如果確定為換入變量，方程如果確定為換入變量，方程其中為中與對應(yīng)的系數(shù)列向量。其中為中與對應(yīng)的系數(shù)列向量?，F(xiàn)在需在現(xiàn)

46、在需在 中確定一個基變量為換出變量。中確定一個基變量為換出變量。 當(dāng)由零慢慢增加到某個值時，當(dāng)由零慢慢增加到某個值時， 的非負(fù)性可能被打破。的非負(fù)性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量：為保持解的可行性，可以按最小比值原則確定換出變量： 若若B12mX =(x ,x ,x )T-1-1-1im+ki-1-1m+kim+k(B b)(B b)=min|(B P) 0,1im =(B P)(B P)ll m+kx-1-1-1-1BNBm+km+kX=B b-B NXX=B b-B Pxm+kPm+kxm+kx則選取對應(yīng)的基變量則選取對應(yīng)的基變量 為換出變量。為換出變量。 x

47、lBX 定理定理3 3：無最優(yōu)解判別定理：無最優(yōu)解判別定理 若若 是一個基本可行解，有一個檢驗(yàn)數(shù)是一個基本可行解，有一個檢驗(yàn)數(shù) ，但是，則該線性規(guī)劃問題無最優(yōu)解。但是，則該線性規(guī)劃問題無最優(yōu)解。1B bX=0-1m+kB P0m+k0證：令證：令 ，則得新的可行解，則得新的可行解將上式代入將上式代入因?yàn)橐驗(yàn)?, , 故當(dāng)故當(dāng)+時，時，Z+Z+。-1-1-1-1Bm+km+km+kX =B b-B PxB b-B Pm+1-1-1Bm+1m+knBm+knxZ=C B b+(, )C B b+x m+kx,(0) m+k0尋找更好的基可行解 由于基可行解與基對應(yīng)，即尋找一個新的基可行由于基可行解

48、與基對應(yīng)，即尋找一個新的基可行解，相當(dāng)于從上一個基解，相當(dāng)于從上一個基B0變換為下一個新的基變換為下一個新的基B1，因，因此，本步驟也稱為基變換。此，本步驟也稱為基變換。（基變換）（基變換）0NNMNbBzz可行：改善：基變換的原則）變換的方法：（nklPPPP,N進(jìn)基進(jìn)基出基出基進(jìn)基；對應(yīng)的令保證“改善”進(jìn)基kkP0可決定出基。由保證“可行”出基011kBNXBbBX 出基。對應(yīng)的令進(jìn)基；對應(yīng)的方法：令likikiiilkjjkPPBPBbBP0)()()(0111minmax稱作檢驗(yàn)比。i 以例以例1 1為例，可按上述單純形法的步驟求出其最優(yōu)解，其為例，可按上述單純形法的步驟求出其最優(yōu)解，

49、其大致的過程如下。大致的過程如下。（1 1）先將模型化為標(biāo)準(zhǔn)型）先將模型化為標(biāo)準(zhǔn)型0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz(2) (2) 確定初始基可行解、檢驗(yàn)確定初始基可行解、檢驗(yàn);00,300)(0,0,360,2,00)(360,200,3,0100TTXbBB111;,5OPP向量為再計(jì)算檢驗(yàn)比確定出基量為計(jì)算檢驗(yàn)數(shù)確定進(jìn)基向（3 3）換基、計(jì)算下一個基可行解、再檢驗(yàn)，直至最優(yōu)）換基、計(jì)算下一個基可行解、再檢驗(yàn)，直至最優(yōu);50,0)(0,24,240,)(240,50,30,1051411111TTXbB

50、B;0,0)(20,24,84,(84,20,24),103544912122TTXbBB00;,41PP向量為再計(jì)算檢驗(yàn)比確定出基量為計(jì)算檢驗(yàn)數(shù)確定進(jìn)基向前解為最優(yōu)。計(jì)算檢驗(yàn)數(shù)均非正，當(dāng)問題：當(dāng)模型規(guī)模較大時，計(jì)算量很大。問題：當(dāng)模型規(guī)模較大時，計(jì)算量很大。事實(shí)上，單純形法的實(shí)現(xiàn)是在單純形表上完成的。事實(shí)上，單純形法的實(shí)現(xiàn)是在單純形表上完成的。三、單純形表 單純形表是基于單純形法的步驟設(shè)計(jì)的計(jì)算格單純形表是基于單純形法的步驟設(shè)計(jì)的計(jì)算格式，是單純形法的具體實(shí)現(xiàn)。式，是單純形法的具體實(shí)現(xiàn)。110101100)()(000BmBbBmBCbBuBikiiijBBjjmi nM回顧單純形法步驟回顧

51、單純形法步驟bBN需計(jì)算ABN需計(jì)算,AbB1內(nèi)容是因此，單純形表的主體 121110AbBAbBAbB 即單純形表。變換迭代計(jì)算的由此設(shè)計(jì)了基于初等行得。也可通過初等行變換求鄰兩個只有一列不同，故相而相鄰兩個 1BB單純形表的主要結(jié)構(gòu)：單純形表的主要結(jié)構(gòu)： X CABNbBN問題：第一張表的問題：第一張表的B-1=？單位陣單位陣I。檢驗(yàn)數(shù)的公式是什么？檢驗(yàn)數(shù)的公式是什么？jBjjPBCcN在哪里？jPBN列中的第jAB1 例5：用單純形法求解例10,3001032005436049.21212121xxxxxxxxts21127xxMaxz將模型化為標(biāo)準(zhǔn)型：解：增加松弛變量,543xxx 0

52、,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz問題：標(biāo)準(zhǔn)模型的問題：標(biāo)準(zhǔn)模型的A中是否含中是否含I？松弛變量系數(shù)恰好構(gòu)成松弛變量系數(shù)恰好構(gòu)成I。的計(jì)算的計(jì)算:XBCBB-1bx1x2x3x4x5四、單純形法的實(shí)現(xiàn)四、單純形法的實(shí)現(xiàn)單純形表單純形表例例：煤電油例：煤電油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10 x2 300 x1 , x20s.t.Max Z=7 x1 +12x29 x1 +4x2 +x3 =3604x1 +5x2 +x4 = 2003 x1 +10

53、 x2 +x5 = 300 x1 ,x50s.t.化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表單純形表:71111PBCcB 77 0 , 0 , 0 349x5x4x3x2x1B-1bCBXB四、單純形法的實(shí)現(xiàn)四、單純形法的實(shí)現(xiàn)單純形表單純形表例例：煤電油例：煤電油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10 x2 300 x1 , x20s.t.Max Z=7 x1 +12x29 x1 +4x2 +x3 =3604x1 +5x2 +x4 = 2003 x1 +10 x2 +x

54、5 = 300 x1 ,x50s.t.化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表單純形表:790的計(jì)算的計(jì)算:11111)()(kPBbB 904360 4030 x5x4x3x2x1B-1bCBXB四、單純形法的實(shí)現(xiàn)四、單純形法的實(shí)現(xiàn)單純形表單純形表例例：煤電油例：煤電油例Max Z=7 x1 +12x29 x1 +4x23604x1 +5x2 2003 x1 +10 x2 300 x1 , x20s.t.Max Z=7 x1 +12x29 x1 +4x2 +x3 =3604x1 +5x2 +x4 = 2003 x1 +10 x

55、2 +x5 = 300 x1 ,x50s.t.化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表單純形表:7904030 樞紐樞紐元素元素x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表單純形表:7904030 x3x4x20012300.31000.1以以10為主元進(jìn)行初等行變換為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.2即即:1111PBCcB 74 . 3 12,0,0 3 .05 .28 .7x5x4x3x2x1

56、B-1bCBXBx3x4x5000360200300943451010001000112000單純形表單純形表:7904030 x3x4x20012300.31000.1以以10為主元進(jìn)行初等行變換為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.2即即:5155PBCcB 02 . 1 12,0,0 1 .05 .04 .030.820100 x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表單純形表:7904030 x3x4x20012300.31000.1以以10為主元進(jìn)行初等行

57、變換為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.230.820100 x3x1x2071224010-0.12 0.16201000.4 -0.284001-3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表單純形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 以以 為主元進(jìn)行初等行變換為主元進(jìn)行初等行變換2.5x3x1x20712

58、24010-0.12 0.16201000.4 -0.284001-3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表單純形表:7904030 x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100 X*=(20,24,84,0,0)T Z*=428例：例：用單純形法求解用單純形法求解Min S= - x1 +2x2x1 - x2 - 2x1 +2x2 6x1 , x20s.t.化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型Ma

59、x S = x1 -2x2-x1 + x2 +x3 = 2x1 +2x2 +x4= 6x1 , ,x40s.t.XBCBB-1bx1x2x3x4x302-1110不考慮不考慮x406120161-2x3080311x11612010-40-1X*=(6,0,8,0)T Z*= -6x3x1x2071224010 -0.120.16201000.4 -0.284001 -3.12 1.16000-1.36 -0.52x5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表單純形表:7904030 x3x4x20012300.310

60、00.1502.5001 -0.5240 7.8010 -0.43.4000 -1.230.820100注：單純形表中的信息注：單純形表中的信息每一列的含義：每一列的含義：B-1(b A)=(B-1b, B-1 P1,， B-1 Pn)每個表中的每個表中的B和和B-1的查找：的查找： B從初表中找；從初表中找； B-1從當(dāng)前表中找，對應(yīng)于從當(dāng)前表中找，對應(yīng)于初表中的初表中的I的位置。的位置。 ),(243PPPB 1000510401 以第以第2個表為例：個表為例： 1B 1 . 0005 . 0104 . 001終表分析終表分析最優(yōu)基最優(yōu)基B* 和和(B*)-1的查找的查找 ),(213*P