【正文】 11144342414433323134232221241312111XXXXXXXXXXXXXXXX表示第 j 項(xiàng)工作只指派 1 人完成 ??????????????????????111144434241343332312423222114131211XXXXXXXXXXXXXXXX表示第 i 人被指派完成一項(xiàng)工作 Xij=0 或 1 (i , j = 1 , 2 , 3 , 4 ) 67 諸如此類，有 n項(xiàng)任務(wù)，恰好有 n個(gè)人可承擔(dān)這些任務(wù)，但由于每人的技術(shù)專長不同，完成任務(wù)的效率 (所費(fèi)時(shí)間不同，為使完成 n項(xiàng)任務(wù)的總效率最高（即所需總時(shí)間最少），應(yīng)如何指派（分派）人員的問題統(tǒng)稱為指派（分派）問題。 一、指派問題的數(shù)學(xué)模型及其特點(diǎn) ： ? ?? ??? ninj ijijijCXCMinZ1 1)0(???????????????????),.. .,2,1(10),.. .,2,1(1),.. .,2,1(111nijXniXnjXijnjijniij或68 （ 1） 給定一個(gè)指派問題時(shí) ， 必須給出效率矩陣 （ 系數(shù)矩陣 ） C=(Cij)nxn,且 Cij?0， 因此必有最優(yōu)解 ( )。 ? ?? ? ?? ni nj ijij XCMinZ 1 1 0（ 2）指派問題是一種特殊的平衡運(yùn)輸問題，由于模型結(jié)構(gòu)的特殊性（看作每個(gè)產(chǎn)地的產(chǎn)量均為 1，每個(gè)銷地的銷量均為 1），故可用更為簡便的匈牙利算法進(jìn)行求解。 二、指派問題的解法 ——匈牙利法 匈牙利法是求解指派問題的一種好算法，它只能求解目標(biāo)函數(shù)為最小化的情況，它由匈牙利數(shù)學(xué)家柯尼格（)提出，因此而得名。 69 ：對同一項(xiàng)工作 （ 任務(wù) ） j來說 ，同時(shí)提高或降低每人相同的效率 （ 常數(shù) ti） ， 不影響其最優(yōu)指派；同樣 ， 對同一個(gè)人 i來說 ， 完成各項(xiàng)工作的效率都提高或降低相同的效率 （ 常數(shù) di） ， 也不影響其最優(yōu)指派 ， 因此可得到新的效率矩陣 (bij)nxn， 其中 bij=Cij+ti+dj （ 對所有的 i,j） 則新的目標(biāo)函數(shù)為? ?? ??ninjijijXbZ1 139。 ? ?? ????ninjijjiijXdtC1 1)( ? ? ? ? ??? ? ? ? ?????ninjninjniijjnjijiijijXdXtXC1 1 1 1 11)()()(1 1? ?? ????ninjjidtZ其中 ? ?? ??ninjjidt1 1為常數(shù)70 這說明 Z?與 Z同時(shí)達(dá)到最小值 。 因而最優(yōu)解相同 。 故指派問題有以下性質(zhì)： 若從效率矩陣 (Cij)nxn的一行 （ 列 ） 各元素中分別減去該行 （ 列 ） 的最小元素 ， 得到的新效率矩陣 (bij)nxn不改變原指派問題的最優(yōu)解 。 P8889 三、關(guān)于求最大化的指派問題 71 對于求最大化的指派問題 （ 即求 ） ,可采 用構(gòu)造新的效率矩陣 (M－ Cij)nxn， 其中 M=max{Cij}， （ 顯 然 M－ Cij?0） ， 將其轉(zhuǎn)化為 ? ?? ?? ninj ijijXCMaxZ1 1? ?? ? ???ninj ijijXCMZMin1 1)( 求所得到的最優(yōu)解就是原問題的最優(yōu)解。事實(shí)上 由于 nM為常數(shù) ， 因此 ， 使 Z?取得最小的最優(yōu)解就是使 Z取得最大的最優(yōu)解 。 ijninjijninjijninjijij XCXMXCMZ ? ?? ? ? ?? ?? ? ? ??????1 11 1 1 1)( ZnMXCnMijninj ij???? ? ?? ?1 172 ， 即 m+n的情況 。 當(dāng) m?n時(shí) ， 則可用增加虛設(shè)的零元數(shù)行 （ 列 ） 使效率矩陣變成方陣后 ， 再用匈牙利法求解 。 ，但可以不唯一。 nm行 ????????????????000000,2111211??????mnmmnCCCCCC當(dāng) mn時(shí) mn列 ????????????0::::::00001221111??????mnmnnCCCCCC當(dāng) mn時(shí) 73 第四章 動態(tài)規(guī)劃 （ Dynamic Programming) 動態(tài)規(guī)劃是 1 9 5 1年由美國數(shù)學(xué)家貝爾曼 （ R i c h a r d Bellman)提出 ， 它是解決一類多階段決策問題的優(yōu)化方法 ，也是考察問題的一種途徑 ， 而不是一種算法 （ 如 LP單純形法） 。 因此它不象 LP那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則 ， 而必須對具體問題進(jìn)行具體分析處理 。 動態(tài)規(guī)劃方法是現(xiàn)代企業(yè)管理中的一種重要決策方法 。 如果一個(gè)問題可將其過程劃分為若干個(gè)相互聯(lián)系的階段問題 ，且它的每一階段都需進(jìn)行決策 ， 則這類問題均可用動態(tài)規(guī)劃方法進(jìn)行求解 。 根據(jù)多階段決策過程的時(shí)序和決策過程的演變 ， 動態(tài)規(guī)劃方法有以下四種類型：離散確定型 、 離散隨機(jī)型 、 連續(xù)確定型和連續(xù)隨機(jī)型 。 返回 74 167。 1動態(tài)規(guī)劃的基本概念和最優(yōu)化原理 一、引例（最短路問題） 假如上圖是一個(gè)線路網(wǎng)絡(luò)，兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)間的距離（或費(fèi)用），我們的問題是要將貨物從 A地運(yùn)往 E地，中間通過 B、 C、 D三個(gè)區(qū)域，在區(qū)域內(nèi)有多條路徑可走，現(xiàn)求一條由 A到 E的線路，使總距離最短（或總費(fèi)用最小）。 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 75 將該問題劃分為 4個(gè)階段的決策問題 ， 即第一階段為從 A到 Bj（ j=1， 2， 3） ， 有三種決策方案可供選擇；第二階段為從 Bj到 Cj（ j=1,2,3） ， 也有三種方案可供選擇；第三階段為從 Cj到 Dj(j=1,2)， 有兩種方案可供選擇；第四階段為從 Dj到 E， 只有一種方案選擇 。 如果用完全枚舉法 ， 則可供選擇的路線有 3 3 2 1=18（ 條 ） ， 將其一一比較才可找出最短路線： A→B 1→C 2→D 3→E 其長度為 12。 顯然 ， 這種方法是不經(jīng)濟(jì)的 ， 特別是當(dāng)階段數(shù)很多 ， 各階段可供的選擇也很多時(shí) ， 這種解法甚至在計(jì)算機(jī)上完成也是不現(xiàn)實(shí)的 。 由于我們考慮的是從全局上解決求 A到 E的最短路問題， 而不是就某一階段解決最短路線 ， 因此可考慮從最后一階段開始計(jì)算 ， 由后向前逐步推至 A點(diǎn)： 76 第四階段 ， 由 D1到 E只有一條路線 ， 其長度 f4（ D1） =3， 同理 f4（ D2） =4。 第三階段 ， 由 Cj到 Di分別均有兩種選擇 ， 即 ? ? ? ?? ? 644 33minDfDC DfDCminCf2421141113 ????????????????????? ?， 決策點(diǎn)為 D1 ? ? ? ?? ? 643 *33minDfDC DfDCminCf2423141333 ???????????????????,決策點(diǎn)為 D1 ? ? ? ?? ? 7*43 36minDfDC DfDCminCf2422141223 ???????????????????， 決策點(diǎn)為 D2 77 第二階段，由 Bj到 Cj分別均有三種選擇，即： ? ?? ?? ?? ?11667467minCfCBCfCBCfCBminBf *33332322131112 ?????????????????????????????決策點(diǎn)為 C2 ? ?? ?? ?? ?96472*63minCfCBCfCBCfCBminBf *33332322132222 ?????????????????????????????決策點(diǎn)為 C1或C2 ? ?? ?? ?? ?9657266minCfCBCfCBCfCBminBf *33332323131332 ?????????????????????????????決策點(diǎn)為 C2 78 第一階段 ， 由 A到 B， 有三種選擇 ， 即： ? ?? ?? ?? ?12*9394112minBfABBfABBfABminAf5252222211 ?????????????????????????????決策點(diǎn)為 B3 f1（ A） =15說明從 A到 E的最短距離為 12， 最短路線的確定可按計(jì)算順序反推而得 。 即 A→B 3→C 2→D 2→E 上述最短路線問題的計(jì)算過程 ， 也可借助于圖形直觀的表示出來： 79 圖中各點(diǎn)上方框的數(shù) ， 表示該點(diǎn)到 E的最短距離 。 圖中紅箭線表示從 A到 E的最短路線 。 從引例的求解過程可以得到以下啟示： ① 對一個(gè)問題是否用上述方法求解 ， 其關(guān)鍵在于能否將問題轉(zhuǎn)化為相互聯(lián)系的決策過程相同的多個(gè)階段決策問題 。 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 3 4 6 7 6 9 9 11 12 80 所謂多階段決策問題是：把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程 ， 也稱為序貫決策過程 。 如下圖所示： 決策 決策 決策狀態(tài) 狀態(tài) 狀態(tài) 狀態(tài) 狀態(tài)1 2 n ② 在處理各階段決策的選取上 ， 不僅只依賴于當(dāng)前面臨的狀態(tài) ， 而且還要注意對以后的發(fā)展 。 即是從全局考慮解決局部 （ 階段 ） 的問題 。 ③ 各階段選取的決策 ， 一般與 “ 時(shí)序 ” 有關(guān) ， 決策依賴于當(dāng)前的狀態(tài) ， 又隨即引起狀態(tài)的轉(zhuǎn)移 ， 整個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來 ， 故有 “ 動態(tài) ” 含義 。 因此 ， 把這種方法稱為動態(tài)規(guī)劃方法 。 ④ 決策過程是與階段發(fā)展過程逆向而行 。 81 多階段決策問題的典型例子： ? 企業(yè)在生產(chǎn)過程中 ， 由于需求是隨著時(shí)間變化的因素 ，因此企業(yè)為了獲得全年最佳經(jīng)濟(jì)效益 ， 就要在整個(gè)生產(chǎn)過程中逐月或逐季的根據(jù)庫存和需求決定生產(chǎn)計(jì)劃 。 ? 某種機(jī)器 ， 可以在高 、 低兩種負(fù)荷下生產(chǎn) 。 高負(fù)荷下生產(chǎn)的產(chǎn)量多 ， 但每生產(chǎn)一個(gè)階段后機(jī)器的完好率低；低負(fù)荷下生產(chǎn)時(shí)的情況則相反 。 現(xiàn)在需要安排該種機(jī)器在多個(gè)階段內(nèi)的生產(chǎn) ， 問應(yīng)該如何決定各階段中機(jī)器的使用 ， 使整個(gè)計(jì)劃期內(nèi)的總產(chǎn)量最大 。 ? 某臺設(shè)備，例如汽車，剛買來時(shí)故障少，耗油低，出車時(shí)間長，處理價(jià)值和