1、線性規(guī)劃的典型應用內(nèi)容內(nèi)容生產(chǎn)組織與計劃問題生產(chǎn)組織與計劃問題運輸問題運輸問題指派問題指派問題下料問題下料問題生產(chǎn)組織與計劃問題生產(chǎn)組織與計劃問題例題例題某制藥廠生產(chǎn)甲、乙兩種藥品，生產(chǎn)這兩種藥品要消耗某種維生某制藥廠生產(chǎn)甲、乙兩種藥品，生產(chǎn)這兩種藥品要消耗某種維生素。生產(chǎn)每噸藥品所需要的維生素量，所占用的設備時間，以及素。生產(chǎn)每噸藥品所需要的維生素量，所占用的設備時間，以及該廠每周可提供的資源總量如下表所示：該廠每周可提供的資源總量如下表所示：每噸產(chǎn)品的消耗每噸產(chǎn)品的消耗 每周資源總量每周資源總量 甲甲乙乙維生素（公斤）維生素（公斤） 30302020160160設備（臺班）設備（臺班） 5

2、 51 11515已知該廠生產(chǎn)每噸甲、乙藥品的利已知該廠生產(chǎn)每噸甲、乙藥品的利潤分別為潤分別為5 5萬元和萬元和2 2萬元。但根據(jù)市萬元。但根據(jù)市場需求調(diào)查的結(jié)果，甲藥品每周的場需求調(diào)查的結(jié)果，甲藥品每周的產(chǎn)量不應超過產(chǎn)量不應超過4 4噸。問該廠應如何安噸。問該廠應如何安排兩種藥品的產(chǎn)量才能使每周獲得排兩種藥品的產(chǎn)量才能使每周獲得的利潤最大？的利潤最大？121212112maxZ=5x +2x30 x20 x1605xx15. .x4x0,x0st一般描述一般描述數(shù)學模型數(shù)學模型112211112211211222221122max. . .0(1,., )nnnnnnmmmnnmjZstjn

3、C x C xC xa xa xa xba xa xa xba xa xa xbx求解方法求解方法理論上的一般求解方法：理論上的一般求解方法： 二變量：圖解法二變量：圖解法 三變量以上：單純形法三變量以上：單純形法使用軟件：使用軟件：MatlabMatlab、lingolingo（lindolindo）運輸問題2321341運輸問題網(wǎng)絡圖運輸問題網(wǎng)絡圖a2=27a3=19b1=22b2=13b3=12b4=13a1=14供應量供應地運價需求量需求地675384275910614+27+19= 22+13+12+13供需平衡問題運輸問題的一般描述運輸問題的一般描述產(chǎn)需平橫產(chǎn)需平橫11111212

4、111211211211112222212min. .mnmnnmmmnmmmnnmnnijZs tC xC xC xxxxaxxxaxxxbxxxbxxxb0(1,2,.,;1,2,., )im jnx供供應應地地約約束束需需求求地地約約束束11mnijijab供不應求供不應求11111212111211211211112222212min. .mnmnnmmmnmmmnnmnnijZs tC xC xC xxxxaxxxaxxxbxxxbxxxb0(1,2,.,;1,2,., )im jnx供供應應地地約約束束需需求求地地約約束束11mnijijab供過于求供過于求111112121112

5、11211211112222212min. .mnmnnmmmnmmmnnmnnijZs tC xC xC xxxxaxxxaxxxbxxxbxxxb0(1,2,.,;1,2,., )im jnx供供應應地地約約束束需需求求地地約約束束11mnijijab轉(zhuǎn)運問題及圖示轉(zhuǎn)運問題及圖示所謂轉(zhuǎn)運問題所謂轉(zhuǎn)運問題(Transhipment Problem)實質(zhì)上是運輸問實質(zhì)上是運輸問題的一種，其區(qū)別就在于不是將工廠生產(chǎn)出的產(chǎn)品直接題的一種，其區(qū)別就在于不是將工廠生產(chǎn)出的產(chǎn)品直接送的顧客手中，而是要經(jīng)過某些中間環(huán)節(jié)，如倉庫、配送的顧客手中，而是要經(jīng)過某些中間環(huán)節(jié)，如倉庫、配送中心等送中心等.圖圖7-2

6、表示的（即有一個中間環(huán)節(jié)）的轉(zhuǎn)運問表示的（即有一個中間環(huán)節(jié)）的轉(zhuǎn)運問題題. 數(shù)學模型數(shù)學模型(1)(1)(2)(2)1111(1)1(1)(2)11min Z= ; , 1,2,(), 1,2, ,(s.t. mllnijijjkjkijjklijijmnijjkikc xcxxaimxxjl運出量應不大于生產(chǎn)量運入(2)1(1)(2) , 1,2,() 0,0, 1,2,1,2, ,1,2,.ljkkjijjkxbknxxim jl kn量應等于運出量運入量應等于需求量(1)ijx(2)jkx(1)ijc(2)ijc運輸問題的求解運輸問題的求解 模型也是線性規(guī)劃模型，可用單純形法； 模型的系

7、數(shù)矩陣是矩陣維數(shù)較大、涉及變量較多，系數(shù)矩陣是 稀疏矩陣，因此可以考慮更好的算法； 一般方法：表上作業(yè)法； 大體步驟： 先給一個初始方案（最小元素法、西北角法、沃格爾法） 判斷最優(yōu)性（閉回路法、對偶變量法） 如果不是，對該方案進行修改，再判斷，直到方案最優(yōu)。指派問題指派問題指派問題描述描述指派問題也稱分配問題，主要研究人指派問題也稱分配問題，主要研究人和工作（任務）間如何匹配，以使所和工作（任務）間如何匹配，以使所有工作完成的效率實現(xiàn)最優(yōu)化。形式有工作完成的效率實現(xiàn)最優(yōu)化。形式上，指派問題給定了一系列所要完成上，指派問題給定了一系列所要完成的工作以及一系列完成工作的人員，的工作以及一系列完成工

8、作的人員，所需要解決的問題就是要確定出指派所需要解決的問題就是要確定出指派哪個人去完成哪項工作。哪個人去完成哪項工作。在現(xiàn)實生活中，經(jīng)常會遇到指派人員做某在現(xiàn)實生活中，經(jīng)常會遇到指派人員做某項工作（任務）的情況項工作（任務）的情況指派問題的假設（平衡指派）指派問題的假設（平衡指派） 人的數(shù)量和工作的數(shù)量相等；人的數(shù)量和工作的數(shù)量相等； 每個人只能完成一項工作；每個人只能完成一項工作； 每項工作只能由一個人來完成；每項工作只能由一個人來完成； 每個人和每項工作的組合都會有一個每個人和每項工作的組合都會有一個 相關(guān)的成本（單位成本）；相關(guān)的成本（單位成本）；由于每人的由于每人的 知識、能力、經(jīng)驗等

9、不同，故各人完成知識、能力、經(jīng)驗等不同，故各人完成 不同任務所需的時間（或其它資源）不不同任務所需的時間（或其它資源）不 同；同； 目標是要確定如何指派能使總成本最小目標是要確定如何指派能使總成本最小111212122212nnnnnnxxxxxxXxxx 111212122212nnnnnnccccccCccc 設設xij為第為第i個人做第個人做第j項工作，取值項工作，取值0 0或或1 1 cij為第為第i個人完成第個人完成第j項工作所需要的成本項工作所需要的成本指派問題的數(shù)學模型 設設xij為第為第i個人做第個人做第j項工作，項工作， cij為第為第i個人完成第個人完成第j項工作所需要的成

10、本項工作所需要的成本 平衡指派問題的數(shù)學模型為平衡指派問題的數(shù)學模型為1111 ()Min z1 (1,2,)s.t. 1 (1,2,)01 ( ,1,2,) nnijijijnijjnijiijijc xxinxjnxi jn LLL(第 人只能做一項工作)(第 項工作只能一人做)非負 或需要說明的是需要說明的是指派問題實際上是一種特殊的運輸問題。指派問題實際上是一種特殊的運輸問題。其中出發(fā)地是人，目的地是工作。只不過其中出發(fā)地是人，目的地是工作。只不過，每一個出發(fā)地的供應量都為，每一個出發(fā)地的供應量都為1 1（因為每（因為每個人都要完成一項工作），每一個目的地個人都要完成一項工作），每一個

11、目的地的需求量都為的需求量都為1 1（因為每項工作都要完成（因為每項工作都要完成）。由于運輸問題有）。由于運輸問題有“整數(shù)解性質(zhì)整數(shù)解性質(zhì)”，因，因此，沒有必要加上所有決策變量都是此，沒有必要加上所有決策變量都是0-10-1變量的約束變量的約束. .求解按照一般的線性規(guī)劃編程求解即可。求解按照一般的線性規(guī)劃編程求解即可。指派問題是一種特殊的LP問題，是一種特殊的運輸問題。11111212111211211211112222212min. .mnmnnmmmnmmmnnmnnijZs tC xC xC xxxxaxxxaxxxbxxxbxxxb0(1,2,.,;1,2,., )im jnx區(qū)別：

12、變量取區(qū)別：變量取0 0或或1 1；整數(shù)規(guī)劃介紹整數(shù)規(guī)劃介紹在許多實際問題中，決策變量必須為整數(shù)。例如當決在許多實際問題中，決策變量必須為整數(shù)。例如當決策變量是分配的人數(shù)、購買的設備數(shù)、投入的車輛數(shù)、策變量是分配的人數(shù)、購買的設備數(shù)、投入的車輛數(shù)、是否投資等的時候，它們一般必須為非負整數(shù)才有意義。是否投資等的時候，它們一般必須為非負整數(shù)才有意義。在這種情況下，常需要應用整數(shù)規(guī)劃進行優(yōu)化。在這種情況下，常需要應用整數(shù)規(guī)劃進行優(yōu)化。整數(shù)規(guī)劃（整數(shù)規(guī)劃（Integer ProgrammingInteger Programming，簡稱，簡稱IPIP），是要），是要求全部或部分決策變量為整數(shù)的規(guī)劃。整

13、數(shù)規(guī)劃分為線求全部或部分決策變量為整數(shù)的規(guī)劃。整數(shù)規(guī)劃分為線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃。在此只介紹線性整數(shù)規(guī)性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃。在此只介紹線性整數(shù)規(guī)劃，簡稱為整數(shù)規(guī)劃。劃，簡稱為整數(shù)規(guī)劃。整數(shù)規(guī)劃分為兩大類：一般整數(shù)規(guī)劃與整數(shù)規(guī)劃分為兩大類：一般整數(shù)規(guī)劃與0-10-1整數(shù)規(guī)劃整數(shù)規(guī)劃（Binary Integer ProgrammingBinary Integer Programming，簡稱，簡稱BIPBIP）。）。整數(shù)規(guī)劃與一般規(guī)劃相比，其可行解不是連續(xù)的，而整數(shù)規(guī)劃與一般規(guī)劃相比，其可行解不是連續(xù)的，而是離散的是離散的。整數(shù)規(guī)劃舉例整數(shù)規(guī)劃舉例某航空公司是一家使用小型飛機經(jīng)營短途

14、航線的小型區(qū)域性企某航空公司是一家使用小型飛機經(jīng)營短途航線的小型區(qū)域性企業(yè)。該公司已經(jīng)經(jīng)營得不錯，其管理層決定拓展其經(jīng)營領(lǐng)域。業(yè)。該公司已經(jīng)經(jīng)營得不錯，其管理層決定拓展其經(jīng)營領(lǐng)域。 管理層面臨的基本問題是：是采購更多的小型飛機來開辟一管理層面臨的基本問題是：是采購更多的小型飛機來開辟一些新的短途航線，還是開始通過為一些跨地區(qū)航線購買大型的些新的短途航線，還是開始通過為一些跨地區(qū)航線購買大型的飛機來進軍全國市場（或雙管齊下）？哪一種戰(zhàn)略最有可能獲飛機來進軍全國市場（或雙管齊下）？哪一種戰(zhàn)略最有可能獲得最高收益？得最高收益？ 下表提供了購買每一種飛機的年凈利潤期望（包括資本回收下表提供了購買每一種

15、飛機的年凈利潤期望（包括資本回收成本）；給出了每架飛機的采購成本，以及可用于飛機采購的成本）；給出了每架飛機的采購成本，以及可用于飛機采購的總可用資金總可用資金1 1億元；并表明了管理層希望小型飛機的采購不超過億元；并表明了管理層希望小型飛機的采購不超過兩架。兩架。需要的決策是：小型飛機和大型飛機各需要采購多少才能夠獲需要的決策是：小型飛機和大型飛機各需要采購多少才能夠獲得最大的年總凈利潤？得最大的年總凈利潤？小型飛機小型飛機大型飛機大型飛機可獲得的總資金可獲得的總資金每架飛機年利潤每架飛機年利潤100100萬元萬元500500萬元萬元1 1億元億元每架飛機采購成本每架飛機采購成本500500

16、萬元萬元50005000萬元萬元最多購買數(shù)量最多購買數(shù)量2 2沒有限制沒有限制數(shù)學模型數(shù)學模型設小型飛機與大型飛機的購買數(shù)量分別為設小型飛機與大型飛機的購買數(shù)量分別為x1、x2( (架架) )1212112Max z100500500500010000s.t.2,0 xxxxxx x且為整數(shù)由于離散問題比連續(xù)問題更難以處理，整數(shù)規(guī)劃要比一般線性規(guī)由于離散問題比連續(xù)問題更難以處理，整數(shù)規(guī)劃要比一般線性規(guī)劃難解得多，而且至今尚無一種像求解線性規(guī)劃那樣較成熟的算劃難解得多，而且至今尚無一種像求解線性規(guī)劃那樣較成熟的算法。目前常用的基本算法有分支定界法、割平面法等。法。目前常用的基本算法有分支定界法、

17、割平面法等。對于指派問題（對于指派問題（0-10-1規(guī)劃），目前認為最簡潔的方法規(guī)劃），目前認為最簡潔的方法匈牙利法。匈牙利法。各種變形的指派問題建模各種變形的指派問題建模有些人并不能進行某項工作有些人并不能進行某項工作任務比人多任務比人多( (人少事多人少事多););人比任務多（人多事少）；人比任務多（人多事少）；某人可以同時被指派給多個任務（一人可做幾件事）某人可以同時被指派給多個任務（一人可做幾件事）某事可以由多人共同完成（一事可由多人完成）某事可以由多人共同完成（一事可由多人完成） 目標是與指派有關(guān)的總利潤最大而不是使總成本最小目標是與指派有關(guān)的總利潤最大而不是使總成本最小各種變形的指

18、派問題建模各種變形的指派問題建模（1 1）有些人并不能進行某項工作）有些人并不能進行某項工作 如果第如果第i i個人不能干第個人不能干第j j項工作，則項工作，則x xijij0 0；（2 2）人少事多人少事多(m(m(人數(shù)人數(shù))n)n)n（工作數(shù)）（工作數(shù)）) )p 填上一些虛擬的事，填上一些虛擬的事，n+1n+1，i+2i+2，m;m;p p 模型模型01,ijcinm ，1111 ()Min z1 (1,2,)s.t. 1 (1,2,)0 ( ,1,2,) ijijijijjijimjmmimijc xxixjxi jmmmLLL(第 人只能做一項工作)(第 項工作只能一人做)非負 一人

19、可以做多事一人可以做多事5家建筑公司承建家建筑公司承建5項工程的指派問題，為了保證工程項工程的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司質(zhì)量，經(jīng)研究決定，舍棄建筑公司 A4和和A5，而讓技，而讓技術(shù)力量較強的建筑公司術(shù)力量較強的建筑公司A1，A2和和A3來承建。根據(jù)實際來承建。根據(jù)實際情況，可以允許每家建筑公司承建一項或兩項工程。情況，可以允許每家建筑公司承建一項或兩項工程。求使總費用最少的指派方案。求使總費用最少的指派方案。4871512791714106912871A2A3A1B2B3B4B5B4871512487151279171410791714106912876912871B2B3B4B5B1A1A2A2A3A3A487151204871512079171410079171410069128706912870C1A1A2A2A3A3A1B2B3B4B5B6B1112161