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

1、數(shù)學(xué)規(guī)劃模型 數(shù)學(xué)規(guī)劃模型是在實際問題的數(shù)學(xué)建模中應(yīng)用 最廣泛的模型之一，也是運籌學(xué)的一個重要分支。 在生產(chǎn)實踐中，經(jīng)常要制定使問題的某一項指標(biāo) “最優(yōu)”的方案，這里的最優(yōu)包括“最大”、“最 小”、“最多”、“最少”等。如：如何合理地分 配、使用有限的資源（人力、物力及資金等）以獲 得“最大收益”等諸如此類的問題，就是所謂數(shù)學(xué) 規(guī)劃問題，數(shù)學(xué)規(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)品 原料

2、甲產(chǎn) 品/t 乙產(chǎn) 品/t 現(xiàn)有 原料 總量 鋼材/t95360 電力/(kw.h)45200 工作日/個310300 單位產(chǎn)品的利潤/(萬元/t)712 試擬訂生產(chǎn)計劃，使該廠獲得利潤最大 12 12 12 12 12 12 712 max712, . .95360, 45200, xxz zxx zxx zxx stxx xx 解 設(shè)甲、乙兩種產(chǎn)品計劃生產(chǎn)量分別為 和 噸，利潤為 萬元 則 ， 我們的任務(wù)是求 的最大值，且 ， 受到鋼材的限制、電力的限制 工作日的限制、非負(fù)條件的限制等，可得線性規(guī)劃的數(shù)學(xué)模型 12 12 310300, 0,0 xx xx （1.1） ， 1212 12

3、(1.1)( ,)zf x xxx xx 式中，目標(biāo)函數(shù)是 和 的線性函數(shù)， 而約束條件是 和 的線性不等式，因此稱式(1.1) 為線性規(guī)劃模型。 線性規(guī)劃模型的解法 兩個變量的線性規(guī)劃模型的圖解法 單純形法 數(shù)學(xué)軟件，如Lindo軟件、Lingo軟件、 Matlab等 例1.2 投資方案的確定 某部門要進行投資，現(xiàn)有四個投資項目。 項目A：從第一年到第四年的每年年初需要投資，并 于次年年末回收本利115；項目B：從第三年年初需 要投資，到第五年年末回收本利125%，但規(guī)定最大 投資額不超過40萬元；項目C：第二年初需要投資， 到第五年末才能回收本利140%，但規(guī)定最大投資額 部超過30萬元；

4、項目D：五年內(nèi)每年的年初可買公債， 于當(dāng)年年末歸還，并可獲得6%的利息。 已知該部門現(xiàn)有資金100萬元，試為該部門確定投資 方案，使得第五年末它擁有的資金本利總額最大？ 1）模型建立。 決策變量。決策變量為每年年初向四個項目的投資 額，設(shè)第i(i=1,2,3,4,5)年年初向A,B,C,D(j=1,2,3,4) 四個項目的投資額為xij（萬元）。 目標(biāo)函數(shù)。設(shè)第五年年末擁有的資金本利總額為z， 為了方便，將所有可能的投資列于下表1.2 年份 項目 12345 投資限額/萬 元 Ax11x21x31x41 Bx3240 Cx2330 Dx14x24x34x44x54 41322354 1.151

5、.251.401.06zxxxx 目標(biāo)函數(shù)應(yīng)該是四項投資在第五年年末回收的本利之和，于是， 目標(biāo)函數(shù)為 約束條件 a為了獲得最大的投資收益，每年年初應(yīng)將手頭的全 部資金投出去，因此第一年的投資總額應(yīng)是100萬元， 即x11+x14=100 b第二年的投資總額應(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. 322 41322354 1114 212

6、32414 3132342411 41443421 54 .40,30. max1.151.251.401.06, . .100 1.06, 1.061.15, 1.061.15, cxx zxxxx stxx xxxx xxxxx xxxx x 由于投資的限制，因此還有 由此得投資問題的數(shù)學(xué)模型為 4431 3223 1.061.15, 40,30, 0,1,5;1,4 ij xx xx xij 2）模型求解。用Lindo軟件求解，求得 投資方案的最優(yōu)解為 x11=71.698112萬元， x14=28.301888萬元， x23=30萬元， x32=40萬元， x34=42.452831萬

7、元， x41=45萬元， 其余決策變量均為零，最優(yōu)值z=143.75萬元。 例1.3 貨機裝運。 某貨機有三個貨艙：前艙、中艙、后艙。三個貨艙 所能裝載的貨物的最大重量和體積都要限制，如表 1.3所示。并且，為了保持飛機的平衡，三個貨艙中 實際裝載貨物的重量必須與其最大容許重量成比例。 表1.3 三個貨艙裝載貨物的最大容許量和體積 前艙中艙后艙 重量限制/t10168 體積限制/m3680087005300 現(xiàn)有四類貨物供該貨機本次飛行裝運，其有關(guān)信息 如表1.4，最后一列指裝運后獲得的利潤。 表1.4 四類裝運貨物的信息 質(zhì)量/t空間/(m3/t)利潤(元/t) 貨物1184803100 貨

8、物2156503800 貨物3235803500 貨物4123902850 應(yīng)如何安排裝運，使該貨機本次飛行利潤最大？ 1）模型假設(shè)。問題中沒有對貨物裝運提出其他要 求，我們可做如下假設(shè)： 每種貨物可以分割到任意??； 每種貨物可以在一個或多個貨艙中任意分布； 多種貨物可以混裝，并保證不留空隙。 2）模型建立。 決策變量：用xij表示第i種貨物裝入第j個貨艙的重 量（噸），貨艙j=1,2,3分別表示前艙、中艙、后艙。 目標(biāo)函數(shù)：決策目標(biāo)是最大化總利潤，即目標(biāo)函數(shù)為 111213212223 313233414243 3100()3800() 3500()2850(). zxxxxxx xxxxx

9、x 約束條件：約束條件包括以下4個方面： 111213 212223 313233 414243 11213141 12223242 13233343 . 18, 15, 23, 12; 10, 16, 8; a xxx xxx xxx xxx xxxx xxxx xxxx 供裝載的四種貨物的總重量約束，即 b.三個貨艙的重量限制，即 11213141 12223242 13233343 1121314112223242 13233343 . 4806505803906800, 4806505803908700, 4806505803905300; . 1016 . 8 c xxxx xxxx

10、 xxxx d xxxxxxxx xxxx 三個貨艙的空間限制 三個貨艙裝入重量的平衡約束，即 3）模型求解。將以上模型輸入Lindo 模型， 可以得到結(jié)果：最優(yōu)解為 x21=10t,x23=5t,x32=12.947t,x33=3t,x42=3.053t, 其余變量均為零，最優(yōu)值z=121515.8t 2.非線性規(guī)劃模型 非線性規(guī)劃問題可以看作是線性規(guī)劃問題的 一種自然推廣，亦是數(shù)學(xué)規(guī)劃的一個重要組成部 分。凡目標(biāo)函數(shù)和約束條件中包含有非線性函數(shù) 的數(shù)學(xué)規(guī)劃問題都稱為非線性規(guī)劃問題。較之線 性規(guī)劃模型而言，非線性規(guī)劃模型更能真實地反 映問題的實質(zhì)。 例2.1 設(shè)用甲、乙、丙三種有限資源生產(chǎn)A

11、,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)量，以便使 總收益最大。 1234 12341 1223344 1122 3344 12 , , ( ,) (11 0.01 )(120.02) (130.03)(140.04) (1

12、1121 A B C Dx xxx z x xx xp xp xp xp x xxxx xxxx xx 解 設(shè)四種產(chǎn)品的產(chǎn)量分別為 , 和 ，則問題的 目標(biāo)函數(shù)（總收益函數(shù)） 34 2222 1234 314) (0.010.020.030.04) xx xxxx 其中，第一項是不變價格下的總收益，第二項是需要扣除的 因價格變動造成的收益值，注意到資源的約束，上述問題可表為 1234 2222 1234 1234 1234 134 max(11121314) (0.010.020.030.04), . .232200 798300 37400, 0,1,2,3,4 j zxxxx xxxx s

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

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

15、 ,0 zx xxx x stx x x xx x 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è)時間/h 0.5 2+0.25x2 3 整數(shù)規(guī)劃模型 在一個數(shù)學(xué)規(guī)劃模型中，如果它的某些決策變量或 全部變量要求取整數(shù)時，就稱這個數(shù)學(xué)規(guī)劃模型為整

16、 數(shù)規(guī)劃模型。整數(shù)規(guī)劃模型可分為整數(shù)線性規(guī)劃模型 與整數(shù)非線性規(guī)劃模型。整數(shù)規(guī)劃又分為整數(shù)規(guī)劃、 混合整數(shù)規(guī)劃及0-1規(guī)劃。 整數(shù)規(guī)劃模型的一般形式 12 12 min( ,), . .( ,)0,1,2, 0,1,2, , ,1,2, . n in j j f x xx sth x xxim xjn xjn 為整數(shù) 12 12 (1,2,), (1,2,), (1,2, ) in in j fh imx xx fh imx xx xjn 當(dāng) 和均是的線性函數(shù)時, 我們稱模型為整數(shù)線性規(guī)劃模型； 當(dāng) 和中至少有一個是的 非線性函數(shù)時，稱模型為整數(shù)非線性規(guī)劃模型。 若整數(shù)規(guī)劃模型中的決策變量只能

17、 取0或1，則稱模型為0-1規(guī)劃. 例3.1 某航空公司為滿足客運量日益增長的需要，欲購 置一批新的遠程及短程客機。每架客機價格6300萬元， 中程客機5000萬元，短程客機3500萬元。該公司現(xiàn)有 資金7.5億元可用于購買飛機。估計年凈利潤每架遠程 客機為420萬元，中程客機300萬元，短程客機230萬 元。該公司現(xiàn)有熟練駕駛員可用來配備30架新飛機。 維修設(shè)備足以維修新增加40架新的短程客機，每架中 程客機的維修量相當(dāng)于4/3架短程客機，而每架遠程客 機的維修量相當(dāng)于5/3架短程客機。為獲取最大利潤， 該公司應(yīng)購買各類客機多少架？ 12 3 123 123 123 123 123 123

18、max420300230, . . 63005000350075000, 30, 54 40, 33 ,0, , xx x zxxx stxxx xxx xxx x x x x x x 解 設(shè)購買遠程、中程、短程客機的數(shù)量分別為 、 和 架，問題的數(shù)學(xué)模型為 均為整數(shù)。 用Lindo軟件求解 例3.2 合理下料問題 某鋼管零售商從鋼管廠家進貨，將鋼管按照顧客的要求 切割后售出，從鋼管廠進貨時得到的原料鋼管都是19m. 1）現(xiàn)有一客戶需要50根4m、20根6m和15根8m的鋼 管，應(yīng)如何下料最節(jié)??？ 1）問題的分析。 首先，應(yīng)當(dāng)確定哪些切割模式是可行的。所謂一個 切割模式，是指按照客戶需要在原料

19、上安排切割的一 種組合。例如：我們可以將19m的鋼管切割成3根4m的 鋼管，余料為7m；或者將19m的鋼管切割成4m、6m 和8m的鋼管各1根，余料為1m。顯然，可行的切割模 式是很多的。 其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通 常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或 等于客戶需要的鋼管的最小此寸。例如：將19m 的鋼管切割成3根4m的鋼管是可行的，但余料為 7m，可以進一步將7m的余料切割成4m鋼管 （余料為3m），或者將7m的余料切割為6m鋼 管（余料為1m）。在這種合理性假設(shè)下，切割 模式一共有7種，如表3.1所示 表3.1 鋼管下料的合理切割模式 4m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根

20、數(shù)余料m 模式14003 模式23101 模式32013 模式41203 模式51111 模式60301 模式70023 問題化為在滿足客戶需要的條件下，按照哪些合理的模式， 切割多少根原料鋼管最為節(jié)省。而所謂最為節(jié)省，可以有 兩種標(biāo)準(zhǔn)：一是切割后剩余的總余料量最小，二是切割原 料鋼管的總根數(shù)最少。下面將對這兩個目標(biāo)分別討論。 2）模型建立。 決策變量：用表示按第種模式切割的原料鋼管的根 數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。 目標(biāo)函數(shù)：以切割后剩余的總余料量最少為目標(biāo)， 則由表3.1可得 z1=3x1+x2+3x3+3x4+x5+x6+3x7 以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有 z2=x1+x2+

21、x3+x4+x5+x6+x7 下面分別在這兩種目標(biāo)下求解。 12345 2456 357 3.1 43250, 2320, 215. xxxxx xxxx xxx 約束條件：為滿足客戶的需求，按照表應(yīng)有 3）模型求解 分別將目標(biāo)函數(shù)與約束條件構(gòu)成整數(shù)線性規(guī)劃模型 輸入Lindo求解。 2）該客戶除需要1）中的三種鋼管外還需要10根5m 的鋼管。應(yīng)如何下料最節(jié)??？ 1）問題分析。按照問題1）的思路，可以通過枚舉法首 先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格 增加到4種，所以枚舉法的工作量較大。下面介紹的整數(shù) 非線性規(guī)劃模型，可以同時確定切割模式和切割計劃， 是帶有普遍性的方法。 同問題1

22、）類似，一個合理的切割模式的余料不應(yīng)該 大于和等于客戶需要的鋼管的最小尺寸(本題中為4m)， 切割計劃中只使用合理的切割模式，而由于本題中的參 數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3m。 此外，這里我們僅選擇總根數(shù)最少為目標(biāo)進行求解。 2）模型建立。 決策變量：由于不同切割模式不能超過3種，可以用xi 表示按照第i種模式(i=1,2,3)切割的原料鋼管的根數(shù)，顯 然它們應(yīng)當(dāng)是非負(fù)整數(shù)。設(shè)所使用的第i種切割模式下 每根原料鋼管生產(chǎn)4m,5m,6m和8m的鋼管數(shù)量分別為 r1i,r2i,r3i和r4i(均為非負(fù)整數(shù))。 123 11 1122133 21 1222233 31 132233

23、3 41 1422433 . 50, 10, 20, 15. zxxx r xr xr x r xr xr x r xr xr x r xr xr x 目標(biāo)函數(shù)：切割原料鋼管總根數(shù)最少，目標(biāo)函數(shù)為 約束條件：為滿足客戶的需求，應(yīng)有 11213141 12223242 13233343 19 16456819, 16456819, 16456819. m rrrr rrrr rrrr 每一種切割模式必須可行、合理，所以每根原料鋼管的 成品量不能超過，也能少于16m(余量不能大于3m)， 于是 3)模型求解。 以上模型是一個整數(shù)非線性規(guī)劃模型，我們用Lingo軟 件求解。 0-1整數(shù)規(guī)劃模型 例3

24、.3 指派問題。 在實際工作中，常常會碰到這樣的問題：要派n個人去 完成n項不同的任務(wù)，每人必須而且只需完成其中一項。 但由于各人的專長不同，完成各項任務(wù)的效率也就不同， 因此就產(chǎn)生這樣一個問題，應(yīng)指派哪個人去完成哪項任 務(wù)，使總的效率最高或總的花費時間最少？今欲指派甲、 乙、丙、丁四人加工A、B、C、D四種不同零件，每人 加工四種零件分別所需要的時間如表3.2所示。問應(yīng)該 指派每人加工何種零件使總的花費時間最少？ 表3.2 工人加工零件的工作效率 ABCD 甲4658 乙61074 丙78119 丁9386 1 1, 0, ij ij x ij ）模型建立. 決策變量：設(shè)表示第個人去加工零件

25、的情況，即 當(dāng)指派第 人去加工 零件時， 當(dāng)不指派第 人去加工 零件時， 1112131421222324 3132333441424344 465861074 781199386 z zxxxxxxxx xxxxxxxx 目標(biāo)函數(shù)：問題使總的花費時間最少，用 表示 總的花費時間，則目標(biāo)函數(shù)為 11121314 21222324 31323334 41424344 1, 1, 1, 1. xxxx xxxx xxxx xxxx 約束條件：由于每人只能加工一種零件，則有 11213141 12223242 13233343 14243444 1, 1, 1, 1. xxxx xxxx xxxx

26、xxxx 而每種零件必有一個人來加工，則有 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萬元，設(shè)備投資估計bi與 每項投資每年獲利ci,列于表3.3，試求最

27、優(yōu)選址方案。 表3.3 投資估計與年獲利估計 i1234567 bi/萬元15018030020030010080 ci/萬元25466053551716 1 1, (1,2,7). 0, i i i i A A xi A ）模型建立. 決策變量:本問題的決策變量是確定是否選擇 點，設(shè) 當(dāng) 點被選用， 當(dāng) 點沒被選用 7 1 7 1234567 1 ,2,1,1, ii i i ii i z zc x xb b xb xxxxxxx 目標(biāo)函數(shù)：問題是如何選址使年利潤最大，用 表示 利潤，則目標(biāo)函數(shù)為 約束條件： 應(yīng)滿足選址限制及投資總額不超過 元的 限制，因此有 7 1 7 1 123 45

28、67 max, . ., 2, 1, 1, 01,1,2,7 ii i ii i i zc x stb xb xxx xx xx xi 建立數(shù)學(xué)模型為 或 這是一個變量只能取0或1的整數(shù)規(guī)劃模型，是整數(shù)規(guī) 劃中的特殊情形，稱之為0-1整數(shù)規(guī)劃模型。用Lindo軟 件求解。 4 動態(tài)規(guī)劃 前面介紹的各種規(guī)劃都是在決策條件下相對確 定的，即系統(tǒng)處于某一確定階段時的最優(yōu)化決策方 法。但在實際工作中，當(dāng)對一個經(jīng)濟系統(tǒng)進行分析 時，往往要求對系統(tǒng)在包括若干階段的整個過程進 行最優(yōu)化決策(稱為多階段決策問題)。所謂多階段 決策過程，是指這樣一類決策過程，由于它的特殊 性，可以將該過程(一般是按時間或空間)

29、劃分為若 干個互相聯(lián)系的階段而在每個階段都需要做出決策， 以使整個過程取得最優(yōu)的效益。在多階段決策過程 中，各個階段所采取的決策通常與時間有關(guān)， 前一階段采取的決策如何，不但決定著該階段的效益， 而且還直接影響到以后各階段的效益，可見它是一個 動態(tài)的規(guī)劃問題，所以稱為動態(tài)規(guī)劃。當(dāng)然動態(tài)規(guī)劃 也可以用來處理本來與時間無關(guān)的靜態(tài)問題，這只需 在靜態(tài)模型中人為地引進“時間”因素，并按時間分 段將靜態(tài)問題轉(zhuǎn)化為動態(tài)模型，然后按動態(tài)規(guī)劃方法 處理。 動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題 的一種途徑，而不是一種特殊算法。因而它不像線性 規(guī)劃那樣有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達式和明確定義的一種 規(guī)則，而是必須

30、對具體問題進行具體分析處理。因此， 在學(xué)習(xí)時除了要對基本概念和方法正確理解外，應(yīng)以 豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。 例4.1 (最短路線問題) 設(shè)在圖4.1中，A,Bi,Cj,Dp,E(i,j=1,2,3,p=1,2)代表城市， 兩城市之間的連線代表道路，連線旁的數(shù)字代表道路的 長度。求由城市A到城市E的最短路線。 A B1 B2 B3 C1 C2 C3 D1 D2 E 3 5 4 1 5 8 4 6 4 4 2 4 2 6 9 7 5 1 2 解此問題可以先求出一切可能的點A到點E的路線， 求出各條路線的總長度，再比較它們的大小，選出其 中的最小者即為所求。這種解法(窮舉法)

31、想起來十分 簡單，但真要實現(xiàn)它卻比較困難，特別是當(dāng)城市和道 路的數(shù)量較多時，窮舉法的計算量非常大，以致使大 型計算機的計算也會失去實用價值。 容易看出，在窮舉法中有許多計算是重復(fù)的，例如在 計算路線AB1C2D1E與路線AB1C2D2E的總長時，其中 AB1C2的長度就要重復(fù)計算兩次。下面給出一種高效 的計算方法。首先依照空間的自然順序，將該問題劃 分為4個階段，并引入如下符號： kk 稱為階段變量，表示由某點到E點的階段數(shù)， 可取1,2,3,4中任一數(shù). ,. ijp SS A B CDE 稱為狀態(tài)變量，表示在任意階段所處的位置， 可取中任意一點 321 21 21 ( ) () k uSS

32、k u BC BC BC 稱為決策變量，表示當(dāng)狀態(tài)處于 且還有 個 階段要走時，下一步所選取的點。例如，表 示現(xiàn)在處于點，還有三個階段要走，下一步選取 ， 即要走的路線。 322 2 ( ) () k fS SkSE fBB BE 稱為目標(biāo)函數(shù)或指標(biāo)函數(shù)，表示現(xiàn)在處于狀 態(tài) ，還有 個階段要走，由 到終點 的最短距離。例 如表示現(xiàn)在處于點，還有3個 階段要走，由 點到終點 的最短距離 22 ( ,( ) ( )( ,)5 k k d S uSS uSd A BAB 稱為報酬函數(shù)，表示從 到下一步所選 的點的距離。例如表示 到的距離為5. 412331 3233 131232333 313233

33、 431 ( )(), ()() ( ,)()( ,)(), ( ,)() 3(),5(),4() ( )min 3( AE fABEBEBEfB fBfBAE d A BfBd A BfBd A BfB fBfBfB fAfB 本題的目的是要求從始點 到終點 的最短距離 。如果已知 到 ，到 和到 的最短距離 和，就容易求出點 到點 的最短距離。只要 比較， 即找出中的最小者，就可 得出到的 最短距離 3233 ),5(),4()fBfB 313233 212223 312122 32212223 33212223 11 (),(),() (),(),(), ()min1(),5() ()m

34、in8(),4(),6() ()min4(),4(),2() ( fBfBfB f Cf Cf C fBf Cf C fBf Cf Cf C fBf Cf Cf C DEf 但是都是未知的，要得到它們， 必須先求得然后再做比較，即 依此類推，最后只要求出到 的最短距 離 112 11121 2 112 )() ()1,()2. ,. :8 Df D f Df DD DEAAE E ABCDE 與 即可。顯然有這樣，計算由點和 開始，逐步遠離點最后推向點 于是得到了由 到 的最短距離，同時也可以得到由任意一點到 得最短距 離，相應(yīng)的最短路線也可以得出 最短路線最短距離： 例4.2 背包問題：一個

35、旅行者需要某些物品。假設(shè)可以 在4種物品中隨意挑選，且已知每件物品的重量及其效 用，效用能夠用數(shù)量表示出來。又設(shè)旅行者背包最多只 能裝10kg物品，相應(yīng)數(shù)據(jù)由表4-2給出。問如何選取裝 入背包中的物品及件數(shù)，才可使總效用最大？ 表4-2 每件物品的相應(yīng)信息 物品重量(kg)效用 1526 2316 329 415 解： 這是一個整數(shù)規(guī)劃問題。然而由于該模型的 特殊結(jié)構(gòu)，可以通過對問題的分析得出用動態(tài)規(guī)劃解 此類問題的基本思想和基本方法。類似于例4.1的做 法，首先對某一物品求最優(yōu)。假設(shè)在背包中裝物品1， 2，3的最優(yōu)件數(shù)已定，要決定如何裝物品4，使效用 最大。對物品4求最優(yōu)時，其限裝數(shù)量應(yīng)是0

36、到10之間 的整數(shù)，記為s4(表示裝入物品4的重量，因為每件物 品4的重量等于1kg),求得的最大效用是s4的函數(shù)f4(s4)， 于是 44 4444 0 44 * 444 ()max55(4 1) (0,1,10) us fsus uu us s 其中表示第四種物品的件數(shù)。記 的最優(yōu)值 為 333 33334 433 34 3, ( ). 2(42) uss f ssus ssu 第二步：考慮背包中裝有物品 和物品 ，裝入物品 的件數(shù)為兩種物品的總限重為與 相應(yīng)的最大效 用記為、 和 之間存在下列關(guān)系 3333 33 3334434 0 20/2 33333 0/2 * 3 333 4.13

37、4 4 ( )max 9()max 95 max 95(2)5(0,1,10) (43) 0 2 usus us f sufsus ususs s uuu 類似于例，兩種物品 和 的最優(yōu)組合，對于相應(yīng)的物 品 來說也是最優(yōu)的，于是得到關(guān)系式 其中表示取最大整數(shù)。記 的最優(yōu)值為 ，則 2222 2222 22 22 322 2223323 0 30/3 222 0/30/3 2 3 4 2, (). 3(44) ()max 16( )max 165 max 165(3)max usus usus u s fs ssu fsuf sus usu 第三步：考慮背包中裝有物品 ， ， ，裝入背包中 的

38、物品 的件數(shù)記為為物品的總限重，相應(yīng)的最大 效用記為存在下列關(guān)系 22 2 22 * 2 222 5 5(0,1,10)(45) 3 3 us s ss s uuu 記 的最優(yōu)值為 ，故。 11 11 111 11 211 11122 0 5 1211 0/5 1 4 4 ( ) 5(46) ( )max 26() max 26(5 ) (47) 4 us us uss f s ssu f sufs ufsu s 最后，考慮背包中裝有 種物品。設(shè)裝有物品1的 件數(shù)為種物品的總限重為 ，與 相應(yīng)的最大效用 記為，類似地，有 因為 為 種物品的總限重，且假 設(shè)旅行者 1 10,10,kgs 過的背

39、包最多 只能裝所以于是 1 1 1 2 112 010/5 1 11 02 1 1 02 * 11 (10)max 265 3 105 max265(105 ) 3 105 max50 3 max53,52,5253 04 53. u u u s fus u uu u u uu 對應(yīng)的 的最優(yōu)值。與 種物品的最優(yōu)組合 相對應(yīng)，最大效用為 * 2 12 * 344 * 22344 * 1234 01,(46) 3 (44)0(42) 10,3,1,1. 4 (,)(0,3,0,1) s uu uus susus u u u u 下面求最優(yōu)組合 表示背包中不裝入物品 由式、 式、和式，以及，分別得

40、出 故背包中裝入的 種物品的最優(yōu)組合為 例4.3 機器負(fù)荷分配問題：某種機器可在高低兩種負(fù)荷 下進行生產(chǎn)，設(shè)機器在高負(fù)荷下的產(chǎn)量g與投入生產(chǎn)地 機器數(shù)量x的關(guān)系為g=10 x，年完好率為a=0.75;在低負(fù) 荷下的產(chǎn)量h與投入生產(chǎn)地機器數(shù)量y的關(guān)系為h=8y,年 完好率為b=0.9.假定開始生產(chǎn)時完好的機器數(shù)量s1=100, 試制定一個5年計劃，確定每年年投入高低兩種負(fù)荷下 生產(chǎn)地機器數(shù)量，使5年內(nèi)產(chǎn)品的總產(chǎn)量最大。 1 (1,2,3,4,5,6) 1 0.750.9( ).() 5 k k kkk kkkk k k skk xk sxs xfsks 解：假設(shè)階段變量表示年度，狀態(tài)變 量 表示

41、 年初擁有的完好機器數(shù)，也就是第年末 擁有的完好機器數(shù)，決策變量 表示第 年初投入高負(fù) 荷生產(chǎn)的機器數(shù)，狀態(tài)轉(zhuǎn)移方程 最優(yōu)指標(biāo)函數(shù)表示第 年初從資源 出發(fā)到第 年末的產(chǎn)量的最大值。 5555 11 () 66 555556655 00 * 55555 ()max 108()()(5,1) ()0 ()0 5 ()max108()()max28 ()10 kkk kkkkkkk xDs kkkkk xsxs fsxsxfsk fs D sxxs k f sxsxfsxs xsf ss 動態(tài)規(guī)劃的基本方程為 其中 當(dāng)時，有 顯然，當(dāng)時，的最大為 值 44 44 44 44 5444 4444455

42、 0 4445 0 444444 0 44 0 * 44444 4 4 0.750.9() ()max108()() max108() 10 max108() 100.750.9() max0.517 () ( xs xs xs xs k sxsx fsxsxf s xsxs xsxxsx xs fsxxs fs 當(dāng)時， 由于是 的線性增函數(shù)，所以當(dāng)時， 44 )17.5s的最大值為 33 33 33 4333 3333344 0 3334 0 33 0 * 3333 3 0.750.9() ( )max108()() max108() 17.5 max 0.62523.75 0( )23.7

43、5 xs xs xs k sxsx f sxsxfs xsxs xs xf ss 當(dāng)時，有 顯然，當(dāng)時，的最大值為 22 22 22 3222 2222233 0 2223 0 22 0 * 2222 2 0.750.9() ()max108()( ) max108()23.75 max 1.562529.375 0()29.375 xs xs xs k sxsx fsxsxf s xsxs xs xfss 當(dāng)時，有 顯然，當(dāng)時，的最大值 11 11 11 2111 1111122 0 1112 0 11 0 * 1111 1 0.750.9() ( )max108()() max108()29.375 max 2.40634.4375 0( )34.4375 xs xs xs k sxsx f sxsxfs xsxs xs xf ss 當(dāng)時，有 于是，當(dāng)時，的最大值為 111 * 1234455 1 * 12111 * 2322 100,5( )3443.75 0, 100 0,0.750.