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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、兼顧，合理安排，用最少的資源最少的資源 （如資金、設(shè)備、原標材料、人工、時間等）（如資金、設(shè)備、原標材料、人工、時間等）去完成確定的任務(wù)或目標去完成確定的任務(wù)或目標（2 2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多好的經(jīng)濟效益（如產(chǎ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)品利潤源及單位產(chǎn)品利潤 問：應(yīng)如何安排生產(chǎn)計劃，才問：應(yīng)如何安排生產(chǎn)計劃，才能使總利潤最大？能使總利潤最大？ 解：解：1.1.決策變量：設(shè)產(chǎn)品決策變量：設(shè)產(chǎn)品I I、IIII的產(chǎn)量的產(chǎn)量 分別為分別為 x1、x22.2.目標函數(shù)：設(shè)總利潤為目標函數(shù)：設(shè)總利潤為z z，則有：，則有： max z = 2 x1 + x23.3.約束條件：約束條件： 5x2 15 6x1+ 2x2 24 x1+ x2 5 x1， x20例例1.3 已知資料如下表所示，已知資料如下表所示，問如何安排生產(chǎn)才能使利潤問如何安排生產(chǎn)才能使利潤最大？或如何考慮利潤大，最大？或如何考慮利

18、潤大，產(chǎn)品好銷。產(chǎn)品好銷。 設(shè) 備產(chǎn) 品 A B C D利潤（元） 2 1 4 0 2 2 2 0 4 3 有 效 臺 時12 8 16 12解：解：1.1.決策變量：設(shè)產(chǎn)品決策變量：設(shè)產(chǎn)品I I、IIII的產(chǎn)量的產(chǎn)量分別為分別為 x1、x22.2.目標函數(shù)：設(shè)總利潤為目標函數(shù)：設(shè)總利潤為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種藥物不超過種藥物不超過180單位，且單位，且使原料總成本最小。使原料總成本最小。1.1.決策變量：設(shè)四種原料的使用決策變量：設(shè)四種原料的使用 量分別為：量分別為：x1、x2 、x3 、x42.2.目標函數(shù)：設(shè)總成本為目標函數(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 某航運局現(xiàn)有船只種類、數(shù)量以及計劃期內(nèi)各條航某航運局現(xiàn)有船只種類、數(shù)量以及計劃期內(nèi)各條航線的貨運量、貨運成本如下表所示：線的貨運量、貨運成本如下表所示：航線號航線號船隊船隊類型類型編隊形式編隊形式貨運成本貨運成本（千元隊）（千元隊）貨運量貨運量（千噸）（千噸）拖輪拖輪A型型駁船駁船B型型駁船駁船1112362521436202322472404142720船只種類船只種類船只數(shù)船只數(shù)拖拖 輪輪30A型駁船型駁船34B型駁船型駁船52航線號航線號合同貨運量合同貨運量12002400問：應(yīng)如何編隊，才能既完成合同任務(wù)

21、，又使總貨運成本為最??？問：應(yīng)如何編隊，才能既完成合同任務(wù)，又使總貨運成本為最??？ 解：解：設(shè)：設(shè)：x xj j為第為第j j號類型船隊的隊數(shù)（號類型船隊的隊數(shù)（j = 1j = 1，2 2，3 3，4 4），）， z z 為總貨運成本為總貨運成本則：則： 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 簡寫為：簡寫為：) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中：其中： mnmnaaaaA1111 0 )( (min) maxXBAXCXZ其中：其中：) (21ncccC nxxX1 mbbB16. 線性規(guī)劃問題的標準形式線性規(guī)劃問題的標準形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特點：特點：(1

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

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

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

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

27、極小值問題反號，變?yōu)榍髽O大值將極小值問題反號，變?yōu)榍髽O大值標準形式如下：標準形式如下： 0,5 )(252 )( 7 )(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ76, xx引入變量引入變量 無約束2121212,0435832xxxxxxx-xminZ10 x ,x ,x ,x ,xx)x(xxx)x(xx)x(xxZaxm1111654364354343435832例例1.8 將線性規(guī)劃問題化為標準型將線性規(guī)劃問題化為標準型解：解： 例例1.9 將線性規(guī)劃問題化為標準型將線性規(guī)劃問題化為標準型解：解：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無約束 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ī)劃問題的解

29、線性規(guī)劃問題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj線性規(guī)劃問題線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個解，使目標函數(shù)中找出一個解，使目標函數(shù)(1)達到最大值。達到最大值。 可行解可行解：滿足約束條件、的解為可行解。所有可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。的集合為可行域。 最優(yōu)解最優(yōu)解：使目標函數(shù)達到最大值的可行解。：使目標函數(shù)達到最大值的可行解。 基：基：設(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é)模型化為標準形式：解：將數(shù)學(xué)模型化為標準形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量，列單純形表計算?？勺鳛槌跏蓟兞?，列單純形表計算。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變成標準型變成標準型 0, 12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ例例1.14 用單純形法求解用單純形法求解約束方程的系數(shù)矩陣約束方程的

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

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

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

35、1,2,7jZxxxMxMxxxxxxxxxxxxxxxjL其中：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。紹的單純形法求解該模型，計算結(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é)模型化為標準形式解：首先將數(shù)學(xué)模型化為標準形式1231234123513max3 2114232 10,1,2,5jZxxxxxxxxxxxxxxjL系數(shù)矩陣中不存在

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

38、純形法求解該模型，計算結(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 用計算機處理數(shù)據(jù)時，只能用很大的數(shù)代替用計算機處理數(shù)據(jù)時，只能用很大的數(shù)代替M,可能造可能造成計算機上的錯誤，故多采用成計算機上的錯誤，故多采用兩階段法兩階段法。 第一階段：第一階段： 在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型：在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型：1111 11111 1min00 nn mnnnnmmnnn mmxxxxa xa xxba xaxxbLLLMMOL1 0 n mxxL 對上述模型求解（單純形法），若對上述模型求解（單純形法），若=

40、0,說明問題存在基說明問題存在基可行解，可以進行第二個階段；否則，原問題無可行解，?？尚薪?，可以進行第二個階段；否則，原問題無可行解，停止運算。止運算。第一階段的線性規(guī)劃問題可寫為：第一階段的線性規(guī)劃問題可寫為：67123412356137min 2 =11 42 3 2 1 xxxxxxxxxxxxxx127 ,0 x xx，第一階段單純形法迭代的過程見下表第一階段單純形法迭代的過程見下表（注意：沒有化為極大化問題）（注意：沒有化為極大化問題）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 第二階段：第二階段： 在第一階段的最終表中，去掉人工變量，將目標函數(shù)的在第一階段的最終表中，去掉人工變量，將目標函數(shù)的系數(shù)換成原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始系數(shù)換成原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始表（用單純形法計算）。表（用單純形法計算）。例：例： 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），目標函數(shù)），目標函數(shù) Z = 2 通過大法或兩階段法求初始的基本可行解。但是通過大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變?nèi)绻诖蠓ǖ淖顑?yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔

43、助線性規(guī)劃的目標函數(shù)的極小值量，或者兩階段法的輔助線性規(guī)劃的目標函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。大于零，那么該線性規(guī)劃就不存在可行解。 無可行解無可行解 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 例例運算到檢驗數(shù)全負為止，仍含有人工變量，無可行解。運算到檢驗數(shù)全負為止，仍含有人工變量，無可行解。 無最優(yōu)解與無可行解時兩個不同的概念。無最優(yōu)解與無可行解時兩個不同的概念。 無可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指無可行解是指原規(guī)劃不存在可行解，從幾何的角度

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

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

47、變量等于零，這就是退退化化（會產(chǎn)生退化解）。（會產(chǎn)生退化解）。 為避免出現(xiàn)計算的循環(huán)，勃蘭特為避免出現(xiàn)計算的循環(huán)，勃蘭特(Bland)提出一個簡便有效的規(guī)提出一個簡便有效的規(guī)則（攝動法原理）：則（攝動法原理）： 當存在多個當存在多個 時，選下標最小的非基變量為換入變量；時，選下標最小的非基變量為換入變量；(2) 當當值出現(xiàn)兩個以上相同的最小值時，選下標最小的基變量為換值出現(xiàn)兩個以上相同的最小值時，選下標最小的基變量為換出變量。出變量。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 第一次迭代第一次迭代中使用了攝動中使用了攝動法原理，選擇法原理，選擇下標為下標為6的基的基變量變量x6離基。離基?？傻米顑?yōu)解可得最優(yōu)解maxZ=，X1,0,1,0,3T 無窮多最優(yōu)解無窮多最優(yōu)解 若線性規(guī)劃問題某個基本可行解所有的非基變量檢驗若線性規(guī)劃問題某個基本可行解所有的非基變量檢驗數(shù)都小于等于零，但其中存在一個檢驗數(shù)

49、等于零，那么該數(shù)都小于等于零，但其中存在一個檢驗數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。線性規(guī)劃問題有無窮多最優(yōu)解。例：最優(yōu)表：例：最優(yōu)表：非基變量檢驗非基變量檢驗數(shù)，數(shù)，所以有無窮多所以有無窮多最優(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)表中所有非基變量的檢驗數(shù)非零）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解。則線性規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判

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

51、立模模型型個個 數(shù)數(shù)取取 值值右右 端端 項項等式或等式或不等式不等式極大或極小極大或極小新加變新加變量系數(shù)量系數(shù)兩兩個個三個三個以上以上xj0 xj無無約束約束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對對任任一一)0( lklkiiaab 計計算算lkxx替替換換基基變變量量用用非非基基變變量量新新單單純純形形表表列列出出下下一一個個ax含有含有量中是否量中是否基變基變 0 j非非基基變變量量的的有有某某個個最最優(yōu)優(yōu)解解一一唯唯 無無可可行行解解最優(yōu)解最優(yōu)解無窮多無窮多是是否否環(huán)環(huán)循循否否否否否否是是是是是是循環(huán)循環(huán)無無界界解解一般而言，一個經(jīng)濟、管理問題凡是滿足以下條一般而言，一個經(jīng)濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。件時，才能建立線性規(guī)劃模型。 要求解問題的目標函數(shù)能用數(shù)值指標來反映，且要求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函

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

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

55、：1. 資源的合理利用資源的合理利用 某廠計劃在下一生產(chǎn)周期內(nèi)生產(chǎn)某廠計劃在下一生產(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)品可獲得的利潤如表所示，問如何安排生產(chǎn)計劃，才能充制以及每件產(chǎn)品可獲得的利潤如表所示，問如何安排生產(chǎn)計劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤最大？分利用現(xiàn)有的資源，使獲得的總利潤最大？單件單件 產(chǎn)產(chǎn) 消耗消耗 品品資源資源資源資源限制限制單件利潤單件利潤1 nBBL1 mAAM1 mbbM1 CnCL1111 nmm n

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

57、最低？加工加工 零零 時間時間 件件機床機床機時機時限制限制必須零件數(shù)必須零件數(shù)1 nBBL1 maaM1 nbbL1 111 nmm naaaaLMML加工加工 零零 成本成本 件件機床機床1 nBBL1 mAAM1 111 nmm nccccLMML1 mAAM 0 min ( 11ijjijiijijminjijijijjiijxbxaxaxcZxBAx一一組組變變量量）。模模型型：的的數(shù)數(shù)量量，求求在在一一生生產(chǎn)產(chǎn)周周期期加加工工零零件件為為機機床床設(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工序時，只能在工序時，只能在B1設(shè)備上加工；產(chǎn)品設(shè)備上加工；產(chǎn)品只能在只能在A2與與B2設(shè)備上加工。設(shè)備上加工。加工單位產(chǎn)品所需工序時間及其他各項數(shù)據(jù)如下表，加工單位產(chǎn)品所需工序時間及其他各項數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大。試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大。設(shè)備設(shè)備產(chǎn)品產(chǎn)品設(shè)備有效設(shè)備有效臺時臺時設(shè)備加工費設(shè)備加工費（單位小時）（單位小時）A1

59、5106000300A2791210 000321B1684000250B24117000783B374000200原料費（每件）原料費（每件）0.250.350.5售價（每件）售價（每件）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目標是利潤最大化，即利潤的計算公式如下：目標是利潤最大化，即利潤的計算公式如下： 5131)()(ii該該設(shè)設(shè)備備實實際際使使用用臺臺時時每每臺臺時時的的設(shè)設(shè)備備費費用用該該產(chǎn)產(chǎn)品品件件數(shù)數(shù)銷銷售售單單價價原原料料單單價價利利潤潤帶入數(shù)據(jù)整理得到：帶入數(shù)據(jù)整理得到：123