1、管 理 運 籌 學主講：陳鼎藩社科系工商管理教研室1 目 錄第1章 線性規劃第2章 對偶理論第3章 運輸問題第4章 整數規劃與分配問題 第5章 圖與網絡分析第6章 方案評審法和關鍵路線法第7章 目標規劃2第1章 線性規劃1.1 線性規劃的數學模型1.2 圖解法1.3 單純形法原理與計算步驟1.4 單純形法進一步討論1.5 線性規劃建模3ex1.1:甲企業方案生產兩種產品、，這兩種產品都要分別在A、B、C、D四種不同設備上加工，每生產一件產品的設備加工工時、設備生產能力、產品單位利潤如下表，問、各生產多少使利潤到達最大？ 1.1 線性規劃數學模型 生產能力A 2 2 12B 1 2 8C 4 0

2、 16D 0 4 12獲利 2元/件 3元/件4解 設分別生產、產品數量為x1、x2 那么利潤Z=2x1+3x2,考慮到設備的生產能力那么應受到以下條件的限制使得2x1+2x212x1 +2x284x1 164x2 12x1，x2 0利潤目標為max z=2x1+3x2 A 設備生產能力約束B 設備生產能力約束C、D 設備生產能力約束現實問題變量非負Z=2x1 +3x2 max5 線性規劃模型三要素決策變量variable：指決策者為實現規劃目標采取的方案、措施，是問題中要確定的未知量。目標函數objective：問題要到達的目的要求。約束條件(constrains)：決策變量取值時受到的各種

3、資源的限制。目標函數和約束條件皆為決策變量的線性函數6 線性規劃數學模型的幾種形式目標函數：maxminz=c1x1 +c2x2 + +cnxna11x1 +a12 x2+ +a1n xn(,=)b1 a21x1 +a22 x2+ +a2n xn (,=)b2 am1x1 +am2 x2+ +amn xn(,=)bm x1 ,x2 ,xn 0.約束條件s.t.簡寫形式7矩陣形式向量形式8標準形式：非標準形式如何轉化？目標函數為求極小值約束條件為不等式變量取值無約束目標函數求最大值約束條件取等式變量非負ex1.2 91.2 圖解法優點：直觀性強，便于了解線性規劃問題解的情況計算步驟：缺點：只能求

4、解兩個變量的線性規劃模型建立坐標系圖示約束條件，確定滿足約束的解的范圍畫出目標函數直線族確定最優解10可行域目標函數等值線最優解64-860 x1x211線性規劃問題解的情況唯一最優解交于一點無窮多個最優解交于一條線段無解無可行域無界解121.3 單純形法解的概念可行解：滿足約束條件的解X=x1, , xnT稱為線性規劃問題的可行解。可行域：可行解的集合。最優解：使目標函數到達最大值的可行解。基：假設A為約束方程組的mn階系數矩陣，RA= m, B是A的mm階滿秩子矩陣，那么稱B為線性規劃問題的一個基。13基向量：B中的每一個列向量pj稱為基向量。基變量：基向量pj對應的變量xj稱為基變量。基

5、解：在約束方程組 A X = b 中，令所有的非基變量都為零，即 xm+1 = xm+2 = = xn=0， ,又因為B滿秩，根據克拉姆法那么，由m個約束方程組可解出m個基變量的唯一解XBXB=x1,x2, xm ,將這個解加上非基變量取0的值有X= x1,x2, xm，0， 0 T，稱X為線性規劃問題的基解。基可行解：假設基解X0，那么X為基可行解。可行基：對應于基可行解的基稱為可行基。14ex1.7 找出以下線性規劃問題的基解、基可行解15凸集及其頂點凸集凸集不是凸集頂點凸集：如果集合C上任意兩個點X1、X2，其連線上的所有點都在集合C上，那么C是凸集。頂點:16根本定理定理1：假設線性規

6、劃問題存在可行解，那么問題的可行域是凸集。引理1：線性規劃問題的可行解X=x1,xnT為基可行解的充分必要條件是X的正分量所對應的系數列向量是線性無關的。定理2：線性規劃問題的基可行解X對應線性規劃問題可行域凸集的頂點。定理3：假設線性規劃問題有最優解，一定存在一個基可行解是最優解。推論：假設線性規劃問題有最優解，至少在可行域的一個頂點取得最優。17單純形法計算步驟：化為標準型求初始基可行解，列出初始單純形表最優性檢驗從一個基可行解轉換到相鄰的基可行解迭代18單純形表c1 c2 cm cj cn x1 x2 xm xj xn cj c1 x1 b1c2 x2 b2: : : : :cm xm

7、bm cB 基 b1 0 0 a1j a1n0 1 0 a2j a2n: : : : : : : : :0 0 1 amj amj cj - zj0 0 0 19ex1.8 用單純性法求解以下線性規劃問題20ex1.9 用單純性法求解以下線性規劃問題211.4 單純形法進一步討論人工變量法22化為標準型：添加人工變量x6、x7：23兩階段法第一階段：求解一個目標函數中只包含人工變量的線性規劃模型第二階段：假設第一階段的模型目標函數值為0,那么原問題有可行解。24解的判別：唯一最優解基變量不含人工變量所有的檢驗數 0所有的非基變量的檢驗數 =700X1+0.5X2+0.2X3+2X4+0.5X5

8、=300.5X1+X2+0.2X3+2X4+0.8X5=100ENDLINDO 輸入文件：LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1) 32.43590 VARIABLE VALUE REDUCED COST X1 0.000000 0.059615 X2 0.000000 0.593590 X3 0.000000 0.352564 X4 39.743591 0.000000 X5 25.641026 0.000000LINDO 輸出文件：30 Ex1.11 某糖果廠用原料A、B、C加工成三種不同牌號的糖果甲、乙、丙，各種牌號糖果

9、中A、B、C含量、原料本錢、各種原料的每月限用量，三種牌號糖果的單位加工費及售價如下表所示，問該廠每月生產這三種糖果各多少千克，使該廠獲利最大，建立此問題的數學模型并求解。甲 乙 丙 原料本錢 每月限用量 元/kg (kg)A 60% 30% 2.00 2000B 1.50 2500C 20% 50% 60% 1.00 1200加工費元/kg售價元/kg 3.40 2.85 2.25 0.5 0.4 0.3 31MAX (3.40-0.5)(X11+X21+X31)+(2.85-0.4)()+(2.25-0.3)(X13+X23+X33)-2.0(X11+X12+X13)-1.50(X21+X

10、22+X23)-1.0(X31+X32+X33)=0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X33STX11+X12+X13=2000X21+X22+X23 =2500X31+X32+X33=0.6X11+X21+X31X31=0.3 (X12+X22+X32 )X32=0.5X12+X22+X32X33=0.6X13+X23+X33END原始模型：32MAX 0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X33STX11+

11、X12+X13=2000X21+X22+X23 =2500X31+X32+X33=0X31-0.2X11-0.2X21-0.2X31=0X32-0.5X12-0.5X22-0.5X32=0X33-0.6X13-0.6X23-0.6X330 ,那么該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，那么其對應的對偶變量一定為零。 49ex 2.3 線性規劃問題：要求：1寫出其對偶問題；2原問題最優解為X*=2，2，4，0，試根據對偶理論，直接求出對偶問題的最優解。506基解的互補性 和變量的對應關系： 線性規劃問題原問題和對偶問題之間存在一對互補的基解，其中原問題的松弛變量對應于對偶問題的變量，

12、對偶問題的剩余變量對應原問題的變量，這些互相對應的變量如果在一個問題的解中是基變量，那么在另一個問題的解中是非基變量。將這對互補的基解分別代入原問題和對偶問題的目標函數中，有z=.51LP1LP2y1 對應 x3 y2 對應x4 y3對應x5 x1對應y4 x2對應y5 52LP1的最終單純行表：CB 基bx1x2x3x4x52 x10 x43 x23431000011/2-20010-1/54/51/5zj -cj000101/5CB 基by1y2y3y4y512 y115 y311/5102-4/501-1/21/50-1/5zj -cj004033LP2的最終單純行表532.4 影子價格

13、 bi 是線性規劃問題約束的右端項，代表第i種資源的擁有量 。而對偶變量 yi 的意義代表對一個單位第i種資源的估價，這種估價不是資源的市場價格，是根據資源在生產中做出的奉獻而作的估價，稱之為影子價格。541影子價格與市場價格的區別： 市場價格是數，相比照較穩定，而它的影子價格那么有賴于資源的利用情況，是未知數。由于企業生產任務、產品結構等情況發生變化，資源的影子價格隨之改變。552影子價格 是一種邊際價格563資源的影子價格又 是一種時機本錢 在純市場經濟條件下，在ex2.4中，當第3種資源的市場價格低于1/5時，可以買進這種資源；當市場價格高于影子價格時，就會賣出這種資源。影子價格最終會與

14、市場價格處于同等水平。574互補松弛性的經濟含義585檢驗數的經濟意義cj 代表第j種產品的產值， 是生產該種產品所消耗各項資源影子價格的總和，即產品的隱含本錢。當產品的產值大于本錢時，生產該產品有利可圖，應安排該種產品檢驗數大于零的變量作為進基變量。596資源影子價格的應用 對線性規劃的求解是確定資源的最有效分配方案，而對其對偶問題的求解那么是確定資源的恰當估價，這種估價直接涉及到資源的最有效利用。 資源的影子價格可以作為公司內部的結算價格；社會上可對一些最緊缺的資源，借助影子價格規定使用這種資源一單位時必須上交的利潤額，以控制某些公司超低本錢使用社會資源，侵蝕公眾福利。602.5 對偶單純

15、形法612.6 靈敏度分析 靈敏度分析：對系統或事物因周圍條件變化顯示出來的敏感程度的分析。62靈敏度分析的步驟1將參數的改變計算反映到最終的單純形表上2檢查原問題是否仍為可行解3檢查對偶問題是否仍為可行解633檢查對偶問題是否仍為可行解4按下表所列情況得出結論和決定繼續計算步驟原問題對偶問題結論或繼續計算的步驟可行解可行解仍為問題的最優解可行解非可行解用單純形法繼續迭代求最優解非可行解可行解用對偶單純形法繼續迭代求最優解非可行解非可行解引進人工變量，編制新的單純行表重新計算64分析cj變化的影響65分析bi的變化范圍66增加一個變量的分析增加一個變量的分析在實際問題中反映為增加一種新產品。e

16、x 2.7 現在該公司方案增加一種新產品x6，該產品單位利潤為4元，p6=(2 4 5)T，原有條件不變，試分析該公司是否生產這種新產品？67增加一個約束條件的分析 增加一個約束條件的分析在實際問題中反映為增加一道工序或者增加一種資源限制。ex 2.8 增加一個約束條件 3x1+2x214，要求分析最優解變化。68第3章 運輸問題3.1 運輸問題的數學模型3.2 表上作業法3.3 產銷不平衡的運輸問題及其應用693.1 運輸問題的數學模型ex3.1 某食品公司經銷的主要產品之一就是糖果，其下屬三個生產廠，該公司把這些糖果分別運往四個地區門市部銷售，各加工廠產量、各門市部銷售量及從每個加工廠到各

17、銷售門市部每噸糖果的運價如下表所示，問該食品公司應如何調運，在滿足各門市部需求量的情況下，使總的運費支出為最小。 銷地 產地B1 B2 B 3 B4 生產量A1 A2A33 11 3 101 9 2 87 4 10 5749需求量3 6 5 6運價70 銷地 Bj 產地 AiB1 Bn 生產量A1 Amc11 c1n cm1 cmna1am需求量b1 bn運價cij一般運輸問題的運輸表7172733.2 運輸單純形法 表上作業法分析實際問題列出產銷平衡表及單位運價表確定初始調運方案最小元素法orVogel法求檢驗數閉回路法or 位勢法找出絕對值最大的負檢驗數，閉回路法調整，得出新的調運方案所有

18、檢驗數0是否得到最優方案算出總的運費迭代74表3-1 表上作業法計算 銷地 B1B2B 3B4生產量A1 x113113107A219284A3741059需求量3656運價產地753.3 產銷不平衡的運輸問題及其應用ex3.2 設有A1、A2、A3三個產地生產某種物資，其產量分別為7t、5t、7t，B1、B2、B3、B4四個銷售地需要該物資，銷量分別為2t、3t、4t、6t，又知各產銷地之間的單位運價如下表，試決定總運費最小的調運方案。處理產銷不平衡的思路：轉化為產銷平衡問題76 銷地 B1B2B 3B4生產量A1 211347A2103595A378127需求量2346運價產地表3-277

19、ex3.3 設有三個化肥廠供給四個地區的農用化肥。假定等量的化肥在這些地區使用效果相同，各化肥廠年產量，各地區需要量及從各化肥廠到各地區單位化肥的運價如表3-3所示，試決定使總的運費最節省的化肥調撥方案。78 產量（萬噸）A1613221750B1413191560C19202350最低需求（萬噸）最高需求（萬噸）3050707003010不限需求地區化肥廠表3-3運價79ex3.4 江南廠按照合同要求需于每個季度末分別完成10、15、25、20臺同一規格的柴油機。該廠每個季度生產能力及生產每臺柴油機的本錢如表3-4所示，又如果生產的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護費用0.15

20、萬元。要求在完成合同的條件下，制訂使該廠全年生產、儲存和維護費用為最小的決策方案。 季度 生產能力（臺）單臺成本（萬元）12342535301010.811.111.011.3表3-480ex3.5 東海造船廠根據合同要在當年算起的連續三年年末各提供三條規格相同的大型貨輪。該廠今后三年的生產能力及生產本錢如表3-5所示。 加班生產情況下每條貨輪本錢比正產生產時多出70萬元，又知造出的貨輪如當年不交貨，每條貨輪每積壓一年將增加維護保養等費用為40萬元。在簽訂合同時該廠已有兩條當年制造的未交貨的積壓貨輪。該廠希望在第三年年末在交完合同任務后能儲存一條備用。問該廠應該如何生產方案，使在滿足上述要求的

21、條件下，使總的費用支出為最小？ 81 年度 正常生產時可完成的貨輪數加班生產時可完成的貨輪數正常生產時每條貨輪成本第一年第二年第三年241323500萬600萬550萬表3-582ex3.6 東興煤炭公司下屬桔祥、平安、雙福三個煤礦，年生產能力分別為120、160、100萬t ，公司同三個城市簽訂了下年度的供貨合同：城市1-110萬t,城市2-150萬t,城市3-70萬t,但城市3表示愿意購置剩余的全部煤炭。另有城市4雖未簽訂合同，但也表示只要公司有剩余煤炭，原全部收購。從各礦至四個城市的煤炭單位運價見表3-6。 1234吉祥平安雙福856724513235表3 - 6城市煤礦83第4章 整數

22、規劃與分配問題4.1 整數規劃的特點及作用4.2 分配問題與匈牙利法4.3 分枝定界法 4.4 整數規劃建模844.1 整數規劃的特點及作用整數規劃：要求一局部或全部決策變量必須取整數 的規劃問題整數線性規劃。整數規劃的定義和分類85純整數規劃：全部決策變量取整數的線性規劃。混合整數規劃：只要求一局部決策變量取整數的線 性規劃問題。0-1規劃：要求決策變量取0或1邏輯值的規劃問題。86邏輯變量在建模中的用法1 m個約束條件中只有k個起作用872 約束條件的右端項可能是r個值中的某一個883 兩組條件滿足其中一組894 用以表示含固定費用的函數90ex4.1 現有資金總額為B，可供選擇的工程為n

23、個。工程jj=1n所需投資額和預期收益分別為aj和cj。此外，由于種種原因，有三個附加條件：第一：假設選擇工程1就必須選擇工程2；第二：工程3和4至少選擇一個；第三：工程5、6、7恰好選擇兩個。問應當如何選擇投資工程，才能使總收益最大？試建立此問題的數學模型。914.2 分配問題與匈牙利法 m件任務分別由m個人完成，第jj=1m個人完成第i i=1m件任務的本錢費用為cij，問應如何分配任務可使總費用最小。 人員Bj 任務AiB1 Bm A1 Amc11 c1m cm1 cmm 本錢 cij分配問題Assignment Problem的數學模型9293匈牙利法 1955年，庫恩利用匈牙利數學家

24、康尼格的關于矩陣中獨立零元素的定理，提出了解分配問題的一種算法，習慣上稱之為匈牙利法。 匈牙利法的關鍵是利用了分配問題最優解的以下性質：假設從分配問題的系數矩陣稱為效率矩陣的某行或某列的各元素分別減去一個常數k ，得到一個新的矩陣，那么以新矩陣為系數矩陣的分配問題與原分配問題的最優解相同。因為系數矩陣的這種變化并不影響到數學模型的約束方程組，而只是使目標函數減少了常數k,所以最優解不發生變化。94變換效率矩陣 確定獨立零元素是否有m個獨立零元素NY未劃去零元素是否構成閉回路每行減去本行最小元素每列減去本列最小元素從“行找，“列畫線從“列找，“行畫線Y最優解間隔指派沿閉回路N找到未被直線覆蓋最小

25、元素k，畫線的行Ui=0，否那么Ui=k,畫線的列vj=-k，否那么vj=0匈牙利法計算步驟 :每一元素分別減去Ui和vj95ex4.2 有一份說明書要分別翻譯成英、日、德、俄四種文字，交給甲、乙、丙、丁四個人去完成。因個人專業不同，他們完成不同文字的翻譯所需的時間如表4-1所示，應如何分配翻譯任務，使這四個人分別完成四項任務總的時間為最小。 甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119表4 - 1 人工作96一般的分配問題1 人數和事數不等的問題 人少事多，一人只做一件事：添上一些虛擬的人，這些虛擬人完成各事的費用系數為0，即這些費用不會發生的。

26、 人少事多，事情必須全部完成：意味著某些人要完成假設干件事情，那么可將該人化作相同的幾個人來接受指派，這幾個“相同的人做同一件事的費用系數當然也相同。 人多事少：添上一些虛擬的事，當然完成虛擬事的費用為0。972 某事不能由某人做的分配問題 假設某件事一定不能由某個人來做，那么可將相應的費用系數取任意大的系數 M 即可。3 最大化分配問題 目標函數是求最大值，按照以下方法轉化為最小分配問題:找出效率矩陣B中最大的元素 m，用m 分別減去原效率矩陣 B 的每一個元素，得出新的效率矩陣 C,那么以C為效率矩陣的最小化分配問題和以B為效率矩陣的最大化分配問題最優解相同，求解C 。9899ex4.3

27、某商業公司方案開辦5家新商店，為了盡早建成營業，商業公司決定由5家建筑公司分別承建，建筑公司Aii=15對新商店Bii=15的建造費用的報價是cij，見表4-3，商業公司如何來分配建造任務，才能使總的建造費用最少？ B1B2B3B4B5A1A2A3A4A547666899797171214121514861012107106表4 - 3 建筑商商店報價100ex4.4 對于ex4.2中的分配問題，為了保證工程質量，經研究決定，舍棄建筑公司A4和A5，而讓技術力量相對較強的建筑公司A1 、A2 和A3來承建。根據實際情況，可以允許每家建筑公司承建一家或二家商店。求使總費用最少的指派方案。 B1B

28、2B3B4B5A1A2A3476899717121514812107 建筑商商店1014.3 分枝定界法Branch and Bound method102分枝定界法的思路和步驟1求解整數規劃的松弛問題 設整數規劃問題為A，它的松弛問題為B，那么A的可行域是B 的可行域的子集 。假設B無可行解那么A無可行解；假設B的最優解是A的可行解滿足A整數要求，那么也是A的最優解；否那么B的最優解不滿足A的整數要求就是A最優解的上界求極大時或下界值求極小時，轉2。1032分枝 對問題B，任選一個不符合整數要求的變量進行分枝。1043定界 對B的子問題求最優解，假設該解滿足A的約束，即找到了A的一個可行解，

29、否那么該解為所屬分枝的邊界值求極大化時為上界，求極小化時為下界。 假設所有的子問題的最優解均非A的可行解，那么選取其邊界值最大求極大值時或最小求極小值時的子問題進一步細分子問題求解 分枝過程一直進行下去，直到找到A的一個可行解為止。假設計算時同時出現兩個以上可行解，那么選取其中最大求極大值時或最小求極小值時的一個保存，轉4。1054剪枝 將各子問題的邊界值與保存的可行解的值進行比較，把邊界值劣于可行解的分枝剪去。假設除保存下來的可行解外，其余分枝均被剪去，那么該可行解就是A的最優解；否那么回到2，選取邊界值最優的一個繼續分枝。 假設計算中又出現新的可行解，那么與原可行解進行比較，保存最優的，并

30、重復上述步驟。106 L0X1=3.25 X2=2.5 Z=14.75 L1X1=3.5 X2=2 Z=14.5 L2X1=2.5 X2=3 Z=13.5 L11X1=3 X2=2 Z=13 L12X1=4 X2=1 Z=14X22X23X13X14分枝定界過程1074.4 整數規劃建模ex4.6 東方大學計算機實驗室聘用4名大學生代號1、2、3、4和2名研究生代號5、6值班答疑。每人從周一至周五每天最多可安排的值班時間及每人每小時值班報酬如下表學生代號報酬(元/h)每天最多可安排的值班時間 周一 周二 周三 周四 周五1 2345610.010.0 9.9 9.810.811.3 6 0 6

31、 0 7 0 6 0 6 0 4 8 3 0 5 5 5 6 0 4 3 0 4 8 0 0 6 0 6 3 108 該實驗室開放時間是8：00至晚上10：00，開放時間須有且僅須一名學生值班。規定大學生每周值班不少于8小時，研究生每周不少于7小時。每名學生每周值班不超過3次，每次值班不少于2小時，每天安排值班的學生不超過3人。且其中必須有一名研究生。試為該實驗室安排一張人員的值班表，試總支付報酬最小。109Ex4.7 下表為某醫院每天的護士值班最低需求人數。護士連續工作5天必須休息2天。在正常工作日5天周工資為300元；周六上班額外補助25元；周日上班額外補助35元。試安排護士值班方案，使醫

32、院的總工資支出最少。DayMonTueWedThu Fri Sat SunReq15171414151920110Ex4.8 鞍山街郵局周一到周日每天所需值班人員如下表所示：DayMonTueWedThu Fri Sat SunReq15171414151920 1規定郵局職工每周上班5天，休息2天，具體上班和休息時間由郵局安排，但保證每名職工每周至少有一個休息日安排在周六和周日。問該郵局至少應配備多少名職工，試建立數學模型并求解； 2在上述給定條件的根底上，又假定該郵局有主任、副主任各一人，上級規定每天值班人員中至少有一名主任或副主任，又同樣保證主任或副主任每周至少休一個周六或周日，試建立數

33、學模型并求解。111 ex4.9 紅星日用化工廠為發運產品,下一年度需6種不同容積的包裝箱，每種包裝箱的需求量及生產一個可變費用如下表：包裝箱代號123456容積(m3)需求量(個)可變費用(元/個) 0.085005.00.15508.00.1270010.00.1590012.10.2045016.30.2540018.2 由于生產不同容積包裝箱時需進行專門準備、下料等，生產某一容積包裝箱的固定費用為1200元。又假設某一容積包裝箱數量不夠時，可用比它容積大的代替，試問該化工廠應訂做哪幾種代號的包裝箱各多少個，使費用最節省。112ex4.10 春江市方案為新建的5個居民小區中的兩個分別各設

34、一所小學，下表給出了各小區內及各小區間的步行時間min,及各居民小區小學生人數。要求為該市提供決策建議，兩所小學應分別建在哪兩個小區，以及各居民小區的小學生應分到哪所小學上學，使學生總的上學步行時間為最短。 小學位于該區小學生人數 至其他區步行時間（min） 1234512345200180300160350 5 20 15 25 10 20 4 20 15 25 15 20 6 25 15 25 15 25 4 12 10 25 15 12 5113ex4.11 清遠市下設8個區，下表給出救護車從一個區至另一個區的車程min，該市擬建救護中心，要求各區離救護中心的車程必須在8min內，試為該

35、市提供決策建議：至少建立多少個救護中心，建于何處？ 至從 2 3456781234567891011127131378141187881712101410151410916712114ex4.12 某公司需生產2000件某種產品，該種產品可利用A、B、C、D設備中任意一種加工，每種設備的生產準備結束費、生產該產品時的單件本錢以及每種設備限定的最大加工能力件如下表所示，問如何安排產品生產，使得總費用最低。試建立該問題的數學模型。 設備準備結束費(元)生產成本（元/件）生產能力（件）ABCD1000 980 800 70020241628 900100012001600115ex4.13 漢光汽車

36、制造廠生產珠江、松花江、黃河三種牌號的汽車。各生產1臺時的鋼材、勞動力消耗及單位利潤，每月可供使用的鋼材及勞動力小時數見下表所示：珠江松花江黃河每月可供量鋼材（t）勞動力（h）1.53003.02505.0400 6 000 600 000預期利潤（元）200030004000 上述三種汽車的的經濟批量均為月產1000臺以上，即各牌號汽車或不生產或大于1000臺/月，試為該廠找出一個使利潤最大的生產方案方案。116第5章 圖與網絡分析5.1 圖的根本概念與模型5.2 樹圖和圖的最小生成樹5.3 最短路問題5.4 網絡最大流5.5 最小費用流1175.1 圖的根本概念與模型哥尼斯堡七橋難題 Se

37、ven Bridges PuzzleAB 瑞士數學家歐拉E Euler于1736年發表了題為“依據幾何位置的解題方法的論文，有效地解決了七橋難題，被認為是圖論的創始人。118環球旅行問題 1857年，愛爾蘭數學家哈密爾頓Hamilton創造了一種游戲，他用一個實心正12面體象征地球，正12面體的20個頂點分別代表世界上20座名城，要求游戲者從任一城市出發，尋找一條可經由每個城市一次且僅一次再回到出發點的路，這就是“環球旅行問題。119 它與七橋問題不同，前者要在圖中找一條經過每邊一次且僅一次的路，通稱歐拉回路，而后者是要在圖中找一條經過每個點一次且僅一次的路，通稱為哈密爾頓回路。 在這一時期，

38、還有許多諸如迷宮問題、博奕問題以及棋盤上馬的行走路線之類的游戲難題，吸引了許多學者。這些看起來似乎無足輕重的游戲卻引出了許多有實用意義的新問題，開辟了新學科。 運籌學中的“中國郵路問題：一個郵遞員從郵局出發要走遍他所負責的每條街道去送信，問應如何選擇適當的路線可使所走的總路程最短。這個問題是由我國管梅谷教授在1962年首先提出，因此國際上成為“中國郵路問題。它與歐拉回路有密切的關系。而著名的“貨郎擔問題那么是一個帶權的哈密爾頓回路問題。120龐加萊猜測 任何一個封閉的三維空間，只要它里面所有封閉曲線都可以收縮成一點，這個空間就一定是一個三維圓球這就是法國數學家龐加萊于1904年提出的猜測。20

39、00年5月，美國的克萊數學研究所為每道題懸賞百萬美元求解。 2006年6月3日，中山大學朱熹平教授和曹懷東以一篇長達300多頁的論文，給出了龐加萊猜測的完全證明。破解了國際數學界關注上百年的重大難題龐加萊猜測。運用漢密爾頓、佩雷爾曼等的理論根底，朱熹平和曹懷東第一次成功處理了猜測中“奇異點的難題，從而完全破解了困擾世界數學家多年的龐加萊猜測。121 圖：如果用點表示研究的對象，用邊表示這些對象之間的聯系，那么圖G可以定義為點和邊的集合，記作G = V，E 。式中V是點的集合，E是邊的集合當V、E都是有限集合時稱G為有限圖，否那么為無限圖。 網絡圖：如果給圖中的點和邊賦以具體的含義和權數，如距離

40、、費用、容量等，把這樣的圖稱為網絡圖，記作N。 122 上圖中的點(又稱頂點或節點)用“v 表示，邊用“e 表示，對每條邊可用它所聯結的點表示，如記作e1=v1,v2。如果邊vi, vj的端點有序，即它表示以vi為始點 ，vj為終點的有向邊或稱弧此時圖G稱之為有向圖。否那么為無向圖。圖的表示v4v2v3v1v2v1e1123 端點，關聯邊，相鄰 假設有邊e可表示為是e=vi, vj,稱vi、 vj是邊e的端點，反之稱邊e為點vi或vj關聯邊。 假設點vi、vj與同一條邊關聯，稱點vi和vj相鄰；假設邊ei和ej具有公共的端點，稱邊 ei和ej相鄰。 124環，多重邊，簡單圖 如果邊e的兩個端點

41、相重，稱該邊為環。如果兩個點之間的邊多于一條，稱為具有多重邊。對無環、無多重邊的圖稱作簡單圖。 次，奇點，偶點，孤立點 與某一個點vi相關聯的邊的數目稱為點的次(也叫做度或線度)，記作d(vi)。次為奇數的點稱作奇點，次為偶數的點稱作偶點，次為0的點稱作孤立點。 任何圖中頂點次數的總合等于邊數的兩倍，任何圖中奇點必為偶數個。125用點的次數來求解一筆畫問題：126鏈，圈，路，回路，連通圖 圖中有些點和邊的交替序列 = v0 , e1 ，v1, e2 ， ，ek ， vk ，假設其中各邊el，e2， ，ek 互不相同，且任意vi，t-1 和 vi，t (2tk)均相鄰，稱為鏈 如果鏈中所有的頂點

42、 v0，v1， ，vk也不相同，這樣的鏈稱為路。 對起點與終點相重合的鏈稱作圈，起點與終點重合的路稱作回路 假設在一個圖中，如果每一對頂點之間至少存在一條鏈，稱這樣的圖為連通圖，否那么稱該圖是不連通的 127完全圖，偶圖 一個簡單圖中假設任意兩點之間均有邊相連，稱這樣的圖為完全圖含有n個頂點的完全圖，其邊數有n(n-1)/2條 如果圖的頂點能分成兩個互不相交的非空集合V1和V2，使在同一集合中任意兩個頂點均不相鄰，稱這樣的圖為偶圖(也稱二分圖) 如果偶圖的頂點集合V1和V2之間的每一對不同頂點都有一條邊相連，稱這樣的圖為完全偶圖 完全偶圖中V1含m個頂點，V2含n個頂點，那么其邊數共mn條.

43、128子圖，局部圖 圖G1=V1，E1和圖G2=V2，E2如果有V1 V2和E1 E2，稱G1是G2的一個子圖假設有V1=V2，E1 E2，那么稱G1是G2的一個局部圖. 注意局部圖也是子圖，但子圖不一定是局部圖 129ex5.1 證明在9個工廠之間，不可能每個工廠只與其它3個工廠有業務聯系，也不可能只有4個工廠與偶數個工廠有業務聯系。 ex5.2 6個人圍成圓圈就座，每個人恰好只與相鄰者不相識，是否可以重新就座，使每個人都與鄰座相識？ 130ex5.3 有甲、乙、丙、丁、戊、己六名運發動報名參加A、B、C、D、E、F六個工程的比賽下表中打“的是各運發動報名參加的比賽工程問六個工程的比賽順序應

44、如何安排，做到每名運發動都不連續地參加兩項比賽 ABCDEF甲乙丙丁戊己1315.2 樹圖和圖的最小生成樹 樹圖(簡稱樹，記作T (V，E)是一類簡單而十分有用的圖樹圖的定義是無圈的連通圖 這類圖與大自然中樹的特征相似，因而得名樹圖鐵路專用線、管理組織機構、學科分類和一些決策過程往往都可以用樹圖的形式表示 24351132性質1：任何樹中必存在次為1的點 樹的性質 以后稱次為1的點為懸掛點，與懸掛點關聯的邊稱為懸掛邊很顯然，如果從樹圖中拿掉懸掛點及與其關聯的懸掛邊，余下的點和邊構成的圖形仍連通且無圈，那么還是一個樹圖 性質2：具有n個頂點的樹的邊數恰好為(n-1)條 性質3：任何具有n個頂點

45、、(n-1)條邊的連通圖是樹 133 兩點說明： 1樹是無圈連通圖中邊數最多的，在樹圖上只要任意再加上一條邊，必定會出現圈 2由于樹圖是無圈的連通圖，即樹圖的任意兩個點之間有一條且僅有一條惟一通路因此樹圖也是最脆弱的連通圖只要從樹圖中取走任一條邊，圖就不連通因此一些重要的網絡不能按樹的結構設計 134圖的最小生成樹定理1：圖中任一個點i，假設j是與i相鄰點中距離最近的，那么邊i，j必含在該圖的最小局部樹內 如果G1是G2的局部圖，又是樹圖，那么稱G1是G2的局部樹(或支撐樹)樹圖的各條邊稱為樹枝(假定各邊均有權重)，一般圖G，含有多個局部樹，其中樹枝總長最小的局部樹，稱為該圖的最小生成樹(也稱

46、最小支撐樹，minimum spanning tree) 推論：把圖的所有點分成V和 兩個集合，那么兩集合之間連線的最短邊一定包含在最小局部樹。135用破圈法求最小生成樹方法：從網絡圖N中任取一回路，去掉這個回路中權數最大的一條邊，得一子網絡圖N1在N1中再任取一回路，再去掉回路中權數最大的一條邊，得N2如此繼續下去，一直到剩下的子圖中不再含回路止該子圖就是N的最小局部樹 v1v2v3v5v7v6v4527274263161365.3 最短路問題 最短路問題，一般來說就是從給定的網絡圖中找出任意兩點之間權數最短的一條路。權數可以是距離、時間、費用等。 有些問題，如選址、管道鋪設時的選線、設備更

47、新、投資、某些整數規劃和動態規劃問題，也可以歸結為求最短路問題。 求最短路有兩種算法，一是求從某一點到其他各點之間最短距離的Dijkstra1959算法，另一種是求網絡圖上任意兩點之間最短距離的矩陣算法。137Dijkstra算法(標號算法)的根本思路和步驟 Dijkstra算法由荷蘭計算機大師Dijkstra于1959年提出，可用于求解指定兩點間的最短路，或從指定點到其余點的最短路，目前被認為是求無負權網絡最短路的最好算法。13824351全局最短，局部必最短。 假設用dij表示圖中兩相鄰點i和j的距離，假設i和j不相鄰，令dij =，顯然dii =0，假設用Lsi表示從s到i點的最短距離，

48、現要求從s點到某一點t的最短路，用Dijkstra 算法的步驟如下：139 1從點s出發，因Lss=0，將此值標在s旁的小方框內，表示s點已經標號； 2從s點出發，找出與s相鄰的點中距離最小的一個，設為r,將Lsr = Lss +dsr的值標在r旁的小方框內，說明點r已有標號； 3從已標號的點出發，找出與這些點相鄰的所有未標號點p，假設有Lsp = min Lss+ dsp; Lsr + drp,那么對p點標號，并將Lsp的值標注在p旁小方框中； 4重復第3步，一直到t點得到標號為止。140ex5.5 一艘貨輪在A港裝貨后駛往F港，中途需靠港加油和淡水，從A港到F港全部可能的航線及距離如以下圖

49、所示，F港有三個碼頭F1、F2、F3，試求最合理的停靠的碼頭及航線，使總路程最短。50AB1B2C1C2C3D1D2F1F2F345203060403050604030555030204030141ex5.4 某工廠使用一臺設備，每年年初工廠都要作出決策，如果繼續使用舊的，要付維修費，假設購置新設備，要付購置費。試制定一個5年的更新方案，使總支出最少。 設備在各年的購置費，及不同機器役齡時的殘值與維修費，如下表所示：第1年第2年第3年第4年第5年購買費1112131414機器役齡0-11-22-33-44-5維修費5681118殘值43210142Floyd算法矩陣算法 以任意兩點i,j間的距

50、離來構造矩陣：D=d i jn n，假設i,j 相鄰那么d i j= l i j ,不相鄰那么 d i j = ，顯然 d i i = 0。143v1v2v3v5v7v6v452727426316144ex5.5 某地區的交通網絡如以下圖所示，其中點代表居民小區，邊代表公路，權值為公路距離，問區中心醫院應該建在哪個小區，可使離醫院最遠的居民小區就診時所走的路程最近?302060203018251515v1v2v3v4v5v6v71455.4 最大流問題 最大流問題是一類應用極為廣泛的問題，例如在交通運輸網絡中有人流、車流、貨物流，供水網絡中有水流，金融系統中有現金流，通訊系統中有信息流，等等。

51、 20世紀50年代福特Ford、富克遜Fulkerson建立的“網絡流理論，是網絡應用的重要組成局部。 146最大流有關概念 容量網絡是指對網絡上的每條弧vi，vj)都給出一個最大的通過能力，稱為該弧的容量，記為cvi，vj)或簡寫為cij。 在容量網絡中通常規定一個發點(也稱源點，記為s)和一個收點(也稱匯點，記為t)，網絡中既非發點又非收點的其他點稱為中間點。 網絡的最大流是指網絡中從發點到收點之間允許通過的最大流量對有多個發點和多個收點的網絡，可以另外虛設一個總發點和一個總收點，并將其分別與各發點、收點連起來，就可以轉換為只含一個發點和一個收點的網絡所以下面只研究具有一個發點和一個收點的網絡 147v1v2v3v5v7v6527274316148 流是指加在網絡各條弧上的一組負載量。 對加在弧vi , vj)上的負載量記作fvi , vj) ，或簡寫為fij 假設網絡上所有的fij =0，這個流稱為零流 稱在容量網絡上滿足以下條件的一組流為可行流： (1)容量限制條件對所有弧有： 0 fvi , vj) cvi , vj) (2)中間點j平衡條件： fvi , vj) = fvj , vk) 假設以 v (f) 表示網絡中從s t的流量那么有 fvs , vj) = fvj , vt) 149割和流量 割是指將容量網絡中的發點和收點分割開，并使s f的流中斷的一組