運籌與優(yōu)化模型課件

1例1、某工廠制造A.B兩種產(chǎn)品，制造A每噸需用煤9t，電力4kw，3個工作日；制造B每噸需用煤5t，電力5kw，10個工作日。已知制造產(chǎn)品A和B每噸分別獲利7000元和12000元，現(xiàn)工廠只有煤360t，電力200kw，工作日300個可以利用，問

A、B兩種產(chǎn)品各應(yīng)生產(chǎn)多少噸才能獲利最大？解：設(shè)

,（單位為噸）分別表示A、B產(chǎn)品的計劃生產(chǎn)數(shù)；f表示利潤（單位千元）則問題歸結(jié)為如下線性規(guī)劃問題：2目標(biāo)函數(shù)約束條件其中(,)為決策向量，滿足約束條件的(,)稱為可行決策。線性規(guī)劃問題就是指目標(biāo)函數(shù)為諸決策變量的線性函數(shù)，給定的條件可用諸決策變量的線性等式或不等式表示的決策問題。線性規(guī)劃求解的有效方法是單純形法（進(jìn)一步了解可參考有關(guān)書籍），當(dāng)然簡單的問題也可用圖解法。如用圖解法求解例1：由約束條件決定的可行域如圖陰影所示，目標(biāo)函數(shù)的等值線向右上方移動時其值增大，在到達(dá)點 時f取得最大值；3當(dāng)

=20, =24時，即產(chǎn)品A生產(chǎn)20t，產(chǎn)品B生產(chǎn)24t時，生產(chǎn)方案最優(yōu)。其最大利潤為：7×20＋12×24＝428千元例2：某兩個煤廠

.

，每月進(jìn)煤數(shù)量分別為60t和100t聯(lián)合供應(yīng)3個居民區(qū) 。3個居民區(qū)每月對煤的需求量依次分別為50t,70t,40t，煤廠 離3個居民區(qū) 的距離依次為10km,5km,6km，煤廠 離3個居民區(qū)

的距離依次分別為4km,8km,12km，問如何分配供煤量使得運輸費（即t·km）達(dá)到最小？4解：設(shè) 表示

(i=1.2)煤廠提供給

（j=1.2.3)居民區(qū)的煤量；f表示總運輸費此問題歸結(jié)為：5一般線性規(guī)劃問題的數(shù)學(xué)表達(dá)式：s.t6例3：生產(chǎn)組織與計劃問題設(shè)有m種資源，第i(i=1,2…,m)種資源的現(xiàn)存量為，現(xiàn)要生產(chǎn)n種產(chǎn)品，已知生產(chǎn)j(j=1,2…,n)種產(chǎn)品時，每單位產(chǎn)品需要第i種資源量為，而每單位j種產(chǎn)品可得利潤，問如何組織生產(chǎn)才能使利潤最大？解：用 表示生產(chǎn)第j(j=1,2,…,n)種產(chǎn)品的計劃數(shù)，上述問題可歸結(jié)為如下的數(shù)學(xué)問題：7二、整數(shù)規(guī)劃模型對于線性規(guī)劃：決策變量是連續(xù)變量，最優(yōu)解可能是小數(shù)或分?jǐn)?shù)。8但是在許多實際問題中，往往要求所得的解為整數(shù)，例如投資項目的選擇、機(jī)器的臺數(shù)、完成工作的人數(shù)、裝貨的車數(shù)等，分?jǐn)?shù)和小數(shù)的答案就沒有現(xiàn)實意義了。在現(xiàn)性規(guī)劃中，若限制

(j=1,2,…,n)是非負(fù)整數(shù)，則這種線性規(guī)劃問題稱為整數(shù)規(guī)劃問題。9例4：分配問題假設(shè)某工廠用m臺機(jī)床加工n種零件。在一個生產(chǎn)周期內(nèi)，第i(i=1,2,…,m)臺機(jī)床只能工作 個機(jī)時，而第j(j=1,2,…,n)種零件必須完成 個，又第i臺機(jī)床加工第j種零件所需機(jī)時和成本分別為 （機(jī)時／個）和

（元／個）。問在這個生產(chǎn)周期內(nèi)怎樣安排各機(jī)床的生產(chǎn)任務(wù)，才能使得既完成加工任務(wù)，又使總的加工成本最少？解：在一個生產(chǎn)周期內(nèi)，假設(shè)第i臺機(jī)床加工第j種零件的個數(shù)為

。由于 是零件個數(shù)，因此必須是非負(fù)整數(shù)，10本問題的數(shù)學(xué)模型為：11三、非線性規(guī)劃模型非線性規(guī)劃模型的一般形式為：f(X)為目標(biāo)函數(shù)，(2)、(3)為約束條件，

(2)為不等式約束，(3)為等式約束；

若只有(1)稱為無約束問題。1213例5：容器的設(shè)計問題某公司專門生產(chǎn)儲藏用容器，定貨合同要求該公司制造一種敞口的長方體容器，容積恰好為12立方

米，該容器的底必須為正方形，容器總重量不超過68公斤。已知用作容器四壁的材料為每平方米10

元，重3公斤；用作容器底的材料每平方米20元，重2公斤。試問制造該容器所需的最小費用是多少？模型建立 設(shè)該容器底邊長和高分別為 米、 米，則問題的數(shù)學(xué)模型為（容器的費用）14一般來說，非線性規(guī)劃模型的求解要比線性規(guī)劃模型求解困難得多，雖然現(xiàn)在已經(jīng)發(fā)展了許多非線性規(guī)劃的算法，但到目前為止，還不象線性規(guī)劃那樣有通用的單純形算法，而是各種算法都有自己特定的適用范圍，如求解法有：最速下降法、牛頓法、可行方向法、懲罰函數(shù)法等。盡管如此，非線性規(guī)劃的實際應(yīng)用還是相當(dāng)廣泛的。155.2

實際問題中的優(yōu)化模型16一、投資策略某部門現(xiàn)有資金10萬元，五年內(nèi)有以下投資項目供選擇：項目A,從第一年到第四年每年初投資，次年末收回本金且獲利15%；項目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元；項目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元；項目D，每年初投資，年末收回本金且獲利6%。問如何確定投資策略使第五年末本息總額最大。問題的目標(biāo)函數(shù)是第五年末的本息總額，決策變量是每年初各個項目的投資額，約束條件是每年初擁有的資金。用 表示第 年初（ ）項目分別代表A,B,C,D)的投資額，根據(jù)所給條件只有下表1列出的才是需要求解的。項目A

BCD年份1234517項目A,從第一年到第四年每年初投資，次年末收回本金且獲利15%；項目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元；項目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元；項目D，每年初投資，年末收回本金且獲利6%。因為項目D每年初可以投資，且年末能收回本息，所以每年初都應(yīng)把資金全部投出去，由此可得如下的約束條件：第一年初：第二年初：第三年初

第四年初：第五年初：項目B,C對投資額的限制：18項目A,從第一年到第四年每年初投資，次年末收回本金且獲利15%；項目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元；項目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元；項目D，每年初投資，年末收回本金且獲利6%。每項投資應(yīng)為非負(fù)的：第五年末本息總額為19由此得投資問題的線性規(guī)劃模型如下：s.t.2021求解得即第1年項目A,D分別投資3.8268和6.1732(萬元)；第2年項目A,C分別投資3.5436和3(萬元)；第3年項目A,B分別投資0.4008和4(萬元)；第4年項目A投資4.0752(萬元)；第5年項目D投資0.4609(萬元)；5年后總資金14。375萬元，即盈利43.75%.二、貨機(jī)裝運22問題 某架貨機(jī)有三個貨艙：前倉、中倉、后倉。三個貨艙所能裝載的貨物的最大重量和體積都有限制，如表3所示。并且，為了保持飛機(jī)的平衡，三個貨艙中實際裝載貨物的重量必須與其最大容許重量成比例。前倉中倉后倉重量限制（噸）10168體積限制（米3）680087005300現(xiàn)有四類貨物供該貨機(jī)本次飛行裝運，其有關(guān)信息如表4，最后一列指裝運后所獲得的利潤。重量（噸）空間（米3/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物412390285023應(yīng)如何安排裝運，使該貨機(jī)本次飛行獲利最大？模型假設(shè)問題中沒有對貨物裝運提出其它要求，我們可作如下假設(shè)：每種貨物可以分割到任意?。幻糠N貨物可以在一個或多個貨艙中任意分布；3）多種貨物可以混裝，并保證不留空隙。模型建立決策變量：表示第i種貨物裝入第j個貨艙的重量（噸），貨艙j=1,2,3分別表示前倉、中倉、后倉。決策目標(biāo)是最大化總利潤，即約束條件包括以下4個方面：1）從裝載的四種貨物的總重量約束，即242）三個貨艙的重量限制，即3）三個貨艙的空間限制，即254）三個貨艙裝入重量的平衡約束，即模型求解將以上模型輸入LINDO求解，可以得到：26OBJECTIVE

FUNCTION

VALUE271)121515.8VARIABLEVALUEREDUCED

COSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.000000650.000000X423.0526320.000000X430.000000650.000000實際上，不妨將所得最優(yōu)解作四舍五入，結(jié)果為貨物2裝入前倉10噸、裝入后倉5噸；貨物3裝入中倉13噸、裝入后倉3噸；貨物4裝入中倉3噸，最大利潤約121516元。評注初步看來，本例與運輸問題類似，似乎可以把4種貨物看成4個供應(yīng)點，3個貨艙看成3個需求點（或者反過來，把貨艙看成供應(yīng)點，貨物看成需求點）。但是，這

里對供需量的限制包括兩個方面：重量限制和空間限制，且有裝載均勻要求，因此它只能看成是運輸問題的一種

變形和擴(kuò)展。2829三、鋼管下料問題 某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進(jìn)貨時得到的原料鋼管都是19m?，F(xiàn)有一客戶需要50根4m、20根6m和15根8m的鋼管，應(yīng)如何下料最節(jié)省？零售商如果采用的不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要（1）中的三種鋼管外，還需要

10根5m的鋼管。應(yīng)如何下料最節(jié)省。問題（1）的求解問題分析首先，應(yīng)當(dāng)確定哪些切割模式是可行的。所謂一個切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。例如：我們可以將19

m的鋼管切割成3根4

m的鋼管，余料為7

m；或者將19

m的鋼管切割成4

m、6

m和8m的鋼管各1根，余料為1m。顯然，可行的切割模式是很多的。其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。例如：將19

m的鋼管切割成3根4

m的鋼管，余料為7

m，可進(jìn)一步將7m的余料切割成4m

鋼管（余料為3m），或者將7m的余料切割成6m鋼管（余料為1m）。30在這種合理性假設(shè)下，切割模式一共有7種，如表9所示。314m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根數(shù)余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省。而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)：一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最小。下面將對這兩個目標(biāo)分別討論。模型建立決策變量表示按照第i種模式（ ）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。決策目標(biāo)以切割后剩余的總余料量最小為目標(biāo)，則由表9可得以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有32334m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根數(shù)余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023約束條件為滿足客戶的需求，按照表9應(yīng)有模型求解1．將（1），（3），（4），（5）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO如下：34Min

3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20x3+x5+2x7>=15endgin7求解可以得到最優(yōu)解如下：OBJECTIVE

FUNCTION

VALUE1)

27.0000035VARIABLEVALUEREDUCED

COSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000即按照模式2切割12根原料鋼管，按照模式5切割15根原料鋼管，共27根，總余料量為27m。顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和5的余料為1

m），這會導(dǎo)致切割原料鋼管的總根數(shù)較多。2．將（2）～（5）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO求解，可以得到最優(yōu)解如下：OBJECTIVE

FUNCTION

VALUE1）

25.00000VARIABLEVALUEREDUCED

COSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000即按照模式2切割15根原料鋼管、按模式5切割5根、按模式7切割5根、共25根，可算出總余料量為35m。與上面得到的結(jié)果相比，總余料量增加了8m，但是所用的原料鋼管的總根數(shù)減少了2根。在余料沒有用途情況下，通常選擇總根數(shù)最小為目3標(biāo)6

。問題（2）的求解問題（2）：零售商如果采用的不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要（1）中的三種鋼管外，還需要10根5m的鋼管。應(yīng)如何下料最節(jié)省。問題分析按照（1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。下面介紹的整數(shù)非線性規(guī)劃模型，可以同時確定切割模式和切割計劃，是帶有普遍性的方法。37同（1）類似，一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸（本題中為4m），切割計劃中只使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3m。此外，這里我們僅選擇總根數(shù)最小為目標(biāo)進(jìn)行求解。模型建立決策變量由于不同切割模式不能超過3種，可以用表示按照第i種模式（）切割38的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。設(shè)所使用的第i種切割模式下每根原料鋼管生產(chǎn)4m，5m，6m和8m的鋼管數(shù)量分別為（非負(fù)整數(shù)）。決策目標(biāo)切割原料鋼管的總根數(shù)最小，目標(biāo)為約束條件為滿足客戶的需求，應(yīng)有39每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19m，也不能少于16

m（余量不能大于3m），于是模型求解在（7）～（10）式中出現(xiàn)決策變量的乘積，是一個整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我們發(fā)現(xiàn)運行很長時間也難以得到最優(yōu)解。為了減少運行時間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。40例如，由于3種切割模式的排列順序是無關(guān)緊要的，所以不妨增加以下約束又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的上界和下界。首先，無論如何，原料鋼管的總根數(shù)不可能少于根即至少需26根。其次，考慮一種非常特殊的生產(chǎn)計劃：第一種切割模式下只生產(chǎn)4m鋼管，一根原料鋼管切割成4根4

m鋼管，為滿足50根4

m鋼管的需求，需要13根原料鋼管；41第二種切割模式下只生產(chǎn)5

m、6

m鋼管，一根原料鋼管切割成1根5

m鋼管和2根6

m鋼管，為滿足10根5

m和20根6m鋼管的需求，需要10根原料鋼管；第三種切割模式下只生產(chǎn)8

m鋼管，一根原料鋼管切割成2根8m鋼管，為滿足15根8m鋼管的需求，需要

8根原料鋼管。于是滿足要求的這種生產(chǎn)計劃共需13+10+8=31根原料鋼管，這就得到了最優(yōu)解的一個上界。所以可增加以下約束將（6）～（15）構(gòu)成的模型輸入LINGO如下：4243model：min=x1+x2+x3；x1*r11+x2*r12+x3*r13>=50；x1*r21+x2*r22+x3*r23>=10；x1*r31+x2*r32+x3*r33>=20；x1*r41+x2*r42+x3*r43>=15；4*r11+5*r21+6*r31+8*r41<=19；4*r12+5*r22+6*r32+8*r42<=19；4*r13+5*r23+6*r33+8*r43<=19；4*r11+5*r21+6*r31+8*r41>=16；4*r12+5*r22+6*r32+8*r42>=16；4*r13+5*r23+6*r33+8*r43>=16；x1+x2+x3>=26；x1+x2+x3<=31；x1>=x2；x2>=x3；@gin(x1)

；@gin(x2)

；@gin(x3)

；@gin(r11)

；@gin(r12)

；@gin(r13)

；@gin(r21)

；@gin(r22)

；@gin(r23)

；@gin(r31)

；@gin(r32)

；@gin(r33)

；@gin(r41)

；@gin(r42)

；@gin(r43)

；end注：LINGO軟件用于求解非線性規(guī)劃（包括含有整數(shù)變量的），輸入總是以“model：”開始，以“end”結(jié)束；中間的語句必須以“；”分開。約束中“@gin(x1)”表示x1為整數(shù)，其他類似（如果要表示x1為0-1整數(shù)，應(yīng)該用“@int(x1)”）。在LINGO8.0版本中，缺省設(shè)置假定所有變量非負(fù)，所以上面的輸入中沒有關(guān)于變量非負(fù)的顯式約束。經(jīng)過運行（一般需要幾分鐘），得到輸出如下：44Local

optimal

solution

found

at

iteration：Objective

value：45VariableX1X2Value10.0000010.000001221128.00000ReducedCost0.0000002.000000X38.000001.000000R113.000000.000000R122.000000.000000R210.000000.000000R221.000000.000000R311.000000.000000R321.000000.000000R330.000000.000000R410.000000.000000R420.000000.000000R432.000000.000000即按照模式1，2，3分別切割10，10，8根原料鋼管，使用原料鋼管總根數(shù)為28根，第一種切割模式下一根原料鋼管切割成3根4m鋼管和1根6m鋼管；第二種切割模式下一根原料鋼管切割成2根4m鋼管、1根5m鋼管和1根6m鋼管；第三種切割模式下一根原料鋼管切割成2根8m鋼管。46475.3

動態(tài)規(guī)劃模型例8：最短線路問題問題：現(xiàn)選擇一條從到的鋪管線路，使總距離最短？若用窮舉法要算2×3×2×2×2×1＝48種不同線路，比較這48種結(jié)果即可得出，但當(dāng)段數(shù)增加，且各段選擇也增加時，窮舉法將變得非常龐大，以至利用計算機(jī)都十分困難。下面用動態(tài)規(guī)劃的方法計算最短線路問題的特性：如果最短線路在第k站通過點 ，則這一線路在由出發(fā)到達(dá)終點的那一部分線路，對于從點到達(dá)終點的所有可能選擇的不同線路來說，必定也是距離最短的。（反正法）最短線路問題的這一特性啟示我們，從最后一段開始，用從后向前逐步遞推的方法，求出各點到的最短線路，最后求得從

到 的最短線路。48的最短距離；k＝6時：設(shè) 表示由

到 的最短距離；設(shè) 表示由

到顯然k＝5時：如果表示由

到 的最短距離。49最短線路是最短線路是最短線路是50k＝4時：最短線路是最短線路是5152最短線路是k＝3時：最短線路是53最短線路是最短線路是54最短線路是k＝2時：最短線路是55最短線路是出發(fā)點只有最短線路是最短距離為18。56說明此例揭示了動態(tài)規(guī)劃的基本思想。動態(tài)規(guī)劃方法比窮舉法（48種）大大節(jié)省了計算量。計算結(jié)果不僅得到了

到 的最短線路和最短距離，而且得到了其它各點到 的最短線路和最短距離，這對于很多實際問題來說是很有用處的。動態(tài)規(guī)劃法求解的數(shù)學(xué)描述討論動態(tài)規(guī)劃中最優(yōu)目標(biāo)函數(shù)的建立，一般有下列術(shù)語和步驟：１、階段用動態(tài)規(guī)劃求解多階段決策系統(tǒng)時，要根據(jù)具體情況，將系統(tǒng)適當(dāng)?shù)胤殖扇舾蓚€階段，以便分若干個階段求解，描述階段的變量稱為階段變量。上例分六個階段，是一個六階段的決策過程。例中由系統(tǒng)的最后階段向初始階段求最優(yōu)解的過程稱為動態(tài)規(guī)劃的逆推解法。２、狀態(tài)狀態(tài)表示系統(tǒng)在某一階段所處的位置或狀態(tài)。上例中第一階段有一個狀態(tài)，第二階段有兩個狀態(tài)，過程的狀態(tài)可用狀態(tài)變量 來描述，某個階段所有可能狀態(tài)的全體可用狀態(tài)集合來描述，57３、決策某一階段的狀態(tài)確定之后，從該狀態(tài)演變到下一階段某一狀態(tài)所作的選擇稱為決策。描述決策的變量稱為決策變量如上例中在第k階段用表示處于狀態(tài)時的決策變量。決策變量限制的范圍稱為允許決策集合。用 表示第k階段從 出發(fā)的決策集合。４、策略由每階段的決策

(i＝1,2,…,n)組成的決策函數(shù)序列稱為全過程策略或簡稱策略，用p表示，58由系統(tǒng)的第k個階段開始到終點的決策過程稱為全過程的后部子過程，相應(yīng)的策略稱為后部子過程策略。用 表示k子過程策略，對于每一個實際的多階段決策過程，可供選擇的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。５、狀態(tài)轉(zhuǎn)移某一階段的狀態(tài)變量及決策變量取定后，下一階段的狀態(tài)就隨之而定。5960設(shè)第k個階段的狀態(tài)變量為，決策變量為 ，則第k+1個階段的狀態(tài)

用表示從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱它為狀態(tài)轉(zhuǎn)移方程。６、階段效益系統(tǒng)某階段的狀態(tài)一經(jīng)確定，執(zhí)行某一決策所得的效益稱為階段效益，它是整個系統(tǒng)效益的一部分，是 階段狀態(tài)和 階段決策的函數(shù)，記為７、指標(biāo)函數(shù)指標(biāo)函數(shù)是系統(tǒng)執(zhí)行某一策略所產(chǎn)生的效益的數(shù)量表示，根據(jù)不同的實際問題，效益可以是利潤、距離、產(chǎn)量或資源的耗量等。指標(biāo)函數(shù)可以定義在全過程上，也可以定義在后部子過程上。指標(biāo)函數(shù)往往是各階段效益的某種和式，取最優(yōu)策略時的指標(biāo)函數(shù)稱為最優(yōu)策略指標(biāo)。如上例中，表示從出發(fā)到終點的最優(yōu)策略指標(biāo)。上例中顯然為零，稱它為邊值條件。而動態(tài)規(guī)劃的求解就是對k＝n,n-1,…,2,1逐級求出最優(yōu)策略指標(biāo)的過程。８、動態(tài)規(guī)劃的基本方程61例9：機(jī)器負(fù)荷分配問題某種機(jī)器可以在高低兩種負(fù)荷下生產(chǎn)，年產(chǎn)量與年初投入生產(chǎn)的機(jī)器數(shù)有關(guān)。在高負(fù)荷下生產(chǎn)時，年產(chǎn)量 ，式中 為投入生產(chǎn)的機(jī)器數(shù)，年終的完好機(jī)器數(shù)為 ，稱系數(shù)0.7為機(jī)器完好率。在低負(fù)荷下生產(chǎn)時，年產(chǎn)量 ，式中為投入生產(chǎn)的機(jī)器數(shù)，機(jī)器完好率為0.9，設(shè)開始時，完好的機(jī)器數(shù)為 臺，要求制定一個五年計劃，在每年開始時決定如何重新分配完好機(jī)器在兩種不同負(fù)荷下工作的數(shù)量，使五年的總產(chǎn)量最高。62解：此問題與上例類似。設(shè)階段變量k表示年度；狀態(tài)變量 是第k年初擁有的完好機(jī)器數(shù)（也是第k-1年度末完好機(jī)器數(shù)）。決策變量 規(guī)定為第k年度中分配在高負(fù)荷下生產(chǎn)的機(jī)器數(shù)。于是 是該年度分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)。k=2

k=3

k=4

k=563記表示第k年到第五年末的最高總產(chǎn)量k＝5時這說明第5年初要把全部完好機(jī)器投入高負(fù)荷下生產(chǎn)。k＝4時64k＝3時65k＝2時k＝1時66由此知五年最高總產(chǎn)量為23700再由上遞推知67高負(fù)荷生產(chǎn)的完好機(jī)器的最優(yōu)組合簡記：這表明在前兩年年初全部完好機(jī)器投入低負(fù)荷生產(chǎn)，后三年年初全部完好機(jī)器投入高負(fù)荷生產(chǎn)。第五年末的完好機(jī)器數(shù)為0.7×397＝278臺在此例中，我們僅考慮最高產(chǎn)量，而未考慮五年計劃后的完好機(jī)器數(shù)。問題1：若計劃為n個年度，怎樣決策？問題2：若要求在第5年末完好的機(jī)器數(shù)為500臺，如何決策使5年總產(chǎn)量最高？68這類問題稱為固定終端問題由上討論知：狀態(tài)轉(zhuǎn)移方程仍為表示第k年初開始到第5年末的最高產(chǎn)量，稱為最優(yōu)值函數(shù)，其遞推關(guān)系為k=1,2,3,4,569其中為第k段的效益值，即第k年的產(chǎn)量。表示第6年的產(chǎn)量不計算在總產(chǎn)量之內(nèi)，故為零。由假設(shè)，又根據(jù)(1)得一般地，當(dāng)確定后，選擇 來確定，現(xiàn)已經(jīng)沒有選擇余地，它由在 已經(jīng)給定，故和 確定。于是7071由(2)可知最優(yōu)值72最優(yōu)值類似地得到這是五年最高產(chǎn)量這表明，如果限定五年后的完好機(jī)器數(shù)為500臺，則總產(chǎn)量低于無限制的情況，最優(yōu)策略也相應(yīng)有所變化，由第一年到第四年全部完好機(jī)器投入低負(fù)荷生產(chǎn)。為了計算第5年投入高負(fù)荷生產(chǎn)的完好機(jī)器數(shù) ，先計算所以即第5年有452臺機(jī)器投入高負(fù)荷生產(chǎn)，其余投入低負(fù)荷生產(chǎn)。73§3

存貯模型工廠為了連續(xù)生產(chǎn)必須貯存一些原材料，商店為了連續(xù)銷售必須貯存一些商品，象這類的實際問題當(dāng)然要考慮其經(jīng)濟(jì)效益。因此就必須考慮一個貯存多少的問題。原料、商品存得太多，貯存費用高，存得太少則無法滿足需求。747576問題：尋求一個好的存貯策略，即多長時間訂一次貨，每次訂多少貨才能使總費用最少？模型一：不允許缺貨的存貯模型建模目的：在單位時間的需求量為常數(shù)的情況下，制定最優(yōu)存貯策略，即多長時間訂一次貨，每次訂多少貨，使總費用最小。模型假設(shè)１、每次訂貨費為 ，每天每噸貨物貯存費為

；２、每天的貨物需求量為r噸；３、每T天訂貨Q噸，當(dāng)貯存量降到零時，訂貨立即到達(dá)（即不允許缺貨）。對于第3條假設(shè)中訂貨可以瞬時完成，可解釋為由于需求是確定和已知的，只要提前訂貨使得貯存量為零時立即進(jìn)貨就行了，當(dāng)然，貯存量降到零不符合實際生產(chǎn)需要，應(yīng)該有一個最低庫存量，可以認(rèn)為模型中的貯存量是在這個最低存量之上計算的。模型建立訂貨周期T、訂貨量Q與每天需求量r之間滿足Q＝rT (3-1)訂貨后貯存量由Q均勻地下降，記任意時刻t的貯存量為q，則q(t)的變化規(guī)律可以用圖表示：77考察一個訂貨周期的總費用：訂貨費為

；貯存費是因為積分值恰是圖中三角形面積A，顯然A＝。78由(3-1)式可知一個訂貨周期T內(nèi)的總費用為于是平均每天的費用為所以制定最優(yōu)貯存策略可歸結(jié)為：求訂貨周期T,使C(T)最小。思考：為什么不用 作為目標(biāo)函數(shù)？利用微分法，79再根據(jù)(3-1)式有(3-5)式是經(jīng)濟(jì)理論中著名的經(jīng)濟(jì)訂貨批量公式（簡稱E.O.Q公式）。(3-5)式表明：訂貨費越高，需求量r越大，訂貨批量Q應(yīng)越大；貯存費越高，則每次訂貨批量應(yīng)越小。這些當(dāng)然符合常識，但公式中平方根關(guān)系是憑常識難以得到的。說明：貨物本身的價格不影響最優(yōu)貯存策略。因為若記每噸貨物價格為k，則一周期T的總費用 中應(yīng)添加一項kQ，由于Q＝rT，所以(3-3)中增加一常數(shù)項kr對求解結(jié)果(3-4),(3-5)無影響。80例1.某商店有甲商品出售，每單位甲商品價格

500元，其存貯費每年為價格的20％，甲商品每次訂購費需20元，顧客對甲商品的年需求量為365單位，而且需求率為常數(shù)（即顧客每天需求商品1單位），在不缺貨的條件下，求最優(yōu)策略。解：以年為單位，則需求速度：r＝365于是訂貨批量（單位）訂貨周期81即每隔12天訂一次貨，每次訂12個單位為最優(yōu)策略。若按天為單位：則r＝1，這與以年為單位結(jié)果相同。82模型二：允許缺貨的存貯模型允許缺貨就是企業(yè)或商店可以在存貯降到零后，還可以再等一段時間訂貨。缺貨時因失去銷售機(jī)會而使利潤減少，減少的利潤可以視為因缺貨而付出的費用，稱缺貨費；于是此模型的第

1,2條假設(shè)與不允許缺貨的存貯模型相同，而第3條該為：每隔T天訂貨Q噸，允許缺貨，每天每噸貨物缺貨費為

。缺貨時貯存量視作負(fù)值，q(t)圖形如下：8384貨物在t＝ 時售完，有一段時間缺貨（這時需求量仍為r），在t＝T時下一次訂貨量Q到達(dá)。于是一個訂貨周期T內(nèi)的總費用：訂貨費貯存費由圖知缺貨費由圖知所以總費用85每天平均費用下面問題是當(dāng)T,Q為何值時，使C(T,Q)最小。利用微分法，求出T,Q的最優(yōu)值，記為86則與不允許缺貨的存貯模型相比即：允許缺貨時訂貨周期應(yīng)增大，而訂貨批量應(yīng)減少。當(dāng)缺貨費 越大時,

和 越接近T和Q。這個結(jié)果是合理的，因為 即缺貨造成的損失無限變大，相當(dāng)于不允許缺貨。87問題1、某廠每天需要角鋼100噸，目前每月訂購一次，每次訂購的費用為2500元，每天每噸角鋼的儲存費為

0.18元。如果不允許缺貨，問是否應(yīng)改變訂貨策略，改變后能節(jié)省多少費用。如果允許缺貨，每天每噸的缺貨費為0.4元，試制訂訂策略。2、飲料廠某種飲料生產(chǎn)能力為5000L/天，需求為2000L/天，每次生產(chǎn)準(zhǔn)備費為300元，生產(chǎn)成本為10元/L，而資金為貸款，貸款月息為3%，試制訂生產(chǎn)計劃。88§4森林救火的數(shù)學(xué)模型問題：森林失火了，消防站接到報警后應(yīng)派多少消防隊員前去救火？問題分析森林損失費通常正比于森林燒毀的面積，而燒毀的面積與失火、滅火（指火被撲滅）的時間有關(guān)，滅火的時間又取決于消防隊員數(shù)目，隊員越多，滅火越快。救援費除與消防隊員人數(shù)有關(guān)外，也與消防隊員滅火時間的長短有關(guān)。記失火時刻為t＝0，開始救火時刻為

，將火撲滅