運(yùn)籌學(xué)第10章3講

第2節(jié)生產(chǎn)與存儲問題

在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到要合理地安排生產(chǎn)(或購買)與庫存的問題，達(dá)到既要滿足社會的需要，又要盡量降低成本費(fèi)用。因此，正確制定生產(chǎn)(或采購)策略，確定不同時期的生產(chǎn)量(或采購量)和庫存量，以使總的生產(chǎn)成本費(fèi)用和庫存費(fèi)用之和最小，這就是生產(chǎn)與存儲問題的最優(yōu)化目標(biāo)。2.1

生產(chǎn)計劃問題

設(shè)某公司對某種產(chǎn)品要制定一項(xiàng)n個階段的生產(chǎn)(或購買)計劃。已知它的初始庫存量為零，每階段生產(chǎn)(或購買)該產(chǎn)品的數(shù)量有上限的限制；每階段社會對該產(chǎn)品的需求量是已知的，公司保證供應(yīng)；在n階段末的終結(jié)庫存量為零。問該公司如何制定每個階段的生產(chǎn)(或采購)計劃，從而使總成本最小。上述問題的數(shù)學(xué)模型為 可令v0，v1，….，vn為為狀態(tài)變量，vk-1表示第k階段開始時的庫存量。最優(yōu)值函數(shù)fk(vk)表示從第1階段初始庫存量為0到第k階段末庫存量為vk時的最小總費(fèi)用。用動態(tài)規(guī)劃方法來求解此問題看作一個n階段決策問題。xk為決策變量，它表示第k階段的生產(chǎn)量。狀態(tài)轉(zhuǎn)移方程為允許決策集合為順序遞推關(guān)系式為： 邊界條件為最后求得的fn(0)即為所求的最小總費(fèi)用。例1某工廠要對一種產(chǎn)品制訂今后四個時期的生產(chǎn)計劃，據(jù)估計在今后四個時期內(nèi)，市場對于該產(chǎn)品的需求量如下表所示。時期(k)1234需求量(dk)2324假定該廠生產(chǎn)每批產(chǎn)品的固定成本為3千元，若不生產(chǎn)就為0；每單位產(chǎn)品成本為1千元；每個時期生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過6個單位；每個時期末未售出的產(chǎn)品，每單位需付存儲費(fèi)0.5千元。還假定在第一個時期的初始庫存量為0，第四個時期之末的庫存量也為0。試問該廠應(yīng)如何安排各個時期的生產(chǎn)與庫存，才能在滿足市場需要的條件下，使總成本最小。解:按四個時期將問題分為四個階段。由題意知，在第k時期內(nèi)的生產(chǎn)成本為第k時期末庫存量為vk時的存儲費(fèi)用為故第k時期內(nèi)的總成本為動態(tài)規(guī)劃的順序遞推關(guān)系式為 用動態(tài)規(guī)劃方法來求解，其符號含義與上面相同。狀態(tài)轉(zhuǎn)移方程為允許決策集合為解:按四個時期將問題分為四個階段。由題意知，在第k時期內(nèi)的生產(chǎn)成本為第k時期末庫存量為vk時的存儲費(fèi)用為故第k時期內(nèi)的總成本為當(dāng)k=1時，對v1在0至同理得 時期(k)1234需求量(dk)2324之間的值分別進(jìn)行計算。當(dāng)k=2時，由對v2在0至之間的值分別進(jìn)行計算。從而有

時期(k)1234需求量(dk)2324

當(dāng)k=3時，由對v3在0至之間的值分別進(jìn)行計算，從而有時期(k)1234需求量(dk)2324當(dāng)k=4時，

再按計算的順序反推算，可找出每個時期的最優(yōu)生產(chǎn)決策為：

其相應(yīng)的最小總成本為20.5千元。時期(k)1234需求量(dk)2324因要求第4時期之末的庫存量為0，即v4=0，故有把上面例題中的有關(guān)數(shù)據(jù)列成表，可找出一些規(guī)律性的東西。階段i01234需求量di—2324生產(chǎn)量xi—5060庫存量vi03040對每個i，有vi-1·xi＝0，（i＝1，2，3，4）其中v0=0。由表中的數(shù)字可以看到，這類庫存問題有如下特征：

每個子問題的最優(yōu)生產(chǎn)決策特別簡單，它們的最小總成本之和就等于原問題的最小總成本(2)對于最優(yōu)生產(chǎn)決策來說，可分解為兩個子問題：一個是從第1階段到第2階段；另一個是從第3階段到第4階段。由假設(shè)v0=0和vn=0，故階段0和n是再生產(chǎn)點(diǎn)?？梢宰C明：若庫存問題的目標(biāo)函數(shù)g(x)在凸集合S上是凹函數(shù)(或凸函數(shù))，則g(x)在S的頂點(diǎn)上具有再生產(chǎn)點(diǎn)性質(zhì)的最優(yōu)策略。下面運(yùn)用再生產(chǎn)點(diǎn)性質(zhì)來求庫存問題為凹函數(shù)的解。

設(shè)c(j,i)(j≤i)為階段j到階段i的總成本，給定j?1和i是再生產(chǎn)點(diǎn)，并且階段j到階段i期間的產(chǎn)品全部由階段j供給。

第k時期末庫存量為vk時的存儲費(fèi)用為故第k時期內(nèi)的總成本為時期(k)1234需求量(dk)2324 設(shè)最優(yōu)值函數(shù)fi表示在階段i末庫存量vi=0時，從階段1到階段i的最小成本。則對應(yīng)的遞推關(guān)系式為邊界條件為 解：

，故相應(yīng)的最小總成本為20.5千元。

所以故所以最優(yōu)生產(chǎn)決策為：例4

某車間需要按月在月底供應(yīng)一定數(shù)量的某種部件給總裝車間，由于生產(chǎn)條件的變化，該車間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉庫以備后用。已知總裝車間的各個月份的需求量以及在加工車間生產(chǎn)該部件每單位數(shù)量所需工時數(shù)如下表所示。月份k0123456需求量dk0853274單位工時ak111813172010設(shè)倉庫容量限制為H=9，開始庫存量為2，期終庫存量為0，需要制定一個半年的逐月生產(chǎn)計劃，既使得滿足需要和庫容量的限制，又使得生產(chǎn)這種部件的總耗費(fèi)工時數(shù)為最少。狀態(tài)轉(zhuǎn)移方程：

且 故允許決策集合為解:

按月份劃分階段，用可表示月份序號。設(shè)狀態(tài)變量sk為第k段開始時(本段需求量送出之前，上段產(chǎn)品送入之后)部件庫存量。決策變量uk為第k段內(nèi)的部件生產(chǎn)量。最優(yōu)值函數(shù)表示在第k段開始的庫存量為sk時，從第k段至第6段所生產(chǎn)部件的最小累計工時數(shù)。因而可寫出逆推關(guān)系式為當(dāng)k=6時，因要求期終庫存量為0，即s7=0。因每月的生產(chǎn)是供應(yīng)下月的需要，故第6個月不用生產(chǎn)，即u6=0。因此f6(s6)=0，當(dāng)k=5時故及最優(yōu)解且月份k0123456需求量dk0853274單位工時ak111813172010當(dāng)k=4時，由知又，因而故及最優(yōu)解月份k0123456需求量dk0853274單位工時ak111813172010當(dāng)k=3時，故D3(s3)為故得及最優(yōu)解當(dāng)k=2時，其中D2(s2)為故得

及最優(yōu)解

月份k0123456需求量dk0853274單位工時ak111813172010當(dāng)k=1時，其中D1(s1)為故得及最優(yōu)解當(dāng)k=0時，其中D0(s0)為故得及最優(yōu)解所以f0=357和u0*=7月份k0123456需求量dk0853274單位工時ak111813172010因s0=2，再按計算順序反推，即得各階段最優(yōu)決策為： 所以，0至5月最優(yōu)生產(chǎn)計劃為：7，4，9，3，0，4，最小總工時為357。

月份k0123456需求量dk0853274單位工時ak1118131720102.2

不確定性的采購問題

在實(shí)際問題中，還會遇到某些多階段決策過程，其狀態(tài)轉(zhuǎn)移不是完全確定的，出現(xiàn)了隨機(jī)性因素，狀態(tài)轉(zhuǎn)移是按照某種已知概率分布取值的。具有這種性質(zhì)的多階段決策過程稱為隨機(jī)性決策過程。用動態(tài)規(guī)劃方法也可處理這類隨機(jī)性問題，又稱為隨機(jī)性動態(tài)規(guī)劃。2.2

不確定性的采購問題例6采購問題。某廠生產(chǎn)上需要在近五周內(nèi)必須采購一批原料，而估計在未來五周內(nèi)價格有波動，其浮動價格和概率已測得如下表所示。試求在哪一周以什么價格購入，使其采購價格的數(shù)學(xué)期望值最小，并求出期望值。單價概率5000.36000.37000.4解.安采購限期5周分為5個階段。單價概率5000.36000.37000.4k=5時，k=4時于是第4周最優(yōu)決策為單價概率5000.36000.37000.4所以 單價概率5000.36000.37000.4最優(yōu)策略