【正文】 因此，整個(gè)系統(tǒng)正常工作的可靠性，可以用它的正常工作的概率來衡量。但備用元件多了，整個(gè)系統(tǒng)的成本、重量、體積均相應(yīng)加大，工作精度也降低。這些部件的正常工作關(guān)系為串接關(guān)系，為提高系統(tǒng)工作的可靠性，在每一個(gè)部件上均裝有主要元件的備用件，并且設(shè)計(jì)了備用件自動(dòng)投入裝置。 ? 建立狀態(tài)轉(zhuǎn)移方程 sk+1=skxk ? 最優(yōu)指標(biāo)函數(shù) fk(sk)表示在擁有資源 sk，分配給第 k種產(chǎn)品至第 n 種產(chǎn)品所得到的最大總收入。 ? 劃分階段 將 n種產(chǎn)品按 1,2,…… ,n的序號(hào)排列 ,每種產(chǎn)品為一個(gè)階段 ,分為 n個(gè)階段 ,k=1,2,…… ,n. ? 狀態(tài)變量 sk表示分配給第 k個(gè)產(chǎn)品至第 n 種產(chǎn)品的資源數(shù)。若分配數(shù)量 xi用于生產(chǎn)第 i種產(chǎn)品，其產(chǎn)生的效益為 ri(xi)。 ? rk(t)：在第 k年設(shè)備已使用過 t年，再使用 1年的效益 ? uk(t)：在第 k年設(shè)備已使用過 t年，再使用 1年的維修費(fèi)用 ? ck(t)：在第 k年賣掉一臺(tái)已使用過 t年的設(shè)備，買進(jìn)一臺(tái)新設(shè)備的更新費(fèi)用 ? a：折扣因子，表示一年以后的單位收入價(jià)值相當(dāng)于現(xiàn)在的 a單位 ? fk(t)：已使用了 t年的舊設(shè)備，從第 k年開始在以后繼續(xù)使用到規(guī)定的第 n年未知幾年內(nèi)的總回收額 88 設(shè)備更新問題 ? 劃分階段 k表示計(jì)劃使用該設(shè)備的年限數(shù) ? 狀態(tài)變量 sk表示第 k年初，設(shè)備已使用過的年數(shù) ? 決策變量 xk表示第 k年初更新，還是繼續(xù)使用舊設(shè)備，分別用 R和 K表示 。在適當(dāng)?shù)臅r(shí)候，就要賣掉舊設(shè)備，購(gòu)買新設(shè)備。這就是要研究的問題。 kkkk axss ???? 1 ka87 設(shè)備更新問題 ? 在企業(yè)中，經(jīng)常遇到設(shè)備陳舊或部分損壞需要更新的問題。如何制定生產(chǎn)策略使三個(gè)月內(nèi)的期望費(fèi)用最小。在第 3個(gè)月末要把現(xiàn)有的庫(kù)存以每單位 2元的價(jià)格售出。因?yàn)閹?kù)存能力有限，每月末的庫(kù)存量不能超過 3單位。如果生產(chǎn)的數(shù)量大于需求，就出現(xiàn)庫(kù)存。在一個(gè)月內(nèi)生產(chǎn) x單位的產(chǎn)品，所需成本為 c(x)，其中 c(0)=0，當(dāng) x0時(shí)，c(x)=3+2x。 85 生產(chǎn)計(jì)劃問題 ? 劃分階段 按月份劃分階段，每個(gè)月為一個(gè)階段， k=1,2,…… ,n. ? 狀態(tài)變量 第 k階段開始時(shí)（即本階段需求送出之前，上階段產(chǎn)品送入之后）部件庫(kù)存量，記為 sk ? 決策變量 第 k階段內(nèi)的部件生產(chǎn)量，記為 uk ? 建立狀態(tài)轉(zhuǎn)移方程 sk+1=sk+ukdk ? 最優(yōu)指標(biāo)函數(shù) fk(sk)表示在第 k階段開始的庫(kù)存量為 sk時(shí)，從第 k階段到最后一階段生產(chǎn)部件的最小 累計(jì)工時(shí)數(shù)。 ? 某中轉(zhuǎn)倉(cāng)庫(kù)要按月在月初供應(yīng)一定數(shù)量的某種部件給總裝車間，由于生產(chǎn)條件的變化，生產(chǎn)車間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉(cāng)庫(kù)以備后用?，F(xiàn)將此三種產(chǎn)品運(yùn)往市場(chǎng)出售，運(yùn)輸能力總重量不超過 6 噸，問如何安排運(yùn)輸，使總利潤(rùn)最大？ 種類 1 2 3 重量（噸 /公斤） 2 3 4 單件利潤(rùn)（元） 80 130 180 最優(yōu)方案： X1 =（ ） X2 =（ ） Z=260 82 練習(xí) 2：求下列問題的最優(yōu)解 ??????????且為整數(shù)0,10543654m a x321321321xxxxxxxxxZ X=(2. 1. 0) 最優(yōu)值為 Z = 13 83 背包問題 ? 一位旅行者攜帶背包旅游，已知他的背包所能承受的重量為 w千克，現(xiàn)有 n種物品可供他選擇裝入包中，第 i種物品的單件重量為 wi 千克，其價(jià)值是攜帶數(shù)量 的函數(shù) 。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤(rùn)最大。（即將加工時(shí)間由小到大排列即可） 1j 2j3j 4j5j零件加工順序 工序時(shí)間 1 3 4 5 7 實(shí)際通過時(shí)間 1 4 8 13 20 交貨時(shí)間 8 23 14 6 20 平均通過時(shí)間 )1481320(51 ??????x延遲時(shí)間 = 13 – 6 = 7 70 （ 2）按時(shí)交貨排列順序 1j2j3j4j 5j零件加工順序 工序時(shí)間 1 3 4 5 7 實(shí)際通過時(shí)間 5 6 10 17 20 交貨時(shí)間 8 23 14 6 20 平均通過時(shí)間 )56101720(51 ??????x延遲時(shí)間 = 0 71 （ 3）既滿足交貨時(shí)間，又使平均通過時(shí)間最小 1j 2j3j 4j 5j零件加工順序 工序時(shí)間 1 3 4 5 7 實(shí)際通過時(shí)間 1 6 9 13 20 交貨時(shí)間 8 23 14 6 20 延遲時(shí)間 = 0 平均通過時(shí)間 )1691320(51 ??????x72 2. n 2 排序問題 即 n 種零件經(jīng)過 2 種設(shè)備進(jìn)行加工，如何安排？ 例： 4 9 5 2 3 B 5 3 7 8 6 A 零件 2j1j 3j 4j 5j設(shè)備 A B T 73 經(jīng)變換為 4 9 5 2 3 B 5 3 7 8 6 A 零件 2j1j3j4j 5j設(shè)備 加工順序圖如下： A B T 3j 1j 2j4j 5j3 7 5 6 8 9 5 4 3 2 +2 +2 5 加工周期 T = 3+7+5+6+8+2 = 31 小即 BA tt i ??74 3. n 3 排序問題 即 n 種零件經(jīng)過 3 種設(shè)備進(jìn)行加工，如何安排？ 例： 3 4 6 8 5 6 4 6 8 3 5 7 9 3 10 C B A 1j2j3j4j5jA B C T 75 A B C T 變換 4+3 6+4 5+8 6+5 6+4 8+6 5+3 7+5 3+9 10+3 B + C A+B 1j2j3j4j5j76 排序 4+3 6+4 5+8 6+5 6+4 8+6 5+3 7+5 3+9 10+3 B + C A+B 1j2j3j4j5j復(fù)原 3 4 6 8 5 6 4 6 8 3 5 7 9 3 10 C B A 1j2j3j4j5j77 計(jì)算 T = 6+10+8+7+6+4+3 = 44 計(jì)算依據(jù)： ABcCBABCBAttttttttttiiiiii???????? 或即可按下式計(jì)算或 m a xm i nm a xm i n78 練習(xí)： 11 8 5 10 7 9 8 2 7 7 4 6 C B A 1j2j3j4jT=45 1j2j 3j4j79 練習(xí)： 求投資分配問題得最優(yōu)策略，其中 a＝ 50 萬(wàn)元，其余資料如表所示。其目的是使加工周期為最短。 ? ?)60()(max)60( 3460,10,04 yfygf y ??? ? ?67 16007025656060855011040135251550m a x)0()60()10()50()20()40()30()30()40()20()50()10()60()0(m a x34343434343434?????????????????????????????????????????????????????????????fgfgfgfgfgfgfg最優(yōu)策略為（ 20， 0， 30， 10），最大利潤(rùn)為 160萬(wàn)元。得到下表 66 投資 利潤(rùn) 0 10 20 30 40 50 60 f3(x) 0 25 60 85 110 135 155 最優(yōu) 策略 (0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30) 第四階段：求 f4(60)。 ? ?)60()(m ax)60( 2360,10,03 yfygf y ??? ? ?65 1550115202105010070859060105251200m a x)0()60()10()50()20()40()30()30()40()20()50()10()60()0(m a x23232323232323?????????????????????????????????????????????????????????????fgfgfgfgfgfgfg最優(yōu)策略為（ 20， 10， 30），最大利潤(rùn)為 155萬(wàn)元。 64 投資 利潤(rùn) 0 10 20 30 40 50 60 f2(x) 0 20 50 70 90 105 120 最優(yōu)策略 (0,0) (10,0) (0,10) (20,0) (20,10) (20,20) (30,20) (40,20) 第三階段：求 f3(x)。 最優(yōu)策略為（ 0， 0），最大利潤(rùn)為 0萬(wàn)元。 63 ? ?50 )20()(m a x)20( 1220,10,02?????yfygfy? ?20 )10()(m a x)10( 12,10,02?????yfygfy最優(yōu)策略為（ 10， 0）或（ 0 ， 10 ） ，此時(shí)最大利潤(rùn)為20萬(wàn)元。 62 ? ?90 )40()(m a x)40( 1240,10,02?????yfygfy ?最優(yōu)策略為（ 20， 20），此時(shí)最大利潤(rùn)為 90萬(wàn)元。 同理可求得其它 f2(x) 的值。此時(shí)需考慮第一、第二個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤(rùn)。 第一階段：求 f1(x)。 投資 利潤(rùn) 0 10 20 30 40 50 60 g1(x) 0 20 50 65 80 85 85 g2(x) 0 20 40 50 55 60 65 g3(x) 0 25 60 85 100 110 115 g4(x) 0 25 40 50 60 65 70 解 ：依據(jù)題意，是要求 f4(60) 。 當(dāng) k=1 時(shí)， f1(x) = g1(x) （因?yàn)橹唤o一個(gè)工廠） 當(dāng) 1＜ k≤n 時(shí)，其遞推關(guān)系如下： 設(shè)： y 為分給第 k 個(gè)工廠的資金（其中 0≤y ≤ x ），此時(shí)還剩 x － y（萬(wàn)元）的資金需要分配給前 k－ 1 個(gè)工廠，如果采取最優(yōu)策略，則得到的最大利潤(rùn)為 fk－ 1(x－ y) ，因此總的利潤(rùn)為： gk(y) ＋ fk－ 1(x－ y) 57 ? ?nkyxfygxf kkxyk,3,2