人大錄屏2021下半年運籌學

Chapter3運輸規(guī)劃

(TransportationProblem)運輸規(guī)劃問題的數(shù)學模型表上作業(yè)法運輸問題的應用本章主要內(nèi)容：運輸規(guī)劃問題的數(shù)學模型例3.1某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1,B2,B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應如何調(diào)運可使總運輸費用最??？B1B2B3產(chǎn)量A1646200A2655300銷量150150200運輸規(guī)劃問題的數(shù)學模型解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝500

設xij

為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）運輸規(guī)劃問題的數(shù)學模型運輸問題的一般形式：產(chǎn)銷平衡A1、A2、…、Am

表示某物資的m個產(chǎn)地；B1、B2、…、Bn

表示某物質(zhì)的n個銷地；ai

表示產(chǎn)地Ai的產(chǎn)量；bj

表示銷地Bj

的銷量；cij表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。設xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：運輸規(guī)劃問題的數(shù)學模型變化：

1）有時目標函數(shù)求最大。如求利潤最大或營業(yè)額最大等；

2）當某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)；

3）產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。定理:

設有m個產(chǎn)地n個銷地且產(chǎn)銷平衡的運輸問題，則基變量數(shù)為m+n-1。表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其實質(zhì)是單純形法。步驟描述方法第一步求初始基行可行解（初始調(diào)運方案）最小元素法、元素差額法、第二步求檢驗數(shù)并判斷是否得到最優(yōu)解當非基變量的檢驗數(shù)σij全都非負時得到最優(yōu)解，若存在檢驗數(shù)σij<0，說明還沒有達到最優(yōu)，轉第三步。閉回路法和位勢法第三步調(diào)整運量，即換基，選一個變量出基，對原運量進行調(diào)整得到新的基可行解，轉入第二步表上作業(yè)法例3.2某運輸資料如下表所示：單位銷地運價產(chǎn)地產(chǎn)量311310719284741059銷量3656問：應如何調(diào)運可使總運輸費用最??？表上作業(yè)法解：第1步求初始方案方法1：最小元素法基本思想是就近供應，即從運價最小的地方開始供應（調(diào)運），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058341633表上作業(yè)法總的運輸費＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元

元素差額法對最小元素法進行了改進，考慮到產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方案。85102120151515510總運費是z=10×8+5×2+15×1=105最小元素法：表上作業(yè)法85102120151551510總運費z=10×5+15×2+5×1=85后一種方案考慮到C11與C21之間的差額是8－2=6，如果不先調(diào)運x21，到后來就有可能x11≠0，這樣會使總運費增加較大，從而先調(diào)運x21，再是x22，其次是x12用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。表上作業(yè)法方法2：Vogel法1）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量行差額A170A2

41A391銷量3656列差額2513311310192741058表上作業(yè)法2）再從差值最大的行或列中找出最小運價確定供需關系和供需數(shù)量。當產(chǎn)地或銷地中有一方數(shù)量供應完畢或得到滿足時，劃去運價表中對應的行或列。重復1)和2)，直到找出初始解為至。B1B2B3B4產(chǎn)量行差額A170A2

41A3

91銷量3656列差額25133113101927410586表上作業(yè)法單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額01135216××表上作業(yè)法單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額0231216×××3×表上作業(yè)法單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額021216×××3×3×表上作業(yè)法單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額6×××3×3×125該方案的總運費:(2×3)＋(3×5)+(1×1)＋(3×8)＋(4×6)+(3×5)＝85元表上作業(yè)法第2步最優(yōu)解的判別（檢驗數(shù)的求法）

求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為λij由第一章知，求最小值的運輸問題的最優(yōu)判別準則是：所有非基變量的檢驗數(shù)都非負，則運輸方案最優(yōu)求檢驗數(shù)的方法有兩種：閉回路法位勢法（▲）表上作業(yè)法閉回路的概念為一個閉回路，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表表上作業(yè)法例下表中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8個頂點，這8個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43

一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉90度與另一頂點連接，表3－3中的變量x32及x33不是閉回路的頂點，只是連線的交點。表上作業(yè)法閉回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如變量組不能構成一條閉回路，但A中包含有閉回路

變量組變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；表上作業(yè)法用位勢法對初始方案進行最優(yōu)性檢驗：1）由ij=Cij-（Ui+Vj）計算位勢Ui

，Vj

，因?qū)兞慷杂衖j=0，即Cij-（Ui+Vj）=0，令U1=02）再由ij=Cij-（Ui+Vj）計算非基變量的檢驗數(shù)ijB1B2B3B4UiA1A2A3Vj3113101927410584363130-1-531029（1）（2）（1）（-1）（10）（12）當存在非基變量的檢驗數(shù)kl≥0，說明現(xiàn)行方案為最優(yōu)方案，否則目標成本還可以進一步減小。表上作業(yè)法當存在非基變量的檢驗數(shù)kl<0且kl=min{ij}時，令Xkl進基。從表中知可選X24進基。第3步確定換入基的變量第4步確定換出基的變量以進基變量xik為起點的閉回路中，標有負號的最小運量作為調(diào)整量θ，θ對應的基變量為出基變量，并打上“×”以示換出作為非基變量。表上作業(yè)法B1B2B3B4UiA1A2A3Vj311310192741058436313(＋)(－)(＋)(－)調(diào)整步驟為：在進基變量的閉回路中標有正號的變量加上調(diào)整量θ，標有負號的變量減去調(diào)整量θ，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗數(shù)重新檢驗。125表上作業(yè)法當所有非基變量的檢驗數(shù)均非負時，則當前調(diào)運方案即為最優(yōu)方案，如表此時最小總運費：Z=(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元B1B2B3B4UiA1A2A3Vj3113101927410585363120-2-531039（0）（2）（2）（1）（12）（9）表上作業(yè)法表上作業(yè)法的計算步驟：分析實際問題列出產(chǎn)銷平衡表及單位運價表確定初始調(diào)運方案（最小元素法或Vogel法）求檢驗數(shù)（位勢法）所有檢驗數(shù)≥0找出絕對值最大的負檢驗數(shù)，用閉合回路調(diào)整，得到新的調(diào)運方案得到最優(yōu)方案，算出總運價表上作業(yè)法表上作業(yè)法計算中的問題：（1）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標函數(shù)值得到改善，但通常取σij<0中最小者對應的變量為換入變量。（2）無窮多最優(yōu)解 產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。表上作業(yè)法⑵退化解：

※表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量時則需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個0即可。

※利用進基變量的閉回路對解進行調(diào)整時，標有負號的最小運量（超過2個最小值）作為調(diào)整量θ，選擇任意一個最小運量對應的基變量作為出基變量，并打上“×”以示作為非基變量。表上作業(yè)法

銷地產(chǎn)地B1B2B3B4產(chǎn)量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11檢驗數(shù)是0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。表上作業(yè)法

銷地產(chǎn)地B1B2B3B4產(chǎn)量A17A24A39銷量36562011443137782106×3×416×06×××在x12、x22、x33、x34中任選一個變量作為基變量，例如選x34例：用最小元素法求初始可行解運輸問題的應用

求極大值問題目標函數(shù)求利潤最大或營業(yè)額最大等問題。運輸問題的應用求解方法： 將極大化問題轉化為極小化問題。設極大化問題的運價表為C，用一個較大的數(shù)M（M≥max{cij}）去減每一個cij得到矩陣C′，其中C′=（M－cij）≥0,將C′作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解。運輸問題的應用例3.3下列矩陣C是Ai（I=1，2，3）到Bj的噸公里利潤,運輸部門如何安排運輸方案使總利潤最大.

銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量8149運輸問題的應用

銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量8149得到新的最小化運輸問題，用表上作業(yè)法求解即可。運輸問題的應用

產(chǎn)銷不平衡的運輸問題 當總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題.這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。

當產(chǎn)大于銷時，即：數(shù)學模型為：運輸問題的應用由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設一個倉庫，假設該倉庫為一個虛擬銷地Bn+1，bn+1作為一個虛設銷地Bn+1的銷量(即庫存量)。各產(chǎn)地Ai到Bn+1的運價為零，即Ci,n+1=0,（i=1，…，m）。則平衡問題的數(shù)學模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可運輸問題的應用

當銷大于產(chǎn)時，即：數(shù)學模型為：由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設一個產(chǎn)地Am+1，產(chǎn)量為：運輸問題的應用銷大于產(chǎn)化為平衡問題的數(shù)學模型為：具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。運輸問題的應用例3.4求下列表中極小化運輸問題的最優(yōu)解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因為有：運輸問題的應用所以是一個產(chǎn)大于銷的運輸問題。表中A2不可達B1，用一個很大的正數(shù)M表示運價C21。虛設一個銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，得到新的運價表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180運輸問題的應用下表為計算結果?？煽闯觯寒a(chǎn)地A4還有20個單位沒有運出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180運輸問題的應用3.生產(chǎn)與儲存問題例3.5某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。季度生產(chǎn)能力/臺單位成本/萬元Ⅰ2510.8Ⅱ3511.1Ⅲ3011Ⅳ1011.3運輸問題的應用解：設xij為第i季度生產(chǎn)的第j季度交貨的柴油機數(shù)目，那么應滿足：交貨：

x11=10生產(chǎn)：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度生產(chǎn)的柴油機數(shù)目看作第i個生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機數(shù)目看作第j個銷售點的銷量；設cij是第i季度生產(chǎn)的第j季度交貨的每臺柴油機的實際成本，應該等于該季度單位成本加上儲存、維護等費用?？蓸嬙煜铝挟a(chǎn)銷平衡問題：運輸問題的應用jiⅠⅡⅢⅣ產(chǎn)量Ⅰ10.810.9511.111.2525ⅡM11.1011.2511.4035ⅢMM11.0011.1530ⅣMMM11.3010銷量1015252010070由于產(chǎn)大于銷，加上一個虛擬的銷地D，化為平衡問題，即可應用表上作業(yè)法求解。運輸問題的應用該問題的數(shù)學模型：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23 +11.4x24+11.0x33+11.15x34+11.3x44

jiⅠⅡⅢⅣD產(chǎn)量Ⅰ10.810.9511.111.25025ⅡM11.1011.2511.40035ⅢMM11.0011.15030ⅣMMM11.30010銷量1015252030100100運輸問題的應用jiⅠⅡⅢⅣD產(chǎn)量Ⅰ1015025Ⅱ053035Ⅲ25530Ⅳ1010銷量1015252030100100最優(yōu)生產(chǎn)決策如下表，最小費用z＝773萬元。Chapter4整數(shù)規(guī)劃

(IntegerProgramming)整數(shù)規(guī)劃的特點及應用分支定界法分配問題與匈牙利法本章主要內(nèi)容：整數(shù)規(guī)劃的特點及應用整數(shù)規(guī)劃（簡稱：IP） 要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標函數(shù)和約束條件構成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃數(shù)學模型的一般形式：整數(shù)規(guī)劃的特點及應用整數(shù)線性規(guī)劃問題的種類：

純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃?；旌险麛?shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。

0-1型整數(shù)線性規(guī)劃：決策變量只能取值0或1的整數(shù)線性規(guī)劃。整數(shù)規(guī)劃的特點及應用整數(shù)規(guī)劃的典型例子例4.1工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應求，故需要再建一家工廠。相應的建廠方案有A3和A4兩個。這種物資的需求地有B1,B2,B3,B4四個。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運費cij，見下表：B1B2B3B4年生產(chǎn)能力A12934400A28357600A37612200A44525200年需求量350400300150工廠A3或A4開工后，每年的生產(chǎn)費用估計分別為1200萬或1500萬元?，F(xiàn)要決定應該建設工廠A3還是A4，才能使今后每年的總費用最少。整數(shù)規(guī)劃的特點及應用解：這是一個物資運輸問題，特點是事先不能確定應該建A3還是A4中哪一個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)物資。為此，引入0-1變量：再設xij為由Ai運往Bj的物資數(shù)量，單位為千噸；z表示總費用，單位萬元。則該規(guī)劃問題的數(shù)學模型可以表示為：整數(shù)規(guī)劃的特點及應用混合整數(shù)規(guī)劃問題整數(shù)規(guī)劃的特點及應用例4.2現(xiàn)有資金總額為B?？晒┻x擇的投資項目有n個，項目j所需投資額和預期收益分別為aj和cj（j＝1,2,..,n），此外由于種種原因，有三個附加條件：若選擇項目1，就必須同時選擇項目2。反之不一定項目3和4中至少選擇一個；項目5,6,7中恰好選擇2個。應該怎樣選擇投資項目，才能使總預期收益最大。整數(shù)規(guī)劃的特點及應用解：對每個投資項目都有被選擇和不被選擇兩種可能，因此分別用0和1表示，令xj表示第j個項目的決策選擇，記為：投資問題可以表示為：整數(shù)規(guī)劃的特點及應用例4.3指派問題或分配問題。人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經(jīng)考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。

工作人員ABCD甲85927390乙95877895丙82837990丁86908088整數(shù)規(guī)劃的特點及應用設數(shù)學模型如下：要求每人做一項工作，約束條件為：整數(shù)規(guī)劃的特點及應用每項工作只能安排一人，約束條件為：變量約束：整數(shù)規(guī)劃的特點及應用整數(shù)規(guī)劃問題解的特征：

整數(shù)規(guī)劃問題的可行解集合是它松弛問題可行解集合的一個子集，任意兩個可行解的凸組合不一定滿足整數(shù)約束條件，因而不一定仍為可行解。整數(shù)規(guī)劃問題的可行解一定是它的松弛問題的可行解（反之不一定），但其最優(yōu)解的目標函數(shù)值不會優(yōu)于后者最優(yōu)解的目標函數(shù)值。整數(shù)規(guī)劃的特點及應用例4.3設整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。整數(shù)規(guī)劃的特點及應用用圖解法求出最優(yōu)解為：x1＝3/2,x2=10/3，且有Z=29/6

現(xiàn)求整數(shù)解(最優(yōu)解):如用舍入取整法可得到4個點即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。x1x2⑴⑵33(3/2,10/3)

按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如右圖所示。其中(2,2),(3,1)點的目標函數(shù)值最大，即為Z=4。整數(shù)規(guī)劃的特點及應用整數(shù)規(guī)劃問題的求解方法：

分支定界法和割平面法匈牙利法（指派問題）分支定界法1）求整數(shù)規(guī)劃的松弛問題最優(yōu)解； 若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉下一步；2）分支與定界： 任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束：xi≤[xi]和xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界。 檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標函數(shù)值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算，若還存在非整數(shù)解并且目標值大于(max)整數(shù)解的目標值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。分支定界法的解題步驟：分支定界法例4.4用分枝定界法求解整數(shù)規(guī)劃問題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題(原整數(shù)規(guī)劃問題的松馳問題)LPIP分支定界法用圖解法求松弛問題的最優(yōu)解，如圖所示。x1x2⑴⑵3(18/11,40/11)⑶21123x1＝18/11,x2=40/11Z=－218/11≈(－19.8)即Z也是IP最小值的下限。對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2≤3，x2≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2分支定界法分支：分別求出（LP1）和（LP2）的最優(yōu)解。分支定界法先求LP1,如圖所示。此時在B點取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問題已探明，此枝停止計算。x1x2⑴⑵33(18/11,40/11)⑶11BAC同理求LP2,如圖所示。在C

點取得最優(yōu)解。即:x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z(2)<Z(1)＝－16∴原問題有比－16更小的最優(yōu)解，但x2不是整數(shù)，故繼續(xù)分支。分支定界法在IP2中分別再加入條件：x2≤3,x2≥4得下式兩支：分別求出LP21和LP22的最優(yōu)解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACD先求LP21,如圖所示。此時D在點取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(21)＝-87/5≈-17.4<Z(1)=-16但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1≤2。求LP22，如圖所示。無可行解，故不再分枝。分支定界法

在（LP21）的基礎上繼續(xù)分枝。加入條件3≤x1≤2有下式：分別求出（LP211）和（LP212）的最優(yōu)解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACDEF先求（LP211）,如圖所示。此時在E點取得最優(yōu)解。即x1＝2,x2=3,Z(211)＝－17找到整數(shù)解，問題已探明，此枝停止計算。求（LP212），如圖所示。此時F在點取得最優(yōu)解。即x1＝3,x2=2.5,Z(212)＝－31/2≈－15.5>Z(211)

如對LP212繼續(xù)分解，其最小值也不會低于－15.5，問題探明,剪枝。分支定界法原整數(shù)規(guī)劃問題的最優(yōu)解為:x1=2,x2=3,Z*=－17以上的求解過程可以用一個樹形圖表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP21x1=12/5,x2=3Z(21)

＝－17.4LP22無可行解LP211x1=2,x2=3Z(211)

＝－17LP212x1=3,x2=5/2Z(212)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃分支定界法例4.5用分枝定界法求解解:先求對應的松弛問題（記為LP0）用圖解法得到最優(yōu)解X＝(3.57,7.14),Z0=35.7,如下圖所示。分支定界法1010松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC分支定界法10x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8①②LP2:X=(4,6.5),Z2=35.5分支定界法10x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336分支定界法10x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212分支定界法上述分枝過程可用下圖表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP21:X=(4.33,6)Z21=35.33x2≤6LP211:X=(4,6)Z211=34LP212:X=(5,5)Z212=35x1≤4x1≥5LP22無可行解x2≥7小結學習要點：掌握一般整數(shù)規(guī)劃問題概念及模型結構掌握分支定界法原理能夠用分支定界法求解一般整數(shù)規(guī)劃問題課后練習：分配問題與匈牙利法指派問題的數(shù)學模型的標準形式：

設n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作的效率（時間或費用）為Cij(i=1.2…n;j=1.2…n)并假設Cij≥0。問應如何分配才能使總效率（時間或費用）最高？設決策變量分配問題與匈牙利法指派問題的數(shù)學模型為：分配問題與匈牙利法克尼格定理:

如果從分配問題效率矩陣[aij]的每一行元素中分別減去(或加上)一個常數(shù)ui，從每一列中分別減去(或加上)一個常數(shù)vj，得到一個新的效率矩陣[bij]，則以[bij]為效率矩陣的分配問題與以[aij]為效率矩陣的分配問題具有相同的最優(yōu)解。分配問題與匈牙利法指派問題的求解步驟：1)變換指派問題的系數(shù)矩陣(cij)為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即從(cij)的每行元素都減去該行的最小元素；再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。2)進行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。分配問題與匈牙利法找獨立0元素，常用的步驟為：

從只有一個0元素的行開始，給該行中的0元素加圈，記作◎。然后劃去◎所在列的其它0元素，記作?

；這表示該列所代表的任務已指派完，不必再考慮別人了。依次進行到最后一行。從只有一個0元素的列開始（畫?的不計在內(nèi)），給該列中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?

，表示此人已有任務，不再為其指派其他任務了。依次進行到最后一列。若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸瓦M行，直到所有0元素都已圈出和劃掉為止。分配問題與匈牙利法

若◎元素的數(shù)目m等于矩陣的階數(shù)n（即：m＝n），那么這指派問題的最優(yōu)解已得到。若m<n,則轉入下一步。3)用最少的直線通過所有0元素。其方法：

對沒有◎的行打“√”；對已打“√”

的行中所有含?元素的列打“√”

；再對打有“√”的列中含◎元素的行打“√”

；重復①、②直到得不出新的打√號的行、列為止；對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。注：l應等于m，若不相等，說明試指派過程有誤，回到第2步，另行試指派；若l＝m<n，表示還不能確定最優(yōu)指派方案，須再變換當前的系數(shù)矩陣，以找到n個獨立的0元素，為此轉第4步。分配問題與匈牙利法4)變換矩陣(bij)以增加0元素 在沒有被直線通過的所有元素中找出最小值，沒有被直線通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉回第2步。分配問題與匈牙利法例4.6有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務，可使總時間最少？

任務人員ABCD甲67112乙4598丙31104丁5982分配問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素。－52）試指派（找獨立0元素）◎◎◎??

找到3個獨立零元素但m=3<n=

4分配問題與匈牙利法3）作最少的直線覆蓋所有0元素

◎◎◎??√√√獨立零元素的個數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；4）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩陣，將沒有被直線通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。得到新的矩陣，重復2）步進行試指派分配問題與匈牙利法000000試指派◎◎◎??◎得到4個獨立零元素，所以最優(yōu)解矩陣為：即完成4個任務的總時間最少為：2＋4＋1+8=15分配問題與匈牙利法例4.7已知四人分別完成四項工作所需時間如下表，求最優(yōu)分配方案。

任務人員ABCD甲215134乙1041415丙9141613丁78119分配問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素?！?◎??◎◎2）試指派（找獨立0元素）獨立0元素的個數(shù)為4,指派問題的最優(yōu)指派方案即為甲負責D工作，乙負責B工作，丙負責A工作，丁負責C工作。這樣安排能使總的工作時間最少，為4＋4＋9＋11＝28。分配問題與匈牙利法例4.8已知五人分別完成五項工作耗費如下表，求最優(yōu)分配方案。

任務人員ABCDE甲