管理運籌學(xué)復(fù)習(xí)提綱

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

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

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

4、）定義決策變量（x1 ，x2 ，xn），每一組值表示一個方案。（3）用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)。（4）用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件。一般形式目標(biāo)函數(shù)：max（min）z = c1 x1 + c2 x2 + +xn約束條件：s.t.a11 x1 + a12 x2 + + a1n xn （=, ）b1a21 x1 + a22 x2 + + a2n xn （=, ）b2am1 x1 + am2 x2 + + amn xn （=, ）bmx1 ，x2 ， ，xn 0對于只包含兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示

5、線性規(guī)劃問題的有關(guān)概念，并求解。下面通過例 1 詳細(xì)介紹圖解法的解題過程取各約束條件的公共部分（如圖 2-1（f）所示）。目標(biāo)函數(shù) z = 50x1 + 100x2，當(dāng) z 取某一固定值時得到一條直線，直線上的每一點都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動等值線，當(dāng)移動到 B 點時，z 在可行域?qū)崿F(xiàn)了最大化。A、B、C、D、E是可行域的頂點，有限個約束條件其可行域的頂點也是有限的。線性規(guī)劃的標(biāo)準(zhǔn)化容之一引入松弛變量（資源的剩余量）例 1 中引入 s1，s2，s3，模型變化為：4.重要結(jié)論如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應(yīng)一個最優(yōu)解；無窮多個最優(yōu)解。若將例 1 中的目標(biāo)

6、函數(shù)變?yōu)?max z=50x1+50x2，則線段 BC 上的所有點都代表了最優(yōu)解；無界解。即可行域的圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。若在例 1 的數(shù)學(xué)模型中再增加一個約束條件 4x1+3x21200，則可行域為空域，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。5.線性規(guī)劃的標(biāo)準(zhǔn)化6.線性規(guī)劃的標(biāo)準(zhǔn)形式有四個特點：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項非負(fù)。對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式。7.為了使約束由不等式成為等式而引進(jìn)的變量 s，當(dāng)不等式為“小于等于”時稱為“松

7、弛變量”；當(dāng)不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的松弛變量或剩余變量。8.9.靈敏度分析：在建立數(shù)學(xué)模型和求得最優(yōu)解之后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）ci , aij , bj 變化時，對最優(yōu)解產(chǎn)生的影響。一、目標(biāo)函數(shù)中的系數(shù) ci 的靈敏度分析二、約束條件中常數(shù)項 bj 的靈敏度分析當(dāng)約束條件中常數(shù)項 bj 變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化。A.考慮例 1 的情況：假設(shè)設(shè)備臺時增加 10 個臺時，即 b1 變化為 310，這時可行域擴大，最優(yōu)解為 x2 = 250 和 x1 + x

8、2 = 310 的交點 x1 = 60，x2 = 250。變化后的總利潤 變化前的總利潤 = 增加的利潤(50 × 60+ 100 × 250) (50 × 50+100 × 250) = 500，500 / 10 = 50（元）說明在一定圍每增加（或減少）1 個臺時的設(shè)備能力就可增加（或減少）50 元利潤，這稱為該約束條件的對偶價格。B.假設(shè)原料 A 增加 10 千克，即 b2 變化為 410，這時可行域擴大，但最優(yōu)解仍為 x2 = 250 和 x1 + x2 = 300 的交點 x1 = 50，x2 = 250。此變化對總利潤無影響，該約束條件的對偶

9、價格為 0。解釋：原最優(yōu)解沒有把原料 A 用盡，有 50 千克的剩余，因此增加 10千克只增加了庫存，而不會增加利潤。在一定圍，當(dāng)約束條件中常數(shù)項增加 1 個單位時，（1）若約束條件的對偶價格大于 0，則其最優(yōu)目標(biāo)函數(shù)值得到改善（變好）；（2）若約束條件的對偶價格小于 0，則其最優(yōu)目標(biāo)函數(shù)值受到影響（變壞）；（3）若約束條件的對偶價格等于 0，則其最優(yōu)目標(biāo)函數(shù)值不變。課本重點習(xí)題：P23-26 習(xí)題1 2 6 8第3章 線性規(guī)劃問題的計算機求解(P27-P38)1. 隨書軟件為“管理運籌學(xué)”2.5 版（Windows 版），是“管理運籌學(xué)”2.0 版（Windows 版）的升級版。它包括：線性

10、規(guī)劃、運輸2. 問題、整數(shù)規(guī)劃（0-1 整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關(guān)鍵路徑、存儲論、排隊論、決策分析、預(yù)測問題和層次分析法，共 15 個子模塊。3. “管理運籌學(xué)”軟件的輸出信息分析當(dāng)有多個系數(shù)變化時，需要進(jìn)一步討論。百分之一百法則：對于所有變化的目標(biāo)函數(shù)決策系數(shù)（約束條件右端常數(shù)值），當(dāng)其所有允許增加的百分比與允許減少的百分比之和不超過100%時，最優(yōu)解不變（對偶價格不變，最優(yōu)解仍是原來幾個線性方程的解）。在使用百分之一百法則進(jìn)行靈敏度分析時，要注意以下幾方面。（1）當(dāng)允許增加量（允許減少量）為無窮大時，則對任意增

11、加量（減少量），其允許增加（減少）百分比均看作零。（2）百分之一百法則是充分條件，但非必要條件；也就是說超過 100%，最優(yōu)解或?qū)ε純r格并不一定變化。（3）百分之一百法則不能用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時變化的情況。這種情況下，只能重新求解。在松弛/剩余變量欄中，約束條件 2 的值為 125，它表示對原料 A 的最低需求，即對 A 的剩余變量值為 125；同理可知約束條件 1 的剩余變量值為 0；約束條件 3 的松弛變量值為 0。在對偶價格欄中，約束條件 3 的對偶價格為 1 萬元，也就是說如果把加工時數(shù)從 600 小時增加到 601 小時，則總成本將得到改進(jìn)，由 800萬元

12、減少到 799 萬元。也可知約束條件 1 的對偶條件為-4 萬元，也就是說如果把購進(jìn)原料 A 和 B 的總量下限從 350t 增加到 351t，那么總成本將增加，由 800 萬元增加到 804 萬元。當(dāng)然如果減少對原料 A和 B 的總量的下限，那么總成本將得到改進(jìn)。在常數(shù)項圍一欄中，知道當(dāng)約束條件 1 的常數(shù)項在 300 到 475 圍變化，且其他約束條件不變時，約束條件 1 的對偶價格不變，仍為-4；當(dāng)約束條件 2 的常數(shù)項在負(fù)無窮到 250 圍變化，且其他約束條件的常數(shù)項不變時，約束條件 2 的對偶價格不變，仍為 0；當(dāng)約束條件 3 的常數(shù)項在 475 到 700 圍變化，且其他約束條件的

13、常數(shù)項不變時，約束條件 3 的對偶價格不變，仍為 1。3.注意（1）當(dāng)約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標(biāo)函數(shù)值增加的數(shù)量稱為影子價格。在求目標(biāo)函數(shù)最大值時，當(dāng)約束條件中的常數(shù)項增加一個單位時，目標(biāo)函數(shù)值增加的數(shù)量就為改進(jìn)的數(shù)量，此時影子價格等于對偶價格；在求目標(biāo)函數(shù)最小值時，改進(jìn)的數(shù)量就是減少的數(shù)量，此時影子價格即為負(fù)的對偶價格。（2） 管理運籌學(xué)”軟件可以解決含有 100 個變量 50 個約束方程的線性規(guī)劃問題，可以解決工商管理量的問題。如果想要解決更大的線性規(guī)劃問題，可以使用由芝加哥大學(xué)的 L.E.Schrage 開發(fā)的 LINDO 計算機軟件包的微型計算機版本 LINDO/PC。

14、課本重點習(xí)題：P34-38 習(xí)題1 2 3 4第4章 線性規(guī)劃在工商管理中的應(yīng)用(P39-P66)包括：人力資源分配的問題 生產(chǎn)計劃的問題 套裁下料問題 配料問題 投資問題§1人力資源分配問題例 1某晝夜服務(wù)的公交線路每天各時間段所需司機和乘務(wù)人員數(shù)如表 4-1 所示。設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作 8h，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又使配備最少司機和乘務(wù)人員的人數(shù)最少？例 2一家中型的百貨商場對售貨員的需求經(jīng)過統(tǒng)計分析如表 4-2 所示。為了保證售貨員充分休息，要求售貨員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的。問應(yīng)該如何安

15、排售貨員的休息日期，既滿足工作需要，又使配備的售貨員的人數(shù)最少？§2生產(chǎn)計劃的問題例 3某公司面臨一個是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品都需要經(jīng)過鑄造、機加工和裝配三道工序。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表 4-3 所示。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和外包協(xié)作各應(yīng)多少件？解：設(shè) x1，x2，x3 分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5 分別為由外包協(xié)作鑄造再由本公司進(jìn)行機械加工和裝配的甲、乙兩種產(chǎn)

16、品的件數(shù)。每件產(chǎn)品的利潤如下：可得到 xi （i = 1,2,3,4,5）的利潤分別為 15 元、10 元、7 元、13 元、9 元。*該公司的最大利潤為 29 400 元*最優(yōu)的生產(chǎn)計劃為全部由自己生產(chǎn)的產(chǎn)品甲 1 600 件，鑄造工序外包而其余工序自行生產(chǎn)的產(chǎn)品乙 600 件。例 4永久機械廠生產(chǎn)、三種產(chǎn)品，均要經(jīng)過 A、B 兩道工序加工。設(shè)有兩種規(guī)格的設(shè)備 A1、A2 能完成 A 工序；有三種規(guī)格的設(shè)備 B1、B2、B3 能完成 B 工序。產(chǎn)品可在 A、B 的任何規(guī)格的設(shè)備上加工；產(chǎn)品可在工序 A 的任何一種規(guī)格的設(shè)備上加工，但對 B 工序，只能在 B1 設(shè)備上加工；產(chǎn)品只能在 A2 與

17、 B2 設(shè)備上加工。數(shù)據(jù)如表 4-4 所示。問：為使該廠獲得最大利潤，應(yīng)如何制定產(chǎn)品加工方案？解：設(shè) xijk 表示第 i 種產(chǎn)品，在第 j 種工序上的第 k 種設(shè)備上加工的數(shù)量。建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)為計算利潤最大化，利潤的計算公式為：利潤 = （銷售單價 原料單價）× 產(chǎn)品件數(shù)之和 （每臺時的設(shè)備費用 × 設(shè)備實際使用的總臺時數(shù)）之和。這樣得到目標(biāo)函數(shù)：max (1.250.25) (x111+x112) + (20.35) (x211+x212) + (2.800.5) x312 300/6 000(5x111+10x211) -321/10 000 (7x11

18、2+9x212+12x312)-250/4 000(6x121+8x221)-783/7 000(4x122+11x322)-200/4 000(7x123).經(jīng)整理可得：max0.75x111+0.775 3x112+1.15x211+1.361 1x212+1.914 8x312-0.375x121-0.5x221-0.447 4x122-1.230 4x322-0.35x123*該廠的最大利潤為 1 146.600 5 元。§4 套裁下料問 題例 5.某工廠要做 100 套鋼架，每套用長為 2.9 m，2.1 m，1.5 m 的圓鋼各一根。已知原料每根長 7.4 m，問：應(yīng)如何

19、下料，可使所用原料最省？解：共可設(shè)計下列 8 種下料方案，如表 4-5 所示。設(shè) x1, x2, x3, x4, x5, x6 , x7 , x8 分別為上面 8 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。用管理運籌學(xué)軟件計算得出最優(yōu)下料方案：按方案 1 下料 30 根；按方案 2 下料 10 根；按方案 4 下料 50 根。即：x1=30;x2=10；x3=0；x4=50；x5=0；x6= x7= x8=0只需 90 根原材料就可制造出 100 套鋼架。注意：在建立此類型數(shù)學(xué)模型時，約束條件用大于等于號比用等于號要好。因為有時在套用一些下料方案時可能會多出一根某種規(guī)格的圓鋼，但它可

20、能是最優(yōu)方案。如果用等于號，這一方案就不是可行解了。若可能的下料方案太多，可以先設(shè)計出較好的幾個下料方案。首先要求每個方案下料后的料頭較短；其次方案總體能裁下所有各種規(guī)格的圓鋼，且不同方案有著不同的各種所需圓鋼的比。這樣套裁即使不是最優(yōu)解，也是次優(yōu)解，也能滿足要求并達(dá)到省料目的。如我們用前 5 種下料方案供套裁用，進(jìn)行建模求解，也可得到上述最優(yōu)解。§5配 料 問 題例 6某工廠要用三種原料1、2、3 混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如表4-6 和表 4-7 所示。問：該廠應(yīng)如何安排生產(chǎn)，使利潤最大？解：設(shè) xij 表示第 i 種（甲、乙、丙）產(chǎn)品中原料 j 的含量。這樣我

21、們建立數(shù)學(xué)模型時，要考慮：對于甲：x11，x12，x13；對于乙：x21，x22，x23；對于丙：x31，x32，x33；對于原料 1：x11，x21，x31；對于原料 2：x12，x22，x32；對于原料 3：x13，x23，x33；目標(biāo)函數(shù)：利潤最大，利潤 = 收入 原料支出約束條件：規(guī)格要求 4 個；供應(yīng)量限制 3 個。利潤=總收入-總成本=甲、乙、丙三種產(chǎn)品的銷售單價 × 產(chǎn)品數(shù)量甲、乙、丙使用的原料單價 × 原料數(shù)量。故有：目標(biāo)函數(shù)：約束條件：從表 4-6 中可知x110.5（x11+x12+x13）x120.25（x11+x12+x13）x210.25（x21+

22、x22+x23）x220.5（x21+x22+x23）從表 4-7 中可知，生產(chǎn)甲、乙、丙的原材料不能超過原材料的供應(yīng)限額，故有x11+x21+x31100x12+x22+x32100x13+x23+x3360通過整理，得到以下模型：目標(biāo)函數(shù)：max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33約束條件：線性規(guī)劃的計算機解為 x11 = 100，x12 = 50，x13 = 50，其余的 xij = 0，也就是說每天只生產(chǎn)產(chǎn)品甲 200 kg，分別需要用第 1 種原料 100 kg，第 2 種原料 50 kg，第 3 種原料 50 kg。

23、7;6 投 資 問 題例 9 某部門現(xiàn)有資金 200 萬元，今后五年考慮給以下的項目投資。項目 A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利 110%；項目 B：從第一年到第四年每年年初都可投資，次年末能收回本利 125%，但規(guī)定每年最大投資額不能超過 30 萬元；項目 C：第三年年初需要投資，第五年末能收回本利 140%，但規(guī)定最大投資額不能超過 80 萬元；項目 D：第二年年初需要投資，第五年末能收回本利 155%，但規(guī)定最大投資額不能超過 100 萬元。據(jù)測定每次投資 1 萬元的風(fēng)險指數(shù)如右表 4-10 所示：問：（1）應(yīng)如何確定這些項目每年的投資額，使得第五年年末擁有資金的本

24、利金額最大？（2）應(yīng)如何確定這些項目每年的投資額，使得第五年年末擁有資金的本利在 330萬元的基礎(chǔ)上總的風(fēng)險系數(shù)最小？ 所設(shè)變量與問題相同，目標(biāo)函數(shù)為風(fēng)險最小，有min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24在問題的約束條件中加上“第五年末擁有資金本利在 330 萬元”的條件，于是模型如下。min f = (x11+x21+x31+x41+x51) +3 (x12+x22+x32+x42) +4x33+5.5x24s. t. x11+ x12 = 200x21 + x22+ x24 = 1.1x11；x31 + x32+ x3

25、3 = 1.1x21+ 1.25x12；x41 + x42 = 1.1x31+ 1.25x22；x51 = 1.1x41+ 1.25x32；xi2 30 ( i =1，2，3，4 )，x33 80，x24 1001.1x51 + 1.25x42+ 1.4x33+ 1.55x24330xij 0（i= 1，2，3，4，5；j = 1、2、3、4）運用“管理運籌學(xué)”軟件求得此問題的解為：x5A=33.5，x4B=30，x3C=80，x2D=100，x1A=170，x1B=30，x2A=57，x2B=30，x3A=0，x3B=20.2，x4A=7.5。課本重點習(xí)題：P57-61 習(xí)題1 3 4 5

26、6第七章 運輸問題(P126-P162)§1 運 輸 模 型例 1. 某公司從兩個產(chǎn)地 A1、A2 將物品運往三個銷地 B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地的每件物品的運費如表 7-1 所示，問：應(yīng)如何調(diào)運可使總運輸費用最?。恳话氵\輸問題的線性規(guī)劃模型：產(chǎn)銷平衡A1、A2、Am 表示某物資的 m 個產(chǎn)地；B1、B2、Bn 表示某物質(zhì)的 n 個銷地；si 表示產(chǎn)地Ai 的產(chǎn)量；dj 表示銷地 Bj 的銷量；cij 表示把物資從產(chǎn)地 Ai 運往銷地 Bj 的單位運價。設(shè) xij 為從產(chǎn)地 Ai 運往銷地 Bj 的運輸量，得到下列一般運輸量問題的模型：變化：（1）

27、有時目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等。（2）當(dāng)某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)。（3）產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。§2運輸問題的計算機求解例 2. 某公司從兩個產(chǎn)地 A1、A2 將物品運往三個銷地 B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表 7-3 所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？解：增加一個虛設(shè)的銷地運輸費用為 0。例 3. 某公司從兩個產(chǎn)地 A1、A2 將物品運往三個銷地 B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運

28、費如表 7-5 所示，問：應(yīng)如何調(diào)運可使總運輸費用最小？解：增加一個虛設(shè)的產(chǎn)地運輸費用為 0。§3 運輸問題的應(yīng)用§4 運輸問題的表上作業(yè)法1、數(shù)學(xué)模型在物流調(diào)運問題中，如何根據(jù)已有的交通網(wǎng)，制定調(diào)運方案，將貨物運到各需求地，而使總運費最小，是很關(guān)鍵的問題。這類問題可用如下數(shù)學(xué)語言描述。已知有m個生產(chǎn)地點Ai（i=1，2m），可供應(yīng)某種物質(zhì)，其供應(yīng)量分別為：ai（i=1，2，3，m），有n個銷地（需要地）Bj（j=1，2n），其需求量分別為bj（j=1，2，n），從Ai到Bj運輸單位物資的運價為Cij。這些數(shù)據(jù)可匯總于產(chǎn)銷平衡表和單位運價表中，如表7-1、表7-2所示。表7

29、-1 產(chǎn)銷平衡表 銷地產(chǎn)地1，2n產(chǎn)量1a12a2mam銷量b1，b2bn表7-2 單位運價表 銷地產(chǎn)地12n1C11C12C1n2C21C22C2nmCm1Cm2Cmn為了制定使總運費最小的調(diào)運方案，我們可以建立數(shù)學(xué)模型。如果我們設(shè)Xij表示由產(chǎn)地Ai供應(yīng)給銷地的運量，則運輸問題的線性規(guī)劃模型可分為三種情況：（1） 產(chǎn)銷平衡，即在的情況下，求（總費用最少）。滿足約束條件：1，2，n）（滿足各銷地的需要量）1，2，m）（各產(chǎn)地的發(fā)出量等于各地產(chǎn)量） Xij0（i=1，2，m；j=1，2，n）（調(diào)出量不能為負(fù)數(shù)）（2）產(chǎn)大于銷，即在的情況下，求（總費用最少）。滿足約束條件：1，2，n）ai（i=

30、1，2，m） Xij0（i=1，2，m；j=1，2，n）（3）銷大于產(chǎn)，即在的情況下，求（總費用最少）。滿足約束條件：bj（j=1，2，n）=ai（i=1，2，m） Xij0（i=1，2，m；j=1，2，n）物資調(diào)運問題可采用圖上作業(yè)法或表上作業(yè)法求其最佳的調(diào)運方案。2、物資調(diào)運問題的表上作業(yè)法物資調(diào)運的表上作業(yè)法，是指在物資調(diào)運平衡表上確定物資調(diào)運最優(yōu)方案的一種調(diào)運方法。利用表上作業(yè)法，尋求運費最少的運輸方案，其步驟可歸納如下：（1）列出運輸物資平衡表及運價表；（2）在表上做出初始方案；（3）檢查初始方案是否為最優(yōu)方案；（4）調(diào)整初始方案得到最優(yōu)解。一般說來，每調(diào)整一次得到一個新的方案，而這

31、個新方案的運費比前一個方案要少一些，如此經(jīng)過幾次調(diào)整，最后可以得到最優(yōu)方案。下面舉例說明：某公司有三個儲存某種物資的倉庫，供應(yīng)四個工地的需要。三個倉庫的供應(yīng)量和四個工地的需求量以及由各倉庫到各工地調(diào)運單位物資的運價（元/噸），如表7-3 所示，試求運輸費用最少的合理運輸方案。表7-3 供需情況和單位運價 工地運價 （元/噸）倉庫B1B2B3B4供應(yīng)量（t）A1311310700A21928400A374105900需求量3006005006002000求解步驟如下：（1）列出調(diào)運物資平衡表7-4和運價表7-5 表7-4 物資平衡表 需供B1B2B3B4供應(yīng)量（t）A1700A2400

32、A3900需求量（t）3006005006002000表7-5 運價表 工地運價倉庫B1B2B3B4A1311310A21928A374105平衡表和運價表是表上作業(yè)法的基本資料和運算的依據(jù)。表上作業(yè)法的實質(zhì)就是利用運價表在平衡表上進(jìn)行求解。為了敘述和考慮問題的方便，通常把上面的平衡表看作為矩陣，并把表中的方格記為（i，j）的形式。如（2，3）表示第二行第三列的方格；（1，4）表示第一行第四列的方格等。此外，在求解過程中，如果平衡表的（2，1）方格中表寫上300，即表示A2倉庫調(diào)運300噸物質(zhì)到第一個工地。（2）編制初始調(diào)運方案一般最優(yōu)方案是由初始方案經(jīng)過反復(fù)調(diào)整得到的。因此，編制出較好的初始

33、調(diào)運方案顯得非常重要。確定初始方案通常有兩種方法：一是西北角法，二是最小元素法。 西北角法。從供需平衡表的西北角第一格開始，按集中供應(yīng)的原則，依次安排調(diào)運量。由于集中供應(yīng)，所以未填數(shù)值的格子的Xij均為0，從而得到一個可行方案。按西北角法，本例的初始運輸方案如表7-6所示。表7-6 初始方案 需供B1B2B3B4供應(yīng)量（t）A1300400700A2200200400A3300600900需求量（t）3006005006002000由A1B1余400；A1B2400缺200；A2B2200余200；A2B3200缺300；A3B3300余600；A3B4600余0。此時運輸總成本為：S=300

34、×3400×11200×9200×2300×10+600×513500（元） 最小元素法。所謂最小元素法，就是按運價表一次挑選運費小的供需點盡量優(yōu)先安排供應(yīng)的運輸方法。首先針對具有最小運輸成本的路徑，并且最大限度地予以滿足；然后按“最低運輸成本優(yōu)先集中供應(yīng)”的原則，依次安排其他路徑的運輸量。仍以上述實例，具體做法是在表7-5 上找出最小的數(shù)值（當(dāng)此數(shù)值不止一個時，可任意選擇一個，方格（2，1）數(shù)值是1，最小。這樣，參考A2盡可能滿足B1工地的需求，于是在平衡表中有（2，1）=300，即在空格（2，1）中填入數(shù)字300，此時由于工地B1

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

36、求，為了滿足供需平衡，所以最后在平衡表上應(yīng)有（1，4）=300，這樣就得到表7-8的初始調(diào)運方案。表中填有數(shù)字的方格右上角是其相應(yīng)的運價（元/噸）。根據(jù)得到的初始調(diào)運方案，可以計算其運輸費用。（元）表7-7 供需量的分配 需供B1B2B3B4供應(yīng)量（t）A1400700A2 300 100400A3600300900需求量（t）3006005006002000表7-8 初始調(diào)運方案 需供B1B2B3B4供應(yīng)量（t）A1400330010700A230011002400A360043005900需求量（t）3006005006002000對于應(yīng)用最小元素法編制初始方案說明以下幾點： 應(yīng)用最小元素

37、法編制初始調(diào)運方案，這里的“最小”是指局部而言，而整體考慮的運費不見得一定是最小的。 特別需要指出，并不是任意一個調(diào)運方案都可以作為表上作業(yè)法的初始方案?？梢宰鳛槌跏挤桨傅恼{(diào)運方案，其填有數(shù)字的方格將恰好是（行數(shù)m+列數(shù)n-1）個，在我們這個例子中為（3+4-1=6），因此，可以作為初始調(diào)運方案提出。但是，在制定初始方案有時會碰到按最小元素所確定的方格中，其相應(yīng)的供應(yīng)點再無物資可供應(yīng)或需求點已全部得到滿足的情況，此時平衡表上填有數(shù)字的方格數(shù)小于（m+n-1）。我們規(guī)定，在未填有數(shù)字的方格中必須填上一個，并將這和其他發(fā)生供需關(guān)系的格子同樣看待，而不能作為空格，其目的是保證使填有數(shù)字的方格數(shù)等于（

38、m+n-1）的要求。下面用一個例子來說明上述情況的處理。表7-9和表7-10給出了一個物資調(diào)運問題，運用最小元素經(jīng)過三次運算后，得到下面表7-11和表7-12。表7-9 供需平衡表 產(chǎn)地銷地B1B2B3供應(yīng)量（t）A110A220A340需求量（t）10204070表7-10 運價表銷地 運價 產(chǎn)地B1B2B3A1122A2313A3231可以看出，表7-13雖然構(gòu)成了一個調(diào)運方案。但在運價表中，（1，3）及（2，3）方格尚未被劃去，所以在平衡表7-12中，方格（1，3）及（2，3）處在各填上一個“0”，隨后得表7-13，表7-13填有數(shù)字（包括0）的方格數(shù)恰是3+3-1=5，如此才可以構(gòu)成調(diào)

39、運問題的初始方案。表7-11 運價表銷地運價產(chǎn)地B1B2B3A1122A2313A3231表7-12 供需平衡表 產(chǎn)地銷地B1B2B3供應(yīng)量（t）A11010A22020A34040需求量（t）10204070表7-13 初始調(diào)用方案 產(chǎn)地銷地B1B2B3供應(yīng)量（t）A110010A220020A34040需求量（t）10204070（3）初始方案的檢驗在制定了初始調(diào)運方案之后，需要對它進(jìn)行檢驗，如果制定的初始調(diào)運方案不是最優(yōu)方案，需要對其進(jìn)行調(diào)整直到獲得最優(yōu)調(diào)運方案。運輸問題表上作業(yè)法，判斷調(diào)運方案是否為最優(yōu)解，有兩種方法：一種叫做閉回路法，另一種是位勢法。 閉合回路法。對于表上作業(yè)法的初始

40、方案來說，從調(diào)運方案表上的一個空格出發(fā)，存在一條且僅一條以某空格（用表示）為起點，以其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉回路。這個閉回路具有以下性質(zhì)：第一，每個頂點都是轉(zhuǎn)角點；第二，閉合回路是一條封閉折線，每一邊條都是水平或垂直的；第三，每一行（列）若有閉合回路的頂點，則必有兩個。只有從空格出發(fā)，其余各轉(zhuǎn)角點所對應(yīng)的方格均填有數(shù)字時，所構(gòu)成的閉合回路，才是我們所說的閉回路；另外，過任一空格的閉回路不僅是存在的，而且是惟一的。下面以表7-8給定的初始調(diào)運方案為例，說明閉回路的性質(zhì)，表7-14給出了空格，（1，1）和（3，1）所形成的閉回路：（1，1）（1·，3）（2，3）（2，

41、1）（1，1）（3，1）（2，1）（2，3）（1，3）（1，4）（3，4）（3，1）表7-14 初始調(diào)運方案 需供B1B2B3B4供應(yīng)量（t）A1400300700A2300100400A3600300900需求量（t）300600·5006002000其他空格的閉回路與此同理。在調(diào)運方案的每個空格所形成的閉回路上，作單位物資的運量調(diào)整，總可以計算出相應(yīng)的運費是增加還是減少。我們把所計算出來的每條閉回路上調(diào)整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。檢驗數(shù)的求法，就是在閉回路上，從空格出發(fā)，沿閉回路，將各頂點的運輸成本依次設(shè)置“+”、“-”，交替正負(fù)符號，然后求其代數(shù)和。這

42、個代數(shù)和數(shù)字稱為檢驗數(shù)，用ij表示。例如，上述表格上的檢驗數(shù)11=3-119-10。用同樣的方法可以求其他空格的檢驗數(shù)，見表7-15。如果檢驗數(shù)小于0，表示在該空格的閉合回路上調(diào)整運量使運費減少；相反，如果檢驗數(shù)大于0，則會使運費增加。因此調(diào)運方案是否是最優(yōu)方案的判定標(biāo)準(zhǔn)就是：初始調(diào)運方案，如果它所有的檢驗數(shù)都是非負(fù)的，那么這個初始調(diào)運方案一定最優(yōu)。否則，這一調(diào)運方案不一定是最優(yōu)的。表7-15 檢驗數(shù)計算 需供B1B2B3B4供應(yīng)量（t）A103+211400330010700A23001+191002-18400A3+1076004+5103005900需求量（t）3006005006002

43、000 位勢法。用該調(diào)運問題的相對運價減去表7-17中的數(shù)值，那么對初始方案中每個填有運量數(shù)值的方格來說，都會滿足 （7-1）而對每個空格來說，相應(yīng)得到的數(shù)值就是該空格的檢驗數(shù)，即 （7-2）上式就是用位勢法來求檢驗數(shù)的公式。本例中，設(shè)Cij（i=1，2，3；j=1，2，3，4）表示變量xij相應(yīng)的運價，將初始調(diào)運方案中填有數(shù)字方格的Cij分解成兩部分：其中ui和Vj分別稱為該方格對應(yīng)i行和j列的位勢量，因為i有m=3行，j有n=4列，故位勢的個數(shù)有m+n=3+4=7個。但·填有運量數(shù)的單元只有m+n-1=6個，這樣，m+n-1=6個Cij的方程，要解出m+n=7個未知的位勢量，ui

44、和Vj可以有很多解。所以，可以先任意給定一個未知數(shù)的位勢量，如表7-16所示。表7-16 位勢計算表 需點供點UiA310u1=2B12u2=1C45u3=-3Vjv1=0v2=7v3=1v4=8表7-17 準(zhǔn)檢驗數(shù) 需點供點UiA29310u1=2B1829u2=1C-34-25u3=-3Vjv1=0v2=7v3=1v4=8V1=0，則由C21=V2+V1=1，可以得到u2=1，再由C23=2，又得到V3=1；由C13=3，可得u1=2，依次可以得到V4=8，u3=-3，V2=7等。由上面所求出的行位勢量uj與列位勢量Vj對應(yīng)相加，得到準(zhǔn)檢驗數(shù)，如表7-17所示。表中帶有 者為初始調(diào)運方案表

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

46、400+100=500 300-100=200 x23 x24 100-100=0 0+100=100從空格X24開始，沿閉回路在各奇數(shù)次轉(zhuǎn)角點中挑選運量的最小數(shù)值作為調(diào)整量。本例是將x23方格的100作為調(diào)整量，將這個數(shù)值填入空格X24，同時調(diào)整該閉合回路中其他轉(zhuǎn)角點上的運量，使各行、列保持原來的供需平衡，這樣便得到一個新的調(diào)整方案，如表7-20所示。按新方案計算調(diào)運物資的運輸費用為：（元）表7-20 調(diào)整后的方案 需供B1B2B3B4供應(yīng)量（t）A131500320010700A23001921008400A376004103005900需求量（t）3006005006002000新方案是

47、否是最優(yōu)方案，還要對它再進(jìn)行檢驗。經(jīng)計算，該新方案的所有檢驗數(shù)都是非負(fù)的，說明這個方案已是最優(yōu)調(diào)運方案了。綜上所述，采用表上作業(yè)法求解平衡運輸問題的物資調(diào)運最優(yōu)方案的步驟如圖7-1所示。課本重點習(xí)題：P153-156習(xí)題1 2 第十三章 存儲論(P287-P324)存儲論主要解決存儲策略問題，即如下兩個問題。（1）補充存儲物資時，每次補充數(shù)量（Q）是多少？（2）應(yīng)該間隔多長時間（T）來補充這些存儲物資？建立不同的存儲模型來解決上面兩個問題，如果模型中的需求率、生產(chǎn)率等一些數(shù)據(jù)皆為確定的數(shù)值時，存儲模型被稱為確定性存儲模型；如果模型中含有隨機變量則被稱為隨機性存儲模型。§1 經(jīng)濟(jì)訂購批

48、量存儲模型經(jīng)濟(jì)訂購批量存儲模型，又稱不允許缺貨，生產(chǎn)時間很短存儲模型，是一種最基本的確定性存儲模型。在這種模型里，需求率即單位時間從存儲中取走物資的數(shù)量，是常量或近似乎常量；當(dāng)存儲降為零時，可以立即得到補充并且所要補充的數(shù)量全部同時到位（包括生產(chǎn)時間很短的情況，我們可以把生產(chǎn)時間近似地看成零）。這種模型不允許缺貨，并要求單位存儲費，每次訂購費，每次訂貨量都是常數(shù)，分別為一些確定的、不變的數(shù)值。例1 益民食品批發(fā)部是個中型的批發(fā)公司，它為附近 200 多家食品零售店提供貨源。批發(fā)部的負(fù)責(zé)人為了減少存儲的成本，他選擇了某種品牌的方便面進(jìn)行調(diào)查研究，制定正確的存儲策略。下面為過去 12 周的該品牌方

49、便面的需求數(shù)據(jù)。過去 12 周里每周的方便面需求量并不是一個常量，即使以往 12 周里每周需求量是一個常量 ，而以后時間里需求量也會出現(xiàn)一些變動，但由于其方差相對來說很小，我們可以近似地把它看成一個常量，即需求量每周為 3 000 箱，這樣的處理是合理的和必要的。計算存儲費：每箱存儲費由兩部分組成，第一部分是購買方便面所占用資金的利息，如果資金是從銀行貸款，則貸款利息就是第一部分的成本；如果資金是自己的，則由于存儲方便面而不能把資金用于其他投資，我們把此資金的利息稱為機會成本，第一部分的成本也應(yīng)該等于同期的銀行貸款利息。方便面每箱 30 元，而銀行貸款年利息為 12%，所以每箱方便面存儲一年要

50、支付的利息款為 3.6 元。第二部分由儲存?zhèn)}庫的費用、保險費用、損耗費用、管理費用等構(gòu)成，經(jīng)計算每箱方便面儲存一年要支付費用 2.4 元，這個費用占方便面進(jìn)價 30 元的 8%。把這兩部分相加，可知每箱方便面存儲一年的存儲費為 6 元，即 C1= 6 元/年·箱，占每箱方便面進(jìn)價的 20%。計算訂貨費：訂貨費指訂一次貨所支付的手續(xù)費、費、交通費、采購人員的勞務(wù)費等，訂貨費與所訂貨的數(shù)量無關(guān)。這里批發(fā)部計算的每次的訂貨費為 C3=25 元/次。這種存儲模型的特點如下。（1）需求率（單位時間的需求量）為 d；（2）無限供貨率（單位時間入庫的貨物數(shù)量）；（3）不允許缺貨；（4）單位貨物單位

51、時間的存儲費 c1；（5）每次的訂貨費 c3；（6）每期初進(jìn)行補充，即期初存儲量為 Q。單位時間總費用=單位時間的存儲費用+單位時間的訂貨費用單位時間的存儲費用=單位時間購買貨物所占用資金的利息+儲存?zhèn)}庫的費用+保險費用+損耗費用+管理費用等設(shè)每次的訂貨量為 Q，由于補充的貨物全部同時到位，故 0 時刻的存儲量為 Q。到 T 時刻存儲量為 0，則 0 到 T 時間的平均存儲量為 Q/2。又設(shè)單位時間的總需求量為 D，單位貨物的進(jìn)價成本即貨物單價為 c，則靈敏度分析：批發(fā)部負(fù)責(zé)人在得到了最優(yōu)方案存儲策略之后。他開始考慮這樣一個問題：這個最優(yōu)存儲策略是在每次訂貨費為 25 元，每年單位存儲費 6 元，或占每箱方便面成本價格 30元的 20%（稱之為存儲率）的情況下求得的。一旦每次訂貨費或存儲率預(yù)測值有誤差，那么最優(yōu)存儲策略會有多大的變化呢？這就是靈敏度分析。為此，我們用管理運籌學(xué)軟件計算了當(dāng)存儲率和訂貨費發(fā)生變動時，最優(yōu)訂貨量及其最小的一年總費用以及取定訂貨量為 1 140.18 箱時相應(yīng)的一年的總費用，如表 13-2 所示。從表 13-2 中可以看到當(dāng)存儲率和