《運籌學(xué)（第3版）》 課件 第6章 動態(tài)規(guī)劃

實用運籌學(xué)

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

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

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

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

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

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

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

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

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

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

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

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

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

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