第1,2章緒論、線性規(guī)劃與單純形法ppt

1、運(yùn)運(yùn) 籌籌 學(xué)學(xué)( Operations Research )運(yùn) 籌 帷 幄 之 中決 勝 千 里 之 外緒 論Introduction第一章（1）運(yùn)籌學(xué)簡(jiǎn)述（2）運(yùn)籌學(xué)的主要內(nèi)容（3）本課程的教材及參考書(shū)（4）本課程的特點(diǎn)和要求（5）本課程授課方式與考核 （6）運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用本章主要內(nèi)容：運(yùn)籌學(xué)（運(yùn)籌學(xué)（Operations Research,簡(jiǎn)寫(xiě)簡(jiǎn)寫(xiě)OR ）系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國(guó)有人把運(yùn)籌系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國(guó)有人把運(yùn)籌學(xué)稱(chēng)之為管理科學(xué)學(xué)稱(chēng)之為管理科學(xué)(Management Science)。運(yùn)籌學(xué)所研究的。運(yùn)籌學(xué)所研究的問(wèn)題，可簡(jiǎn)單地歸結(jié)為一句話

2、：?jiǎn)栴}，可簡(jiǎn)單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱(chēng)之為故有人稱(chēng)之為最優(yōu)化技術(shù)最優(yōu)化技術(shù)。運(yùn)籌學(xué)的歷史與發(fā)展 “運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早“田忌賽馬” 。 齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對(duì)局三次，每次勝負(fù)1000金。田忌在好友、著名的軍事謀略家孫臏的指導(dǎo)下，以以下安排： 齊王 上中 下 田忌 下上 中丁謂的皇宮修復(fù)工程 北宋年間，丁謂負(fù)責(zé)修復(fù)火毀的開(kāi)封皇宮。他的施工方案是：先將皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔(dān)繁重的運(yùn)輸任務(wù)；修復(fù)工

3、程完成后，實(shí)施大溝排水，并將原廢墟物回填，修復(fù)成原來(lái)的大街。丁謂將取材、運(yùn)輸及清廢用“一溝三用”巧妙地解決了，體現(xiàn)了系統(tǒng)規(guī)劃的思想。 國(guó)際上運(yùn)籌學(xué)的思想可追溯到1914年，當(dāng)時(shí)的蘭徹斯特提出了軍事運(yùn)籌學(xué)的作戰(zhàn)模型。1917年，丹麥工程師埃爾朗在研究自動(dòng)電話系統(tǒng)中通話線路與用戶呼叫的數(shù)量關(guān)系問(wèn)題時(shí)，提出了埃爾朗公式，研究了隨機(jī)服務(wù)系統(tǒng)中的系統(tǒng)排隊(duì)與系統(tǒng)擁擠問(wèn)題。存儲(chǔ)論的最優(yōu)批量公式是在20世紀(jì)20年代初提出的?！斑\(yùn)作研究(Operational Research)小組”:解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題。例如：1. 如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍德空襲2. 對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊

4、時(shí)損失最少；3. 在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷力等。 在生產(chǎn)管理方面的應(yīng)用，最早是1939年前蘇聯(lián)的康特洛為奇提出了生產(chǎn)組織與計(jì)劃中的線性規(guī)劃問(wèn)題，并給出解乘數(shù)法的求解方法，出版了第一部關(guān)于線性規(guī)劃的著作生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法。 但當(dāng)時(shí)并沒(méi)有引起重視，直到1960年康特洛為奇再次出版了最佳資源利用的經(jīng)濟(jì)計(jì)算，才受到國(guó)內(nèi)外的一致重視，為此康特洛為奇獲得了諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。 線性規(guī)劃提出后很快受到經(jīng)濟(jì)學(xué)家的重視，如：二次世界大戰(zhàn)中從事運(yùn)輸模型研究的美國(guó)經(jīng)濟(jì)學(xué)家?guī)炱章梗═.C.Koopmans），他很快看到了線性規(guī)劃在經(jīng)濟(jì)中應(yīng)用的意義，并呼吁年輕的經(jīng)濟(jì)學(xué)家

5、要關(guān)注線性規(guī)劃。其中阿羅、薩謬爾遜、西蒙、多夫曼和胡爾威茨等都獲得了諾貝爾獎(jiǎng)。 20世紀(jì)50年代中期，錢(qián)學(xué)森、許國(guó)志等教授在國(guó)內(nèi)全面介紹和推廣運(yùn)籌學(xué)知識(shí)，1956年，中國(guó)科學(xué)院成立第一個(gè)運(yùn)籌學(xué)研究室，1957年運(yùn)籌學(xué)運(yùn)用到建筑和紡織業(yè)中，1958年提出了圖上作業(yè)法，山東大學(xué)的管梅谷教授提出了“中國(guó)郵遞員問(wèn)題”，1970年，在華羅庚教授的直接指導(dǎo)下，在全國(guó)范圍內(nèi)推廣統(tǒng)籌方法和優(yōu)選法。 1978年11月，在成都召開(kāi)了全國(guó)數(shù)學(xué)年會(huì)，對(duì)運(yùn)籌學(xué)的理論與應(yīng)用研究進(jìn)行了一次檢閱，1980年4月在山東濟(jì)南正式成立了“中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)會(huì)”，1984年在上海召開(kāi)了“中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)會(huì)第二屆代表大會(huì)暨學(xué)術(shù)交流會(huì)”，

6、并將學(xué)會(huì)改名為“中國(guó)運(yùn)籌學(xué)會(huì)”。成熟的學(xué)科分支向縱深發(fā)展新的研究領(lǐng)域產(chǎn)生與新的技術(shù)結(jié)合與其他學(xué)科的結(jié)合加強(qiáng)傳統(tǒng)優(yōu)化觀念不斷變化運(yùn)籌學(xué)的發(fā)展趨勢(shì)數(shù)學(xué)規(guī)劃（數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)、動(dòng)態(tài)規(guī)劃等）規(guī)劃等）圖論圖論存儲(chǔ)論存儲(chǔ)論排隊(duì)論排隊(duì)論對(duì)策論對(duì)策論決策分析決策分析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 Progra

7、m)：在線性規(guī)劃的基礎(chǔ)上，變：在線性規(guī)劃的基礎(chǔ)上，變量加上整數(shù)約束。量加上整數(shù)約束。3. 非線性規(guī)劃非線性規(guī)劃(Nonlinear Program)：目標(biāo)函數(shù)和約束條件：目標(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)題。題、哥尼

8、斯堡城問(wèn)題、最短路、最大流問(wèn)題。6、存儲(chǔ)論（、存儲(chǔ)論（Inventory Theory)：主要解決生產(chǎn)中的庫(kù)存問(wèn)：主要解決生產(chǎn)中的庫(kù)存問(wèn)題，訂貨周期和訂貨量等問(wèn)題。題，訂貨周期和訂貨量等問(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) ：主要研究定量化決策。：主要研究定量化決策。17

9、運(yùn)籌學(xué)方法使用情況運(yùn)籌學(xué)方法使用情況( (美美1983)1983)18 運(yùn)籌學(xué)方法在中國(guó)使用情況運(yùn)籌學(xué)方法在中國(guó)使用情況 ( (隨機(jī)抽樣隨機(jī)抽樣) )選用教材選用教材 運(yùn)籌學(xué)運(yùn)籌學(xué)教材編寫(xiě)組 （第3版）清華大學(xué)出版社參考教材參考教材運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用胡運(yùn)權(quán)主編 哈工大出版社管理運(yùn)籌學(xué)韓伯棠主編 （第2版）高等教育出版社運(yùn)籌學(xué)(修訂版) 錢(qián)頌迪主編 清華出版社先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點(diǎn)：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用運(yùn)籌學(xué)的研究的主要步驟：真實(shí)系統(tǒng)系統(tǒng)分析問(wèn)題描述模型建立與修改模型求解與檢驗(yàn)結(jié)果分析與實(shí)施數(shù)據(jù)準(zhǔn)備學(xué)科總成績(jī)學(xué)科總成績(jī)平時(shí)成績(jī)平時(shí)成績(jī)（30）課堂考勤課堂考勤

10、（50）平時(shí)作業(yè)平時(shí)作業(yè)（50）期末成績(jī)期末成績(jī)（70）講授為主，結(jié)合習(xí)題作業(yè)運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用涉及的方面：運(yùn)籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用涉及的方面：1. 生產(chǎn)計(jì)劃2. 運(yùn)輸問(wèn)題3. 人事管理4. 庫(kù)存管理5. 市場(chǎng)營(yíng)銷(xiāo)6. 財(cái)務(wù)和會(huì)計(jì)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)籌學(xué)管理運(yùn)籌學(xué)”2.02.0版包括：線性規(guī)劃、運(yùn)輸問(wèn)題、整數(shù)規(guī)劃（版包括：線性規(guī)劃、運(yùn)輸問(wèn)題、整數(shù)規(guī)劃（0-10-1整數(shù)整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對(duì)策論、最短路徑、規(guī)劃、

11、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對(duì)策論、最短路徑、最小生成樹(shù)、最大流量、最小費(fèi)用最大流、關(guān)鍵路徑、存儲(chǔ)論、排隊(duì)論、最小生成樹(shù)、最大流量、最小費(fèi)用最大流、關(guān)鍵路徑、存儲(chǔ)論、排隊(duì)論、決策分析、預(yù)測(cè)問(wèn)題和層次分析法，共決策分析、預(yù)測(cè)問(wèn)題和層次分析法，共1515個(gè)子模塊。個(gè)子模塊。運(yùn) 籌 帷 幄 之 中決 勝 千 里 之 外線性規(guī)劃及單純形法Linear Programming第一章第一章Chapter1 線性規(guī)劃線性規(guī)劃 (Linear Programming) LP的數(shù)學(xué)模型 圖解法 單純形法 單純形法的進(jìn)一步討論人工變量法 LP模型的應(yīng)用1. 規(guī)劃問(wèn)題規(guī)劃問(wèn)題生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合

12、理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問(wèn)題。（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤(rùn)最大.）例1.1 某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D 四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤(rùn)最大？ 設(shè)設(shè) 備備產(chǎn)產(chǎn) 品品 A B C D利潤(rùn)（元）利潤(rùn)（元） 甲甲 2 1 4 0 2 乙乙 2 2

13、 0 4 3 有有 效效 臺(tái)臺(tái) 時(shí)時(shí) 12 8 16 12例1.2 某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量 解：要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過(guò)180單位，且使原料總成本最小。1.決策變量：設(shè)四種原料的使用 量分別為：x1、x2 、x3 、x42.目標(biāo)函數(shù)：設(shè)總成本為z min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.約束條件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x4 0

14、00 )( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 簡(jiǎn)寫(xiě)為：) (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,

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

16、（1）例1.3 將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321無(wú)無(wú)約約束束xxxxxxxxxxxxxxxZ 解:（）因?yàn)閤3無(wú)符號(hào)要求 ，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以用 替換 ， 且33xx 3x0,33 xx(2) 第一個(gè)約束條件是“”號(hào)，在“”左端加入松馳變量x4，x40,化為等式；(3) 第二個(gè)約束條件是“”號(hào)，在“”左端減去剩余變量x5，x50；(4) 第3個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1),將右端常數(shù)項(xiàng)化為正數(shù)； (5) 目標(biāo)函數(shù)是最小值，為了化為求最大值，令z=-z,得到max z=-z，即當(dāng)z

17、達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然;12334512334123351233123345max23()005() 7 () 252() 5,0 Zxxxxxxxxxxxxxxxxxxxxx xxxxx標(biāo)準(zhǔn)形式如下： 無(wú)約束2121212,0435832xxxxxxx-xminZ10 x ,x ,x ,x ,xx)x(xxx)x(xx)x(xxZaxm1111654364354343435832例1.4 將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型解： 例1.5 將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型解：Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4

18、 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)題的解線性規(guī)劃問(wèn)題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnj

19、ijijnjjj線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題，就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。 可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。 最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。 基：設(shè)A為約束條件的mn系數(shù)矩陣(m04010換出行將3化為15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/52/540011最優(yōu)解為：X*=(18,4,0,0)T,目標(biāo)函數(shù)值為z*=318+44=70.例例1.13 用單純形法求解用單純形法求解 02053115232.2max321321321321

20、xxxxxxxxxtsxxxZ、解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。cj12100icB基變量基變量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 2021/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9-1/9-7/3j 學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及3個(gè)基本定理2. 熟練掌握線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化

21、3.熟練掌握單純形法的解題思路及求解步驟人工變量法人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱(chēng)為的變量稱(chēng)為人工變量人工變量，構(gòu)成的可行基稱(chēng)為，構(gòu)成的可行基稱(chēng)為人工基人工基，用，用大大MM法法或或兩階段法兩階段法求解，這種用人工變量作

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

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

24、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)形式1231234123513max3 2114232 10,1,2,5jZxxxxxxxxxxxxxxjL系數(shù)矩陣中不存在單位矩陣，無(wú)法建立初始單純形表。故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：123456712

25、3412356137max3 3 11 -4 2 + 3 2 10,1,2,7jZxxxxxMxMxxxxxxxxxxxxxxjL+0 +0 其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見(jiàn)下表。 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

26、-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-1x210100-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ù)代替M,可能造成計(jì)算機(jī)上的錯(cuò)誤，故多采用兩階段法。 第一階段： 在原線性規(guī)劃問(wèn)題中加入人工變量，構(gòu)造如下模型：1111 11111 1min00 nn mnnnnmmnnn mmxxxxa xa

27、xxba xaxxbLLLMMOL1 0 n mxxL 對(duì)上述模型求解（單純形法），若=0,說(shuō)明問(wèn)題存在基可行解，可以進(jìn)行第二個(gè)階段；否則，原問(wèn)題無(wú)可行解，停止運(yùn)算。第一階段的線性規(guī)劃問(wèn)題可寫(xiě)為：67123412356137min 2 =11 42 3 2 1 xxxxxxxxxxxxxx127 ,0 x xx，第一階段單純形法迭代的過(guò)程見(jiàn)下表（注意：沒(méi)有化為極大化問(wèn)題）Cj0000011CBXBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-2010001146-1-301000 x4103-20100-11x610100-11-210

28、 x31-201000110-1001030 x4123001-22-50 x210100-11-20 x31-201000000000011 第二階段： 在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表（用單純形法計(jì)算）。例： x,x ,x x x x xx xxx xxx x xxxZmax 0123241123721731653214321321，cj3-1-100cBxBbx1x2x3x4x50 x4123001-24-1x210100-1-1x31-20100Z-21000-13x141001/3-2/3-1x210100-1-1

29、x390012/3-4/3Z2000-1/3-1/3第二階段：54321003xxxxxZmax 最優(yōu)解為（4 1 9 0 0），目標(biāo)函數(shù) Z = 2 通過(guò)大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有非零人非零人工變量工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。 無(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

30、/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 -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ú)可行解。 無(wú)最優(yōu)解與無(wú)可行解是兩個(gè)不同的概念。

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

32、優(yōu)解1-1P=01-2 退化 即計(jì)算出的 （用于確定換出變量）存在有兩個(gè)以上相同的最小比值，會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基變量等于零，這就是退化（會(huì)產(chǎn)生退化解）。 為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特(Bland)提出一個(gè)簡(jiǎn)便有效的規(guī)則（攝動(dòng)法原理）： 當(dāng)存在多個(gè) 時(shí)，選下標(biāo)最小的非基變量為換入變量；(2) 當(dāng)值出現(xiàn)兩個(gè)以上相同的最小值時(shí)，選下標(biāo)最小的基變量為換出變量。0j000-242-8030Z-5-60-420-805Z10001001x3 212060-2411x1 3321300-803x5 00-30-425-800Z1100 1001x7 00106-1-2410 x1 30-1130

33、-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)法原理，選擇下標(biāo)為6的基變量x6離基?？傻米顑?yōu)解maxZ=，X1,0,1,0,3T 無(wú)窮多最優(yōu)解 若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。例：最優(yōu)表：非基變量檢驗(yàn)數(shù)，所以有無(wú)窮多最優(yōu)解。C 1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -

34、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ù)非零,則線性規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線性規(guī)劃具有多重最優(yōu)解（或無(wú)窮多最優(yōu)解）。3）無(wú)界解判別：某個(gè)k0且aik（i=1，2,m）則線性規(guī)劃具有無(wú)界解。4）無(wú)可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri0時(shí)，則表明原線性規(guī)劃無(wú)可行解。5）退化解的判別：存在某個(gè)基變量為零的基本可行解。單純性法小結(jié)單純性法小結(jié):建建立立模模型型變量個(gè)數(shù)變量個(gè)數(shù)變量取值變量取值約束條件約束條件目標(biāo)函數(shù)目標(biāo)函數(shù)新

35、加變新加變量系數(shù)量系數(shù)兩兩個(gè)個(gè)三個(gè)三個(gè)以上以上x(chóng)j0 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停止停止Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika對(duì)對(duì)任任一一)0( lklkiiaab 計(jì)計(jì)算算lkxx替替換換

36、基基變變量量用用非非基基變變量量新新單單純純形形表表列列出出下下一一個(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)反映，且為線性函數(shù) 存在著多種方案 要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述常見(jiàn)問(wèn)題常見(jiàn)問(wèn)題合理利用線材問(wèn)題：如何下料使用材最

37、少。配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)。投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要。運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。 (1)設(shè)立決策變量； (2)明確約束條件并用決策變量的線性等式或不等式表示； (3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極小（Min）； (4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。建立線性規(guī)劃模型的過(guò)程可以分為四個(gè)步驟：例10. 合理利用線材問(wèn)題?，F(xiàn)要做?，F(xiàn)要做100套鋼架，每套需套鋼架，每套需用長(zhǎng)為用長(zhǎng)為2.9m，2.1m和

38、和1.5m的元鋼各一根。已知原料的元鋼各一根。已知原料長(zhǎng)長(zhǎng)7.4m，問(wèn)應(yīng)如何下料，使用的原材料最省。，問(wèn)應(yīng)如何下料，使用的原材料最省。表1-11解：若在每一根原材料上截取2.9m，2.1m和1.5m的元鋼各一根組成一套，每根原材料剩下料頭0.9m（7.4-2.9-2.1-1.5=0.9)。為了做100套鋼架，需用原材料100根，共有90m料頭。若改為用套裁，這可以節(jié)約原材料。下面有幾種套裁方案，都可以考慮采用。見(jiàn)表1-11。為了得到為了得到100套鋼架，需要混合使用各種下料方案。設(shè)按套鋼架，需要混合使用各種下料方案。設(shè)按方方案下料的原材料根數(shù)為案下料的原材料根數(shù)為x1,方案為方案為x2，方案為

39、方案為x3，方案為方案為x4,方案為方案為x5。根據(jù)表。根據(jù)表1-11的方案，可列出以下數(shù)學(xué)模型：的方案，可列出以下數(shù)學(xué)模型：0,1003231002210028 . 03 . 02 . 01 . 00min54321532154342154321xxxxxxxxxxxxxxxxxxxxz在以上約束條件中加入人工變量在以上約束條件中加入人工變量x6,x7,x8；然后用表；然后用表1-12進(jìn)行進(jìn)行計(jì)算。計(jì)算。表1-12cj00.10.20.30.8-M-M - -MiCBXBbx1x2x3x4x5x6x7x8-M-M-Mx6x7x810010010010320102 21200101000100

40、01100/1100/3 cj-zj4M-0.1+3M-0.2+4M-0.3+3M-0.8+4M000第第1次計(jì)算次計(jì)算cj 0 0.1 0.2 0.3 0.8 -M -M -M i CB XB b x1 x2 x3 x4 x5 x6 x7 x8 -M -M 1 x6 x7 x1 200/3 100 100/3 0 0 1 5/3 0 1/3 -2/3 2 2/3 1 2 0 -1 1 1 1 0 0 0 1 0 -1/3 0 1/3 200/3 100/2 cj-zj 0 -0.1+5/3M -0.2+4/3M -0.3+3M -0.8 0 0 -4/3M 第第2次計(jì)算次計(jì)算最終計(jì)算表（第最

41、終計(jì)算表（第3次計(jì)算）次計(jì)算）由計(jì)算得到最優(yōu)下料方案是：按方案下料30根；方案下料10根；方案下料50根。即需90根原材料可以制造100套鋼架。有非基變量的檢驗(yàn)數(shù)為零，所以存在多重最優(yōu)解 。cj00.10.20.30.8-M-M-MiCBXBbx1x2x3x4x5x6x7x80.1-0.30 x2x4x1105030001100-111010-9/101/313/103/50-1/5-3/101/31/10-1/502/5 cj-zj 0000-0.74-M+0.06-M+0.12-M-0.02某工廠要用三種原材料某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的混合調(diào)配出三種不同規(guī)格的產(chǎn)

42、品產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格要求，產(chǎn)品單價(jià)，每天能供。已知產(chǎn)品的規(guī)格要求，產(chǎn)品單價(jià)，每天能供應(yīng)的原材料數(shù)量及原材料單價(jià)，分別見(jiàn)表應(yīng)的原材料數(shù)量及原材料單價(jià)，分別見(jiàn)表1-13和表和表1-14。該廠。該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大? 表1-13例例1111 配料問(wèn)題配料問(wèn)題 產(chǎn)品名稱(chēng)產(chǎn)品名稱(chēng)規(guī)規(guī) 格格 要要 求求單價(jià)（元單價(jià)（元/kg/kg）A A原材料原材料C C不少于不少于50%50%原材料原材料P P不超過(guò)不超過(guò)25%25%5050B B原材料原材料C C不少于不少于25%25%原材料原材料P P不超過(guò)不超過(guò)50%50%3535D D不限不限2525

43、表表1-14表明這些原材料供應(yīng)數(shù)量的限額。加入到產(chǎn)品表明這些原材料供應(yīng)數(shù)量的限額。加入到產(chǎn)品A、B、D的原材料的原材料C總量每天不超過(guò)總量每天不超過(guò)100kg，P的總量不超過(guò)的總量不超過(guò)100kg，H總量不超過(guò)總量不超過(guò)60kg。原材料名稱(chēng) 每天最多供應(yīng)量（kg） 單價(jià)/(元/kg) C 100 65 P 100 25 H 60 35 表1-14根據(jù)表根據(jù)表1-13有：有：)391 (21,41,41,21BBBBAAAAPCPC這里 AC+AP+AH=A； BC+BP+BH=B (1-40)將(1-40)逐個(gè)代入(1-39)并整理得到0214121041414304143410212121H

44、PCHPCHPCHPCBBBBBBAAAAAA解：解： 如以如以AC表示產(chǎn)品表示產(chǎn)品A中中C的成分，的成分，AP表示產(chǎn)品表示產(chǎn)品A中中P的成分，依次類(lèi)推。的成分，依次類(lèi)推。由此得約束條件由此得約束條件AC+BC+DC100AP+BP+DP100AH+BH+DH60在約束條件中共有9個(gè)變量，為計(jì)算和敘述方便，分別用x1,x9表示。令x1=Ac, x2=Ap, x3=AH,x4=BC, x5=BP, x6=BH,x7=DC, x8=DP, x9=DH.約束條件可表示為：約束條件可表示為：0,601001000212121041414304143410212121919638527416546543

45、21321xxxxxxxxxxxxxxxxxxxxxxx目標(biāo)函數(shù)n目的是使利潤(rùn)最大，即產(chǎn)品價(jià)格減去原材料的價(jià)格為最大。目的是使利潤(rùn)最大，即產(chǎn)品價(jià)格減去原材料的價(jià)格為最大。n產(chǎn)品價(jià)格為：產(chǎn)品價(jià)格為：50(x1+x2+x3)產(chǎn)品產(chǎn)品A 35(x4+x5+x6) 產(chǎn)品產(chǎn)品B 25(x7+x8+x9) 產(chǎn)品產(chǎn)品Dn原材料價(jià)格為：原材料價(jià)格為：65(x1+x4+x7)原材料原材料C 25(x2+x5+x8) 原材料P 35(x3+x6+x9) 原材料H為了得到初始解，在約束條件中加入松弛變量x10 x16，得到數(shù)學(xué)模型：例例11的線性規(guī)劃模型的線性規(guī)劃模型0,6010010002121210414143

46、04143410212121010401030152515max18109116963158521474113654126541132110321161514131211109754321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz約束條件目標(biāo)函數(shù)最優(yōu)解最優(yōu)解n用單純形法計(jì)算，經(jīng)過(guò)四次迭代，得最優(yōu)解為：用單純形法計(jì)算，經(jīng)過(guò)四次迭代，得最優(yōu)解為： x1=100,x2=50,x3=50n這表示：需要用原料這表示：需要用原料C為為100kg，P為為50kg，H為為50kg，構(gòu)，構(gòu)成產(chǎn)品成產(chǎn)品A。n即每天只生產(chǎn)產(chǎn)品即每天只生產(chǎn)產(chǎn)品A為為200kg，分別

47、需要用原料，分別需要用原料C為為100kg，P為為50kg，H為為50kg。n從最終計(jì)算表中得到，總利潤(rùn)是從最終計(jì)算表中得到，總利潤(rùn)是z=500元元/天。天。例例12 優(yōu)化安排問(wèn)題優(yōu)化安排問(wèn)題 某快遞公司下設(shè)一個(gè)快件分揀部，處理每天到達(dá)和外寄某快遞公司下設(shè)一個(gè)快件分揀部，處理每天到達(dá)和外寄的快件。根據(jù)統(tǒng)計(jì)資料及經(jīng)驗(yàn)預(yù)測(cè)，每天各時(shí)段快件數(shù)量的快件。根據(jù)統(tǒng)計(jì)資料及經(jīng)驗(yàn)預(yù)測(cè)，每天各時(shí)段快件數(shù)量如下表所示。如下表所示。180時(shí)段時(shí)段到達(dá)快件數(shù)到達(dá)快件數(shù)時(shí)段時(shí)段到達(dá)快件數(shù)到達(dá)快件數(shù)10：00以前500014:00-15:00300010:00-11:00400015:00-16:00400011:00-

48、12:00300016:00-17:00450012:00-13:00400017:00-18:00350013:00-14:00250018:00-19:002500清華大學(xué)出版社181快件分揀由機(jī)器操作，分揀效率為每臺(tái)快件分揀由機(jī)器操作，分揀效率為每臺(tái)500件件/h,每臺(tái)機(jī)器操作每臺(tái)機(jī)器操作時(shí)需要配一名職工。共有時(shí)需要配一名職工。共有11臺(tái)機(jī)器。分揀部一部分是全日制臺(tái)機(jī)器。分揀部一部分是全日制職工，上班時(shí)間分別為：職工，上班時(shí)間分別為：10:00-18:00,11:00-19:00和和12：00-20:00，每人每天工資，每人每天工資150元，另一部分是非全日制職工，每元，另一部分是非全日

49、制職工，每天上班天上班5小時(shí)，分別為小時(shí)，分別為13:00-18:00,14:00-19:00,15:00-20:00，每人每天工資每人每天工資80元?？旒幚淼囊?guī)則是：從每個(gè)整點(diǎn)起可處元。快件處理的規(guī)則是：從每個(gè)整點(diǎn)起可處理該整點(diǎn)前到達(dá)的快件，例如從理該整點(diǎn)前到達(dá)的快件，例如從11：00起可處理起可處理10:00前和前和10：00-11:00之間到達(dá)的快件，之間到達(dá)的快件，13:00起可整理所有這之前到達(dá)的起可整理所有這之前到達(dá)的等。因快件有時(shí)間性要求，凡是等。因快件有時(shí)間性要求，凡是12:00前到達(dá)的快件必須在前到達(dá)的快件必須在14:00以前處理完；以前處理完；15:00以前到達(dá)的，必須在以前到達(dá)的，必須在17：00以前處理以前處理完；全部快件在當(dāng)天完；全部快件在當(dāng)天20:00以