第二章-系統(tǒng)工程-運籌學

線性規(guī)劃及數(shù)學模型

線性規(guī)劃是運籌學的一個重要分支。線性規(guī)劃在理論上比較成熟，在實用中的應用日益廣泛與深入。特別是在電子計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領域更為廣泛了。從解決技術問題的最優(yōu)化設計到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸業(yè)、軍事、經(jīng)濟計劃和管理決策等領域都可以發(fā)揮作用。它已是現(xiàn)代科學管理的重要手段之一。1.1問題的提出從一個簡化的生產(chǎn)計劃安排問題開始例1某工廠在計劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗，如表所示。資源

產(chǎn)品ⅠⅡ

擁有量設備128臺時原材料

A

4016kg原材料B0412kg續(xù)例1

該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問應如何安排計劃使該工廠獲利最多?如何用數(shù)學關系式描述這問題，必須考慮數(shù)學模型例2.簡化的環(huán)境保護問題

靠近某河流有兩個化工廠(見圖1)，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。

圖1續(xù)例2第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，第二化工廠每天排放這種工業(yè)污水1.4萬立方米。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應不大于0.2%。這兩個工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是1000元/萬立方米，第二化工廠處理工業(yè)污水的成本是800元/萬立方米。現(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應處理多少工業(yè)污水，使這兩個工廠總的處理工業(yè)污水費用最小。

建模型之前的分析和計算

設：第一化工廠每天處理工業(yè)污水量為x1萬立方米，第二化工廠每天處理工業(yè)污水量為x2萬立方米

數(shù)學模型共同的特征每一個線性規(guī)劃問題都用一組決策變量

表示某一方案，這組決策變量的值就代表一個具體方案。一般這些變量取值是非負且連續(xù)的；(2)要有各種資源和使用有關資源的技術數(shù)據(jù)，創(chuàng)造新價值的數(shù)據(jù)；共同的特征（繼續(xù)）(3)存在可以量化的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示;(4)要有一個達到目標的要求，它可用決策變量的線性函數(shù)(稱為目標函數(shù))來表示。按問題的不同，要求目標函數(shù)實現(xiàn)最大化或最小化。線性規(guī)劃的一般模型形式目標函數(shù)約束條件存儲論

存儲論的基本概念確定性存貯模型隨機性存貯模型

存儲論的基本概念

一存儲問題的提出

人們在生產(chǎn)和日常生活活動中往往將所需的物資、用品和食物暫時地儲存起來，以備將來使用或消費。這種儲存物品的現(xiàn)象是為了解決供應(生產(chǎn))與需求(消費)之間的不協(xié)調(diào)的一種措施，這種不協(xié)調(diào)性一般表現(xiàn)為供應量與需求量和供應時期與需求時期的不一致性上，出現(xiàn)供不應求或供過于求。人們在供應與需求這兩環(huán)節(jié)之間加入儲存這一環(huán)節(jié)，就能起到緩解供應與需求之間的不協(xié)調(diào)，以此為研究對象，利用運籌學的方法去解決最合理、最經(jīng)濟地儲存問題。例如(1)水電站在雨季到來之前，水庫應蓄水多少?(2)工廠生產(chǎn)需用原料，如沒有儲存一定數(shù)量的原料，會發(fā)生停工待料現(xiàn)象。(3)在商店里若存儲商品數(shù)量不足，會發(fā)生缺貨現(xiàn)象，失去銷售機會而減少利潤；如果存量過多，一時售不出去，會造成商品積壓，占用流動資金過多而且周轉(zhuǎn)不開，這樣也會給商家造成經(jīng)濟損失。專門研究這類有關存儲問題的科學，構成運籌學的一個分支，叫作存儲論(inventory)，也稱庫存論。本章所介紹的存儲問題，模型并不復雜，原理也容易掌握，應用這些原理可以從一個方面改善企業(yè)的經(jīng)營管理，以達到節(jié)約資金，獲得更多利潤的目的。二存儲論的基本概念1.需求對存儲來說，由于需求，從存儲中取出一定的數(shù)量，使存儲量減少，這就是存儲的輸出。有的需求是間斷式的，有的需求是連續(xù)均勻的。圖1和圖2分別表示t時間內(nèi)的輸出量皆為

S-W，但兩者的輸出方式不同。圖1表示輸出是間斷的，圖2表示輸出是連續(xù)的。有的需求是確定性的，如鋼廠每月按合同賣給電機廠矽鋼片10噸。有的需求是隨機性的，如書店每日賣出去的書可能是1000本，也可能是800本。但是經(jīng)過大量的統(tǒng)計以后，可能會發(fā)現(xiàn)每日售書數(shù)量的統(tǒng)計規(guī)律，稱之為有一定的隨機分布的需求。圖1，22補充(訂貨或生產(chǎn))存儲由于需求而不斷減少，必須加以補充，否則最終將無法滿足需求。補充就是存儲的輸入。補充的辦法可能是向其他工廠購買，從訂貨到貨物進入“存儲”往往需要一段時間，我們把這段時間稱為備貨時間（即工廠的生產(chǎn)時間和運輸時間）。從另一個角度看，為了在某一時刻能補充存儲，必須提前訂貨，那么這段時間也可稱之為提前時間(leadtime)。備貨時間可能很長，也可能很短，可能是隨機性的，也可以是確定性的。存儲論要解決的問題是：多少時間補充一次，每次補充的數(shù)量應該是多少。決定多少時間補充一次以及每次補充數(shù)量的策略稱為存儲策略。存儲策略的優(yōu)劣如何衡量呢?最直接的衡量標準，是計算該策略所耗用的平均費用多少。為此有必要對費用進行詳細的分析。3費用（主要包括以下費用）(1)存儲費C1，包括貨物占用資金應付的利息以及使用倉庫、保管貨物、貨物損壞變質(zhì)等支出的費用。(2)訂貨費，包括兩項費用，一項是訂購費用C3(固定費用，或一次性費用)如手續(xù)費、電信往來、派人員外出采購等費用。訂購費與訂貨次數(shù)有關，而與訂貨數(shù)量無關。另一項是可變費用，它與訂貨數(shù)量及貨物本身的價格，運費等有關。如貨物單價為K元，訂購費用為C3元，訂貨數(shù)量為Q，則訂貨費用為：C3+KQ。(3)生產(chǎn)費，補充存儲時，如果不需向外廠訂貨，由本廠自行生產(chǎn)，這時仍需要支出兩項費用。一項是準備、結(jié)束費用，如更換模、夾具需要工時，或添置某些專用設備等屬于這項費用；它是一次性的費用，或稱為固定費用，也用C3表示。另一項是與生產(chǎn)產(chǎn)品的數(shù)量有關的費用如材料費、加工費等(可變費用)。(4)缺貨費C2，當存儲供不應求時所引起的損失。如失去銷售機會的損失、停工待料的損失以及不能履行合同而繳納罰款等。在不允許缺貨的情況下，在費用上處理的方式是缺貨費為無窮大。4存儲策略如前所述決定何時補充，補充多少數(shù)量的辦法稱之為存儲策略，常見的策略有三種類型。(1)t0循環(huán)策略，每隔t0時間補充存儲量Q。(2)(s,S)策略，每當存儲量x＞s時不補充。當x≤s時補充存儲。補充量Q=S-x(即將存儲量補充到S)。(3)(t,s,S)混合策略，每經(jīng)過t時間檢查存儲量x，當x＞s時不補充。當x≤s時，補充存儲量使之達到S。一個好的存儲策略，既可以使總費用最小，又可避免因缺貨影響生產(chǎn)(或?qū)︻櫩褪バ庞?存儲模型的兩大類型：一類叫作確定性模型，即模型中的數(shù)據(jù)皆為確定的數(shù)值；另一類叫作隨機性模型，即模型中含有隨機變量，而不是確定的數(shù)值。由于具體條件有差別，制定存儲策略時又不能忽視這些差別，因而模型也有多種類型。本章將按確定性存儲模型及隨機性存儲模型兩大類，分別介紹一些常用的存儲模型，并從中得出相應的存儲策略。三確定性存儲模型

模型一：不允許缺貨，備貨時間很短假設：(1)缺貨費用無窮大；(2)當存儲降至零時，可以立即得到補充(即備貨時間或拖后時間很短，可以近似地看作零)；(3)需求是連續(xù)的、均勻的，設需求速度R(單位時間的需求量)為常數(shù)，則t時間的需求量為Rt；(4)每次訂貨量不變，訂購費不變(每次備貨量不變，裝配費不變)；(5)單位存儲費不變。分析模型一其存儲量的變化情況用右圖表示假定每隔t時間補充一次存儲，那么訂貨量必須滿足t時間的需求Rt，記訂貨量為Q，Q=Rt，訂購費為C3，貨物單價為K，則訂貨費為C3+KRt；t時間的平均訂貨費為t時間內(nèi)的平均存儲量為(此結(jié)果由上頁圖中利用幾何知識易得出，平均存儲量為三角形高的二分之一)單位時間內(nèi)單位物品的存儲費用為C1，

t時間內(nèi)所需平均存儲費用為1/2(RtC1）。

t時間內(nèi)總的平均費用為C(t）對(1)式利用微積分求最小值的方法可求出令費用最少時的訂貨時間和數(shù)量。經(jīng)濟批量公式因得即存儲論中著名的經(jīng)濟訂購批量(economicorderingquantity)公式。簡稱為E.O.Q公式，也稱平方根公式，或經(jīng)濟批量(economiclotsize)公式。

所以，C(t0)為最小值由于Q0、t0皆與K無關，所以此后在費用函數(shù)中略去KR這項費用。如無特殊需要不再考慮此項費用，(1)式改寫為最佳費用公式

將t0代入(4)式得出最佳費用

從費用曲線也可以求出t0，Q0，C0費用曲線C(t)曲線的最低點(minC(t))的橫坐標t0與存儲費用曲線、訂購費用曲線交點橫坐標相同。即例1某廠按合同每年需提供D個產(chǎn)品，不許缺貨。假設每一周期工廠需裝配費C3元，存儲費每年每單位產(chǎn)品為C1元，問全年應分幾批供貨才能使裝配費，存儲費兩者之和最少。解設全年分n批供貨，每批生產(chǎn)量Q=D/n，周期為1/n年(即每隔1/n年供貨一次)。公式公式說明從例1中還看到這些公式在實際應用時還會有一點問題，因為t0(或Q0，n0)不一定是整數(shù)。假設t0=16.235(天)。很明顯，小數(shù)點后面的數(shù)字對實際訂貨間隔的時間是沒有意義的，這時可以取近似的整數(shù)。取t0≈16或t0≈17都可以。為了精確起見，可以比較C(16)、C(17)的大小，再決定t0=16或t0=17。例2某軋鋼廠每月按計劃需產(chǎn)角鋼3000噸，每噸每月需存儲費5.3元，每次生產(chǎn)需調(diào)整機器設備等，共需準備費2500元。若該廠每月生產(chǎn)角鋼一次，生產(chǎn)批量為3000噸。每月需總費用5.3×1/2×3000+25000=10450(元/月)全年需費用10450×12=125400(元/年)然后按E.O.Q公式計算每次生產(chǎn)批量計算批量和批次計算需要的數(shù)據(jù)兩次生產(chǎn)相隔的時間t0=（365/21.4）≈17(天)17天的單位存儲費(5.3/30)×17=3.00(元/噸)，共需費用5.3/30×17×1682+2500≈5025(元)。按全年生產(chǎn)21.5次(兩年生產(chǎn)43次)計算，全年共需費用5025×21.5=108037(元/年)。兩者相比較，該廠在利用E.O.Q公式求出經(jīng)濟批量進行生產(chǎn)即可每年節(jié)約資金125400－108037=17363(元)模型二：不允許缺貨，生產(chǎn)需一定時間

本模型的假設條件，除生產(chǎn)需要一定時間的條件外，其余皆與模型一的相同。設生產(chǎn)批量為Q，所需生產(chǎn)時間為T，則生產(chǎn)速度為P=Q/T。已知需求速度為R，(R＜P)。生產(chǎn)的產(chǎn)品一部分滿足需求，剩余部分才作為存儲，這時存儲變化如圖所示。在［0，T］區(qū)間內(nèi)，存儲以(P-R)速度增加，在［T，t］區(qū)間內(nèi)存儲以速度R減少。T與t皆為待定數(shù)。從上圖易知(P-R)T=R(t-T)，即PT=Rt(等式表示以速度P生產(chǎn)T時間的產(chǎn)品等于t時間內(nèi)的需求)，并求出公式公式例3某廠每月需甲產(chǎn)品100件，每月生產(chǎn)率為500件，每批裝配費為50元，每月每件產(chǎn)品存儲費為4元，求E.O.Q及最低費用。解已知C3=50，C1=4，P=500，R=100，將各值代入公式(7)及(8)得例4某商店經(jīng)售甲商品成本單價500元，年存儲費用為成本的20%，年需求量365件，需求速度為常數(shù)。甲商品的定購費為20元，提前期為10天，求E.O.Q及最低費用。解此例題從表面上看，似乎應按模型二處理。因為拖后時間似乎與生產(chǎn)需一定時間意義差不多。其實不然，現(xiàn)將本題存儲變化情況用圖表示之(見下頁圖)，并與模型一、模型二的圖相比較，可看到與模型一完全相同。本題只需在存儲降至零時提前10天訂貨即可保證需求。計算訂貨點由于提前期為t1=0天，10天內(nèi)的需求為10單位甲商品，因此只要當存儲降至10單位時，就要訂貨。一般設t1為提前期，R為需求速度，當存儲降至L=Rt1的時候即要訂貨。L稱為“訂購點”(或稱訂貨點)。確定多少時間訂一次貨，雖可以用E.O.Q除以R得出to(to=Qo/R)，但求解的過程中并沒有求出to，只求出訂貨點L即可，這時存儲策略是：不考慮to，只要存儲降至L即訂貨，訂貨量為Qo，稱這種存儲策略為定點定貨。相對地每隔to時間訂貨一次稱為定時訂貨，每次訂貨量不變則稱為定量訂貨。

模型三：允許缺貨，備貨時間很短模型一、模型二是在不允許缺貨的情況下推導出來的。本模型是允許缺貨，并把缺貨損失定量化來加以研究。由于允許缺貨，所以企業(yè)可以在存儲降至零后，還可以再等一段時間然后訂貨。這就意味著企業(yè)可以少付幾次訂貨的固定費用，少支付一些存儲費用。一般地說當顧客遇到缺貨時不受損失，或損失很小，而企業(yè)除支付少量的缺貨費外也無其他損失，這時發(fā)生缺貨現(xiàn)象可能對企業(yè)是有利的。本模型的假設條件除允許缺貨外，其余條件皆與模型一相同。設單位時間單位物品存儲費用為C1，每次訂購費為C3，缺貨費為C2(單位缺貨損失)，R為需求速度。求最佳存儲策略，使平均總費用最小(見下圖)。假設最初存儲量為S

公式公式公式公式將(10)式，(11)式代入C(t,S)由于模型三中允許缺貨

在允許缺貨情況下，存儲量只需達到S0即可，

顯然Q0＞S0，它們的差值表示在to時間內(nèi)的最大缺貨量。說明在允許缺貨條件下，經(jīng)過研究而得出的存儲策略是：每隔to時間訂貨一次，訂貨量為Qo，用Qo中的一部分補足所缺貨物，剩余部分So進入存儲。很明顯，在相同的時間段落里，允許缺貨的訂貨次數(shù)比不允許缺貨時訂貨次數(shù)減少了。例5已知需求速度R=100件，C1=4元，C2=1.5元，C3=50元，求S0及C0。解利用(12)式，(13)式即可計算模型一、二、三存儲策略之間的差別可以看到不允許缺貨生產(chǎn)需要時間很短條件下得出的存儲策略：最大存儲量S0=Q0在不允許缺貨、生產(chǎn)需一定時間條件下，得出存儲策略在允許缺貨、生產(chǎn)需時間很短條件下，得出存儲策略模型二、三只是以模型一的存儲策略乘上相應的因子，這樣可以便于記憶，再有

都是同一個數(shù)值，這樣就得出它們之間的差別與內(nèi)在聯(lián)系。模型四：允許缺貨(需補足缺貨)、生產(chǎn)需一定時間假設條件除允許缺貨生產(chǎn)需一定時間外，其余條件皆與模型一相同，其存儲變化如圖所示分析圖?。?，t］為一個周期，設t1時刻開始生產(chǎn)。［0,t2］時間內(nèi)存儲為零，B表示最大缺貨量。［t1,t2］時間內(nèi)除滿足需求外，補足［0,t1］時間內(nèi)的缺貨。［t2,t3］時間內(nèi)滿足需求后的產(chǎn)品進入存儲，存儲量以(P-R)速度增加。S表示存儲量，t3時刻存儲量達到最大，t3時刻停止生產(chǎn)。［t3,t］時間存儲量以需求速度R減少。

由圖易知：

最大缺貨量B=Rt1，或B=(P-R)(t2-t1)；即Rt1=(P-R)(t2-t1)，得最大存儲量S=(P-R)(t3-t2)，或S=R(t-t3)即(P-R)(t3-t2)=R(t-t3)，得在［0，t］時間內(nèi)所需費用：存儲費：將(16)式代入消去t3，得在［0，t］時間內(nèi)所需費用：缺貨費：將(15)式代入消去t1，得在［0，t］時間內(nèi)所需費用：裝配費：C3

在［0,t］時間內(nèi)總平均費用為：為了得到最佳公式，分別求偏導數(shù)：

推導由(18)式得，由(17)式得

推導：將(19)式代入上式消去t2得由(19)有公式S0(最大存儲量)B0(最大缺貨量)最小費用：

四隨機性存儲模型隨機性存儲模型的重要特點是需求為隨機的，其概率或分布為已知。在這種情況下，前面所介紹過的模型已經(jīng)不能適用了。例如商店對某種商品進貨500件，這500件商品可能在一個月內(nèi)售完，也有可能在兩個月之后還有剩余。商店如果想既不因缺貨而失去銷售機會，又不因滯銷而過多積壓資金，這時必須采用新的存儲策略可供選擇的策略主要有三種(1)定期訂貨，但訂貨數(shù)量需要根據(jù)上一個周期末剩下貨物的數(shù)量決定訂貨量。剩下的數(shù)量少，可以多訂貨。剩下的數(shù)量多，可以少訂或不訂貨。這種策略可稱為定期訂貨法。(2)定點訂貨，存儲降到某一確定的數(shù)量時即訂貨，不再考慮間隔的時間。這一數(shù)量值稱為訂貨點，每次訂貨的數(shù)量不變，這種策略可稱之為定點訂貨法。(3)把定期訂貨與定點訂貨綜合起來的方法，隔一定時間檢查一次存儲，如果存儲數(shù)量高于一個數(shù)值s，則不訂貨。小于s時則訂貨補充存儲，訂貨量要使存儲量達到S，這種策略可以簡稱為(s,S)存儲策略。與確定性模型不同的特點還有：不允許缺貨的條件只能從概率的意義方面理解，如不缺貨的概率為0.9等。存儲策略的優(yōu)劣通常以贏利的期望值的大小作為衡量的標準。為了講清楚隨機性存儲問題的解法，先通過一個例題介紹求解的思路。例6某商店擬在新年期間出售一批日歷畫片，每售出一千張可贏利700元。如果在新年期間不能售出，必須削價處理，作為畫片出售。由于削價，一定可以售完，此時每千張賠損400元。根據(jù)以往的經(jīng)驗，市場需求的概率見下表。每年只能訂貨一次，問應訂購日歷畫片幾千張才能使獲利的期望值最大?解如果該店訂貨4千張，我們計算獲利的可能數(shù)值訂購量為4千張時獲利的期望值：E[C(4)]=(-1600)×0.05+(-500)×0.10+600×0.25+1700×0.35+2800×0.15+2800×0.10=1315(元)上述計算法及結(jié)果列于下表

獲利期望值最大者標有(*)記號，為1440元?？芍摰暧嗁?000張日歷畫片可使獲利期望值最大。

從相反的角度考慮求解當訂貨量為Q時，可能發(fā)生滯銷賠損(供過于求的情況)，也可能發(fā)生因缺貨而失去銷售機會的損失(求過于供的情況)。把這兩種損失合起來考慮，取損失期望值最小者所對應的Q值。訂購量為2千張時，損失的可能值：當訂貨量為2千張時，缺貨和滯銷兩種損失之和的期望值E[C(2)]=(-800)×0.05+(-400)×0.10+0×0.25+(-700)×0.35+(-1400)×0.15+(-2100)×0.10=－745(元)按此算法列出下表。比較表中期望值以-485最大，即485為損失最小值。該店訂購