《管理運籌學》復習提綱

1、管理運籌學復習提綱管理運籌學復習提綱第1章 緒論（p1-p9)1.決策過程(解決問題的過程)（1）認清問題。（)找出一些可供選擇的方案。(3）確定目標或評估方案的標準。（）評估各個方案：解的檢驗、靈敏性分析等。（5)選出一個最優(yōu)的方案：決策。()執(zhí)行此方案:回到實踐中。(7）進行后評估：考察問題是否得到圓滿解決。其中:（1）(2）（3）形成問題。(4）(5)分析問題:定性分析與定量分析，構成決策2. 運籌學的分支:線性規(guī)劃、整數(shù)線性規(guī)劃、動態(tài)規(guī)劃、圖與網(wǎng)絡模型、存儲論、排隊論、排序與統(tǒng)籌方法、決策分析、對策論、預測、目標規(guī)劃，此外,還有多目標規(guī)劃、隨機規(guī)劃、模糊規(guī)劃等。3. 運籌學在工商管理中

2、的應用1）生產(chǎn)計劃:生產(chǎn)作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等,追求利潤最大化和成本最小化。2）庫存管理:多種物資庫存量的管理,某些設備的庫存方式、庫存量等的確定。）運輸問題：確定最小成本的運輸線路、物資的調撥、運輸工具的調度以及建廠地址的選擇等。4）人事管理:對人員的需求和使用的預測,確定人員編制、人員合理分配，建立人才評價體系等。5)市場營銷:廣告預算、媒介選擇、定價、產(chǎn)品開發(fā)與銷售計劃制定等。6)財務和會計:預測、貸款、成本分析、定價、證券管理、現(xiàn)金管理等。此外,還有設備維修、更新，項目選擇、評價,工程優(yōu)化設計與管理等。3. 學習管理運籌學必須使用相應的計算機軟件,必須

3、注重學以致用的原則。第二章 線性規(guī)劃的圖解法(p10p26)1一些典型的線性規(guī)劃在管理上的應用合理利用線材問題：如何在保證生產(chǎn)的條件下,下料最少；配料問題:在原料供應量的限制下如何獲取最大利潤;投資問題:從投資項目中選取方案，使投資回報最大;產(chǎn)品生產(chǎn)計劃:合理利用人力、物力、財力等，使獲利最大；勞動力安排:用最少的勞動力來滿足工作的需要;運輸問題：如何制定調運方案,使總運費最小。2.線性規(guī)劃的組成目標函數(shù):a f 或 minf ;約束條件：s.t(subject ),滿足于；決策變量:用符號來表示可控制的因素。3.建模過程(1)理解要解決的問題，明確在什么條件下，要追求什么目標。(2)定義決策

4、變量(x1,2 ，,x),每一組值表示一個方案。(3）用決策變量的線性函數(shù)形式寫出目標函數(shù)，確定最大化或最小化目標。()用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件。一般形式目標函數(shù)：ax(min）z 1 1+2 x+ +cnx約束條件:s.t a111+ 1 x2 + + a1n x （=， )b11 x1+a22 x2 + a2x (， )b2am1 x + a2 x2+ + amn x(=, ）bm1 ，x , ，xn 0對于只包含兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念,并求解。下面通過例 1詳細介紹圖解法的解題過程取各約束條

5、件的公共部分(如圖21(f）所示)。目標函數(shù) z =x1 + 100x2,當 z 取某一固定值時得到一條直線,直線上的每一點都具有相同的目標函數(shù)值,稱之為“等值線”。平行移動等值線,當移動到點時，在可行域內實現(xiàn)了最大化。a、b、c、d、e是可行域的頂點,有限個約束條件其可行域的頂點也是有限的。線性規(guī)劃的標準化內容之一引入松弛變量(資源的剩余量）例 中引入 s1，s2，3,模型變化為:4.重要結論如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應一個最優(yōu)解;無窮多個最優(yōu)解。若將例1 中的目標函數(shù)變?yōu)?maxz50x1+50,則線段 bc 上的所有點都代表了最優(yōu)解;無界解。即可行域的范圍延伸到無窮

6、遠，目標函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯,忽略了一些必要的約束條件；無可行解。若在例1 的數(shù)學模型中再增加一個約束條件 4x+320，則可行域為空域,不存在滿足約束條件的解,當然也就不存在最優(yōu)解了。線性規(guī)劃的標準化6.線性規(guī)劃的標準形式有四個特點：目標最大化;約束為等式；決策變量均非負；右端項非負。對于各種非標準形式的線性規(guī)劃問題,我們總可以通過變換,將其轉化為標準形式。.為了使約束由不等式成為等式而引進的變量，當不等式為“小于等于”時稱為“松弛變量”；當不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束,則將其轉化為標準形式時，必須對各個約束引進不同的松

7、弛變量或剩余變量。.靈敏度分析：在建立數(shù)學模型和求得最優(yōu)解之后,研究線性規(guī)劃的一個或多個參數(shù)(系數(shù)) , aj ，變化時,對最優(yōu)解產(chǎn)生的影響。一、目標函數(shù)中的系數(shù) ci 的靈敏度分析二、約束條件中常數(shù)項 bj 的靈敏度分析當約束條件中常數(shù)項bj 變化時,線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化。.考慮例 1 的情況:假設設備臺時增加 10個臺時，即 1變化為0,這時可行域擴大，最優(yōu)解為x2= 25和 x1 x2 10 的交點 x 6,x2 = 2。變化后的總利潤變化前的總利潤= 增加的利潤(5 60+10 20) （50 50+10 250) 50,50 /1= 5(元)說明在一定范圍內

8、每增加(或減少)個臺時的設備能力就可增加(或減少)0 元利潤,這稱為該約束條件的對偶價格。b假設原料 a 增加1 千克,即 b2 變化為 410，這時可行域擴大，但最優(yōu)解仍為x2=25 和x1 2= 0 的交點 x1 =0，x2 = 25。此變化對總利潤無影響，該約束條件的對偶價格為 0。解釋：原最優(yōu)解沒有把原料 a用盡,有 50 千克的剩余，因此增加 10千克只增加了庫存，而不會增加利潤。在一定范圍內，當約束條件中常數(shù)項增加 個單位時，（1)若約束條件的對偶價格大于0，則其最優(yōu)目標函數(shù)值得到改善（變好）;(）若約束條件的對偶價格小于 0,則其最優(yōu)目標函數(shù)值受到影響(變壞);(3）若約束條件的

9、對偶價格等于 0，則其最優(yōu)目標函數(shù)值不變。課本重點習題:6 習題 2 6 第3章 線性規(guī)劃問題的計算機求解(p27-38）1. 隨書軟件為“管理運籌學”2.5 版(widos 版）,是“管理運籌學”2.0版(windows版）的升級版。它包括：線性規(guī)劃、運輸2. 問題、整數(shù)規(guī)劃（0-1 整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃)、目標規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關鍵路徑、存儲論、排隊論、決策分析、預測問題和層次分析法，共5 個子模塊。3. “管理運籌學”軟件的輸出信息分析當有多個系數(shù)變化時，需要進一步討論。百分之一百法則:對于所有變化的目標函數(shù)決策系數(shù)（約束條件右端

10、常數(shù)值）,當其所有允許增加的百分比與允許減少的百分比之和不超過00%時,最優(yōu)解不變（對偶價格不變,最優(yōu)解仍是原來幾個線性方程的解）。在使用百分之一百法則進行靈敏度分析時,要注意以下幾方面。（1)當允許增加量(允許減少量)為無窮大時，則對任意增加量(減少量）,其允許增加（減少）百分比均看作零。()百分之一百法則是充分條件，但非必要條件；也就是說超過 100%,最優(yōu)解或對偶價格并不一定變化。(3)百分之一百法則不能用于目標函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時變化的情況。這種情況下，只能重新求解。在松弛/剩余變量欄中，約束條件 2 的值為 125,它表示對原料 a 的最低需求，即對 a 的剩余變

11、量值為 25；同理可知約束條件1的剩余變量值為 0；約束條件 3的松弛變量值為 0。在對偶價格欄中，約束條件 的對偶價格為 1 萬元,也就是說如果把加工時數(shù)從600 小時增加到 01小時,則總成本將得到改進，由 800萬元減少到 799 萬元。也可知約束條件 1的對偶條件為-4 萬元,也就是說如果把購進原料 a 和 的總量下限從 50t增加到1t，那么總成本將增加,由 800萬元增加到 804 萬元。當然如果減少對原料 a和b 的總量的下限,那么總成本將得到改進。在常數(shù)項范圍一欄中，知道當約束條件 1的常數(shù)項在300 到 45 范圍內變化,且其他約束條件不變時，約束條件 的對偶價格不變,仍為-

12、4；當約束條件 2 的常數(shù)項在負無窮到 0 范圍內變化,且其他約束條件的常數(shù)項不變時，約束條件 的對偶價格不變，仍為 ；當約束條件 3 的常數(shù)項在 75到 70 范圍內變化,且其他約束條件的常數(shù)項不變時,約束條件 3 的對偶價格不變，仍為 1。3.注意（1)當約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標函數(shù)值增加的數(shù)量稱為影子價格。在求目標函數(shù)最大值時，當約束條件中的常數(shù)項增加一個單位時,目標函數(shù)值增加的數(shù)量就為改進的數(shù)量,此時影子價格等于對偶價格;在求目標函數(shù)最小值時，改進的數(shù)量就是減少的數(shù)量,此時影子價格即為負的對偶價格。()管理運籌學”軟件可以解決含有100 個變量 50 個約束方程的線性

13、規(guī)劃問題，可以解決工商管理中大量的問題。如果想要解決更大的線性規(guī)劃問題,可以使用由芝加哥大學的 .e.schge開發(fā)的 lido 計算機軟件包的微型計算機版本lido/pc。課本重點習題：p- 習題 4第4章 線性規(guī)劃在工商管理中的應用（p39-p66)包括:人力資源分配的問題 生產(chǎn)計劃的問題 套裁下料問題 配料問題 投資問題1人力資源分配問題例 1某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數(shù)如表 4-所示。設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作 8h,問該公交線路怎樣安排司機和乘務人員,既能滿足工作需要,又使配備最少司機和乘務人員的人數(shù)最少?例 2一家中型的百貨商場

14、對售貨員的需求經(jīng)過統(tǒng)計分析如表 4-2 所示。為了保證售貨員充分休息,要求售貨員每周工作五天,休息兩天,并要求休息的兩天是連續(xù)的。問應該如何安排售貨員的休息日期，既滿足工作需要，又使配備的售貨員的人數(shù)最少?2 生產(chǎn)計劃的問題例 .某公司面臨一個是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品,這三種產(chǎn)品都需要經(jīng)過鑄造、機加工和裝配三道工序。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質量。數(shù)據(jù)如表 4- 所示。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件?甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和外包協(xié)作各應多少件?解:設 x1，x,x3 分

15、別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù),4,x5 分別為由外包協(xié)作鑄造再由本公司進行機械加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。每件產(chǎn)品的利潤如下：可得到 xi （i = ,3,4,5)的利潤分別為 15 元、0 元、7 元、3元、9 元。該公司的最大利潤為 2 40元最優(yōu)的生產(chǎn)計劃為全部由自己生產(chǎn)的產(chǎn)品甲 1 600 件,鑄造工序外包而其余工序自行生產(chǎn)的產(chǎn)品乙600件。例 4永久機械廠生產(chǎn)、三種產(chǎn)品，均要經(jīng)過、 兩道工序加工。設有兩種規(guī)格的設備a1、a2 能完成 工序;有三種規(guī)格的設備 b1、b2、b3 能完成 b 工序。產(chǎn)品可在a、b的任何規(guī)格的設備上加工；產(chǎn)品可在工序 a 的任何

16、一種規(guī)格的設備上加工，但對 b 工序，只能在 b 設備上加工;產(chǎn)品只能在 a2 與b2 設備上加工。數(shù)據(jù)如表 4 所示。問:為使該廠獲得最大利潤，應如何制定產(chǎn)品加工方案?解:設 xk 表示第i種產(chǎn)品,在第j 種工序上的第 種設備上加工的數(shù)量。建立如下的數(shù)學模型。目標函數(shù)為計算利潤最大化,利潤的計算公式為:利潤= （銷售單價 原料單價） 產(chǎn)品件數(shù)之和（每臺時的設備費用 設備實際使用的總臺時數(shù))之和。這樣得到目標函數(shù)：max (.50.5) (x111x11) +(03）(x21） +(2.800.） x32 3/6 000(5x11+0x21）-3110 000 （7x1129x2212x312

17、)-250/ 000(6x11+x21)-783/7 000(4x122+11x322）2/4 00（12).經(jīng)整理可得：max0.75x1+0.775 3x121.5x21+.361212+194 8x3120.37x21-0.5x21-0. 41221.230 x22.35123*該廠的最大利潤為 116.6005 元。 套裁下料問題例5某工廠要做 10 套鋼架，每套用長為 .9 m,. m,1.5 的圓鋼各一根。已知原料每根長 7.4 m，問:應如何下料,可使所用原料最?。拷猓汗部稍O計下列 8 種下料方案,如表5所示。設 x, , x3, x4, ， x6, x, x8 分別為上面 8

18、種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學模型。用管理運籌學軟件計算得出最優(yōu)下料方案:按方案1 下料 0 根；按方案 2下料 10 根；按方案4下料 50 根。即:x=3; x2=0； 3=；x45; x5;x6=x7= x8只需 90 根原材料就可制造出 100 套鋼架。注意:在建立此類型數(shù)學模型時,約束條件用大于等于號比用等于號要好。因為有時在套用一些下料方案時可能會多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號，這一方案就不是可行解了。若可能的下料方案太多,可以先設計出較好的幾個下料方案。首先要求每個方案下料后的料頭較短；其次方案總體能裁下所有各種規(guī)格的圓鋼，且不同方案有著

19、不同的各種所需圓鋼的比。這樣套裁即使不是最優(yōu)解，也是次優(yōu)解，也能滿足要求并達到省料目的。如我們用前 5種下料方案供套裁用，進行建模求解,也可得到上述最優(yōu)解。5 配 料 問 題例 6某工廠要用三種原料1、2、 混合調配出三種不同規(guī)格的產(chǎn)品甲、乙、丙,數(shù)據(jù)如表4-6和表47所示。問：該廠應如何安排生產(chǎn),使利潤最大?解：設ij 表示第 種(甲、乙、丙）產(chǎn)品中原料 j的含量。這樣我們建立數(shù)學模型時，要考慮:對于甲：11，x,x；對于乙:x1，x2,x23;對于丙：x3,32，x33;對于原料 :1,x21，x3;對于原料 2：x2,x，x3;對于原料 3:x,x3,x33；目標函數(shù):利潤最大,利潤=

20、收入 原料支出約束條件:規(guī)格要求 個；供應量限制個。利潤總收入-總成本=甲、乙、丙三種產(chǎn)品的銷售單價 產(chǎn)品數(shù)量甲、乙、丙使用的原料單價 原料數(shù)量。故有:目標函數(shù)：約束條件:從表 -6中可知x115(x11+x12+x3）10.2(x11+1+x13)x210.25（21+x22+x3)x225（x2+22+x23)從表 47中可知，生產(chǎn)甲、乙、丙的原材料不能超過原材料的供應限額，故有11x2+x31100x12+x2+3210x13+x23x3360通過整理,得到以下模型:目標函數(shù)：mz -5x11+2x1+5x13-3021+122-4x310x33約束條件:線性規(guī)劃的計算機解為x1 = 1

21、00,x2 50，x13 5，其余的 xj =0,也就是說每天只生產(chǎn)產(chǎn)品甲 00 g,分別需要用第 1 種原料 0 g，第 種原料 5k,第 種原料 0kg。6 投 資 問題例 某部門現(xiàn)有資金 20 萬元，今后五年內考慮給以下的項目投資。項目 a:從第一年到第五年每年年初都可投資，當年末能收回本利10%;項目 b：從第一年到第四年每年年初都可投資，次年末能收回本利 125%，但規(guī)定每年最大投資額不能超過 30 萬元；項目 ：第三年年初需要投資,第五年末能收回本利4%,但規(guī)定最大投資額不能超過80萬元;項目 d:第二年年初需要投資，第五年末能收回本利 155%，但規(guī)定最大投資額不能超過 100

22、萬元。據(jù)測定每次投資 萬元的風險指數(shù)如右表4-0 所示:問:(）應如何確定這些項目每年的投資額,使得第五年年末擁有資金的本利金額最大？ （2）應如何確定這些項目每年的投資額,使得第五年年末擁有資金的本利在 30萬元的基礎上總的風險系數(shù)最小? 所設變量與問題相同，目標函數(shù)為風險最小，有mn =x11x1+x31+x41x1+3(x12+x22+x32x2)+4335.x2在問題的約束條件中加上“第五年末擁有資金本利在3 萬元”的條件，于是模型如下。min f= (11+x31x41+1） +(12x22x32+x2)33+5.x2st. x11+ x12 =2x2 + x2+x24 = 1.1x

23、11；x31 + 3+33 = 1.1x21+ 1.25x2；x1 x42 =11x31+ .25x22；51 =1141+1.25x2；2 30 ( =1,2，,4 )，33 ,x24 101x + 1.2x4+ 1.43+ 24330xi 0( 1,2,3，4，5; = 、2、)運用“管理運籌學”軟件求得此問題的解為:5a=33.5,x0,3c,2d=100，1a0，x1b=，x=5,x2b0，x3a=0,3b=20.2,x4.5。課本重點習題:7-6習題1 3 4 5 6第七章 運輸問題(26-p62)1 運 輸模型例 1. 某公司從兩個產(chǎn)地a1、a2 將物品運往三個銷地1、2、b3，各

24、產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地的每件物品的運費如表 -1 所示,問:應如何調運可使總運輸費用最??？一般運輸問題的線性規(guī)劃模型：產(chǎn)銷平衡a、2、am 表示某物資的 m個產(chǎn)地;、b、b表示某物質的n 個銷地;si 表示產(chǎn)地a的產(chǎn)量；dj 表示銷地 bj 的銷量;cij 表示把物資從產(chǎn)地 a 運往銷地 bj 的單位運價。設 xij為從產(chǎn)地 ai 運往銷地 bj 的運輸量,得到下列一般運輸量問題的模型：變化:(）有時目標函數(shù)求最大。如求利潤最大或營業(yè)額最大等。(2)當某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)。(3)產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時

25、)或銷地(產(chǎn)大于銷時)。2 運輸問題的計算機求解例 2. 某公司從兩個產(chǎn)地 1、a 將物品運往三個銷地 1、b2、b,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表7-3所示,問：應如何調運可使總運輸費用最??？解：增加一個虛設的銷地運輸費用為 0。例 3. 某公司從兩個產(chǎn)地a1、a2 將物品運往三個銷地 b1、b、3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表- 所示，問:應如何調運可使總運輸費用最??？解:增加一個虛設的產(chǎn)地運輸費用為 0。3 運輸問題的應用4 運輸問題的表上作業(yè)法1、數(shù)學模型在物流調運問題中，如何根據(jù)已有的交通網(wǎng)，制定調運方案，將貨物運到各

26、需求地，而使總運費最小，是很關鍵的問題。這類問題可用如下數(shù)學語言描述。已知有個生產(chǎn)地點ai（=1，2),可供應某種物質,其供應量分別為：ai(i=,2,3,m）,有n個銷地（需要地）b(j=，n）,其需求量分別為bj（j1，,n)，從ai到bj運輸單位物資的運價為cij。這些數(shù)據(jù)可匯總于產(chǎn)銷平衡表和單位運價表中，如表71、表72所示。表7-1 產(chǎn)銷平衡表 銷地產(chǎn)地1,2n產(chǎn)量1a12amam銷量b,bbn表7-2 單位運價表 銷地產(chǎn)地2nc11c12c12c212c2nmcm1cm2cmn為了制定使總運費最小的調運方案，我們可以建立數(shù)學模型。如果我們設xj表示由產(chǎn)地ai供應給銷地的運量,則運輸

27、問題的線性規(guī)劃模型可分為三種情況：（1） 產(chǎn)銷平衡，即在的情況下,求（總費用最少)。滿足約束條件: 1,2,n)（滿足各銷地的需要量） ,2,，m)（各產(chǎn)地的發(fā)出量等于各地產(chǎn)量） xij(i=1,，；=,2,，n)（調出量不能為負數(shù)）()產(chǎn)大于銷，即在的情況下，求（總費用最少)。滿足約束條件: ，2，,n) ai(i=1,2，m） xi0(i，,m;j=，2，,n)（3）銷大于產(chǎn)，即在的情況下,求（總費用最少)。滿足約束條件：bj（j1，2，) =a（i1，2，m） xj0(i1，2,，m；，,n）物資調運問題可采用圖上作業(yè)法或表上作業(yè)法求其最佳的調運方案。2、物資調運問題的表上作業(yè)法物資調運

28、的表上作業(yè)法，是指在物資調運平衡表上確定物資調運最優(yōu)方案的一種調運方法。利用表上作業(yè)法，尋求運費最少的運輸方案，其步驟可歸納如下:（1)列出運輸物資平衡表及運價表；（）在表上做出初始方案；（3)檢查初始方案是否為最優(yōu)方案;(4)調整初始方案得到最優(yōu)解。一般說來，每調整一次得到一個新的方案,而這個新方案的運費比前一個方案要少一些,如此經(jīng)過幾次調整，最后可以得到最優(yōu)方案。下面舉例說明:某公司有三個儲存某種物資的倉庫,供應四個工地的需要。三個倉庫的供應量和四個工地的需求量以及由各倉庫到各工地調運單位物資的運價（元/噸）,如表-3所示,試求運輸費用最少的合理運輸方案。表73 供需情況和單位運價 工地運

29、價(元/噸)倉庫bb3b4供應量(t）13110700928400a374150需求量3000求解步驟如下:（1)列出調運物資平衡表-4和運價表7-5表7- 物資平衡表 需供b12b3b4供應量(t)a70200a90需求量（t)300表7- 運價表 工地運價倉庫1b2bba131130a298a3741 平衡表和運價表是表上作業(yè)法的基本資料和運算的依據(jù)。表上作業(yè)法的實質就是利用運價表在平衡表上進行求解。為了敘述和考慮問題的方便，通常把上面的平衡表看作為矩陣，并把表中的方格記為(i，)的形式。如（2，）表示第二行第三列的方格；（1，4)表示第一行第四列的方格等。此外,在求解過程中，如果平衡表的

30、(2，1)方格中表寫上300,即表示a2倉庫調運300噸物質到第一個工地。(2)編制初始調運方案一般最優(yōu)方案是由初始方案經(jīng)過反復調整得到的。因此，編制出較好的初始調運方案顯得非常重要。確定初始方案通常有兩種方法:一是西北角法,二是最小元素法。西北角法。從供需平衡表的西北角第一格開始，按集中供應的原則，依次安排調運量。由于集中供應，所以未填數(shù)值的格子的xj均為0，從而得到一個可行方案。按西北角法，本例的初始運輸方案如表所示。表76 初始方案 需供b12b3b供應量(t）a130040000a22000040a300090需求量(t）3200由ab1余400；b40缺200；a2b200余00;a

31、2320缺30;3b3300余00;a30余0。此時運輸總成本為:s3003+40112009200200+6005=350(元） 最小元素法。所謂最小元素法,就是按運價表一次挑選運費小的供需點盡量優(yōu)先安排供應的運輸方法。首先針對具有最小運輸成本的路徑,并且最大限度地予以滿足;然后按“最低運輸成本優(yōu)先集中供應”的原則，依次安排其他路徑的運輸量。仍以上述實例,具體做法是在表7-5 上找出最小的數(shù)值（當此數(shù)值不止一個時,可任意選擇一個,方格（2，1）數(shù)值是1,最小。這樣，參考盡可能滿足1工地的需求,于是在平衡表中有(2，）30,即在空格(2,1）中填入數(shù)字30,此時由于工地b1已全部得到滿足，不再

32、需求a和a3倉庫的供應,運價表中的第一列數(shù)字已不起作用，因此將原運價表75的第一列劃去，并標注（如表7-5所示）。然后,在運價表未劃去的行、列中，再選取一個最小的數(shù)值,即（,3)=2,讓2倉庫盡量滿足b3工地的需求。由于a2倉儲量0噸已供給b1工地30噸,所以最多只能供應3工地10噸。于是在平衡表(2,3)左格填入100。相應地，由于倉庫a所儲物資已全部供應完畢，因此,在運價表中與a2同行的運價也已不再起作用，所以也將它們劃去，并標注,仿照上面的方法，一直作下去,得表7-7。此時，在運價表中只有方格（1，4)處的運價表沒有劃掉，而4尚有300噸的需求，為了滿足供需平衡,所以最后在平衡表上應有（

33、,4)=00,這樣就得到表-8的初始調運方案。表中填有數(shù)字的方格右上角是其相應的運價（元噸）。根據(jù)得到的初始調運方案，可以計算其運輸費用。(元)表7-7供需量的分配 需供bb2b3b4供應量(t)1400700a2 300 00400a36003000需求量()32000表7-8初始調運方案 需供b1b23b4供應量（)43000700a2301100240a30430590需求量(t）200對于應用最小元素法編制初始方案說明以下幾點： 應用最小元素法編制初始調運方案，這里的“最小”是指局部而言，而整體考慮的運費不見得一定是最小的。 特別需要指出,并不是任意一個調運方案都可以作為表上作業(yè)法的初

34、始方案。可以作為初始方案的調運方案，其填有數(shù)字的方格將恰好是(行數(shù)m列數(shù)n-）個,在我們這個例子中為(+41=6），因此,可以作為初始調運方案提出。但是，在制定初始方案有時會碰到按最小元素所確定的方格中,其相應的供應點再無物資可供應或需求點已全部得到滿足的情況，此時平衡表上填有數(shù)字的方格數(shù)小于（m+n-1）。我們規(guī)定,在未填有數(shù)字的方格中必須填上一個，并將這和其他發(fā)生供需關系的格子同樣看待,而不能作為空格，其目的是保證使填有數(shù)字的方格數(shù)等于（m+1)的要求。下面用一個例子來說明上述情況的處理。表9和表710給出了一個物資調運問題，運用最小元素經(jīng)過三次運算后，得到下面表1和表-1。表79供需平衡

35、表 產(chǎn)地銷地b1b2b3供應量（t)a110a20a0需求量(t)10400表710 運價表銷地 運價 產(chǎn)地1b2a1122a2313a1可以看出,表7-13雖然構成了一個調運方案。但在運價表中,(，3)及（2,）方格尚未被劃去,所以在平衡表-12中,方格(1，3）及（2，3)處在各填上一個“0”,隨后得表7-13,表7-13填有數(shù)字(包括0)的方格數(shù)恰是3+3-1=,如此才可以構成調運問題的初始方案。表7-11 運價表銷地運價產(chǎn)地bb2b32a2313a32表7-12 供需平衡表 產(chǎn)地銷地b1b2b3供應量()a11010a2003040需求量（t)10204070表7-13 初始調用方案

36、產(chǎn)地銷地b2b3供應量（t)10010a22020a3040需求量(t）102007（)初始方案的檢驗在制定了初始調運方案之后,需要對它進行檢驗，如果制定的初始調運方案不是最優(yōu)方案,需要對其進行調整直到獲得最優(yōu)調運方案。運輸問題表上作業(yè)法，判斷調運方案是否為最優(yōu)解,有兩種方法:一種叫做閉回路法,另一種是位勢法。閉合回路法。對于表上作業(yè)法的初始方案來說，從調運方案表上的一個空格出發(fā),存在一條且僅一條以某空格（用表示)為起點，以其他填有數(shù)字的點為其他頂點的閉合回路,簡稱閉回路。這個閉回路具有以下性質：第一,每個頂點都是轉角點；第二，閉合回路是一條封閉折線,每一邊條都是水平或垂直的;第三，每一行（列

37、）若有閉合回路的頂點，則必有兩個。只有從空格出發(fā)，其余各轉角點所對應的方格內均填有數(shù)字時,所構成的閉合回路,才是我們所說的閉回路；另外，過任一空格的閉回路不僅是存在的，而且是惟一的。下面以表-8給定的初始調運方案為例，說明閉回路的性質，表-14給出了空格，(1，1）和（，)所形成的閉回路:(1，1）(1，3)(2,3)（2,1）(，1)(3,1)（2,1）（,3)(1,)(1，4）(3,4）（3,）表7-14 初始調運方案 需供1b4供應量(）a1400300700a230010400a36030090需求量(t）000050600200其他空格的閉回路與此同理。在調運方案內的每個空格所形成的

38、閉回路上,作單位物資的運量調整,總可以計算出相應的運費是增加還是減少。我們把所計算出來的每條閉回路上調整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。檢驗數(shù)的求法，就是在閉回路上,從空格出發(fā)，沿閉回路,將各頂點的運輸成本依次設置“+”、“-”，交替正負符號,然后求其代數(shù)和。這個代數(shù)和數(shù)字稱為檢驗數(shù),用i表示。例如,上述表格上的檢驗數(shù)1131+91=0。用同樣的方法可以求其他空格的檢驗數(shù)，見表7-15。如果檢驗數(shù)小于0,表示在該空格的閉合回路上調整運量使運費減少；相反，如果檢驗數(shù)大于0，則會使運費增加。因此調運方案是否是最優(yōu)方案的判定標準就是:初始調運方案,如果它所有的檢驗數(shù)都是非負的，那

39、么這個初始調運方案一定最優(yōu)。否則,這一調運方案不一定是最優(yōu)的。表7-1 檢驗數(shù)計算 需供bb4供應量（）a103+2140010a23001+102-403+760400590需求量（）200 位勢法。用該調運問題的相對運價減去表7-7中的數(shù)值，那么對初始方案中每個填有運量數(shù)值的方格來說，都會滿足 （7-1）而對每個空格來說,相應得到的數(shù)值就是該空格的檢驗數(shù),即 （72）上式就是用位勢法來求檢驗數(shù)的公式。本例中,設cij(i=1，2,；=1,3,4）表示變量ij相應的運價,將初始調運方案中填有數(shù)字方格的cij分解成兩部分:其中u和v分別稱為該方格對應i行和j列的位勢量，因為有m3行,j有n=4

40、列,故位勢的個數(shù)有m+=3+4=個。但填有運量數(shù)的單元只有m+1=6個，這樣,mn-1=6個cij的方程，要解出mn=個未知的位勢量,和j可以有很多解。所以,可以先任意給定一個未知數(shù)的位勢量，如表16所示。表16 位勢計算表 需點供點ui31u1b12u2=1c45u3=-3vjv10v=73=v4=表717 準檢驗數(shù) 需點供點ua20u1=2b1829u2=1-34253=jv1=02=3=1v4=810，則由1=2v11，可以得到u2=1,再由c3=2,又得到1；由c3=3，可得u1=2，依次可以得到v4=,3=-3,2=等。由上面所求出的行位勢量uj與列位勢量v對應相加，得到準檢驗數(shù)，如

41、表所示。表中帶有 者為初始調運方案表里的空格。按照位勢法計算本例初始調運方案的檢驗數(shù)，計算結果如表18所示。在本例中,由于檢驗數(shù)出現(xiàn)負值,依照最優(yōu)方案判定準則，可知初始調運方案不一定是最優(yōu)的，需要進行調整。表7-18 檢驗數(shù)表 需點供點a1b-1c112（4） 調運方案的調整當判定一個初始調運方案不是最優(yōu)調運方案時，就要在檢驗出現(xiàn)負值的該空格內進行調整。如果檢驗數(shù)是負值的空格不止一個時，一般選擇負檢驗數(shù)絕對值大的空格作為具體調整對象。具體調整的方法仍用前例加以說明。由于從初始調運方案的檢驗數(shù)表7-18中發(fā)現(xiàn),空格x4的檢驗數(shù)是負數(shù)，因此對其進行調整,具體過程如表-19所示。表19 調運方案調整

42、表 x x14 00+0=500 3001020 23 x 100-100=0 0+100=0從空格x24開始,沿閉回路在各奇數(shù)次轉角點中挑選運量的最小數(shù)值作為調整量。本例是將x23方格的10作為調整量,將這個數(shù)值填入空格x24內,同時調整該閉合回路中其他轉角點上的運量,使各行、列保持原來的供需平衡，這樣便得到一個新的調整方案,如表7-20所示。按新方案計算調運物資的運輸費用為：（元)表7-20調整后的方案 需供1bb3b4供應量(t）15a230a76需求量(t）3000新方案是否是最優(yōu)方案，還要對它再進行檢驗。經(jīng)計算，該新方案的所有檢驗數(shù)都是非負的，說明這個方案已是最優(yōu)調運方案了。綜上所述

43、，采用表上作業(yè)法求解平衡運輸問題的物資調運最優(yōu)方案的步驟如圖7-1所示。課本重點習題:15316習題1 2 第十三章 存儲論（p28-p324）存儲論主要解決存儲策略問題,即如下兩個問題。（1)補充存儲物資時，每次補充數(shù)量（q)是多少?（）應該間隔多長時間(t）來補充這些存儲物資?建立不同的存儲模型來解決上面兩個問題,如果模型中的需求率、生產(chǎn)率等一些數(shù)據(jù)皆為確定的數(shù)值時，存儲模型被稱為確定性存儲模型;如果模型中含有隨機變量則被稱為隨機性存儲模型。1 經(jīng)濟訂購批量存儲模型經(jīng)濟訂購批量存儲模型，又稱不允許缺貨，生產(chǎn)時間很短存儲模型，是一種最基本的確定性存儲模型。在這種模型里，需求率即單位時間從存儲

44、中取走物資的數(shù)量,是常量或近似乎常量;當存儲降為零時，可以立即得到補充并且所要補充的數(shù)量全部同時到位(包括生產(chǎn)時間很短的情況,我們可以把生產(chǎn)時間近似地看成零）。這種模型不允許缺貨，并要求單位存儲費，每次訂購費,每次訂貨量都是常數(shù),分別為一些確定的、不變的數(shù)值。例1 益民食品批發(fā)部是個中型的批發(fā)公司,它為附近 200 多家食品零售店提供貨源。批發(fā)部的負責人為了減少存儲的成本,他選擇了某種品牌的方便面進行調查研究，制定正確的存儲策略。下面為過去2 周的該品牌方便面的需求數(shù)據(jù)。過去12 周里每周的方便面需求量并不是一個常量，即使以往 周里每周需求量是一個常量 ，而以后時間里需求量也會出現(xiàn)一些變動,但

45、由于其方差相對來說很小，我們可以近似地把它看成一個常量,即需求量每周為 300箱,這樣的處理是合理的和必要的。計算存儲費:每箱存儲費由兩部分組成，第一部分是購買方便面所占用資金的利息,如果資金是從銀行貸款,則貸款利息就是第一部分的成本;如果資金是自己的,則由于存儲方便面而不能把資金用于其他投資,我們把此資金的利息稱為機會成本,第一部分的成本也應該等于同期的銀行貸款利息。方便面每箱30 元,而銀行貸款年利息為 12%,所以每箱方便面存儲一年要支付的利息款為36 元。第二部分由儲存?zhèn)}庫的費用、保險費用、損耗費用、管理費用等構成,經(jīng)計算每箱方便面儲存一年要支付費用 2.4 元，這個費用占方便面進價

46、30元的8%。把這兩部分相加,可知每箱方便面存儲一年的存儲費為6 元，即 c1= 6 元/年箱，占每箱方便面進價的 0%。計算訂貨費：訂貨費指訂一次貨所支付的手續(xù)費、電話費、交通費、采購人員的勞務費等,訂貨費與所訂貨的數(shù)量無關。這里批發(fā)部計算的每次的訂貨費為 c3= 元/次。這種存儲模型的特點如下。（1)需求率（單位時間的需求量)為d;(2）無限供貨率(單位時間內入庫的貨物數(shù)量）;（3）不允許缺貨；（4)單位貨物單位時間的存儲費 1;（)每次的訂貨費 c3；（6）每期初進行補充,即期初存儲量為 q。單位時間內總費用=單位時間內的存儲費用單位時間內的訂貨費用單位時間內的存儲費用=單位時間內購買貨物所占用資金的利息儲存?zhèn)}庫的費用+保險費用+損耗費用管理費用等設每次的訂貨量為q，由于補充的貨物全部同時到位，故 0 時刻的存儲量為q。到t 時刻存儲量為0，則0到 t 時間內的平均存儲量為 q/2。又設單位時間內的總需求量為 d，單位貨物的進價成本即貨物單價為 c,則靈敏度分析:批發(fā)部負責人在得到了最優(yōu)方案存儲策略之后。他開始考慮這樣一個問題:這個最優(yōu)存儲策略是在每次訂貨費為 25 元,每年單位存儲費6元，或占每箱方便面成本價格 3元的 （稱之為存儲率)的情況下求得的。一旦每次訂貨費或存儲率預測值有誤差,那么最優(yōu)存儲策略會有多大的變化呢?這就是靈敏度分析。為此,我們用管理運籌學軟件計算了