多階段生產(chǎn)計(jì)劃尋找最短路

1、 連續(xù)動(dòng)態(tài)過(guò)程的優(yōu)化歸結(jié)為求泛函的極值. 求泛函極值的常用方法: 變分法, 最優(yōu)控制論. 離散動(dòng)態(tài)過(guò)程的優(yōu)化 動(dòng)態(tài)規(guī)劃模型.靜態(tài)優(yōu)化問(wèn)題優(yōu)化目標(biāo)是數(shù)值最優(yōu)策略是數(shù)值 函數(shù)對(duì)應(yīng)的數(shù)值稱為泛函(函數(shù)的函數(shù)).動(dòng)態(tài)優(yōu)化問(wèn)題優(yōu)化目標(biāo)是數(shù)值最優(yōu)策略是函數(shù)12.1 速降線與短程線 通過(guò)兩個(gè)古典問(wèn)題介紹變分法的基本概念, 給出主要結(jié)果. 速降線問(wèn)題 給定豎直平面內(nèi)不在一條垂直線上的兩個(gè)點(diǎn)A, B, 求連接A, B的光滑曲線，使質(zhì)點(diǎn)在重力作用下沿該曲線以最短時(shí)間從A滑到B (摩擦力不計(jì)). A. B若沿陡峭曲線下滑, 雖路徑加長(zhǎng)，但速度增長(zhǎng)很快.若沿直線段AB下滑, 路徑雖短, 但速度增長(zhǎng)慢; 速降線問(wèn)題 .

2、 A. B建立坐標(biāo)系xOy, xyy=y(x)O曲線弧長(zhǎng) 能量守恒質(zhì)點(diǎn)在曲線y(x)上的速度ds/dt 質(zhì)點(diǎn)沿曲線y(x)從A到B的時(shí)間 求y(x) 使 J(y(x) 達(dá)到最小. m質(zhì)點(diǎn)質(zhì)量，g重力加速度 A(0,0), B(x1,y1), 曲線AB y=y(x) 滿足條件短程線問(wèn)題 . A. Bxyzo給定曲面上的兩個(gè)點(diǎn)A, B, 求曲面上連接A, B的最短曲線. 建立坐標(biāo)系 A(x0, y0, z0 ), B(x1, y1 , z1 )曲線的弧長(zhǎng) 曲線的長(zhǎng)度 求y =y(x), z =z(x) 使J(y(x) , z(x)達(dá)到最小. 滿足條件曲面方程f(x,y,z)=0 f(x,y,z)=

3、0曲面上連接A, B的曲線 y =y(x), z =z(x) y =y(x) z =z(x)泛函、泛函的變分和極值自變量t，函數(shù)x(t), y(t) 函數(shù)、函數(shù)的微分和極值 泛函、泛函的變分和極值 1. 對(duì)于t在某域的任一個(gè)值, 有y的一個(gè)值與之對(duì)應(yīng), 稱y是t的函數(shù)，記作y=f(t) 1.對(duì)于某函數(shù)集合的每一個(gè)函數(shù)x(t), 有J的一個(gè)值與之對(duì)應(yīng), 稱J是x(t)的泛函, 記作J(x(t) 2. t在t0的增量記作 t= t- t0, 微分dt= t 2. x(t)在x0(t)的增量記作 x(t)= x(t)-x0(t)，x(t)稱x(t)的變分 3. y在t0的增量記作 f= f(t0+t

4、) - f(t0)， f的線性主部是函數(shù)的微分, 記作dy，dy = f (t0)dt 3. 泛函J(x(t)在x0(t)的增量記作J = J(x0(t)+ x(t)- J(x0(t), J的線性主部稱泛函的變分,記作 J(x0(t) 泛函、泛函的變分和極值函數(shù)、函數(shù)的微分和極值 泛函、泛函的變分和極值 4. 若函數(shù)y在域內(nèi)t點(diǎn)達(dá)到極值，則在t點(diǎn)的微分dy(t)=0 4. 若泛函J(x(t)在函數(shù)集合內(nèi)的x(t)達(dá)到極值, 則在x(t)的變分J(x(t)=0 5. y在t的微分的另一表達(dá)式5. 泛函J(x(t)在x(t)的變分可以表為泛函J(x(t)在x(t)達(dá)到極值的必要條件 歐拉方程(最簡(jiǎn)

5、泛函極值的必要條件)最簡(jiǎn)泛函F具有二階連續(xù)偏導(dǎo)數(shù)，x(t)為二階可微函數(shù) 固定端點(diǎn)條件下的泛函 J(x(t)在x(t)達(dá)到極值的必要條件: x(t)滿足二階微分方程兩個(gè)任意常數(shù)由 確定 歐拉方程用歐拉方程解速降線問(wèn)題求y(x) 使 達(dá)到最小 , 且歐拉方程圓滾線方程 c2=0, c1由y(x1)=y1確定.橫截條件(變動(dòng)端點(diǎn)問(wèn)題)容許函數(shù) x(t)的一個(gè)端點(diǎn)固定: x(t1)=x1; 另一個(gè)端點(diǎn)在給定曲線 x=(t) 上變動(dòng): x(t2)= (t2) (t2可變).x(t). A. Bx=(t)txot2歐拉方程在變動(dòng)端點(diǎn)的定解條件 x=(t)垂直于橫軸 (t2固定) x=(t)平行于橫軸包含

6、多個(gè)未知函數(shù)泛函的歐拉方程歐拉方程泛函的條件極值求u(t)U (容許集合) 使J(u(t)在條件下達(dá)到極值, 且x(t)X (容許集合) 最優(yōu)控制問(wèn)題: u(t)控制函數(shù), x(t)狀態(tài)函數(shù)(軌線).泛函的條件極值用拉格朗日乘子化為無(wú)條件極值歐拉方程由方程組和端點(diǎn)條件解出最優(yōu)控制u(t)和最優(yōu)軌線x(t).Hamilton函數(shù)12.2 生產(chǎn)計(jì)劃的制訂問(wèn)題 生產(chǎn)任務(wù)是在一定時(shí)間內(nèi)提供一定數(shù)量的產(chǎn)品. 生產(chǎn)費(fèi)用隨著生產(chǎn)率(單位時(shí)間的產(chǎn)量)的增加而變大. 貯存費(fèi)用隨著已經(jīng)生產(chǎn)出來(lái)的產(chǎn)量的增加而變大. 生產(chǎn)計(jì)劃用每一時(shí)刻的累積產(chǎn)量表示.建模目的尋求最優(yōu)生產(chǎn)計(jì)劃, 使完成生產(chǎn)任務(wù)所需的總費(fèi)用(生產(chǎn)費(fèi)用與

7、貯存費(fèi)用之和)最小.分析與假設(shè)生產(chǎn)任務(wù): t=0開始生產(chǎn), t=T提供數(shù)量為Q的產(chǎn)品.生產(chǎn)計(jì)劃(累積產(chǎn)量): x(t)生產(chǎn)率(單位時(shí)間產(chǎn)量):生產(chǎn)費(fèi)用貯存費(fèi)用總費(fèi)用 生產(chǎn)率提高一個(gè)單位的生產(chǎn)費(fèi)用與生產(chǎn)率成正比 貯存費(fèi)用與貯存量成正比模型與求解求x(t) (0, 0tT)使C(x(t)最小.歐拉方程考察x(t)0 (0tT) 的條件txQT0只有當(dāng)生產(chǎn)任務(wù)Q 足夠大時(shí)才需要從 t=0開始生產(chǎn).若 怎么辦? ?模型解釋最優(yōu)生產(chǎn)計(jì)劃滿足方程 邊際成本生產(chǎn)費(fèi)用貯存費(fèi)用邊際貯存最優(yōu)生產(chǎn)計(jì)劃在邊際成本的變化率等于邊際貯存時(shí)達(dá)到.生產(chǎn)計(jì)劃的制訂 最優(yōu)生產(chǎn)計(jì)劃的目標(biāo)函數(shù)只考慮生產(chǎn)費(fèi)用與貯存 費(fèi)用, 并對(duì)這兩種

8、費(fèi)用作了最簡(jiǎn)單的假設(shè). 對(duì)于泛函極值問(wèn)題用古典變分法求解, 得到最優(yōu)生 產(chǎn)計(jì)劃x(t)(累積產(chǎn)量)為二次函數(shù). 實(shí)際條件x(t)0 導(dǎo)致對(duì)已知參數(shù)的要求: 對(duì)函數(shù)施加的閉約束, 如對(duì)生產(chǎn)率的限制 可能導(dǎo)致古典變分法的失敗.若參數(shù)不滿足該要求怎樣處理?12.3 國(guó)民收入的增長(zhǎng)背景和問(wèn)題 國(guó)民經(jīng)濟(jì)收入的來(lái)源: 擴(kuò)大再生產(chǎn)的積累 資金；滿足人民生活需要的消費(fèi)資金 . 如何安排積累資金和消費(fèi)資金的比例， 使國(guó)民經(jīng)濟(jì)收入得到最快的增長(zhǎng). 從最優(yōu)控制的角度討論十分簡(jiǎn)化的模型.一般模型國(guó)民經(jīng)濟(jì)收入 x(t)，其中用于積累資金的部分y(t),求最優(yōu)積累率使國(guó)民收入 x(t)在時(shí)間T內(nèi)增長(zhǎng)最快.積累率 u(t)

9、=y(t)/x(t)國(guó)民收入增長(zhǎng)率對(duì)偶等價(jià)泛函條件極值哈密頓函數(shù)求解最優(yōu)控制函數(shù)u(t)和最優(yōu)狀態(tài)x(t).簡(jiǎn)化模型假設(shè)討論函數(shù)f的具體、簡(jiǎn)化形式描述以上假設(shè)的最簡(jiǎn)模型國(guó)民收入相對(duì)增長(zhǎng)率 積累率u較小時(shí) 隨u的增加而增加 積累資金擴(kuò)大再生產(chǎn)的促進(jìn)作用. 隨著u的變大 的增加變慢. u增加到一定程度后 反而減小 消費(fèi)資金太少對(duì)國(guó)民收入的制約作用.模型求解對(duì)于最簡(jiǎn)模型 不必解泛函極值問(wèn)題, 可以直接得到 u=a/2b時(shí) 最大.使國(guó)民收入 x(t)增長(zhǎng)最快的最優(yōu)積累率是常數(shù) u=a/2b結(jié)果解釋12.4 漁船出海背景和問(wèn)題 繼續(xù)討論開發(fā)漁業(yè)資源的最大經(jīng)濟(jì)效益模型. 用出海漁船數(shù)量表示捕撈強(qiáng)度, 作為

10、控制函數(shù). 當(dāng)漁場(chǎng)魚量增長(zhǎng)到一定數(shù)量后才出海捕撈. 用特殊形式的控制函數(shù)將動(dòng)態(tài)優(yōu)化問(wèn)題化為 普通的函數(shù)極值.模型假設(shè) x(t)的自然增長(zhǎng)服從Logistic規(guī)律, 單位時(shí)間 捕撈量與u(t), x(t)成正比. 當(dāng)t 時(shí)才派漁船出海, 且u(t)=U(常數(shù)). 魚的出售單價(jià)為p, 每只漁船單位時(shí)間費(fèi)用為c, 折扣因子 (通貨膨脹率)為 .漁場(chǎng)魚量x(t), 漁船數(shù)量u(t) x(0)=N/K (K很大), t 時(shí)x(t)保持穩(wěn)定.建模與求解 泛函極值問(wèn)題目標(biāo)函數(shù): 捕魚業(yè)的長(zhǎng)期效益x(t)在t= 的連續(xù)性 函數(shù)極值問(wèn)題建模與求解目標(biāo)函數(shù): 捕魚業(yè)的長(zhǎng)期效益b(1)費(fèi)用-價(jià)格比的下界模型解釋最優(yōu)

11、解應(yīng)在邊際收益等于邊際損失時(shí)達(dá)到單位時(shí)間利潤(rùn)短期利潤(rùn)的增加:長(zhǎng)期收益的減少:漁 船 出 海以漁船數(shù)量u(t)為控制函數(shù)的最大效益模型泛函極值.假定u(t)的特殊形式 , 化為函數(shù)極值. u(t)假定的合理性: 泛函極值問(wèn)題的解正是取這種形式.最優(yōu)解在邊際收益等于邊際損失時(shí)達(dá)到, 是短期利益與長(zhǎng)期利益取得折中的結(jié)果.12.5 賽跑的速度背景和問(wèn)題 將賽程分成若干階段, 根據(jù)賽跑運(yùn)動(dòng)員的生理 條件對(duì)各階段的速度作最恰當(dāng)?shù)陌才? 以期獲 得最好的成績(jī). Keller提出一個(gè)簡(jiǎn)單模型(1974), 根據(jù)4個(gè)生理參 數(shù)從最優(yōu)控制的角度確定各階段的速度函數(shù), 并 可以預(yù)測(cè)比賽成績(jī). 尋求速度安排的最佳策略

12、是復(fù)雜的生理力學(xué)問(wèn)題.問(wèn)題分析 運(yùn)動(dòng)員在賽跑中要克服體內(nèi)外的阻力以達(dá)到 和保持一定速度, 需要發(fā)揮向前的沖力. 這些能量怎樣分配到賽跑的各個(gè)階段, 并在到 達(dá)終點(diǎn)前將其全部用完. 為沖力作功提供能量的來(lái)源: 賽跑前貯存在體內(nèi) 的能量;賽跑中通過(guò)氧的代謝作用產(chǎn)生的能量. 模型要確定的3個(gè)關(guān)系:沖力與速度 沖力作功與能量來(lái)源速度與比賽成績(jī) 將最佳成績(jī)歸結(jié)成以距離為目標(biāo)、與速度、 沖力、能量等函數(shù)有關(guān)的極值問(wèn)題.模型假設(shè) 賽跑中體內(nèi)外的阻力與速度成正比, 比例系數(shù)-1 賽跑中在氧的代謝下單位時(shí)間產(chǎn)生的能量是常數(shù) 賽跑前貯存在體內(nèi)供賽跑的能量是常數(shù)E0 運(yùn)動(dòng)員能發(fā)揮的最大沖力是F 運(yùn)動(dòng)員具有單位質(zhì)量，

13、初速為零. 比賽成績(jī)：“一定距離下時(shí)間最短”等價(jià)為 “一定時(shí)間內(nèi)距離最大” .一般模型以速度v(t)在時(shí)間T內(nèi)跑完賽程D阻力與速度成正比, 比例系數(shù)-1單位質(zhì)量運(yùn)動(dòng)員，初速為零運(yùn)動(dòng)員的最大沖力是F單位時(shí)間產(chǎn)生的能量是賽跑前貯存的能量是E0運(yùn)動(dòng)員賽跑速度v(t), 體內(nèi)能量E(t)D固定, 求v(t)使T最小T固定, 求v(t)使D最大以D(v(t)為目標(biāo)的泛函條件極值 (,F,E0為已知參數(shù))短跑模型用最大沖力F跑全程, 可取得最好成績(jī)最長(zhǎng)的短跑賽程以體內(nèi)能量E(t)不小于零為標(biāo)準(zhǔn)tEE00tcte(單調(diào)增)v小 E增加 v大 E減少 最遠(yuǎn)距離(最長(zhǎng)的短跑賽程)為短跑模型Keller根據(jù)當(dāng)時(shí)的

14、世界記錄得到各參數(shù)的估計(jì)值:后來(lái)根據(jù)1987年約翰遜的百米成績(jī)(9.83s)修正參數(shù):估計(jì)用最大沖力跑全程時(shí)最長(zhǎng)的短跑賽程中長(zhǎng)跑模型當(dāng)賽程超過(guò)Dc時(shí)不能用最大沖力跑全程將賽程分為3個(gè)階段:初始階段(0t t1) 用最大沖力跑, 在短時(shí)間獲得高速度.中間階段(t1 t t2) 保持勻速.最后階段(t2 t T) 把體內(nèi)能量用完, 靠慣性沖刺.問(wèn)題: 確定t1 ,t2 及3個(gè)階段的速度v1(t), v2(t), v3(t)中長(zhǎng)跑模型初始階段用最大沖力跑, 與短跑模型相同t1待定最后階段把體內(nèi)能量用完, E(t)=0中間階段保持勻速t2, v2待定中長(zhǎng)跑模型中間階段在條件E(t2)=0下求v(t)使

15、D(v(t)最大t1, t2, v2待定中長(zhǎng)跑模型引入乘子化為無(wú)條件極值泛函極值必要條件確定t1, t2, v2模型解釋tvt1t20Tv2中長(zhǎng)跑模型3段速度示意圖 賽跑的最佳策略是最后把體內(nèi)能量全部用完, 靠慣性 沖刺,這必然導(dǎo)致速度的短暫下降, 單從賽跑的時(shí)間看 (不考慮比賽的策略), 這樣做是最優(yōu)的. Keller對(duì)一般模型提出分段解法, 不能證明是最優(yōu)的, 但它是合理的簡(jiǎn)化, 在將動(dòng)力學(xué)與生理學(xué)相結(jié)合, 用 建模方法探討體育問(wèn)題上提供了范例.最后一段(通常一兩秒鐘)速度有所下降12.6 多階段最優(yōu)生產(chǎn)計(jì)劃離散動(dòng)態(tài)優(yōu)化問(wèn)題動(dòng)態(tài)規(guī)劃模型是有效方法 問(wèn)題 考察T個(gè)時(shí)段某產(chǎn)品的生產(chǎn)計(jì)劃生產(chǎn)準(zhǔn)備

16、費(fèi)c0 單件生產(chǎn)成本k 單件每時(shí)段存貯費(fèi)h0 每時(shí)段最大生產(chǎn)能力Xm 每時(shí)段最大存貯量Im 第1時(shí)段初有庫(kù)存量i1 制訂產(chǎn)品生產(chǎn)計(jì)劃(每時(shí)段產(chǎn)量)使T個(gè)時(shí)段的總費(fèi)用最小 已知需求量dt (t=1,2,T) 例 T =3, d1=2, d2=1, d3=2, Xm =4,c0=3, k=2, h0=1, Im =3, i1=1 確定需求問(wèn)題優(yōu)化模型(最短路)隨機(jī)需求問(wèn)題分析與求解 生產(chǎn)費(fèi)用時(shí)段t初的存貯量it, 時(shí)段t+1初的存貯量 it+1= it+ xt-dt時(shí)段t的存貯費(fèi) h(it)= h0(it+ xt-dt) = it+xt-dt 時(shí)段t的產(chǎn)量 xt (t=1,2,3)xtXm=4，i

17、tIm=3需求量dt準(zhǔn)備費(fèi)c0=3成本k=2存貯費(fèi)h0=1最大生產(chǎn)能力Xm=4最大存貯量Im=3將多時(shí)段生產(chǎn)計(jì)劃問(wèn)題簡(jiǎn)化為多個(gè)單時(shí)段問(wèn)題 由后向前分解時(shí)段3初的存貯量i3, 產(chǎn)量x3(i3), 最小費(fèi)用f3(i3)1. 最后時(shí)段(時(shí)段3)需求量d3=2 f3(0)=c(2)= 3+22=7為使3個(gè)時(shí)段的總費(fèi)用最小，時(shí)段3末的存貯量應(yīng)為0 i3= 0f3(1)=c(1)= 3+21=5f3(2)=c(0)=0 x3(0)=2i3= 1x3(1)=1i3= 2x3(2)=0分析與求解 2. 時(shí)段2需求量d2=1 時(shí)段2初存貯量i2, 產(chǎn)量x2(i2), 時(shí)段2,3最小費(fèi)用之和時(shí)段2的費(fèi)用: c(x

18、2)+h(i2) i3=i2+x2-1 1i2+x23 i2x2c(x2)h(i2)f3(i2+x2-1)c+ h+ f3f2(i2)，x2(i2)0150712f2(0)=11x2(0)=3027151303920 11*10007 7*f2(1)=7x2(1)=01151511127209200156f2(2)=6x2(2)=021520730020 2*f2(3)=2x2(3)=03. 時(shí)段1時(shí)段1初存貯量i1=1, 產(chǎn)量x1(i1), 需求量d1=2 時(shí)段13最小費(fèi)用之和時(shí)段1的費(fèi)用: c(x1)+h(i1) i2=i2+x2-2 2i2+x25 i1x1c(x1)h=i1+x1-2f

19、2(i1+x1-2)c+ h+ f2f1(i1)，x1(i1)11501116f1(1)=15x1(1)=212717 15*139261714113216f1(1)=15, x1(1)=2i2=i1+x1-2=1+2-2=1i3=i2+x2-1=1+0-1=0最優(yōu)生產(chǎn)計(jì)劃：3個(gè)時(shí)段的產(chǎn)量為x1=2，x2=0，x3=2x2(i2)=x2(1)=0 x3(0)=2最短路問(wèn)題 002101231路段1路段2路段1路段3終點(diǎn)多階段生產(chǎn)計(jì)劃尋找最短路5811145811069172750各路段站點(diǎn): i1=1, i2=0,1,2,3, i3=0,1,2, i4=0兩站點(diǎn)距離: 本時(shí)段生產(chǎn)費(fèi)與存貯費(fèi)之和

20、 路段3各站點(diǎn)到終點(diǎn)的最短距離: f3(i3)路段2各站點(diǎn)到終點(diǎn)的最短距離: f2(i2)路段1站點(diǎn)1到終點(diǎn)的最短距離: f1(1)最短路: i1=1, x1(1)=2i2=1, x2(1)=0i3=0, x3(0)=2i4=0 它的子路徑如 i2=1i3=0i4=0 也是最短路確定需求下多時(shí)段(T時(shí)段)生產(chǎn)計(jì)劃的一般模型最大生產(chǎn)能力Xm 最大存貯量Im 第1時(shí)段初庫(kù)存量i1 需求量dt, 產(chǎn)量xt , 存貯量it, 生產(chǎn)費(fèi)c (xt), 存貯費(fèi)h(it) 1. 根據(jù)對(duì)時(shí)段T末存貯量的要求，確定fT+1(iT+1) 2. 時(shí)段從后向前地計(jì)算最小費(fèi)用，遞推公式：f1(i1)為總費(fèi)用最小值 3.時(shí)

21、段從前向后地確定最優(yōu)生產(chǎn)計(jì)劃: 由i1 , xt(it) 及 it+1= it +xt(it)-dt 得到 xt動(dòng)態(tài)規(guī)劃模型隨機(jī)需求下的多階段生產(chǎn)計(jì)劃 需求量隨機(jī)存貯量隨機(jī)存貯費(fèi)及總費(fèi)用隨機(jī)優(yōu)化目標(biāo)是總費(fèi)用的期望最小隨機(jī)動(dòng)態(tài)規(guī)劃模型隨機(jī)需求: P(dt=1)=1/3, P(dt=2)=2/3 (t=1,2,3) 存貯費(fèi)的期望值Eh(it)= h0E (it+ xt-dt) =(it+xt-1)P(dt=1) +(it+xt-2)P(dt=2)=(it+xt-1)/3+2(it+xt-2)/3=it+xt-5/3 對(duì)于存貯量i3, 計(jì)劃結(jié)束時(shí)出售剩余量得到的回報(bào)為s(i3),期望值Es(i3)=

22、1.5(i3+x3-1)/3+2(i3+x3-2)/3=1.5(i3+x3)-2.5 計(jì)劃結(jié)束時(shí)存貯量隨機(jī), 假定剩余存貯量以1.5的價(jià)格出售 隨機(jī)需求下的多階段生產(chǎn)計(jì)劃 1. 最后時(shí)段(時(shí)段3)時(shí)段3初的存貯量i3, 產(chǎn)量x3(i3), 期望費(fèi)用最小值f3(i3)Es(i3)=1.5(i3+x3)-2.5P(dt=1)=1/3, P(dt=2)=2/3 f3(0)=c(2)-Es(0)=7-1/2=13/2, x3(0)=2f3(1)=c(1)- Es(1)=5-1/2=9/2, x3(1)=1 f3(2)=c(0)- Es(2)=0-1/2=-1/2, x3(2)=0 f3(3)=c(0)

23、- Es(3)=0-2= -2, x3(3)=0 計(jì)算2. 時(shí)段2時(shí)段2,3期望費(fèi)用最小值2i2+x24, x2Xm , i2Imi2x2c(x2)Eh(i2)f3 (i2+x2-1)/3+2 f3 (i2+x2-2)/3c+Eh+ f3f2(i2)，x2(i2)0271/335/679/6f2(0)= 37/3x2(0)=40394/317/679/604117/3-1 37/3*1151/335/667/6f2(1)= 31/3x2(1)=31274/317/667/61397/3-1 31/3*2001/335/6 37/6*f2(2)=37/6x2(2)=02154/317/655/6

24、2277/3-125/33004/317/6 25/6*f2(3)= 25/6x2(3)=03157/3-119/33. 時(shí)段1時(shí)段1初存貯量i1=1 2i1+x14 i1x1c(x1)Eh(i1)f2 (i1+x1-1)/3+2 f2 (i1+x1-2)/3c+Eh+ f2f1(i1)，x1(i1)1151/3105/9306/18f1(1)=303/18x1(1)=31274/3161/18311/181397/333/6 303/18*時(shí)段13期望費(fèi)用最小值x2(i2)=0 d1=1i2=1+3-1=3d1=2 i2=1+3-2=2 x2(i2)=0 x3(i3)=0 d2=1i3=3+0-1=2d2=2 i3=3+0-2=1 x3(i3) =1 x3(i3)=1 d2=1i