第七講 運籌學(xué)建模

1、1 1第七講第七講 運籌學(xué)模型運籌學(xué)模型7.1 線性規(guī)劃模型線性規(guī)劃模型(運輸問題模型運輸問題模型)7.2 01型整數(shù)規(guī)劃模型型整數(shù)規(guī)劃模型7.3 目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃模型7.4 非線性規(guī)劃問題非線性規(guī)劃問題2 2運籌學(xué)的分支較多，本章我們只介紹線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃及非線性規(guī)劃等方面的內(nèi)容，重點講解運籌學(xué)模型的分析和建立，模型的求解通常使用LINGO軟件來完成.3 31.運輸問題模型概述運輸問題模型概述運輸問題是一類特殊的線性規(guī)劃模型，該模型的建立最初用于解決一個部門的運輸網(wǎng)絡(luò)所要求的最經(jīng)濟的運輸路線和產(chǎn)品的調(diào)配問題，并取得了成功.然而，在實際問題的應(yīng)用中，除運輸問題外，許多非運輸問題

2、的實際問題一樣可以建立其相應(yīng)的運輸問題模型，并由此而求出其最優(yōu)解.下面以“產(chǎn)銷平衡模型”為例對運輸問題進行簡單的概括和描述.7.1 運輸問題模型運輸問題模型4 4某產(chǎn)品的生產(chǎn)有m個產(chǎn)地Ai(i1，2，m)，其生產(chǎn)量分別為ai(i1，2，m)，而該產(chǎn)品的銷售有n個銷售地Bj(j1，2，n)，其需要量分別為bj(j1，2，n).已知該產(chǎn)品從產(chǎn)地Ai(i1，2，m)到銷售地Bj(j1，2，n)的單位運價為cij(i1，2，m；j1，2，n)，試建立該運輸問題的線性規(guī)劃模型.假設(shè)從產(chǎn)地Ai(i1，2，m)到銷售地Bj(j1，2，n)的運輸量為xij.5 5我們可把運輸量xij(i1，2，m；j1，2，

3、n)匯總于產(chǎn)銷平衡表7-1中，而把單位運價cij(i1，2，m；j1，2，n)匯總于單位運價表7-2中.則在該產(chǎn)銷平衡表中，第j列的含義為：從各產(chǎn)地Ai(i1，2，m)發(fā)往銷售地j的部分運輸量x1j，x2j，xmj的和應(yīng)等于銷量bj，第i行的含義類同.6 6 表表 7-17 7 表表 7-28 8由以上的討論，對產(chǎn)銷平衡的情形，我們可給出其運輸問題的數(shù)學(xué)模型如下：(7.1.1)11min Z=mnijijijc x11 1,2,s.t. 1,2,0mijjinijijijxbjnxaimx9 9 當(dāng)然，在實際問題的應(yīng)用中，常出現(xiàn)產(chǎn)銷不平衡的情形，此時，需要把產(chǎn)銷不平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題來進

4、行討論.例如當(dāng)產(chǎn)量大于銷量時，只需增加一個虛擬的銷售地jn1，而該銷售地的需要量為即可.銷量大于產(chǎn)量的情形類同.1miia1niib11mniiiiab1niib1miia10 102.應(yīng)用實例應(yīng)用實例例例1 生產(chǎn)時序的安排.(1)問題的提出.北方飛機公司為全球各航空公司制造商用飛機.其生產(chǎn)過程之最后階段為生產(chǎn)噴射引擎，然后裝置于制成的機體，該公司有若干近期必須交付使用的合同，現(xiàn)需安排今后四個月飛機噴射引擎的生產(chǎn)計劃，并需于每月末分別提供10、15、25、20臺引擎.已知該公司各月的生產(chǎn)能力和生產(chǎn)每臺引擎的成本如表7-3所示，又如果生產(chǎn)出來的引擎當(dāng)月不能交貨的，每臺引擎每積壓一個月需存儲和維護

5、費用0.015百萬元，試在完成合約的情況下，制定一引擎數(shù)量的生產(chǎn)安排方案，以使該公司今后四個月的生產(chǎn)費用最小.11 11 表表 7-312 12 (2)模型分析與變量的假設(shè).用運輸問題模型求該問題最優(yōu)解的關(guān)鍵在于怎樣建立該問題的產(chǎn)銷平衡表及元素xij和單位運價表及元素cij.為此，我們假設(shè)xij表示第i月生產(chǎn)并用于第j月交貨的引擎數(shù)，因公司必須完成合同，則xij應(yīng)滿足：(7.1.2)11122213233314243444 10 15 2520 xxxxxxxxxx13 13每月生產(chǎn)的用于當(dāng)月和以后各月交貨的引擎數(shù)不可能超過該公司的實際生產(chǎn)能力，xij應(yīng)滿足：11121314222324344

6、444 25 35 (4.2.3) 30 10 xxxxxxxxxx14 14 下面構(gòu)造“單位運價表”，它應(yīng)等價于這里的“成本費用表”.因第i月生產(chǎn)并用于第j月交貨的引擎數(shù)的實際成本cij應(yīng)該是其生產(chǎn)單位成本再加上存儲、維護費用，從而我們可得其“成本費用表”如表7-4所示.15 15表 7-416 16 由于這是產(chǎn)銷不平衡問題，故增加一虛擬的銷售地D，使之能構(gòu)造為產(chǎn)銷平衡模型，并把“產(chǎn)銷平衡表和單位運價表”合二為一(見表7-5).在表7-5中，ai表示公司第i月的生產(chǎn)能力，bj表示第j月的合同供應(yīng)量，cij表示相應(yīng)的成本費用，因在實際問題中，當(dāng)ij時，xij0，故令相應(yīng)的cijM.17 17表

7、 7-518 18 (3)模型的建立與求解.如上討論，我們可給出“生產(chǎn)時序的安排”所對應(yīng)的“運輸問題模型”：(7.1.4)4411min =ijijijzc x4141 s.t. 0ijijiiijijjjijc xac xbx19 19據(jù)此，我們可求出其最優(yōu)解為：x1110， x1215， x235， x3320， x3410， x4410相應(yīng)的最小生產(chǎn)費用為： 今后四個月引擎數(shù)量的生產(chǎn)安排如表7-6所示.4411min =77.3ijijijzc x2020 表 7-621 217.2.1整數(shù)規(guī)劃的定義和模型 1.整數(shù)規(guī)劃的定義 在求解線性規(guī)劃問題時,得到的最優(yōu)解可能是分數(shù)或小數(shù),但許多實

8、際一要求得到的解為整數(shù)才行。這種要求線性規(guī)劃有整數(shù)解的問題，稱為整數(shù)規(guī)劃（Integer programming)或簡稱IP。7.2 01型整數(shù)規(guī)劃模型型整數(shù)規(guī)劃模型2222 2. 整數(shù)規(guī)劃的分類 如不中特殊說明，一般指整數(shù)線性規(guī)劃。對于整數(shù)線性規(guī)劃模型大致可分為三類： 變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。 變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。 變量只能取0或1時，稱之為0-1整數(shù)規(guī)劃。本節(jié)重點介紹0-1整數(shù)規(guī)劃。23233.整數(shù)規(guī)劃的實例例1 某廠擬用火車裝運甲、乙兩種貨物集裝箱，每箱的體積、重量、可獲利潤以及裝運所受限制如表7-7所示，問兩種貨物各裝多少箱，可使獲得利潤最大？242

9、4解：設(shè)甲、乙兩種貨物裝運箱數(shù)分別為X1和X2，顯然X1和X2都要求為整數(shù)，最大利潤為Z于是可建立整數(shù)規(guī)劃模型如下： 注：是不是可通過把不考慮整數(shù)要求求得的最優(yōu)解經(jīng)過“化整”得到滿足整數(shù)要求的最優(yōu)解呢？211020 xxMaxZ為整數(shù)且21212121,0,13522445 . .xxxxxxxxts2525此例可解得X1=8,X2=0,湊整為X1=5,X2=0,這就破壞了條件（1），因而不是可行解：如截斷小數(shù)變?yōu)閄1=4,X2=0,這當(dāng)然滿足所有約束條件，但不是最優(yōu)解，因為對X1=4,X2=0有Z=80，而對X1=4,X2=1(也是可行解)有Z=90.因此這就要專門研究整數(shù)規(guī)劃的解法。262

10、6 4.整數(shù)規(guī)劃的求解方法（1）分枝定界法可求純或混合整數(shù)線性規(guī)劃。（2）割平面法可求純或混合整數(shù)線性規(guī)劃（3）隱枚舉法求解“0-1”整數(shù)規(guī)劃：過濾隱枚舉法；分枝隱枚舉法。（4）匈牙利法解決指派問題（“0-1”規(guī)劃特殊情形）（5）蒙特卡洛法求解各種類型規(guī)劃。這里不一一介紹，感興趣的同學(xué)再去查找相關(guān)資料。27277.2.2 01型整數(shù)規(guī)劃問題 1. 01型整數(shù)規(guī)劃模型概念 0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量僅取值0或1.這時稱為0-1變量，或稱二進制變量。僅取值0或1這個條件可由約束條件“且為整數(shù)”所代替，這是和一般整數(shù)規(guī)劃的約束條件形式一致的。在一些問題中，如果引入0-1變量，就

11、可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個問題中討論了。在實際問題的討論中，01型整數(shù)規(guī)劃模型也對應(yīng)著大量的最優(yōu)決策的活動與安排討論，我們將列舉一些模型范例，以說明這個事實.282801型整數(shù)規(guī)劃的數(shù)學(xué)模型為：這里，0|1表示0或1.1 122max(min)nnzc xc xc x11 11221121 1222221 12212( , )( , )s.t.( , ),0|1nnnnmmmnnmna xa xa xba xa xa xba xaxaxbx xx 2929 2 . 01型整數(shù)規(guī)劃模型的解法型整數(shù)規(guī)劃模型的解法01型整數(shù)規(guī)劃模型的解法一般為窮舉法或隱枚舉法，窮舉法指的是

12、對決策變量x1，x2，xn的每一個0或1值，均比較其目標(biāo)函數(shù)值的大小，以從中求出最優(yōu)解.這種方法一般適用于決策變量個數(shù)n較小的情況.當(dāng)n較大時，由于n個0、1的可能組合數(shù)為2n，故此時即便用計算機進行窮舉來求最優(yōu)解，也幾乎是不可能的.隱枚舉法是增加了過濾條件的一類窮舉法，該法雖能減少運算次數(shù)，但對有些問題并不適用.3030 3. 應(yīng)用實例應(yīng)用實例 例例1：選址問題：選址問題某公司擬在市東、南、西三區(qū)建立門市部。某公司擬在市東、南、西三區(qū)建立門市部。擬議中有擬議中有7個位置（個位置（i=1,2,7）可供選擇。規(guī)定：）可供選擇。規(guī)定：由由A1、A2、A3三個點中至多選兩個；在西區(qū)三個點中至多選兩個

13、；在西區(qū)A4、A5兩個點中至多選一個；在南區(qū)兩個點中至多選一個；在南區(qū)A6、A7兩個點中至多兩個點中至多選一個。如選用點，設(shè)備投資估計為元，每年可獲選一個。如選用點，設(shè)備投資估計為元，每年可獲利潤估計為元，但投資總額不能超過利潤估計為元，但投資總額不能超過B元。問應(yīng)選元。問應(yīng)選擇哪幾個點可使年利潤最大？擇哪幾個點可使年利潤最大？31 31解：引入0-1變量，令 于是建立下列模型：)7,.,2 , 1( ixi點沒被選用當(dāng)點被選用當(dāng)iiiAAx 0 17,.,2 , 1, 10112max7654321772211772211ixxxxxxxxBxbxbxbxcxcxcZi或3232例例2：指派

14、問題：指派問題有一份說明書，需譯成英、日、德、俄四種文字?，F(xiàn)有甲、乙、丙、丁四個人，他們的將說明書譯成不同文字所需的時間如表7-8所示。問應(yīng)指派哪個人完成哪項工作，使所需的總時間最少？3333解：一般地，有n項任務(wù)，n個完成人，第i人完成第j項任務(wù)的代價為 （i,j=1,2,，n).為了求得總代價最小的指派方案，引入0-1變量 ，令數(shù)學(xué)模型為： 0 1項任務(wù)人完成第不指派第項任務(wù)人完成第指派第jijixijijc),.,2, 1,(njixij1011. .min11或ijnjijniijijijxxxtsxcZ3434 例例3 工程上馬的決策問題工程上馬的決策問題.(1)問題的提出.某部門三

15、年內(nèi)有四項工程可以考慮上馬，每項工程的期望收益和年度費用(千元)如表7-9所示.假定每一項已選定的工程要在三年內(nèi)完成，試確定應(yīng)該上馬哪些工程，方能使該部門可能的期望收益最大.3535表 7-93636 (2)模型分析與變量的假設(shè).這是工程上馬的決策問題，對任一給定的工程而言，它只有兩種可能，要么上馬，要么不上馬，這兩種情況分別用1、0表示，設(shè)： 因每一年的投資不超過所能提供的可用資金數(shù)，故該01型整數(shù)規(guī)劃問題的約束條件為：0,(1,2,3,4)jjjxj決定不投資第 個項目決定投資第個 項目1，3737由于期望收益盡可能大，故目標(biāo)函數(shù)為:max z20 x140 x220 x330 x4123

16、41234123412345438187962281021024,0|1xxxxxxxxxxxxx x x x3838 (3)模型的建立與求解.至此，我們得到該問題的01型整數(shù)規(guī)劃模型為max z20 x140 x220 x330 x4約束條件為:1234123412341234543818 79622 81021024 ,0|1xxxxxxxxxxxxx x x x3939 下面用隱枚舉法求其最優(yōu)解.易知，該01型整數(shù)規(guī)劃模型有一可行解(0，0，0，1)，它對應(yīng)的目標(biāo)函數(shù)值為z30.自然，該模型的最優(yōu)解所對應(yīng)的目標(biāo)函數(shù)值應(yīng)不小于30，于是，我們增加一過濾條件為：20 x140 x220 x3

17、30 x430在此過濾條件(過濾條件可不唯一)下，用隱枚舉法求01型整數(shù)規(guī)劃模型的最優(yōu)解的步驟為：4040先判斷第一枚舉點所對應(yīng)的目標(biāo)函數(shù)值是否滿足過濾條件，若不滿足，則轉(zhuǎn)下一步；若滿足，再判斷該枚舉點是否滿足各約束條件，若有一個約束條件不滿足，則轉(zhuǎn)下一步，若均滿足，則將該枚舉點所對應(yīng)的目標(biāo)函數(shù)值z1(本例中，z130)作為新的目標(biāo)值，并修改過濾條件為：20 x140 x220 x330 x4z1再轉(zhuǎn)下一步.41 41再判斷第二枚舉點所對應(yīng)的目標(biāo)函數(shù)值是否滿足新的過濾條件，若不滿足，則轉(zhuǎn)下一步；若滿足，接著判斷該枚舉點是否滿足各約束條件，若有一個約束條件不滿足，則轉(zhuǎn)下一步，若均滿足，則將該枚舉

18、點所對應(yīng)的目標(biāo)函數(shù)值z2(z2z1)作為新的目標(biāo)值，并修改過濾條件為：20 x140 x220 x330 x4z2再轉(zhuǎn)下一步.4242重復(fù)步驟，直至所有的枚舉點均比較結(jié)束為止.由隱枚舉法的求解步驟我們可給出該問題的求解過程如表7-10所示，并得到最優(yōu)解為x1，x2，x3，x4(0，1，1，1)，相應(yīng)的目標(biāo)值為90(千元).故應(yīng)上馬的工程為2號、3號、4號工程.4343表表 7-104444續(xù)表注：在該表中，表示滿足相應(yīng)條件，表示不滿足相應(yīng)條件.45457.3.1 目標(biāo)規(guī)劃模型概述目標(biāo)規(guī)劃模型概述1.相關(guān)的幾個概念相關(guān)的幾個概念1)正、負偏差變量d，d正偏差變量d表示決策值xi(i1，2，n)超

19、過目標(biāo)值的部分；負偏差變量d表示決策值xi(i1，2，n)未達到目標(biāo)值的部分.一般而言，正負偏差變量d，d的相互關(guān)系如下：7.3 目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃模型4646當(dāng)決策值xi(i1，2，n)超過規(guī)定的目標(biāo)值時，d0，d0；當(dāng)決策值xi(i1，2，n)未超過規(guī)定的目標(biāo)值時，d0，d0；當(dāng)決策值xi(i1，2，n)正好等于規(guī)定的目標(biāo)值時，d0，d0.47472)絕對約束和目標(biāo)約束絕對約束是必須嚴格滿足的等式約束或不等式約束，前述線性規(guī)劃中的約束條件一般都是絕對約束；而目標(biāo)約束是目標(biāo)規(guī)劃所特有的，在約束條件中允許目標(biāo)值發(fā)生一定的正偏差或負偏差的一類約束，它通過在約束條件中引入正、負偏差變量d、d來實

20、現(xiàn).48483)優(yōu)先因子(優(yōu)先級)與權(quán)系數(shù)目標(biāo)規(guī)劃問題常要求許多目標(biāo)，在諸多目標(biāo)中，凡決策者要求第一位達到的目標(biāo)賦予優(yōu)先因子P1，要求第二位達到的目標(biāo)賦予優(yōu)先因子P2，并規(guī)定PkPk1，即Pk1級目標(biāo)的討論是在Pk級目標(biāo)得以實現(xiàn)后才進行的(這里k1，2，n).若要考慮兩個優(yōu)先因子相同的目標(biāo)的區(qū)別，則可通過賦予它們不同的權(quán)系數(shù)wj來完成.49492.目標(biāo)規(guī)劃模型的目標(biāo)函數(shù)目標(biāo)規(guī)劃模型的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)是根據(jù)各目標(biāo)約束的正、負偏差變量d、d和其優(yōu)先因子來構(gòu)造的.一般而言，當(dāng)每一目標(biāo)值確定后，我們總要求盡可能地縮小決策值與目標(biāo)值的偏差，故目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是min zf(d，d)的形式

21、.我們可將其分為以下三種情形：5050(1)當(dāng)決策值xi(i1，2，n)要求恰好等于規(guī)定的目標(biāo)值時，這時正、負偏差變量d、d+都要盡可能小，即對應(yīng)的目標(biāo)函數(shù)為:min zf(dd)51 51 (2)當(dāng)決策值xi(i1，2，n)要求不超過規(guī)定的目標(biāo)值時，這時正偏差變量d要盡可能小，即對應(yīng)的目標(biāo)函數(shù)為:min zf(d)5252 (3)當(dāng)決策值xi(i1，2，n)要求超過規(guī)定的目標(biāo)值時，這時負偏差變量d要盡可能小，即對應(yīng)的目標(biāo)函數(shù)為:min zf(d) 目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式為：11min ()LKllkklkklkzPw dw d5353 (7.3.1)11,(1,2, ,)(=,) ,(1

22、,2,)s.t.0,(1,2, ),0,(1,2,)njkjjkkkkjnijjijjkkc xddgkk ga xb imxjnddkK為相應(yīng)的目標(biāo)值54547.3.2 目標(biāo)規(guī)劃模型舉例目標(biāo)規(guī)劃模型舉例例例1 某工廠的總生產(chǎn)能力為每天500小時，該廠生產(chǎn)A，B兩種產(chǎn)品，每生產(chǎn)一件A產(chǎn)品或B產(chǎn)品均需一小時，由于市場需求有限，每天只有300件A產(chǎn)品或400件B產(chǎn)品可賣出去，每出售一件A產(chǎn)品可獲利10元，每出售一件B產(chǎn)品可獲利5元，廠長按重要性大小的順序列出了下列目標(biāo)，并要求按這樣的目標(biāo)進行相應(yīng)的生產(chǎn).(1)盡量避免生產(chǎn)能力閑置；(2)盡可能多地賣出產(chǎn)品，但對于能否多賣出A產(chǎn)品更感興趣；(3)盡量

23、減少加班時間.5555解解 模型的分析與建立：顯然，這樣的多目標(biāo)決策問題，是單目標(biāo)決策的線性規(guī)劃模型所難勝任的.對于這類問題，必須采用新的方法和手段來建立對應(yīng)的模型.5656設(shè)x1，x2分別表示產(chǎn)品A，B的生產(chǎn)數(shù)量，d1表示生產(chǎn)能力閑置的時間，d1表示加班時間，d2表示產(chǎn)品A沒能達到銷售目標(biāo)的數(shù)目，d3表示產(chǎn)品B沒能達到銷售目標(biāo)的數(shù)目.因要求盡量避免生產(chǎn)能力閑置及盡量減少加班時間，故有目標(biāo)約束條件：d1、d1要盡可能小，又要求盡可能多地賣出產(chǎn)品，故有目標(biāo)約束條件：1211500 xxdd1223300,400 xdxd5757d2、d3要盡可能小，多賣出A產(chǎn)品的要求可體現(xiàn)在目標(biāo)函數(shù)的權(quán)系數(shù)中，

24、于是可得到目標(biāo)規(guī)劃模型為:滿足的約束條件為： (7.3.2)11222331min 2PdPdPdPd12111213121231500300. .400,0 xxddxdstxdx x dddd5858 例例2 職工的調(diào)資方案問題.(1)問題的提出.某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時，要求相關(guān)部門遵守以下的規(guī)定：年工資總額不超過60000元；每級的人數(shù)不超過定編規(guī)定的人數(shù)；、級的升級面盡可能達到現(xiàn)有人數(shù)的20%；級不足編制的人數(shù)可錄用新職工，又級的職工中有10%的人要退休.相關(guān)資料匯總于表7-11中，試為單位領(lǐng)導(dǎo)擬定一個滿足要求的調(diào)資方案.5959 表 7-116060 (2)模型分

25、析與變量假設(shè).顯然這是一個多目標(biāo)規(guī)劃的決策問題，適于用目標(biāo)規(guī)劃模型求解，故需要確定該問題與之對應(yīng)的決策變量、目標(biāo)值、優(yōu)先等級及權(quán)系數(shù)等.設(shè)x1，x2，x3分別表示提升到、級和錄用到級的新職工人數(shù)，由題設(shè)要求可確定各目標(biāo)的優(yōu)先因子如下：P1年工資總額不超過60000元；P2每級的人數(shù)不超過定編規(guī)定的人數(shù)；P3、級的升級面盡可能達到現(xiàn)有人數(shù)的20%.61 61下面再確定目標(biāo)約束.因為要求年工資總額不超過60000元，所以有： 且正偏差變量d1要盡可能小.又第二目標(biāo)要求每級的人數(shù)不超過定編規(guī)定的人數(shù)，所以:11223112000(1010 10%)1500(12)1000(15)60000 xxxx

26、xdd6262對于級，有，且正偏差變量d2要盡可能?。粚τ诩?，有，且正偏差變量d3要盡可能小；對于級，有，且正偏差變量d4要盡可能小；對于第三目標(biāo)，、級的升級面盡可能達到現(xiàn)有人數(shù)的20%，我們有下述約束：12210(10.1)12xdd12331215xxdd23441515xxdd15526612 20%15 20%xddxdd6363 (3)模型的建立.由此，我們可得到該問題的目標(biāo)規(guī)劃模型為：滿足約束條件112234356min ()()zPdP dddP dd)6 , 5 , 4 , 3 , 2 , 1; 3 , 2 , 1(0,34 . 20336000)15(1000)12(1500

27、)9(2000662551443233212211132211jiddxddxddxddxxddxxddxddxxxxxjji6464 求解后可得到該問題的一個多重解，并將這些解匯總于表7-12中，以供領(lǐng)導(dǎo)根據(jù)具體情況進行決策.6565表表 7-126666例例3 波德桑小姐是一個小學(xué)教師，她剛剛繼承了一筆遺產(chǎn)，交納稅金后凈得50000美元.波德桑小姐感到她的工資已足夠她每年的日常開支，但是還不能滿足她暑假旅游的計劃.因此，她打算把這筆遺產(chǎn)全部用去投資，利用投資的年息資助她的旅游.她的目標(biāo)當(dāng)然是在滿足某些限制的條件下進行投資，使這些投資的年息最大.波德桑小姐的目標(biāo)優(yōu)先等級是：第一，她希望至少投

28、資20000美元去購買年息為6的政府公債；第二，她打算最少用5000美元，至多用15000美元購買利息為5的信用卡；第三，她打算最多用10000美元購買隨時可兌換現(xiàn)款的股票，這些股票的平均利息為8；第四，她希望給她的侄子的新企業(yè)至少投資30000美元，她侄子允諾給她7的利息.6767解解 模型的分析與建立過程如下：設(shè)：設(shè)：x1購買公債的投資額；x2購買信用卡的投資額；x3購買可兌換股票的投資額；x4對她侄子企業(yè)的投資額.6868則得線性規(guī)劃模型如下：0,30000100001500050002000050000. t . s07. 008. 005. 006. 0max432143221432

29、14321xxxxxxxxxxxxxxxxxz6969 如果用線性規(guī)劃的單純形法求解這個問題，就會發(fā)現(xiàn)這個問題無可行解，或者說這個問題“不可行”.只要檢查一下第1、第2、第3和第6個約束，問題的不可行性是一目了然的.簡而言之，波德桑小姐沒有足夠的錢來實現(xiàn)她的愿望.然而，對于波德桑小姐來說，用線性規(guī)劃得出的這樣一個答案是不能使她滿意的.而能夠使她滿意的是，她希望知道即使不可能絕對地滿足她的全部愿望，那么怎樣才能盡可能地接近于滿足她的愿望？在這樣一個更為實際的許可條件下，我們假定她的目標(biāo)優(yōu)先等級如下：7070P1她的全部投資額不允許超過50000美元，這是一個絕對約束；P2盡可能地滿足：用2000

30、0美元購買公債，用500015000美元購買信用卡，她認為購買信用卡比購買公債重要2倍；P3盡可能資助她的侄子30000美元；P4盡可能用10000美元購買兌換股票，每年利息的總收入盡可能達到4000美元.那么，可以建立這個問題的目標(biāo)規(guī)劃模型：71 710)6, 2 , 1(,),4 , 3 , 2 , 1(400007. 008. 005. 006. 030000100001500050002000050000. .)()22(max774321664553442332221114321475463432211kddjxddxxxxddxddxddxddxddxddxxxxtsxddPdPd

31、ddPdPzkkj7272 求解這個目標(biāo)規(guī)劃問題，得到的滿意解是：x120000， x25000， x30， x425000 因此，我們得到了一個有意義的解，這個解能夠最好地滿足(即使不能絕對地滿足)波德桑小姐的全部目標(biāo).事實上，在實際的決策中，決策者的某些目標(biāo)不可能完全達到，這本來也是很自然的事情.7373例例4 一個公司需要從兩個倉庫調(diào)撥同一種零部件給下屬的三個工廠.每個倉庫的供應(yīng)能力，每個工廠的需求數(shù)量以及從每個倉庫到每個工廠之間的單位運費如表7-13所示(表中方格內(nèi)的數(shù)字為單位運費).7474表表 7-137575公司提出的目標(biāo)要求是：P1盡量滿足工廠3的全部需求；P2其他兩個工廠的需

32、求分別至少滿足75；P3總運費要求最少；P4倉庫2給工廠1的供應(yīng)量至少為1000單位；P5工廠1和工廠2的需求量滿足程度盡可能平衡.試建立這個問題的目標(biāo)規(guī)劃模型.7676解 設(shè)xij(i1，2；j1，2，3)表示倉庫i調(diào)運到工廠j的零部件數(shù)量.約束條件與目標(biāo)函數(shù)的建立過程如下：(1)供應(yīng)與需求約束：400015002000400030005523134422123321112223222111131211ddxxddxxddxxddxxxddxxx7777(2)滿足工廠3的全部需求的目標(biāo)可以通過將上面的偏差變量d5的最小化列入第一級目標(biāo)來反映.(3)滿足工廠1、2的75的需求，可建立約束： (

33、4)總運費要求最少，可建立約束：11251500772212662111ddxxddxx03108124108232221131211dxxxxxx7878 (5)對工廠1特殊供應(yīng)量的要求，可建立約束： (6)對工廠1、2的需求滿足程度的平衡的要求，可表示為得到約束：10009921ddx1500200022122111xxxx04343101022211211ddxxxx7979 (7)目標(biāo)函數(shù)為: 綜合以上分析，可得這個問題的目標(biāo)規(guī)劃模型為：)()(min10105948376251ddPdPdPddPdPz808010, 2 , 10,32121004343100003108124101

34、125150040001500200040003000. t . s)()(min10102221121199218232221131211772212662111552313442212332111222322211113121110105948376251ldd,jixddxxxxddxdxxxxxxddxxddxxddxxddxxddxxddxxxddxxxddPdPdPddPdPzllij，；，81 81 事實上，由于有了、兩個約束條件，可以取消、兩個約束條件.82827.4.1 非線性規(guī)劃的實例與定義非線性規(guī)劃的實例與定義如果目標(biāo)函數(shù)或約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問題為非線

35、性規(guī)劃問題.一般說來，解非線性規(guī)劃要比解線性規(guī)劃問題困難得多.非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個方法都有自己特定的適用范圍.下面通過實例給出非線性規(guī)劃數(shù)學(xué)模型的一般形式以及基本概念.7.4 非線性規(guī)劃問題非線性規(guī)劃問題8383例例1 (投資決策問題)某企業(yè)有n個項目可供選擇投資，并且至少要對其中一個項目投資.已知該企業(yè)擁有總資金A元，投資于第i(i1，n)個項目需花資金ai元，并預(yù)計可收益bi元.試選擇最佳投資方案.解解 設(shè)投資決策變量為： (i1，n)1,0iiix決定投資第 個項目決定不投資第 個項目，8484則投資總額為，投資總收益為.因為該公司至少要對一個項目投資，并且總

36、的投資金額不能超過總資金A，故有限制條件：另外，由于xi(i1，n)只取值0或1，所以還有 xi(1xi)0 (i1，n)niiixa1niiixb1niiiAxa108585 最佳投資方案應(yīng)是投資額最小而總收益最大的方案，所以這個最佳投資決策問題歸結(jié)為總資金以及決策變量(取0或1)的限制條件下，極大化總收益和總投資之比.因此，其數(shù)學(xué)模型為：(7.4.1)xi(1xi)0 (i1，n)niiiniiixaxbQ11max1s.t.0niiia xA8686 上面的例題是在一組等式或不等式的約束下，求一個函數(shù)的最大值(或最小值)問題，其中目標(biāo)函數(shù)或約束條件中至少有一個非線性函數(shù)，這類問題稱之為非

37、線性規(guī)劃問題(NP)，可概括為一般形式： minf(x)s.t.hj(x)0 (j1，q) (NP)(6.4.2)gi(x)0 (i1，p) 其中xx1，xnT稱為模型(NP)的決策變量，f稱為目標(biāo)函數(shù)，gi(i1，p)和hj(j1，q)稱為約束函數(shù).另外，gi(x)0(i1，p)稱為等式約束，8787hj(x)0(j1，q)稱為不等式約束.8888對于一個實際問題，在把它歸結(jié)成非線性規(guī)劃問題時，一般要注意如下幾點：(1)確定供選方案.首先要收集同問題有關(guān)的資料和數(shù)據(jù)，在全面熟悉問題的基礎(chǔ)上，確認什么是問題的可供選擇的方案，并用一組變量來表示它們.(2)提出追求目標(biāo).經(jīng)過資料分析，根據(jù)實際需要

38、和可能，提出要追求極小化或極大化的目標(biāo).并且，運用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式.(3)給出價值標(biāo)準(zhǔn).在提出要追求的目標(biāo)之后，要確立所考慮目標(biāo)的“好”或“壞”的價值標(biāo)準(zhǔn)，并用某種數(shù)量形式來描述它.8989(4)尋求限制條件.由于所追求的目標(biāo)一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示.90907.4.2 非線性規(guī)劃的非線性規(guī)劃的MATLAB解法解法如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達到(特別是可行域的頂點上達到)；而非線性規(guī)劃的最優(yōu)解(如果最優(yōu)解存在)則可能在其可行域的任意一點達到.MATLAB中非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式:(7.4.3)(minxfAeqBeqs.t.( )0Ceq( )0 xxC xxAB91 91其中f(x)是標(biāo)量函數(shù)，A、B、Aeq，Beq是相應(yīng)維數(shù)的矩陣和向量，C(x)、Ceq(x)是非線性向量函數(shù).9292MATLAB中的命令是 XFMINCON(FUN，X0，A，B，Aeq，Beq，LB，UB，NONLCON，OPTIONS)它的返回值是向量x，其中FUN是用M文件定義的函數(shù)f(x)；x0是x的初始值；A，B，Aeq，Beq定義了線性約束A*