《運(yùn)籌學(xué)（第3版）》 課件 第3章 運(yùn)輸問題和指派問題

實(shí)用運(yùn)籌學(xué)

－－運(yùn)用Excel建模和求解（第3版）第3章運(yùn)輸問題和指派問題TheTransportationandAssignmentProblems本章內(nèi)容要點(diǎn)運(yùn)輸問題的基本概念運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題的變形轉(zhuǎn)運(yùn)問題指派問題的基本概念指派問題的變形本章主要內(nèi)容框架圖3.1運(yùn)輸問題的基本概念運(yùn)輸問題源于在日常生活中人們把某些物品或人們自身從一些地方轉(zhuǎn)移到另一些地方，要求所采用的運(yùn)輸路線或運(yùn)輸方案是最經(jīng)濟(jì)或成本最小的，這就成為一個(gè)運(yùn)籌學(xué)問題。隨著經(jīng)濟(jì)水平的不斷提升，現(xiàn)代物流業(yè)蓬勃發(fā)展，如何充分利用時(shí)間、信息、倉(cāng)儲(chǔ)、配送和聯(lián)運(yùn)體系創(chuàng)造更多的價(jià)值，向運(yùn)籌學(xué)提出了更高的挑戰(zhàn)。這要求科學(xué)地組織貨源、運(yùn)輸和配送，使運(yùn)輸問題變得日益復(fù)雜，但其基本思想仍然是實(shí)現(xiàn)現(xiàn)有資源的最優(yōu)化配置。3.1運(yùn)輸問題的基本概念一般的運(yùn)輸問題就是解決如何把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地的問題，在每個(gè)產(chǎn)地的供應(yīng)量和每個(gè)銷地的需求量以及各地之間的運(yùn)輸單價(jià)已知的前提下，確定一個(gè)使得總運(yùn)輸成本最小的方案。平衡運(yùn)輸問題的條件如下：（1）明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應(yīng)量（產(chǎn)量）、需求量（銷量）和單位運(yùn)輸成本。（2）需求假設(shè)：每一個(gè)出發(fā)地（產(chǎn)地）都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地（銷地）。與之類似，每一個(gè)目的地（銷地）都有一個(gè)固定的需求量，所有的需求量都必須由出發(fā)地（產(chǎn)地）滿足。即“總供應(yīng)量＝總需求量”。（3）成本假設(shè)：從任何一個(gè)出發(fā)地（產(chǎn)地）到任何一個(gè)目的地（銷地）的貨物運(yùn)輸成本與所運(yùn)送的貨物數(shù)量呈線性關(guān)系，因此，貨物運(yùn)輸成本就等于單位運(yùn)輸成本乘以所運(yùn)送的貨物數(shù)量（目標(biāo)函數(shù)是線性的）。3.2運(yùn)輸問題的數(shù)學(xué)模型產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型設(shè)從產(chǎn)地Ai運(yùn)往銷地Bj的物資數(shù)量為xij（i=1,2,?,m;j=1,2,?,n)

3.2.1產(chǎn)銷平衡的運(yùn)輸問題例3-1

某公司有三個(gè)加工廠（A1、A2和A3）生產(chǎn)某種產(chǎn)品，每日的產(chǎn)量分別為7噸、4噸、9噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)（B1、B2、B3和B4），四個(gè)銷售點(diǎn)每日的銷量分別為3噸、6噸、5噸、6噸。從三個(gè)加工廠（產(chǎn)地）到四個(gè)銷售點(diǎn)（銷地）的單位產(chǎn)品運(yùn)價(jià)如表3-2所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，才能在滿足四個(gè)銷售點(diǎn)的銷量的前提下，使總運(yùn)費(fèi)最??？銷售點(diǎn)B1銷售點(diǎn)B2銷售點(diǎn)B3銷售點(diǎn)B4加工廠A1311310加工廠A21928加工廠A3741053.2.1產(chǎn)銷平衡的運(yùn)輸問題【解】首先，三個(gè)加工廠A1、A2、A3的總產(chǎn)量為7＋4＋9＝20（噸）；四個(gè)銷售點(diǎn)B1、B2、B3、B4的總銷量為3＋6＋5＋6＝20（噸）。也就是說，總產(chǎn)量等于總銷量，故該運(yùn)輸問題是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。（1）決策變量

設(shè)xij為從加工廠Ai（i＝1,2,3）運(yùn)往銷售點(diǎn)Bj（j=1,2,3,4）的運(yùn)輸量。（2）目標(biāo)函數(shù)

本問題的目標(biāo)是使公司的總運(yùn)費(fèi)最小。3.2.1產(chǎn)銷平衡的運(yùn)輸問題（3）約束條件①三個(gè)加工廠的產(chǎn)品全部都要運(yùn)送出去（產(chǎn)量約束）②四個(gè)銷售點(diǎn)的產(chǎn)品全部都要得到滿足（銷量約束）③非負(fù)3.2.1產(chǎn)銷平衡的運(yùn)輸問題運(yùn)輸問題是一種特殊的線性規(guī)劃問題，一般采用“表上作業(yè)法”求解，但Excel的“規(guī)劃求解”功能還是采用“單純形法”來求解。例3-1的電子表格模型（1）設(shè)置條件格式的操作請(qǐng)參見本章附錄。（2）將單元格的字體和背景顏色設(shè)置為相同顏色以實(shí)現(xiàn)“渾然一體”的效果，可以起到隱藏單元格內(nèi)容的作用。當(dāng)單元格被選中時(shí)，編輯欄中仍然會(huì)顯示單元格的真實(shí)數(shù)據(jù)。（3）本章所有例題的最優(yōu)解（運(yùn)輸方案或指派方案）有一個(gè)共同特點(diǎn)，即“0”值較多，所以都使用了Excel的“條件格式”功能。3.2.1產(chǎn)銷平衡的運(yùn)輸問題例3-1的最優(yōu)調(diào)運(yùn)方案網(wǎng)絡(luò)圖A2A3A1B2B3B1B47365649231635產(chǎn)量

加工廠

運(yùn)輸量

銷售點(diǎn)

銷量運(yùn)輸問題的整數(shù)解性質(zhì)需要注意的是：運(yùn)輸問題有這樣一個(gè)性質(zhì)（整數(shù)解性質(zhì)），即只要它的產(chǎn)量（供應(yīng)量）和銷量（需求量）都是整數(shù)，任何存在可行解的運(yùn)輸問題就必然存在所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有決策變量都是整數(shù)的約束條件。由于運(yùn)輸量經(jīng)常以卡車、集裝箱等為單位，如果卡車不能裝滿，就很不經(jīng)濟(jì)了。整數(shù)解性質(zhì)避免了運(yùn)輸量（運(yùn)輸方案）為小數(shù)的麻煩。3.2.2產(chǎn)銷不平衡的運(yùn)輸問題實(shí)際問題中，產(chǎn)銷往往是不平衡的。（1）銷大于產(chǎn)（供不應(yīng)求）運(yùn)輸問題的數(shù)學(xué)模型（以滿足小的產(chǎn)量為準(zhǔn)）3.2.2產(chǎn)銷不平衡的運(yùn)輸問題（2）產(chǎn)大于銷（供過于求）運(yùn)輸問題的數(shù)學(xué)模型（以滿足小的銷量為準(zhǔn)）3.2.2產(chǎn)銷不平衡的運(yùn)輸問題例3-2自來水輸送問題。某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來水由A、B、C三個(gè)水庫(kù)供應(yīng)。四個(gè)居民區(qū)每天的基本生活用水量分別為3萬(wàn)噸、7萬(wàn)噸、1萬(wàn)噸、1萬(wàn)噸，但由于水源緊張，三個(gè)水庫(kù)每天最多只能分別供應(yīng)5萬(wàn)噸、6萬(wàn)噸、5萬(wàn)噸自來水。由于地理位置的差別，自來水公司從各水庫(kù)向各居民區(qū)供水所需支付的引水管理費(fèi)不同（見表3?4，其中水庫(kù)C與丁區(qū)之間沒有輸水管道），其他管理費(fèi)用都是4500元／萬(wàn)噸。根據(jù)公司規(guī)定，各居民區(qū)用戶按照統(tǒng)一標(biāo)準(zhǔn)9000元／萬(wàn)噸收費(fèi)。此外，四個(gè)居民區(qū)都向公司申請(qǐng)了額外用水量，分別為每天5萬(wàn)噸、7萬(wàn)噸、2萬(wàn)噸、4萬(wàn)噸。問：（1）該公司應(yīng)如何分配供水量，才能獲利最大？（2）為了增加供水量，自來水公司正在考慮進(jìn)行水庫(kù)改造，使三個(gè)水庫(kù)每天的最大供水量都增加一倍，那時(shí)供水方案應(yīng)如何改變？公司利潤(rùn)可增加到多少？3.2.2產(chǎn)銷不平衡的運(yùn)輸問題【解】可以把“自來水輸送問題”看作“運(yùn)輸問題”，也就是用“運(yùn)輸問題”的方法求解“自來水輸送問題”。設(shè)xij為水庫(kù)i向居民區(qū)j的日供水量（11個(gè)變量）

3.2.2產(chǎn)銷不平衡的運(yùn)輸問題例3-2問題（1）的線性規(guī)劃模型目標(biāo)：從獲利最大轉(zhuǎn)化為引水管理費(fèi)最小由于A、B、C三個(gè)水庫(kù)的總供水量5＋6＋5＝16，超過四個(gè)居民區(qū)的基本生活用水量之和3＋7＋1＋1＝12（供過于求），但又少于四個(gè)居民區(qū)的基本生活用水量與額外用水量之和（3＋7＋1＋1）＋（5＋7＋2＋4）＝30（供不應(yīng)求），所以本問題既是“供過于求”又是“供不應(yīng)求”的不平衡運(yùn)輸問題。

3.2.2產(chǎn)銷不平衡的運(yùn)輸問題例3-2問題（1）的電子表格模型電子表格模型中有12個(gè)變量（供水量，C9:F11區(qū)域），通過增加約束條件“$F$11＝0”，實(shí)現(xiàn)“水庫(kù)C與居民區(qū)丁之間沒有輸水管道”。3.2.2產(chǎn)銷不平衡的運(yùn)輸問題例3-2問題（1）的最優(yōu)供水方案網(wǎng)絡(luò)圖BCA乙丙甲丁5814356551541水庫(kù)供水量居民區(qū)最大供水量最大用水量3.2.2產(chǎn)銷不平衡的運(yùn)輸問題例3-2問題（2）方法1的線性規(guī)劃模型目標(biāo)：將獲利最大轉(zhuǎn)化為引水管理費(fèi)最小由于A、B、C三個(gè)水庫(kù)每天的最大供水量都提高一倍，則公司總供水能力增加到16×2＝32萬(wàn)噸，大于總需求量30萬(wàn)噸，為“供過于求”的不平衡運(yùn)輸問題。

3.2.2產(chǎn)銷不平衡的運(yùn)輸問題例3-2問題（2）方法1

的電子表格模型電子表格模型中有12個(gè)變量（供水量，C9:F11區(qū)域），通過增加約束條件“$F$11＝0”，實(shí)現(xiàn)“水庫(kù)C與居民區(qū)丁之間沒有輸水管道”。3.2.2產(chǎn)銷不平衡的運(yùn)輸問題例3-2問題（2）的最優(yōu)供水方案網(wǎng)絡(luò)圖BCA乙丙甲丁10814351210105353水庫(kù)供水量居民區(qū)最大供水量最大用水量43.2.2產(chǎn)銷不平衡的運(yùn)輸問題例3-2問題（2）方法2：目標(biāo)為獲利最大電子表格模型中有12個(gè)變量（供水量，C9:F11區(qū)域），通過增加約束條件“$F$11＝0”，實(shí)現(xiàn)“水庫(kù)C與居民區(qū)丁之間沒有輸水管道”。

3.3運(yùn)輸問題的變形現(xiàn)實(shí)生活中符合產(chǎn)銷平衡運(yùn)輸問題的每個(gè)條件的情況很少。一個(gè)特征近似但其他一個(gè)或者幾個(gè)特征不符合產(chǎn)銷平衡運(yùn)輸問題條件的運(yùn)輸問題卻經(jīng)常出現(xiàn)。下面是要討論的一些特征：特征1：總供應(yīng)量大于總需求量。每個(gè)供應(yīng)量（產(chǎn)量）代表了從其出發(fā)地（產(chǎn)地）運(yùn)送出去的最大數(shù)量（而不是一個(gè)固定的數(shù)值，≤）特征2：總供應(yīng)量小于總需求量。每個(gè)需求量（銷量）代表了在其目的地（銷地）接收到的最大數(shù)量（而不是一個(gè)固定的數(shù)值，≤）特征3：一個(gè)目的地（銷地）同時(shí)存在最小需求量和最大需求量，于是所有在這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的（需求量可在一定范圍內(nèi)變化，≥、≤）特征4：在運(yùn)輸中不能利用特定的出發(fā)地（產(chǎn)地）--目的地（銷地）組合（xij=0）特征5：目標(biāo)是使與運(yùn)輸量有關(guān)的總利潤(rùn)最大而不是使總成本最?。∕in－>

Max）3.3運(yùn)輸問題的變形例3-3

某公司決定使用三個(gè)有生產(chǎn)余力的工廠進(jìn)行四種產(chǎn)品的生產(chǎn)。生產(chǎn)每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任意種產(chǎn)品的數(shù)量來衡量（見表3-7的最右列）。而每種產(chǎn)品每天有一定的需求量（見表3-7的最后一行）。除了工廠2不能生產(chǎn)產(chǎn)品3以外，每個(gè)工廠都可以生產(chǎn)這些產(chǎn)品。然而，每種產(chǎn)品在不同工廠中的單位成本（元）是有差異的（如表3-7所示）?，F(xiàn)在需要決定的是在哪個(gè)工廠生產(chǎn)哪種產(chǎn)品，可使總成本最小。單位成本生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠24029一2375工廠33730272145需求量203030403.3運(yùn)輸問題的變形【解】把“指定工廠生產(chǎn)產(chǎn)品問題”看作“運(yùn)輸問題”。本問題中，工廠2不能生產(chǎn)產(chǎn)品3，這樣可以增加約束條件x23＝0

；并且總供應(yīng)量（75+75+45=195）>總需求量（20+30+30+40=120），是供大于求的運(yùn)輸問題。其數(shù)學(xué)模型：設(shè)xij為工廠i生產(chǎn)產(chǎn)品j

的數(shù)量3.3運(yùn)輸問題的變形例3-3的電子表格模型產(chǎn)品4分在2個(gè)工廠（工廠2和工廠3）生產(chǎn)3.3運(yùn)輸問題的變形例3-4

需求量存在最小需求量和最大需求量（需求量可在一定范圍內(nèi)變化）的問題。某公司在三個(gè)工廠中專門生產(chǎn)一種產(chǎn)品。在未來的四個(gè)月中，四個(gè)處于國(guó)內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能有大量訂購(gòu)該產(chǎn)品。顧客1是公司最重要的顧客，所以他的訂單要全部滿足；顧客2和顧客3也是公司很重要的顧客，所以營(yíng)銷經(jīng)理認(rèn)為至少要滿足他們訂單的1/3；對(duì)于顧客4，營(yíng)銷經(jīng)理認(rèn)為并不需要特殊考慮。由于運(yùn)輸成本的差異，單位利潤(rùn)也不同，利潤(rùn)很大程度上取決于哪個(gè)工廠供應(yīng)哪個(gè)顧客（見表3-8）。問應(yīng)向每個(gè)顧客供應(yīng)多少產(chǎn)品，才能使公司的總利潤(rùn)最大？單位利潤(rùn)（元）產(chǎn)量（件）顧客1顧客2顧客3顧客4工廠1554246538000工廠2371832485000工廠3295951357000最少供應(yīng)量（件）7000300020000要求訂購(gòu)量（件）70009000600080003.3運(yùn)輸問題的變形【解】該問題要求滿足不同顧客的需求（訂購(gòu)量），解決辦法：實(shí)際供應(yīng)量

最少供應(yīng)量實(shí)際供應(yīng)量

要求訂購(gòu)量

目標(biāo)是總利潤(rùn)最大，而不是總成本最小。其數(shù)學(xué)模型：設(shè)xij為工廠i供應(yīng)顧客j的產(chǎn)品數(shù)量3.3運(yùn)輸問題的變形例3-4的電子表格模型3.4轉(zhuǎn)運(yùn)問題在實(shí)際工作中，有一類問題是需要先將物品由產(chǎn)地運(yùn)到某個(gè)中間轉(zhuǎn)運(yùn)地，這個(gè)轉(zhuǎn)運(yùn)地可以是產(chǎn)地、銷地或中間轉(zhuǎn)運(yùn)倉(cāng)庫(kù)，然后再運(yùn)到銷售目的地，這類問題稱為轉(zhuǎn)運(yùn)問題，可以通過建模轉(zhuǎn)化為運(yùn)輸問題模型。例3-5

例3-1是一個(gè)普通的產(chǎn)銷平衡運(yùn)輸問題，如果假定：（1）每個(gè)加工廠（產(chǎn)地）的產(chǎn)品不一定直接運(yùn)到銷售點(diǎn)（銷地），可以將其中幾個(gè)加工廠的產(chǎn)品集中一起運(yùn)；（2）運(yùn)往各銷售點(diǎn)的產(chǎn)品可以先運(yùn)給其中幾個(gè)銷售點(diǎn)，再轉(zhuǎn)運(yùn)給其他銷售點(diǎn)；（3）除產(chǎn)地、銷地之外，中間還可以有幾個(gè)轉(zhuǎn)運(yùn)站，在產(chǎn)地之間、銷地之間或產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。3.4轉(zhuǎn)運(yùn)問題例3-5轉(zhuǎn)運(yùn)問題（續(xù)）已知各產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站及相互之間的單位產(chǎn)品運(yùn)價(jià)如表3-9所示，問在考慮產(chǎn)銷地之間非直接運(yùn)輸?shù)那闆r下，如何將三個(gè)加工廠生產(chǎn)的產(chǎn)品運(yùn)往銷售點(diǎn)，才能使總運(yùn)費(fèi)最??？單位運(yùn)價(jià)加工廠（產(chǎn)地）中間轉(zhuǎn)運(yùn)站銷售點(diǎn)（銷地）A1A2A3T1T2T3T4B1B2B3B4加工廠（產(chǎn)地）A1

132143311310A21

一35一21928A33一

1一2374105中間轉(zhuǎn)運(yùn)站T1231

1322846T215一1

114527T34一231

21824T4323212

1一26銷售點(diǎn)（銷地）B13172411

142B21194858一1

21B33210422242

3B410856746213

3.4轉(zhuǎn)運(yùn)問題【解】現(xiàn)在把該轉(zhuǎn)運(yùn)問題轉(zhuǎn)化成一般運(yùn)輸問題，要做如下處理：（1）由于問題中的所有加工廠、中間轉(zhuǎn)運(yùn)站、銷售點(diǎn)都可以看作產(chǎn)地，也可以看作銷地，因此把整個(gè)問題當(dāng)作有11個(gè)產(chǎn)地和11個(gè)銷地的擴(kuò)大的運(yùn)輸問題。（2）對(duì)擴(kuò)大的運(yùn)輸問題建立單位運(yùn)價(jià)表。方法是將不可能的運(yùn)輸方案的運(yùn)價(jià)用任意大的正數(shù)（相對(duì)極大值）M代替，其余運(yùn)價(jià)cij不變。（3）所有中間轉(zhuǎn)運(yùn)站的產(chǎn)量等于銷量，即流入量等于流出量。（4）擴(kuò)大的運(yùn)輸問題中原來的產(chǎn)地（加工廠）與銷地（銷售點(diǎn)），因?yàn)橐灿兄虚g轉(zhuǎn)運(yùn)站的作用，所以同樣在原來的產(chǎn)量與銷量上加t＝20噸。即三個(gè)加工廠的每日產(chǎn)量分別改為27噸、24噸和29噸，銷量均為20噸；四個(gè)銷售點(diǎn)的每日銷量分別改為23噸、26噸、25噸和26噸，產(chǎn)量均為20噸。同時(shí)引進(jìn)xii為輔助變量（虛擬運(yùn)量）。3.4轉(zhuǎn)運(yùn)問題【解】表3-10為擴(kuò)大的運(yùn)輸問題產(chǎn)銷平衡表與單位運(yùn)價(jià)表。單位運(yùn)價(jià)A1A2A3T1T2T3T4B1B2B3B4產(chǎn)量A1013214331131027A210M35M2192824A33M01M237410529T12310132284620T215M1011452720T34M23102182420T432321201M2620B13172411014220B21194858M102120B332104222420320B410856746213020銷量20202020202020232625262403.4轉(zhuǎn)運(yùn)問題例3-5的電子表格模型例3-5（轉(zhuǎn)運(yùn)問題）有多組最優(yōu)解。（1）最優(yōu)調(diào)運(yùn)方案1：無(wú)需中間轉(zhuǎn)運(yùn)站，如表3-11和圖3-12所示；（2）最優(yōu)調(diào)運(yùn)方案2：需中間轉(zhuǎn)運(yùn)站T1，如表3-12和圖3-13所示；（3）最優(yōu)調(diào)運(yùn)方案3：需中間轉(zhuǎn)運(yùn)站T3，如表3-13和圖3-14所示。3.5指派問題的基本概念在生活中經(jīng)常會(huì)遇到這樣的問題：某單位需完成n項(xiàng)任務(wù)，恰好有n個(gè)人可以承擔(dān)這些任務(wù)。由于每個(gè)人的專長(zhǎng)不同，各人完成的任務(wù)不同，所需的時(shí)間（或效率）也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)所需的總時(shí)間最短（或總效率最高）。這類問題稱為指派問題或分派問題。平衡指派問題的假設(shè)如下：（1）人的數(shù)量和任務(wù)的數(shù)量相等；（2）每個(gè)人只能完成一項(xiàng)任務(wù)；（3）每項(xiàng)任務(wù)只能由一個(gè)人完成；（4）每個(gè)人和每項(xiàng)任務(wù)的組合都會(huì)有一個(gè)相關(guān)的成本（單位成本）；（5）目標(biāo)是要確定如何指派才能使總成本最小。3.5指派問題的基本概念設(shè)xij為是否指派第i個(gè)人去完成第j項(xiàng)任務(wù)，目標(biāo)函數(shù)系數(shù)cij為第i個(gè)人完成第j項(xiàng)任務(wù)所需要的單位成本。平衡指派問題的線性規(guī)劃模型如下：3.5指派問題的基本概念需要說明的是：指派問題實(shí)際上是一種特殊的運(yùn)輸問題。其中出發(fā)地是“人”，目的地是“任務(wù)”。只不過，每個(gè)出發(fā)地的供應(yīng)量都為1（因?yàn)槊總€(gè)人都要完成一項(xiàng)任務(wù)），每個(gè)目的地的需求量也都為1（因?yàn)槊宽?xiàng)任務(wù)都要完成）。由于運(yùn)輸問題有整數(shù)解性質(zhì)，因此，指派問題沒有必要加上所有決策變量都是0-1變量的約束條件。指派問題是一種特殊的線性規(guī)劃問題，有一種簡(jiǎn)便的求解方法：匈牙利方法（HungarianMethod），但Excel的“規(guī)劃求解”功能還是采用單純形法來求解。3.5指派問題的基本概念例3-6

某公司的營(yíng)銷經(jīng)理將要主持召開一年一度的由營(yíng)銷區(qū)域經(jīng)理以及營(yíng)銷人員參加的銷售協(xié)商會(huì)議。為了更好地召開這次會(huì)議，他安排小張、小王、小李、小劉四個(gè)人，每個(gè)人負(fù)責(zé)完成一項(xiàng)任務(wù)：A、B、C和D。由于每個(gè)人完成每項(xiàng)任務(wù)的時(shí)間和工資不同。問公司應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，才能使總成本最??？完成每項(xiàng)任務(wù)的時(shí)間（小時(shí)）每小時(shí)工資（元）任務(wù)A任務(wù)B任務(wù)C任務(wù)D小張3541274014小王4745325112小李3956364313小劉32512546153.5指派問題的基本概念【解】

該問題是一個(gè)典型的平衡指派問題。單位成本為每個(gè)人完成每項(xiàng)任務(wù)的總工資；目標(biāo)是要確定哪個(gè)人去完成哪項(xiàng)任務(wù)，才能使總成本最??；供應(yīng)量為1表示每個(gè)人都只能完成一項(xiàng)任務(wù)；需求量為1表示每項(xiàng)任務(wù)也只能由一個(gè)人完成；總?cè)藬?shù)（4人）和總?cè)蝿?wù)數(shù)（4項(xiàng)）相等。3.5指派問題的基本概念例3-6的線性規(guī)劃模型設(shè)xij為是否指派人員i去完成任務(wù)j

3.5指派問題的基本概念例3-6的電子表格模型3.5指派問題的基本概念例3-6的最優(yōu)指派方案網(wǎng)絡(luò)圖小李小劉小張BCAD人指派任務(wù)小王3.6指派問題的變形經(jīng)常會(huì)遇到指派問題的變形，之所以稱它們?yōu)樽冃?，是因?yàn)樗鼈兌疾粷M足平衡指派問題所有假設(shè)中的一個(gè)或者多個(gè)。一般考慮下面的一些特征：特征1：某人不能完成某項(xiàng)任務(wù)（相應(yīng)的xij＝0）；特征2：每個(gè)人只能完成一項(xiàng)任務(wù)，但是任務(wù)數(shù)比人數(shù)多(人少事多)；特征3：每項(xiàng)任務(wù)只由一個(gè)人完成，但是人數(shù)比任務(wù)數(shù)多（人多事少）；特征4：某人可以同時(shí)被指派多項(xiàng)任務(wù)（一人可做多事）；特征5：某事需要由多人共同完成（一事需多人做）；特征6：目標(biāo)是與指派有關(guān)的總利潤(rùn)最大而不是總成本最小；特征7：實(shí)際能夠完成的任務(wù)數(shù)小于總?cè)藬?shù)，也小于總?cè)蝿?wù)數(shù)。3.6指派問題的變形例3-7指派工廠生產(chǎn)產(chǎn)品問題。題目見例3-3，即某公司需要安排三個(gè)工廠來生產(chǎn)四種產(chǎn)品，相關(guān)的數(shù)據(jù)見表3-7。在例3-3中，允許產(chǎn)品生產(chǎn)分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的隱性成本（包括額外的設(shè)置、配送和管理成本等）。因此，管理人員決定在禁止產(chǎn)品生產(chǎn)分解發(fā)生