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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、法。|圖解法圖解法n對(duì)于只有兩個(gè)變量的簡(jiǎn)單的線性規(guī)劃問(wèn)題，也可采用圖解法求解。對(duì)于只有兩個(gè)變量的簡(jiǎn)單的線性規(guī)劃問(wèn)題，也可采用圖解法求解。n這種方法僅適用于只有兩個(gè)變量的線性規(guī)劃問(wèn)題。它的特點(diǎn)是直觀而這種方法僅適用于只有兩個(gè)變量的線性規(guī)劃問(wèn)題。它的特點(diǎn)是直觀而易于理解，但實(shí)用價(jià)值不大。易于理解，但實(shí)用價(jià)值不大。n通過(guò)通過(guò)圖解法圖解法求解可以理解線性規(guī)劃的一些基本概念。求解可以理解線性規(guī)劃的一些基本概念。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 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)畫(huà)出可行區(qū)域畫(huà)出可行區(qū)域算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 44 8.2.3 二維線性規(guī)劃的圖解法n(2)求目標(biāo)函數(shù)的梯度，并畫(huà)出其方向求目標(biāo)函數(shù)的梯度，并畫(huà)出其方向87654321O123456x1x2A(4,0)B(4,2)C(2,3)D(0,3)11222(,)2,33Tfxf xxfx算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué)

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

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

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

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

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

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

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

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

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

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

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

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

49、分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 62 8.2.4 用Excel解線性規(guī)劃|Step 1: n建立電子表格模型建立電子表格模型產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品設(shè)備所用時(shí)間設(shè)備所用時(shí)間設(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單位利潤(rùn)單位利潤(rùn)2 23 30 0生產(chǎn)件數(shù)生產(chǎn)件數(shù)0 00 0算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 63 8.2.4 用Excel解線性規(guī)劃|Step 2: 規(guī)劃求解規(guī)劃求解算法設(shè)計(jì)

50、與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 64 8.2.4 用Excel解線性規(guī)劃|Step3:得到求解結(jié)果得到求解結(jié)果產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品設(shè)備所用時(shí)間設(shè)備所用時(shí)間設(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單位利潤(rùn)單位利潤(rùn)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è)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 66 |單純形法單純形法：nG.B.Danzig于于1947年首先發(fā)明的。年首先發(fā)明的。n近近50年來(lái)，年來(lái)，單純形法單純形法一直是求解線性規(guī)劃的最有效的一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問(wèn)題的求解。方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問(wèn)題的求解。n本節(jié)討論單純形法的基本概念、原理及算法。本節(jié)討論單純形法的基本概念、原理及算法。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 67 8.3.1 線性規(guī)劃解的基本概念|定義：定義：n對(duì)線性規(guī)劃對(duì)

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è)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 68 8.3.1 線性規(guī)劃解的基本概念|可行解可行解n滿足所有約束條件的解滿足所有約束條件的解X = ( x1, x2, , xn )稱為可行解。稱為可行解。|基、基向量、基變量、基解、基可行解基、

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

54、量組。n與基向量對(duì)應(yīng)的變量與基向量對(duì)應(yīng)的變量 xj (j=1,2,m)稱為稱為基變量基變量,其它的變其它的變量為非基變量。量為非基變量。n若令非基變量為若令非基變量為0，則由約束方程組，則由約束方程組 AX=b 求得一個(gè)解求得一個(gè)解X=(x1, x2, ,xm, 0,0)稱為稱為基解基解（基解不一定可行），若（基解不一定可行），若基解又滿足非負(fù)條件，則稱為基解又滿足非負(fù)條件，則稱為基可行解基可行解。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 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è)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 71 8.3.1 線性規(guī)劃解的基本概念|解的性質(zhì)解的性質(zhì)n定理定理1：n線性規(guī)劃的可行集線性規(guī)劃的可行集R=X|AXb，X0是凸集。是凸集。n定理定理2：n線性規(guī)

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

57、解所對(duì)應(yīng)的目標(biāo)，然后比較這些基可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值，就可以確定這個(gè)線性規(guī)劃的函數(shù)值，就可以確定這個(gè)線性規(guī)劃的最優(yōu)解最優(yōu)解。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 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è)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 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è)計(jì)與分析算法設(shè)計(jì)與分析線性規(guī)劃線性規(guī)劃四川師范大學(xué)

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

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