數(shù)學(xué)規(guī)劃課件

第二章數(shù)學(xué)規(guī)劃模型

數(shù)學(xué)規(guī)劃論起始20世紀(jì)30年代末，50年代與60年代發(fā)展成為一個(gè)完整的分支并受到數(shù)學(xué)界和社會(huì)各界的重視。七八十年代是數(shù)學(xué)規(guī)劃飛速發(fā)展時(shí)期，無(wú)論是從理論上還是算法方面都得到了進(jìn)一步完善。時(shí)至今日數(shù)學(xué)規(guī)劃仍然是運(yùn)籌學(xué)領(lǐng)域中熱點(diǎn)研究問(wèn)題。從國(guó)內(nèi)外的數(shù)學(xué)建模競(jìng)賽的試題中看，有近1/4的問(wèn)題可用數(shù)學(xué)規(guī)劃進(jìn)行求解。

數(shù)學(xué)規(guī)劃模型的一般表達(dá)式：

為目標(biāo)函數(shù)，為約束函數(shù)，為可控變量，為已知參數(shù)，為隨機(jī)參數(shù)。

數(shù)學(xué)規(guī)劃分為線性規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、隨機(jī)規(guī)劃、整數(shù)規(guī)劃、分式規(guī)劃、幾何規(guī)劃、目標(biāo)規(guī)劃、平衡規(guī)劃、參數(shù)規(guī)劃、多目標(biāo)規(guī)劃等十幾種。當(dāng)然這么多規(guī)劃其中亦有交叉。又可經(jīng)過(guò)組產(chǎn)生新的規(guī)劃，每一種規(guī)劃有專著問(wèn)世。

第一節(jié)線性規(guī)劃模型線性規(guī)劃模型是運(yùn)籌學(xué)的重要分支，是20世紀(jì)三四十年代初興起的一門學(xué)科。1947年美國(guó)數(shù)學(xué)家丹齊格G.B.Dantzig及其同事提出的求解線性規(guī)劃的單純形法及有關(guān)理論具有劃時(shí)代的意義。他們的工作為線性規(guī)劃這一學(xué)科的建立奠定了理論基礎(chǔ)。隨著1979年前蘇聯(lián)數(shù)學(xué)家哈奇揚(yáng)的橢球算法和1984年美籍印度數(shù)學(xué)家卡瑪卡爾H.Karmarkar算法的相繼問(wèn)世，線性規(guī)劃的理論更加完備成熟，實(shí)用領(lǐng)域更加寬廣。線性規(guī)劃研究的實(shí)際問(wèn)題多種多樣，如生產(chǎn)計(jì)劃問(wèn)題、物資運(yùn)輸問(wèn)題、合理下料問(wèn)題、庫(kù)存問(wèn)題、勞動(dòng)力問(wèn)題、最優(yōu)設(shè)計(jì)問(wèn)題等。

例2.1生產(chǎn)組織與計(jì)劃問(wèn)題。某工廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，主要材料有鋼材3600kg、專用設(shè)備能力3000臺(tái)時(shí)。材料與設(shè)備能力的消耗定額以及單位產(chǎn)品所獲利潤(rùn)如下表所示，問(wèn)如何安排生產(chǎn)，才能使該廠所獲利潤(rùn)最大（只需建立數(shù)學(xué)模型）。產(chǎn)品單位產(chǎn)品消耗定額材料與設(shè)備甲（件）乙（件）現(xiàn)有材料與設(shè)備能力鋼材（kg）銅材（kg）設(shè)備能力（臺(tái)時(shí)）單位產(chǎn)品的利潤(rùn)（元）943600452000310300070120建模過(guò)程：設(shè)甲、乙兩種產(chǎn)品計(jì)劃生產(chǎn)量分別為和（件），總的利潤(rùn)為（元）。那么我們的任務(wù)就是：求變量的值為多少時(shí)，才能使總利潤(rùn)最大，由已知條件，，要受下列限制：(1)生產(chǎn)甲、乙兩種產(chǎn)品所用鋼材的總數(shù)不能超過(guò)現(xiàn)有鋼材數(shù)，即(2)生產(chǎn)甲、乙兩種產(chǎn)品所用銅材的總數(shù)不能超過(guò)現(xiàn)有銅材數(shù)，即(3)生產(chǎn)兩種產(chǎn)品所用的設(shè)備能力的總數(shù)不能超過(guò)現(xiàn)有設(shè)備能力的臺(tái)時(shí)數(shù)，即

(4)甲、乙兩種產(chǎn)品的計(jì)劃生產(chǎn)量不能為負(fù)數(shù)，即于是問(wèn)題轉(zhuǎn)化為求解如下的條件極值問(wèn)題（數(shù)學(xué)模型）：

例2.2

設(shè)有m種物質(zhì)，第種物資的庫(kù)存量為，每種物資都可以生產(chǎn)n種產(chǎn)品,第種物資生產(chǎn)第種產(chǎn)品時(shí)，每生產(chǎn)單位產(chǎn)品所需物資量為，每種物資生產(chǎn)第種產(chǎn)品時(shí)，每單位產(chǎn)品可獲利潤(rùn)（表2—2）問(wèn)如何組織生產(chǎn)才能使利潤(rùn)最大？

用表示生產(chǎn)第種產(chǎn)品計(jì)劃數(shù)，則問(wèn)題歸結(jié)為如下數(shù)學(xué)問(wèn)題（數(shù)學(xué)模型）：

約束條件的意義是：每種原料生產(chǎn)n種產(chǎn)品所需要的資源總量不能超過(guò)該種資源的庫(kù)存量；每種產(chǎn)品的生產(chǎn)計(jì)劃數(shù)不能為負(fù)。

表2銷地單位物資運(yùn)價(jià)產(chǎn)地產(chǎn)量需求量類似的問(wèn)題很多，諸如下料問(wèn)題、配料問(wèn)題、分配問(wèn)題、工廠選址問(wèn)題等等。它們的解決都是歸結(jié)上述的線性規(guī)劃問(wèn)題，只是約束條件有的是等式，有的是不等式。通過(guò)以上兩例可以看出：盡管所提問(wèn)題的內(nèi)容不同，但從構(gòu)成數(shù)學(xué)問(wèn)題的結(jié)構(gòu)來(lái)看，卻屬于同一類優(yōu)化問(wèn)題，其結(jié)構(gòu)具有如下特征：

（1）目標(biāo)函數(shù)是決策變量的線性函數(shù)。（2）約束條件都是決策變量的線性等式或不等式。二、線性規(guī)劃的解法概述、解的性質(zhì)及單純形法我們稱如下的條件極值問(wèn)題

為標(biāo)準(zhǔn)的線性規(guī)劃問(wèn)題。

若引進(jìn)記號(hào)則（LP）可簡(jiǎn)單地表示為進(jìn)一步，若令，則（LP）可表示為：

對(duì)于非標(biāo)準(zhǔn)形式的線性規(guī)劃，可通過(guò)下列辦法化成標(biāo)準(zhǔn)形式。①若求,可化為求.②若約束條件中含有不等式或則可引進(jìn)新變量（稱為松弛變量），化為等式約束：或③今后總假定，否則在等式兩邊乘以-1即可。④若變量無(wú)非負(fù)限制，則引入兩個(gè)非負(fù)變量與令，便可化為標(biāo)準(zhǔn)形式。解法概述（1）單純形法：1947年由美國(guó)數(shù)學(xué)家Dantzig提出，雖然在特殊情況下可能出現(xiàn)循環(huán)，但這種方法仍是目前求解線性規(guī)劃問(wèn)題最常用的方法。事實(shí)上在大量的實(shí)際問(wèn)題計(jì)算中看出，循環(huán)情況從未出現(xiàn)過(guò)（僅在特意構(gòu)造下才能出現(xiàn)）。它是一種迭代方法。（2）橢球法：1977年由前蘇聯(lián)數(shù)學(xué)家khachiyan提出的多項(xiàng)式時(shí)間算法，它在理論上保證了多項(xiàng)式時(shí)間算法的存在性。但大量數(shù)值研究發(fā)現(xiàn)，對(duì)于大多數(shù)實(shí)際問(wèn)題，橢球法在計(jì)算上不如單純形方法。線性規(guī)劃問(wèn)題的軟件解法求解線性規(guī)劃的常用方法是1947年G.B.Dantzig提出的單純形法。這種方法是以尋找最優(yōu)解的迭代過(guò)程為主線?；舅悸肥牵航o出一個(gè)基可行解（一個(gè)頂點(diǎn)）后，判斷其是否為最優(yōu)解；若它不是最優(yōu)解，可用迭代的方法轉(zhuǎn)換到另一個(gè)基可行解（頂點(diǎn)），最終找到使目標(biāo)函數(shù)值更優(yōu)的基可行解。經(jīng)過(guò)有限次迭代后，這一迭代過(guò)程以找到最優(yōu)解或判定問(wèn)題無(wú)最優(yōu)解為目標(biāo)。另外，求解線性規(guī)劃的方法還有Karmarkar算法和橢球算法。求解線性規(guī)劃的軟件很多，下面介紹Mathematica和MATLAB軟件。Mathematica和MATLAB求解Mathematica命令可用于求解各種形式的線性規(guī)劃問(wèn)題的命令。命令的輸入格式：

c=c1x1+c2x2+…+cnxn；

m={a11x1+a12x2+…+a1nxn<=b1，

…

am1x1+am2x2+…+amnxn<=bm}；用于求極小值的命令：

ConstrainedMin[c，m，{x1,x2,…,xn}]用于求極大值的命令：

ConstrainedMax[c，m，{x1,x2,…,xn}]MATLAB命令

命令輸入格式及線性規(guī)劃模型如下：其中：x0是算法迭代的初始點(diǎn)；nEq表示等式約束的個(gè)數(shù)。三、建模舉例例2.4營(yíng)養(yǎng)配餐問(wèn)題。每種蔬菜含有的營(yíng)養(yǎng)素成份是不同的，從醫(yī)學(xué)上知道，每人每周對(duì)每種營(yíng)養(yǎng)成分的最低需求量。某醫(yī)院營(yíng)養(yǎng)室在制定下一周菜單時(shí)，需要確定表2-3中所列六種蔬菜的供應(yīng)量，以便使費(fèi)用最小而又能滿足營(yíng)養(yǎng)素等其它方面的要求。規(guī)定白菜的供應(yīng)一周內(nèi)不多于20kg，其它蔬菜的供應(yīng)在一周內(nèi)不多于40kg，每周共需供應(yīng)140kg蔬菜，為了使費(fèi)用最小又滿足營(yíng)養(yǎng)素等其它方面的要求，問(wèn)在下一周內(nèi)應(yīng)當(dāng)供應(yīng)每種蔬菜各多少kg？

問(wèn)題分析與模型建立設(shè)分別表示下一周內(nèi)應(yīng)當(dāng)供應(yīng)的青豆、胡蘿卜、菜花、白菜、甜菜及土豆的量，費(fèi)用目標(biāo)函數(shù)為：

約束條件：鐵的需求量至少6個(gè)單位數(shù)：磷的需求量至少25個(gè)單位數(shù)：維生素A的需求量至少17500個(gè)單位：維生素C的需求量至少245個(gè)單位：煙酸的需求量至少5個(gè)單位數(shù)：

每周需供應(yīng)140千克蔬菜，即

0≤x1≤400≤x2≤400≤x3≤400≤x4≤200≤x5≤400≤x6≤40

b=(-1)*[140;6;25;17500;245;5];

xLB=zeros(6,1);

xUB=[40;40;40;20;40;40];

nEq=1;

x0=0*ones(6,1);

x=lp(c,A,b,xLB,xUB,x0,nEq);

disp('青豆需要的份數(shù)')

x(1)disp('胡羅卜需要的份數(shù)')

x(2)disp('菜花需要的份數(shù)')x(3)disp('白菜需要的份數(shù)')x(4)disp('甜菜需要的份數(shù)')x(5)disp('土豆需要的份數(shù)')x(6)執(zhí)行后輸出青豆需要的份數(shù)ans=

40胡羅卜需要的份數(shù)ans=

40.0000菜花需要的份數(shù)

ans=

0白菜需要的份數(shù)

ans=

20.0000甜菜需要的份數(shù)

ans=

0土豆需要的份數(shù)ans=

40最小費(fèi)用

ans=

560.0000四、整數(shù)線性規(guī)劃在許多線性規(guī)劃模型中，變量取整數(shù)時(shí)才有意義。例如，不可分解產(chǎn)品的數(shù)目，如汽車、房屋、飛機(jī)等，或只能用整數(shù)來(lái)記數(shù)的對(duì)象。這樣的線性規(guī)劃稱為整數(shù)線性規(guī)劃，簡(jiǎn)稱整數(shù)規(guī)劃，記為IP。整數(shù)規(guī)劃分為兩類：一類為純整數(shù)規(guī)劃，記為PIP，它要求問(wèn)題中全部變量都取整數(shù)；另一類是混合整數(shù)規(guī)劃，記之為MIP，它的某些變量只能取整數(shù)，而其他變量則為連續(xù)變量。整數(shù)規(guī)劃的特殊情況是0-1規(guī)劃，其變量只取0或者1；圖論中的一些問(wèn)題（如背包問(wèn)題等）也可用0-1規(guī)劃來(lái)描述。

在整數(shù)規(guī)劃模型中，若每一變量只取0或1，即為0-1規(guī)劃模型。0-1規(guī)劃模型因其特殊性，又不同于整數(shù)規(guī)劃的解法。如一般0-1規(guī)劃的隱枚舉法，指派問(wèn)題中的匈牙利法，背包問(wèn)題則可以用動(dòng)態(tài)規(guī)劃的方法求解。下面的幾個(gè)例子說(shuō)明了0-1規(guī)劃在實(shí)際問(wèn)題中的使用。例5.2背包問(wèn)題有n件物品，編號(hào)為1，2，…，n。第件重為kg，價(jià)值為元。今一裝包者欲將這些物品裝入一包，其質(zhì)量不能超過(guò)kg，問(wèn)應(yīng)裝入哪幾件價(jià)值最大？

解引入變量

將物品裝包不將物品裝包于是得問(wèn)題的模型為

取0或1，i=1，2，…，n背包問(wèn)題看似簡(jiǎn)單，但應(yīng)用很廣，例如某些投資問(wèn)題即可歸入背包問(wèn)題模型。此類問(wèn)題可以

描述為：設(shè)有總額為元的資金，投資幾項(xiàng)事業(yè)，第項(xiàng)副業(yè)需投資元，利潤(rùn)為元問(wèn)應(yīng)選擇哪些項(xiàng)總利潤(rùn)為最大？

例2.6某鉆井隊(duì)要從以下10個(gè)可供選擇的井位中確定5個(gè)鉆井探油，使總的鉆探費(fèi)用為最小。若10個(gè)井位的代號(hào)為，相應(yīng)的鉆探費(fèi)用為，并且井位選擇要滿足下列限制條件：

（1）或選和，或選；（2）選擇了或就不能選，反之亦然；（3）在中最多只能選兩個(gè)。試建立其數(shù)學(xué)模型：

解引入變量

選擇不選擇

于是以上問(wèn)題的數(shù)學(xué)模型為：

例2.7指派問(wèn)題。有項(xiàng)任務(wù)，由個(gè)人來(lái)完成，每人只能干一件，第個(gè)人完成第項(xiàng)任務(wù)需要的時(shí)間為小時(shí)，問(wèn)怎樣安排能使總用時(shí)最少？

解引入0-1型變量

人完成任務(wù)人不去完成任務(wù)

于是該問(wèn)題的數(shù)學(xué)模型為

整數(shù)規(guī)劃的解法較復(fù)雜，主要有分枝定界法、割平面法，隱枚舉法及解指派問(wèn)題的匈牙利法等。

分配甲、乙、丙、丁去完成A、B、C、D四項(xiàng)任務(wù)，每人完成一項(xiàng)，每項(xiàng)任務(wù)只能由一個(gè)人去完成，試做出任務(wù)分配使總時(shí)間最少。（個(gè)人完成各項(xiàng)任務(wù)如下表）個(gè)人完成各項(xiàng)任務(wù)如下表任務(wù)人員

AB

C

D甲86109乙912711丙7435丁95811編寫(xiě)Lingo程序如下model:sets:worker/w1..w4/;job/j1..j4/;