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

實(shí)用運(yùn)籌學(xué)

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

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

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

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

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

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

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

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

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

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

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

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

某公司擬將500萬(wàn)元資金投放給下屬的A、B、C三個(gè)企業(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臺(tái)機(jī)床，能夠加工2種零件，要安排1-4月的任務(wù)，根據(jù)以往的經(jīng)驗(yàn)，這些機(jī)床用來加工第1種零件，1個(gè)月后損壞率為1/3。而用來加工第2種零件時(shí)，1個(gè)月后損壞率為1/10。又知道，每臺(tái)機(jī)床加工第1種零件時(shí)每個(gè)月的收益為10萬(wàn)元，加工第2種零件時(shí)每個(gè)月的收益為7萬(wàn)元。試問：怎樣分配機(jī)床，才能使總收益最大？6.4.2資源的多段分配問題例6-7的線性規(guī)劃模型6.4.2資源的多段分配問題例6-7的電子表格模型本章上機(jī)實(shí)驗(yàn)1．實(shí)驗(yàn)?zāi)康?/p>