數(shù)學建模-數(shù)學規(guī)劃

1、陳旺虎http:/ 數(shù)學規(guī)劃 線性規(guī)劃 線性規(guī)劃的軟件解法 整數(shù)規(guī)劃 目標規(guī)劃1.數(shù)學規(guī)劃 數(shù)學規(guī)劃論起始數(shù)學規(guī)劃論起始2020世紀世紀3030年代末，年代末，5050年代與年代與6060年代發(fā)年代發(fā)展成為一個完整的分支并受到數(shù)學界和社會各界的重展成為一個完整的分支并受到數(shù)學界和社會各界的重視。視。 七八十年代是數(shù)學規(guī)劃飛速發(fā)展時期，無論是從理論七八十年代是數(shù)學規(guī)劃飛速發(fā)展時期，無論是從理論上還是算法方面都得到了進一步完善。上還是算法方面都得到了進一步完善。 時至今日數(shù)學規(guī)劃仍然是運籌學領(lǐng)域中熱點研究問題。時至今日數(shù)學規(guī)劃仍然是運籌學領(lǐng)域中熱點研究問題。 從國內(nèi)外的數(shù)學建模競賽的試題中看，有近

2、從國內(nèi)外的數(shù)學建模競賽的試題中看，有近1/41/4的問題的問題可用數(shù)學規(guī)劃進行求解。可用數(shù)學規(guī)劃進行求解。 數(shù)學規(guī)劃模型的一般表達式：數(shù)學規(guī)劃模型的一般表達式： 為目標函數(shù)，為目標函數(shù)， 為約束函數(shù)，為約束函數(shù)， 為可控變量，為可控變量， 為已知參數(shù)，為已知參數(shù)， 為隨機參數(shù)。為隨機參數(shù)。 min max, ,f x . .,0s t gxfgx數(shù)學規(guī)劃模型2. 線性規(guī)劃 線性規(guī)劃模型是運籌學的重要分支，是線性規(guī)劃模型是運籌學的重要分支，是2020世紀三四十年世紀三四十年代初興起的一門學科。代初興起的一門學科。 19471947年美國數(shù)學家丹齊格年美國數(shù)學家丹齊格G.B.DantzigG.B.

3、Dantzig及其同事提出的求及其同事提出的求解線性規(guī)劃的單純形法及有關(guān)理論具有劃時代的意義。解線性規(guī)劃的單純形法及有關(guān)理論具有劃時代的意義。他們的工作為線性規(guī)劃這一學科的建立奠定了理論基礎(chǔ)。他們的工作為線性規(guī)劃這一學科的建立奠定了理論基礎(chǔ)。 隨著隨著19791979年前蘇聯(lián)數(shù)學家哈奇揚的橢球算法和年前蘇聯(lián)數(shù)學家哈奇揚的橢球算法和19841984年美年美籍印度數(shù)學家卡瑪卡爾籍印度數(shù)學家卡瑪卡爾H.KarmarkarH.Karmarkar算法的相繼問世，線算法的相繼問世，線性規(guī)劃的理論更加完備成熟，實用領(lǐng)域更加寬廣。性規(guī)劃的理論更加完備成熟，實用領(lǐng)域更加寬廣。 線性規(guī)劃研究的實際問題多種多樣，如

4、生產(chǎn)計劃問題、線性規(guī)劃研究的實際問題多種多樣，如生產(chǎn)計劃問題、物資運輸問題、合理下料問題、庫存問題、勞動力問題、物資運輸問題、合理下料問題、庫存問題、勞動力問題、最優(yōu)設(shè)計問題等。最優(yōu)設(shè)計問題等。 就模型而言，線形規(guī)劃模型類似于高等數(shù)學中的條件極就模型而言，線形規(guī)劃模型類似于高等數(shù)學中的條件極值問題，只是其目標函數(shù)和約束條件都限定為線性函數(shù)。值問題，只是其目標函數(shù)和約束條件都限定為線性函數(shù)。 線性規(guī)劃模型的求解方法目前仍以單純形法為主要方法。線性規(guī)劃模型的求解方法目前仍以單純形法為主要方法。 本節(jié)將介紹的主要內(nèi)容本節(jié)將介紹的主要內(nèi)容線性規(guī)劃模型的建立及標準形式；線性規(guī)劃模型的建立及標準形式；線性

5、規(guī)劃模型的解和單純形法；線性規(guī)劃模型的解和單純形法；整數(shù)線性規(guī)劃模型及建模案例等。整數(shù)線性規(guī)劃模型及建模案例等。例2.1 生產(chǎn)組織與計劃問題 某工廠計劃生產(chǎn)甲、乙兩種產(chǎn)品，主要材料有鋼材某工廠計劃生產(chǎn)甲、乙兩種產(chǎn)品，主要材料有鋼材3600kg3600kg、專用設(shè)備能力專用設(shè)備能力30003000臺時。材料與設(shè)備能力的消耗定額以及單臺時。材料與設(shè)備能力的消耗定額以及單位產(chǎn)品所獲利潤如下表所示位產(chǎn)品所獲利潤如下表所示問如何安排生產(chǎn)，才能使該廠所獲利潤最大？問如何安排生產(chǎn)，才能使該廠所獲利潤最大？產(chǎn)產(chǎn)品品單位產(chǎn)品消單位產(chǎn)品消 耗定額耗定額材料與設(shè)備材料與設(shè)備甲（件）甲（件）乙（件乙（件）現(xiàn)有材料與現(xiàn)

6、有材料與設(shè)備能力設(shè)備能力鋼材鋼材（kg）銅材銅材（kg）設(shè)備能力（臺時）設(shè)備能力（臺時）單位產(chǎn)品的利潤（元）單位產(chǎn)品的利潤（元）9 4 36004 5 20003 10 300070 120設(shè)甲、乙兩種產(chǎn)品計劃生產(chǎn)量分別為設(shè)甲、乙兩種產(chǎn)品計劃生產(chǎn)量分別為x1x1和和x2x2件，總的利潤為件，總的利潤為Z Z元元那么那么, ,我們的任務(wù)就是：求變量的值為多少時，才能使總利潤我們的任務(wù)就是：求變量的值為多少時，才能使總利潤 最大最大? ?由已知條件，由已知條件， x1x1和和x2x2要受下列限制：要受下列限制： (1)(1)生產(chǎn)甲、乙兩種產(chǎn)品所用鋼材的總數(shù)不能超過現(xiàn)有鋼材數(shù)，即生產(chǎn)甲、乙兩種產(chǎn)品所

7、用鋼材的總數(shù)不能超過現(xiàn)有鋼材數(shù)，即 (2)(2)生產(chǎn)甲、乙兩種產(chǎn)品所用銅材的總數(shù)不能超過現(xiàn)有銅材數(shù)，即生產(chǎn)甲、乙兩種產(chǎn)品所用銅材的總數(shù)不能超過現(xiàn)有銅材數(shù)，即 (3)(3)生產(chǎn)兩種產(chǎn)品所用的設(shè)備能力的總數(shù)不能超過現(xiàn)有設(shè)備能力的臺時數(shù)，生產(chǎn)兩種產(chǎn)品所用的設(shè)備能力的總數(shù)不能超過現(xiàn)有設(shè)備能力的臺時數(shù)，即即 1270120zxx12943600 xx12452000 xx123103000 xx建模過程(4)甲、乙兩種產(chǎn)品的計劃生產(chǎn)量不能為負數(shù)，即甲、乙兩種產(chǎn)品的計劃生產(chǎn)量不能為負數(shù)，即 問題轉(zhuǎn)化為求解如下的條件極值（問題轉(zhuǎn)化為求解如下的條件極值（數(shù)學模型數(shù)學模型）：）： 120,0 xx12max70

8、120zxx12121212943600452000. .31030000,0 xxxxstxxxx建模過程設(shè)有設(shè)有m m種物質(zhì)，第種物質(zhì)，第i i種物資的庫存量為種物資的庫存量為b bi i每種物資都可以生產(chǎn)每種物資都可以生產(chǎn)n n種產(chǎn)品種產(chǎn)品, ,第第i i種物資生產(chǎn)第種物資生產(chǎn)第j j種產(chǎn)品種產(chǎn)品時，每生產(chǎn)單位產(chǎn)品所需物資量為時，每生產(chǎn)單位產(chǎn)品所需物資量為a aijij每種物資生產(chǎn)第每種物資生產(chǎn)第j j種產(chǎn)品時，每單位產(chǎn)品可獲利潤種產(chǎn)品時，每單位產(chǎn)品可獲利潤C Cj j（如下表）（如下表）問如何組織生產(chǎn)才能使利潤最大？問如何組織生產(chǎn)才能使利潤最大？ 例2.2 最大利潤問題 用用x xj

9、j表示生產(chǎn)第表示生產(chǎn)第j j種產(chǎn)品計劃數(shù)，則問題歸結(jié)為如下數(shù)學問題：種產(chǎn)品計劃數(shù)，則問題歸結(jié)為如下數(shù)學問題：約束條件的意義是：每種原料生產(chǎn)約束條件的意義是：每種原料生產(chǎn)n n種產(chǎn)品所需要的資源總量不能超種產(chǎn)品所需要的資源總量不能超過該種資源的庫存量；每種產(chǎn)品的生產(chǎn)計劃數(shù)不能為負。過該種資源的庫存量；每種產(chǎn)品的生產(chǎn)計劃數(shù)不能為負。njjjnxcxxxf1, 21).,(maxmibxaxxgtsinjjijni,.,1,),.,(. .11njxj,.,1, 0建模過程 設(shè)某類物資有設(shè)某類物資有m m個產(chǎn)地，有個產(chǎn)地，有n n個銷售地個銷售地. . 第第i i個產(chǎn)地的產(chǎn)量為個產(chǎn)地的產(chǎn)量為a ai

10、 i, ,第第j j個銷售地的需要量為個銷售地的需要量為b bj j. . 從產(chǎn)地從產(chǎn)地i i到銷售地到銷售地j j運輸單位物資的運價（單價）為運輸單位物資的運價（單價）為C Cijij. . 今考慮在產(chǎn)銷平衡的條件下，即今考慮在產(chǎn)銷平衡的條件下，即 應(yīng)如何組織運輸，才能使得即滿足各地的需要，又使應(yīng)如何組織運輸，才能使得即滿足各地的需要，又使總運總運費最小。費最小。11mnijijab例2.3 運輸問題用用x xijij表示產(chǎn)地表示產(chǎn)地i i供給銷地供給銷地j j的物資數(shù)量，則問題變成在產(chǎn)銷平衡條件的物資數(shù)量，則問題變成在產(chǎn)銷平衡條件下，求解以下數(shù)學問題：下，求解以下數(shù)學問題： 考察上述幾個問

11、題的數(shù)學模型，他們的目標函數(shù)及約束函數(shù)都是自變考察上述幾個問題的數(shù)學模型，他們的目標函數(shù)及約束函數(shù)都是自變量的線性函數(shù)，故稱這類數(shù)學問題為量的線性函數(shù)，故稱這類數(shù)學問題為線性規(guī)劃問題。線性規(guī)劃問題。1. .1,2,mijjis txbjn11,2,nijijxaim0ijx 11minmnijijijzc x建模過程 類似的問題很多類似的問題很多諸如下料問題、配料問題、分配問題、工廠選址問題等等。諸如下料問題、配料問題、分配問題、工廠選址問題等等。解決方法都歸結(jié)為上述的線性規(guī)劃問題，只是約束條件有的是等解決方法都歸結(jié)為上述的線性規(guī)劃問題，只是約束條件有的是等式，有的是不等式。式，有的是不等式。

12、 通過以上例子可以看出通過以上例子可以看出盡管所提問題的內(nèi)容不同，但從構(gòu)成數(shù)學問題的結(jié)構(gòu)來看，卻屬盡管所提問題的內(nèi)容不同，但從構(gòu)成數(shù)學問題的結(jié)構(gòu)來看，卻屬于同一類優(yōu)化問題，其結(jié)構(gòu)具有如下特征：于同一類優(yōu)化問題，其結(jié)構(gòu)具有如下特征： （1 1）目標函數(shù)是決策變量的線性函數(shù)。）目標函數(shù)是決策變量的線性函數(shù)。 （2 2）約束條件都是決策變量的線性等式或不等式。）約束條件都是決策變量的線性等式或不等式?？偨Y(jié) 稱如下的稱如下的條件極值問題條件極值問題 為為標準的線性規(guī)劃問題標準的線性規(guī)劃問題。njxmibxaxxgtsxcxxfLPjnjijijnnjjjn,.,1, 0,.,1,),.,(. .),.

13、,(min1111線性規(guī)劃的解法概述 若引進記號若引進記號 則（則（LPLP）可簡單地表示為）可簡單地表示為 進一步，若令進一步，若令 則（則（LPLP）可表示為：）可表示為： 11,TTnncccbbb minTfxc x. .s t Axb0 x ,0nDxRA xbxxCxfTDx)(minnmijTnaAxxx)(,),.,(對于非標準形式的線性規(guī)劃，可通過下列辦法化成標準形式。對于非標準形式的線性規(guī)劃，可通過下列辦法化成標準形式。若求若求 , ,可化為求可化為求 . .若約束條件中含有不等式若約束條件中含有不等式 或或 則可引進則可引進新變量新變量 （稱為（稱為松弛變量松弛變量），化

14、為等式約束：），化為等式約束： 或或 今后總假定今后總假定 ，否則在等式兩邊乘以，否則在等式兩邊乘以-1-1即可。即可。若變量若變量 無非負限制，則引入兩個非負變量無非負限制，則引入兩個非負變量 與與 令令 ，便可化為標準形式。，便可化為標準形式。 max fxAxbAxb1nx1nAxxb1nAxxb0b jx)(min(xfjxjx jjjxxx （1 1）單純形法單純形法19471947年由美國數(shù)學家年由美國數(shù)學家DantzigDantzig提出；提出； 雖然在特殊情況下可能出現(xiàn)循環(huán)，但這種方法仍是目前雖然在特殊情況下可能出現(xiàn)循環(huán)，但這種方法仍是目前求解線性規(guī)劃問題最常用的方法；求解線性

15、規(guī)劃問題最常用的方法； 事實上在大量的實際問題計算中看出，循環(huán)情況從未出事實上在大量的實際問題計算中看出，循環(huán)情況從未出現(xiàn)過（僅在特意構(gòu)造下才能出現(xiàn)）；現(xiàn)過（僅在特意構(gòu)造下才能出現(xiàn)）； 是一種是一種迭代方法迭代方法。 （2 2）橢球法橢球法19771977年由前蘇聯(lián)數(shù)學家年由前蘇聯(lián)數(shù)學家khachiyankhachiyan提出的提出的多項式時間算法；多項式時間算法；它在理論上保證了多項式時間算法的存在性；它在理論上保證了多項式時間算法的存在性； 但大量數(shù)值研究發(fā)現(xiàn)，對于大多數(shù)實際問題，橢球法在但大量數(shù)值研究發(fā)現(xiàn)，對于大多數(shù)實際問題，橢球法在計算上不如單純形方法。計算上不如單純形方法。解法概述（

16、3 3）KarmarkarKarmarkar內(nèi)點法內(nèi)點法19831983年由美籍印度數(shù)學家年由美籍印度數(shù)學家KarmarkarKarmarkar提出的；提出的； 也是一種也是一種多項式時間算法多項式時間算法，在大多數(shù)情況下比單純形算法的計算，在大多數(shù)情況下比單純形算法的計算速度要快。速度要快。（4 4）圖上作業(yè)與表上作業(yè)法）圖上作業(yè)與表上作業(yè)法前一種是前一種是5050年代由我國數(shù)學工作者提出的，后者是年代由我國數(shù)學工作者提出的，后者是19501950年年DantzingDantzing提出的；提出的；這二種方法主要是為解決這二種方法主要是為解決運輸問題運輸問題（特殊的線性規(guī)劃）而設(shè)計的。（特殊

17、的線性規(guī)劃）而設(shè)計的。 據(jù)統(tǒng)計在用線性規(guī)劃解決的實際問題中，據(jù)統(tǒng)計在用線性規(guī)劃解決的實際問題中，70%70%以上屬于運輸問題類以上屬于運輸問題類型。型。3. 線性規(guī)劃問題的軟件解法l 求解線性規(guī)劃的常用方法是求解線性規(guī)劃的常用方法是19471947年年G.B.DantzigG.B.Dantzig提出的單純提出的單純形法。形法。l 這種方法是以尋找最優(yōu)解的迭代過程為主線?；舅悸肥沁@種方法是以尋找最優(yōu)解的迭代過程為主線?；舅悸肥?給出一個基可行解（一個頂點）后，判斷其是否為最優(yōu)解；給出一個基可行解（一個頂點）后，判斷其是否為最優(yōu)解； 若它不是最優(yōu)解，可用迭代的方法轉(zhuǎn)換到另一個基可行解（頂點），

18、若它不是最優(yōu)解，可用迭代的方法轉(zhuǎn)換到另一個基可行解（頂點），最終找到使目標函數(shù)值更優(yōu)的基可行解。最終找到使目標函數(shù)值更優(yōu)的基可行解。 經(jīng)過有限次迭代后，這一迭代過程以找到最優(yōu)解或判定問題無最優(yōu)經(jīng)過有限次迭代后，這一迭代過程以找到最優(yōu)解或判定問題無最優(yōu)解為目標。解為目標。 求解線性規(guī)劃的軟件很多，下面介紹求解線性規(guī)劃的軟件很多，下面介紹MathematicaMathematica和和MATLABMATLAB軟件。軟件。Mathematica和MATLAB求解 MathematicaMathematica命令命令 可用于求解各種形式的線性規(guī)劃問題的命令，輸入格式：可用于求解各種形式的線性規(guī)劃問題的

19、命令，輸入格式： c=c1x1+c2x2+cnxn； m=a11x1+a12x2+a1nxn=b1， am1x1+am2x2+amnxn P Pi+1i+1，i = 1,2,i = 1,2,L-1,L-1. . 目標規(guī)劃模型 即在計算過程中即在計算過程中, , 首先保證首先保證P P1 1級目標的實現(xiàn)，這時可級目標的實現(xiàn)，這時可不考慮次級目標；而不考慮次級目標；而P P2 2級目標是在實現(xiàn)級目標是在實現(xiàn)P P1 1級目標的基礎(chǔ)上級目標的基礎(chǔ)上考慮的，以此類推?？紤]的，以此類推。當需要區(qū)別具有相同優(yōu)先因子的若干個目標的差別當需要區(qū)別具有相同優(yōu)先因子的若干個目標的差別時，可分別賦于它們不同的權(quán)系數(shù)

20、時，可分別賦于它們不同的權(quán)系數(shù)w wj j 。優(yōu)先因子及權(quán)系數(shù)的值，均由決策者按具體情況來優(yōu)先因子及權(quán)系數(shù)的值，均由決策者按具體情況來確定確定 （4 4）目標規(guī)劃的目標函效）目標規(guī)劃的目標函效 目標規(guī)劃的目標函數(shù)是通過各目標約束的正、目標規(guī)劃的目標函數(shù)是通過各目標約束的正、負偏差變量和賦于相應(yīng)的優(yōu)先等級來構(gòu)造的負偏差變量和賦于相應(yīng)的優(yōu)先等級來構(gòu)造的目標規(guī)劃模型決策者的要求是盡可能從某個方向決策者的要求是盡可能從某個方向縮小偏離目標的數(shù)值縮小偏離目標的數(shù)值。于是，目標規(guī)劃的目標函數(shù)應(yīng)該是求極小值于是，目標規(guī)劃的目標函數(shù)應(yīng)該是求極小值min min f f f f （d d + +，d d - -

21、) ) 其基本形式有三種：其基本形式有三種： 要求恰好達到目標值，即使相應(yīng)目標約束的正、負要求恰好達到目標值，即使相應(yīng)目標約束的正、負偏差變量都要盡可能地小。偏差變量都要盡可能地小。這時取這時取 min min （d d + + + + d d - - ) )； 要求不超過目標值，即使相應(yīng)目標約束的正偏差變要求不超過目標值，即使相應(yīng)目標約束的正偏差變量要盡可能地小。量要盡可能地小。這時取這時取 min min （d d + + ) )；目標規(guī)劃模型 要求不低于目標值，即使相應(yīng)目標約束的負偏差變量要要求不低于目標值，即使相應(yīng)目標約束的負偏差變量要盡可能地小。盡可能地小。這時取這時取 min mi

22、n （d d - - ) )；對于上例對于上例, , 我們根據(jù)決策者的考慮可知我們根據(jù)決策者的考慮可知 第一優(yōu)先級要求第一優(yōu)先級要求 minmin（d d1 1+ + + + d d2 2+ + ) )； 第二優(yōu)先級要求第二優(yōu)先級要求 minmin（d d3 3+ + ) )； 第三優(yōu)先級要求第三優(yōu)先級要求 minmin（d d4 4- - ) )； 第四優(yōu)先級要求第四優(yōu)先級要求 minmin（d d1 1- - + 2+ 2d d2 2- - ) )，這里，這里, , 當不能滿足市當不能滿足市場需求時場需求時, , 市場認為市場認為B B產(chǎn)品的重要性是產(chǎn)品的重要性是A A產(chǎn)品的產(chǎn)品的2 2倍

23、即減少倍即減少B B產(chǎn)品的影響是產(chǎn)品的影響是A A產(chǎn)品的產(chǎn)品的2 2倍，因此引入了倍，因此引入了2:12:1的權(quán)系數(shù)。的權(quán)系數(shù)。 目標規(guī)劃模型綜合上述分析，我們可得到下列目標規(guī)劃模型綜合上述分析，我們可得到下列目標規(guī)劃模型 Min f = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- + 2d2- ) s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 (5) 12x1 + 18x2 +d4- -d4+ =252 x1 , x2 , di- ,di+ 0 , i = 1,2,

24、3,4. 目標規(guī)劃模型根據(jù)上面討論根據(jù)上面討論, ,我們可以得到目標規(guī)劃的一般形式如下我們可以得到目標規(guī)劃的一般形式如下KknjddxmibxaKkgddxctsddPLGPkkjnjijijnjkkkjkjLlKkklkklkl, 2 , 1, 2 , 1, 0, 2 , 1,),(, 2 , 1,. . )(min)(1111作業(yè) 1. 加工奶制品的生產(chǎn)計劃加工奶制品的生產(chǎn)計劃 1桶牛奶可以加工桶牛奶可以加工3公斤公斤A1，每公斤獲利，每公斤獲利24元，耗時元，耗時12小時；可以小時；可以加工加工4公斤公斤A2 ，每公斤獲利，每公斤獲利16元；耗時元；耗時8小時；小時； 每天供應(yīng)每天供應(yīng)5

25、0桶牛奶，總的加工時為桶牛奶，總的加工時為480小時，至多加工小時，至多加工100公斤的公斤的A1； 制訂生產(chǎn)計劃，使每天獲利最大制訂生產(chǎn)計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計劃？公斤，應(yīng)否改變生產(chǎn)計劃？其他費用其他費用: :450元元/千噸千噸 應(yīng)如何分配水庫供水量，公司才能獲利最多？應(yīng)如何分配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增加到多少？若水庫供水量都提高一倍，公司利潤可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費引水管理