運(yùn)輸問(wèn)題和指派問(wèn)題

1、 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題實(shí)用運(yùn)籌學(xué)實(shí)用運(yùn)籌學(xué)運(yùn)用運(yùn)用ExcelExcel建模和求解建模和求解運(yùn)輸問(wèn)題和指派問(wèn)題運(yùn)輸問(wèn)題和指派問(wèn)題 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題本章內(nèi)容要點(diǎn)本章內(nèi)容要點(diǎn) 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的基本概念及其的基本概念及其各種變形的建模與應(yīng)用各種變形的建模與應(yīng)用 指派問(wèn)題指派問(wèn)題的基本概念及其的基本概念及其各種變形的建模與應(yīng)用各種變形的建模與應(yīng)用 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題本章節(jié)內(nèi)容本章節(jié)內(nèi)容3.1 3.1 運(yùn)輸問(wèn)題基本概念運(yùn)輸問(wèn)題基本概念3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型3.3 3.3 各種運(yùn)輸問(wèn)題變形的建

2、模各種運(yùn)輸問(wèn)題變形的建模3.4 3.4 運(yùn)輸問(wèn)題應(yīng)用舉例運(yùn)輸問(wèn)題應(yīng)用舉例3.5 3.5 指派問(wèn)題指派問(wèn)題3.6 3.6 各種指派問(wèn)題變形的建模各種指派問(wèn)題變形的建模 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題本章主要內(nèi)容框架圖本章主要內(nèi)容框架圖產(chǎn)銷(xiāo)平衡（總產(chǎn)量等于總銷(xiāo)量）產(chǎn)大于銷(xiāo)（總產(chǎn)量大于總銷(xiāo)量）銷(xiāo)大于產(chǎn)（總產(chǎn)量小于總銷(xiāo)量）運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題和指派問(wèn)題各種變形的建模應(yīng)用舉例平衡指派問(wèn)題（總?cè)藬?shù)等于總?cè)蝿?wù)數(shù)）指派問(wèn)題數(shù)學(xué)模型和電子表格模型各種變形的建模 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.1 3.1 運(yùn)輸問(wèn)題基本概念運(yùn)輸問(wèn)題基本概念運(yùn)輸問(wèn)題最初起源于人們?cè)谌粘Ｉ钪邪涯承?/p>

3、運(yùn)輸問(wèn)題最初起源于人們?cè)谌粘Ｉ钪邪涯承┪锲坊蛉藗冏陨韽囊恍┑胤睫D(zhuǎn)移到另一些地方物品或人們自身從一些地方轉(zhuǎn)移到另一些地方，要求所采用的，要求所采用的運(yùn)輸路線運(yùn)輸路線或或運(yùn)輸方案是最經(jīng)濟(jì)運(yùn)輸方案是最經(jīng)濟(jì)或成本最低或成本最低的，這就成為了一個(gè)運(yùn)籌學(xué)問(wèn)題。的，這就成為了一個(gè)運(yùn)籌學(xué)問(wèn)題。隨著經(jīng)濟(jì)的不斷發(fā)展，現(xiàn)代隨著經(jīng)濟(jì)的不斷發(fā)展，現(xiàn)代物流業(yè)物流業(yè)蓬勃發(fā)展，蓬勃發(fā)展，如何充分利用時(shí)間、信息、倉(cāng)儲(chǔ)、配送和聯(lián)運(yùn)如何充分利用時(shí)間、信息、倉(cāng)儲(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)輸問(wèn)要求科學(xué)地組織貨源、運(yùn)輸和配

4、送使得運(yùn)輸問(wèn)題變得日益復(fù)雜，但是其基本思想仍然是題變得日益復(fù)雜，但是其基本思想仍然是實(shí)現(xiàn)實(shí)現(xiàn)現(xiàn)有資源的最優(yōu)化配置現(xiàn)有資源的最優(yōu)化配置。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.1 3.1 運(yùn)輸問(wèn)題基本概念運(yùn)輸問(wèn)題基本概念一般的運(yùn)輸問(wèn)題就是解決如何把某種產(chǎn)品從若干個(gè)一般的運(yùn)輸問(wèn)題就是解決如何把某種產(chǎn)品從若干個(gè)產(chǎn)地產(chǎn)地調(diào)運(yùn)到若干個(gè)調(diào)運(yùn)到若干個(gè)銷(xiāo)地銷(xiāo)地，在每個(gè)產(chǎn)地的，在每個(gè)產(chǎn)地的供應(yīng)量供應(yīng)量和每個(gè)銷(xiāo)地的和每個(gè)銷(xiāo)地的需求量需求量已知，并知道各地之間的已知，并知道各地之間的運(yùn)輸單價(jià)運(yùn)輸單價(jià)的前提下，如的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。平衡運(yùn)輸問(wèn)題平

5、衡運(yùn)輸問(wèn)題的條件：的條件：1.1.明確出發(fā)地（產(chǎn)地）、目的地（銷(xiāo)地）、供應(yīng)量（產(chǎn)量）、需明確出發(fā)地（產(chǎn)地）、目的地（銷(xiāo)地）、供應(yīng)量（產(chǎn)量）、需求量（銷(xiāo)量）和單位成本。求量（銷(xiāo)量）和單位成本。2.2.需求假設(shè)：每一個(gè)出發(fā)地都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)需求假設(shè)：每一個(gè)出發(fā)地都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。與之類(lèi)似，每一個(gè)目的地都有一個(gè)固量都必須配送到目的地。與之類(lèi)似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須由出發(fā)地滿(mǎn)足。即定的需求量，整個(gè)需求量都必須由出發(fā)地滿(mǎn)足。即“總供應(yīng)總供應(yīng)總需求總需求”。3.3.成本假設(shè)：從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送成成本假

6、設(shè)：從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送成本與所配送的數(shù)量成線性比例關(guān)系，因此成本就等于配送的單本與所配送的數(shù)量成線性比例關(guān)系，因此成本就等于配送的單位成本乘以所配送的數(shù)量（目標(biāo)函數(shù)是線性的）。位成本乘以所配送的數(shù)量（目標(biāo)函數(shù)是線性的）。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.1 3.1 運(yùn)輸問(wèn)題基本概念運(yùn)輸問(wè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è)銷(xiāo)售點(diǎn)分別運(yùn)往四個(gè)銷(xiāo)售點(diǎn)B1B1、B2

7、B2、B3B3、B4B4，各銷(xiāo)售點(diǎn)每日銷(xiāo)，各銷(xiāo)售點(diǎn)每日銷(xiāo)量分別為：量分別為：3 3噸、噸、6 6噸、噸、5 5噸、噸、6 6噸；從各工廠到各銷(xiāo)售點(diǎn)噸；從各工廠到各銷(xiāo)售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如表的單位產(chǎn)品運(yùn)價(jià)如表4 41 1所示。問(wèn)該公司應(yīng)如何調(diào)運(yùn)這所示。問(wèn)該公司應(yīng)如何調(diào)運(yùn)這些產(chǎn)品，在滿(mǎn)足各銷(xiāo)售點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)些產(chǎn)品，在滿(mǎn)足各銷(xiāo)售點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)最少？最少？ 表表4 41 1 各工廠到各銷(xiāo)售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)（元各工廠到各銷(xiāo)售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)（元/ /噸）噸）B1B1B2B2B3B3B4B4產(chǎn)量（噸）產(chǎn)量（噸）A1A13 311113 310107 7A2A21 19 92 28

8、 84 4A3A37 74 410105 59 9銷(xiāo)量（噸）銷(xiāo)量（噸）3 36 65 56 6 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型（1 1）產(chǎn)銷(xiāo)平衡產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的數(shù)學(xué)模型 具有具有m個(gè)產(chǎn)地個(gè)產(chǎn)地A Ai i（i1,2,1,2, ,m）和和n個(gè)銷(xiāo)地個(gè)銷(xiāo)地 B Bj j（j1,2,1,2, ,n）的運(yùn)輸問(wèn)題的數(shù)學(xué)模型為的運(yùn)輸問(wèn)題的數(shù)學(xué)模型為1111()()M in (1, 2,) s.t. (1, 2,)0 (1, 2,; 1, 2,)mnijijijnijijmijjiijzc xxaimxbj

9、nximjn 產(chǎn) 量 約 束銷(xiāo) 量 約 束 LLLL11mnijijab 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wè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è)銷(xiāo)地銷(xiāo)地B1B1、B2B2、B3B3、B4B4的總銷(xiāo)量為的總銷(xiāo)量為3 36 65 56 62020。由于總。由于總產(chǎn)量等于總銷(xiāo)量，故該問(wèn)題是一個(gè)產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。產(chǎn)量等于總銷(xiāo)量，故該問(wèn)題是一個(gè)產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。(1)(1)決策變量決

10、策變量 設(shè)設(shè)xij為從產(chǎn)地為從產(chǎn)地AiAi運(yùn)往銷(xiāo)地運(yùn)往銷(xiāo)地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ù) 本問(wèn)題的目標(biāo)是使得總運(yùn)輸費(fèi)最小。本問(wèn)題的目標(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 741 0 5xxxxxxxxxxxx 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型（3 3）約束條件）約束條件滿(mǎn)足產(chǎn)地產(chǎn)量滿(mǎn)足產(chǎn)地產(chǎn)量（3 3個(gè)產(chǎn)地的個(gè)產(chǎn)地的產(chǎn)品

11、都要全部產(chǎn)品都要全部配送出去）配送出去）滿(mǎn)足銷(xiāo)地銷(xiāo)量滿(mǎn)足銷(xiāo)地銷(xiāo)量（4 4個(gè)銷(xiāo)地的個(gè)銷(xiāo)地的產(chǎn)品都要全部產(chǎn)品都要全部得到滿(mǎn)足）得到滿(mǎn)足）非負(fù)非負(fù)111213142122232431323334111213142122232431323334112131122232Min z311 310 9 2 8 7 410 57 4 9 3 s.t. 6 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1323331424345 6 0(1,2,3;1,2,3,4)ijxxxxxxxij 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格

12、模型u運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，一般采用運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，一般采用“表上作表上作業(yè)法業(yè)法”求解運(yùn)輸問(wèn)題，但求解運(yùn)輸問(wèn)題，但ExcelExcel的的“規(guī)劃求解規(guī)劃求解”還是采用還是采用“單純形法單純形法”來(lái)求解。來(lái)求解。u例例4.14.1的電子表格模型的電子表格模型 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型u 需要注意的是：運(yùn)輸問(wèn)題有這樣一個(gè)性質(zhì)需要注意的是：運(yùn)輸問(wèn)題有這樣一個(gè)性質(zhì)（整數(shù)解性質(zhì)整數(shù)解性質(zhì)），只要它的），只要它的供應(yīng)量供應(yīng)量和和需求需求量量都是都是整數(shù)整數(shù)，任何有可行解的運(yùn)輸問(wèn)題必，任

13、何有可行解的運(yùn)輸問(wèn)題必然有所有決策變量都是然有所有決策變量都是整數(shù)的最優(yōu)解整數(shù)的最優(yōu)解。因。因此，沒(méi)有必要加上所有變量都是整數(shù)的約此，沒(méi)有必要加上所有變量都是整數(shù)的約束條件。束條件。u 由于運(yùn)輸量經(jīng)常以卡車(chē)、集裝箱等為單位由于運(yùn)輸量經(jīng)常以卡車(chē)、集裝箱等為單位，如果卡車(chē)不能裝滿(mǎn)的話，就很不經(jīng)濟(jì)了，如果卡車(chē)不能裝滿(mǎn)的話，就很不經(jīng)濟(jì)了。整數(shù)解性質(zhì)就避免了運(yùn)輸量（運(yùn)輸方案。整數(shù)解性質(zhì)就避免了運(yùn)輸量（運(yùn)輸方案）為小數(shù)的麻煩。）為小數(shù)的麻煩。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型（2 2）產(chǎn)大于銷(xiāo)（供過(guò)于求）產(chǎn)大于銷(xiāo)（供過(guò)于求）

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

15、. (1,2, ) 0 (1,2,;1,2, )mniji jijnijijmijjiijzc xxaimxbjnxim jn產(chǎn)量約束銷(xiāo)量約束LLLL 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型例例4.2 4.2 某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供供1010，1515，2525，2020臺(tái)同一規(guī)格的柴油機(jī)。已知該廠臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如表各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如表4 44 4所示。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨的，每臺(tái)

16、所示。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨的，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用15001500元。要求元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)（包括在完成合同的情況下，做出使該廠全年生產(chǎn)（包括儲(chǔ)存、維護(hù)）費(fèi)用最小的決策。儲(chǔ)存、維護(hù)）費(fèi)用最小的決策。表表4 44 4 各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本季度季度生產(chǎn)能力（臺(tái)）生產(chǎn)能力（臺(tái)）單位成本（萬(wàn)元）單位成本（萬(wàn)元）1 1252510.810.82 2353511.111.13 3303011.011.04 4101011.311.3 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指

17、派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型解：解：這是一個(gè)這是一個(gè)生產(chǎn)與儲(chǔ)存（庫(kù)存）問(wèn)題生產(chǎn)與儲(chǔ)存（庫(kù)存）問(wèn)題，除了采用第，除了采用第3 3章的方法外，還可以轉(zhuǎn)化為章的方法外，還可以轉(zhuǎn)化為運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題來(lái)做。來(lái)做。 由于每個(gè)季度生產(chǎn)出來(lái)的柴油機(jī)不一定當(dāng)季交貨，由于每個(gè)季度生產(chǎn)出來(lái)的柴油機(jī)不一定當(dāng)季交貨，所以設(shè)所以設(shè)xij為第為第i季度生產(chǎn)的第季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)季度交貨的柴油機(jī)數(shù)。則第則第i季度生產(chǎn)的第季度生產(chǎn)的第j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本本cij為：為： cij= =第第i季度每臺(tái)的生產(chǎn)成本季度每臺(tái)的生產(chǎn)

18、成本+0.15(+0.15(j-i) )（儲(chǔ)存、維護(hù)等費(fèi)用）（儲(chǔ)存、維護(hù)等費(fèi)用） 把第把第i季度生產(chǎn)的柴油機(jī)數(shù)看作第季度生產(chǎn)的柴油機(jī)數(shù)看作第i個(gè)生產(chǎn)廠商的個(gè)生產(chǎn)廠商的產(chǎn)量；把第產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)看作第季度交貨的柴油機(jī)數(shù)看作第j個(gè)銷(xiāo)售點(diǎn)的個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量；生產(chǎn)成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。將生銷(xiāo)量；生產(chǎn)成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。將生產(chǎn)與儲(chǔ)存問(wèn)題轉(zhuǎn)化為運(yùn)輸問(wèn)題，相關(guān)數(shù)據(jù)見(jiàn)表產(chǎn)與儲(chǔ)存問(wèn)題轉(zhuǎn)化為運(yùn)輸問(wèn)題，相關(guān)數(shù)據(jù)見(jiàn)表4 45 5。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型表表4 45 5 柴油機(jī)生產(chǎn)的相關(guān)數(shù)據(jù)柴

19、油機(jī)生產(chǎn)的相關(guān)數(shù)據(jù)1 12 23 34 4生產(chǎn)能力生產(chǎn)能力1 110.810.810.9510.9511.1011.1011.2511.2525252 211.1011.1011.2511.2511.4011.4035353 311.0011.0011.1511.1530304 411.3011.301010需求量需求量1010151525252020由表由表4 45 5可知，總產(chǎn)量（生產(chǎn)能力）為可知，總產(chǎn)量（生產(chǎn)能力）為25+35+30+10=10025+35+30+10=100，總銷(xiāo)量（需求量）為，總銷(xiāo)量（需求量）為10+15+25+20=7010+15+25+20=70，因此是，因此是產(chǎn)

20、大于銷(xiāo)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題。的運(yùn)輸問(wèn)題。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型該生產(chǎn)與該生產(chǎn)與儲(chǔ)存問(wèn)題儲(chǔ)存問(wèn)題（轉(zhuǎn)化為（轉(zhuǎn)化為產(chǎn)大于銷(xiāo)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)的運(yùn)輸問(wè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 xxxxxxxxxxxxxxxxx1424344

21、4 25200 ( ,1, 2,3, 4; )ijxxxxxijij 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型例例4.24.2的電子表格模型的電子表格模型 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型例例4.34.3 某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1A1、A2A2將物品運(yùn)往將物品運(yùn)往三個(gè)銷(xiāo)地三個(gè)銷(xiāo)地 B1 B1、B2B2、B3B3，各產(chǎn)地的產(chǎn)量、各銷(xiāo)，各產(chǎn)地的產(chǎn)量、各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物品的運(yùn)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物品的運(yùn)費(fèi)如

22、表費(fèi)如表4 46 6所示。問(wèn)應(yīng)如何調(diào)運(yùn)，可使得總所示。問(wè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)量A1A11313151512127878A2A21111292922224545銷(xiāo)量銷(xiāo)量535336366565（銷(xiāo)大于產(chǎn)）（銷(xiāo)大于產(chǎn)） 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型解：解：由表由表4 46 6知，總產(chǎn)量為知，總產(chǎn)量為78+45=12378+45=123，總銷(xiāo)量為，總銷(xiāo)量為53+36+65=15453+36+65=154

23、，銷(xiāo)大于產(chǎn)銷(xiāo)大于產(chǎn)( (供不應(yīng)求供不應(yīng)求) )。數(shù)學(xué)模型如下：。數(shù)學(xué)模型如下： 設(shè)設(shè)xij為產(chǎn)地為產(chǎn)地AiAi運(yùn)往銷(xiāo)地運(yùn)往銷(xiāo)地BjBj的物品數(shù)量的物品數(shù)量11121321222311121312122232112111222213233Min z 13151211292278 ()45 ()53 ()s.t. 36 ()65 ()0(1,2;1,2,3)ijxxxxxxxxxAxxxAxxBxxBxxBxij產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地銷(xiāo)地 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.2 3.2 運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型例例4.34.3的電子表格模型的電子表格模型 運(yùn)輸問(wèn)

24、題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.3 3.3 各種運(yùn)輸問(wèn)題變形的建模各種運(yùn)輸問(wèn)題變形的建?，F(xiàn)實(shí)生活中符合產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題每一個(gè)條件的情況很少。一現(xiàn)實(shí)生活中符合產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題每一個(gè)條件的情況很少。一個(gè)特征近似但其中的一個(gè)或者幾個(gè)特征卻并不符合產(chǎn)銷(xiāo)平衡運(yùn)個(gè)特征近似但其中的一個(gè)或者幾個(gè)特征卻并不符合產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題條件的運(yùn)輸問(wèn)題卻經(jīng)常出現(xiàn)。輸問(wèn)題條件的運(yùn)輸問(wè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ù)量

25、（而不是一個(gè)固定的數(shù)值, ,）。）。（2 2）總供應(yīng)小于總需求總供應(yīng)小于總需求。每一個(gè)需求量（銷(xiāo)量）代表了在其目。每一個(gè)需求量（銷(xiāo)量）代表了在其目的地中所接收到的最大數(shù)量（而不是一個(gè)固定的數(shù)值的地中所接收到的最大數(shù)量（而不是一個(gè)固定的數(shù)值, ,）。）。（3 3）一個(gè)目的地）一個(gè)目的地同時(shí)存在著最小需求和最大需求同時(shí)存在著最小需求和最大需求，于是所有在，于是所有在這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的（這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的（, ,）。）。（4 4）在配送中）在配送中不能使用不能使用特定的出發(fā)地特定的出發(fā)地目的地組合（目的地組合（xij=0=0）。）。（5 5）目標(biāo)是使與配送數(shù)量有關(guān)的）

26、目標(biāo)是使與配送數(shù)量有關(guān)的總利潤(rùn)最大總利潤(rùn)最大而不是使總成本最而不是使總成本最小。（小。（MinMin MaxMax） 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.3 3.3 各種運(yùn)輸問(wèn)題變形的建模各種運(yùn)輸問(wèn)題變形的建模例例4.44.4 某公司決定使用三個(gè)有生產(chǎn)余力的工廠進(jìn)行四種新產(chǎn)品的生產(chǎn)。某公司決定使用三個(gè)有生產(chǎn)余力的工廠進(jìn)行四種新產(chǎn)品的生產(chǎn)。每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任意種產(chǎn)品的數(shù)量來(lái)衡量（見(jiàn)表意種產(chǎn)品的數(shù)量來(lái)衡量（見(jiàn)表4 47 7的最右列）。而每種產(chǎn)品每天有一定的最右列）。而每種產(chǎn)品每天有一定的

27、需求量（見(jiàn)表的需求量（見(jiàn)表4 47 7的最后一行）。每家工廠都可以制造這些產(chǎn)品，除的最后一行）。每家工廠都可以制造這些產(chǎn)品，除了工廠了工廠2 2不能生產(chǎn)產(chǎn)品不能生產(chǎn)產(chǎn)品3 3以外。然而，每種產(chǎn)品在不同工廠中的單位成本以外。然而，每種產(chǎn)品在不同工廠中的單位成本是有差異的（如表是有差異的（如表4 47 7所示）。所示）。 現(xiàn)在需要決定的是在哪個(gè)工廠生產(chǎn)哪種產(chǎn)品，可使總成本最小?，F(xiàn)在需要決定的是在哪個(gè)工廠生產(chǎn)哪種產(chǎn)品，可使總成本最小。表表4 47 7 產(chǎn)品生產(chǎn)的有關(guān)數(shù)據(jù)產(chǎn)品生產(chǎn)的有關(guān)數(shù)據(jù)單位成本（元）單位成本（元）生產(chǎn)能力生產(chǎn)能力產(chǎn)品產(chǎn)品1 1產(chǎn)品產(chǎn)品2 2產(chǎn)品產(chǎn)品3 3產(chǎn)品產(chǎn)品4 4工廠工廠1 1

28、41412727282824247575工廠工廠2 24040292923237575工廠工廠3 337373030272721214545需求量需求量2020303030304040 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.3 3.3 各種運(yùn)輸問(wèn)題變形的建模各種運(yùn)輸問(wèn)題變形的建模解：解：指定工廠生產(chǎn)產(chǎn)品指定工廠生產(chǎn)產(chǎn)品可以看作運(yùn)輸問(wèn)題來(lái)求可以看作運(yùn)輸問(wèn)題來(lái)求解。本題中，工廠解。本題中，工廠2 2不能不能生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品3 3，這樣可以，這樣可以增增加約束條件加約束條件x230 0 ；并；并且，總供應(yīng)（且，總供應(yīng)（75+75+45=19575+75+45=195） 總需求總需求（20+30+

29、30+40=12020+30+30+40=120）。）。其數(shù)學(xué)模型如下：其數(shù)學(xué)模型如下： 設(shè)設(shè)xij為工廠為工廠i生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品j的數(shù)量的數(shù)量1112131421222431323334112131122232132333142434Min z41272824 4029 23 3730272120 (1)30 (2)30 (3)40 (s.t. xxxxxxxxxxxxxxxxxxxxxxx產(chǎn)品產(chǎn)品產(chǎn)品111213142122232431323334234)75 (1)75 (2)45 (3)00(1,2,3;1,2,3,4)ijxxxxxxxxxxxxxxij產(chǎn)品工廠工廠工廠 運(yùn)輸問(wèn)題運(yùn)輸

30、問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.3 3.3 各種運(yùn)輸問(wèn)題變形的建模各種運(yùn)輸問(wèn)題變形的建模例例4.44.4的電子表格模型的電子表格模型產(chǎn)品產(chǎn)品4 4分在分在2 2個(gè)工廠生產(chǎn)個(gè)工廠生產(chǎn) 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.3 3.3 各種運(yùn)輸問(wèn)題變形的建模各種運(yùn)輸問(wèn)題變形的建模例例4.54.5 某公司在某公司在3 3個(gè)工廠中專(zhuān)門(mén)生產(chǎn)一種產(chǎn)品。在未來(lái)的個(gè)工廠中專(zhuān)門(mén)生產(chǎn)一種產(chǎn)品。在未來(lái)的4 4個(gè)月中，有四個(gè)月中，有四個(gè)處于國(guó)內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能大量訂購(gòu)。顧客個(gè)處于國(guó)內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能大量訂購(gòu)。顧客1 1是公司是公司最好的顧客，所以他的全部訂購(gòu)量都應(yīng)該滿(mǎn)足；顧客最好

31、的顧客，所以他的全部訂購(gòu)量都應(yīng)該滿(mǎn)足；顧客2 2和顧客和顧客3 3也是公司很也是公司很重要的顧客，所以營(yíng)銷(xiāo)經(jīng)理認(rèn)為作為最低限度至少要滿(mǎn)足他們訂單的重要的顧客，所以營(yíng)銷(xiāo)經(jīng)理認(rèn)為作為最低限度至少要滿(mǎn)足他們訂單的1/31/3；對(duì)于顧客對(duì)于顧客4 4，銷(xiāo)售經(jīng)理認(rèn)為并不需要進(jìn)行特殊考慮。由于運(yùn)輸成本上的差異，銷(xiāo)售經(jīng)理認(rèn)為并不需要進(jìn)行特殊考慮。由于運(yùn)輸成本上的差異，銷(xiāo)售一個(gè)產(chǎn)品得到的凈利潤(rùn)也不同，很大程度上取決于哪個(gè)工廠供應(yīng)哪，銷(xiāo)售一個(gè)產(chǎn)品得到的凈利潤(rùn)也不同，很大程度上取決于哪個(gè)工廠供應(yīng)哪個(gè)顧客（見(jiàn)表個(gè)顧客（見(jiàn)表4 48 8）。問(wèn)應(yīng)）。問(wèn)應(yīng)向每一個(gè)顧客供應(yīng)多少貨物向每一個(gè)顧客供應(yīng)多少貨物，以使公司總利潤(rùn)，

32、以使公司總利潤(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)量7000700030003000200020000 0最大采購(gòu)量最大采購(gòu)量70007000900090006000600080008000 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.3 3.3 各種運(yùn)輸問(wèn)題變形的建

33、模各種運(yùn)輸問(wèn)題變形的建模解：解：該問(wèn)題要求滿(mǎn)足不該問(wèn)題要求滿(mǎ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ù)量111213142122232431323334111213142122232431323334Max z55424653 37183248 295951358000 (1)5000 (2)7000 (3)s.t. x

34、xxxxxxxxxxxxxxxxxxxxxxxx工廠工廠工廠1121311222321323331424347000 (1)30009000 (2)20006000 (3)8000 (4)0(1,2,3;1,2,3,4)ijxxxxxxxxxxxxij顧客顧客顧客顧客 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.3 3.3 各種運(yùn)輸問(wèn)題變形的建模各種運(yùn)輸問(wèn)題變形的建模例例4.54.5的電子表格模型的電子表格模型 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.4 3.4 運(yùn)輸問(wèn)題應(yīng)用舉例運(yùn)輸問(wèn)題應(yīng)用舉例例例4.64.6 某廠生產(chǎn)設(shè)備是以銷(xiāo)定產(chǎn)的。已知某廠生產(chǎn)設(shè)備是以銷(xiāo)定產(chǎn)的。已知1 16 6月份各月的

35、生產(chǎn)能力、月份各月的生產(chǎn)能力、合同銷(xiāo)量和單臺(tái)設(shè)備平均生產(chǎn)費(fèi)用，如表合同銷(xiāo)量和單臺(tái)設(shè)備平均生產(chǎn)費(fèi)用，如表4 49 9所示。所示。 已知上年末庫(kù)存已知上年末庫(kù)存103103臺(tái)。如果當(dāng)月生產(chǎn)出來(lái)的設(shè)備當(dāng)月不交貨，則臺(tái)。如果當(dāng)月生產(chǎn)出來(lái)的設(shè)備當(dāng)月不交貨，則需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本0.10.1萬(wàn)元，每臺(tái)設(shè)備每月的平均萬(wàn)元，每臺(tái)設(shè)備每月的平均倉(cāng)儲(chǔ)費(fèi)、維護(hù)費(fèi)為倉(cāng)儲(chǔ)費(fèi)、維護(hù)費(fèi)為0.20.2萬(wàn)元。萬(wàn)元。7 78 8月份為銷(xiāo)售淡季，全廠停產(chǎn)月份為銷(xiāo)售淡季，全廠停產(chǎn)1 1個(gè)月，個(gè)月，因此在因此在6 6月份完成銷(xiāo)售合同后還要留出庫(kù)存月份完成銷(xiāo)售合同后還要留出庫(kù)存8080臺(tái)。

36、加班生產(chǎn)設(shè)備每臺(tái)增臺(tái)。加班生產(chǎn)設(shè)備每臺(tái)增加成本加成本1 1萬(wàn)元。問(wèn)應(yīng)如何安排萬(wàn)元。問(wèn)應(yīng)如何安排1 16 6月份的生產(chǎn)，使總的生產(chǎn)（包括運(yùn)輸月份的生產(chǎn)，使總的生產(chǎn)（包括運(yùn)輸、倉(cāng)儲(chǔ)、維護(hù)）費(fèi)用最少？、倉(cāng)儲(chǔ)、維護(hù)）費(fèi)用最少？月份月份正常生產(chǎn)能力正常生產(chǎn)能力（臺(tái)）（臺(tái)）加班生產(chǎn)能力加班生產(chǎn)能力（臺(tái)）（臺(tái)）合同銷(xiāo)量合同銷(xiāo)量（臺(tái)）（臺(tái)）單臺(tái)費(fèi)用單臺(tái)費(fèi)用（萬(wàn)元）（萬(wàn)元）1 1月月6060101010410415152 2月月50501010757514143 3月月9090202011511513.513.54 4月月100100404016016013135 5月月10010040401031031313

37、6 6月月80804040707013.513.5 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.4 3.4 運(yùn)輸問(wèn)題應(yīng)用舉例運(yùn)輸問(wèn)題應(yīng)用舉例例例4.74.7 華中金剛石鋸片廠有兩條生產(chǎn)線，分別生產(chǎn)華中金剛石鋸片廠有兩條生產(chǎn)線，分別生產(chǎn)直徑直徑900-1800mm900-1800mm大鋸片基體大鋸片基體2000020000片，直徑片，直徑350-350-800mm800mm中小鋸片基體中小鋸片基體4000040000片。公司在全國(guó)有片。公司在全國(guó)有2525個(gè)銷(xiāo)個(gè)銷(xiāo)售網(wǎng)點(diǎn)，主要銷(xiāo)售區(qū)域集中在福建、廣東、廣西、售網(wǎng)點(diǎn)，主要銷(xiāo)售區(qū)域集中在福建、廣東、廣西、四川、山東四川、山東5 5個(gè)石材主產(chǎn)區(qū)。為完成總

38、廠的要求，個(gè)石材主產(chǎn)區(qū)。為完成總廠的要求，公司決定一方面拿出公司決定一方面拿出10%10%的產(chǎn)量穩(wěn)定與前期各個(gè)客的產(chǎn)量穩(wěn)定與前期各個(gè)客戶(hù)的聯(lián)系以保證將來(lái)的市場(chǎng)區(qū)域份額，另一方面，戶(hù)的聯(lián)系以保證將來(lái)的市場(chǎng)區(qū)域份額，另一方面，面臨如何將剩余的面臨如何將剩余的90%90%的產(chǎn)量合理分配給的產(chǎn)量合理分配給五個(gè)石材五個(gè)石材主產(chǎn)區(qū)和其他省區(qū)主產(chǎn)區(qū)和其他省區(qū)，以獲取最大的利潤(rùn)。各個(gè)銷(xiāo)售，以獲取最大的利潤(rùn)。各個(gè)銷(xiāo)售區(qū)的最低需求、銷(xiāo)售固定費(fèi)用、每片平均運(yùn)費(fèi)、每區(qū)的最低需求、銷(xiāo)售固定費(fèi)用、每片平均運(yùn)費(fèi)、每片從總廠庫(kù)房的購(gòu)進(jìn)價(jià)與當(dāng)?shù)氐匿N(xiāo)售價(jià)差貢獻(xiàn)等自片從總廠庫(kù)房的購(gòu)進(jìn)價(jià)與當(dāng)?shù)氐匿N(xiāo)售價(jià)差貢獻(xiàn)等自然情況見(jiàn)表然情況見(jiàn)表4

39、 41212。問(wèn)應(yīng)如何分配給各個(gè)銷(xiāo)售區(qū)，。問(wèn)應(yīng)如何分配給各個(gè)銷(xiāo)售區(qū)，才能使得總利潤(rùn)為最大？才能使得總利潤(rùn)為最大？ 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題表412 大鋸片和小鋸片的相關(guān)數(shù)據(jù)銷(xiāo)售銷(xiāo)售區(qū)域區(qū)域銷(xiāo)售銷(xiāo)售固定固定費(fèi)用費(fèi)用（萬(wàn)（萬(wàn)元）元）規(guī)格直徑規(guī)格直徑900mm900mm1800mm1800mm規(guī)格直徑規(guī)格直徑350mm350mm800mm800mm最低最低需求需求（片）（片）最高最高需求需求（片）（片）每片每片平均平均運(yùn)費(fèi)運(yùn)費(fèi)（元）（元）每片每片零售零售與出與出廠價(jià)廠價(jià)差差（元）（元）每片每片利潤(rùn)利潤(rùn)（元）（元）最低最低需求需求（片）（片）最高最高需求需求（片）（片）每片每片平均平均運(yùn)

40、費(fèi)運(yùn)費(fèi)（元）（元）每片每片零售零售與出與出廠價(jià)廠價(jià)差差（元）（元）每片每片利潤(rùn)利潤(rùn)（元）（元）福建福建212135003500800080008080350350270270750075002200022000222285856363廣東廣東101020002000600060006060300300240240450045002000020000151575756060廣西廣西9 925002500600060007575370370295295400040001500015000252585856060四川四川8 82500250060006000808038038030030050005

41、0002000020000252589896464山東山東7 720002000800080007878320320242242400040001800018000212180805959其他其他省區(qū)省區(qū)909020002000未作未作統(tǒng)計(jì)統(tǒng)計(jì)909035035026026040004000未作未作統(tǒng)計(jì)統(tǒng)計(jì)282885855757 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.5 3.5 指派問(wèn)題指派問(wèn)題u在現(xiàn)實(shí)生活中，經(jīng)常會(huì)遇到指派人員做某項(xiàng)在現(xiàn)實(shí)生活中，經(jīng)常會(huì)遇到指派人員做某項(xiàng)工作（任務(wù)）的情況。工作（任務(wù)）的情況。指派問(wèn)題指派問(wèn)題的許多應(yīng)用是的許多應(yīng)用是用來(lái)幫助管理人員解決如何為一項(xiàng)即將開(kāi)展

42、的用來(lái)幫助管理人員解決如何為一項(xiàng)即將開(kāi)展的工作指派人員的問(wèn)題。其他的一些應(yīng)用如為工工作指派人員的問(wèn)題。其他的一些應(yīng)用如為工作指派機(jī)器、設(shè)備或工廠等。作指派機(jī)器、設(shè)備或工廠等。u指派問(wèn)題也稱(chēng)指派問(wèn)題也稱(chēng)分配問(wèn)題分配問(wèn)題，主要研究人和工作，主要研究人和工作（任務(wù)）間如何匹配，以使所有工作完成的效（任務(wù)）間如何匹配，以使所有工作完成的效率實(shí)現(xiàn)最優(yōu)化。形式上，指派問(wèn)題給定了一系率實(shí)現(xiàn)最優(yōu)化。形式上，指派問(wèn)題給定了一系列所要完成的工作以及一系列完成工作的人員列所要完成的工作以及一系列完成工作的人員，所需要解決的問(wèn)題就是要確定出指派哪個(gè)人，所需要解決的問(wèn)題就是要確定出指派哪個(gè)人去完成哪項(xiàng)工作。去完成哪項(xiàng)工

43、作。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.5 3.5 指派問(wèn)題指派問(wèn)題u指派問(wèn)題的假設(shè)：指派問(wèn)題的假設(shè)：（1 1）人的數(shù)量和工作的數(shù)量）人的數(shù)量和工作的數(shù)量相等相等；（2 2）每個(gè)人）每個(gè)人只能完成一項(xiàng)只能完成一項(xiàng)工作；工作；（3 3）每項(xiàng)工作）每項(xiàng)工作只能由一個(gè)人只能由一個(gè)人來(lái)完成；來(lái)完成；（4 4）每個(gè)人和每項(xiàng)工作的組合都會(huì)有）每個(gè)人和每項(xiàng)工作的組合都會(huì)有一個(gè)相關(guān)的成本（一個(gè)相關(guān)的成本（單位成本單位成本）；）；（5 5）目標(biāo)是要確定如何指派才能使）目標(biāo)是要確定如何指派才能使總總成本最小成本最小。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.5 3.5 指派問(wèn)題指派問(wèn)題u設(shè)決策變量設(shè)決策

44、變量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平衡指派問(wèn)題的數(shù)學(xué)模型為平衡指派問(wèn)題的數(shù)學(xué)模型為1111 ()Min z1 (1,2, )s.t. 1 (1,2, )0 ( ,1,2, ) nnijijijnijjnijiijijc xxinxjnxi jn(第 人只能做一項(xiàng)工作)(第 項(xiàng)工作只能一人做)非負(fù) LLL 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.5 3.5 指派問(wèn)題指派問(wèn)題u需要說(shuō)明的是：需要說(shuō)明的是：指派問(wèn)題指派問(wèn)題實(shí)際上是一種實(shí)際上是一種特殊特殊的

45、運(yùn)輸問(wèn)題的運(yùn)輸問(wèn)題。其中出發(fā)地是人，目的地是工作。其中出發(fā)地是人，目的地是工作。只不過(guò)，每一個(gè)出發(fā)地的。只不過(guò)，每一個(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)輸問(wèn)題有由于運(yùn)輸問(wèn)題有“整數(shù)解性質(zhì)整數(shù)解性質(zhì)”，因此，沒(méi)有，因此，沒(méi)有必要加上所有決策變量都是必要加上所有決策變量都是0-10-1變量變量的約束。的約束。u指派問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，有一指派問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，有一種快捷的求解方法：種快捷的求解方法：匈牙

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

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

48、運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.5 3.5 指派問(wèn)題指派問(wèn)題解解：該問(wèn)題是一個(gè)：該問(wèn)題是一個(gè)典型的指派問(wèn)題典型的指派問(wèn)題。單位成本單位成本為每個(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è)人來(lái)完成個(gè)人來(lái)完成總?cè)藬?shù)（總?cè)藬?shù)（4 4人）和總?cè)蝿?wù)數(shù)（人）和總?cè)蝿?wù)數(shù)（4 4項(xiàng)）項(xiàng)）相等相等 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.5 3.5 指派問(wèn)題指派問(wèn)題數(shù)學(xué)模型

49、：數(shù)學(xué)模型：設(shè)設(shè)xij為指派人員為指派人員i去做工作去做工作j（i，j1,2,3,4)1,2,3,4) 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 2

50、4 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) 工 作 ）（ 小 劉 要 完 成 一 項(xiàng) 工 作 ）（ 工 作 A 要 有 1 人 完 成 ）（ 工 作 B 要 有 1 人 完 成 ）（ 工 作 C 要 有 1 人 完 成 ）（ 工 作要 有 1 人0 ( ,1, 2 , 3 , 4 ) ijxij完 成 ）（ 非 負(fù) ） 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.5 3.5 指派

51、問(wèn)題指派問(wèn)題電子表格模型電子表格模型 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.6 3.6 各種指派問(wèn)題變形的建模各種指派問(wèn)題變形的建模經(jīng)常會(huì)遇到指派問(wèn)題的經(jīng)常會(huì)遇到指派問(wèn)題的變形變形，之所以稱(chēng)它們?yōu)樽冃?，之所以稱(chēng)它們?yōu)樽冃?，是因?yàn)樗鼈兌疾粷M(mǎn)足平衡指派問(wèn)題所有假設(shè)之中的一是因?yàn)樗鼈兌疾粷M(mǎn)足平衡指派問(wèn)題所有假設(shè)之中的一個(gè)或者多個(gè)。一般考慮下面的一些特征：個(gè)或者多個(gè)。一般考慮下面的一些特征：（1 1）有些人并）有些人并不能不能進(jìn)行某項(xiàng)工作（相應(yīng)的進(jìn)行某項(xiàng)工作（相應(yīng)的xij0 0）; ;（2 2）雖然每個(gè)人完成一項(xiàng)任務(wù)，但是任務(wù)比人多）雖然每個(gè)人完成一項(xiàng)任務(wù)，但是任務(wù)比人多( (人少事多人少事多);

52、);（3 3）雖然每一項(xiàng)任務(wù)只由一個(gè)人完成，但是人比任務(wù)多（）雖然每一項(xiàng)任務(wù)只由一個(gè)人完成，但是人比任務(wù)多（人人多事少多事少）；）；（4 4）某人可以同時(shí)被指派給多個(gè)任務(wù)（）某人可以同時(shí)被指派給多個(gè)任務(wù)（一人可做幾件事一人可做幾件事）；）；（5 5）某事可以由多人共同完成（）某事可以由多人共同完成（一事可由多人完成一事可由多人完成） ；（6 6）目標(biāo)是與指派有關(guān)的）目標(biāo)是與指派有關(guān)的總利潤(rùn)最大總利潤(rùn)最大而不是使總成本最??；而不是使總成本最小；（7 7）實(shí)際需要完成任務(wù)數(shù)不超過(guò)總?cè)藬?shù)也不超過(guò)總?cè)蝿?wù)數(shù)。）實(shí)際需要完成任務(wù)數(shù)不超過(guò)總?cè)藬?shù)也不超過(guò)總?cè)蝿?wù)數(shù)。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.6

53、 3.6 各種指派問(wèn)題變形的建模各種指派問(wèn)題變形的建模例例4.94.9 題目見(jiàn)例題目見(jiàn)例4.44.4，即某公司需要安排三，即某公司需要安排三個(gè)工廠來(lái)生產(chǎn)四種新產(chǎn)品，相關(guān)的數(shù)據(jù)在表個(gè)工廠來(lái)生產(chǎn)四種新產(chǎn)品，相關(guān)的數(shù)據(jù)在表4 47 7中已經(jīng)給出。在例中已經(jīng)給出。在例4.44.4中，允許產(chǎn)品生中，允許產(chǎn)品生產(chǎn)分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的產(chǎn)分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的隱性成本（包括額外的設(shè)置、配送和管理成隱性成本（包括額外的設(shè)置、配送和管理成本等）。因此，管理人員決定在本等）。因此，管理人員決定在禁止產(chǎn)品生禁止產(chǎn)品生產(chǎn)分解產(chǎn)分解發(fā)生的情況下對(duì)問(wèn)題進(jìn)行分析。發(fā)生的情況下對(duì)問(wèn)題進(jìn)行分析。新問(wèn)

54、題描述為：已知如表新問(wèn)題描述為：已知如表4 47 7所示的數(shù)所示的數(shù)據(jù)，問(wèn)如何把每一個(gè)工廠指派給至少一個(gè)新?lián)瑔?wèn)如何把每一個(gè)工廠指派給至少一個(gè)新產(chǎn)品（每一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)），產(chǎn)品（每一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)），使總成本達(dá)到最??？使總成本達(dá)到最?。?運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.6 3.6 各種指派問(wèn)題變形的建模各種指派問(wèn)題變形的建模解：解： 該問(wèn)題可視為該問(wèn)題可視為指派工廠生產(chǎn)產(chǎn)品問(wèn)題指派工廠生產(chǎn)產(chǎn)品問(wèn)題，工，工廠可以看作指派問(wèn)題中的人，產(chǎn)品則可以看作廠可以看作指派問(wèn)題中的人，產(chǎn)品則可以看作需要完成的工作（任務(wù)）。由于有四種產(chǎn)品和需要完成的工作（任務(wù)）。由于有四種產(chǎn)品和三

55、個(gè)工廠，所以就有兩個(gè)工廠各只能生產(chǎn)一種三個(gè)工廠，所以就有兩個(gè)工廠各只能生產(chǎn)一種新產(chǎn)品，第三個(gè)工廠生產(chǎn)兩種新產(chǎn)品。只有工新產(chǎn)品，第三個(gè)工廠生產(chǎn)兩種新產(chǎn)品。只有工廠廠1 1和工廠和工廠2 2有生產(chǎn)兩種產(chǎn)品的能力。有生產(chǎn)兩種產(chǎn)品的能力。這里涉及如何把這里涉及如何把運(yùn)輸問(wèn)題轉(zhuǎn)換為指派問(wèn)題運(yùn)輸問(wèn)題轉(zhuǎn)換為指派問(wèn)題，關(guān)，關(guān)鍵所在是鍵所在是數(shù)據(jù)轉(zhuǎn)換數(shù)據(jù)轉(zhuǎn)換。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.6 3.6 各種指派問(wèn)題變形的建模各種指派問(wèn)題變形的建模數(shù)據(jù)轉(zhuǎn)換：數(shù)據(jù)轉(zhuǎn)換：（1 1）單位指派成本單位指派成本: : 原來(lái)的單位成本轉(zhuǎn)換成原來(lái)的單位成本轉(zhuǎn)換成整批整批成本（單位成本成本（單位成本需求量），即單位指

56、派成本需求量），即單位指派成本為為每個(gè)工廠生產(chǎn)每種產(chǎn)品的成本每個(gè)工廠生產(chǎn)每種產(chǎn)品的成本。（2 2）供應(yīng)量和需求量的轉(zhuǎn)換問(wèn)題供應(yīng)量和需求量的轉(zhuǎn)換問(wèn)題：三個(gè)工廠生產(chǎn)：三個(gè)工廠生產(chǎn)四種產(chǎn)品，但一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)，根四種產(chǎn)品，但一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)，根據(jù)生產(chǎn)能力，工廠據(jù)生產(chǎn)能力，工廠3 3只能生產(chǎn)一種產(chǎn)品（供應(yīng)量為只能生產(chǎn)一種產(chǎn)品（供應(yīng)量為1 1），而工廠），而工廠1 1和工廠和工廠2 2可以生產(chǎn)可以生產(chǎn)2 2種產(chǎn)品（供應(yīng)量種產(chǎn)品（供應(yīng)量為為2 2），而產(chǎn)品的需求量為），而產(chǎn)品的需求量為1 1。還有。還有“總供應(yīng)（總供應(yīng)（2+2+1=52+2+1=5） 總需求（總需求（1+1+1+1=4

57、1+1+1+1=4）”, , 為人多事少為人多事少的指派問(wèn)題的指派問(wèn)題。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.6 3.6 各種指派問(wèn)題變形的建模各種指派問(wèn)題變形的建模數(shù)學(xué)模型：數(shù)學(xué)模型：設(shè)設(shè)xij為指派工廠為指派工廠i生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品j（i=1,2,3;=1,2,3;j=1,2,3,4)=1,2,3,4) 1 11 21 31 42 12 22 43 13 23 33 41 11 21 31 42 12 22 32 43 13 23 33 41M in z4 12 02 73 02 83 02 44 04 02 02 93 0 2 34 03 72 03 03 02 73 02 14 0

58、2 (1 )2 (2 )1 (3 )s .t. xxxxxxxxxxxxxxxxxxxxxxxx工 廠 工 廠工 廠12 13 11 22 23 21 32 33 31 42 43 42 31 (1 )1 (2 )1 (3 )1 (4 )= 00 (1, 2 , 3;1, 2 , 3 , 4 )ijxxxxxxxxxxxxxij產(chǎn) 品產(chǎn) 品產(chǎn) 品產(chǎn) 品 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.6 3.6 各種指派問(wèn)題變形的建模各種指派問(wèn)題變形的建模電子表格模型電子表格模型 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.6 3.6 各種指派問(wèn)題變形的建模各種指派問(wèn)題變形的建模例例4.104.10

59、一家制藥公司，為了提升企業(yè)的競(jìng)爭(zhēng)一家制藥公司，為了提升企業(yè)的競(jìng)爭(zhēng)力，決定加大科研力度。在研究了市場(chǎng)的需要力，決定加大科研力度。在研究了市場(chǎng)的需要，分析了當(dāng)前藥物的不足并且拜會(huì)了大量對(duì)有，分析了當(dāng)前藥物的不足并且拜會(huì)了大量對(duì)有良好前景的醫(yī)藥領(lǐng)域進(jìn)行研究的科學(xué)家之后，良好前景的醫(yī)藥領(lǐng)域進(jìn)行研究的科學(xué)家之后，決定由五位科學(xué)家開(kāi)發(fā)五個(gè)項(xiàng)目。為了保證這決定由五位科學(xué)家開(kāi)發(fā)五個(gè)項(xiàng)目。為了保證這些科學(xué)家都能夠到他們感興趣的項(xiàng)目中去，為些科學(xué)家都能夠到他們感興趣的項(xiàng)目中去，為此建立了一個(gè)此建立了一個(gè)投標(biāo)系統(tǒng)投標(biāo)系統(tǒng)。這五位科學(xué)家每個(gè)人。這五位科學(xué)家每個(gè)人都有都有10001000點(diǎn)的投標(biāo)點(diǎn)。他們向每一個(gè)項(xiàng)目投標(biāo)

60、點(diǎn)的投標(biāo)點(diǎn)。他們向每一個(gè)項(xiàng)目投標(biāo)，并且把較多的投標(biāo)點(diǎn)投向自己最感興趣的項(xiàng)，并且把較多的投標(biāo)點(diǎn)投向自己最感興趣的項(xiàng)目中。表目中。表4 41515顯示了這顯示了這5 5位科學(xué)家進(jìn)行投標(biāo)的位科學(xué)家進(jìn)行投標(biāo)的情況。情況。 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 和指派問(wèn)題和指派問(wèn)題3.6 3.6 各種指派問(wèn)題變形的建模各種指派問(wèn)題變形的建模表表4 415 15 科學(xué)家項(xiàng)目投標(biāo)表科學(xué)家項(xiàng)目投標(biāo)表投投標(biāo)標(biāo)點(diǎn)點(diǎn)a a項(xiàng)項(xiàng)目目b b項(xiàng)項(xiàng)目目c c項(xiàng)項(xiàng)目目d d項(xiàng)項(xiàng)目目e e項(xiàng)項(xiàng)目目李李爾爾博博士士10100 040400 020200 020200 010100 0朱朱諾諾博博士士0 020200 080800 00 00 0 運(yùn)