【正文】 B 1 B 2 B 3 產(chǎn)量 A 1 6 4 6 2 0 0 A 2 6 5 5 3 0 0 銷量 1 5 0 1 5 0 2 0 0 案例：產(chǎn)銷平衡問題 ? 解：產(chǎn)銷平衡問題： 總產(chǎn)量 = 總銷量 ? 設(shè) xij 為從產(chǎn)地 Ai運往銷地 Bj的運輸量，得到下列運輸量表： B 1 B 2 B 3 產(chǎn)量 A 1 x 11 x 12 x 13 2 0 0 A 2 x 21 x 22 x 23 3 0 0 銷量 1 5 0 1 5 0 2 0 0 Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 . x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij ≥ 0 ( i = 2； j = 3） EXCEL求解過程 ? ? sumproduct建立決策目標公式 ? ，分別對供銷，用 sum函數(shù)進行合計計算 ? ，用線性規(guī)劃 ? 選擇目標和變量區(qū)域 ? 約束條件設(shè)置很重要（變量區(qū)域 ＝ 0， sum函數(shù)統(tǒng)計的區(qū)域要與常數(shù)區(qū)域數(shù)值相等） ? 求解完成 ? 注意：如某產(chǎn)銷條件不平衡時，只需要在條件上根據(jù)情況修改 第二節(jié) 運輸問題和指派問題 ? 一、運輸問題及其模型 ? A A ? 、 Am 表示某物資的 m個產(chǎn)地； B B ? 、 Bn 表示某物質(zhì)的 n個銷地； si 表示產(chǎn)地 Ai的產(chǎn)量； dj 表示銷地 Bj 的銷量； cij 表示把物資從產(chǎn)地 Ai運往銷地 Bj的單位運價 ? 設(shè) xij 為從產(chǎn)地 Ai運往銷地 Bj的運輸量，得到下列一般運輸量問題的模型： ? （一）產(chǎn)銷平衡問題 m n Min f = ? ? cij xij i = 1 j = 1 n . ? xij = si i = 1,2,?,m j = 1 m ? xij = dj j = 1,2,?,n i = 1 xij ≥ 0 (i = 1,2,?,m 。 j = 1,2,?,n) 第二節(jié) 運輸問題和指派問題 ?（三）銷大于產(chǎn)問題 m n Min f = ? ? cij xij i = 1 j = 1 n . ? xij = si i = 1,2,?,m j = 1 m ? xij ≤ dj j = 1,2,?,n i = 1 xij ≥ 0 (i = 1,2,?,m 。 例題分析 2：產(chǎn)大于銷問題 ?（四） 運輸問題的計算機求解 ?例 某公司從兩個產(chǎn)地 A A2將物品運往三個銷地 B B B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？ B 1 B 2 B 3 產(chǎn)量 A 1 6 4 6 3 00 A 2 6 5 5 300 銷量 150 150 200 6 0 0 500 例題分析 2：產(chǎn)大于銷問題 ? 解：增加一個虛設(shè)的銷地運輸費用為 0 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 6 4 6 0 3 00 A 2 6 5 5 0 300 銷量 150 150 200 100 6 0 0 600 例題分析 3：銷大于產(chǎn)問題 ?例 某公司從兩個產(chǎn)地 A A2將物品運往三個銷地 B B B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？ B 1 B 2 B 3 產(chǎn)量 A 1 6 4 6 200 A 2 6 5 5 300 銷量 250 200 200 5 0 0 650 例題分析 3：銷大于產(chǎn)問題 ? 解：增加一個虛設(shè)的產(chǎn)地運輸費用為 0 B 1 B 2 B 3 產(chǎn)量 A 1 6 4 6 2 00 A 2 6 5 5 300 A 3 0 0 0 150 銷量 250 200 200 65 0 650 習(xí)題 From/to E F G H Factory supply A 25 35 36 60 15 B 55 30 45 38 6 C 40 50 26 65 14 D 60 40 66 27 11 Destination requirement 10 12 15 9 46 第二節(jié) 運輸問題和指派問題 ? 二、指派問題（特殊的運輸問題） ?（一）任務(wù)數(shù) =人數(shù)（產(chǎn)銷平衡的運輸問題） ?任務(wù)數(shù)與人數(shù)相等的指派問題實質(zhì)上就是產(chǎn)銷平衡的運輸問題，且每行、每列的產(chǎn)量或銷量都等于 1。 j = 1,2,?,n) 例題分析 4：指派問題 ?例 13 有一份說明書，要分別譯成英、日、德、俄四種文字，因各人專長不同，他們完成翻譯不同文字所需的時間見下表： 專家 工作 甲 乙 丙 丁 譯成英文 2 1 0 9 7 譯成日文 1 5 4 14 8 譯成德文 13 1 4 16 1 1 譯成俄文 4 15 1 3 9 解法：匈牙利法 ? 匈牙利法是求解及小型（優(yōu)化方向為極?。┲概蓡栴}的一種方法，這種方法最初由 ，后經(jīng)改進而形成，解法基于匈牙利數(shù)學(xué)家 個定理而得名。經(jīng)過上述變換后，（ bij）中的每行和每列都至少含有一個 0元素，稱位于不同行不同列的 0元素為獨立的 0元素。 ? （ 3） ：矩陣中獨立 0元素的最多個數(shù)等于能覆蓋所有 0元素的最少直線數(shù)。 （對效率矩陣每行每列減去該行該列最小元素） 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 Cij＝ 2 4 11 4 0 8 7 5 11 0 10 4 2 3 5 0 0 11 9 5 5 0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 5 ? 第二步 畫出包含所有 0的直線，并使畫出直線條數(shù)最少。否則第三步（注意不能畫斜線）（例中 3條直線 4，要第三步） 0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 5 ? 第三步 在 沒有被直線覆蓋 的元素中找出最小元素，并對沒畫直線的行上各元素減去最小元素，對畫直線列的各元素都加上 這個最小元素，變換成新效率矩陣 0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 5 2 2 2 6 0 3 11 0 5 4 2 3 0 0 2 9 2 3 +2 0 6 0 3 13 0 5 4 4 3 0 0 0 9 2 3 ? 第四步 對上一步結(jié)果重新畫直線，如果直線條數(shù)等于矩陣行或列數(shù)，完成求解。然后從剩下表中重復(fù)分配。 ? 若任務(wù)數(shù) 人數(shù)，就增加假想工作，就可以化為產(chǎn)銷平衡問題。C1,C2,C3。 ? 狀態(tài) sk：在各階段開始時的客觀條件稱為各階段的狀態(tài)。 ? 決策 uk：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。 ? 決策允許集合 Dk(sk)：在狀態(tài) sk下，允許采取決策的全體。 ? 策略 Pk,n(sk)：從第 k階段開始到最后第 n階段的決策序列，稱 k子策略。 第三節(jié) 動態(tài)規(guī)劃 ? 階段指標函數(shù) dk(sk, uk)：從狀態(tài) sk出發(fā)，選擇決策 uk所產(chǎn)生的第 k階段指標。動態(tài)規(guī)劃要求過程指標具有可分離性，即 Vk,n(sk, uk, uk+1, ?, un) = vk(sk, uk)+Vk+1(sk+1,