運(yùn)籌學(xué)1線性規(guī)劃

1、陳文林陳文林Sy_運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外緒緒 論論Introduction第一章第一章（1）運(yùn)籌學(xué)簡(jiǎn)述）運(yùn)籌學(xué)簡(jiǎn)述（2）運(yùn)籌學(xué)的主要內(nèi)容）運(yùn)籌學(xué)的主要內(nèi)容（3）本課程的教材及參考書）本課程的教材及參考書（4）本課程的特點(diǎn)和要求）本課程的特點(diǎn)和要求（5）本課程授課方式與考核）本課程授課方式與考核 （6）運(yùn)籌學(xué)在管理中的應(yīng)用）運(yùn)籌學(xué)在管理中的應(yīng)用本章主要內(nèi)容：本章主要內(nèi)容：運(yùn)籌學(xué)（運(yùn)籌學(xué)（Operations Research,簡(jiǎn)寫簡(jiǎn)寫OR ）系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國(guó)有人把運(yùn)籌系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國(guó)有人把運(yùn)籌學(xué)稱之為管理科

2、學(xué)學(xué)稱之為管理科學(xué)(Management Science)。運(yùn)籌學(xué)所研究的。運(yùn)籌學(xué)所研究的問(wèn)題，可簡(jiǎn)單地歸結(jié)為一句話：?jiǎn)栴}，可簡(jiǎn)單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱之為故有人稱之為最優(yōu)化技術(shù)最優(yōu)化技術(shù)。運(yùn)籌學(xué)的歷史與發(fā)展運(yùn)籌學(xué)的歷史與發(fā)展 “運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早“田忌賽馬田忌賽馬” 。 齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對(duì)局三次，每次勝負(fù)對(duì)局三次，每次勝負(fù)1000金。田忌在好友、著名的軍事謀金。田忌在好友、著

3、名的軍事謀略家孫臏的指導(dǎo)下，以以下安排：略家孫臏的指導(dǎo)下，以以下安排： 齊王齊王 上上中中 下下 田忌田忌 下下上上 中中丁謂的皇宮修復(fù)工程丁謂的皇宮修復(fù)工程 北宋年間，丁謂負(fù)責(zé)修復(fù)火毀的開封皇宮。他北宋年間，丁謂負(fù)責(zé)修復(fù)火毀的開封皇宮。他的施工方案是：先將皇宮前的一條大街挖成一條大的施工方案是：先將皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔(dān)繁重的運(yùn)輸任務(wù)；修令與汴水相連形成的河道承擔(dān)繁重的運(yùn)輸任務(wù)；修復(fù)工程完成后，實(shí)施大溝排水，并將原廢墟物回填，復(fù)工程完成后，實(shí)施大溝排水，并將原廢墟物回填，修復(fù)

4、成原來(lái)的大街。丁謂將取材、運(yùn)輸及清廢用修復(fù)成原來(lái)的大街。丁謂將取材、運(yùn)輸及清廢用“一溝三用一溝三用”巧妙地解決了，體現(xiàn)了系統(tǒng)規(guī)劃的思巧妙地解決了，體現(xiàn)了系統(tǒng)規(guī)劃的思想。想。 國(guó)際上運(yùn)籌學(xué)的思想可追溯到國(guó)際上運(yùn)籌學(xué)的思想可追溯到1914年，當(dāng)時(shí)的年，當(dāng)時(shí)的蘭徹斯特提出了軍事運(yùn)籌學(xué)的作戰(zhàn)模型。蘭徹斯特提出了軍事運(yùn)籌學(xué)的作戰(zhàn)模型。1917年，年，丹麥工程師埃爾朗在研究自動(dòng)電話系統(tǒng)中通話線路丹麥工程師埃爾朗在研究自動(dòng)電話系統(tǒng)中通話線路與用戶呼叫的數(shù)量關(guān)系問(wèn)題時(shí)，提出了埃爾朗公式，與用戶呼叫的數(shù)量關(guān)系問(wèn)題時(shí)，提出了埃爾朗公式，研究了隨機(jī)服務(wù)系統(tǒng)中的系統(tǒng)排隊(duì)與系統(tǒng)擁擠問(wèn)題。研究了隨機(jī)服務(wù)系統(tǒng)中的系統(tǒng)排隊(duì)與

5、系統(tǒng)擁擠問(wèn)題。存儲(chǔ)論的最優(yōu)批量公式是在存儲(chǔ)論的最優(yōu)批量公式是在20世紀(jì)世紀(jì)20年代初提出的。年代初提出的。“運(yùn)作研究運(yùn)作研究(Operational Research)小組小組”:解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：1. 如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍德空如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍德空襲襲2. 對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)損失最少；德國(guó)潛艇攻擊時(shí)損失最少；3. 在各種情況下如何調(diào)整反潛深水炸彈的在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷力等。力等。

6、在生產(chǎn)管理方面的應(yīng)用，最早是在生產(chǎn)管理方面的應(yīng)用，最早是1939年前蘇聯(lián)的康特洛為奇提年前蘇聯(lián)的康特洛為奇提出了生產(chǎn)組織與計(jì)劃中的線性規(guī)劃問(wèn)題，并給出解乘數(shù)法的求解方出了生產(chǎn)組織與計(jì)劃中的線性規(guī)劃問(wèn)題，并給出解乘數(shù)法的求解方法，出版了第一部關(guān)于線性規(guī)劃的著作法，出版了第一部關(guān)于線性規(guī)劃的著作生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法方法。 但當(dāng)時(shí)并沒有引起重視，直到但當(dāng)時(shí)并沒有引起重視，直到1960年康特洛為奇再次出版了年康特洛為奇再次出版了最佳資源利用的經(jīng)濟(jì)計(jì)算最佳資源利用的經(jīng)濟(jì)計(jì)算，才受到國(guó)內(nèi)外的一致重視，為此康，才受到國(guó)內(nèi)外的一致重視，為此康特洛為奇獲得了諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。特洛為奇獲

7、得了諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。 線性規(guī)劃提出后很快受到經(jīng)濟(jì)學(xué)家的重視，如：二次世界大戰(zhàn)線性規(guī)劃提出后很快受到經(jīng)濟(jì)學(xué)家的重視，如：二次世界大戰(zhàn)中從事運(yùn)輸模型研究的美國(guó)經(jīng)濟(jì)學(xué)家?guī)炱章梗ㄖ袕氖逻\(yùn)輸模型研究的美國(guó)經(jīng)濟(jì)學(xué)家?guī)炱章梗═.C.Koopmans），），他很快看到了線性規(guī)劃在經(jīng)濟(jì)中應(yīng)用的意義，并呼吁年輕的經(jīng)濟(jì)學(xué)他很快看到了線性規(guī)劃在經(jīng)濟(jì)中應(yīng)用的意義，并呼吁年輕的經(jīng)濟(jì)學(xué)家要關(guān)注線性規(guī)劃。其中阿羅、薩謬爾遜、西蒙、多夫曼和胡爾威家要關(guān)注線性規(guī)劃。其中阿羅、薩謬爾遜、西蒙、多夫曼和胡爾威茨等都獲得了諾貝爾獎(jiǎng)。茨等都獲得了諾貝爾獎(jiǎng)。 20世紀(jì)世紀(jì)50年代中期，錢學(xué)森、許國(guó)志等教授在國(guó)內(nèi)全面介年代中期，錢學(xué)森、

8、許國(guó)志等教授在國(guó)內(nèi)全面介紹和推廣運(yùn)籌學(xué)知識(shí)，紹和推廣運(yùn)籌學(xué)知識(shí)，1956年，中國(guó)科學(xué)院成立第一個(gè)運(yùn)籌學(xué)研年，中國(guó)科學(xué)院成立第一個(gè)運(yùn)籌學(xué)研究室，究室，1957年運(yùn)籌學(xué)運(yùn)用到建筑和紡織業(yè)中，年運(yùn)籌學(xué)運(yùn)用到建筑和紡織業(yè)中，1958年提出了圖上年提出了圖上作業(yè)法，山東大學(xué)的管梅谷教授提出了作業(yè)法，山東大學(xué)的管梅谷教授提出了“中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題”，1970年，在華羅庚教授的直接指導(dǎo)下，在全國(guó)范圍內(nèi)推廣統(tǒng)籌方年，在華羅庚教授的直接指導(dǎo)下，在全國(guó)范圍內(nèi)推廣統(tǒng)籌方法和優(yōu)選法。法和優(yōu)選法。 1978年年11月，在成都召開了全國(guó)數(shù)學(xué)年會(huì)，對(duì)運(yùn)籌學(xué)的理論月，在成都召開了全國(guó)數(shù)學(xué)年會(huì)，對(duì)運(yùn)籌學(xué)的理論與應(yīng)用研

9、究進(jìn)行了一次檢閱，與應(yīng)用研究進(jìn)行了一次檢閱，1980年年4月在山東濟(jì)南正式成立了月在山東濟(jì)南正式成立了“中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)會(huì)中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)會(huì)”，1984年在上海召開了年在上海召開了“中國(guó)數(shù)學(xué)會(huì)運(yùn)中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)會(huì)第二屆代表大會(huì)暨學(xué)術(shù)交流會(huì)籌學(xué)會(huì)第二屆代表大會(huì)暨學(xué)術(shù)交流會(huì)”，并將學(xué)會(huì)改名為，并將學(xué)會(huì)改名為“中國(guó)中國(guó)運(yùn)籌學(xué)會(huì)運(yùn)籌學(xué)會(huì)”。成熟的學(xué)科分支向縱深發(fā)展成熟的學(xué)科分支向縱深發(fā)展新的研究領(lǐng)域產(chǎn)生新的研究領(lǐng)域產(chǎn)生與新的技術(shù)結(jié)合與新的技術(shù)結(jié)合與其他學(xué)科的結(jié)合加強(qiáng)與其他學(xué)科的結(jié)合加強(qiáng)傳統(tǒng)優(yōu)化觀念不斷變化傳統(tǒng)優(yōu)化觀念不斷變化運(yùn)籌學(xué)的發(fā)展趨勢(shì)運(yùn)籌學(xué)的發(fā)展趨勢(shì)數(shù)學(xué)規(guī)劃（數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)

10、劃線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)、動(dòng)態(tài)規(guī)劃等）規(guī)劃等）圖論圖論存儲(chǔ)論存儲(chǔ)論排隊(duì)論排隊(duì)論對(duì)策論對(duì)策論排序與統(tǒng)籌方法排序與統(tǒng)籌方法決策分析決策分析1. 線性規(guī)劃（線性規(guī)劃（Linear Program）是一個(gè)成熟的分支，它有）是一個(gè)成熟的分支，它有效的算法效的算法單純形法，主要解決生產(chǎn)計(jì)劃問(wèn)題，合理下料單純形法，主要解決生產(chǎn)計(jì)劃問(wèn)題，合理下料問(wèn)題，最優(yōu)投資問(wèn)題。問(wèn)題，最優(yōu)投資問(wèn)題。2. 整數(shù)規(guī)劃整數(shù)規(guī)劃(Integrate Program)：在線性規(guī)劃的基礎(chǔ)上，變：在線性規(guī)劃的基礎(chǔ)上，變量加上整數(shù)約束。量加上整數(shù)約束。3. 非線性規(guī)劃非線性規(guī)劃(Nonlinear Program)：目標(biāo)函數(shù)和

11、約束條件：目標(biāo)函數(shù)和約束條件是非線性函數(shù)，如證券投資組合優(yōu)化是非線性函數(shù)，如證券投資組合優(yōu)化:如何合理投資使風(fēng)險(xiǎn)如何合理投資使風(fēng)險(xiǎn)最小。最小。4. 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃(Dynamic Program)：多階段決策問(wèn)題。是美國(guó)：多階段決策問(wèn)題。是美國(guó)貝爾曼于貝爾曼于1951年提出的。年提出的。5、圖與網(wǎng)絡(luò)、圖與網(wǎng)絡(luò)(Graph Theory and Network)：中國(guó)郵遞員問(wèn)：中國(guó)郵遞員問(wèn)題、哥尼斯堡城問(wèn)題、最短路、最大流問(wèn)題。題、哥尼斯堡城問(wèn)題、最短路、最大流問(wèn)題。6、存儲(chǔ)論（、存儲(chǔ)論（Inventory Theory)：主要解決生產(chǎn)中的庫(kù)存問(wèn)：主要解決生產(chǎn)中的庫(kù)存問(wèn)題，訂貨周期和訂貨量等問(wèn)

12、題。題，訂貨周期和訂貨量等問(wèn)題。7、排隊(duì)論、排隊(duì)論(Queue Theory)：主要研究排隊(duì)系統(tǒng)中的系統(tǒng)排：主要研究排隊(duì)系統(tǒng)中的系統(tǒng)排隊(duì)和系統(tǒng)擁擠現(xiàn)象，從而評(píng)估系統(tǒng)的服務(wù)質(zhì)量。隊(duì)和系統(tǒng)擁擠現(xiàn)象，從而評(píng)估系統(tǒng)的服務(wù)質(zhì)量。8、對(duì)策論、對(duì)策論(Game Theory)：主要研究具有斗爭(zhēng)性質(zhì)的優(yōu)化：主要研究具有斗爭(zhēng)性質(zhì)的優(yōu)化問(wèn)題。問(wèn)題。9、決策分析、決策分析(Decision Analysis) ：主要研究定量化決策。：主要研究定量化決策。選用教材選用教材 運(yùn)籌學(xué)教程運(yùn)籌學(xué)教程胡運(yùn)權(quán)主編胡運(yùn)權(quán)主編 （第（第3 3版）清華出版社版）清華出版社參考教材參考教材運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用胡運(yùn)權(quán)主編胡運(yùn)

13、權(quán)主編 哈工大出版社哈工大出版社管理運(yùn)籌學(xué)管理運(yùn)籌學(xué)韓伯棠主編韓伯棠主編 （第（第2 2版）高等教育出版版）高等教育出版社社運(yùn)籌學(xué)運(yùn)籌學(xué)( (修訂版修訂版) ) 錢頌迪主編錢頌迪主編 清華出版社清華出版社先修課：先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點(diǎn)：特點(diǎn)：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用運(yùn)籌學(xué)的研究的主要步驟：運(yùn)籌學(xué)的研究的主要步驟：真實(shí)系統(tǒng)真實(shí)系統(tǒng)系統(tǒng)分析系統(tǒng)分析問(wèn)題描述問(wèn)題描述模型建立模型建立與修改與修改模型求解模型求解與檢驗(yàn)與檢驗(yàn)結(jié)果分析與結(jié)果分析與實(shí)施實(shí)施數(shù)據(jù)準(zhǔn)備數(shù)據(jù)準(zhǔn)備學(xué)科總成績(jī)學(xué)科總成績(jī)平時(shí)成績(jī)平時(shí)

14、成績(jī)（4040）課堂考勤課堂考勤（5050）平時(shí)作業(yè)平時(shí)作業(yè)（5050）期末成績(jī)期末成績(jī)（6060）講授為主，結(jié)合習(xí)題作業(yè)講授為主，結(jié)合習(xí)題作業(yè)運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用涉及的方面：運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用涉及的方面：1.1. 生產(chǎn)計(jì)劃生產(chǎn)計(jì)劃2.2. 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題3.3. 人事管理人事管理4.4. 庫(kù)存管理庫(kù)存管理5.5. 市場(chǎng)營(yíng)銷市場(chǎng)營(yíng)銷6.6. 財(cái)務(wù)和會(huì)計(jì)財(cái)務(wù)和會(huì)計(jì)7.7.物流配送物流配送另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項(xiàng)目的選擇另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項(xiàng)目的選擇與評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)等。與評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)等。運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千

15、千 里里 之之 外外線線 性性 規(guī)規(guī) 劃及單純形法劃及單純形法Linear ProgrammingLinear Programming LP的數(shù)學(xué)模型的數(shù)學(xué)模型 圖解法圖解法 單純形法單純形法 單純形法的進(jìn)一步討論人工變量法單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用模型的應(yīng)用1. 規(guī)劃問(wèn)題規(guī)劃問(wèn)題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問(wèn)題。這就是規(guī)劃問(wèn)題。（1 1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌

16、兼顧，合理安排，用最少的資源最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)去完成確定的任務(wù)或目標(biāo)（2 2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤(rùn)最大、利潤(rùn)最大. .）例例1.1 如圖所示，如何截取如圖所示，如何截取x使鐵皮所圍成的容積最使鐵皮所圍成的容積最大？大？ x xa a xxav 220 dxdv0)2()2()2(22 xaxxa6ax 例例1.2 某廠生產(chǎn)兩種產(chǎn)品，某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品

17、所需資下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn)源及單位產(chǎn)品利潤(rùn) 問(wèn)：應(yīng)如何安排生產(chǎn)計(jì)劃，才問(wèn)：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使總利潤(rùn)最大？能使總利潤(rùn)最大？ 解：解：1.1.決策變量：設(shè)產(chǎn)品決策變量：設(shè)產(chǎn)品I I、IIII的產(chǎn)量的產(chǎn)量 分別為分別為 x1、x22.2.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z z，則有：，則有： max z = 2 x1 + x23.3.約束條件：約束條件： 5x2 15 6x1+ 2x2 24 x1+ x2 5 x1， x20例例1.3 已知資料如下表所示，已知資料如下表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？或如何考慮利潤(rùn)大，最大？或如何考慮利

18、潤(rùn)大，產(chǎn)品好銷。產(chǎn)品好銷。 設(shè) 備產(chǎn) 品 A B C D利潤(rùn)（元） 2 1 4 0 2 2 2 0 4 3 有 效 臺(tái) 時(shí)12 8 16 12解：解：1.1.決策變量：設(shè)產(chǎn)品決策變量：設(shè)產(chǎn)品I I、IIII的產(chǎn)量的產(chǎn)量分別為分別為 x1、x22.2.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z z，則，則有：有： max z = 2 x1 + x23.3.約束條件：約束條件： x1 0 , x2 0 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12例例1.4 某廠生產(chǎn)三種藥物，某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的這些藥物可以從四種不同的原料中提取。下表給出了單原料

19、中提取。下表給出了單位原料可提取的藥物量位原料可提取的藥物量 解：解：要求：生產(chǎn)要求：生產(chǎn)A種藥物至少種藥物至少160單位；單位；B種藥物恰好種藥物恰好200單位，單位，C種藥物不超過(guò)種藥物不超過(guò)180單位，且單位，且使原料總成本最小。使原料總成本最小。1.1.決策變量：設(shè)四種原料的使用決策變量：設(shè)四種原料的使用 量分別為：量分別為：x1、x2 、x3 、x42.2.目標(biāo)函數(shù)：設(shè)總成本為目標(biāo)函數(shù)：設(shè)總成本為z min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.3.約束條件：約束條件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x

20、1 x2 +x3 +2 x4 180 x1、x2 、x3 、x4 0 例例1.5 某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：線的貨運(yùn)量、貨運(yùn)成本如下表所示：航線號(hào)航線號(hào)船隊(duì)船隊(duì)類型類型編隊(duì)形式編隊(duì)形式貨運(yùn)成本貨運(yùn)成本（千元隊(duì)）（千元隊(duì)）貨運(yùn)量貨運(yùn)量（千噸）（千噸）拖輪拖輪A型型駁船駁船B型型駁船駁船1112362521436202322472404142720船只種類船只種類船只數(shù)船只數(shù)拖拖 輪輪30A型駁船型駁船34B型駁船型駁船52航線號(hào)航線號(hào)合同貨運(yùn)量合同貨運(yùn)量12002400問(wèn)：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)

21、，又使總貨運(yùn)成本為最??？問(wèn)：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最小？ 解：解：設(shè)：設(shè)：x xj j為第為第j j號(hào)類型船隊(duì)的隊(duì)數(shù)（號(hào)類型船隊(duì)的隊(duì)數(shù)（j = 1j = 1，2 2，3 3，4 4），）， z z 為總貨運(yùn)成本為總貨運(yùn)成本則：則： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1+20 x2 200 40 x3+20 x4 400 xj 0 （ j = 1,2,3,4）00 )( )( (min) max1221111212111221

22、1 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 簡(jiǎn)寫為：簡(jiǎn)寫為：) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中：其中： mnmnaaaaA1111 0 )( (min) maxXBAXCXZ其中：其中：) (21ncccC nxxX1 mbbB16. 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特點(diǎn)：特點(diǎn)：(1

23、) 目標(biāo)函數(shù)求最大值（有時(shí)求最小值）目標(biāo)函數(shù)求最大值（有時(shí)求最小值）(2) 約束條件都為等式方程，且右端常數(shù)項(xiàng)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零都大于或等于零(3) 決策變量決策變量xj為非負(fù)。為非負(fù)。 目標(biāo)函數(shù)的轉(zhuǎn)換目標(biāo)函數(shù)的轉(zhuǎn)換 如果是求極小值即如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問(wèn)題。，可化為求極大值問(wèn)題。 jjxczmin也就是：令也就是：令 ，可得到上式。，可得到上式。zz jjxczzmax即即 若存在取值無(wú)約束的變量若存在取值無(wú)約束的變量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx 變量的變換變量的變

24、換 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。 ijijbxa0 iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0 iniinjijxbxxa稱為剩余變量稱為剩余變量 常量常量 bi0 的變換的變換: :約束方程兩邊乘以約束方程兩邊乘以（1）例例1.6 將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321無(wú)無(wú)約約束束xxxxxxxxxxxxxxxZ用用 替換替換 ，且，且 解解:（）因?yàn)椋ǎ┮驗(yàn)閤3無(wú)符號(hào)要求無(wú)符號(hào)要求 ，即，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)取正值也可取負(fù)值，

25、標(biāo)準(zhǔn)型中要求變量非負(fù)，所以型中要求變量非負(fù)，所以33xx 3x0,33 xx(2) 第一個(gè)約束條件是第一個(gè)約束條件是“”號(hào)，在號(hào)，在“”左端加入松馳變量左端加入松馳變量x4，x40,化為等式；化為等式；(3) 第二個(gè)約束條件是第二個(gè)約束條件是“”號(hào)，在號(hào)，在“”左端減去剩余變量左端減去剩余變量x5，x50；(4) 第第3個(gè)約束方程右端常數(shù)項(xiàng)為個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以，方程兩邊同乘以(-1),將右將右端常數(shù)項(xiàng)化為正數(shù)；端常數(shù)項(xiàng)化為正數(shù)； (5) 目標(biāo)函數(shù)是最小值，為了化為求最大值，令目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到得到max z=-z，即當(dāng)，即當(dāng)z達(dá)到最小值

26、時(shí)達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然達(dá)到最大值，反之亦然; 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式如下： 例例1.7 將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321xxxxxxxxxxxxxxxZ為無(wú)約束（無(wú)非負(fù)限制）為無(wú)約束（無(wú)非負(fù)限制） 解解: : 用用 替換替換 ，且，且 ， 54xx 3x0,54 xx將第將第3 3個(gè)約束方程兩邊乘以（個(gè)約束方程兩邊乘以（1 1）將

27、極小值問(wèn)題反號(hào)，變?yōu)榍髽O大值將極小值問(wèn)題反號(hào)，變?yōu)榍髽O大值標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式如下： 0,5 )(252 )( 7 )(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ76, xx引入變量引入變量 無(wú)約束2121212,0435832xxxxxxx-xminZ10 x ,x ,x ,x ,xx)x(xxx)x(xx)x(xxZaxm1111654364354343435832例例1.8 將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型解：解： 例例1.9 將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型解：解：Mi

28、n f= -3 x1 + 5 x2 + 8 x3 - 7 x4s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1 , x3 , x4 0； x2無(wú)約束 Max z = 3x15x2+5x2”8x3 +7x4 s.t. 2x13x2+3x2”+5x3+6x4+x5= 28 4x1+2x2-2x2”+3x3-9x4-x6= 39 -6x2+6x2”-2x3-3x4-x7 = 58 x1 ,x2,x2”,x3 ,x4 ,x5 ,x6 ,x7 0 7. 7. 線性規(guī)劃問(wèn)題的解

29、線性規(guī)劃問(wèn)題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj線性規(guī)劃問(wèn)題線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題，就是從滿足約束條件求解線性規(guī)劃問(wèn)題，就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個(gè)解，使目標(biāo)函數(shù)中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。達(dá)到最大值。 可行解可行解：滿足約束條件、的解為可行解。所有可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。的集合為可行域。 最優(yōu)解最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。：使目標(biāo)函數(shù)達(dá)到最大值的可行解。 基：基：設(shè)設(shè)A為約束條件的為約束條件的mn階系數(shù)矩陣

30、階系數(shù)矩陣(m04010換換出出行行將將3化為化為15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011例例1.13 用單純形法求解用單純形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量，列單純形表計(jì)算?？勺鳛槌跏蓟兞?，列單純形表計(jì)算。cj12100ic

31、B基變量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 2021/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j 0,124 16 482122232max2121212121xxxxxxxxxxZ變成標(biāo)準(zhǔn)型變成標(biāo)準(zhǔn)型 0, 12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ例例1.14 用單純形法求解用單純形法求解約束方程的系數(shù)矩陣約束方程的

32、系數(shù)矩陣 654321100040010004001021000122ppppppA IppppB100001000010000165436543 xxxx,21xx ,為基變量為基變量為非基變量為非基變量I I 為單位矩陣且線性獨(dú)立為單位矩陣且線性獨(dú)立cjcBxBb0000 x3x4x5x61281612 2x2 學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個(gè)基本定理個(gè)基本定理2. 熟練掌握線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化熟練掌握線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化 3.熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟人工變量法：人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有

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

34、 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系數(shù)矩陣中不存在系數(shù)矩陣中不存在單位矩陣，無(wú)法建單位矩陣，無(wú)法建立初始單純形表。立初始單純形表。故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：123671234612351237max3243 4 2 10 22 10,

35、1,2,7jZxxxMxMxxxxxxxxxxxxxxxjL其中：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。紹的單純形法求解該模型，計(jì)算結(jié)果見下表。 cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M-Mx63-650-1013/50 x58-3300108/3-1x31

36、2-210005-6M5M0-M002x23/56/5101/500 x531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j 例例1.11 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃12312312313123max3 2114232 +10Zxxxxxxxxxxxxxx、 、解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式1231234123513max3 2114232 10,1,2,5jZxxxxxxxxxxxxxxjL系數(shù)矩陣中不存在

37、系數(shù)矩陣中不存在單位矩陣，無(wú)法建單位矩陣，無(wú)法建立初始單純形表。立初始單純形表。故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：1234567123412356137max3 3 11 -4 2 + 3 2 10,1,2,7jZxxxxxMxMxxxxxxxxxxxxxxjL+0 +0 其中：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。紹的單

38、純形法求解該模型，計(jì)算結(jié)果見下表。 Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z-4M3-6M-1+M-1+3M0-M000 x4103-20100-1-Mx610100-11-21-1x31-2010001Z-M-11-1+M00-M0-3M+1j Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-1x31-2010001Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x

39、210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+2/3 用計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只能用很大的數(shù)代替用計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只能用很大的數(shù)代替M,可能造可能造成計(jì)算機(jī)上的錯(cuò)誤，故多采用成計(jì)算機(jī)上的錯(cuò)誤，故多采用兩階段法兩階段法。 第一階段：第一階段： 在原線性規(guī)劃問(wèn)題中加入人工變量，構(gòu)造如下模型：在原線性規(guī)劃問(wèn)題中加入人工變量，構(gòu)造如下模型：1111 11111 1min00 nn mnnnnmmnnn mmxxxxa xa xxba xaxxbLLLMMOL1 0 n mxxL 對(duì)上述模型求解（單純形法），若對(duì)上述模型求解（單純形法），若=

40、0,說(shuō)明問(wèn)題存在基說(shuō)明問(wèn)題存在基可行解，可以進(jìn)行第二個(gè)階段；否則，原問(wèn)題無(wú)可行解，停可行解，可以進(jìn)行第二個(gè)階段；否則，原問(wèn)題無(wú)可行解，停止運(yùn)算。止運(yùn)算。第一階段的線性規(guī)劃問(wèn)題可寫為：第一階段的線性規(guī)劃問(wèn)題可寫為：67123412356137min 2 =11 42 3 2 1 xxxxxxxxxxxxxx127 ,0 x xx，第一階段單純形法迭代的過(guò)程見下表第一階段單純形法迭代的過(guò)程見下表（注意：沒有化為極大化問(wèn)題）（注意：沒有化為極大化問(wèn)題）Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-201000

41、1146-1-301000 x4103-20100-11x610100-11-210 x31-201000110-1001030 x4123001-22-50 x210100-11-20 x31-201000000000011 第二階段：第二階段： 在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表（用單純形法計(jì)算）。表（用單純形法計(jì)算）。例：例： x,x ,x x x x xx xxx xxx x xxxZmax 01232411237217

42、31653214321321，cj3-1-100cBxBbx1x2x3x4x50 x4123001-24-1x210100-1-1x31-20100Z-21000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3Z2000-1/3-1/3第二階段：第二階段：54321003xxxxxZmax 最優(yōu)解為（最優(yōu)解為（4 1 9 0 0），目標(biāo)函數(shù)），目標(biāo)函數(shù) Z = 2 通過(guò)大法或兩階段法求初始的基本可行解。但是通過(guò)大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變?nèi)绻诖蠓ǖ淖顑?yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔

43、助線性規(guī)劃的目標(biāo)函數(shù)的極小值量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。大于零，那么該線性規(guī)劃就不存在可行解。 無(wú)可行解無(wú)可行解 C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0-M-M x4x7x8 643 1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 6/1-3/1 Z -7M -6-4M -15-M -3+M -2+M -1-2M 0 -M -M 0 0 0-M-2 x4x7x2 343 1 0 2 1 0 1 0 -11 0 -

44、1 0 -1 0 1 00 1 -1 0 0 -1 0 1 3/14/1- Z Z -3+M 0 -3-M 0 -M -2 0 2-M -3-M-2 x1x7x2 313 1 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 例例運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無(wú)可行解。運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無(wú)可行解。 無(wú)最優(yōu)解與無(wú)可行解時(shí)兩個(gè)不同的概念。無(wú)最優(yōu)解與無(wú)可行解時(shí)兩個(gè)不同的概念。 無(wú)可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指無(wú)可行解是指原規(guī)劃不存在可行解，從幾何的角度

45、解釋是指 線性規(guī)劃問(wèn)題的可行域?yàn)榭占?；線性規(guī)劃問(wèn)題的可行域?yàn)榭占?無(wú)最優(yōu)解則是指線性規(guī)劃問(wèn)題存在可行解，但是可行解的目無(wú)最優(yōu)解則是指線性規(guī)劃問(wèn)題存在可行解，但是可行解的目 標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大（或者無(wú)窮?。?。無(wú)最優(yōu)解也稱為有限最優(yōu)解，或無(wú)界解。（或者無(wú)窮小）。無(wú)最優(yōu)解也稱為有限最優(yōu)解，或無(wú)界解。 判別方法：無(wú)最優(yōu)解判別定理判別方法：無(wú)最優(yōu)解判別定理在求解極大化的線性規(guī)劃問(wèn)題過(guò)程中，若某單純形表的檢驗(yàn)在求解極大化的線性規(guī)劃問(wèn)題過(guò)程中，若某單純形表的檢驗(yàn) 行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量

46、行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問(wèn)題的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問(wèn)題 無(wú)最優(yōu)解無(wú)最優(yōu)解 無(wú)最優(yōu)解無(wú)最優(yōu)解C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z022001= 20因因 但但 所以原問(wèn)題無(wú)最優(yōu)解所以原問(wèn)題無(wú)最優(yōu)解1-1P=01-2 退化退化 即計(jì)算出的即計(jì)算出的 （用于確定換出變量）存在有兩個(gè)以上相同的最小（用于確定換出變量）存在有兩個(gè)以上相同的最小比值，會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基變量等于零，這就是比值，會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基

47、變量等于零，這就是退退化化（會(huì)產(chǎn)生退化解）。（會(huì)產(chǎn)生退化解）。 為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特(Bland)提出一個(gè)簡(jiǎn)便有效的規(guī)提出一個(gè)簡(jiǎn)便有效的規(guī)則（攝動(dòng)法原理）：則（攝動(dòng)法原理）： 當(dāng)存在多個(gè)當(dāng)存在多個(gè) 時(shí)，選下標(biāo)最小的非基變量為換入變量；時(shí)，選下標(biāo)最小的非基變量為換入變量；(2) 當(dāng)當(dāng)值出現(xiàn)兩個(gè)以上相同的最小值時(shí)，選下標(biāo)最小的基變量為換值出現(xiàn)兩個(gè)以上相同的最小值時(shí)，選下標(biāo)最小的基變量為換出變量。出變量。0j000-242-8030Z-5-60-420-805Z10001001x3 212060-2411x1 3321300-803x5 00-30-425-800

48、Z1100 1001x7 00106-1-2410 x1 30-1130-3-800 x5 0-11001001x7 000106-1-2410 x6 0000136-4-3210 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C 第一次迭代第一次迭代中使用了攝動(dòng)中使用了攝動(dòng)法原理，選擇法原理，選擇下標(biāo)為下標(biāo)為6的基的基變量變量x6離基。離基?？傻米顑?yōu)解可得最優(yōu)解maxZ=，X1,0,1,0,3T 無(wú)窮多最優(yōu)解無(wú)窮多最優(yōu)解 若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)

49、等于零，那么該數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。例：最優(yōu)表：例：最優(yōu)表：非基變量檢驗(yàn)非基變量檢驗(yàn)數(shù)，數(shù)，所以有無(wú)窮多所以有無(wú)窮多最優(yōu)解。最優(yōu)解。C 1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -10 1 0 1 01 0 0 -2 12/23/1-Z8 0 0 0 0 -14= 0解的判別：解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解。則線性規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判

50、別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線性規(guī)劃具有多重最優(yōu)解（或無(wú)窮多最優(yōu)解）。則線性規(guī)劃具有多重最優(yōu)解（或無(wú)窮多最優(yōu)解）。3）無(wú)界解判別：某個(gè)）無(wú)界解判別：某個(gè)k0且且aik（i=1，2,m）則線性）則線性規(guī)劃具有無(wú)界解。規(guī)劃具有無(wú)界解。4）無(wú)可行解的判斷：當(dāng)用大）無(wú)可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并單純形法計(jì)算得到最優(yōu)解并且存在且存在Ri0時(shí)，則表明原線性規(guī)劃無(wú)可行解。時(shí)，則表明原線性規(guī)劃無(wú)可行解。5）退化解的判別：存在某個(gè)基變量為零的基本可行解。）退化解的判別：存在某個(gè)基變量為零的基本可行解。單純性法小結(jié)單純性法小結(jié):建建立

51、立模模型型個(gè)個(gè) 數(shù)數(shù)取取 值值右右 端端 項(xiàng)項(xiàng)等式或等式或不等式不等式極大或極小極大或極小新加變新加變量系數(shù)量系數(shù)兩兩個(gè)個(gè)三個(gè)三個(gè)以上以上xj0 xj無(wú)無(wú)約束約束xj 0 bi 0bi 0=max Zmin Zxs xa求求解解圖圖解解 法法、單單純純形形法法單單純純形形法法不不處處理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不處處理理約束約束條件條件兩端兩端同乘同乘以以-1-1加加松松弛弛變變量量xs加加入入人人工工變變量量xa減減去去xs加加入入xa不不處處理理令令z=- ZminZ=max z0-M停止停止A Ajjjzc :求求0 j所所有有kj即即找找

52、出出max)()0(0 jika對(duì)對(duì)任任一一)0( lklkiiaab 計(jì)計(jì)算算lkxx替替換換基基變變量量用用非非基基變變量量新新單單純純形形表表列列出出下下一一個(gè)個(gè)ax含有含有量中是否量中是否基變基變 0 j非非基基變變量量的的有有某某個(gè)個(gè)最最優(yōu)優(yōu)解解一一唯唯 無(wú)無(wú)可可行行解解最優(yōu)解最優(yōu)解無(wú)窮多無(wú)窮多是是否否環(huán)環(huán)循循否否否否否否是是是是是是循環(huán)循環(huán)無(wú)無(wú)界界解解一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿足以下條一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿足以下條件時(shí)，才能建立線性規(guī)劃模型。件時(shí)，才能建立線性規(guī)劃模型。 要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線性函

53、數(shù)為線性函數(shù) 存在著多種方案存在著多種方案 要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述束可用線性等式或不等式描述常見問(wèn)題常見問(wèn)題合理利用線材問(wèn)題：如何下料使用材最少。合理利用線材問(wèn)題：如何下料使用材最少。配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)。利潤(rùn)。投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。最大。產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。使獲利最大。勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)

54、滿足工作的需要。勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要。運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。 (1)設(shè)立決策變量；設(shè)立決策變量； (2)明確約束條件并用決策變量的線性等式或不等式表明確約束條件并用決策變量的線性等式或不等式表示；示； (3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。ǎ┻€是極小（Min）；）； (4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。建立線性規(guī)劃模型的過(guò)程可以分為四個(gè)步驟：建立線性規(guī)劃模型的過(guò)程可以分為四個(gè)步驟

55、：1. 資源的合理利用資源的合理利用 某廠計(jì)劃在下一生產(chǎn)周期內(nèi)生產(chǎn)某廠計(jì)劃在下一生產(chǎn)周期內(nèi)生產(chǎn)B1,B2, Bn種產(chǎn)品，要消耗種產(chǎn)品，要消耗A1,A2, Am種資源，已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限種資源，已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限制以及每件產(chǎn)品可獲得的利潤(rùn)如表所示，問(wèn)如何安排生產(chǎn)計(jì)劃，才能充制以及每件產(chǎn)品可獲得的利潤(rùn)如表所示，問(wèn)如何安排生產(chǎn)計(jì)劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤(rùn)最大？分利用現(xiàn)有的資源，使獲得的總利潤(rùn)最大？單件單件 產(chǎn)產(chǎn) 消耗消耗 品品資源資源資源資源限制限制單件利潤(rùn)單件利潤(rùn)1 nBBL1 mAAM1 mbbM1 CnCL1111 nmm n

56、aaaaLMML 0maxjijijjjxbxaxcZ模型2. 生產(chǎn)組織與計(jì)劃問(wèn)題生產(chǎn)組織與計(jì)劃問(wèn)題 某工廠用機(jī)床某工廠用機(jī)床A1,A2, Am 加工加工B1,B2, Bn 種零件。在一個(gè)周期內(nèi)，種零件。在一個(gè)周期內(nèi)，各機(jī)床可能工作的機(jī)時(shí)（臺(tái)時(shí)），工廠必須完成各種零件的數(shù)量、各機(jī)各機(jī)床可能工作的機(jī)時(shí)（臺(tái)時(shí)），工廠必須完成各種零件的數(shù)量、各機(jī)床加工每個(gè)零件的時(shí)間（機(jī)時(shí)床加工每個(gè)零件的時(shí)間（機(jī)時(shí)/個(gè)）和加工每個(gè)零件的成本（元個(gè)）和加工每個(gè)零件的成本（元/個(gè)）如表個(gè)）如表所示，問(wèn)如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使總成本所示，問(wèn)如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使總成本最低？

57、最低？加工加工 零零 時(shí)間時(shí)間 件件機(jī)床機(jī)床機(jī)時(shí)機(jī)時(shí)限制限制必須零件數(shù)必須零件數(shù)1 nBBL1 maaM1 nbbL1 111 nmm naaaaLMML加工加工 零零 成本成本 件件機(jī)床機(jī)床1 nBBL1 mAAM1 111 nmm nccccLMML1 mAAM 0 min ( 11ijjijiijijminjijijijjiijxbxaxaxcZxBAx一一組組變變量量）。模模型型：的的數(shù)數(shù)量量，求求在在一一生生產(chǎn)產(chǎn)周周期期加加工工零零件件為為機(jī)機(jī)床床設(shè)設(shè)某廠生產(chǎn)某廠生產(chǎn)、三種產(chǎn)品，都分別經(jīng)三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設(shè)兩道工序加工。設(shè)A工序可分別在設(shè)備工序可分別在設(shè)備A1和和

58、A2上完上完成，有成，有B1、B2、B3三種設(shè)備可用于完成三種設(shè)備可用于完成B工序。已知工序。已知產(chǎn)品產(chǎn)品可在可在A、B任何一種設(shè)備上加工；產(chǎn)品任何一種設(shè)備上加工；產(chǎn)品可在可在任何規(guī)格的任何規(guī)格的A設(shè)備上加工，但完成設(shè)備上加工，但完成B工序時(shí)，只能在工序時(shí)，只能在B1設(shè)備上加工；產(chǎn)品設(shè)備上加工；產(chǎn)品只能在只能在A2與與B2設(shè)備上加工。設(shè)備上加工。加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表，加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。設(shè)備設(shè)備產(chǎn)品產(chǎn)品設(shè)備有效設(shè)備有效臺(tái)時(shí)臺(tái)時(shí)設(shè)備加工費(fèi)設(shè)備加工費(fèi)（單位小時(shí)）（單位小時(shí)）A1

59、5106000300A2791210 000321B1684000250B24117000783B374000200原料費(fèi)（每件）原料費(fèi)（每件）0.250.350.5售價(jià)（每件）售價(jià)（每件）1.252.002.8解：設(shè)解：設(shè)xijk表示產(chǎn)品表示產(chǎn)品i在工序在工序j的設(shè)備的設(shè)備k上加工的數(shù)量。約束條上加工的數(shù)量。約束條件有：件有：）（上加工的數(shù)量相等）上加工的數(shù)量相等），在工序在工序（產(chǎn)品（產(chǎn)品上加工的數(shù)量相等）上加工的數(shù)量相等），在工序在工序（產(chǎn)品（產(chǎn)品上加工的數(shù)量相等）上加工的數(shù)量相等），在工序在工序（產(chǎn)品（產(chǎn)品設(shè)備設(shè)備設(shè)備設(shè)備）（設(shè)備（設(shè)備）（設(shè)備（設(shè)備設(shè)備設(shè)備3 , 2 , 1; 2 ,

60、 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(6000105322312221212211123122121112111123322122221121312212112211111 kjixxxxxxxxxxxxxxxxxxxxxijk目標(biāo)是利潤(rùn)最大化，即利潤(rùn)的計(jì)算公式如下：目標(biāo)是利潤(rùn)最大化，即利潤(rùn)的計(jì)算公式如下： 5131)()(ii該該設(shè)設(shè)備備實(shí)實(shí)際際使使用用臺(tái)臺(tái)時(shí)時(shí)每每臺(tái)臺(tái)時(shí)時(shí)的的設(shè)設(shè)備備費(fèi)費(fèi)用用該該產(chǎn)產(chǎn)品品件件數(shù)數(shù)銷銷售售單單價(jià)價(jià)原原料料單單價(jià)價(jià)利利潤(rùn)潤(rùn)帶入數(shù)據(jù)整理得到：帶入數(shù)據(jù)整理得到：123