1、本章知識結(jié)構(gòu),第 3 章 運(yùn)輸和指派問題,本章教學(xué)目標(biāo)與要求,n 掌握產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型及其特點(diǎn)；,n 掌握運(yùn)輸問題的表上作業(yè)法，包括初始調(diào)運(yùn)方案的確定、檢驗(yàn)數(shù)的計(jì)算、運(yùn)輸方案的調(diào)整方法；,n 掌握產(chǎn)銷不平衡運(yùn)輸問題轉(zhuǎn)化為產(chǎn)銷平衡問題的處理辦法；掌握運(yùn)輸問題在實(shí)踐中的典型應(yīng)用；,n 掌握標(biāo)準(zhǔn)指派問題的求解方法，會(huì)將各種非標(biāo)準(zhǔn)指派問題轉(zhuǎn)化為標(biāo)準(zhǔn)指派問題。,導(dǎo)入案例,運(yùn)儲(chǔ)物流的運(yùn)輸問題 運(yùn)輸成本占物流總成本的35-50左右，占商品價(jià)格的4-10，運(yùn)輸對物流總成本的節(jié)約具有舉足輕重的作用。運(yùn)儲(chǔ)物流在物流運(yùn)輸管理中要著重考慮：運(yùn)輸方式的選擇，運(yùn)輸路線的選擇，編制運(yùn)輸計(jì)劃等問題。 運(yùn)輸方式合適與

2、否決定了運(yùn)輸時(shí)間的長短，決定了成本的高低，各種運(yùn)輸工具都有其使用的優(yōu)勢領(lǐng)域，對運(yùn)輸工具進(jìn)行優(yōu)化選擇，按運(yùn)輸工具特點(diǎn)進(jìn)行裝卸運(yùn)輸作業(yè)，最大限度地發(fā)揮所用運(yùn)輸工具的作用；選擇運(yùn)輸路線要與交通運(yùn)輸工具結(jié)合起來，盡量安排直達(dá)運(yùn)輸，以減少運(yùn)輸裝卸、轉(zhuǎn)運(yùn)環(huán)節(jié)，縮短運(yùn)輸時(shí)間；編制運(yùn)輸計(jì)劃還要從全局出發(fā)，深入調(diào)查研究，綜合平衡，積極組織計(jì)劃運(yùn)輸、合理運(yùn)輸、直達(dá)運(yùn)輸、均衡運(yùn)輸，按照成本最低的原則來制定合理的計(jì)劃 。,3.1 運(yùn)輸問題概述,運(yùn)輸問題的典型提法是將某種物質(zhì)從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，已知每個(gè)產(chǎn)地的產(chǎn)量和每個(gè)銷地的銷量，如何在許多可行調(diào)運(yùn)方案中選擇一個(gè)總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。根據(jù)總產(chǎn)量與總銷量是否相等

3、的數(shù)量關(guān)系，運(yùn)輸問題通常可劃分為產(chǎn)銷平衡（相等）和產(chǎn)銷不平衡（不相等）兩大類別。產(chǎn)銷平衡的運(yùn)輸問題主要在這一節(jié)介紹，產(chǎn)銷不平衡的運(yùn)輸問題將在后面節(jié)中討論。,3.1.1 運(yùn)輸問題的引入,在生產(chǎn)、交換活動(dòng)中，不可避免地要進(jìn)行物資調(diào)運(yùn)工作。某時(shí)期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食、礦砂、木材等各類物資，分別運(yùn)送到需要這些物資的地區(qū)。,3.1 運(yùn)輸問題概述,【例3.1】某物流公司從兩個(gè)產(chǎn)地A1 (內(nèi)蒙) 、A2 (山西)將煤炭運(yùn)往三個(gè)銷地B1 (北京) 、B2 (山東) 、B3 (上海) ，各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地運(yùn)往各銷地的每單位煤炭運(yùn)費(fèi)數(shù)據(jù)見下表，問：應(yīng)如何調(diào)運(yùn)煤炭可使總運(yùn)輸費(fèi)用最小？,解：

4、此為產(chǎn)銷平衡的運(yùn)輸問題（總產(chǎn)量 = 總銷量）。,設(shè)xij為從產(chǎn)地Ai (i=1,2)運(yùn)往銷地Bj (j=1,2,3)的運(yùn)輸量,x11,x12,x13,x21,x22,x23,則該問題的數(shù)學(xué)模型為,3.1 運(yùn)輸問題概述,該問題顯然是一個(gè)線性規(guī)劃模型，其系數(shù)矩陣A見下表,3.1 運(yùn)輸問題概述,可以看出運(yùn)輸問題的系數(shù)矩陣有如下特征：,（1）共有3+2行，分別表示各產(chǎn)地和銷地；32列，分別表示各決策變量的系數(shù)列；,（2）每列只有兩個(gè)1，其余為0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用，由xij的行列下標(biāo)所決定，這是運(yùn)輸問題表上作業(yè)法的由來。,3.1 運(yùn)輸問題概述,3.1.2 運(yùn)輸問題的數(shù)學(xué)模型,一般地，

5、產(chǎn)銷平衡的運(yùn)輸問題可以表述為：設(shè)有m個(gè)地點(diǎn)（稱為產(chǎn)地或發(fā)地）A1 , A2 , Am的某種物資調(diào)至n個(gè)地點(diǎn)B1 , B2 , Bn （稱為銷地或收地），各個(gè)產(chǎn)地需要調(diào)出的物資量分別為a1 , a2 , am單位，各個(gè)銷地需要調(diào)進(jìn)的物資量分別為b1 , b2 , bn單位，且各個(gè)發(fā)點(diǎn)的供應(yīng)量之和等于各個(gè)收點(diǎn)的需求量之和。已知每個(gè)發(fā)點(diǎn)Ai到每個(gè)收點(diǎn)Bj的物資單位調(diào)運(yùn)價(jià)格為cij ?，F(xiàn)問如何安排調(diào)運(yùn)，才能使總運(yùn)費(fèi)最小。,3.1 運(yùn)輸問題概述,設(shè)xij表示從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)量，,x11,x12,x1n,x21,x22,x2n,xm1,xm2,xmn,于是產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型為：,3.1

6、運(yùn)輸問題概述,C=,XT=,A=,=b,平衡運(yùn)輸問題模型寫成矩陣形式為:,3.1 運(yùn)輸問題概述,在實(shí)際問題建立運(yùn)輸問題模型時(shí)，還會(huì)出現(xiàn)如下一些變化：,1）有時(shí)問題表面看不是運(yùn)輸問題，但其仍要求費(fèi)用最低或要求目標(biāo)函數(shù)（利潤或營業(yè)額）最大化，仍可看成運(yùn)輸問題；,2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，模型中可直接加入（等式或不等式）約束。,3.1.3 運(yùn)輸問題的數(shù)學(xué)模型的特征,運(yùn)輸問題是一類線性規(guī)劃問題，其目標(biāo)函數(shù)一般為求總運(yùn)費(fèi)的極小值。根據(jù)線性規(guī)劃的有關(guān)理論，如果它的最優(yōu)解存在，一定可以在基可行解中找到，因而需先考察運(yùn)輸問題約束方程組系數(shù)矩陣的秩r(A) .,定理3.1 平衡運(yùn)輸問題模型的系數(shù)矩陣的

7、秩r(A)=m+n-1 。,運(yùn)輸問題是特殊的線性規(guī)劃，單純形法仍適合于運(yùn)輸問題。為此還要了解運(yùn)輸問題基可行解的性質(zhì)，為說明其基本可行解的特征，引入閉回路的概念。,3.1 運(yùn)輸問題概述,定義3.1 在平衡運(yùn)輸問題的決策變量表中，凡是能夠排列成下列形式的 xab , xad , xcd , xce , , xst , xsb 或 xab , xcb , xcd , xed , , xst , xat 其中，a,d,s各不相同； b,c,t 各不相同，稱這些變量的集合為一閉回路，并將上式中的決策變量稱為該閉回路的頂點(diǎn)。,例如x13, x16, x36, x34, x24, x23； x23, x53

8、, x55, x45, x41, x21等都是閉回路，這些決策變量就是閉回路的頂點(diǎn)。,3.1 運(yùn)輸問題概述,根據(jù)閉回路可以看出其的一些明顯特點(diǎn)，閉回路是一個(gè)具有如下條件頂點(diǎn)格子的集合：,1）每一個(gè)頂點(diǎn)格子都是轉(zhuǎn)角點(diǎn)；,2）每一行（或列）若有閉回路的頂點(diǎn)，則必有兩個(gè)頂點(diǎn)；,3）每兩個(gè)頂點(diǎn)格子的連線都是水平的或垂直的；,4）閉回路中頂點(diǎn)的個(gè)數(shù)必為偶數(shù)。,定理3.2 對于產(chǎn)銷平衡運(yùn)輸問題的閉回路來說，具有下面結(jié)論： 1）該問題m+n-1個(gè)變量構(gòu)成基變量的充要條件是這些變量不包含任何閉回路； 2）給定一組基變量，那么從決策變量表中可找出唯一一個(gè)從任意非基變量出發(fā)，經(jīng)過基變量為頂點(diǎn)，又回到該非基變量的閉

9、回路。,事實(shí)上，閉回路是一個(gè)簡化的局部調(diào)運(yùn)方案，反映了全局調(diào)運(yùn)方案是否最優(yōu)。定理3.2給出了運(yùn)輸問題基本解的重要性質(zhì)，為尋求運(yùn)輸問題的基本可行解提供了依據(jù)。與一般的線性規(guī)劃問題有所不同，產(chǎn)銷平衡的運(yùn)輸問題總是存在可行解，且目標(biāo)函數(shù)值有界，故運(yùn)輸問題必有最優(yōu)解。,3.2 運(yùn)輸問題的表上作業(yè)法,運(yùn)輸問題作為一類特殊的線性規(guī)劃問題，在求解時(shí)仍可采用單純形法的計(jì)算步驟，但因?yàn)檫\(yùn)輸決策變量有兩個(gè)下標(biāo)，可以在單位運(yùn)價(jià)表和產(chǎn)銷平衡表中進(jìn)行基變量與非基變量的換基迭代，再加上運(yùn)輸問題模型系數(shù)矩陣的特征，早期的研究者們提出了專門針對運(yùn)輸問題的單純形法表上作業(yè)法。,表上作業(yè)法的主要步驟：,第一步 求一個(gè)初始基可行解

10、，即確定初始調(diào)運(yùn)方案。,第二步 計(jì)算檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解。若是則迭代停止；否則轉(zhuǎn)下一步；,第三步 換基迭代(即調(diào)整運(yùn)量)。選一個(gè)變量出基，對原運(yùn)輸方案進(jìn)行調(diào)整得到新的調(diào)運(yùn)方案，改進(jìn)當(dāng)前方案，返回第二步，直至求出最優(yōu)解為止。,給出初始運(yùn)輸方案,改進(jìn)運(yùn)輸方案,yes,no,3.2 運(yùn)輸問題的表上作業(yè)法,3.2.1 初始基可行解的確定,確定初始可行解常用的方法有西北角法、最小元素法和差值（Vogel近似）法。, 西北角法,從產(chǎn)銷平衡表的西北角（左上角）第一格開始，按集中供應(yīng)的原則，依次安排調(diào)運(yùn)量，即分析對應(yīng)產(chǎn)地和銷地的供需數(shù)量關(guān)系，盡最大可能滿足需求，若某行（列）的產(chǎn)量（銷量）已滿足，則把該行

11、（列）的其他格劃去；接著從未被劃線的運(yùn)價(jià)中再找出西北角的方格，重復(fù)上述操作，如此進(jìn)行下去，直至得到一個(gè)基本可行解。,【例3.2】 設(shè)某種產(chǎn)品有三個(gè)生產(chǎn)廠商A1、A2、A3，聯(lián)合供應(yīng)四個(gè)銷地B1、B2、B3、 B4 ，其供應(yīng)量、需要量和單位產(chǎn)品的運(yùn)輸成本見下表，試求一調(diào)運(yùn)方案。,3.2 運(yùn)輸問題的表上作業(yè)法,西北角法確定出的初始調(diào)運(yùn)方案為：,由A1B1運(yùn)3;A1B2運(yùn)4;A2B2運(yùn)2;A2B3運(yùn)2;A3B3運(yùn)3;A3B4運(yùn)6，方案的運(yùn)輸總費(fèi)用為, 最小元素法,3.2 運(yùn)輸問題的表上作業(yè)法,最小元素法是按照“最低運(yùn)輸成本優(yōu)先集中供應(yīng)”的原則，即運(yùn)價(jià)最小的需求優(yōu)先滿足，即從單位運(yùn)價(jià)中最小的運(yùn)價(jià)開始確

12、定供需關(guān)系，然后依次找單位運(yùn)價(jià)的次小值，一直到給出初始基本可行解為止。最小元素法的基本思想是就近供應(yīng)，每一次都要求找出單位運(yùn)價(jià)表中最小的元素，在運(yùn)量表內(nèi)對應(yīng)的方格填入允許取得的最大數(shù)，若某行（列）的供應(yīng)量（需求量）已滿足，則把運(yùn)價(jià)表中該運(yùn)價(jià)所在行（列）劃去；再找出未劃去的單位運(yùn)價(jià)中的最小數(shù)值，一直進(jìn)行下去，直至得到一個(gè)基可行解。,【例3.3】 求下表所給運(yùn)輸問題的初始調(diào)運(yùn)方案。,由A1B3運(yùn)7;A2B1運(yùn)3;A2B4運(yùn)6;A3B2運(yùn)5;A3B4運(yùn)2，方案的運(yùn)輸總費(fèi)用為,3.2 運(yùn)輸問題的表上作業(yè)法,最小元素法確定出的初始調(diào)運(yùn)方案為：,3.2 運(yùn)輸問題的表上作業(yè)法,【例3.4】 用最小元素法求例

13、3.2運(yùn)輸問題的初始調(diào)運(yùn)方案。,由A1B3運(yùn)4;A1B4運(yùn)3; A2B1運(yùn)3;A2B3運(yùn)1;A3B2運(yùn)6;A3B4運(yùn)3，方案的運(yùn)輸總費(fèi)用為,最小元素法確定出的初始調(diào)運(yùn)方案為：,3.2 運(yùn)輸問題的表上作業(yè)法, 差值法（Vogel法）,差值法又稱為伏格爾法。最小元素法只考慮了局部的運(yùn)輸費(fèi)用最小，有時(shí)為了節(jié)省某一處運(yùn)費(fèi)，可能會(huì)導(dǎo)致其他處運(yùn)費(fèi)很大，缺乏對整個(gè)供需關(guān)系的考慮。差額法考慮產(chǎn)地和銷地最小和次小運(yùn)價(jià)的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，不然就會(huì)增加總的費(fèi)用。最小元素法只考慮了局部的運(yùn)輸費(fèi)用最小，有時(shí)為了節(jié)省某一處運(yùn)費(fèi)，可能會(huì)導(dǎo)致其他處運(yùn)費(fèi)很大，缺乏對整個(gè)供需關(guān)系的考慮。差額法考慮產(chǎn)地和銷地

14、最小和次小運(yùn)價(jià)的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，不然就會(huì)增加總的費(fèi)用。,差值法的步驟如下：,1）算出單位運(yùn)價(jià)表各行各列中次小元素和最小元素的差額；,2）在差額最大的行或列中的最小元素處填上盡可能大的調(diào)運(yùn)數(shù)（若幾個(gè)差額同為最大，則可任取其一）；,3）這時(shí)必有一列或一行調(diào)運(yùn)完畢，在剩下的運(yùn)價(jià)表中再求最大差額，進(jìn)行第二次調(diào)運(yùn)，直至最后調(diào)運(yùn)完畢，就得到一個(gè)初始調(diào)運(yùn)方案。,3.2 運(yùn)輸問題的表上作業(yè)法,【例3.5】用差值法求例3.2的初始調(diào)運(yùn)方案。,2,5,1,3,0,1,1,5,3,2,7,6,7,2,2,10,8,10,3.2 運(yùn)輸問題的表上作業(yè)法,【例3.5】用差值法求例3.2的初始調(diào)運(yùn)方

15、案。,由A1B3運(yùn)5;A1B4運(yùn)2; A2B1運(yùn)3;A2B4運(yùn)1;A3B2運(yùn)6;A3B4運(yùn)3，方案的運(yùn)輸總費(fèi)用為,差值法確定出的初始調(diào)運(yùn)方案為：,3.2 運(yùn)輸問題的表上作業(yè)法,3.2.2 檢驗(yàn)數(shù)的計(jì)算,表上作業(yè)法計(jì)算檢驗(yàn)數(shù)的方法有兩種：一種是閉回路法，另一種是位勢法。, 閉回路法,根據(jù)單純形法原理，要判斷某個(gè)可行解是否為最優(yōu)解，需要計(jì)算非基變量的檢驗(yàn)數(shù)。用閉回路法求檢驗(yàn)數(shù)時(shí)，對于給定的調(diào)運(yùn)方案（基可行解），從非基變量xij出發(fā)作一條閉回路，并從xij開始將該閉回路上的頂點(diǎn)順序編號（順時(shí)針或逆時(shí)針均可），起點(diǎn)xij為零，依此類推。稱編號為奇數(shù)的點(diǎn)為奇點(diǎn)，編號為偶數(shù)的點(diǎn)為偶點(diǎn)，則對應(yīng)xij的檢驗(yàn)數(shù)

16、ij等于該閉回路上偶點(diǎn)處單位運(yùn)價(jià)的總和與奇點(diǎn)處單位運(yùn)價(jià)的總和之差，即,ij =偶點(diǎn)處單位運(yùn)價(jià)的總和奇點(diǎn)處單位運(yùn)價(jià)的總和,【例3.6】 求例3.4給出的可行解所對應(yīng)的非基變量檢驗(yàn)數(shù)。,3.2 運(yùn)輸問題的表上作業(yè)法,0,1,2,3,3.2 運(yùn)輸問題的表上作業(yè)法,0,1,2,3,3.2 運(yùn)輸問題的表上作業(yè)法,0,1,2,3,4,5,3.2 運(yùn)輸問題的表上作業(yè)法,0,1,2,3,3.2 運(yùn)輸問題的表上作業(yè)法,1,2,3,4,5,0,3.2 運(yùn)輸問題的表上作業(yè)法,1,2,3,0,3.2 運(yùn)輸問題的表上作業(yè)法,注：如果全部檢驗(yàn)數(shù)均為正數(shù)或零，則調(diào)運(yùn)方案一定為最優(yōu)方案；如果檢驗(yàn)數(shù)中仍存在負(fù)數(shù)，則調(diào)運(yùn)方案不是

17、最優(yōu)方案。, 位勢法,3.2 運(yùn)輸問題的表上作業(yè)法,位勢法的步驟為：,1）在產(chǎn)銷平衡表中，即調(diào)運(yùn)方案中增加ui行和vj列，但在相應(yīng)的基變量格（即數(shù)字格中）不是填寫調(diào)運(yùn)量，而是填寫相應(yīng)的運(yùn)價(jià)，寫在格的左上角；,2）令u1=0或vn=0，根據(jù)式cij-(ui+vj)=0(其中xij為基變量)依一定次序計(jì)算和，將結(jié)果填寫在表中；,3）將非基變量的運(yùn)價(jià)填入相應(yīng)格的左上角，根據(jù)式ij=cij-(ui+vj)(其中xij為非基變量) 計(jì)算相應(yīng)的檢驗(yàn)數(shù)，將結(jié)果填入相應(yīng)格，寫在該格的右下角。,【例3.7】 應(yīng)用位勢法求例3.4給出的初始可行解所對應(yīng)的非基變量的檢驗(yàn)數(shù)。,3.2 運(yùn)輸問題的表上作業(yè)法,3.2 運(yùn)

18、輸問題的表上作業(yè)法,3.2 運(yùn)輸問題的表上作業(yè)法,3.2 運(yùn)輸問題的表上作業(yè)法,3.2 運(yùn)輸問題的表上作業(yè)法,3.2 運(yùn)輸問題的表上作業(yè)法,3.2 運(yùn)輸問題的表上作業(yè)法,3.2 運(yùn)輸問題的表上作業(yè)法,注：閉回路法的主要缺點(diǎn)是當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都會(huì)產(chǎn)生困難。當(dāng)運(yùn)輸問題的產(chǎn)地與銷地很多時(shí)，空格的數(shù)目很多，用閉回路法計(jì)算檢驗(yàn)數(shù)，要找很多的閉回路，計(jì)算量很大，而用位勢法就簡便得多。,3.2 運(yùn)輸問題的表上作業(yè)法,3.2.3 閉回路的調(diào)整,當(dāng)初始基本可行解非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)數(shù)時(shí)，便需換基迭代。具體步驟如下：,1）若有兩個(gè)和兩個(gè)以上的負(fù)檢驗(yàn)數(shù)時(shí)，一般選擇其中最小的負(fù)檢驗(yàn)數(shù)，以它

19、對應(yīng)的空格為調(diào)入格，以此格為出發(fā)點(diǎn)，作一閉回路，并從該空格出發(fā)，沿閉回路，將各頂點(diǎn)依次編號，空格編號為0。,2）取奇點(diǎn)所在格中最小的運(yùn)量(記為)，然后在閉回路中偶點(diǎn)增加 、奇點(diǎn)減少 ，得出新的調(diào)整方案。,說明：重新計(jì)算空格的檢驗(yàn)數(shù)。如果所有的檢驗(yàn)數(shù)都為正數(shù)或零，那么求出的就是最優(yōu)解，不然，重復(fù)上述過程。,【練習(xí)】 應(yīng)用閉回路調(diào)整例3.4給出的初始可行解，并計(jì)算所對應(yīng)的新的可行解非基變量的檢驗(yàn)數(shù)。,3.2 運(yùn)輸問題的表上作業(yè)法,0,1,2,3,3.2 運(yùn)輸問題的表上作業(yè)法,3.2 運(yùn)輸問題的表上作業(yè)法,3.3 其他形式的運(yùn)輸問題,產(chǎn)銷平衡運(yùn)輸問題相當(dāng)于線性規(guī)劃的標(biāo)準(zhǔn)型，實(shí)際問題中經(jīng)常還會(huì)遇到一些

20、其他的運(yùn)輸問題，解決的主要方法是將這些問題都轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問題。,3.3.1 產(chǎn)銷不平衡的運(yùn)輸問題,產(chǎn)銷不平衡的運(yùn)輸問題分兩類：一是供大于求的運(yùn)輸問題；一是供不應(yīng)求的運(yùn)輸問題。, 供大于求的運(yùn)輸問題,供大于求的運(yùn)輸問題，即在aibj的情況下，求cij xij（總費(fèi)用最少），就得供大于求的運(yùn)輸問題模型,3.3 其他形式的運(yùn)輸問題,3.3 其他形式的運(yùn)輸問題,事實(shí)上，上面模型就是m個(gè)產(chǎn)地和n+1個(gè)銷地的產(chǎn)銷平衡運(yùn)輸問題，相當(dāng)于增加了一個(gè)“虛擬”銷地Bn+1，由于這個(gè)銷地并不存在，每個(gè)產(chǎn)地的剩余物資只能留在原產(chǎn)地，因此Ai產(chǎn)地運(yùn)到Bn+1的單位運(yùn)價(jià)為cin+1=0，而這個(gè)銷地的銷量是bn+1

21、。因而供大于求運(yùn)輸問題的求解思路是添加一個(gè)虛擬銷地，轉(zhuǎn)化為平衡運(yùn)輸問題來處理。,3.3 其他形式的運(yùn)輸問題, 供不應(yīng)求的運(yùn)輸問題,供不應(yīng)求的運(yùn)輸問題，即在aibj的情況下，求cij xij（總費(fèi)用最少），就得供大于求的運(yùn)輸問題模型,3.3 其他形式的運(yùn)輸問題,事實(shí)上，上面模型就是m+1個(gè)產(chǎn)地和n個(gè)銷地的產(chǎn)銷平衡運(yùn)輸問題，相當(dāng)于增加了一個(gè)“虛擬”產(chǎn)地Am+1，其相應(yīng)的產(chǎn)量是am+1 。由于這個(gè)產(chǎn)地并不存在，因此Am+1產(chǎn)地運(yùn)到Bj的單位運(yùn)價(jià)為cm+1j=0。因而供不應(yīng)求運(yùn)輸問題的求解思路是添加一個(gè)虛擬產(chǎn)地，轉(zhuǎn)化為平衡運(yùn)輸問題來處理。,【例3.8】 某公司在不同地區(qū)有A1、A2和A3三個(gè)工廠，產(chǎn)品

22、將運(yùn)往B1、B2 、B3和B4四個(gè)地區(qū)，其單位運(yùn)價(jià)表見下表，試建立產(chǎn)銷平衡的運(yùn)輸問題的數(shù)學(xué)模型。,3.3 其他形式的運(yùn)輸問題,解： 這是一個(gè)供大于求的物資調(diào)運(yùn)問題，故增加一個(gè)虛擬的銷地B5，需求量為b5=280-220=60，令ci5=0(i=1,2,3)，該供需平衡運(yùn)輸問題的數(shù)學(xué)模型為：,3.3 其他形式的運(yùn)輸問題,實(shí)際上，上述模型相應(yīng)的產(chǎn)銷平衡運(yùn)輸表如下表所示，,該問題的最優(yōu)調(diào)運(yùn)方案為：,3.3 其他形式的運(yùn)輸問題,3.3.2 禁運(yùn)與封鎖的運(yùn)輸問題,在實(shí)際的物資運(yùn)輸管理中常遇到以下情況，某種物資不能從產(chǎn)地Ai運(yùn)往銷地Bj ，或者銷地Bj不接收從產(chǎn)地Ai調(diào)入的物資，稱前者為Ai對Bj的禁運(yùn)，

23、后者為Bj對Ai的封鎖。造成禁運(yùn)或封鎖的因素很多，例如Ai與Bj之間沒有運(yùn)輸線，或者由于自然災(zāi)害造成了原有交通運(yùn)輸線的中斷，這樣就形成了Ai對Bj的禁運(yùn)；如果物資需通過鐵路，航運(yùn)運(yùn)輸，由于運(yùn)輸能力有限，有關(guān)部門暫時(shí)禁止這批物資通過他們所管轄的路段，也人為地造成了Ai對Bj的禁運(yùn)；由于某經(jīng)濟(jì)原因，如質(zhì)量問題或合同約束，銷地Bj拒絕接收產(chǎn)地Ai的物資，從而形成Bj對Ai的封鎖。,禁運(yùn)和封鎖給物資運(yùn)輸管理工作帶來的后果是在制定物資調(diào)運(yùn)方案時(shí)，必須使物資從Ai到Bj的調(diào)運(yùn)量為零。也就是說，在數(shù)學(xué)模型中要增加約束條件xij=0 ，去掉這個(gè)約束條件使模型轉(zhuǎn)化為運(yùn)輸問題的方法是：將Ai到Bj的運(yùn)價(jià)cij修改

24、為一個(gè)充分大的正數(shù)M，從而使得任意一個(gè)含有xij0的調(diào)運(yùn)方案均不可能成為最優(yōu)方案，這樣在得到了相應(yīng)的運(yùn)輸問題的最優(yōu)調(diào)運(yùn)方案時(shí)，約束條件xij=0自動(dòng)地得到了滿足，與線性規(guī)劃的大M法相對應(yīng)。,【例3.9】 供需雙方在協(xié)商后簽訂了一個(gè)供貨合同，合同規(guī)定供給方向六個(gè)地區(qū)（記為B1,B2, B6 ）提供某種物資并負(fù)責(zé)物資的運(yùn)輸，同時(shí)規(guī)定B2和B4的物資只能由產(chǎn)地A1或A2調(diào)入，各地的供給量、需求量和單位運(yùn)價(jià)由下表給出，試求滿足合同要求的最優(yōu)調(diào)運(yùn)方案。,3.3 其他形式的運(yùn)輸問題,解 合同要求B2和B4的物資只能由A1或A2供給，形成了B2和B4對A3的封鎖。將c32和c34改為M，見下表，,3.3 其

25、他形式的運(yùn)輸問題,應(yīng)用表上作業(yè)法求解該運(yùn)輸問題，得到最優(yōu)調(diào)運(yùn)方案如下：,3.3 其他形式的運(yùn)輸問題,3.3.3 運(yùn)力限制的運(yùn)輸問題,在制定物資調(diào)運(yùn)方案時(shí)，管理人員應(yīng)該考慮物資所經(jīng)路段的運(yùn)輸能力。設(shè)Ai到Bj的路段的運(yùn)輸能力為dij，如果Ai的供應(yīng)量和Bj的需求量都大于dij ，則從Ai到Bj的物資調(diào)運(yùn)量至多為dij 。也就是說，在物資調(diào)運(yùn)時(shí)Ai到Bj的路段存在著運(yùn)輸能力的限制，此時(shí)相應(yīng)的數(shù)學(xué)模型中應(yīng)增加運(yùn)輸能力約束，即有xijdij 。為將這種類型的問題轉(zhuǎn)化為運(yùn)輸問題模型，可將Bj想象為兩個(gè)銷地Bj和Bj，規(guī)定Bj的需求量為dij ，從而使得Ai到Bj（實(shí)際上為Ai到Bj）路段不再有運(yùn)輸能力的

26、限制，同時(shí)規(guī)定Bj的需求量為bj-dij ，且Bj對Ai封鎖，這樣就不會(huì)有多于dij的物資經(jīng)過Ai到Bj的路段。,【例3.10】 某運(yùn)輸公司可承擔(dān)某種物資的運(yùn)輸任務(wù)，有關(guān)數(shù)據(jù)由下表給出，其中cij 表示單位物資從Ai到Bj的運(yùn)價(jià)。有關(guān)部門在A1到B3，A2到B1 ， A2到B4三個(gè)路段給出該公司的物資通過限量分別為15，15和10。應(yīng)如何指定物資調(diào)運(yùn)方案，才能使運(yùn)輸?shù)目偝杀咀钚　?3.3 其他形式的運(yùn)輸問題,解： 由于A2的供應(yīng)量和B1的需求量都大于該路段的限制量，上述問題在A2到B1路段具有運(yùn)輸能力限制。為建立該問題的運(yùn)輸問題模型，將B1視為二個(gè)銷地B1和B1，需求量分別為15和30，且B1

27、對A2封鎖。同樣處理另外二個(gè)有運(yùn)輸能力限制的路段，A1到B3和 A2到B4，具體的處理結(jié)果見下表：,3.3 其他形式的運(yùn)輸問題,應(yīng)用表上作業(yè)法求解，得調(diào)運(yùn)方案如下：,3.3 其他形式的運(yùn)輸問題,將Bj和Bj合并為Bj (j=1,3,4)，就得到可操作的調(diào)運(yùn)方案，見下表,3.3 其他形式的運(yùn)輸問題,3.3.4 轉(zhuǎn)運(yùn)運(yùn)輸問題,在運(yùn)輸管理中，經(jīng)常要處理物資中轉(zhuǎn)的運(yùn)輸問題，例如物資從產(chǎn)地運(yùn)到銷地必須使用不同的運(yùn)輸工具，這樣就需要首先將物資從產(chǎn)地運(yùn)到某地（稱為中轉(zhuǎn)站），更換運(yùn)輸工具后再運(yùn)往銷地。又如，由于運(yùn)輸能力的限制或價(jià)格因素（轉(zhuǎn)運(yùn)運(yùn)價(jià)小于直接運(yùn)價(jià)），需要將不同產(chǎn)地的物資首先集中到某個(gè)中轉(zhuǎn)站，再由中轉(zhuǎn)

28、站發(fā)往銷地。需要中轉(zhuǎn)站的運(yùn)輸稱為轉(zhuǎn)運(yùn)運(yùn)輸。,這里討論一次轉(zhuǎn)運(yùn)問題，一般提法是：設(shè)有r個(gè)中轉(zhuǎn)站T1,Tr，物資的運(yùn)輸過程是先從產(chǎn)地Ai運(yùn)到某個(gè)中轉(zhuǎn)站Tk ，再運(yùn)往銷地Bj 。已知Ai到Tk的運(yùn)價(jià)為cik ，Tk到Bj的運(yùn)價(jià)為ckj，Ai的供給量為ai，通過Tk的最大運(yùn)輸能力為dk ，Bj的需求量為bj。不妨設(shè)ai=bj , aidk,也就是說，供需是平衡的且所有的物資經(jīng)轉(zhuǎn)運(yùn)后都能送達(dá)銷地?，F(xiàn)在要求一轉(zhuǎn)運(yùn)方案，使得運(yùn)輸?shù)目傎M(fèi)用最小。,3.3 其他形式的運(yùn)輸問題,設(shè)決策變量： xik：從Ai到Tk的調(diào)運(yùn)量(i=1,2,m; k=1,2,r)， xik：從Tk到Bj的調(diào)運(yùn)量( k=1,2,r; j=1

29、,2,n ), 則相應(yīng)的數(shù)學(xué)模型為：,供給約束,運(yùn)輸能力約束,中轉(zhuǎn)站平衡,需求約束,3.3 其他形式的運(yùn)輸問題,根據(jù)轉(zhuǎn)運(yùn)問題模型的結(jié)構(gòu)可以看出，轉(zhuǎn)運(yùn)問題也可轉(zhuǎn)化為運(yùn)輸問題模型求解，其方法是將每個(gè)中轉(zhuǎn)站Tk既看成產(chǎn)地也看成銷地，從而形成一個(gè)有m+r個(gè)產(chǎn)地，有r+n個(gè)銷地的運(yùn)輸問題。由于物資不能由Ai直接到達(dá)Bj，故Bj對Ai封鎖。同樣，不同的中轉(zhuǎn)站之間也互相封鎖。Tk的供給量和需求量均為dk ，從而總供給量為 , ai+dk，總需求量為bj +dk ，以實(shí)現(xiàn)供需平衡。,【例3.11】 將某種物資從A1、 A2和A3運(yùn)往B1、 B2、 B3、 B4和B5五個(gè)銷地，物資必須經(jīng)過T1 、 T2、 T3

30、和T4中的任意一個(gè)中轉(zhuǎn)站轉(zhuǎn)運(yùn)，有關(guān)數(shù)據(jù)由下表給出。試求解該轉(zhuǎn)運(yùn)問題。,3.3 其他形式的運(yùn)輸問題,該轉(zhuǎn)運(yùn)問題可轉(zhuǎn)化為具體7個(gè)產(chǎn)地和9個(gè)銷地的運(yùn)輸問題，有關(guān)數(shù)據(jù)見下表：,3.3 其他形式的運(yùn)輸問題,應(yīng)用表上作業(yè)法可得最優(yōu)調(diào)運(yùn)方案，見下表：,3.3 其他形式的運(yùn)輸問題,實(shí)際運(yùn)輸過程中物資可能需要多次中轉(zhuǎn)，這種類型的轉(zhuǎn)運(yùn)問題比較復(fù)雜，但將它轉(zhuǎn)化為運(yùn)輸問題模型時(shí)，與一次轉(zhuǎn)運(yùn)問題的處理思路一樣，依照禁運(yùn)與封鎖原則，即當(dāng)物資不能從一個(gè)產(chǎn)地或中轉(zhuǎn)站直接到達(dá)另一個(gè)中轉(zhuǎn)站或銷地時(shí)，就應(yīng)當(dāng)對這兩地實(shí)行禁運(yùn)與封鎖。,在現(xiàn)實(shí)生活中，有各種性質(zhì)的指派問題。例如，有若干項(xiàng)工作需要分配給若干人（或部門）來完成；有若干項(xiàng)合同

31、需要選擇若干個(gè)投標(biāo)者來承包；有若干班級需要安排在若干教室上課等等。諸如此類的問題，它們的基本要求是在滿足特定的指派要求條件下，使指派方案的總體效果最佳。,【例3.12】 某廠擬派4個(gè)維修小組去維修4臺(tái)機(jī)車，他們相應(yīng)的完成工作所需時(shí)間cij(i,j=1,2,3,4)由右表給出。如何給每個(gè)小組安排工作才能使完成任務(wù)的總時(shí)間最少。,3.4 指派問題,指派問題也稱分配或配置問題，是資源合理配置或最優(yōu)匹配問題。指派問題通常劃分為標(biāo)準(zhǔn)和非標(biāo)準(zhǔn)的指派問題。,3.4.1 指派問題的引入,解： 該指派問題是安排維修小組去維修機(jī)車，其決策變量為,3.4 指派問題,該問題的數(shù)學(xué)模型為：,任務(wù)約束,人員約束,3.4

32、指派問題,【例3.13】 某商業(yè)公司計(jì)劃開辦五家新商店。為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知建筑公司Ai (i=1,2,3,4,5)對新商店Bj (j=1,2,3,4,5)的建造費(fèi)用的報(bào)價(jià)（萬元）為cij ，見下表。商業(yè)公司應(yīng)當(dāng)對5家建筑公司怎樣分派建筑任務(wù)，才能使總的建筑費(fèi)用最少？,解： 該指派問題是安排建筑公司承建商店，其決策變量為,3.4 指派問題,該問題的數(shù)學(xué)模型為：,顯然指派問題與運(yùn)輸問題相類似，該問題的指派平衡表如下：,3.4 指派問題,3.4 指派問題,3.4.2 標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型,一般地，指派問題的一般提法是：有n項(xiàng)任務(wù)，需分配給n個(gè)人員（或設(shè)備）去

33、完成，已知每個(gè)人員完成某項(xiàng)工作的效率（或成本等）為cij，如何給每個(gè)人員指派一項(xiàng)工作，使得完成任務(wù)的總效率最高（或總成本最少），見下表。,解：,3.4 指派問題,稱矩陣C為效率矩陣（在其他問題中，可根據(jù)實(shí)際意義稱為費(fèi)用矩陣等），其元素cij體現(xiàn)了第i個(gè)人完成第j項(xiàng)工作時(shí)的效率，即,決策變量xij排成的nn矩陣X稱為決策變量矩陣,其中,3.4 指派問題,分析：指派問題解的特征是它有n個(gè)1，其它都是0，且這n個(gè)1位于決策變量矩陣的不同行、不同列，每一種情況為指派問題的一個(gè)可行解，共n!個(gè)解。指派問題是：把這n個(gè)1放到的n 2個(gè)位置的什么地方可使耗費(fèi)的總資源最少？（解最優(yōu)）,【例3.14】 對于效率

34、矩陣,決策變量矩陣,都是指派問題的最優(yōu)解。,3.4 指派問題,3.4.3 指派問題的求解,指派問題既是一類特殊的整數(shù)規(guī)劃問題，又是特殊的運(yùn)輸問題，因此可以用多種相應(yīng)的解法來求解，然而這些解法都沒有充分利用指派問題的特殊性質(zhì)，有效地減少計(jì)算量，直到1955年庫恩（W. W. Kuhn）提出的匈牙利法才有效地解決了指派問題。, 匈牙利法的理論基礎(chǔ),定義3.2 獨(dú)立零元素組 在效率矩陣中，有一組在不同行不同列的零元素，稱為獨(dú)立零元素組，其每個(gè)元素稱為獨(dú)立零元素。,【例3.15】 已知效率矩陣,求其獨(dú)立零元素組。,3.4 指派問題,解： 可行解c12=0， c24 =0， c31 =0， c43 =0

35、是一個(gè)獨(dú)立零元素組，,c12=0， c24 =0， c31 =0， c43 =0分別稱為獨(dú)立零元素；,c12=0， c23 =0， c31 =0， c44 =0也是一個(gè)獨(dú)立零元素組，而c14=0， c23 =0， c31 =0， c44 =0就不是獨(dú)立零元素組.,根據(jù)上述對效率矩陣中零元素的分析，將效率矩陣中出現(xiàn)的獨(dú)立零元素組中零元素所處的位置，在決策變量矩陣中令相應(yīng)的xij =1，其余的xij =0，就可找到指派問題的一個(gè)最優(yōu)解,如例3.14。,問題：在有的問題中效率矩陣中獨(dú)立零元素的個(gè)數(shù)不夠n個(gè)，這樣就無法求出最優(yōu)指派方案，需作進(jìn)一步的分析，首先給出下述定理。,3.4 指派問題,定理3.3

36、 設(shè)指派問題的效率矩陣為C=cijnn，若將該矩陣的某一行（或某一列）的各個(gè)元素都減去同一常數(shù)k（ k可正可負(fù)），得到新的效率矩陣C=cijnn ，則以C為效率矩陣的新的指派問題與原指派問題的最優(yōu)解相同。,推論 若將指派問題的效率矩陣每一行或每一列分別減去各行或各列的最小元素，則得到新指派問題與原指派問題有相同的最優(yōu)解。,定理3.4 效率矩陣中獨(dú)立零元素的最多個(gè)數(shù)等于能覆蓋所有零元素的最少直線數(shù)。,3.4 指派問題, 匈牙利法求解步驟,第一步：變換效率矩陣，將各行各列都減去當(dāng)前各行、各列中最小元素。,第二步：標(biāo)記新矩陣的獨(dú)立零元素。,1）行檢驗(yàn) 對變換后的效率矩陣進(jìn)行逐行檢驗(yàn)，若某行只有一個(gè)未

37、標(biāo)記的零元素時(shí)，用“*”將該零元素做標(biāo)記，然后將被標(biāo)記的零元素所在的列的其它未標(biāo)記的零元素用“”將該零元素標(biāo)記。,2）列檢驗(yàn) 與行檢驗(yàn)過程類似，對進(jìn)行了行檢驗(yàn)的矩陣逐列進(jìn)行檢驗(yàn)，對每列只有一個(gè)未被標(biāo)記的零元素，用“*”將該零元素做一標(biāo)記，然后將該元素所在行的其他未被標(biāo)記的零元素打“”將該零元素標(biāo)記。重復(fù)上述列檢驗(yàn)，直到每一列都沒有未被標(biāo)記的零元素或有兩個(gè)未被標(biāo)記的零元素為止。,這時(shí)可能出現(xiàn)以下三種情況： 每一行均有標(biāo)記“*”出現(xiàn)，“*”的個(gè)數(shù)m恰好等于n； 存在未標(biāo)記的零元素，但他們所在的行和列中，未標(biāo)記過的零元素均至少有兩個(gè)； 不存在未被標(biāo)記過的零元素，“*”的個(gè)數(shù)mn。,3.4 指派問題,

38、3）試指派 若情況出現(xiàn)，則可進(jìn)行試指派：令“*”記號的決策變量取值為1，其他決策變量取值均為零，得到一個(gè)最優(yōu)指派方案，停止計(jì)算。,若情況出現(xiàn)，則對每行、每列的其它未被標(biāo)記的零元素任選一個(gè)，加上標(biāo)記“*”，即給該零元素標(biāo)記“*”，然后給同行、同列的其它未被標(biāo)記的零元素加標(biāo)記“”，然后再進(jìn)行行、列檢驗(yàn)，可能出現(xiàn)情況或，出現(xiàn)情況就會(huì)得到最優(yōu)指派，停止計(jì)算。,若情況出現(xiàn)，則要轉(zhuǎn)入下一步。,第三步：作最少直線覆蓋當(dāng)前所有零元素。,3.4 指派問題,1）對新矩陣中所有不含“*”元素的行打 ；,2）對打的行中，所有零元素所在的列打；,3）對所有打列中標(biāo)記“*”元素所在行打；,4）重復(fù)上述2），3）步，直到不

39、能進(jìn)一步打?yàn)橹梗?5）對未打的每一行劃一直線，對已打的每一列劃一縱線，即得到覆蓋當(dāng)前0元素的最少直線數(shù)。,第四步：對矩陣未被直線覆蓋過的元素中找最小元素，將打行的各元素減去這個(gè)最小元素，將打列的各元素加上這個(gè)最小元素（以避免打行中出現(xiàn)負(fù)元素），這樣就增加了零元素的個(gè)數(shù)，返回第二步。,【例3.16】 求解例3.12和例3.13,3.4 指派問題,解：,故可得到指派問題的最優(yōu)解X，這樣安排能使總的維修時(shí)間最少，維修時(shí)間為z=44911=28（小時(shí)）。,故可得到指派問題的最優(yōu)解X，這樣安排能使總的建造費(fèi)用最少，建造費(fèi)用為z=79666=34（萬元）。,3.4 指派問題,3.4 指派問題,3.4.4

40、非標(biāo)準(zhǔn)指派問題,在實(shí)際應(yīng)用中，常會(huì)遇到非標(biāo)準(zhǔn)形式，如求最大值，人數(shù)與工作數(shù)不相等以及不可接受的配置（某人不可完成某項(xiàng)任務(wù)）等特殊指派問題。解決的思路是先化成標(biāo)準(zhǔn)形式，然后再用匈牙利法求解，即對效率矩陣通過適當(dāng)變換使得滿足匈牙利算法的條件再求解。, 最大化的指派問題,最大化指派問題的一般形式為,解決辦法：設(shè)最大化的指派問題的系數(shù)矩陣為C=cijnn ，M=maxc11,c12,cnn，令B=bijnn = M-cijnn ，則以B為效率矩陣的最小化指派問題和以C為效率矩陣的原最大化指派問題有相同的最優(yōu)解。,3.4 指派問題,【例3.17】 某工廠有4名工人A1, A2, A3, A4,分別操作4

41、臺(tái)車床B1, B2, B3,B4,每小時(shí)單產(chǎn)量如右表，求產(chǎn)值最大的分配方案。,解： 令,M=max10,9,6=10, 人數(shù)和事數(shù)不等的指派問題,3.4 指派問題,B中有4個(gè)獨(dú)立零元素，所以,為最優(yōu)解，最大產(chǎn)值為z=10615=22。,若人數(shù)小于事數(shù)，添一些虛擬的“人”，此時(shí)這些虛擬的“人”做各件事的費(fèi)用系數(shù)取為0，理解為這些費(fèi)用實(shí)際上不會(huì)發(fā)生；若人數(shù)大于事數(shù)，添一些虛擬的“事”，此時(shí)這些虛擬的“事”被各個(gè)人做的費(fèi)用系數(shù)同樣也取為0。,【例3.18】 現(xiàn)有4個(gè)人，5件工作，每人做每件工作所耗時(shí)間如下表：,3.4 指派問題,問指派哪個(gè)人去完成哪項(xiàng)工作，可使總耗時(shí)最小？,解：添加虛擬人A5，構(gòu)造耗

42、時(shí)矩陣C，,應(yīng)用匈牙利法求解，得到最優(yōu)解X，,最少耗時(shí)為z=2767=22。, 一個(gè)人可做幾件事的指派問題,3.4 指派問題,若某人可作幾件事，則可將該人化作相同的幾個(gè)“人”來接受指派。這幾個(gè)“人”做同一件事的費(fèi)用系數(shù)當(dāng)然一樣。,【例3.19】 對例3.13中的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司A4和A5，讓技術(shù)力量較強(qiáng)的建筑公司A1, A2, A3來承建5家商店，其投標(biāo)費(fèi)用見右表。根據(jù)實(shí)際情況，允許每家建筑公司承建一家或兩家商店，求使總費(fèi)用最少的指派方案。,解：由于每家建筑公司最多可承建兩家新商店，因此，把每家建筑公司化作Ai和Ai (i=1,2,3)相同的兩家建筑公司因而

43、費(fèi)用矩陣變?yōu)椋?3.4 指派問題,上面的系數(shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同，引入一件虛擬“事”，使之成為標(biāo)準(zhǔn)的指派問題，其效率矩陣為C ,應(yīng)用匈牙利法求解，得最優(yōu)解X，,總費(fèi)用為z=74978=35（萬元）。, 某事不能由某人去做的指派問題,3.4 指派問題,某事不能由某人去做，可將此人做此事的費(fèi)用取作足夠大的M。,【例3.20】分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)的時(shí)間見下表。由于任務(wù)重，人數(shù)少，考慮：任務(wù)E必須完成，其它4項(xiàng)任務(wù)可選3項(xiàng)完成，但甲不能做A項(xiàng)工作，試確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。,解：這是一人數(shù)與工作不等的指派問題，由于任務(wù)數(shù)大于人數(shù)，所以需要有一個(gè)虛擬的“人”，設(shè)為戊。因?yàn)榧撞荒茏鯝，所以令甲完成工作A的時(shí)間為M；又因?yàn)楣ぷ鱁必須完成，故設(shè)戊完