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

1、數(shù)學規(guī)劃模型 數(shù)學規(guī)劃模型是在實際問題的數(shù)學建模中應(yīng)用最廣泛的模型之一，也是運籌學的一個重要分支。在生產(chǎn)實踐中，經(jīng)常要制定使問題的某一項指標“最優(yōu)”的方案，這里的最優(yōu)包括“最大”、“最小”、“最多”、“最少”等。如：如何合理地分配、使用有限的資源（人力、物力及資金等）以獲得“最大收益”等諸如此類的問題，就是所謂數(shù)學規(guī)劃問題，數(shù)學規(guī)劃又分為線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃等。 線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃 動態(tài)規(guī)劃1.線性規(guī)劃模型1.1例生產(chǎn)計劃問題。某工廠制造甲乙兩種產(chǎn)品，每單位產(chǎn)品消耗和獲得的利潤如表1.1表1.1 生產(chǎn)計劃問題的數(shù)據(jù) 單位消耗 產(chǎn)品 原料甲產(chǎn)品/t乙產(chǎn)品/t現(xiàn)有原

2、料總量 鋼材/t95360 電力/(kw.h)45200 工作日/個310300 單位產(chǎn)品的利潤/(萬元/t)712試擬訂生產(chǎn)計劃，使該廠獲得利潤最大121212121212712max712,. .95360,45200,xxzzxxzxxzxxstxxxx解 設(shè)甲、乙兩種產(chǎn)品計劃生產(chǎn)量分別為 和 噸，利潤為 萬元則 ，我們的任務(wù)是求 的最大值，且 ， 受到鋼材的限制、電力的限制工作日的限制、非負條件的限制等，可得線性規(guī)劃的數(shù)學模型 1212310300,0,0 xxxx （1.1） ，121212(1.1)( ,)zf x xxxxx式中，目標函數(shù)是 和 的線性函數(shù)，而約束條件是 和 的線

3、性不等式，因此稱式(1.1)為線性規(guī)劃模型。線性規(guī)劃模型的解法 兩個變量的線性規(guī)劃模型的圖解法 單純形法 數(shù)學軟件，如Lindo軟件、Lingo軟件、Matlab等例1.2 投資方案的確定某部門要進行投資，現(xiàn)有四個投資項目。項目A：從第一年到第四年的每年年初需要投資，并于次年年末回收本利115；項目B：從第三年年初需要投資，到第五年年末回收本利125%，但規(guī)定最大投資額不超過40萬元；項目C：第二年初需要投資，到第五年末才能回收本利140%，但規(guī)定最大投資額部超過30萬元；項目D：五年內(nèi)每年的年初可買公債，于當年年末歸還，并可獲得6%的利息。已知該部門現(xiàn)有資金100萬元，試為該部門確定投資方案

4、，使得第五年末它擁有的資金本利總額最大？1）模型建立。決策變量。決策變量為每年年初向四個項目的投資額，設(shè)第i(i=1,2,3,4,5)年年初向A,B,C,D(j=1,2,3,4)四個項目的投資額為xij（萬元）。目標函數(shù)。設(shè)第五年年末擁有的資金本利總額為z，為了方便，將所有可能的投資列于下表1.2 年份項目 12345投資限額/萬元Ax11x21x31x41Bx3240Cx2330Dx14x24x34x44x54413223541.151.251.401.06zxxxx目標函數(shù)應(yīng)該是四項投資在第五年年末回收的本利之和，于是，目標函數(shù)為 約束條件a為了獲得最大的投資收益，每年年初應(yīng)將手頭的全部資

5、金投出去，因此第一年的投資總額應(yīng)是100萬元，即x11+x14=100b第二年的投資總額應(yīng)是第一年年底回收的各項投資的本利，即 x21+x23+x24=106%x14同理，第三、四、五年的投資額應(yīng)是上一年年底回收的各項投資本利，即 x31+x32+x34=106%x24+115%x11, x41+x44=106%x34+115%x21, x54=106%x44+115%x31.3224132235411142123241431323424114144342154.40,30.max1.151.251.401.06,. .1001.06,1.061.15,1.061.15,cxxzxxxxstx

6、xxxxxxxxxxxxxxx由于投資的限制，因此還有由此得投資問題的數(shù)學模型為 443132231.061.15,40,30,0,1,5;1,4ijxxxxxij 2）模型求解。用Lindo軟件求解，求得投資方案的最優(yōu)解為x11=71.698112萬元，x14=28.301888萬元，x23=30萬元，x32=40萬元，x34=42.452831萬元，x41=45萬元，其余決策變量均為零，最優(yōu)值z=143.75萬元。例1.3 貨機裝運。某貨機有三個貨艙：前艙、中艙、后艙。三個貨艙所能裝載的貨物的最大重量和體積都要限制，如表1.3所示。并且，為了保持飛機的平衡，三個貨艙中實際裝載貨物的重量必須

7、與其最大容許重量成比例。表1.3 三個貨艙裝載貨物的最大容許量和體積前艙中艙后艙重量限制/t10168體積限制/m3680087005300現(xiàn)有四類貨物供該貨機本次飛行裝運，其有關(guān)信息如表1.4，最后一列指裝運后獲得的利潤。表1.4 四類裝運貨物的信息質(zhì)量/t空間/(m3/t)利潤(元/t)貨物1184803100貨物2156503800貨物3235803500貨物4123902850應(yīng)如何安排裝運，使該貨機本次飛行利潤最大？1）模型假設(shè)。問題中沒有對貨物裝運提出其他要求，我們可做如下假設(shè)：每種貨物可以分割到任意??；每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙。2）

8、模型建立。決策變量：用xij表示第i種貨物裝入第j個貨艙的重量（噸），貨艙j=1,2,3分別表示前艙、中艙、后艙。目標函數(shù)：決策目標是最大化總利潤，即目標函數(shù)為1112132122233132334142433100()3800()3500()2850().zxxxxxxxxxxxx 約束條件：約束條件包括以下4個方面：111213212223313233414243112131411222324213233343.18,15,23,12;10,16,8;axxxxxxxxxxxxxxxxxxxxxxxx供裝載的四種貨物的總重量約束，即b.三個貨艙的重量限制，即1121314112223242

9、13233343112131411222324213233343.4806505803906800,4806505803908700,4806505803905300;.1016.8cxxxxxxxxxxxxdxxxxxxxxxxxx三個貨艙的空間限制三個貨艙裝入重量的平衡約束，即3）模型求解。將以上模型輸入Lindo 模型，可以得到結(jié)果：最優(yōu)解為x21=10t,x23=5t,x32=12.947t,x33=3t,x42=3.053t,其余變量均為零，最優(yōu)值z=121515.8t2.非線性規(guī)劃模型 非線性規(guī)劃問題可以看作是線性規(guī)劃問題的一種自然推廣，亦是數(shù)學規(guī)劃的一個重要組成部分。凡目標函數(shù)和

10、約束條件中包含有非線性函數(shù)的數(shù)學規(guī)劃問題都稱為非線性規(guī)劃問題。較之線性規(guī)劃模型而言，非線性規(guī)劃模型更能真實地反映問題的實質(zhì)。例2.1 設(shè)用甲、乙、丙三種有限資源生產(chǎn)A,B,C,D四種產(chǎn)品，產(chǎn)品的資源消耗定額及資源的有限供應(yīng)量如表2.1所示表2.1 產(chǎn)品的消耗定額與資源供應(yīng)量消耗定額 產(chǎn)品資源 A B C D資源可供應(yīng)量甲1232200乙7981300丙3017400 假定A,B,C,D四種產(chǎn)品價格隨產(chǎn)量的擴大而遞減，其需求函數(shù)分別為p1=11-0.01x1,p2=12-0.02x2,p3=13-0.03x3,p4=14-0.04x4,試確定四種產(chǎn)品的產(chǎn)量，以便使總收益最大。123412341

11、12233441122334412, ,( ,)(11 0.01 )(120.02)(130.03)(140.04)(11121A B C Dx xxxz x xx xp xp xp xp xxxxxxxxxxx解 設(shè)四種產(chǎn)品的產(chǎn)量分別為 , 和 ，則問題的目標函數(shù)（總收益函數(shù)） 3422221234314)(0.010.020.030.04)xxxxxx 其中，第一項是不變價格下的總收益，第二項是需要扣除的因價格變動造成的收益值，注意到資源的約束，上述問題可表為12342222123412341234134max(11121314)(0.010.020.030.04),. .23220079

12、830037400,0,1,2,3,4jzxxxxxxxxstxxxxxxxxxxxxj 顯然，上述問題是一個非線性規(guī)劃問題。在實際經(jīng)濟活動中，產(chǎn)量規(guī)模對價格的影響常常是一個不開忽略的重要因素：上述模型由于適當?shù)乜紤]了價格的可變部分對總收益的影響，而相應(yīng)的線性規(guī)劃模型，總收益函數(shù)只能在假定某不變價格的情況下由產(chǎn)量x1、x2、x3和x4線性確定，故較之線性模型更能真實地反映問題的實質(zhì)。非線性規(guī)劃模型求解 非線性規(guī)劃模型的求解具有一定的難度，并且求解非線性規(guī)劃問題的方法是多種多樣的，解某些問題的有效方法，對另外的問題卻未必有效。我們可以用一些數(shù)學軟件來求解。例2.2 工程造價問題 假定要建造容積為

13、1500m3的長方形倉庫，已知每平方米墻壁、屋頂和地面的造價分別為4元、6元、12元，基于美學考慮，要求寬度應(yīng)為高度的2倍，試建立使造價最省的數(shù)學模型。1）模型建立。決策變量：設(shè)倉庫的寬、高、長分別為x1,x2,x3(m)目標函數(shù)：墻壁面積為2(x1x2+x2x3)，造價為8(x1x2+x2x3)；屋頂與地面面積為x1x3，造價為18 x1x3 ，則目標函數(shù)為z= 8(x1x2+x2x3)+ 18 x1x3 約束條件。容積限制x1x2x3-1500=0,比例限制x1-2x2=0，及非負限制x1,x2,x30由此得到數(shù)學模型2131312312123min8() 18,. .15000,20,0

14、zx xxx xstx x xxxx x x 此為一非線性等式約束規(guī)劃模型。2）模型求解。用Lingo軟件求解。例2.3 經(jīng)營計劃問題某公司經(jīng)營兩種設(shè)備，假設(shè)每種設(shè)備的單位售價以及售出單位設(shè)備所需的營業(yè)時間及該公司在某段時間內(nèi)的總營業(yè)時間見表2.2（表中x1,x2為兩種設(shè)備的售出數(shù)量），建立營業(yè)額最大的營業(yè)營業(yè)計劃模型。表2.2 經(jīng)營計劃的數(shù)據(jù)設(shè)備公司可使用營業(yè)時間單位售價/元30450 800售出單位設(shè)備的營業(yè)時間/h0.52+0.25x23 整數(shù)規(guī)劃模型 在一個數(shù)學規(guī)劃模型中，如果它的某些決策變量或全部變量要求取整數(shù)時，就稱這個數(shù)學規(guī)劃模型為整數(shù)規(guī)劃模型。整數(shù)規(guī)劃模型可分為整數(shù)線性規(guī)劃模型

15、與整數(shù)非線性規(guī)劃模型。整數(shù)規(guī)劃又分為整數(shù)規(guī)劃、混合整數(shù)規(guī)劃及0-1規(guī)劃。整數(shù)規(guī)劃模型的一般形式1212min( ,),. .( ,)0,1,2,0,1,2, ,1,2, .ninjjf x xxsth x xximxjnxjn 為整數(shù)1212(1,2,),(1,2,),(1,2, )ininjfh imx xxfh imx xxxjn當 和均是的線性函數(shù)時,我們稱模型為整數(shù)線性規(guī)劃模型；當 和中至少有一個是的非線性函數(shù)時，稱模型為整數(shù)非線性規(guī)劃模型。若整數(shù)規(guī)劃模型中的決策變量只能取0或1，則稱模型為0-1規(guī)劃.例3.1 某航空公司為滿足客運量日益增長的需要，欲購置一批新的遠程及短程客機。每架客

16、機價格6300萬元，中程客機5000萬元，短程客機3500萬元。該公司現(xiàn)有資金7.5億元可用于購買飛機。估計年凈利潤每架遠程客機為420萬元，中程客機300萬元，短程客機230萬元。該公司現(xiàn)有熟練駕駛員可用來配備30架新飛機。維修設(shè)備足以維修新增加40架新的短程客機，每架中程客機的維修量相當于4/3架短程客機，而每架遠程客機的維修量相當于5/3架短程客機。為獲取最大利潤，該公司應(yīng)購買各類客機多少架？123123123123123123123max420300230,. . 63005000350075000,30,5440,33,0,xxxzxxxstxxxxxxxxxx x xx x x解

17、設(shè)購買遠程、中程、短程客機的數(shù)量分別為 、和 架，問題的數(shù)學模型為 均為整數(shù)。用Lindo軟件求解例3.2 合理下料問題 某鋼管零售商從鋼管廠家進貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進貨時得到的原料鋼管都是19m. 1）現(xiàn)有一客戶需要50根4m、20根6m和15根8m的鋼管，應(yīng)如何下料最節(jié)??？1）問題的分析。 首先，應(yīng)當確定哪些切割模式是可行的。所謂一個切割模式，是指按照客戶需要在原料上安排切割的一種組合。例如：我們可以將19m的鋼管切割成3根4m的鋼管，余料為7m；或者將19m的鋼管切割成4m、6m和8m的鋼管各1根，余料為1m。顯然，可行的切割模式是很多的。 其次，應(yīng)當確定哪些切割

18、模式是合理的。通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小此寸。例如：將19m的鋼管切割成3根4m的鋼管是可行的，但余料為7m，可以進一步將7m的余料切割成4m鋼管（余料為3m），或者將7m的余料切割為6m鋼管（余料為1m）。在這種合理性假設(shè)下，切割模式一共有7種，如表3.1所示表3.1 鋼管下料的合理切割模式4m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根數(shù)余料m模式14003模式23101模式32013模式41203模式51111模式60301模式70023問題化為在滿足客戶需要的條件下，按照哪些合理的模式，切割多少根原料鋼管最為節(jié)省。而所謂最為節(jié)省，可以有兩種標準：一是切割后剩

19、余的總余料量最小，二是切割原料鋼管的總根數(shù)最少。下面將對這兩個目標分別討論。2）模型建立。決策變量：用表示按第種模式切割的原料鋼管的根數(shù)，顯然它們應(yīng)當是非負整數(shù)。目標函數(shù)：以切割后剩余的總余料量最少為目標，則由表3.1可得 z1=3x1+x2+3x3+3x4+x5+x6+3x7 以切割原料鋼管的總根數(shù)最少為目標，則有 z2=x1+x2+x3+x4+x5+x6+x7下面分別在這兩種目標下求解。1234524563573.143250,2320,215.xxxxxxxxxxxx約束條件：為滿足客戶的需求，按照表應(yīng)有3）模型求解分別將目標函數(shù)與約束條件構(gòu)成整數(shù)線性規(guī)劃模型輸入Lindo求解。2）該客

20、戶除需要1）中的三種鋼管外還需要10根5m的鋼管。應(yīng)如何下料最節(jié)??？1）問題分析。按照問題1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。下面介紹的整數(shù)非線性規(guī)劃模型，可以同時確定切割模式和切割計劃，是帶有普遍性的方法。 同問題1）類似，一個合理的切割模式的余料不應(yīng)該大于和等于客戶需要的鋼管的最小尺寸(本題中為4m)，切割計劃中只使用合理的切割模式，而由于本題中的參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3m。此外，這里我們僅選擇總根數(shù)最少為目標進行求解。2）模型建立。 決策變量：由于不同切割模式不能超過3種，可以用xi表示按

21、照第i種模式(i=1,2,3)切割的原料鋼管的根數(shù)，顯然它們應(yīng)當是非負整數(shù)。設(shè)所使用的第i種切割模式下每根原料鋼管生產(chǎn)4m,5m,6m和8m的鋼管數(shù)量分別為r1i,r2i,r3i和r4i(均為非負整數(shù))。12311 112213321 122223331 132233341 1422433.50,10,20,15.zxxxr xr xr xr xr xr xr xr xr xr xr xr x目標函數(shù)：切割原料鋼管總根數(shù)最少，目標函數(shù)為 約束條件：為滿足客戶的需求，應(yīng)有 1121314112223242132333431916456819,16456819,16456819.mrrrrrrrr

22、rrrr每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過，也能少于16m(余量不能大于3m)，于是 3)模型求解。以上模型是一個整數(shù)非線性規(guī)劃模型，我們用Lingo軟件求解。0-1整數(shù)規(guī)劃模型例3.3 指派問題。在實際工作中，常常會碰到這樣的問題：要派n個人去完成n項不同的任務(wù)，每人必須而且只需完成其中一項。但由于各人的專長不同，完成各項任務(wù)的效率也就不同，因此就產(chǎn)生這樣一個問題，應(yīng)指派哪個人去完成哪項任務(wù)，使總的效率最高或總的花費時間最少？今欲指派甲、乙、丙、丁四人加工A、B、C、D四種不同零件，每人加工四種零件分別所需要的時間如表3.2所示。問應(yīng)該指派每人加工何種零件使總的花

23、費時間最少？表3.2 工人加工零件的工作效率ABCD甲4658乙61074丙78119丁938611,0,ijijxij）模型建立.決策變量：設(shè)表示第個人去加工零件的情況，即當指派第 人去加工 零件時，當不指派第 人去加工 零件時，11121314212223243132333441424344465861074781199386zzxxxxxxxxxxxxxxxx目標函數(shù)：問題使總的花費時間最少，用 表示總的花費時間，則目標函數(shù)為111213142122232431323334414243441,1,1,1.xxxxxxxxxxxxxxxx約束條件：由于每人只能加工一種零件，則有112131

24、411222324213233343142434441,1,1,1.xxxxxxxxxxxxxxxx而每種零件必有一個人來加工，則有2).模型求解以上各式構(gòu)成的模型是一個0-1整數(shù)規(guī)劃模型，用Lindo軟件求解。例3.4 選址問題某公司擬在市東、西、南三區(qū)建立門市部，假設(shè)三個區(qū)共有7個位置點Ai (i=1,2,7)可供選擇，且規(guī)定：東區(qū)只能在A1,A2,A3中至多選兩個點；西區(qū)只能在A4,A5兩個點中至少選一個點；南區(qū)只能在A6,A7中至少選一個點。 如選用Ai，設(shè)備投資估計為bi元，每年可獲利潤估計為ci元，問在投資不得超過b元的條件下，怎樣選址可使公司年利潤最大？ 假設(shè)投資總額b為1000

25、萬元，設(shè)備投資估計bi與每項投資每年獲利ci,列于表3.3，試求最優(yōu)選址方案。表3.3 投資估計與年獲利估計i1234567bi/萬元15018030020030010080ci/萬元2546605355171611,(1,2,7).0,iiiiAAxiA）模型建立.決策變量:本問題的決策變量是確定是否選擇 點，設(shè)當 點被選用，當 點沒被選用71712345671,2,1,1,iiiiiiizzc xxbb xb xxxxxxx目標函數(shù)：問題是如何選址使年利潤最大，用 表示利潤，則目標函數(shù)為約束條件： 應(yīng)滿足選址限制及投資總額不超過 元的限制，因此有71711234567max,. .,2,1

26、,1,01,1,2,7iiiiiiizc xstb xbxxxxxxxxi建立數(shù)學模型為 或這是一個變量只能取0或1的整數(shù)規(guī)劃模型，是整數(shù)規(guī)劃中的特殊情形，稱之為0-1整數(shù)規(guī)劃模型。用Lindo軟件求解。4 動態(tài)規(guī)劃 前面介紹的各種規(guī)劃都是在決策條件下相對確定的，即系統(tǒng)處于某一確定階段時的最優(yōu)化決策方法。但在實際工作中，當對一個經(jīng)濟系統(tǒng)進行分析時，往往要求對系統(tǒng)在包括若干階段的整個過程進行最優(yōu)化決策(稱為多階段決策問題)。所謂多階段決策過程，是指這樣一類決策過程，由于它的特殊性，可以將該過程(一般是按時間或空間)劃分為若干個互相聯(lián)系的階段而在每個階段都需要做出決策，以使整個過程取得最優(yōu)的效益。

27、在多階段決策過程中，各個階段所采取的決策通常與時間有關(guān)，前一階段采取的決策如何，不但決定著該階段的效益，而且還直接影響到以后各階段的效益，可見它是一個動態(tài)的規(guī)劃問題，所以稱為動態(tài)規(guī)劃。當然動態(tài)規(guī)劃也可以用來處理本來與時間無關(guān)的靜態(tài)問題，這只需在靜態(tài)模型中人為地引進“時間”因素，并按時間分段將靜態(tài)問題轉(zhuǎn)化為動態(tài)模型，然后按動態(tài)規(guī)劃方法處理。 動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法。因而它不像線性規(guī)劃那樣有一個標準的數(shù)學表達式和明確定義的一種規(guī)則，而是必須對具體問題進行具體分析處理。因此，在學習時除了要對基本概念和方法正確理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)

28、造性的技巧去求解。例4.1 (最短路線問題)設(shè)在圖4.1中，A,Bi,Cj,Dp,E(i,j=1,2,3,p=1,2)代表城市，兩城市之間的連線代表道路，連線旁的數(shù)字代表道路的長度。求由城市A到城市E的最短路線。AB1B2B3C1C2C3D1D2E3541584644242697512 解此問題可以先求出一切可能的點A到點E的路線，求出各條路線的總長度，再比較它們的大小，選出其中的最小者即為所求。這種解法(窮舉法)想起來十分簡單，但真要實現(xiàn)它卻比較困難，特別是當城市和道路的數(shù)量較多時，窮舉法的計算量非常大，以致使大型計算機的計算也會失去實用價值。容易看出，在窮舉法中有許多計算是重復(fù)的，例如在計

29、算路線AB1C2D1E與路線AB1C2D2E的總長時，其中AB1C2的長度就要重復(fù)計算兩次。下面給出一種高效的計算方法。首先依照空間的自然順序，將該問題劃分為4個階段，并引入如下符號：kk 稱為階段變量，表示由某點到E點的階段數(shù)，可取1,2,3,4中任一數(shù).,.ijpSSA B CDE 稱為狀態(tài)變量，表示在任意階段所處的位置，可取中任意一點3212121( )()kuSSku BCBCBC 稱為決策變量，表示當狀態(tài)處于 且還有 個階段要走時，下一步所選取的點。例如，表示現(xiàn)在處于點，還有三個階段要走，下一步選取 ，即要走的路線。3222( )()kfSSkSEfBBBE稱為目標函數(shù)或指標函數(shù)，表

30、示現(xiàn)在處于狀態(tài) ，還有 個階段要走，由 到終點 的最短距離。例如表示現(xiàn)在處于點，還有3個 階段要走，由點到終點 的最短距離22( ,( )( )( ,)5kkd S uSSuSd A BAB 稱為報酬函數(shù)，表示從 到下一步所選的點的距離。例如表示 到的距離為5.4123313233131232333313233431( )(),()()( ,)()( ,)(), ( ,)()3(),5(),4()( )min 3(AEfABEBEBEfBfBfBAEd A BfBd A BfBd A BfBfBfBfBfAfB本題的目的是要求從始點 到終點 的最短距離。如果已知 到 ，到 和到 的最短距離和，

31、就容易求出點 到點 的最短距離。只要比較，即找出中的最小者，就可得出到的 最短距離3233),5(),4()fBfB313233212223312122322122233321222311(),(),()(),(),(),()min1(),5()()min8(),4(),6()()min4(),4(),2()(fBfBfBf Cf Cf CfBf Cf CfBf Cf Cf CfBf Cf Cf CDEf但是都是未知的，要得到它們，必須先求得然后再做比較，即依此類推，最后只要求出到 的最短距 離 112111212112)()()1,()2.,.:8Df Df Df DDDEAAEEABCDE

32、與即可。顯然有這樣，計算由點和開始，逐步遠離點最后推向點 于是得到了由 到的最短距離，同時也可以得到由任意一點到 得最短距離，相應(yīng)的最短路線也可以得出最短路線最短距離：例4.2 背包問題：一個旅行者需要某些物品。假設(shè)可以在4種物品中隨意挑選，且已知每件物品的重量及其效用，效用能夠用數(shù)量表示出來。又設(shè)旅行者背包最多只能裝10kg物品，相應(yīng)數(shù)據(jù)由表4-2給出。問如何選取裝入背包中的物品及件數(shù)，才可使總效用最大？表4-2 每件物品的相應(yīng)信息物品重量(kg)效用15262316329415 解： 這是一個整數(shù)規(guī)劃問題。然而由于該模型的特殊結(jié)構(gòu)，可以通過對問題的分析得出用動態(tài)規(guī)劃解此類問題的基本思想和基

33、本方法。類似于例4.1的做法，首先對某一物品求最優(yōu)。假設(shè)在背包中裝物品1，2，3的最優(yōu)件數(shù)已定，要決定如何裝物品4，使效用最大。對物品4求最優(yōu)時，其限裝數(shù)量應(yīng)是0到10之間的整數(shù)，記為s4(表示裝入物品4的重量，因為每件物品4的重量等于1kg),求得的最大效用是s4的函數(shù)f4(s4)，于是444444044*444()max55(4 1)(0,1,10)usfsusuuus s 其中表示第四種物品的件數(shù)。記 的最優(yōu)值為33333334433343,( ).2(42)ussf ssusssu第二步：考慮背包中裝有物品 和物品 ，裝入物品的件數(shù)為兩種物品的總限重為與 相應(yīng)的最大效用記為、 和 之間

34、存在下列關(guān)系 33333333344340 20/2333330/2*33334.1344( )max 9()max 95 max 95(2)5(0,1,10) (43)02usususf sufsusususssuuu類似于例，兩種物品 和 的最優(yōu)組合，對于相應(yīng)的物品 來說也是最優(yōu)的，于是得到關(guān)系式 其中表示取最大整數(shù)。記 的最優(yōu)值為 ，則22222222222232222233230 30/32220/30/32 3 42,().3(44)()max 16( )max 165 max 165(3)maxususususu sfsssufsuf sususu 第三步：考慮背包中裝有物品 ，

35、， ，裝入背包中的物品 的件數(shù)記為為物品的總限重，相應(yīng)的最大效用記為存在下列關(guān)系 22222*22225 5(0,1,10)(45)33usssssuuu 記 的最優(yōu)值為 ，故。111111111211111220 512110/5144( )5(46)( )max 26()max 26(5 ) (47)4ususussf sssuf sufsufsus最后，考慮背包中裝有 種物品。設(shè)裝有物品1的件數(shù)為種物品的總限重為 ，與 相應(yīng)的最大效用記為，類似地，有 因為 為 種物品的總限重，且假 設(shè)旅行者110,10,kgs 過的背包最多只能裝所以于是1112112010/5111021102*11(

36、10)max 2653105max265(105 )3105max503max53,52,52530453.uuusfusuuuuuuu對應(yīng)的 的最優(yōu)值。與 種物品的最優(yōu)組合相對應(yīng)，最大效用為*212*344*22344*123401,(46)3(44)0(42)10,3,1,1.4(,)(0,3,0,1)suuuussususu u u u下面求最優(yōu)組合表示背包中不裝入物品 由式、式、和式，以及，分別得出故背包中裝入的 種物品的最優(yōu)組合為例4.3 機器負荷分配問題：某種機器可在高低兩種負荷下進行生產(chǎn)，設(shè)機器在高負荷下的產(chǎn)量g與投入生產(chǎn)地機器數(shù)量x的關(guān)系為g=10 x，年完好率為a=0.75;

37、在低負荷下的產(chǎn)量h與投入生產(chǎn)地機器數(shù)量y的關(guān)系為h=8y,年完好率為b=0.9.假定開始生產(chǎn)時完好的機器數(shù)量s1=100,試制定一個5年計劃，確定每年年投入高低兩種負荷下生產(chǎn)地機器數(shù)量，使5年內(nèi)產(chǎn)品的總產(chǎn)量最大。1(1,2,3,4,5,6)10.750.9().()5kkkkkkkkkk kskkxksxsxfsks解：假設(shè)階段變量表示年度，狀態(tài)變量 表示 年初擁有的完好機器數(shù)，也就是第年末擁有的完好機器數(shù)，決策變量 表示第 年初投入高負荷生產(chǎn)的機器數(shù)，狀態(tài)轉(zhuǎn)移方程最優(yōu)指標函數(shù)表示第 年初從資源 出發(fā)到第年末的產(chǎn)量的最大值。555511()6655555665500*55555()max 10

38、8()()(5,1)()0()05()max108()()max28 ()10kkkkkkkkkkxDskkkkkxsxsfsxsxfskfsD sxxskf sxsxfsxsxsf ss 動態(tài)規(guī)劃的基本方程為 其中當時，有顯然，當時，的最大為 值 44444444544444444550444504444440440*44444440.750.9()()max108()()max108() 10 max108() 100.750.9()max0.517 ()(xsxsxsxsksxsxfsxsxf sxsxsxsxxsxxsfsxxsfs當時，由于是 的線性增函數(shù)，所以當時，44)17.5s

39、的最大值為33333343333333344033340330*333330.750.9()( )max108()()max108() 17.5 max 0.62523.75 0( )23.75xsxsxsksxsxf sxsxfsxsxsxsxf ss當時，有顯然，當時，的最大值為22222232222222233022230220*222220.750.9()()max108()( )max108()23.75 max 1.562529.375 0()29.375xsxsxsksxsxfsxsxf sxsxsxsxfss當時，有顯然，當時，的最大值11111121111111122011120110*111110.750.9()( )max108()()max108()29.375 max 2.40634.4375 0( )34.4375xsxsxsksxsxf sxsxfsxsxsxsxf ss當時，有于是，當時，的最大值為111*12344551*12111*2322100,5( )344