運(yùn)籌學(xué)運(yùn)輸與指派問(wèn)題.ppt

,運(yùn)籌學(xué) Operations Research,Chapter 5 運(yùn)輸與指派問(wèn)題 Transportation and Assignment Problem,5.1運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特征 5.2 運(yùn)輸單純形法 5.3 運(yùn)輸模型的應(yīng)用 5.4 指派問(wèn)題,5.1 運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特征 Mathematical Model of Transportation Problems,人們?cè)趶氖律a(chǎn)活動(dòng)中，不可避免地要進(jìn)行物資調(diào)運(yùn)工作。如某時(shí)期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類(lèi)物資，分別運(yùn)到需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量和需要量及各地之間的運(yùn)輸費(fèi)用，如何制定一個(gè)運(yùn)輸方案，使總的運(yùn)輸費(fèi)用最小。這樣的問(wèn)題稱(chēng)為運(yùn)輸問(wèn)題。,5.1 運(yùn)輸模型 Model of Transportation Problems,5.1.1 數(shù)學(xué)模型,產(chǎn)地,銷(xiāo)地,A1 10,A2 8,B4 3,3,5,4,2,3,1,6,8,2,3,2,9,圖5.1,【例5-1】現(xiàn)有A1，A2，A3三個(gè)產(chǎn)糧區(qū)，可供應(yīng) 糧食分別為10，8，5（萬(wàn)噸），現(xiàn)將糧食運(yùn)往B1，B2，B3，B4四個(gè)地區(qū)，其需要量分別為5，7，8，3（萬(wàn)噸）。產(chǎn)糧地到需求地的運(yùn)價(jià)（元/噸）如表5-1所示，問(wèn)如何安排一個(gè)運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)用最少。,運(yùn)價(jià)表（元/噸）,表5-1,5.1 運(yùn)輸模型 Model of Transportation Problems,設(shè)xij(i=1,2,3；j=1,2,3,4)為i個(gè)產(chǎn)糧地運(yùn)往第j個(gè)需求地的運(yùn)量，這樣得到下列運(yùn)輸問(wèn)題的數(shù)學(xué)模型：,運(yùn)量應(yīng)大于或等于零（非負(fù)要求），即,5.1 運(yùn)輸模型 Model of Transportation Problems,有些問(wèn)題表面上與運(yùn)輸問(wèn)題沒(méi)有多大關(guān)系，也可以建立與運(yùn)輸問(wèn)題形式相同的數(shù)學(xué)模型,看一個(gè)例子： 【例5-2】有三臺(tái)機(jī)床加工三種零件，計(jì)劃第i臺(tái)的生產(chǎn)任務(wù)為a i (i=1,2,3)個(gè)零件，第j種零件的需要量為bj (j=1,2,3)，第i臺(tái)機(jī)床加工第j種零件需要的時(shí)間為cij ，如表52所示。問(wèn)如何安排生產(chǎn)任務(wù)使總的加工時(shí)間最少？,表52,5.1 運(yùn)輸模型 Model of Transportation Problems,【解】 設(shè) xi j (i=1,2,3；j=1,2,3,)為第i臺(tái)機(jī)床加工第j種零件的數(shù)量，則此問(wèn)題的數(shù)學(xué)模型為,5.1 運(yùn)輸模型 Model of Transportation Problems,5.1.2 模型特征 運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型,設(shè)有m個(gè)產(chǎn)地（記作A1，A2，A3,Am），生產(chǎn)某種物資，其產(chǎn)量分別為a1,a2，am；有n個(gè)銷(xiāo)地（記作B1，B2，Bn），其需要量分別為b1,b2，bn；且產(chǎn)銷(xiāo)平衡，即 。從第i個(gè)產(chǎn)地到j(luò) 個(gè)銷(xiāo)地的單位運(yùn)價(jià)為cij ，在滿足各地需要的前提下，求總運(yùn)輸費(fèi)用最小的調(diào)運(yùn)方案。,5.1 運(yùn)輸模型 Model of Transportation Problems,設(shè)xij(i=1,2,，m；j=1,2,n)為第i個(gè)產(chǎn)地到第j個(gè)銷(xiāo)地的運(yùn)量， 則數(shù)學(xué)模型為：,5.1 運(yùn)輸模型 Model of Transportation Problems,m 行,n 行,5.1 運(yùn)輸模型 Model of Transportation Problems,運(yùn)輸問(wèn)題具有如下特點(diǎn): 1.運(yùn)輸問(wèn)題存在可行解，也一定存在最優(yōu)解 2.當(dāng)供應(yīng)量和需求量都是整數(shù)時(shí)，則一定存在整數(shù)最優(yōu)解 3.有m+n個(gè)約束，mn個(gè)變量 4.約束條件系數(shù)矩陣的元素等于0或1 5.約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素,這對(duì)應(yīng)于每一個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次,在后n個(gè)約束方程中也出現(xiàn)一次 6.所有約束方程都是等式方程 7.各產(chǎn)地產(chǎn)量之和等于各銷(xiāo)地銷(xiāo)量之和 8.有m+n1個(gè)基變量,因?yàn)楫a(chǎn)銷(xiāo)平衡,所以模型最多只有m+n-1個(gè)獨(dú)立約束方程,即系數(shù)矩陣的秩最多為m+n-1.,5.2 運(yùn)輸單純形法 Transportation Simplex Method,設(shè)平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型為：,5.2 運(yùn)輸單純形法 Transportation Simplex Method,運(yùn)輸單純形法也稱(chēng)為表上作業(yè)法，是直接在運(yùn)價(jià)表上求最優(yōu)解的一種方法，它的步驟是：,第一步：求初始基本可行解（初始調(diào)運(yùn)方案）。 常用的方法有最小元素法、元素差額法（Vogel近似法）、左上角法。,第二步：求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解。常用求檢驗(yàn)的方法有閉回路法和位勢(shì)法，當(dāng)非基變量的檢驗(yàn)數(shù)ij全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)lk0，說(shuō)明還沒(méi)有達(dá)到最優(yōu)，轉(zhuǎn)第三步。,第三步：調(diào)整運(yùn)量，即換基。選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,5.2.1初始基可行解,1. 最小元素法 最小元素法的思想是就近優(yōu)先運(yùn)送，即最小運(yùn)價(jià)Cij對(duì)應(yīng)的變量xij優(yōu)先賦值 然后再在剩下的運(yùn)價(jià)中取最小運(yùn)價(jià)對(duì)應(yīng)的變量賦值并滿足約束，依次下去，直到最后得到一個(gè)初始基可行解。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,【例5-3】求表56所示的運(yùn)輸問(wèn)題的初始基可行解。,表56,5.2 運(yùn)輸單純形法 Transportation Simplex Method,表5759,【解】,30,10,10,60,5.2 運(yùn)輸單純形法 Transportation Simplex Method,20,10,到一組基可行解可用矩陣,表示，矩陣X 中空白處對(duì)應(yīng)的變量是非基變量，運(yùn)量等于零，這組解就是初始調(diào)運(yùn)方案總運(yùn)費(fèi) Z=360+810+520+130+210+910=500,【例5-4】求表5-10給出的運(yùn)輸問(wèn)題的初始基本可行解,表5-10,5.2 運(yùn)輸單純形法 Transportation Simplex Method,表5-11,【解】,5,10,0,15,10,10,5.2 運(yùn)輸單純形法 Transportation Simplex Method,初始基本可行解可用下列矩陣表示,5.2 運(yùn)輸單純形法 Transportation Simplex Method,2元素差額法（Vogel近似法）最小元素法只考慮了局部運(yùn)輸費(fèi)用最小。有時(shí)為了節(jié)省某一處的運(yùn)費(fèi)，而在其它處可能運(yùn)費(fèi)很大。元素差額法對(duì)最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷(xiāo)地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。例如下面兩種運(yùn)輸方案,前一種按最小元素法求得，總運(yùn)費(fèi)是 Z1=108+52+151=105 后一種方案考慮到C11與C21之間的差額是82=6，先調(diào)運(yùn)x21，再是x22，其次是x12這時(shí)總運(yùn)費(fèi) Z2=105+152+51=85Z1。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,基于以上思路，元素差額法求初始基本可行解的步驟是：,第一步：求出每行次小運(yùn)價(jià)與最小運(yùn)價(jià)之差，記為ui，i=1,2,m ；同時(shí)求出每列次小運(yùn)價(jià)與最小運(yùn)價(jià)之差，記為vj，j=1，2，n ；,第二步：找出所有行、列差額的最大值，即L=maxui，vi，差額L對(duì)應(yīng)行或列的最小運(yùn)價(jià)處優(yōu)先調(diào)運(yùn)；,第三步：這時(shí)必有一列或一行調(diào)運(yùn)完畢，在剩下的運(yùn)價(jià)中再求最大差額，進(jìn)行第二次調(diào)運(yùn)，依次進(jìn)行下去，直到最后全部調(diào)運(yùn)完畢，就得到一個(gè)初始調(diào)運(yùn)方案。,用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱(chēng)為近似方案。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,表5-6,【例5-5】用元素差額法求表56運(yùn)輸問(wèn)題的初始基本可行解。,【解】 求行差額 ui, i=1,2,3及列差額vj,j=1,2,3,4.計(jì)算公式為 ui= i行次小運(yùn)價(jià)i行最小運(yùn)價(jià) vj= j列次小運(yùn)價(jià)j例最小運(yùn)價(jià),5.2 運(yùn)輸單純形法 Transportation Simplex Method,表512,【 】,10,5.2 運(yùn)輸單純形法 Transportation Simplex Method,表5-13,10,5.2 運(yùn)輸單純形法 Transportation Simplex Method,【 】,5.2 運(yùn)輸單純形法 Transportation Simplex Method,表5-14,【 】,20,表5-15,【 】,60,30,10,5.2 運(yùn)輸單純形法 Transportation Simplex Method,基本可行解為,總運(yùn)費(fèi)Z=360+810530+120+210+210=470 比最小元素法的總運(yùn)費(fèi)（500）要小30,5.2 運(yùn)輸單純形法 Transportation Simplex Method,3. 左上角法。左上角法(亦稱(chēng)西北角法)是優(yōu)先從運(yùn)價(jià)表的左上角的變量賦值，當(dāng)行或列分配完畢后，再在表中余下部分的左上角賦值，依次類(lèi)推，直到右下角元素分配完畢當(dāng)出現(xiàn)同時(shí)分配完一行和一列時(shí)，仍然應(yīng)在打“”的位置上選一個(gè)變量作基變量，以保證最后的基變量數(shù)等于m+n1,【例5-6】用左上角法求例5-3中表5-6的初始基本可行解,表5-16,10,60,0,10,20,5.2 運(yùn)輸單純形法 Transportation Simplex Method,40,基本可行解為,用左上角法求得的基本可行解對(duì)應(yīng)的目標(biāo)函數(shù)值（總運(yùn)費(fèi)）是 Z91036080540110+220=520,求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗(yàn)數(shù)來(lái)判斷，記xij的檢驗(yàn)數(shù)為ij由第一章知，求最小值的運(yùn)輸問(wèn)題的最優(yōu)判別準(zhǔn)則是：,所有非基變量的檢驗(yàn)數(shù)都非負(fù)，則運(yùn)輸方案最優(yōu)（即為最優(yōu)解）。,求檢驗(yàn)數(shù)的方法有兩種，閉回路法和位勢(shì)法。,1閉回路法求檢驗(yàn)數(shù) 求某一非基變量的檢驗(yàn)數(shù)的方法是：在單位運(yùn)價(jià)表中，以該非基變量為起點(diǎn)，以基變量為其它頂點(diǎn)，找一條閉回路，由起點(diǎn)開(kāi)始，分別在頂點(diǎn)上交替標(biāo)上代數(shù)符號(hào)+、-、+、-、，以這些符號(hào)分別乘以相應(yīng)的運(yùn)價(jià)，其代數(shù)和就是這個(gè)非基變量的檢驗(yàn)數(shù)。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,5.2.2求檢驗(yàn)數(shù),【解】用最小元素法 求得的初始基可行解,【例5-7】用閉回路法求例53表59的檢驗(yàn)數(shù)。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,30,10,10,60,20,10,矩陣中打“”的位置是非基變量，其余是基變量，這里只求非基變量的檢驗(yàn)數(shù)。,求11，先找出x11的閉回路 ，對(duì)應(yīng)的運(yùn)價(jià)為 再用正負(fù)號(hào)分別交替乘以運(yùn)價(jià)有 直接求代數(shù)和得,5.2 運(yùn)輸單純形法 Transportation Simplex Method,5.2 運(yùn)輸單純形法 Transportation Simplex Method,同理可求出其它非基變量的檢驗(yàn)數(shù)：,這里340，說(shuō)明這組基本可行解不是最優(yōu)解。,只要求得的基變量是正確的且數(shù)目為m+n1，則某個(gè)非基變量的閉回路存在且唯一，因而檢驗(yàn)數(shù)唯一。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,2位勢(shì)法求檢驗(yàn) 位勢(shì)法求檢驗(yàn)數(shù)是根據(jù)對(duì)偶理論推導(dǎo)出來(lái)的一種方法。,設(shè)平衡運(yùn)輸問(wèn)題為,設(shè)前m個(gè)約束對(duì)應(yīng)的對(duì)偶變量為ui,i=1,2,m，后n個(gè)約束對(duì)應(yīng)的對(duì)偶變量為vj,j=1,2,n則運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題是,5.2 運(yùn)輸單純形法 Transportation Simplex Method,加入松馳變量ij將約束化為等式,ui+vj+ij=cij,記原問(wèn)題基變量XB的下標(biāo)集合為I，由第二章對(duì)偶性質(zhì)知，原問(wèn)題xij的檢驗(yàn)數(shù)是對(duì)偶問(wèn)題的松弛變量ij，當(dāng)（i，j）I 時(shí)ij=0，因而有,解上面第一個(gè)方程，將ui、vj代入第二個(gè)方程求出ij,5.2 運(yùn)輸單純形法 Transportation Simplex Method,【例5-8】用位勢(shì)法求例5-3表59給出的初始基本可行解的檢驗(yàn)數(shù)。,【解】第一步求位勢(shì)u1、u2、u3及v1、v2、v3、v4。,10 60 40 30,令u1=0得到位勢(shì)的解為,5.2 運(yùn)輸單純形法 Transportation Simplex Method,再由公式 求出檢驗(yàn)數(shù)，其中Cij是非基變量對(duì)應(yīng)的運(yùn)價(jià)。,計(jì)算結(jié)果與例5-7結(jié)果相同。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,5.2.3調(diào)整運(yùn)量,前面講過(guò)，當(dāng)某個(gè)檢驗(yàn)數(shù)小于零時(shí)，基可行解不是最優(yōu)解，總運(yùn)費(fèi)還可以下降，這時(shí)需調(diào)整運(yùn)輸量，改進(jìn)原運(yùn)輸方案，使總運(yùn)費(fèi)減少，改進(jìn)運(yùn)輸方案的步驟是：,第一步：確定進(jìn)基變量,第二步：確定出基變量 在進(jìn)基變量xik的閉回路中，標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量，對(duì)應(yīng)的基變量為出基變量，并打上“”以示作為非基變量。,第三步：調(diào)整運(yùn)量 在進(jìn)基變量的閉回路中標(biāo)有正號(hào)的變量加上調(diào)整量，標(biāo)有負(fù)號(hào)的變量減去調(diào)整量，其余變量不變，得到一組新的基可行解，然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn)。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,因?yàn)橛幸粋€(gè)檢驗(yàn)數(shù)小于零，所以這組基本可行解不是最優(yōu)解。對(duì)應(yīng)的非基變量x34進(jìn)基.,x34的閉回路是,x33最小，x33是出基量，調(diào)整量=10,5.2 運(yùn)輸單純形法 Transportation Simplex Method,在x34的閉回路上x(chóng)34、x23分別加上10，x33、x24分別減去10，其余變量不變，調(diào)整后得到一組新的基可行解：,非基變量的檢驗(yàn)數(shù)：,11=5，14=0，21=6，22=6，32=9，33=3,所有檢驗(yàn)數(shù)ij 0因而得到最優(yōu)解,最小運(yùn)費(fèi),5.2 運(yùn)輸單純形法 Transportation Simplex Method,【例5-9】求下列運(yùn)輸問(wèn)題的最優(yōu)解,表5-19,5.2 運(yùn)輸單純形法 Transportation Simplex Method,【解】 用最小元素法求得初始基本可行解如表5-19,因?yàn)橛?個(gè)檢驗(yàn)數(shù)小于零，所以這組基本可行解不是最優(yōu)解。對(duì)應(yīng)的非基變量x11進(jìn)基.,對(duì)應(yīng)的非基變量x11進(jìn)基.,x11的閉回路是,x33最小，x33是出基量，調(diào)整量=15,5.2 運(yùn)輸單純形法 Transportation Simplex Method,在x11的閉回路上x(chóng)11、x32、x23分別加上15，x12、x33、x21分別減去15，并且在x33處打上記號(hào)“”作為基變量，其余變量不變，調(diào)整后得到一組新的基可行解：,非基變量的檢驗(yàn)數(shù)：,13=3，14=1，22=0，24=8，31=1，33=4,所有檢驗(yàn)數(shù)ij 0因而得到最優(yōu)解,最小運(yùn)費(fèi),5.2 運(yùn)輸單純形法 Transportation Simplex Method,【例5-10】有四項(xiàng)工作指派給甲、乙兩人完成，每人完成兩項(xiàng)工作兩人完成各項(xiàng)工作的時(shí)間（小時(shí)）見(jiàn)表5-18，怎樣安排工作使總時(shí)間最少,表5-18,【解】 設(shè)xij(i=1,2；j=1,2,3,4)為第i人完成第j項(xiàng)工作的狀態(tài),數(shù)學(xué)模型為,5.2 運(yùn)輸單純形法 Transportation Simplex Method,寫(xiě)出表5-18的平衡運(yùn)輸表5-19, 用運(yùn)輸單純形法求解得到最優(yōu)表5-20,表5-19,表5-20,最優(yōu)的工作分配是：甲完成工作C和D，乙完成工作A和B，總時(shí)間Z47（小時(shí)）,5.2 運(yùn)輸單純形法 Transportation Simplex Method,設(shè)數(shù)學(xué)模型為,5.2.4 最大值問(wèn)題,5.2 運(yùn)輸單純形法 Transportation Simplex Method,第一種方法：將極大化問(wèn)題轉(zhuǎn)化為極小化問(wèn)題。設(shè)極大化問(wèn)題的運(yùn)價(jià)表為C=（Cij）mn，用一個(gè)較大的數(shù)M（MmaxCij）去減每一個(gè)Cij得到矩陣C=（Cij）mn ，其中C/ij=MCij0,將C/作為極小化問(wèn)題的運(yùn)價(jià)表，用表上用業(yè)法求出最優(yōu)解，目標(biāo)函數(shù)值為,例如，下列矩陣C是Ai（I=1，2，3）到Bj的單位貨物利潤(rùn),運(yùn)輸部門(mén)如何安排運(yùn)輸方案使總利潤(rùn)最大.,8 14 9,5.2 運(yùn)輸單純形法 Transportation Simplex Method,用最小元素法求初始方案得,11=8,12=4,21=2,23=2全部非負(fù),得到最優(yōu)運(yùn)輸方案X,最大利潤(rùn)Z=89+1010+68+54=240,第二種方法:所有非基變量的檢驗(yàn)數(shù)ij0時(shí)最優(yōu).求初始運(yùn)輸方案可采用最大元素法.如上例,用最大元素得到 的初始運(yùn)輸方案:,8 14 9,求檢驗(yàn)數(shù):11=8,12=4,21=2,23=2,全部非正,得到最優(yōu)解運(yùn)輸方案,結(jié)果與第一種方法相同.,5.2 運(yùn)輸單純形法 Transportation Simplex Method,當(dāng)總產(chǎn)量與總銷(xiāo)量不相等時(shí),稱(chēng)為不平衡運(yùn)輸問(wèn)題.這類(lèi)運(yùn)輸問(wèn)題在實(shí)際中常常碰到,它的求解方法是將不平衡問(wèn)題化為平衡問(wèn)題再按平衡問(wèn)題求解。,1.當(dāng)產(chǎn)大于銷(xiāo)時(shí),即,數(shù)學(xué)模型為,5.2.5 不平衡運(yùn)輸問(wèn)題,5.2 運(yùn)輸單純形法 Transportation Simplex Method,由于總產(chǎn)量大于總銷(xiāo)量，必有部分產(chǎn)地的產(chǎn)量不能全部 運(yùn)送完，必須就地庫(kù)存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉(cāng)庫(kù)，庫(kù)存量 為xi，n+1（i=1，2，m），總的庫(kù)存量為,5.2 運(yùn)輸單純形法 Transportation Simplex Method,bn+1作為一個(gè)虛設(shè)的銷(xiāo)地Bn+1的銷(xiāo)量。各產(chǎn)地Ai到Bn+1的運(yùn)價(jià)為零，即Ci，n+1=0,（i=1，m）。則平衡問(wèn)題的數(shù)學(xué)模型為：,具體求解時(shí),只在運(yùn)價(jià)表右端增加一列Bn+1，運(yùn)價(jià)為零,銷(xiāo)量為bn+1即可,5.2 運(yùn)輸單純形法 Transportation Simplex Method,2.當(dāng)銷(xiāo)大于產(chǎn)時(shí),即,數(shù)學(xué)模型為,5.2 運(yùn)輸單純形法 Transportation Simplex Method,由于總銷(xiāo)量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時(shí)虛設(shè)一個(gè)產(chǎn)地Am+1，產(chǎn)量為,xm+1,j 是Am+1運(yùn)到Bj的運(yùn)量，也是Bj不能滿足需要的數(shù)量。Am+1到Bj的運(yùn)價(jià)為零,即Cm+1,j=0(j=1,2, ,n),5.2 運(yùn)輸單純形法 Transportation Simplex Method,銷(xiāo)大于產(chǎn)平衡問(wèn)題的數(shù)學(xué)模型為 ：,具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)量為am+1即可。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,因?yàn)橛校?【例5-11】求下列表中極小化運(yùn)輸問(wèn)題的最優(yōu)解。,所以是一個(gè)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,表5-21,表中A2不可達(dá)B1，用一個(gè)很大的正數(shù)M表示運(yùn)價(jià)C21。虛設(shè)一個(gè)銷(xiāo)量為b5=180160=20的銷(xiāo)地B5，Ci5=0，i=1，2，3，4。表的右邊增添一列,這樣可得新的運(yùn)價(jià)表：,5.2 運(yùn)輸單純形法 Transportation Simplex Method,下表為計(jì)算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個(gè)單位沒(méi)有運(yùn)出。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,【例5-12】在例5-11中，假定B1的需要量是20到60之間，B2的需要量是50到70，試求極小化問(wèn)題的最優(yōu)解。,5.2.6 需求量不確定的運(yùn)輸問(wèn)題,5.2 運(yùn)輸單純形法 Transportation Simplex Method,先作如下分析： （1）總產(chǎn)量為180，B1，B4的最低需求量 20+50+35+45=150，這時(shí)屬產(chǎn)大于銷(xiāo)；,（2）B1，B4的最高需求是60+70+35+45=210，這時(shí)屬銷(xiāo)大于產(chǎn),（3）虛設(shè)一個(gè)產(chǎn)地A5，產(chǎn)量是210180=30，A5的產(chǎn)量只能供應(yīng)B1或B2。,（4）將B1與B2各分成兩部分 的需求量是20， 的需求量是40， 的需求量分別是50與20，因此 必須由A1，A4供應(yīng)， 可由 A1、A5供應(yīng)。,（5）上述A5不能供應(yīng)某需求地的運(yùn)價(jià)用大M表示，A5到 、 的運(yùn)價(jià)為零。得到下表的產(chǎn)銷(xiāo)平衡表。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,得到這樣的平衡表后，計(jì)算得到最優(yōu)方案表5-23。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,表5-22,表中：x131=0是基變量,說(shuō)明這組解是退化基本可行解,空格處的變量是非基變量。B1，B2，B3，B4實(shí)際收到產(chǎn)品數(shù)量分別是50，50，35和45個(gè)單位。,5.2 運(yùn)輸單純形法 Transportation Simplex Method,表5-23,5.2.7 中轉(zhuǎn)問(wèn)題,產(chǎn)地,銷(xiāo)地,3,5,4,2,3,1,6,8,2,3,2,9,圖5.2,A4,A5,2,2,7,15,中轉(zhuǎn)地,3,4,1,3,5.2 運(yùn)輸單純形法 Transportation Simplex Method,設(shè)xij為Ai到Aj的運(yùn)量，i，j=1，2，m+n+r則中轉(zhuǎn)運(yùn)輸問(wèn)題的數(shù)學(xué)模型為,產(chǎn)大于銷(xiāo)時(shí)將式(5-3a)改為“”約束，銷(xiāo)大于產(chǎn)時(shí)將式(5-3c)改為“”約束,5.2 運(yùn)輸單純形法 Transportation Simplex Method,5.4 指派問(wèn)題 assignment problem,5.4.1問(wèn)題的提出與數(shù)學(xué)模型 指派問(wèn)題也稱(chēng)分配問(wèn)題,是一種特殊的整數(shù)規(guī)劃問(wèn)題,是0-1整數(shù)線性規(guī)劃問(wèn)題.在生活中經(jīng)常會(huì)遇到這樣的問(wèn)題,某單位需要指派m個(gè)人去完成m項(xiàng)任務(wù),每個(gè)人只做一工作,同時(shí),每項(xiàng)工作只由一個(gè)人完成.由于各人的專(zhuān)長(zhǎng)不同,每個(gè)人完成各項(xiàng)任務(wù)的效率也不同.于是產(chǎn)生了應(yīng)指派哪一個(gè)人去完成哪一項(xiàng)任務(wù),使完成項(xiàng)任務(wù)的總效率最高(如所用的時(shí)間為最少)的問(wèn)題.這類(lèi)問(wèn)題為指派問(wèn)題或分配問(wèn)題.,5.4 指派問(wèn)題 assignment problem,【例5-15】人事部門(mén)欲安排四人到四個(gè)不同的崗位工作，每個(gè)崗位一個(gè)人經(jīng)考核四人在不同崗位的成績(jī)（百分制）如表5-28所示，如何安排他們的工作使總成績(jī)最好。類(lèi)似的有m項(xiàng)加工任務(wù)，怎樣指派到m臺(tái)機(jī)床上分別完成的問(wèn)題；m條航線，怎樣指定m艘船去航行的問(wèn)題等.,數(shù)學(xué)模型為：,甲,乙,丙,丁,A,B,C,D,圖5. 3,5.4 指派問(wèn)題 assignment