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

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

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

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

4、越被人們所認(rèn)識(shí)。越廣泛。其作用越來(lái)越被人們所認(rèn)識(shí)。大學(xué)里為什么要開(kāi)設(shè)大學(xué)里為什么要開(kāi)設(shè)運(yùn)籌學(xué)運(yùn)籌學(xué)呢呢? ?請(qǐng)自己考慮。請(qǐng)自己考慮。2022-7-5運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法（如分析、試驗(yàn)、運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法（如分析、試驗(yàn)、量化等）來(lái)決定如何最佳地運(yùn)營(yíng)和設(shè)計(jì)各量化等）來(lái)決定如何最佳地運(yùn)營(yíng)和設(shè)計(jì)各種系統(tǒng)的一門(mén)學(xué)科。運(yùn)籌學(xué)對(duì)經(jīng)濟(jì)管理系種系統(tǒng)的一門(mén)學(xué)科。運(yùn)籌學(xué)對(duì)經(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ā)展：三個(gè)來(lái)源 軍 事 管 理 經(jīng) 濟(jì) 軍事：運(yùn)籌學(xué)的主要發(fā)源地古代軍事運(yùn)籌學(xué)思想中國(guó)古代的“孫子兵法”在質(zhì)的論斷中滲透著量的分析（1981年美國(guó)軍事運(yùn)籌學(xué)會(huì)出版了一本書(shū)，書(shū)中第一句話(huà)就是說(shuō)孫武子是世界上第一個(gè)軍事運(yùn)籌學(xué)的實(shí)踐家），中國(guó)古代運(yùn)籌學(xué)思想的例子還有：田忌賽馬、圍魏救趙、行軍運(yùn)糧，等

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

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

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

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

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

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

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

13、版社，2007；錢(qián)頌迪等，運(yùn)籌學(xué)，北京：清華大學(xué)出版社，錢(qián)頌迪等，運(yùn)籌學(xué)，北京：清華大學(xué)出版社，1990；美美弗雷德里克弗雷德里克S希利爾（希利爾（Frederick S Hillier）,任建標(biāo)譯任建標(biāo)譯,數(shù)據(jù)、數(shù)據(jù)、模型與決策（原書(shū)名模型與決策（原書(shū)名 Introduction to Management Science），北），北京：中國(guó)財(cái)政經(jīng)濟(jì)出版社，京：中國(guó)財(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)容： 線(xiàn)性規(guī)劃線(xiàn)性規(guī)劃:模型與圖解法，單純形法，模型與圖解法，單純形法，對(duì)偶與靈敏度分析，運(yùn)輸問(wèn)題，線(xiàn)性對(duì)偶與靈敏度分析，運(yùn)輸問(wèn)題，線(xiàn)性整數(shù)規(guī)劃整數(shù)規(guī)劃 圖論與網(wǎng)絡(luò)分析圖論與網(wǎng)絡(luò)分析 網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 風(fēng)險(xiǎn)型決策風(fēng)險(xiǎn)型決策 排隊(duì)論排隊(duì)論隨機(jī)模擬隨機(jī)模擬課程基本要求掌握好基本概念、主要模型形式及其特點(diǎn)、適當(dāng)掌握好基本概念、主要模型形式及其特點(diǎn)、適當(dāng)?shù)慕Ｄ芰?，必要的算法原理及?jiǎn)單的計(jì)算的建模能力，必要的算法原理及簡(jiǎn)單的計(jì)算具備計(jì)算機(jī)解題的基本能力具備計(jì)算機(jī)解題的基本能力認(rèn)真聽(tīng)課，勤于思考，多看書(shū)認(rèn)真聽(tīng)課，勤于思

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

16、源甲甲乙乙資源限制資源限制煤煤94360電電45200油油310300單價(jià)單價(jià)712產(chǎn)品產(chǎn)品資源資源線(xiàn)性規(guī)劃模型三要素：線(xiàn)性規(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， 意為意為“使其滿(mǎn)使其滿(mǎn)足足”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) 稱(chēng)為稱(chēng)為價(jià)格系數(shù)價(jià)格系數(shù)A=(aij)mn 稱(chēng)為稱(chēng)為技術(shù)系數(shù)技術(shù)系數(shù)b= (b1,b2, , bm) T 稱(chēng)為稱(chēng)為資源系數(shù)資源系數(shù)例2 某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應(yīng)量見(jiàn)下表：要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安

18、排各住宅多少m2)，求建造方案。水泥水泥(公斤公斤/m2)4000(千工日千工日)147000(千塊千塊)150000(噸噸)20000(噸噸)110000(千元千元)資源限量資源限量3.518025120大模住宅大模住宅3.019030135壁板住宅壁板住宅4.521011012105磚混住宅磚混住宅人工人工(工日工日/m2)磚磚(塊塊/m2)鋼材鋼材(公斤公斤/m2)造價(jià)造價(jià)(元元/m2) 資源資源住宅體系住宅體系 解: 設(shè)今年計(jì)劃修建磚混、壁板、大模住宅各為 x1,x2,x3 m2, z為總面積,則本問(wèn)題的數(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個(gè)變量，個(gè)變量，10個(gè)約束條件。個(gè)約束條件。課堂練習(xí)課堂練習(xí) 某蓄場(chǎng)每日要為每頭牲畜購(gòu)買(mǎi)飼料，以使其某蓄場(chǎng)每日要為每頭牲畜購(gòu)買(mǎi)飼料，以使其獲取所需的獲取所需的A、B、C、D四種養(yǎng)分。有關(guān)數(shù)據(jù)四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場(chǎng)上出售的如

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

21、模型）ABCD價(jià)格價(jià)格M0.50.20.30300N0.10.30.40.2200每頭日需每頭日需10587養(yǎng)分養(yǎng)分飼料飼料答案：答案：設(shè)購(gòu)買(mǎi)設(shè)購(gòu)買(mǎi)M飼料飼料x(chóng)1，N飼料飼料x(chóng)20.5 x1 +0.1x2100.2x1 +0.3x2 50.3x1 +0.4x2 8 0.2x2 7x1 , x20s.t.Min Z=300 x1 +200 x2思考題思考題二、線(xiàn)性規(guī)劃的圖解法二、線(xiàn)性規(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ù)的等值線(xiàn)）作目標(biāo)函數(shù)的等值線(xiàn)給給z不同的值，作相應(yīng)直線(xiàn)，判斷出不同的值，作相應(yīng)直線(xiàn)，判斷出z增大時(shí)，直線(xiàn)的移動(dòng)方向增大時(shí)，直線(xiàn)的移動(dòng)方向?qū)⒅本€(xiàn)向增大方向移動(dòng)，直至可行域?qū)⒅本€(xiàn)向增大方向移動(dòng)，直至可行域邊界，交點(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í)圖解法求解線(xiàn)性規(guī)劃圖解法求解線(xiàn)性規(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）無(wú)可行解）無(wú)可行解注：出現(xiàn)（注：出現(xiàn)（3）、（）、（4）情況時(shí)，建模有問(wèn)題）情況時(shí)，建模有問(wèn)題（4）無(wú)有限最優(yōu)解）無(wú)有限最優(yōu)解補(bǔ)充知識(shí)：凸集凸集：在點(diǎn)集中任取兩點(diǎn)，則其連線(xiàn)仍在其中。即沒(méi)有凹入的部分；沒(méi)有空洞。在凸集中，點(diǎn)A，B，C，D稱(chēng)為極點(diǎn)（或頂點(diǎn)）。ABCD從圖解法中我們了解到以下事實(shí)：若LP問(wèn)題的可行域存在，則可行域一定是凸集。若LP問(wèn)題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無(wú)窮多最優(yōu)解的話(huà)）一定是可行域凸集的某個(gè)極點(diǎn)（頂點(diǎn)）。思路：最優(yōu)解先在可行域中找。（可行域?yàn)榭占?，則無(wú)可行解，故無(wú)最優(yōu)解。）最優(yōu)解在可行域的極點(diǎn)中找。極點(diǎn)是有限個(gè)，若兩個(gè)極點(diǎn)都是最優(yōu)解，則兩個(gè)極點(diǎn)所連線(xiàn)段

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

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

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

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

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

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

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

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

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

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

35、本可行解（簡(jiǎn)稱(chēng)基可行解）。（簡(jiǎn)稱(chēng)基可行解）。例例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中可找出若干個(gè)基中可找出若干個(gè)基B每個(gè)基每個(gè)基B都對(duì)應(yīng)于一個(gè)基本解都對(duì)應(yīng)于一個(gè)基本

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

37、解是否最優(yōu)檢驗(yàn)這個(gè)基可行解是否最優(yōu)尋找一個(gè)更好的基可行解尋找一個(gè)更好的基可行解否否是是停停止止 Dantzig Dantzig的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解（即可行的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解（即可行域頂點(diǎn)）中。域頂點(diǎn)）中。 其基本思路是從一個(gè)初始的基本可行解出發(fā)，尋找一條達(dá)到其基本思路是從一個(gè)初始的基本可行解出發(fā)，尋找一條達(dá)到 最優(yōu)基本可行解的最佳途徑。最優(yōu)基本可行解的最佳途徑。 單純形法的一般步驟如下：?jiǎn)渭冃畏ǖ囊话悴襟E如下： （1 1）尋找一個(gè)初始的基本可行解。）尋找一個(gè)初始的基本可行解。 （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ù)值有所改善改善的另一個(gè)基本可行解，然后轉(zhuǎn)會(huì)到步的另一個(gè)基本可行解，然后轉(zhuǎn)會(huì)到步驟（驟（2 2）。）。 1.確定初始基可行解 由于基可行解是由一個(gè)可行基決定的，因此，由于基可行解是由一個(gè)可行基決定的，因此，確定初始基可行解確定初始基可行解X X0 0相當(dāng)于確定一個(gè)初始可行基相當(dāng)于確定一個(gè)初始可行基B B0 0。方法：方法：若若A中含中含I，則，則B0=I； 若若A中不含中不含I，則可用人工變量法構(gòu)，則可用人工變量法構(gòu) 造一個(gè)造一個(gè)I。問(wèn)題：若問(wèn)題：若B0

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

40、行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值其中分別表示基變量和其中分別表示基變量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。非基變量所對(duì)應(yīng)的價(jià)值系數(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 其中其中 稱(chēng)為非基變量稱(chēng)為非基變量N N的檢驗(yàn)向量，它的各個(gè)分量稱(chēng)為

41、檢驗(yàn)數(shù)。若的檢驗(yàn)向量，它的各個(gè)分量稱(chēng)為檢驗(yàn)數(shù)。若N N的每一個(gè)檢驗(yàn)數(shù)均小的每一個(gè)檢驗(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)解判別定理 對(duì)于線(xiàn)性規(guī)劃問(wèn)題對(duì)于線(xiàn)性規(guī)劃問(wèn)題若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，若某個(gè)基本可行解所對(duì)應(yīng)的

42、檢驗(yàn)向量，則這個(gè)基本可行解就是最優(yōu)解。則這個(gè)基本可行解就是最優(yōu)解。定理定理2 2：無(wú)窮多最優(yōu)解判別定理：無(wú)窮多最優(yōu)解判別定理 若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量，其中存在一個(gè)檢驗(yàn)數(shù)，其中存在一個(gè)檢驗(yàn)數(shù)m+km+k=0=0，則線(xiàn)性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。則線(xiàn)性規(guī)劃問(wèn)題有無(wú)窮多最優(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ǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：做法是： 先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基變量變成基變量（將它的值從零增至正值），變量變成基變量（將它的值從零增至正值）， 再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非基變量（將它的值從正值減至零）?；兞浚▽⑺闹祻恼禍p至

44、零）。由此可得一個(gè)新的基本可行解，由由此可得一個(gè)新的基本可行解，由 可知，這樣的變換一定能使目標(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)向量 ， 若其中有兩個(gè)以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快若其中有兩個(gè)以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快些，通常要用些，通常要用“最大增加原則最大增加原則”，即選取最大正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基，即選取最大

45、正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量為換入變量，即若變量為換入變量，即若 則選取對(duì)應(yīng)的則選取對(duì)應(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 換出變量的確定換出變量的確定 最小比值原則最小比值原則 如果確定為換入變量，方程如果確定為換入變量，方程其中為中與對(duì)應(yīng)的系數(shù)列向量。其中為中與對(duì)應(yīng)的系數(shù)列向量?，F(xiàn)在需在現(xiàn)

46、在需在 中確定一個(gè)基變量為換出變量。中確定一個(gè)基變量為換出變量。 當(dāng)由零慢慢增加到某個(gè)值時(shí)，當(dāng)由零慢慢增加到某個(gè)值時(shí)， 的非負(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則選取對(duì)應(yīng)的基變量則選取對(duì)應(yīng)的基變量 為換出變量。為換出變量。 x

47、lBX 定理定理3 3：無(wú)最優(yōu)解判別定理：無(wú)最優(yōu)解判別定理 若若 是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù)是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù) ，但是，則該線(xiàn)性規(guī)劃問(wèn)題無(wú)最優(yōu)解。但是，則該線(xiàn)性規(guī)劃問(wèn)題無(wú)最優(yōu)解。1B bX=0-1m+kB P0m+k0證：令證：令 ，則得新的可行解，則得新的可行解將上式代入將上式代入因?yàn)橐驗(yàn)?, , 故當(dāng)故當(dāng)+時(shí)，時(shí)，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尋找更好的基可行解 由于基可行解與基對(duì)應(yīng)，即尋找一個(gè)新的基可行由于基可行解

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

49、其大致的過(guò)程如下。大致的過(guò)程如下。（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ì)算下一個(gè)基可行解、再檢驗(yàn)，直至最優(yōu)）換基、計(jì)算下一個(gè)基可行解、再檢驗(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)問(wèn)題：當(dāng)模型規(guī)模較大時(shí)，計(jì)算量很大。問(wèn)題：當(dāng)模型規(guī)模較大時(shí)，計(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ì)了基于初等行得。也可通過(guò)初等行變換求鄰兩個(gè)只有一列不同，故相而相鄰兩個(gè) 1BB單純形表的主要結(jié)構(gòu)：?jiǎn)渭冃伪淼闹饕Y(jié)構(gòu)： X CABNbBN問(wèn)題：第一張表的問(wèn)題：第一張表的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問(wèn)題：標(biāo)準(zhǔn)模型的問(wè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注：?jiǎn)渭冃伪碇械男畔⒆ⅲ簡(jiǎn)渭冃伪碇械男畔⒚恳涣械暮x：每一列的含義：B-1(b A)=(B-1b, B-1 P1,， B-1 Pn)每個(gè)表中的每個(gè)表中的B和和B-1的查找：的查找： B從初表中找；從初表中找； B-1從當(dāng)前表中找，對(duì)應(yīng)于從當(dāng)前表中找，對(duì)應(yīng)于初表中的初表中的I的位置。的位置。 ),(243PPPB 1000510401 以第以第2個(gè)表為例：個(gè)表為例： 1B 1 . 0005 . 0104 . 001終表分析終表分析最優(yōu)基最優(yōu)基B* 和和(B*)-1的查找的查找 ),(213*P