實用運籌學

－－運用Excel建模和求解（第3版）第6章動態規劃DynamicProgramming本章內容要點動態規劃的基本概念生產與存儲問題訂購與銷售問題餐巾供應問題資源分配問題本章主要內容框架圖動態規劃的基本概念動態規劃是解決多階段決策過程的最優化問題的一種方法。該方法是由美國數學家貝爾曼(R

Bellman)等人在20世紀50年代初提出的。他們針對多階段決策問題的特點，提出了解決這類問題的“最優化原理”，并成功地解決了生產管理、工程技術等方面的許多實際問題，從而建立了運籌學的一個新分支，即動態規劃。動態規劃的基本概念在實際決策過程中，由于涉及的參數比較多，往往需要將問題分成若干個階段，對不同階段采取不同的決策，從而使整個決策過程達到最優。顯然，由于各個階段選擇的策略不同，對應的整個過程就可以有一系列不同的策略。動態規劃把困難的多階段決策問題變換成一系列互相聯系的比較容易的單階段問題，解決了這一系列比較容易的單階段問題，也就解決了困難的多階段決策問題。有時階段可以用時間表示，在各個時間段，采用不同的決策，它隨時間而變化，就有了“動態”的含義。動態規劃的基本概念動態規劃是現代企業管理中一種重要的決策方法。本章利用微軟Excel軟件在“公式”和“規劃求解”兩方面的強大功能，對生產與存儲問題、訂購與銷售問題、餐巾供應問題、資源分配問題等進行分析、建模和求解，解決實際經營管理中的優化問題。動態規劃也適用于人生規劃，它是人類智慧的體現。“千里之行，始于足下”，完成任何一項偉大的事業總是從小事做起的，小目標的達成是實現大目標的基礎。6.1生產與存儲問題在生產和經營管理中，經常會遇到如何合理安排生產與庫存的問題，要求既要滿足市場需要，又要盡量降低成本。因此，合理制訂生產策略，確定不同時期的生產量和庫存量，在滿足產品需求量的條件下，可使得總收益最大或總成本（生產成本＋庫存成本）最小。例6-1

某皮鞋公司根據去年的市場需求分析預測今年的需求：第一季度3000雙、第二季度4000雙、第三季度8000雙、第四季度7000雙。企業現在每個季度最多可以生產6000雙皮鞋。為了滿足所有的預測需求，前兩個季度必須有一定的庫存才能滿足后兩個季度的需求。已知每雙皮鞋的銷售利潤為20元，每個季度的庫存成本為8元。請制訂該公司今年每個季度的生產計劃，以使公司的年利潤最大。6.1生產與存儲問題【解】今年市場總需求量為3000＋4000＋8000＋7000＝22000（雙），而該公司最多可生產4×6000＝24000（雙），所以該公司可以滿足市場總需求。（1）決策變量本問題是要制訂該公司今年每個季度的生產計劃，所以設公司四個季度生產的皮鞋數量分別為x1，x2，x3，x4（雙）；四個季度皮鞋的期末庫存量分別為s1，s2，s3，s4（雙）。6.1生產與存儲問題（2）目標函數

公司的年利潤最大。（3）約束條件①滿足每個季度的需求本季度期末庫存＝上季度期末庫存＋本季度生產－本季度市場需求（狀態轉移方程）②每季度的生產力限制③非負6.1生產與存儲問題例6-1的電子表格模型6.1生產與存儲問題例6-2

某毛毯廠是一個小型生產商，致力于生產家用和辦公用的毛毯。四個季度的生產能力、市場需求、每平方米的生產成本以及庫存成本如表6-2所示。毛毯廠需要確定每個季度生產多少毛毯，才能使總成本（生產成本和庫存成本）最小。季度生產能力(平方米)市場需求(平方米)生產成本(元/平方米)庫存成本(元/平方米)一60040020025二30050050025三50040030025四4004003006.1生產與存儲問題【解】本問題可以用例6-1的方法來求解，即有：

本季度期末庫存＝上季度期末庫存＋本季度生產－本季度市場需求這里介紹另外一種解法，即用第4章介紹過的網絡最優化問題中的最小費用流問題的方法來求解。通過建立一個網絡模型來描述該問題。首先根據四個季度建立四個生產節點和四個需求節點。每個生產節點由一個流出弧連接對應的需求節點。弧的流量表示該季度所生產的毛毯數量。相對于每個需求節點，一個流出弧表示該季度毛毯的期末庫存，即供應下一個季度需求節點的毛毯數量。300300500200252525第一季度生產第二季度生產第三季度生產第四季度生產第一季度需求第二季度需求第三季度需求第四季度需求生產節點需求節點600300500400400500400400生產能力市場需求6.1生產與存儲問題例6-2的線性規劃模型（需求節點的凈流量）上季度期末庫存＋本季度生產－本季度期末庫存＝本季度市場需求6.1生產與存儲問題例6-2的電子表格模型（用例6-1的方法來求解）6.1生產與存儲問題例6-2的電子表格模型（用最小費用流問題的方法來求解）6.1生產與存儲問題例6-3

某廠根據訂貨合同進行生產，已知今后四個季度對某產品的需求量如表6-3所示。如果某個季度生產，則需要生產準備費用3萬元，每件產品的生產成本為1萬元。由于生產能力的限制，每個季度的產量最多不超過6件。每件產品一個季度的存儲費用為5000元，并且第一季度開始時與第四季度結束時均沒有產品庫存。在上述條件下該廠應該如何安排各季度的生產與庫存，可使總費用最少？季度一二三四需求量（件）23246.1生產與存儲問題【解】本問題是一個有固定成本（生產準備費用）的生產與存儲問題。（1）決策變量四個季度生產的產品數量分別為x1，x2，x3，x4。

四個季度產品的期末庫存量分別為s1，s2，s3，s4。

引入隱性0-1變量：yi為第i季度是否生產（1表示生產，0表示不生產）。6.1生產與存儲問題（2）目標函數總費用最少。（3）約束條件①對于每個季度來說，本季度期末庫存＝上季度期末庫存＋本季度生產－本季度需求②生產能力限制③第四季度結束時沒有產品庫存④非負⑤隱性0-1變量6.1生產與存儲問題例6-3的電子表格模型6.2訂購與銷售問題例6-4

某商店在未來的4個月里，準備利用它的一個倉庫來專門經銷某種商品，倉庫最多能儲存這種商品1000單位。假定該商品每月只能賣倉庫現有的貨。當商店在某月訂貨時，下月初才能到貨。該商品未來4個月預測的買賣價格如表6-5所示，假定商店在1月開始經銷時，倉庫儲存有該商品500單位。試問若不計庫存費用，該商店如何制訂1-4月的訂購與銷售計劃，可使預期獲利最大？月份訂購單價（元）銷售單價（元）1月10122月983月11134月15176.2訂購與銷售問題【解】（1）決策變量本問題需要制訂1-4月的訂購與銷售計劃，所以設1-4月的銷售量分別為x1，x2，xi，x4，1-4月的訂貨量分別為y1，y2，y3，y4。

還需設輔助變量：1-4月月初倉庫中的存貨量（月初庫存）分別為s1，s2，s3，s4。（2）目標函數因為不考慮庫存費用，所以要使預期獲利最大，只要考慮每月的銷售收入與訂貨成本即可。6.2訂購與銷售問題（3）約束條件①因為當月訂貨，下月初才能到貨，所以該商店每月可銷售的貨是上月的月末庫存和上月的訂貨，而“上月的月末庫存＝上月的月初庫存－上月的銷售”。也就是說，本月的月初庫存＝上月的月初庫存－上月的銷售＋上月的訂貨（本月到貨）②倉庫的容量限制③非負6.2訂購與銷售問題例6-4的電子表格模型6.2訂購與銷售問題需要說明的是：在用Excel求解有庫存（或剩余量）的問題時，輔助變量“庫存si”經常不用可變單元格（填充顏色為“黃底”）表示，而用輸出單元格（公式，無填充顏色）來替代，但此時要求在“約束條件”中加入“庫存≥0或某個值”的約束。如在圖6-6中，沒有“月初庫存”可變單元格，而用“月初庫存”輸出單元格來替代。6.3餐巾供應問題例6-5

某飯店宴席部預計一周內每天接待的客人數如表6-8所示。規定每位客人每天用餐巾一條。所用餐巾可購買新的，每條成本6元，或者用已經洗凈的餐巾。附近有兩家洗衣店：甲店洗凈一條餐巾收費3元，隔一天送回；乙店洗凈一條餐巾收費2元，隔兩天送回。假定每周開始時沒有舊餐巾。問飯店后勤部應如何安排每天餐巾的供應，才能使總成本（費用）最小？星期一二三四五六日客人數1001201401601401802006.3餐巾供應問題例6-5的線性規劃模型P195-1966.3餐巾供應問題例6-5的電子表格模型6.4資源分配問題資源分配問題是將數量一定的若干種資源（例如原材料、資金、機器設備、勞動力等），合理地分配給若干使用者，使總收益最大。資源的多元分配問題資源的多段分配問題6.4.1資源的多元分配問題例6-6

某公司擬將500萬元資金投放給下屬的A、B、C三個企業，各企業獲得資金后的收益如表6-11所示。求總收益最大的投資分配方案。投資收益企業A企業B企業C120122123323434453756.4.1資源的多元分配問題【解】用類似于指派問題（分派問題）的求解方法。決策變量為：6.4.1資源的多元分配問題例6-6的線性規劃模型為：6.4.1資源的多元分配問題例6-6的電子表格模型6.4.2資源的多段分配問題例6-7

某廠現有100臺機床，能夠加工2種零件，要安排1-4月的任務，根據以往的經驗，這些機床用來加工第1種零件，1個月后損壞率為1/3。而用來加工第2種零件時，1個月后損壞率為1/10。又知道，每臺機床加工第1種零件時每個月的收益為10萬元，加工第2種零件時每個月的收益為7萬元。試問：怎樣分配機床，才能使總收益最大？6.4.2資源的多段分配問題例6-7的線性規劃模型6.4.2資源的多段分配問題例6-7的電子表格模型本章上機實驗1．實驗目的