第3章特殊類型的線性規(guī)劃22

第三章特殊類型的線性規(guī)劃一般意義的線性規(guī)劃問題==第一節(jié)運(yùn)輸問題先看一個(gè)具體的例子——例3-1

某廠下屬三個(gè)加工廠同生產(chǎn)一種產(chǎn)品，每天的生產(chǎn)量分別是A1=8噸，A2=7噸，A3=10噸；該工廠把這些產(chǎn)品分別運(yùn)往四個(gè)地區(qū)的門市部銷售，各門市部的銷售量分別為B1=3噸，B2=4噸，B3=9噸，B4=9噸。已知從各加工廠到各門市部的每噸運(yùn)費(fèi)如下表所示。問該工廠如何制定調(diào)運(yùn)產(chǎn)品的方案，在滿足各門市部銷售量的情況下，使總的費(fèi)用為最少？B1B2B3B4A122316A211623A347108先建立數(shù)學(xué)模型假設(shè)從工廠到門市部的運(yùn)輸量為則有Cij為工廠到門市部單位物資的運(yùn)價(jià)ai為第i個(gè)工廠的產(chǎn)量bj為第j個(gè)門市部的銷售量該問題數(shù)學(xué)模型的特點(diǎn)工廠有3(m)個(gè)，門市部有4(n)個(gè)有3×4(

m×n)個(gè)變量有3+4(m+n)個(gè)約束方程用單純形法求解需添加7個(gè)人工變量變量數(shù)增加為19個(gè)，求解計(jì)算量大本例中所建立的數(shù)學(xué)模型一般意義上的系數(shù)矩陣系數(shù)矩陣的每一列元素中均只有兩個(gè)元素為1，其余元素均為零本例中，工廠的產(chǎn)量與門市部的銷量相等，稱為產(chǎn)銷平衡的運(yùn)輸問題。某廠下屬三個(gè)加工廠同生產(chǎn)一種產(chǎn)品，每天的生產(chǎn)量分別是A1=8噸，A2=7噸，A3=10噸；該工廠把這些產(chǎn)品分別運(yùn)往四個(gè)地區(qū)的門市部銷售，各門市部的銷售量分別為B1=3噸，B2=4噸，B3=9噸，B4=9噸。產(chǎn)銷平衡的運(yùn)輸問題一定有最優(yōu)解例3-2為了簡化計(jì)算過程，利用運(yùn)輸問題系數(shù)矩陣的特點(diǎn)，在單純形法的基礎(chǔ)上，創(chuàng)造了一種專門求解運(yùn)輸問題的方法，稱為表上作業(yè)法。表上作業(yè)法的求解過程也包含如下三個(gè)關(guān)鍵步驟：（1）初始基可行解（也稱初始運(yùn)輸方案）的確定；（2）基可行解檢驗(yàn)數(shù)的計(jì)算與最優(yōu)判別；（3）非最優(yōu)基可行解的改進(jìn)（迭代）。

例3-3

假設(shè)某地區(qū)有三個(gè)交通發(fā)生點(diǎn)和四個(gè)交通吸引點(diǎn)，交通發(fā)生點(diǎn)的出行產(chǎn)生量ai、交通吸引點(diǎn)的出行吸引量bj以及各交通發(fā)生點(diǎn)與吸引點(diǎn)之間的運(yùn)輸費(fèi)用如下表所示。問如何組織交通，才能使總的運(yùn)輸費(fèi)用最少？

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO144325O2103475O399845bj162615求解該問題分三個(gè)步驟確定初始方案檢驗(yàn)該方案是否為最優(yōu)方案調(diào)整方案計(jì)算停止是否確定初始方案的方法之一

西北角法

西北角法的基本思想是優(yōu)先產(chǎn)銷平衡表的左上角（西北角）的供應(yīng)關(guān)系。步驟一確定初始方案在逐步確定初始運(yùn)輸方案時(shí)，一般每步要經(jīng)過兩個(gè)過程，先是根據(jù)運(yùn)輸費(fèi)用確定供應(yīng)關(guān)系，然后根據(jù)供需要求進(jìn)行運(yùn)量分配。為了方便，將產(chǎn)銷平衡與運(yùn)輸費(fèi)用表拆成運(yùn)輸費(fèi)用與運(yùn)量分配表。

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO144325O2103475O399845bj162615產(chǎn)銷平衡與出行費(fèi)用表步驟一確定初始方案

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O14432O210347O39984運(yùn)輸費(fèi)用表

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO15O25O35bj162615運(yùn)量分配表從運(yùn)量分配表的最左上角（西北角）的格子開始。讓發(fā)生點(diǎn)O1的物資盡可能多地運(yùn)往吸引點(diǎn)D1。由于吸引點(diǎn)D1需要的物資總量只有1，而發(fā)生地O1要求運(yùn)出的物資總量為5，所以O(shè)1要運(yùn)出的物資總量中1個(gè)單位運(yùn)至D1，即x11=1，將此運(yùn)量１填入運(yùn)量分配表的（O1,D1）格子。這時(shí)吸引點(diǎn)D1物資需求量已經(jīng)滿足，不再需要其他任何發(fā)生地運(yùn)來物資，由平衡條件得x21=0，x31=0。１步驟一確定初始方案

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O14432O210347O39984出行費(fèi)用表

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO1１5O25O35bj162615運(yùn)量分配表從運(yùn)量分配表當(dāng)前的最左上角（西北角）的格子（O1,D２

）開始。讓發(fā)生點(diǎn)O1的物資盡可能多地運(yùn)往吸引點(diǎn)D２。由于吸引點(diǎn)D２需要的物資總量為６，而發(fā)生地O1當(dāng)前能運(yùn)出的物資總量為４，所以O(shè)1能運(yùn)出的物資總量中４個(gè)單位運(yùn)至D２，即x1２=4，將此運(yùn)量４填入運(yùn)量分配表的（O1,D２）格子。這時(shí)發(fā)生地O1物資運(yùn)出量已經(jīng)滿足，不能再向其他任何吸引點(diǎn)運(yùn)送物資，由平衡條件得x1３=0，x1４=0。４步驟一確定初始方案

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O14432O210347O39984出行費(fèi)用表

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO1１４5O25O35bj162615運(yùn)量分配表從運(yùn)量分配表當(dāng)前的最左上角（西北角）的格子（O２,D２）開始。讓發(fā)生點(diǎn)O２的物資盡可能多地運(yùn)往吸引點(diǎn)D２。由于當(dāng)前吸引點(diǎn)D２需要的物資總量只有２，而發(fā)生地O２要求運(yùn)出的物資總量為5，所以O(shè)２要運(yùn)出的物資總量中２個(gè)單位運(yùn)至D２，即x２２=２，將此運(yùn)量２填入運(yùn)量分配表的（O２,D２）格子。這時(shí)吸引點(diǎn)D２物資需求量已經(jīng)滿足，不再需要其他任何發(fā)生地運(yùn)來物資，由平衡條件得x３２=0。２步驟一確定初始方案

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O14432O210347O39984出行費(fèi)用表

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO1１４5O2２5O35bj162615運(yùn)量分配表從運(yùn)量分配表當(dāng)前的最左上角（西北角）的格子（O２,D３）開始。讓發(fā)生點(diǎn)O２的物資盡可能多地運(yùn)往吸引點(diǎn)D３。由于吸引點(diǎn)D３需要的物資總量只有２，而發(fā)生地O２當(dāng)前能運(yùn)出的物資總量為３，所以O(shè)２運(yùn)出的物資總量中２個(gè)單位運(yùn)至D３，即x２３=２，將此運(yùn)量２填入運(yùn)量分配表的（O２,D３）格子。這時(shí)吸引點(diǎn)D３物資需求量已經(jīng)滿足，不再需要其他任何發(fā)生地運(yùn)來物資，由平衡條件得x３３=0。２步驟一確定初始方案

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O14432O210347O39984出行費(fèi)用表

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO1１４5O2２２5O35bj162615運(yùn)量分配表從運(yùn)量分配表當(dāng)前的最左上角（西北角）的格子（O２,D４）開始。讓發(fā)生點(diǎn)O２的物資盡可能多地運(yùn)往吸引點(diǎn)D４。由于吸引點(diǎn)D４需要的物資總量為６，而發(fā)生地O２當(dāng)前能運(yùn)出的物資總量為１，所以O(shè)２運(yùn)出的物資總量中１個(gè)單位運(yùn)至D４，即x２４=１，將此運(yùn)量１填入運(yùn)量分配表的（O２,D４）格子。這時(shí)發(fā)生地D２物資需求量已經(jīng)滿足，不能再向其他任何吸引點(diǎn)運(yùn)來物資。１步驟一確定初始方案

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O14432O210347O39984出行費(fèi)用表

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO1１４5O2２２１5O35bj162615運(yùn)量分配表從運(yùn)量分配表當(dāng)前的最左上角（西北角）的格子（O３,D４）開始。讓發(fā)生點(diǎn)O３的物資盡可能多地運(yùn)往吸引點(diǎn)D４。由于當(dāng)前吸引點(diǎn)D４需要的物資總量為５，而發(fā)生地O３當(dāng)前能運(yùn)出的物資總量為５，所以O(shè)３運(yùn)出的物資總量中５個(gè)單位運(yùn)至D４，即x３４=５，將此運(yùn)量５填入運(yùn)量分配表的（O３,D４）格子。５步驟一確定初始方案

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O14432O210347O39984出行費(fèi)用表

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO1１４5O2２２１5O3５5bj162615運(yùn)量分配表已經(jīng)找到了一個(gè)初始方案＝６１步驟一確定初始方案最小元素法的基本思想是就近供應(yīng)，即依據(jù)單位運(yùn)價(jià)表中最小的運(yùn)價(jià)來確定供需關(guān)系。

確定初始方案的方法之二

最小元素法步驟一確定初始方案

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O14432O210347O39984運(yùn)輸費(fèi)用表

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO15O25O35bj162615運(yùn)量分配表551121從出行費(fèi)用表中選擇最小費(fèi)用項(xiàng)，確定相應(yīng)的運(yùn)量，并使其滿足出行總量平衡條件。初始方案的費(fèi)用為63步驟一確定初始方案最優(yōu)方案的判別

運(yùn)輸方案的最優(yōu)性判別，實(shí)質(zhì)上與單純形法是一樣的。首先，計(jì)算運(yùn)量分配表中每個(gè)空格（即非基變量）的檢驗(yàn)數(shù)，然后判別每個(gè)檢驗(yàn)數(shù)的正負(fù)。因?yàn)檫\(yùn)輸問題是求目標(biāo)函數(shù)極小化的問題，所以，當(dāng)所有≥0時(shí)，此時(shí)的運(yùn)輸方案即為最優(yōu)運(yùn)輸方案，否則，再改進(jìn)當(dāng)前的運(yùn)輸方案。求檢驗(yàn)數(shù)的方法很多。常用方法有兩種：閉回路法和位勢法。步驟二最優(yōu)方案的判別

在原方案的分配表中，從一個(gè)空格開始作一條閉回路，這個(gè)閉回路的邊只能是水平或垂直的；而它的轉(zhuǎn)角，除了開始這個(gè)空格之外，其余的都是填有數(shù)字的格（有交通量的格）。判別最優(yōu)方案的方法之一

閉回路法步驟二最優(yōu)方案的判別

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO1１４5O2２２１5O3５5bj162615運(yùn)量分配表可以證明，運(yùn)量分配表中的任意一個(gè)空格與所有的數(shù)字格組成的格子中，一定有且僅有一個(gè)閉回路步驟二最優(yōu)方案的判別根據(jù)閉回路求檢驗(yàn)數(shù)每一個(gè)空格對(duì)應(yīng)一個(gè)檢驗(yàn)數(shù)每一個(gè)空格的檢驗(yàn)數(shù)根據(jù)該空格的閉回路確定檢驗(yàn)數(shù)的計(jì)算起點(diǎn)空格的運(yùn)費(fèi)為正第一個(gè)轉(zhuǎn)角的運(yùn)費(fèi)為負(fù)第二個(gè)轉(zhuǎn)角的運(yùn)費(fèi)為正第三個(gè)轉(zhuǎn)角的運(yùn)費(fèi)為負(fù)

…

…

…

…

…

…如此正負(fù)交替直至回到起點(diǎn)空格將這些數(shù)字相加，得到該空格的檢驗(yàn)數(shù)步驟二最優(yōu)方案的判別偶數(shù)轉(zhuǎn)角運(yùn)費(fèi)為正奇數(shù)轉(zhuǎn)角運(yùn)費(fèi)為負(fù)

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO1１４5O2２２１5O3５5bj162615運(yùn)量分配表

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O14432O210347O39984出行費(fèi)用表檢驗(yàn)數(shù)λ31=9-4+7-3+4-4=9檢驗(yàn)數(shù)的含義若存在某檢驗(yàn)數(shù)小于0，則對(duì)應(yīng)于該檢驗(yàn)數(shù)的出行量增大，總出行費(fèi)用將減少。若所有的檢驗(yàn)數(shù)都為非負(fù)，則總的出行費(fèi)用將不可能減少。步驟二最優(yōu)方案的判別得到如下的檢驗(yàn)數(shù)表：

D1D2D3D4O1-2-6O27O3997

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4aiO1１４5O2２２１5O3５5bj162615運(yùn)量分配表步驟二最優(yōu)方案的判別判別最優(yōu)方案的方法之二

勢位法步驟二最優(yōu)方案的判別方案的調(diào)整若存在檢驗(yàn)數(shù)小于0，則對(duì)應(yīng)于該檢驗(yàn)數(shù)的出行量增大，總出行費(fèi)用將減少，說明可能存在總費(fèi)用更小的運(yùn)輸方案。步驟三方案的調(diào)整步驟三方案的調(diào)整選擇一個(gè)負(fù)檢驗(yàn)數(shù)找出該負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的閉回路從空格出發(fā)，沿閉合回路前進(jìn)，在各奇數(shù)次轉(zhuǎn)角點(diǎn)數(shù)字（即出行交通量）中，選擇最小值K在閉合回路中，在各奇數(shù)次轉(zhuǎn)角點(diǎn)的數(shù)字都減K，在各偶數(shù)次轉(zhuǎn)角點(diǎn)的數(shù)字都加K步驟三方案的調(diào)整檢驗(yàn)數(shù)D1D2D3D4O1-2-6O27O3997選擇一個(gè)負(fù)檢驗(yàn)數(shù)

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O1１４O2２２１O(jiān)3找出該負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的閉回路從空格出發(fā)，沿閉合回路前進(jìn)，在各奇數(shù)次轉(zhuǎn)角點(diǎn)數(shù)字（即出行交通量）中，選擇最小值Kmin（4，1）=1在閉合回路中，在各奇數(shù)次轉(zhuǎn)角點(diǎn)的數(shù)字都減K，在各偶數(shù)次轉(zhuǎn)角點(diǎn)的數(shù)字都加K

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O1１31O23２0O3對(duì)新得到的分配方案，繼續(xù)進(jìn)行檢驗(yàn)。檢驗(yàn)數(shù)D1D2D3D4O1-2O276O33310

交通吸引點(diǎn)交通發(fā)生點(diǎn)點(diǎn)D1D2D3D4O1１31O23２O3５存在負(fù)檢驗(yàn)數(shù)，目前的方案沒有達(dá)到最優(yōu)步驟三方案的調(diào)整檢驗(yàn)數(shù)D1D2D3D4O1-2O276O3331選擇一個(gè)負(fù)檢驗(yàn)數(shù)

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O1１31O23２O3５找出該負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的閉回路從空格出發(fā)，沿閉合回路前進(jìn)，在各奇數(shù)次轉(zhuǎn)角點(diǎn)數(shù)字（即出行交通量）中，選擇最小值Kmin（3，2）=2在閉合回路中，在各奇數(shù)次轉(zhuǎn)角點(diǎn)的數(shù)字都減K，在各偶數(shù)次轉(zhuǎn)角點(diǎn)的數(shù)字都加K

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O1１121O2500O3５對(duì)新得到的分配方案，繼續(xù)進(jìn)行檢驗(yàn)。

交通吸引點(diǎn)交通發(fā)生點(diǎn)D1D2D3D4O1１121O25O3５檢驗(yàn)數(shù)D1D2D3D4O1O2726O3333所有的檢驗(yàn)數(shù)都為非負(fù)，則總的出行費(fèi)用將不可能減少，目前得到的方案為最優(yōu)的運(yùn)輸方案。運(yùn)輸問題的作業(yè)教材習(xí)題3-2工程中有些線性規(guī)劃問題要求解為整數(shù)如：

以人員、車輛等規(guī)劃對(duì)象原有的計(jì)算方法得到的解存在非整數(shù)的可能第二節(jié)

整數(shù)規(guī)劃

求解整數(shù)規(guī)劃的方法—分枝定界法先看一個(gè)實(shí)例先不考慮整數(shù)約束，解相應(yīng)的線性規(guī)劃問題為了討論方便，將原線性規(guī)劃問題稱為L1。L1的最優(yōu)解為x1=2.25，x2=3.75，Z=41.25例3-4L1的最優(yōu)解為x1=2.25，x2=3.75不滿足整數(shù)條件劃分可行域取x2≤3，x2≥4L2L3任取一個(gè)沒有滿足整數(shù)條件的變量L2的最優(yōu)解為x1=1.8，x2=4，Z=41L3的最優(yōu)解為x1=3，x2=3，Z=39L2L3已經(jīng)得到整數(shù)解L2的最優(yōu)解為x1=1.8，x2=4不滿足整數(shù)條件劃分可行域取x1≤1，x1≥2L4L5L4的最優(yōu)解為x1=1，x2=4.44，Z=40.444L5無最優(yōu)解L4的最優(yōu)解為x1=1，x2=4.44不滿足整數(shù)條件劃分可行域取x2≤4，x2≥5L6L7L6的最優(yōu)解為x1=1，x2=4，Z=37L7的最優(yōu)解為x1=0，x2=5，Z=40原問題LP1新問題LP2新問題LP3新問題LP5新問題LP4新問題LP7新問題LP6直到找到最優(yōu)整數(shù)解或無最優(yōu)解匯總整數(shù)解非整數(shù)解非整數(shù)解無最優(yōu)解整數(shù)解整數(shù)解非整數(shù)解總結(jié)：分枝定界法思路：首先不考慮解為整數(shù)的要求，用單純形法求最優(yōu)解，以此作為目標(biāo)函數(shù)值的上限或下限；其次，選擇其中一個(gè)非整數(shù)的變量，根據(jù)與兩側(cè)相近的整數(shù)劃分可行域，在縮小的可行域內(nèi)尋求最優(yōu)整數(shù)解，以此作為目標(biāo)函數(shù)值的上限或下限；不斷重復(fù)以上過程，直到每一個(gè)可能進(jìn)一步分解的非整數(shù)都找到整數(shù)解時(shí)為止，整數(shù)規(guī)劃作業(yè)教材習(xí)題3-70-1整數(shù)規(guī)劃0-1規(guī)劃是指變量只能取0或1的線性規(guī)劃，是一種特殊的整數(shù)規(guī)劃。在進(jìn)行實(shí)際問題最優(yōu)決策和處理問題時(shí)常常會(huì)碰到這樣的0-1規(guī)劃。例3-5

某道橋公司在同一時(shí)間內(nèi)可參加A1、A2、A3、A4四項(xiàng)工程的投標(biāo)。這些項(xiàng)目要求的工期相同。公司根據(jù)招標(biāo)文件和本公司的技術(shù)水平對(duì)每項(xiàng)工程進(jìn)行了仔細(xì)的研究和計(jì)算，將各項(xiàng)工程的預(yù)期利潤，主要工序的工程量及本企業(yè)的施工能力見下表。問該公司對(duì)哪幾種項(xiàng)目投標(biāo)可能獲得的總利潤最大？試建立這個(gè)問題的數(shù)學(xué)模型。工程項(xiàng)目預(yù)期利潤（萬元）土石方量（m3）混凝土量（m3）其他材料（m3）A1542002802500A282300880480A37.548003001500A4923009005200施工能力1200016009000建立模型設(shè)則建立的數(shù)學(xué)模型0-1規(guī)劃的一般形式0-1規(guī)劃的求解方法——窮舉法每個(gè)變量都只取0，1兩個(gè)值，變量取值的0-1組合是有限的。先列出各變量分別取0或1值的每一種組合，然后在滿足約束條件的變量的0-1組合中找出使目標(biāo)函數(shù)達(dá)到最優(yōu)值的組合即是該0-1規(guī)劃的最優(yōu)解。用這種方法求解變量個(gè)數(shù)為n的0-1規(guī)劃，通常需檢查2n個(gè)組合計(jì)算量大，隨變量數(shù)量的增加呈集合級(jí)數(shù)增長設(shè)計(jì)一種方法，只要檢查變量取值的一部分就能得到原問題的最優(yōu)解。這種方法稱為隱枚舉法。例3-6解：首先，通過試探的方法找到一個(gè)可行解。容易看出,(x1,x2,x3)=(1,0,0)是滿足約束條件的可行解。相應(yīng)的目標(biāo)函數(shù)值為S=3。對(duì)于最大化問題，希望S≥3，因此，增加一個(gè)約束條件過濾條件新的0-1規(guī)劃問題為（0）全部枚舉的方法，3個(gè)變量有8種組合原先4個(gè)約束方程，需要32次計(jì)算增加過濾條件后，可減少計(jì)算次數(shù)解約束條件是否滿足條件？S值（0）（1）（2）（3）（4）（0，0，0）0（0，0，1）5-11015（0，1，0）-2（0，1，1）315（1，0，0）311103（1，0，1）802118（1，1，0）1（1，1，1）626（0）0-1規(guī)劃作業(yè)教材習(xí)題3-5第三節(jié)資源分配問題

有n項(xiàng)任務(wù)，分配給n個(gè)人去完成，要求每個(gè)人完成其中一項(xiàng)任務(wù)，每項(xiàng)任務(wù)只交給其中一個(gè)人完成，已知每個(gè)人完成各項(xiàng)任務(wù)的成本（或效率），求使總成本最少的分配方案。

目的地車輛編號(hào)D1D2D3D4D5D6146665559202822481256225913282239502786446314547545856544644331606322434243364設(shè)某運(yùn)輸隊(duì)有6輛卡車，需分派駛往6個(gè)不同的目的地，由于各輛卡車的性能、消耗和效率不同，因而駛往各目的地的運(yùn)輸成本也不同，如下表所示。試求能使總成本最低的車輛分派方案。例3-7效率矩陣建立數(shù)學(xué)模型資源分配問題的一般模型minZ=s.t.運(yùn)輸問題整數(shù)規(guī)劃資源分配問題資源分配問題的求解方法—匈牙利法定理

效率矩陣的任意一行（列）各元素中分別減去同一常數(shù)，得一變換了的矩陣，則以之為效率矩陣的分派問題最優(yōu)解與原問題的最優(yōu)解相同。

匈牙利法的指導(dǎo)思想設(shè)法對(duì)效率矩陣進(jìn)行變換，使變換后的效率矩陣中有n個(gè)位于不同行不同列的零元素（以下稱為獨(dú)立零元素），沒有負(fù)元素。令n個(gè)獨(dú)立零元素對(duì)應(yīng)的n個(gè)xij＝１，其余的xij＝0匈牙利法的解題步驟——例3-8

有5輛公交車可以在5條公交線路上行駛。不同車輛在不同的路線上發(fā)生的年平均交通事故數(shù)如下表所示。這5輛公交車如何分配，才能使全年的總事故數(shù)最少？匈牙利法的解題步驟

線路編號(hào)車輛R1R2R3R4R5D173328D2108697D392706D460835D553427使費(fèi)用矩陣每行中出現(xiàn)零元素在各行中減去各行的最小元素使費(fèi)用矩陣出現(xiàn)0元素332886972706083553427110620312706083531205初始的費(fèi)用矩陣110620312706083531205第一列、第五列中無0元素。在第一列、第五列中分別減該列的最小元素。使費(fèi)用矩陣出現(xiàn)0元素2110512030627053083401204費(fèi)用矩陣每行、每列中都出現(xiàn)了0元素檢驗(yàn)是否存在位于

不同行不同列的n個(gè)0元素檢驗(yàn)是否存在不同行列的0元素2110512030627053083401204行檢驗(yàn)：若某行只有一個(gè)零元素，則給這零元素加“Δ”，該零元素為獨(dú)立零元素。若某行零元素多于一個(gè)，則暫不標(biāo)號(hào)。每行、每列只能有一個(gè)獨(dú)立零元素檢驗(yàn)是否存在不同行列的0元素2110512030627053083401204列檢驗(yàn)：若某列只有一個(gè)零元素，則給這零元素加“Δ”，該零元素為獨(dú)立零元素。若某列零元素多于一個(gè)，則暫不標(biāo)號(hào)。沒有得到位于不同行不同列的n個(gè)0元素方案的變換方案變換在所有沒有被分配的行打上“”號(hào)。2110512030627053083401204在已打“”號(hào)的行中找出打“”的列，并打“”。在已打“”號(hào)的列中找出打“Δ”的行，并打“”。重復(fù)以上過程，直到無法打“”時(shí)為止。方案變換2110512030627053083401204對(duì)所有打“”號(hào)的列和未打“”號(hào)的行劃線。這些線可以將所有的0元素至少覆蓋一次。如果是MM矩陣，而又要使最優(yōu)解分配在0元素位置上，劃線數(shù)量應(yīng)為M。本例還沒有達(dá)到最優(yōu)解。方案變換在未劃線的元素中找出最小元素2110512030627053083401204未劃線的各行元素減去這個(gè)最小元素已劃線的各列元素加上這個(gè)最小元素1000412040516043084401214對(duì)新的費(fèi)用矩陣進(jìn)行行檢驗(yàn)與列檢驗(yàn)1000412040516043084401214行檢驗(yàn)：若某行只有一個(gè)零元素，則給這零元素加“Δ”，該零元素為獨(dú)立零元素。若某行零元素多于一個(gè)，則暫不標(biāo)號(hào)。1000412040516043084401