第8章_線性規(guī)劃和網(wǎng)絡(luò)流

1、第8章 線性規(guī)劃與網(wǎng)絡(luò)流8.1 8.1 運籌學概論運籌學概論8.2 8.2 線性規(guī)劃基礎(chǔ)線性規(guī)劃基礎(chǔ)8.3 8.3 線性規(guī)劃求解的單純形算法線性規(guī)劃求解的單純形算法8.4 8.4 網(wǎng)絡(luò)流網(wǎng)絡(luò)流算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 2 8.1運籌學概論|運籌學的思想在古代就已經(jīng)產(chǎn)生了運籌學的思想在古代就已經(jīng)產(chǎn)生了n敵我雙方交戰(zhàn)，要克敵制勝就要在了解雙方情況的基礎(chǔ)上，敵我雙方交戰(zhàn)，要克敵制勝就要在了解雙方情況的基礎(chǔ)上，做出最優(yōu)的對付敵人的方法。做出最優(yōu)的對付敵人的方法。運籌帷幄之中，決勝千里之外。8.1.1 運籌學的歷史運籌學的歷史 8.1.2 運籌學的應(yīng)

2、用運籌學的應(yīng)用8.1.3 運籌學的研究分支運籌學的研究分支8.1.4 運籌學與線性規(guī)劃運籌學與線性規(guī)劃算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 3 8.1.1 運籌學的歷史|運籌學的誕生運籌學的誕生n20世紀整個世界參與世紀整個世界參與規(guī)模最大規(guī)模最大的事件是什么？的事件是什么？n第二次世界大戰(zhàn)！第二次世界大戰(zhàn)！n整個世界的資源都投入到了第二次世界大戰(zhàn)中。整個世界的資源都投入到了第二次世界大戰(zhàn)中。n如何才能更好地利用資源，分配有限的資源，這是一如何才能更好地利用資源，分配有限的資源，這是一個值得研究的問題。個值得研究的問題。n當時在英國軍隊中率先成立了研究

3、小組來研究這些問題，當時在英國軍隊中率先成立了研究小組來研究這些問題，這就是著名的這就是著名的OR（ Operational Research Group ）小組，）小組，很快美軍中也相繼成立了很快美軍中也相繼成立了OR小組。小組。n戰(zhàn)爭戰(zhàn)爭 運籌學誕生的溫床運籌學誕生的溫床。 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 4 8.1.1 運籌學的歷史|二戰(zhàn)中成功的運籌學案例：二戰(zhàn)中成功的運籌學案例：n英國防空部門如何布置防空雷達，建立最有效的防空警報系統(tǒng)。英國防空部門如何布置防空雷達，建立最有效的防空警報系統(tǒng)。n英，美空軍如何提高對地面目標轟炸的命中率。英，

4、美空軍如何提高對地面目標轟炸的命中率。n如何安排反潛飛機的巡邏飛行線路，深水炸彈的合理爆炸深度，如何安排反潛飛機的巡邏飛行線路，深水炸彈的合理爆炸深度，摧毀德軍潛艇數(shù)增加摧毀德軍潛艇數(shù)增加400%。n商船如何編隊，遭潛艇攻擊時如何減少損失，使船只受敵機攻商船如何編隊，遭潛艇攻擊時如何減少損失，使船只受敵機攻擊時，中彈數(shù)由擊時，中彈數(shù)由47%降到降到29%。n這些研究大大提高了盟軍的作戰(zhàn)能力，為反法西斯戰(zhàn)爭的最后這些研究大大提高了盟軍的作戰(zhàn)能力，為反法西斯戰(zhàn)爭的最后勝利作出了巨大的貢獻！勝利作出了巨大的貢獻！算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 5 8.

5、1.2 運籌學的應(yīng)用|戰(zhàn)爭結(jié)束了！戰(zhàn)爭結(jié)束了！n 整個世界投入到了戰(zhàn)后的重建國家的經(jīng)濟之中。整個世界投入到了戰(zhàn)后的重建國家的經(jīng)濟之中。n運籌學的應(yīng)用迅速轉(zhuǎn)向了民用，相繼在工業(yè)，農(nóng)業(yè)，經(jīng)濟，運籌學的應(yīng)用迅速轉(zhuǎn)向了民用，相繼在工業(yè)，農(nóng)業(yè)，經(jīng)濟，社會問題等各個領(lǐng)域中展開了應(yīng)用。社會問題等各個領(lǐng)域中展開了應(yīng)用。n如：如：算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 6 8.1.2 運籌學的應(yīng)用|運籌學的應(yīng)用運籌學的應(yīng)用n1.市場銷售市場銷售n2.生產(chǎn)計劃生產(chǎn)計劃n3.運輸問題運輸問題n4.人事管理人事管理n5.設(shè)備維修，更新和可靠性等。設(shè)備維修，更新和可靠性等。n6.

6、計算機和信息系統(tǒng)計算機和信息系統(tǒng)n7.城市管理城市管理n8.對策研究對策研究n算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 7 8.1.3 運籌學的研究分支|研究分支研究分支n規(guī)劃論規(guī)劃論n排隊論排隊論n對策論（博弈論）對策論（博弈論）n圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析n統(tǒng)籌方法統(tǒng)籌方法n存儲論存儲論n決策論、多目標決策等。決策論、多目標決策等。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 8 8.1.4 線性規(guī)劃的發(fā)展|規(guī)劃論規(guī)劃論n規(guī)劃論是目前運籌學中發(fā)展較快、應(yīng)用較廣的一個分支。主要包括：規(guī)劃論是目前運籌學中發(fā)展較快、應(yīng)用較廣的

7、一個分支。主要包括：線性規(guī)劃線性規(guī)劃,非線性規(guī)劃非線性規(guī)劃,整數(shù)規(guī)劃整數(shù)規(guī)劃,目標規(guī)劃目標規(guī)劃,動態(tài)規(guī)劃。動態(tài)規(guī)劃。n規(guī)劃論所研究的問題主要有兩類：規(guī)劃論所研究的問題主要有兩類：n給定了一定數(shù)量的人力、物力，如何合理調(diào)配這些資源，去完成最多的給定了一定數(shù)量的人力、物力，如何合理調(diào)配這些資源，去完成最多的任務(wù)；任務(wù)；n確定了一項任務(wù)，如何精打細算，使用最少的人力、物力，去完成這項確定了一項任務(wù)，如何精打細算，使用最少的人力、物力，去完成這項任務(wù)任務(wù)n對于上述問題的一般數(shù)學模型的建立、探討和求解的理論，稱為對于上述問題的一般數(shù)學模型的建立、探討和求解的理論，稱為數(shù)學數(shù)學規(guī)劃規(guī)劃。n其中重要而常用的

8、一種是其中重要而常用的一種是線性規(guī)劃線性規(guī)劃。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 9 8.1.4 線性規(guī)劃的發(fā)展|發(fā)展歷史發(fā)展歷史n法國數(shù)學家法國數(shù)學家 J.- B.- J.傅里葉和傅里葉和 C.瓦萊普森分別于瓦萊普森分別于1832和和1911年獨立年獨立地提出線性規(guī)劃的想法，但未引起注意。地提出線性規(guī)劃的想法，但未引起注意。 n1939年蘇聯(lián)數(shù)學家年蘇聯(lián)數(shù)學家.康托羅維奇在康托羅維奇在生產(chǎn)組織與計劃中的數(shù)學方法生產(chǎn)組織與計劃中的數(shù)學方法一書中提出線性規(guī)劃問題，也未引起重視。一書中提出線性規(guī)劃問題，也未引起重視。 n1947年旦茨基（年旦茨基（G.

9、B. Dantzig）提出了一般線性規(guī)劃問題求解的方）提出了一般線性規(guī)劃問題求解的方法法單純形法單純形法（simplex method），為這門學科奠定了基礎(chǔ)。自此），為這門學科奠定了基礎(chǔ)。自此線性規(guī)劃已被廣泛應(yīng)用于解決經(jīng)濟管理和工業(yè)生產(chǎn)中遇到的實際問題。線性規(guī)劃已被廣泛應(yīng)用于解決經(jīng)濟管理和工業(yè)生產(chǎn)中遇到的實際問題。 n1947年美國數(shù)學家年美國數(shù)學家J.von諾伊曼提出對偶理論諾伊曼提出對偶理論,開創(chuàng)了線性規(guī)劃的許多開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴大了它的應(yīng)用范圍和解題能力。新的研究領(lǐng)域，擴大了它的應(yīng)用范圍和解題能力。 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學

10、學院 劉芳 10 8.1.4 線性規(guī)劃的發(fā)展n1951年美國經(jīng)濟學家年美國經(jīng)濟學家T.C.庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟領(lǐng)域，為此與康托羅維奇一起獲領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟學獎年諾貝爾經(jīng)濟學獎。 n50年代后對線性規(guī)劃進行大量的理論研究，并涌現(xiàn)出一大年代后對線性規(guī)劃進行大量的理論研究，并涌現(xiàn)出一大批新的算法。如：批新的算法。如：n1954年年C.萊姆基提出對偶單純形法萊姆基提出對偶單純形法n1954年年S.加斯和加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題劃問題n1956年年A.塔克提出互

11、補松弛定理塔克提出互補松弛定理n1960年年G.B.丹齊克和丹齊克和P.沃爾夫提出分解算法等。沃爾夫提出分解算法等。 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 11 8.1.4 線性規(guī)劃的發(fā)展n線性規(guī)劃的研究成果還直接推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)線性規(guī)劃的研究成果還直接推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究。劃、隨機規(guī)劃和非線性規(guī)劃的算法研究。n由于數(shù)字電子計算機的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如由于數(shù)字電子計算機的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規(guī)劃問

12、等，可以很方便地求解幾千個變量的線性規(guī)劃問題。題。n1979年蘇聯(lián)數(shù)學家年蘇聯(lián)數(shù)學家L. G. Khachian提出解線性規(guī)劃問題的橢球算法，提出解線性規(guī)劃問題的橢球算法，并證明它是多項式時間算法。并證明它是多項式時間算法。n1984年美國貝爾電話實驗室的印度數(shù)學家年美國貝爾電話實驗室的印度數(shù)學家N.卡馬卡提出解線性規(guī)卡馬卡提出解線性規(guī)劃問題的新的多項式時間算法。劃問題的新的多項式時間算法。n用這種方法求解線性規(guī)劃問題在變量個數(shù)為用這種方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形時只要單純形法所用時間的法所用時間的1/50。現(xiàn)已形成線性規(guī)劃多項式算法理論?，F(xiàn)已形成線性規(guī)劃多項式算法理論

13、。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 12 8.1.4 線性規(guī)劃的發(fā)展n調(diào)查表明：調(diào)查表明：n在世界在世界500家最大的企業(yè)中，有家最大的企業(yè)中，有85%的企業(yè)都曾使用過的企業(yè)都曾使用過線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。n線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計的資金。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計的資金。8.2 線性規(guī)劃基礎(chǔ)8.2.1 什么是線性規(guī)劃什么是線性規(guī)劃8.2.2 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型8.2.3 二維線性規(guī)劃的圖解法二維線性規(guī)劃的圖解法8.2.4 用用excel求解線性規(guī)劃求

14、解線性規(guī)劃算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 14 8.2.1 什么是線性規(guī)劃n線性規(guī)劃問題是什么樣的一類問題呢？線性規(guī)劃問題是什么樣的一類問題呢？n請看案例請看案例-算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 15 8.2.1 什么是線性規(guī)劃|例例1：生產(chǎn)安排問題：生產(chǎn)安排問題n問題描述：問題描述：產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品設(shè)備可用時間設(shè)備可用時間設(shè)備設(shè)備A2212設(shè)備設(shè)備B12 8設(shè)備設(shè)備C4016設(shè)備設(shè)備D0412單位利潤單位利潤23問：如何安排生產(chǎn)計劃，才能獲利最多？問：如何安排生產(chǎn)計劃，才能獲利最多？算法設(shè)計與分析

15、算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 16 8.2.1 什么是線性規(guī)劃|分析：分析：n假設(shè)假設(shè)x1,x2分別表示在計劃期內(nèi)生產(chǎn)分別表示在計劃期內(nèi)生產(chǎn)、型產(chǎn)品的件數(shù)。型產(chǎn)品的件數(shù)。產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品設(shè)備所用時間設(shè)備所用時間設(shè)備可用時間設(shè)備可用時間設(shè)備設(shè)備A222x12x212設(shè)備設(shè)備B12 x12x28設(shè)備設(shè)備C40 4x1 16設(shè)備設(shè)備D04 4x212單位利潤單位利潤23目標：目標：maxZ 2x13x2生產(chǎn)件數(shù)生產(chǎn)件數(shù)x1x2產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品設(shè)備所用時間設(shè)備所用時間設(shè)備可用時間設(shè)備可用時間設(shè)備設(shè)備A2212設(shè)備設(shè)備B128設(shè)備設(shè)備C4016設(shè)備設(shè)備D0412單位利

16、潤單位利潤23生產(chǎn)件數(shù)生產(chǎn)件數(shù)x1x2算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 17 8.2.1 什么是線性規(guī)劃n于是得到該問題的數(shù)學模型：于是得到該問題的數(shù)學模型：1212121212 max232212 2 8 s.t. 4 16 4120,0Zxxxxxxxxxx目標：算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 18 8.2.1 什么是線性規(guī)劃|例例2：下料問題：下料問題n某車間有長為某車間有長為180cm的鋼管（數(shù)量足夠多），今要將其截的鋼管（數(shù)量足夠多），今要將其截為不同長度的管料，長度分別為為不同長度的管料，

17、長度分別為70cm,52cm,35cm。生產(chǎn)。生產(chǎn)任務(wù)規(guī)定：任務(wù)規(guī)定：70cm需要需要100根，根，52cm和和35cm的管料分別不的管料分別不少于少于150根，根，120根。根。n問：應(yīng)該如何截取，才能完成任務(wù)，同時使余料最少？問：應(yīng)該如何截取，才能完成任務(wù)，同時使余料最少？算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 19 8.2.1 什么是線性規(guī)劃|解：解：n所有可能的截法有所有可能的截法有8種：種：截法截法長度長度余料余料705235120 15212 0631112341035503 0246022670132380055算法設(shè)計與分析算法設(shè)計與分析

18、線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 20 8.2.1 什么是線性規(guī)劃n設(shè)設(shè)xj:第第j種截法的使用次數(shù)。（種截法的使用次數(shù)。（j=1,2,8）n則上述問題的數(shù)學模型為：則上述問題的數(shù)學模型為：12345678123423567134678min 562352462352 100 2 32 150. 3 2351200(1 8)jzxxxxxxxxxxxxxxxxxstxxxxxxxjL算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 21 8.2.1 什么是線性規(guī)劃|例例3：人力資源分配的問題：人力資源分配的問題n某晝夜服務(wù)的公交線路每天各時間段內(nèi)

19、所需司機和乘務(wù)人某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下：員數(shù)如下：班次班次i時間時間至少所需人數(shù)至少所需人數(shù)xi16:0010:0060 x1210:0014:0070 x2314:0018:0060 x3418:0022:0050 x4522:002:0030 x562:006:0030 x6算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 22 8.2.1 什么是線性規(guī)劃n設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時。工作八小時。n問問:n該公交線路怎樣安排司機和乘務(wù)人員，既

20、能滿足工作該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)員？需要，又配備最少司機和乘務(wù)員？算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 23 8.2.1 什么是線性規(guī)劃|解：解：n設(shè)設(shè)xi表示第表示第i班次時開始上班的司機和乘務(wù)人員數(shù)，這樣可班次時開始上班的司機和乘務(wù)人員數(shù)，這樣可以知道以知道:n在第在第i班工作的人數(shù)第班工作的人數(shù)第i1班次時開始上班的人員數(shù)班次時開始上班的人員數(shù)第第i班次時開始上班的人員數(shù)班次時開始上班的人員數(shù);n又要求這六個班次時開始上班的所有人員最少，即：又要求這六個班次時開始上班的所有人員最少，即：要求要求x

21、1 +x2 +x3+x4 +x5 +x6最小。最小。n這樣建立如下的數(shù)學模型：這樣建立如下的數(shù)學模型：算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 24 8.2.1 什么是線性規(guī)劃n目標函數(shù)：目標函數(shù)：nmin z = x1 +x2 +x3+x4 +x5 +x6n約束條件：約束條件：61,0303050607060655443322161jxxxxxxxxxxxxxj算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 25 8.2.1 什么是線性規(guī)劃|從上面的例子可以看出：從上面的例子可以看出：n雖然各個例子的具體內(nèi)容各不相同，但歸

22、結(jié)出的數(shù)學模型雖然各個例子的具體內(nèi)容各不相同，但歸結(jié)出的數(shù)學模型卻屬于同一類問題，即在一組線性等式或不等式的約束之卻屬于同一類問題，即在一組線性等式或不等式的約束之下，求一個線性函數(shù)的最大值或最小值的問題。我們將這下，求一個線性函數(shù)的最大值或最小值的問題。我們將這類問題稱為類問題稱為線性規(guī)劃問題（線性規(guī)劃問題（ Linear Programming ）算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 26 8.2.1 什么是線性規(guī)劃|線性規(guī)劃（線性規(guī)劃（LP）的要素：）的要素：n一組有待決策的變量一組有待決策的變量xj （決策變量決策變量）n一個線性的目標函數(shù)和優(yōu)

23、化準則一個線性的目標函數(shù)和優(yōu)化準則nz稱為稱為目標函數(shù)目標函數(shù)n max或或min成為成為優(yōu)化準則優(yōu)化準則n 一組一組線性的約束條件線性的約束條件（s.t ：subject約束條件）約束條件）|線性規(guī)劃的應(yīng)用線性規(guī)劃的應(yīng)用n線性規(guī)劃是在有限資源的條件下，合理分配和利用資源，線性規(guī)劃是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟效益的優(yōu)化方法。以期取得最佳的經(jīng)濟效益的優(yōu)化方法。 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 27 8.2.2 線性規(guī)劃的數(shù)學模型|線性規(guī)劃（線性規(guī)劃（LP）的定義）的定義：n若目標函數(shù)若目標函數(shù)z為決策變量為決策變量x

24、j的線性函數(shù)，約束條件亦為決策的線性函數(shù)，約束條件亦為決策變量變量xj的線性不等式（或等式），則該數(shù)學表達式（模型）的線性不等式（或等式），則該數(shù)學表達式（模型）稱為稱為線性規(guī)劃模型線性規(guī)劃模型（ Linear Programming Model ）。）。n注：注：n若目標與約束中至少有一為非線性時，則該模型稱為若目標與約束中至少有一為非線性時，則該模型稱為非線性模型（非線性模型（NLP）。）。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 28 8.2.2 線性規(guī)劃的數(shù)學模型|線性規(guī)劃模型的特征：線性規(guī)劃模型的特征： n每個問題都追求每個問題都追求一個目標一個

25、目標，這個目標可以表示為一組變量，這個目標可以表示為一組變量（決策變量）的（決策變量）的線性函數(shù)線性函數(shù)（線性函數(shù)就是一次多項式形式（線性函數(shù)就是一次多項式形式的函數(shù)）的函數(shù)） 。n問題中的若干個問題中的若干個約束條件約束條件，可用線性等式或線性不等式表，可用線性等式或線性不等式表示。示。 n求解過程就是在若干個可行方案中選擇一組或多組方案使求解過程就是在若干個可行方案中選擇一組或多組方案使目標函數(shù)值達到最大或最小。目標函數(shù)值達到最大或最小。 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 29 8.2.2 線性規(guī)劃的數(shù)學模型|建立線性規(guī)劃問題數(shù)學模型的一般步驟

26、：建立線性規(guī)劃問題數(shù)學模型的一般步驟： 1.確定決策變量確定決策變量n確定合適的決策變量是能否成功的建立數(shù)學模型的關(guān)確定合適的決策變量是能否成功的建立數(shù)學模型的關(guān)鍵。鍵。2.確定目標函數(shù)確定目標函數(shù) n將題目要追求目標列成函數(shù)形式（一般用將題目要追求目標列成函數(shù)形式（一般用Z作函數(shù)中作函數(shù)中的因變量，決策變量為自變量）。的因變量，決策變量為自變量）。 3.確定約束條件方程確定約束條件方程 n將題目中與決策變量有關(guān)的限制條件列成代數(shù)方程。將題目中與決策變量有關(guān)的限制條件列成代數(shù)方程。 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 30 一、線性規(guī)劃的一般形式n1

27、.展開式展開式1 12211 11221121 1222221 12212 max(min) ( , )( , ). .( , ),0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xbsta xaxaxbx xx 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 31 一、線性規(guī)劃的一般形式n2.矩陣表示形式矩陣表示形式n令：令：11122212 , ,TnnnnxbcxbcXbCc ccxbc111212122212nnmmmnaaaaaaAaaa算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳

28、32 一、線性規(guī)劃的一般形式n則：線性規(guī)劃可以表示如下：則：線性規(guī)劃可以表示如下：max(min) ( , ).0TZC XAXbstX 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 33 二、線性規(guī)劃的標準型|引：引：n線性規(guī)劃的目標函數(shù)可以極大化，也可以極小化；線性規(guī)劃的目標函數(shù)可以極大化，也可以極小化；n約束條件可以約束條件可以“”型，也可以型，也可以“”型或型或“”型。型。n這種多樣性給討論問題帶來不便。這種多樣性給討論問題帶來不便。n為便于討論，常用以下為便于討論，常用以下標準型標準型進行討論。進行討論。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四

29、川師范大學 計算機科學學院 劉芳 34 二、線性規(guī)劃的標準型n表示如下：表示如下：112211112211211222221122min. . 0(1,2, )0(1,2,)nnnnnnmmmnnmjiZc xc xc xa xa xa xba xa xaxbs taxaxaxbxjnbim算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 35 二、線性規(guī)劃的標準型n當然也可以用向量當然也可以用向量/矩陣表示式矩陣表示式min . .0TZC XAXbstX算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 36 三、一般形式轉(zhuǎn)化為標準

30、型|問題：問題：n怎樣將線性規(guī)劃的一般形式轉(zhuǎn)化為標準形式？怎樣將線性規(guī)劃的一般形式轉(zhuǎn)化為標準形式？|一般步驟：一般步驟：n目標函數(shù)極大化目標函數(shù)極大化“極小化極小化”n約束條件為不等式約束條件為不等式 或或 “=”n取值無非負約束的變量取值無非負約束的變量“非負變量非負變量”n約束條件的右端項約束條件的右端項 bi0 “bi0” 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 37 三、一般形式轉(zhuǎn)化為標準型n1.若目標函數(shù)極大化時，將目標函數(shù)乘以若目標函數(shù)極大化時，將目標函數(shù)乘以1，轉(zhuǎn)換為極，轉(zhuǎn)換為極小化問題。即：小化問題。即：maxTZCXmaxminTZC

31、XZZ ：則令算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 38 三、一般形式轉(zhuǎn)化為標準型n2.約束條件為不等式的情形約束條件為不等式的情形n若某個約束條件若某個約束條件“”，則可在不等式左端加上一個非，則可在不等式左端加上一個非負變量使其變?yōu)榈仁剑@樣的變量稱為負變量使其變?yōu)榈仁?，這樣的變量稱為松弛變量松弛變量。n若某個約束條件若某個約束條件“”，則可在不等式左端減去一個非，則可在不等式左端減去一個非負變量使其變?yōu)榈仁剑@樣的變量稱為負變量使其變?yōu)榈仁?，這樣的變量稱為剩余變量剩余變量。 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院

32、 劉芳 39 三、一般形式轉(zhuǎn)化為標準型n3.變量無非負限制的情況：變量無非負限制的情況： n若若 xi可正可負，則可用可正可負，則可用 xj xk 代替代替 xi ,即：即： xi xj xk ( xj 0, xk 0 )n當當xi0時，令時，令xi xi (xi 0 )。n4. 若有某個常數(shù)項若有某個常數(shù)項bi0時，只需該約束條件兩端乘以時，只需該約束條件兩端乘以“1”即可。即可。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 40 三、一般形式轉(zhuǎn)化為標準型|例如：例如：n將下列線性規(guī)劃問題轉(zhuǎn)化為標準型。將下列線性規(guī)劃問題轉(zhuǎn)化為標準型。12123123123m

33、ax26315. .240,0,Zxxxxxs txxxxxx的符號不受限制。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 41 三、一般形式轉(zhuǎn)化為標準型|解：解：n（1）將目標函數(shù)變?yōu)椋⒛繕撕瘮?shù)變?yōu)閙in Z=Z=2x1x2.n（2）用）用x4x5代替代替x3(x40,x50)；n（3）在第一約束中加松弛變量）在第一約束中加松弛變量x6,在第二約束中減去剩余在第二約束中減去剩余變量變量x7；n于是，得到線性規(guī)劃的標準型如下：于是，得到線性規(guī)劃的標準型如下：121245612457min263 15. . 2 40 (1,2,7)jZxxxxxxxstxxx

34、xxxj 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 42 如何求解一般的線性規(guī)劃問題|單純形法單純形法n求解線性規(guī)劃問題的基本方法是單純形法，現(xiàn)在已有求解線性規(guī)劃問題的基本方法是單純形法，現(xiàn)在已有單純形法單純形法的標準的標準軟件，可在電子計算機上求解約束條件和決策變量數(shù)達軟件，可在電子計算機上求解約束條件和決策變量數(shù)達 10000個以上個以上的線性規(guī)劃問題。的線性規(guī)劃問題。n為了提高解題速度，又有改進單純形法、對偶單純形法、原始對偶方為了提高解題速度，又有改進單純形法、對偶單純形法、原始對偶方法、分解算法和各種多項式時間算法。法、分解算法和各種多項式時間算

35、法。|圖解法圖解法n對于只有兩個變量的簡單的線性規(guī)劃問題，也可采用圖解法求解。對于只有兩個變量的簡單的線性規(guī)劃問題，也可采用圖解法求解。n這種方法僅適用于只有兩個變量的線性規(guī)劃問題。它的特點是直觀而這種方法僅適用于只有兩個變量的線性規(guī)劃問題。它的特點是直觀而易于理解，但實用價值不大。易于理解，但實用價值不大。n通過通過圖解法圖解法求解可以理解線性規(guī)劃的一些基本概念。求解可以理解線性規(guī)劃的一些基本概念。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 43 8.2.3 二維線性規(guī)劃的圖解法|例例1:87654321O123456x1x2x1=4x2=3x1+2x2

36、=82x1+2x2 =12A(4,0)B(4,2)C(2,3)D(0,3)121212121212max(,)232212 2 8s.t. 4 16 4120,0f x xxxxxxxxxxx解解： (1)畫出可行區(qū)域畫出可行區(qū)域算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 44 8.2.3 二維線性規(guī)劃的圖解法n(2)求目標函數(shù)的梯度，并畫出其方向求目標函數(shù)的梯度，并畫出其方向87654321O123456x1x2A(4,0)B(4,2)C(2,3)D(0,3)11222(,)2,33Tfxf xxfx算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學

37、 計算機科學學院 劉芳 45 8.2.3 二維線性規(guī)劃的圖解法n(3)任作一條目標函數(shù)的等值線任作一條目標函數(shù)的等值線ln(4)求最優(yōu)解求最優(yōu)解nB(4,2)為最優(yōu)點，即為最優(yōu)點，即x1=4,x2=2為最優(yōu)解。為最優(yōu)解。n最優(yōu)值最優(yōu)值max f(x1,x2)=14|注：注：n梯度方向梯度方向是目標函數(shù)增長最快的方向。是目標函數(shù)增長最快的方向。n當目標函數(shù)為求最小值時，等值線當目標函數(shù)為求最小值時，等值線l沿著梯度負方向平行沿著梯度負方向平行移動，此時移動，此時l與可行區(qū)域的最后交點的坐標為所求的最優(yōu)與可行區(qū)域的最后交點的坐標為所求的最優(yōu)解。解。8.2.3 二維線性規(guī)劃的圖解法|例例2：nmax

38、 zx1+3x2ns.t.x1+ x26x1+2x28x1 0, x20可行域可行域目標函數(shù)等值線目標函數(shù)等值線最優(yōu)解最優(yōu)解64-860 x1x2算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 47 8.2.3 二維線性規(guī)劃的圖解法|思考：思考：n線性規(guī)劃是否可能存在無窮多個解？線性規(guī)劃是否可能存在無窮多個解？|例如：例如：n將例將例1中的目標函數(shù)改為：中的目標函數(shù)改為： max z2x1+4x2n將例將例2中的目標函數(shù)改為：中的目標函數(shù)改為：max z2x1+2x2算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 48 8.2.3

39、 二維線性規(guī)劃的圖解法|幾個概念：幾個概念：n可行區(qū)域（可行集）：可行區(qū)域（可行集）：n滿足所有約束條件的點的集合稱為可行域滿足所有約束條件的點的集合稱為可行域 可行域中每可行域中每個點，代表該域的一個可行方案，稱為可行解。個點，代表該域的一個可行方案，稱為可行解。n最優(yōu)解：最優(yōu)解：n使目標函數(shù)達到最優(yōu)的可行解，稱為最優(yōu)解。使目標函數(shù)達到最優(yōu)的可行解，稱為最優(yōu)解。n最優(yōu)值：最優(yōu)值：n目標函數(shù)在最優(yōu)解處的函數(shù)值。目標函數(shù)在最優(yōu)解處的函數(shù)值。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 49 12212max2. .0,0ZxxxstxxOx1x228.2.3 二

40、維線性規(guī)劃的圖解法|例例3：n已知線性規(guī)劃：已知線性規(guī)劃：該問題的可行域沿該問題的可行域沿x1軸無限延伸，故有軸無限延伸，故有可行解可行解，但，但無最優(yōu)解無最優(yōu)解。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 50 8.2.3 二維線性規(guī)劃的圖解法|例例4：n已知線性規(guī)劃：已知線性規(guī)劃：12121212max3222. . 280,0Zxxxxstxxxxn該問題可行區(qū)域為空集，故該問題可行區(qū)域為空集，故無解無解。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 51 8.2.3 二維線性規(guī)劃的圖解法|課后練習課后練習1n用圖解法

41、求解下面的線性規(guī)劃問題：用圖解法求解下面的線性規(guī)劃問題： 1212121212max6010011471. .71280,0Zxxxxxxs txxxx算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 52 8.2.3 二維線性規(guī)劃的圖解法|圖解法的啟示圖解法的啟示n1.線性規(guī)劃問題解的可能情況線性規(guī)劃問題解的可能情況:n唯一最優(yōu)解唯一最優(yōu)解n無窮多最優(yōu)解無窮多最優(yōu)解n無解無解可行區(qū)域可行區(qū)域有界（總可以找到最優(yōu)解）有界（總可以找到最優(yōu)解）唯一唯一不唯一不唯一無界無界 有最優(yōu)解有最優(yōu)解無最優(yōu)解無最優(yōu)解空集（無最優(yōu)解）空集（無最優(yōu)解）算法設(shè)計與分析算法設(shè)計與分析線性

42、規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 53 8.2.3 二維線性規(guī)劃的圖解法|圖解法的幾點啟示圖解法的幾點啟示n2.若線性規(guī)劃問題的可行域非空，則可行域是一個若線性規(guī)劃問題的可行域非空，則可行域是一個凸集凸集；凸集例凸集例頂點個數(shù)頂點個數(shù)有限有限有限有限無限無限有限有限無限無限非凸集例非凸集例算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 54 8.2.3 二維線性規(guī)劃的圖解法|圖解法的幾點啟示圖解法的幾點啟示n3.若線性規(guī)劃問題的最優(yōu)解存在，則一定可以在可行域的若線性規(guī)劃問題的最優(yōu)解存在，則一定可以在可行域的凸集的凸集的某個頂點某個頂點或或邊界邊界上

43、達到。上達到。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 55 |對于一般的線性規(guī)劃問題對于一般的線性規(guī)劃問題n約束條件確定了一個約束條件確定了一個n維空間的維空間的“凸的超多面體凸的超多面體”；n根據(jù)線性規(guī)劃理論，可以證明：根據(jù)線性規(guī)劃理論，可以證明：n使目標函數(shù)取得極小使目標函數(shù)取得極小(大大)值的點一定是這個凸的超多面值的點一定是這個凸的超多面體的極點。體的極點。 1 12211 11221121 1222221 12212 max(min) ( , )( , ). .( , ),0nnnnnnmmmnnmnZc xc xc xa xa xa xba

44、xa xa xbsta xaxaxbx xx 算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 56 8.2.4 用Excel解線性規(guī)劃|Excel規(guī)劃求解工具規(guī)劃求解工具n啟動啟動Excel軟件，進入軟件，進入Excel用戶界面；用戶界面；n使用使用“工具工具”菜單下菜單下“加載宏加載宏”菜單項的菜單項的“規(guī)劃求解規(guī)劃求解”子子項項, 則可完成則可完成“規(guī)劃求解規(guī)劃求解”項的加載。項的加載。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 57 8.2.4 用Excel解線性規(guī)劃|求解的具體方法：求解的具體方法：n1.建立電子表格模

45、型建立電子表格模型n1)確定一些單元格來代表決策變量：確定一些單元格來代表決策變量： 一般地：將決策變量一般地：將決策變量x1,x2,xn放到一些連續(xù)的單元放到一些連續(xù)的單元格中，稱為格中，稱為可變單元格可變單元格。 求解前，可變單元格放的是決策變量的初值，一般求解前，可變單元格放的是決策變量的初值，一般使用使用0作為初始值。作為初始值。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 58 8.2.4 用Excel解線性規(guī)劃n2)輸入目標函數(shù)系數(shù)；輸入目標函數(shù)系數(shù)；n3)確定目標單元格，并在其中輸入目標函數(shù)表達式；確定目標單元格，并在其中輸入目標函數(shù)表達式；n4

46、)輸入約束條件左右兩端的數(shù)據(jù)，并將目標值單元格中輸入約束條件左右兩端的數(shù)據(jù)，并將目標值單元格中的公式復(fù)制到目標值下面相應(yīng)的單元格中。的公式復(fù)制到目標值下面相應(yīng)的單元格中。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 59 8.2.4 用Excel解線性規(guī)劃n2.進入規(guī)劃的求解階段進入規(guī)劃的求解階段n1)取菜單欄中取菜單欄中“工具工具”菜單下的菜單下的“規(guī)劃求解規(guī)劃求解”菜單項，菜單項，彈出彈出 “規(guī)劃求解參數(shù)規(guī)劃求解參數(shù)”對話框。對話框。n2)在在“設(shè)置目標單元格設(shè)置目標單元格”文本框中輸入目標單元格地址。文本框中輸入目標單元格地址。n3)在在“等于等于”項目

47、上選定項目上選定“最小值最小值/最小最小”選項。選項。n4)在在“可變單元格可變單元格”文本框中輸入可變單元格區(qū)域地址。文本框中輸入可變單元格區(qū)域地址。n5)打開打開“添加約束添加約束”對話框，依次輸入所有約束條件。對話框，依次輸入所有約束條件。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 60 8.2.4 用Excel解線性規(guī)劃n6) 設(shè)置設(shè)置“規(guī)劃求解選項規(guī)劃求解選項”。n7)單擊單擊“求解求解”按扭，規(guī)劃求解軟件開始運行，運算結(jié)按扭，規(guī)劃求解軟件開始運行，運算結(jié)束后，彈出束后，彈出 “規(guī)劃求解結(jié)果規(guī)劃求解結(jié)果”對話框，可以得到：對話框，可以得到： 保存求

48、解結(jié)果，并給出運算結(jié)果報告；保存求解結(jié)果，并給出運算結(jié)果報告； 可變單元格和目標值單元格分別顯示最優(yōu)解和最優(yōu)可變單元格和目標值單元格分別顯示最優(yōu)解和最優(yōu)值。值。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 61 8.2.4 用Excel解線性規(guī)劃|例：用例：用Excel求解生產(chǎn)安排問題求解生產(chǎn)安排問題產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品設(shè)備所用時間設(shè)備所用時間設(shè)備可用時間設(shè)備可用時間設(shè)備設(shè)備A222x12x212設(shè)備設(shè)備B12 x12x28設(shè)備設(shè)備C40 4x1 16設(shè)備設(shè)備D04 4x212單位利潤單位利潤23目標：目標：maxZ 2x13x2生產(chǎn)件數(shù)生產(chǎn)件數(shù)x1x2算法設(shè)計與

49、分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 62 8.2.4 用Excel解線性規(guī)劃|Step 1: n建立電子表格模型建立電子表格模型產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品設(shè)備所用時間設(shè)備所用時間設(shè)備可用時間設(shè)備可用時間設(shè)備設(shè)備A2 22 20 0 1212設(shè)備設(shè)備B1 12 20 0 8 8設(shè)備設(shè)備C4 40 00 0 1616設(shè)備設(shè)備D0 04 40 0 1212單位利潤單位利潤2 23 30 0生產(chǎn)件數(shù)生產(chǎn)件數(shù)0 00 0算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 63 8.2.4 用Excel解線性規(guī)劃|Step 2: 規(guī)劃求解規(guī)劃求解算法設(shè)計

50、與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 64 8.2.4 用Excel解線性規(guī)劃|Step3:得到求解結(jié)果得到求解結(jié)果產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品設(shè)備所用時間設(shè)備所用時間設(shè)備可用時間設(shè)備可用時間設(shè)備設(shè)備A2 22 21212 1212設(shè)備設(shè)備B1 12 28 8 8 8設(shè)備設(shè)備C4 40 01616 1616設(shè)備設(shè)備D0 04 48 8 1212單位利潤單位利潤2 23 31414生產(chǎn)件數(shù)生產(chǎn)件數(shù)4 42 28.3 線性規(guī)劃求解的單純形法8.3.1 8.3.1 線性規(guī)劃解的基本概念線性規(guī)劃解的基本概念8.3.2 8.3.2 單純形法單純形法8.3.3 8.3.3 兩階段單純

51、形法兩階段單純形法算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 66 |單純形法單純形法：nG.B.Danzig于于1947年首先發(fā)明的。年首先發(fā)明的。n近近50年來，年來，單純形法單純形法一直是求解線性規(guī)劃的最有效的一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。n本節(jié)討論單純形法的基本概念、原理及算法。本節(jié)討論單純形法的基本概念、原理及算法。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 67 8.3.1 線性規(guī)劃解的基本概念|定義：定義：n對線性規(guī)劃對

52、線性規(guī)劃1 12211 11221121 1222221 122min. . 0(1,2, )0(1,2,)nnnnnnmmmnnmjiZc xc xc xa xa xa xba xa xa xbsta xaxaxbxjnbimmin . .0TZC XAXbstX111212122212nnmmmnaaaaaaAaaa算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 68 8.3.1 線性規(guī)劃解的基本概念|可行解可行解n滿足所有約束條件的解滿足所有約束條件的解X = ( x1, x2, , xn )稱為可行解。稱為可行解。|基、基向量、基變量、基解、基可行解基、

53、基向量、基變量、基解、基可行解n若若rank (A) = mn，則，則A（或?qū)Γɑ驅(qū)作初等行變換）中必有作初等行變換）中必有m個線性無關(guān)個線性無關(guān)的列向量，構(gòu)成滿秩矩陣的列向量，構(gòu)成滿秩矩陣B ( |B| 0 )，則則B為該線性規(guī)劃的一個為該線性規(guī)劃的一個基基。不失一般性，設(shè)：不失一般性，設(shè)：11121212221212 ( ,) mmmmmmmaaaaaaBp ppaaa算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 69 8.3.1 線性規(guī)劃解的基本概念n Pj ( j =1,2,m )為為基向量基向量，它們是一個線性無關(guān)的向量組。，它們是一個線性無關(guān)的向

54、量組。n與基向量對應(yīng)的變量與基向量對應(yīng)的變量 xj (j=1,2,m)稱為稱為基變量基變量,其它的變其它的變量為非基變量。量為非基變量。n若令非基變量為若令非基變量為0，則由約束方程組，則由約束方程組 AX=b 求得一個解求得一個解X=(x1, x2, ,xm, 0,0)稱為稱為基解基解（基解不一定可行），若（基解不一定可行），若基解又滿足非負條件，則稱為基解又滿足非負條件，則稱為基可行解基可行解。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 70 123123123123min()23 2. .246,0f Xxxxxxxstxxxx x x解：解：1 1

55、11 2 4A1121 1( ,)1 2BP P是基1( 2,4,0)TX 基本解 非基本可行解例例1：2231 1( ,)2 4BP P是基2(0,1,1)TX基本解 基本可行解2()5fX 3131 1( ,)1 4BP P是基324( ,0, )33TX基本解 基本可行解310()3fX 最優(yōu)解為最優(yōu)解為X2=(0,1,1)T，最優(yōu)值為，最優(yōu)值為5。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 71 8.3.1 線性規(guī)劃解的基本概念|解的性質(zhì)解的性質(zhì)n定理定理1：n線性規(guī)劃的可行集線性規(guī)劃的可行集R=X|AXb，X0是凸集。是凸集。n定理定理2：n線性規(guī)

56、劃的可行集線性規(guī)劃的可行集R的點的點X是是R的頂點的頂點的的充要條件充要條件是是X是是此線性規(guī)劃的基可行解此線性規(guī)劃的基可行解。n定理定理3：n若線性規(guī)劃有最優(yōu)解，則必可以在其可行集的頂點處若線性規(guī)劃有最優(yōu)解，則必可以在其可行集的頂點處獲得。獲得。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 72 8.3.1 線性規(guī)劃解的基本概念|于是：于是：n求解一個線性規(guī)劃的最優(yōu)解的一種解法求解一個線性規(guī)劃的最優(yōu)解的一種解法窮舉法窮舉法n即根據(jù)上述定理，找出所有的基解（即根據(jù)上述定理，找出所有的基解（C(n,m)），從中），從中找出找出基可行解基可行解，然后比較這些基可行

57、解所對應(yīng)的目標，然后比較這些基可行解所對應(yīng)的目標函數(shù)值，就可以確定這個線性規(guī)劃的函數(shù)值，就可以確定這個線性規(guī)劃的最優(yōu)解最優(yōu)解。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 73 8.3.1 線性規(guī)劃解的基本概念|例例2：12341234124234min( ,)2322 44. . 250(1,2,3,4)jf x x x xxxxxxxxstxxxxj解：解：12040112A11212( ,)01BP P是基1(14,5,0,0)TX基本解 基本可行解1()24f X2131 0( ,)0 1BP P是基2(4,0,5,0)TX基本解 基本可行解2()19

58、f X31414( ,)02BP P是基35(14,0,0,)2TX基本解 非基本可行解算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 74 8.3.1 線性規(guī)劃解的基本概念4232 0( ,)11BP P是基4(0,2,7,0)TX基本解 非基本可行解52424(,)12BP P不是基63404( ,)12BP P是基6(0,0,7,1)TX基本解 基本可行解6()19fX12341234124234min(,)2322 44. . 250(1,2,3,4)jf x xxxxxxxxxxs txxxxj算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學

59、計算機科學學院 劉芳 75 8.3.1 線性規(guī)劃解的基本概念n注意：注意：n隨著隨著n，m的增大，線性規(guī)劃基可行解的數(shù)目也隨之增的增大，線性規(guī)劃基可行解的數(shù)目也隨之增大，要求解最優(yōu)解也是很困難的；大，要求解最優(yōu)解也是很困難的；n故：故： 窮舉方法在理論上是可行，但是實際操作（工程）窮舉方法在理論上是可行，但是實際操作（工程）中很少使用。中很少使用。 因而需要尋找新的計算方法因而需要尋找新的計算方法 單純形法單純形法算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 76 8.3.2 單純形法|理論基礎(chǔ)理論基礎(chǔ)n線性規(guī)劃的最優(yōu)解，一定可以在可行集的頂點處獲得。線性規(guī)劃

60、的最優(yōu)解，一定可以在可行集的頂點處獲得。|單純形法的基本思想單純形法的基本思想n從線性規(guī)劃可行集的某一個頂點出發(fā)，沿著使目標函數(shù)值從線性規(guī)劃可行集的某一個頂點出發(fā)，沿著使目標函數(shù)值下降的方向?qū)ふ蚁乱粋€頂點，下降的方向?qū)ふ蚁乱粋€頂點，n而頂點的個數(shù)是有限的，所以，只要這個線性規(guī)劃有最優(yōu)而頂點的個數(shù)是有限的，所以，只要這個線性規(guī)劃有最優(yōu)解，那么通過有限次迭代后，必可求出最優(yōu)解。解，那么通過有限次迭代后，必可求出最優(yōu)解。算法設(shè)計與分析算法設(shè)計與分析線性規(guī)劃線性規(guī)劃四川師范大學 計算機科學學院 劉芳 77 8.3.2 單純形法|設(shè)線性規(guī)劃設(shè)線性規(guī)劃112m in . .0(),0nTiiiijmnmZ