第4講- 運(yùn)輸問題及指派問題

1、運(yùn)用運(yùn)用ExcelExcel建模和求解建模和求解第第4 4章章運(yùn)輸問題和指派問題運(yùn)輸問題和指派問題本章內(nèi)容要點(diǎn)本章內(nèi)容要點(diǎn) 運(yùn)輸問題運(yùn)輸問題的基本概念及其的基本概念及其各種變形的建模與應(yīng)用各種變形的建模與應(yīng)用 指派問題指派問題的基本概念及其的基本概念及其各種變形的建模與應(yīng)用各種變形的建模與應(yīng)用本章節(jié)內(nèi)容本章節(jié)內(nèi)容4.1 4.1 運(yùn)輸問題基本概念運(yùn)輸問題基本概念4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型4.3 4.3 各種運(yùn)輸問題變形的建模各種運(yùn)輸問題變形的建模4.4 4.4 運(yùn)輸問題應(yīng)用舉例運(yùn)輸問題應(yīng)用舉例4.5 4.5 指派問題指派問題4.6 4.6 各種指

2、派問題變形的建模各種指派問題變形的建模本章主要內(nèi)容框架圖本章主要內(nèi)容框架圖產(chǎn)銷平衡（總產(chǎn)量等于總銷量）產(chǎn)大于銷（總產(chǎn)量大于總銷量）銷大于產(chǎn)（總產(chǎn)量小于總銷量）運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題和指派問題各種變形的建模應(yīng)用舉例平衡指派問題（總?cè)藬?shù)等于總?cè)蝿?wù)數(shù)）指派問題數(shù)學(xué)模型和電子表格模型各種變形的建模4.1 4.1 運(yùn)輸問題基本概念運(yùn)輸問題基本概念運(yùn)輸問題最初起源于人們?cè)谌粘Ｉ钪邪涯承┻\(yùn)輸問題最初起源于人們?cè)谌粘Ｉ钪邪涯承┪锲坊蛉藗冏陨韽囊恍┑胤睫D(zhuǎn)移到另一些地方物品或人們自身從一些地方轉(zhuǎn)移到另一些地方，要求所采用的，要求所采用的運(yùn)輸路線運(yùn)輸路線或或運(yùn)輸方案是最經(jīng)濟(jì)運(yùn)輸方案是最經(jīng)濟(jì)或成本

3、最低或成本最低的，這就成為了一個(gè)運(yùn)籌學(xué)問題。的，這就成為了一個(gè)運(yùn)籌學(xué)問題。隨著經(jīng)濟(jì)的不斷發(fā)展，現(xiàn)代隨著經(jīng)濟(jì)的不斷發(fā)展，現(xiàn)代物流業(yè)物流業(yè)蓬勃發(fā)展，蓬勃發(fā)展，如何充分利用時(shí)間、信息、倉儲(chǔ)、配送和聯(lián)運(yùn)如何充分利用時(shí)間、信息、倉儲(chǔ)、配送和聯(lián)運(yùn)體系創(chuàng)造更多的價(jià)值，向運(yùn)籌學(xué)提出了更高的體系創(chuàng)造更多的價(jià)值，向運(yùn)籌學(xué)提出了更高的挑戰(zhàn)。挑戰(zhàn)。要求科學(xué)地組織貨源、運(yùn)輸和配送使得運(yùn)輸問要求科學(xué)地組織貨源、運(yùn)輸和配送使得運(yùn)輸問題變得日益復(fù)雜，但是其基本思想仍然是題變得日益復(fù)雜，但是其基本思想仍然是實(shí)現(xiàn)實(shí)現(xiàn)現(xiàn)有資源的最優(yōu)化配置現(xiàn)有資源的最優(yōu)化配置。4.1 4.1 運(yùn)輸問題基本概念運(yùn)輸問題基本概念一般的運(yùn)輸問題就是解決如

4、何把某種產(chǎn)品從若干個(gè)一般的運(yùn)輸問題就是解決如何把某種產(chǎn)品從若干個(gè)產(chǎn)地產(chǎn)地調(diào)運(yùn)到若干個(gè)調(diào)運(yùn)到若干個(gè)銷地銷地，在每個(gè)產(chǎn)地的，在每個(gè)產(chǎn)地的供應(yīng)量供應(yīng)量和每個(gè)銷地的和每個(gè)銷地的需求量需求量已知，并知道各地之間的已知，并知道各地之間的運(yùn)輸單價(jià)運(yùn)輸單價(jià)的前提下，如的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。平衡運(yùn)輸問題平衡運(yùn)輸問題的條件：的條件：1.1.明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應(yīng)量（產(chǎn)量）、需明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應(yīng)量（產(chǎn)量）、需求量（銷量）和單位成本。求量（銷量）和單位成本。2.2.需求假設(shè)：每一個(gè)出發(fā)地都有一個(gè)固定的供應(yīng)量，所有

5、的供應(yīng)需求假設(shè)：每一個(gè)出發(fā)地都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。與之類似，每一個(gè)目的地都有一個(gè)固量都必須配送到目的地。與之類似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須由出發(fā)地滿足。即定的需求量，整個(gè)需求量都必須由出發(fā)地滿足。即“總供應(yīng)總供應(yīng)總需求總需求”。3.3.成本假設(shè)：從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送成成本假設(shè)：從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送成本與所配送的數(shù)量成線性比例關(guān)系，因此成本就等于配送的單本與所配送的數(shù)量成線性比例關(guān)系，因此成本就等于配送的單位成本乘以所配送的數(shù)量（目標(biāo)函數(shù)是線性的）。位成本乘以所配送的數(shù)量（目標(biāo)函數(shù)是線性的）。4

6、.1 4.1 運(yùn)輸問題基本概念運(yùn)輸問題基本概念例例4.1 4.1 某公司有三個(gè)加工廠某公司有三個(gè)加工廠A1A1、A2A2、A3A3生產(chǎn)某產(chǎn)品，每生產(chǎn)某產(chǎn)品，每日的產(chǎn)量分別為：日的產(chǎn)量分別為：7 7噸、噸、4 4噸、噸、9 9噸；該公司把這些產(chǎn)品噸；該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)分別運(yùn)往四個(gè)銷售點(diǎn)B1B1、B2B2、B3B3、B4B4，各銷售點(diǎn)每日銷，各銷售點(diǎn)每日銷量分別為：量分別為：3 3噸、噸、6 6噸、噸、5 5噸、噸、6 6噸；從各工廠到各銷售點(diǎn)噸；從各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如表的單位產(chǎn)品運(yùn)價(jià)如表4 41 1所示。問該公司應(yīng)如何調(diào)運(yùn)這所示。問該公司應(yīng)如何調(diào)運(yùn)這些產(chǎn)品，在滿足各銷

7、售點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)些產(chǎn)品，在滿足各銷售點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)最少？最少？ 表表4 41 1 各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)（元各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)（元/ /噸）噸）B1B1B2B2B3B3B4B4產(chǎn)量（噸）產(chǎn)量（噸）A1A13 311113 310107 7A2A21 19 92 28 84 4A3A37 74 410105 59 9銷量（噸）銷量（噸）3 36 65 56 64.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型（1 1）產(chǎn)銷平衡產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題的數(shù)學(xué)模型 具有具有m個(gè)產(chǎn)地個(gè)產(chǎn)地A Ai i（i1,2,1,2

8、, ,m）和和n個(gè)銷地個(gè)銷地 B Bj j（j1,2,1,2, ,n）的運(yùn)輸問題的數(shù)學(xué)模型為的運(yùn)輸問題的數(shù)學(xué)模型為1111()()M in (1, 2,) s.t. (1, 2,)0 (1, 2,; 1, 2,)mnijijijnijijmijjiijzc xxaimxbjnximjn 產(chǎn) 量 約 束銷 量 約 束 LLLL11mnijijab4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型對(duì)于例對(duì)于例4.14.1，其數(shù)學(xué)模型如下：，其數(shù)學(xué)模型如下： 首先，三個(gè)產(chǎn)地首先，三個(gè)產(chǎn)地A1A1、A2A2、A3A3的總產(chǎn)量為的總產(chǎn)量為7 74 49 92020；四個(gè)；四個(gè)銷

9、地銷地B1B1、B2B2、B3B3、B4B4的總銷量為的總銷量為3 36 65 56 62020。由于總。由于總產(chǎn)量等于總銷量，故該問題是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。產(chǎn)量等于總銷量，故該問題是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。(1)(1)決策變量決策變量 設(shè)設(shè)xij為從產(chǎn)地為從產(chǎn)地AiAi運(yùn)往銷地運(yùn)往銷地BjBj的運(yùn)輸量的運(yùn)輸量(i(i1,2,3;j=1,2,3,4)1,2,3;j=1,2,3,4) （2 2）目標(biāo)函數(shù)）目標(biāo)函數(shù) 本問題的目標(biāo)是使得總運(yùn)輸費(fèi)最小。本問題的目標(biāo)是使得總運(yùn)輸費(fèi)最小。1 11 21 31 42 12 22 32 43 13 23 33 4M in z31 1 31 0 9 2 8

10、741 0 5xxxxxxxxxxxx4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型（3 3）約束條件）約束條件滿足產(chǎn)地產(chǎn)量滿足產(chǎn)地產(chǎn)量（3 3個(gè)產(chǎn)地的個(gè)產(chǎn)地的產(chǎn)品都要全部產(chǎn)品都要全部配送出去）配送出去）滿足銷地銷量滿足銷地銷量（4 4個(gè)銷地的個(gè)銷地的產(chǎn)品都要全部產(chǎn)品都要全部得到滿足）得到滿足）非負(fù)非負(fù)111213142122232431323334111213142122232431323334112131122232Min z311 310 9 2 8 7 410 57 4 9 3 s.t. 6 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx13

11、23331424345 6 0(1,2,3;1,2,3,4)ijxxxxxxxij4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型u運(yùn)輸問題是一種特殊的線性規(guī)劃問題，一般采用運(yùn)輸問題是一種特殊的線性規(guī)劃問題，一般采用“表上作表上作業(yè)法業(yè)法”求解運(yùn)輸問題，但求解運(yùn)輸問題，但ExcelExcel的的“規(guī)劃求解規(guī)劃求解”還是采用還是采用“單純形法單純形法”來求解。來求解。u例例4.14.1的電子表格模型的電子表格模型4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型（2 2）產(chǎn)大于銷（供過于求）產(chǎn)大于銷（供過于求）運(yùn)輸問題運(yùn)輸問題的數(shù)學(xué)模型的數(shù)學(xué)

12、模型（以滿足小的銷量為準(zhǔn)以滿足小的銷量為準(zhǔn)）11mnijijab1111()()Min z (1,2,) s.t. (1,2, ) 0 (1,2,;1,2, )mniji jijnijijmijjiijc xxaimxbjnxim jn 產(chǎn)量約束銷量約束LLLL4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型（3 3）銷大于產(chǎn)（供不應(yīng)求）銷大于產(chǎn)（供不應(yīng)求）運(yùn)輸問題運(yùn)輸問題的數(shù)學(xué)模型的數(shù)學(xué)模型（以滿足小的產(chǎn)量為準(zhǔn)以滿足小的產(chǎn)量為準(zhǔn)）11mnijijab1111 ()()Min (1,2,) s.t. (1,2, ) 0 (1,2,;1,2, )mniji jijni

13、jijmijjiijzc xxaimxbjnxim jn產(chǎn)量約束銷量約束LLLL4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型該生產(chǎn)與該生產(chǎn)與儲(chǔ)存問題儲(chǔ)存問題（轉(zhuǎn)化為（轉(zhuǎn)化為產(chǎn)大于銷產(chǎn)大于銷的運(yùn)輸問的運(yùn)輸問題）的數(shù)題）的數(shù)學(xué)模型為學(xué)模型為111213142223243334M in z10.8010.9511.1011.25 11.1011.2511.40 11.0011.15 xxxxxxxxx4411121314222324333444111222132333 11.3025 35 30 10s.t. 10 15 xxxxxxxxxxxxxxxxx142434

14、44 25200 ( ,1, 2,3, 4; )ijxxxxxijij4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型例例4.34.3 某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1A1、A2A2將物品運(yùn)往將物品運(yùn)往三個(gè)銷地三個(gè)銷地 B1 B1、B2B2、B3B3，各產(chǎn)地的產(chǎn)量、各銷，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如表費(fèi)如表4 46 6所示。問應(yīng)如何調(diào)運(yùn)，可使得總所示。問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最?。窟\(yùn)輸費(fèi)最??？表表4 46 6 例例4.34.3的運(yùn)輸費(fèi)用表的運(yùn)輸費(fèi)用表 B1B1B2B2B3B3產(chǎn)量產(chǎn)量A1A

15、11313151512127878A2A21111292922224545銷量銷量535336366565（銷大于產(chǎn)）（銷大于產(chǎn)）4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型解：解：由表由表4 46 6知，總產(chǎn)量為知，總產(chǎn)量為78+45=12378+45=123，總銷量為，總銷量為53+36+65=15453+36+65=154，銷大于產(chǎn)銷大于產(chǎn)( (供不應(yīng)求供不應(yīng)求) )。數(shù)學(xué)模型如下：。數(shù)學(xué)模型如下： 設(shè)設(shè)xij為產(chǎn)地為產(chǎn)地AiAi運(yùn)往銷地運(yùn)往銷地BjBj的物品數(shù)量的物品數(shù)量11121321222311121312122232112111222213233M

16、in z 13151211292278 ()45 ()53 ()s.t. 36 ()65 ()0(1,2;1,2,3)ijxxxxxxxxxAxxxAxxBxxBxxBxij產(chǎn)地產(chǎn)地銷地銷地銷地4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型例例4.34.3的電子表格模型的電子表格模型4.3 4.3 各種運(yùn)輸問題變形的建模各種運(yùn)輸問題變形的建?，F(xiàn)實(shí)生活中符合產(chǎn)銷平衡運(yùn)輸問題每一個(gè)條件的情況很少。一現(xiàn)實(shí)生活中符合產(chǎn)銷平衡運(yùn)輸問題每一個(gè)條件的情況很少。一個(gè)特征近似但其中的一個(gè)或者幾個(gè)特征卻并不符合產(chǎn)銷平衡運(yùn)個(gè)特征近似但其中的一個(gè)或者幾個(gè)特征卻并不符合產(chǎn)銷平衡運(yùn)輸問題條件

17、的運(yùn)輸問題卻經(jīng)常出現(xiàn)。輸問題條件的運(yùn)輸問題卻經(jīng)常出現(xiàn)。下面是要討論的一些特征：下面是要討論的一些特征：（1 1）總供應(yīng)大于總需求總供應(yīng)大于總需求。每一個(gè)供應(yīng)量（產(chǎn)量）代表了從其出。每一個(gè)供應(yīng)量（產(chǎn)量）代表了從其出發(fā)地中配送出去的最大數(shù)量（而不是一個(gè)固定的數(shù)值發(fā)地中配送出去的最大數(shù)量（而不是一個(gè)固定的數(shù)值, ,）。）。（2 2）總供應(yīng)小于總需求總供應(yīng)小于總需求。每一個(gè)需求量（銷量）代表了在其目。每一個(gè)需求量（銷量）代表了在其目的地中所接收到的最大數(shù)量（而不是一個(gè)固定的數(shù)值的地中所接收到的最大數(shù)量（而不是一個(gè)固定的數(shù)值, ,）。）。（3 3）一個(gè)目的地）一個(gè)目的地同時(shí)存在著最小需求和最大需求同時(shí)存

18、在著最小需求和最大需求，于是所有在，于是所有在這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的（這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的（, ,）。）。（4 4）在配送中）在配送中不能使用不能使用特定的出發(fā)地特定的出發(fā)地目的地組合（目的地組合（xij=0=0）。）。（5 5）目標(biāo)是使與配送數(shù)量有關(guān)的）目標(biāo)是使與配送數(shù)量有關(guān)的總利潤(rùn)最大總利潤(rùn)最大而不是使總成本最而不是使總成本最小。（小。（MinMin MaxMax）4.3 4.3 各種運(yùn)輸問題變形的建模各種運(yùn)輸問題變形的建模例例4.54.5 某公司在某公司在3 3個(gè)工廠中專門生產(chǎn)一種產(chǎn)品。在未來的個(gè)工廠中專門生產(chǎn)一種產(chǎn)品。在未來的4 4個(gè)月中，有四個(gè)月中，有四個(gè)處

19、于國(guó)內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能大量訂購(gòu)。顧客個(gè)處于國(guó)內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能大量訂購(gòu)。顧客1 1是公司是公司最好的顧客，所以他的全部訂購(gòu)量都應(yīng)該滿足；顧客最好的顧客，所以他的全部訂購(gòu)量都應(yīng)該滿足；顧客2 2和顧客和顧客3 3也是公司很也是公司很重要的顧客，所以營(yíng)銷經(jīng)理認(rèn)為作為最低限度至少要滿足他們訂單的重要的顧客，所以營(yíng)銷經(jīng)理認(rèn)為作為最低限度至少要滿足他們訂單的1/31/3；對(duì)于顧客對(duì)于顧客4 4，銷售經(jīng)理認(rèn)為并不需要進(jìn)行特殊考慮。由于運(yùn)輸成本上的差異，銷售經(jīng)理認(rèn)為并不需要進(jìn)行特殊考慮。由于運(yùn)輸成本上的差異，銷售一個(gè)產(chǎn)品得到的凈利潤(rùn)也不同，很大程度上取決于哪個(gè)工廠供應(yīng)哪，

20、銷售一個(gè)產(chǎn)品得到的凈利潤(rùn)也不同，很大程度上取決于哪個(gè)工廠供應(yīng)哪個(gè)顧客（見表個(gè)顧客（見表4 48 8）。問應(yīng)）。問應(yīng)向每一個(gè)顧客供應(yīng)多少貨物向每一個(gè)顧客供應(yīng)多少貨物，以使公司總利潤(rùn)，以使公司總利潤(rùn)最大？最大？表表4 48 8 工廠供應(yīng)顧客的相關(guān)數(shù)據(jù)工廠供應(yīng)顧客的相關(guān)數(shù)據(jù)單位利潤(rùn)（元）單位利潤(rùn)（元）產(chǎn)量產(chǎn)量顧客顧客1 1顧客顧客2 2顧客顧客3 3顧客顧客4 4工廠工廠1 1555542424646535380008000工廠工廠2 2373718183232484850005000工廠工廠3 3292959595151353570007000最小采購(gòu)量最小采購(gòu)量70007000300030002

21、00020000 0最大采購(gòu)量最大采購(gòu)量700070009000900060006000800080004.3 4.3 各種運(yùn)輸問題變形的建模各種運(yùn)輸問題變形的建模解：解：該問題要求滿足不該問題要求滿足不同顧客的需求（采購(gòu)量同顧客的需求（采購(gòu)量），解決辦法：），解決辦法：實(shí)際供給量實(shí)際供給量 最小采購(gòu)量最小采購(gòu)量實(shí)際供給量實(shí)際供給量 最大采購(gòu)量最大采購(gòu)量 目標(biāo)是利潤(rùn)最大，而目標(biāo)是利潤(rùn)最大，而不是成本最小。不是成本最小。其數(shù)學(xué)模型如下：其數(shù)學(xué)模型如下： 設(shè)設(shè)xij為工廠為工廠i供應(yīng)給顧供應(yīng)給顧客客j的產(chǎn)品數(shù)量的產(chǎn)品數(shù)量111213142122232431323334111213142122232

22、431323334Max z55424653 37183248 295951358000 (1)5000 (2)7000 (3)s.t. xxxxxxxxxxxxxxxxxxxxxxxxx工廠工廠工廠1121311222321323331424347000 (1)30009000 (2)20006000 (3)8000 (4)0(1,2,3;1,2,3,4)ijxxxxxxxxxxxxij顧客顧客顧客顧客4.3 4.3 各種運(yùn)輸問題變形的建模各種運(yùn)輸問題變形的建模例例4.54.5的電子表格模型的電子表格模型4.5 4.5 指派問題指派問題u在現(xiàn)實(shí)生活中，經(jīng)常會(huì)遇到指派人員做某項(xiàng)在現(xiàn)實(shí)生活中，經(jīng)

23、常會(huì)遇到指派人員做某項(xiàng)工作（任務(wù)）的情況。工作（任務(wù)）的情況。指派問題指派問題的許多應(yīng)用是的許多應(yīng)用是用來幫助管理人員解決如何為一項(xiàng)即將開展的用來幫助管理人員解決如何為一項(xiàng)即將開展的工作指派人員的問題。其他的一些應(yīng)用如為工工作指派人員的問題。其他的一些應(yīng)用如為工作指派機(jī)器、設(shè)備或工廠等。作指派機(jī)器、設(shè)備或工廠等。u指派問題也稱指派問題也稱分配問題分配問題，主要研究人和工作，主要研究人和工作（任務(wù)）間如何匹配，以使所有工作完成的效（任務(wù)）間如何匹配，以使所有工作完成的效率實(shí)現(xiàn)最優(yōu)化。形式上，指派問題給定了一系率實(shí)現(xiàn)最優(yōu)化。形式上，指派問題給定了一系列所要完成的工作以及一系列完成工作的人員列所要完

24、成的工作以及一系列完成工作的人員，所需要解決的問題就是要確定出指派哪個(gè)人，所需要解決的問題就是要確定出指派哪個(gè)人去完成哪項(xiàng)工作。去完成哪項(xiàng)工作。4.5 4.5 指派問題指派問題u指派問題的假設(shè)：指派問題的假設(shè)：（1 1）人的數(shù)量和工作的數(shù)量）人的數(shù)量和工作的數(shù)量相等相等；（2 2）每個(gè)人）每個(gè)人只能完成一項(xiàng)只能完成一項(xiàng)工作；工作；（3 3）每項(xiàng)工作）每項(xiàng)工作只能由一個(gè)人只能由一個(gè)人來完成；來完成；（4 4）每個(gè)人和每項(xiàng)工作的組合都會(huì)有）每個(gè)人和每項(xiàng)工作的組合都會(huì)有一個(gè)相關(guān)的成本（一個(gè)相關(guān)的成本（單位成本單位成本）；）；（5 5）目標(biāo)是要確定如何指派才能使）目標(biāo)是要確定如何指派才能使總總成本最小

25、成本最小。4.5 4.5 指派問題指派問題u設(shè)決策變量設(shè)決策變量xij為第為第i個(gè)人做第個(gè)人做第j項(xiàng)工作，而已項(xiàng)工作，而已知目標(biāo)函數(shù)系數(shù)知目標(biāo)函數(shù)系數(shù)cij為第為第i個(gè)人完成第個(gè)人完成第j項(xiàng)工作所項(xiàng)工作所需要的單位成本。需要的單位成本。u平衡指派問題的數(shù)學(xué)模型為平衡指派問題的數(shù)學(xué)模型為1111 ()Min z1 (1,2, )s.t. 1 (1,2, )0 ( ,1,2, ) nnijijijnijjnijiijijc xxinxjnxi jn(第 人只能做一項(xiàng)工作)(第 項(xiàng)工作只能一人做)非負(fù) LLL4.5 4.5 指派問題指派問題u需要說明的是：需要說明的是：指派問題指派問題實(shí)際上是一種實(shí)

26、際上是一種特殊特殊的運(yùn)輸問題的運(yùn)輸問題。其中出發(fā)地是人，目的地是工作。其中出發(fā)地是人，目的地是工作。只不過，每一個(gè)出發(fā)地的。只不過，每一個(gè)出發(fā)地的供應(yīng)量都為供應(yīng)量都為1 1（因（因?yàn)槊總€(gè)人都要完成一項(xiàng)工作），每一個(gè)目的地為每個(gè)人都要完成一項(xiàng)工作），每一個(gè)目的地的的需求量都為需求量都為1 1（因?yàn)槊宽?xiàng)工作都要完成）。（因?yàn)槊宽?xiàng)工作都要完成）。由于運(yùn)輸問題有由于運(yùn)輸問題有“整數(shù)解性質(zhì)整數(shù)解性質(zhì)”，因此，沒有，因此，沒有必要加上所有決策變量都是必要加上所有決策變量都是0-10-1變量變量的約束。的約束。u指派問題是一種特殊的線性規(guī)劃問題，有一指派問題是一種特殊的線性規(guī)劃問題，有一種快捷的求解方法：種

27、快捷的求解方法：匈牙利方法匈牙利方法（Hungarian Hungarian MethodMethod），但），但ExcelExcel的的“規(guī)劃求解規(guī)劃求解”還是采用還是采用“單純形法單純形法”來求解。來求解。4.5 4.5 指派問題指派問題例例4.84.8 某公司的營(yíng)銷經(jīng)理將要主持召開一年一度的某公司的營(yíng)銷經(jīng)理將要主持召開一年一度的由營(yíng)銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會(huì)議由營(yíng)銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會(huì)議。為了更好地安排這次會(huì)議，他安排小張、小王、。為了更好地安排這次會(huì)議，他安排小張、小王、小李、小劉等四個(gè)人，每個(gè)人負(fù)責(zé)完成下面的一項(xiàng)小李、小劉等四個(gè)人，每個(gè)人負(fù)責(zé)完成下面的一項(xiàng)

28、工作：工作：A A、B B、C C和和D D。 由于每個(gè)人完成每項(xiàng)任務(wù)的時(shí)間和工資不同（如由于每個(gè)人完成每項(xiàng)任務(wù)的時(shí)間和工資不同（如表表4 41414所示）。問如何指派，可使總成本最小。所示）。問如何指派，可使總成本最小。人員人員每一項(xiàng)工作所需要的時(shí)間（小時(shí)）每一項(xiàng)工作所需要的時(shí)間（小時(shí)）每小時(shí)工資每小時(shí)工資（元）（元）工作工作A A工作工作B B工作工作C C工作工作D D小張小張35354141272740401414小王小王47474545323251511212小李小李39395656363643431313小劉小劉323251512525464615154.5 4.5 指派問題指派問

29、題解解：該問題是一個(gè)：該問題是一個(gè)典型的指派問題典型的指派問題。單位成本單位成本為每個(gè)人做每項(xiàng)工作的總為每個(gè)人做每項(xiàng)工作的總工資工資目標(biāo)目標(biāo)是要確定哪個(gè)人做哪一項(xiàng)工作是要確定哪個(gè)人做哪一項(xiàng)工作，使總成本最小，使總成本最小供應(yīng)量為供應(yīng)量為1 1代表每個(gè)人都只能完成一代表每個(gè)人都只能完成一項(xiàng)工作項(xiàng)工作需求量為需求量為1 1代表每項(xiàng)工作也只能有一代表每項(xiàng)工作也只能有一個(gè)人來完成個(gè)人來完成總?cè)藬?shù)（總?cè)藬?shù)（4 4人）和總?cè)蝿?wù)數(shù)（人）和總?cè)蝿?wù)數(shù)（4 4項(xiàng)）項(xiàng)）相等相等4.5 4.5 指派問題指派問題數(shù)學(xué)模型：數(shù)學(xué)模型：設(shè)設(shè)xij為指派人員為指派人員i去做工作去做工作j（i，j1,2,3,4)1,2,3,4

30、) 1 11 21 31 42 12 22 32 43 13 23 33 44 14 24 34 41 11 21 31 42 12 2M in z 3 51 44 11 42 71 44 01 4 4 71 24 51 23 21 25 11 2 3 91 35 61 33 61 34 31 3 3 21 55 11 52 51 54 61 51 s .t. xxxxxxxxxxxxxxxxxxxxxx（ 小 張 要 完 成 一 項(xiàng) 工 作 ） 2 32 43 13 23 33 44 14 24 34 41 12 13 14 11 22 23 24 21 32 33 34 31 42 43 44 4D1 1 1 1 1 1 1 xxxxxxxxxxxxxxxxxxxxxxxxxx（ 小 王 要 完 成 一 項(xiàng) 工 作 ）（ 小 李 要 完 成 一 項(xiàng) 工 作 ）（ 小