實(shí)用運(yùn)籌學(xué) 第4章 運(yùn)輸問題和指派問題

1、第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 實(shí)用運(yùn)籌學(xué)實(shí)用運(yùn)籌學(xué) 運(yùn)用運(yùn)用ExcelExcel建模和求解建模和求解 第第4 4章章 運(yùn)輸問題和指派問題運(yùn)輸問題和指派問題 The Transportation The Transportation and Assignment Problemsand Assignment Problems 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 本章內(nèi)容要點(diǎn)本章內(nèi)容要點(diǎn) 運(yùn)輸問題運(yùn)輸問題的基本概念及其的基本概念及其 各種變形的建模與應(yīng)用各種變形的建模與應(yīng)用 指派問題指派問

2、題的基本概念及其的基本概念及其 各種變形的建模與應(yīng)用各種變形的建模與應(yīng)用 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 本章節(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 各種變形的指派問題建模各種變形的指派問題建模 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyri

3、ght 本章主要內(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章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.1 4.1 運(yùn)輸問題基本概念運(yùn)輸問題基本概念 u 運(yùn)輸問題最初起源于人們?cè)谌粘Ｉ钪邪堰\(yùn)輸問題最初起源于人們?cè)谌粘Ｉ钪邪?某些物品或人們自身從一些地方轉(zhuǎn)移到另某些物品或人們自身從一些地方轉(zhuǎn)移到另 一些地方，要

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

5、有資源的最優(yōu)化配置實(shí)現(xiàn)現(xiàn)有資源的最優(yōu)化配置。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.1 4.1 運(yùn)輸問題基本概念運(yùn)輸問題基本概念 u一般的運(yùn)輸問題就是解決如何把某種產(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)用最小的方案。 u平衡運(yùn)輸問題平衡運(yùn)輸問題的條件：的條件：

6、 1.1.明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應(yīng)量（產(chǎn)量）、需明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應(yīng)量（產(chǎn)量）、需 求量（銷量）和單位成本。求量（銷量）和單位成本。 2.2.需求假設(shè)：每一個(gè)出發(fā)地都有一個(gè)固定的供應(yīng)量，所有的供應(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è)：從任何一

7、個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送成 本與所配送的數(shù)量成線性比例關(guān)系，因此成本就等于配送的單本與所配送的數(shù)量成線性比例關(guān)系，因此成本就等于配送的單 位成本乘以所配送的數(shù)量（目標(biāo)函數(shù)是線性的）。位成本乘以所配送的數(shù)量（目標(biāo)函數(shù)是線性的）。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.1 4.1 運(yùn)輸問題基本概念運(yùn)輸問題基本概念 u例例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)品

8、分別運(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-14-1所示。問該公司應(yīng)如何調(diào)運(yùn)這所示。問該公司應(yīng)如何調(diào)運(yùn)這 些產(chǎn)品，在滿足各銷售點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)些產(chǎn)品，在滿足各銷售點(diǎn)的需要量的前提下，使總運(yùn)費(fèi) 最少？最少？ 表表4-1 4-1 各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)（元各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)（元/ /噸）噸） B1B1B2B2B3B3B4B4產(chǎn)量（噸）產(chǎn)量（噸） A1A

9、13 311113 310107 7 A2A21 19 92 28 84 4 A3A37 74 410105 59 9 銷量（噸）銷量（噸）3 36 65 56 6 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.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, ,m）和和n個(gè)銷地個(gè)銷地 B Bj j（j1,2,1,2, ,n）的運(yùn)輸問題的數(shù)學(xué)模型為的運(yùn)輸問題的數(shù)學(xué)模型為 11 1 1 () () M in

10、(1, 2 ,) s.t. (1, 2 ,) 0 (1, 2 ,; 1, 2 ,) mn ijij ij n iji j m ijj i ij zcx xaim xbjn ximjn 產(chǎn) 量 約 束 銷 量 約 束 L L LL 11 mn ij ij ab 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.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è)；四

11、個(gè) 銷地銷地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)最小 11121314 21222324 31323334 Min z311 310 9 2 8 7410 5 x

12、xxx xxxx xxxx 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.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ù) 11121314 21222324 31323334 11121314 21222324 31323334 112131 122232 Min z311 310 9

13、2 8 7 410 5 7 4 9 3 s.t. 6 xxxx xxxx xxxx xxxx xxxx xxxx xxx xxx 132333 142434 5 6 0(1,2,3;1,2,3,4) ij xxx xxx xij 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.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ī)劃求解”還是采用還是采用

14、“ 單純形法單純形法”來求解。來求解。 u例例4.14.1的電子表格模型的電子表格模型 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型 u 需要注意的是：運(yùn)輸問題有這樣一個(gè)性需要注意的是：運(yùn)輸問題有這樣一個(gè)性 質(zhì)（質(zhì)（整數(shù)解性質(zhì)整數(shù)解性質(zhì)），只要它的），只要它的供應(yīng)量供應(yīng)量和和 需求量需求量都是都是整數(shù)整數(shù)，任何有可行解的運(yùn)輸，任何有可行解的運(yùn)輸 問題必然有所有決策變量都是問題必然有所有決策變量都是整數(shù)的最整數(shù)的最 優(yōu)解優(yōu)解。因此，沒有必要加上所有變量都。因此，沒有必要加上所有

15、變量都 是整數(shù)的約束條件。是整數(shù)的約束條件。 u 由于運(yùn)輸量經(jīng)常以卡車、集裝箱等為單由于運(yùn)輸量經(jīng)常以卡車、集裝箱等為單 位，如果卡車不能裝滿的話，就很不經(jīng)位，如果卡車不能裝滿的話，就很不經(jīng) 濟(jì)了。整數(shù)解性質(zhì)就避免了運(yùn)輸量（運(yùn)濟(jì)了。整數(shù)解性質(zhì)就避免了運(yùn)輸量（運(yùn) 輸方案）為小數(shù)的麻煩。輸方案）為小數(shù)的麻煩。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 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é)模型 （以滿足小的銷量為準(zhǔn)以滿足小的銷量為準(zhǔn)

16、） 11 1 1 () () Min z (1,2,) s.t. (1,2, ) 0 (1,2,;1,2, ) mn iji j ij n iji j m ijj i ij c x xaim xbjn xim jn 產(chǎn)量約束 銷量約束 L L LL 11 mn ij ij ab 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.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)） 11 1 1 () (

17、) Min (1,2,) s.t. (1,2, ) 0 (1,2,;1,2, ) mn iji j ij n iji j m ijj i ij zc x xaim xbjn xim jn 產(chǎn)量約束 銷量約束 L L LL 11 mn ij ij ab 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yù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ī)格的柴

18、油機(jī)。已知該廠 各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如表各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如表4-44-4 所示。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨的，每臺(tái)所示。如果生產(chǎn)出來的柴油機(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-4 4-4 各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本 季度季度生產(chǎn)能力（臺(tái)）生產(chǎn)能力（臺(tái)）單位成本（萬元）

19、單位成本（萬元） 1 1252510.810.8 2 2353511.111.1 3 3303011.011.0 4 4101011.311.3 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型 解：解：這是一個(gè)這是一個(gè)生產(chǎn)與儲(chǔ)存（庫(kù)存）問題生產(chǎn)與儲(chǔ)存（庫(kù)存）問題，除了采用第，除了采用第 3 3章的方法外，還可以轉(zhuǎn)化為章的方法外，還可以轉(zhuǎn)化為運(yùn)輸問題運(yùn)輸問題來做。來做。 由于每個(gè)季度生產(chǎn)出來的柴油機(jī)不一定當(dāng)季交貨，由于每個(gè)季度生產(chǎn)出來的柴油機(jī)不一定當(dāng)季交貨， 所以設(shè)所以設(shè)xij為

20、第為第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)成本+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è)銷售點(diǎn)的個(gè)銷售點(diǎn)的 銷量；生產(chǎn)成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。將生銷量；生產(chǎn)成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。將生 產(chǎn)與儲(chǔ)

21、存問題轉(zhuǎn)化為運(yùn)輸問題，相關(guān)數(shù)據(jù)見表產(chǎn)與儲(chǔ)存問題轉(zhuǎn)化為運(yùn)輸問題，相關(guān)數(shù)據(jù)見表4-54-5。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型 表表4-5 4-5 柴油機(jī)生產(chǎn)的相關(guān)數(shù)據(jù)柴油機(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.252525 2 211.1011.1011.2511.2511.4011.403535 3 311.0011.0011.1511.153030 4 411.30

22、11.301010 需求量需求量1010151525252020 由表由表4-54-5可知，總產(chǎn)量（生產(chǎn)能力）為可知，總產(chǎn)量（生產(chǎn)能力）為 25+35+30+10=10025+35+30+10=100，總銷量（需求量）為，總銷量（需求量）為 10+15+25+20=7010+15+25+20=70，因此是，因此是產(chǎn)大于銷產(chǎn)大于銷的運(yùn)輸問題。的運(yùn)輸問題。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.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)輸

23、問的運(yùn)輸問 題）的數(shù)題）的數(shù) 學(xué)模型為學(xué)模型為 11121314 222324 3334 M in z10.8010.9511.1011.25 11.1011.2511.40 11.0011.15 xxxx xxx xx 44 11121314 222324 3334 44 11 1222 132333 11.30 25 35 30 10 s.t. 10 15 x xxxx xxx xx x x xx xxx 14243444 25 20 0 ( ,1, 2,3, 4; ) ij xxxx xijij 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.

24、2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型 例例4.24.2的電子表格模型的電子表格模型 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.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-64-6所示。問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)所

25、示。問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn) 輸費(fèi)最??？輸費(fèi)最??？ 表表4-6 4-6 例例4.34.3的運(yùn)輸費(fèi)用表的運(yùn)輸費(fèi)用表 B1B1B2B2B3B3產(chǎn)量產(chǎn)量 A1A11313151512127878 A2A21111292922224545 銷量銷量535336366565（銷大于產(chǎn)）（銷大于產(chǎn)） 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.2 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型 解：解：由表由表4-64-6知，總產(chǎn)量為知，總產(chǎn)量為78+45=12378+45=123，總銷量為，總銷量為 53+36+65=15453+36

26、+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ù)量 111213212223 1112131 2122232 11211 12222 13233 Min z 131512112922 78 () 45 () 53 () s.t. 36 () 65 () 0(1,2;1,2,3) ij xxxxxx xxxA xxxA xxB xxB xxB xij 產(chǎn)地 產(chǎn)地 銷地 銷地 銷地 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.2 4.

27、2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題數(shù)學(xué)模型和電子表格模型 例例4.34.3的電子表格模型的電子表格模型 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.3 4.3 各種變形的運(yùn)輸問題建模各種變形的運(yùn)輸問題建模 現(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) 輸問題條件的運(yùn)輸問題卻經(jīng)常出現(xiàn)。輸問題條件的運(yùn)輸問題卻經(jīng)常出現(xiàn)。 下面是要討論的一些特征：下面是要討論的一些特征： （

28、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í)存在著最小需求和最大需求，于是所有在，于是所有在 這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的（這兩個(gè)數(shù)值之

29、間的數(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章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.3 4.3 各種變形的運(yùn)輸問題建模各種變形的運(yùn)輸問題建模 例例4.44.4 某公司決定使用三個(gè)有生產(chǎn)余力的工廠進(jìn)行四種新產(chǎn)品的生產(chǎn)。某公司決定使用三個(gè)有生產(chǎn)余力的工廠進(jìn)行四種新產(chǎn)品的生產(chǎn)。 每單位

30、產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任 意種產(chǎn)品的數(shù)量來衡量（見表意種產(chǎn)品的數(shù)量來衡量（見表4-74-7的最右列）。而每種產(chǎn)品每天有一定的最右列）。而每種產(chǎn)品每天有一定 的需求量（見表的需求量（見表4-74-7的最后一行）。每家工廠都可以制造這些產(chǎn)品，除的最后一行）。每家工廠都可以制造這些產(chǎn)品，除 了工廠了工廠2 2不能生產(chǎn)產(chǎn)品不能生產(chǎn)產(chǎn)品3 3以外。然而，每種產(chǎn)品在不同工廠中的單位成本以外。然而，每種產(chǎn)品在不同工廠中的單位成本 是有差異的（如表是有差異的（如表4-74-7所示）。所示）。 現(xiàn)在需要決定的是在哪個(gè)工

31、廠生產(chǎn)哪種產(chǎn)品，可使總成本最小?，F(xiàn)在需要決定的是在哪個(gè)工廠生產(chǎn)哪種產(chǎn)品，可使總成本最小。 表表4-7 4-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 141412727282824247575 工廠工廠2 24040292923237575 工廠工廠3 337373030272721214545 需求量需求量2020303030304040 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.3 4.3 各種變形的運(yùn)輸問題建模各種變形的運(yùn)輸

32、問題建模 解：解：指定工廠生產(chǎn)產(chǎn)品指定工廠生產(chǎn)產(chǎn)品 可以看作運(yùn)輸問題來求可以看作運(yùn)輸問題來求 解。本題中，工廠解。本題中，工廠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+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ù)量 11121314 212224 31323334 112131 122232 132333 142434 Mi

33、n z41272824 4029 23 37302721 20 (1) 30 (2) 30 (3) 40 ( s.t. xxxx xxx xxxx xxx xxx xxx xxx 產(chǎn)品 產(chǎn)品 產(chǎn)品 11121314 21222324 31323334 23 4) 75 (1) 75 (2) 45 (3) 0 0(1,2,3;1,2,3,4) ij xxxx xxxx xxxx x xij 產(chǎn)品 工廠 工廠 工廠 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.3 4.3 各種變形的運(yùn)輸問題建模各種變形的運(yùn)輸問題建模 例例4.44.4的電子表格模型的電

34、子表格模型產(chǎn)品產(chǎn)品4 4分在分在2 2個(gè)工廠生產(chǎn)個(gè)工廠生產(chǎn) 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 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è)處于國(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

35、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è)工廠的差異，銷售一個(gè)產(chǎn)品得到的凈利潤(rùn)也不同，很大程度上取決于哪個(gè)工廠 供應(yīng)哪個(gè)顧客（見表供應(yīng)哪個(gè)顧客（見表4-84-8）。問）。問應(yīng)向每一個(gè)顧客供應(yīng)多少貨物應(yīng)向每一個(gè)顧客供應(yīng)多少貨物，以使公司，以使公司 總利潤(rùn)最大？總利潤(rùn)最大？ 表表4-8 4-8 工廠

36、供應(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 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.3 4.3 各

37、種變形的運(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ù)量 11121314 21222324 31323334 11121314 21222324 31323334 Max z55424653 37183248 29595135 8000

38、(1) 5000 (2) 7000 (3) s.t. xxxx xxxx xxxx xxxx xxxx xxxx x 工廠 工廠 工廠 112131 122232 132333 142434 7000 (1) 30009000 (2) 20006000 (3) 8000 (4) 0(1,2,3;1,2,3,4) ij xx xxx xxx xxx xij 顧客 顧客 顧客 顧客 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.3 4.3 各種變形的運(yùn)輸問題建模各種變形的運(yùn)輸問題建模 例例4.54.5的電子表格模型的電子表格模型 第第4章章 運(yùn)輸問題運(yùn)

39、輸問題 和指派問題和指派問題 Desence copyright 4.4 4.4 運(yùn)輸問題應(yīng)用舉例運(yùn)輸問題應(yīng)用舉例 例例4.64.6 某廠生產(chǎn)設(shè)備是以銷定產(chǎn)的。已知某廠生產(chǎn)設(shè)備是以銷定產(chǎn)的。已知1 16 6月份各月的生產(chǎn)能力、月份各月的生產(chǎn)能力、 合同銷量和單臺(tái)設(shè)備平均生產(chǎn)費(fèi)用，如表合同銷量和單臺(tái)設(shè)備平均生產(chǎn)費(fèi)用，如表4-94-9所示。所示。 已知上年末庫(kù)存已知上年末庫(kù)存103103臺(tái)。如果當(dāng)月生產(chǎn)出來的設(shè)備當(dāng)月不交貨，則臺(tái)。如果當(dāng)月生產(chǎn)出來的設(shè)備當(dāng)月不交貨，則 需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本0.10.1萬元，每臺(tái)設(shè)備每月的平均萬元，每臺(tái)設(shè)備每月的平均 倉(cāng)

40、儲(chǔ)費(fèi)、維護(hù)費(fèi)為倉(cāng)儲(chǔ)費(fèi)、維護(hù)費(fèi)為0.20.2萬元。萬元。7 78 8月份為銷售淡季，全廠停產(chǎn)月份為銷售淡季，全廠停產(chǎn)1 1個(gè)月，個(gè)月， 因此在因此在6 6月份完成銷售合同后還要留出庫(kù)存月份完成銷售合同后還要留出庫(kù)存8080臺(tái)。加班生產(chǎn)設(shè)備每臺(tái)增臺(tái)。加班生產(chǎn)設(shè)備每臺(tái)增 加成本加成本1 1萬元。問應(yīng)如何安排萬元。問應(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)） 合同銷量合同銷量 （臺(tái)）（臺(tái)） 單臺(tái)費(fèi)用單臺(tái)費(fèi)用 （萬元）（萬

41、元） 1 1月月606010101041041515 2 2月月5050101075751414 3 3月月9090202011511513.513.5 4 4月月10010040401601601313 5 5月月10010040401031031313 6 6月月80804040707013.513.5 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.4 4.4 運(yùn)輸問題應(yīng)用舉例運(yùn)輸問題應(yīng)用舉例 解：解：這是一個(gè)生產(chǎn)與儲(chǔ)存問題，但可以轉(zhuǎn)化為運(yùn)這是一個(gè)生產(chǎn)與儲(chǔ)存問題，但可以轉(zhuǎn)化為運(yùn) 輸問題來做。輸問題來做。 （是否可以采用第（是否可以采用第3 3章

42、的方法做？同學(xué)們可以試章的方法做？同學(xué)們可以試 試，然后進(jìn)行比較）試，然后進(jìn)行比較）生產(chǎn)方案不變，但總費(fèi)用為：生產(chǎn)方案不變，但總費(fèi)用為：8329.78329.7萬元萬元 u根據(jù)已知條件可以列出生產(chǎn)能力（正常生產(chǎn)能根據(jù)已知條件可以列出生產(chǎn)能力（正常生產(chǎn)能 力和加班生產(chǎn)能力）和銷量以及運(yùn)價(jià)表（力和加班生產(chǎn)能力）和銷量以及運(yùn)價(jià)表（P120P120） u數(shù)學(xué)模型數(shù)學(xué)模型P120P120121121 u電子表格模型電子表格模型P122P122 u求解結(jié)果求解結(jié)果P123P123 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.4 4.4 運(yùn)輸問題應(yīng)用舉例運(yùn)輸問

43、題應(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è)銷個(gè)銷 售網(wǎng)點(diǎn)，主要銷售區(qū)域集中在福建、廣東、廣西、售網(wǎng)點(diǎn)，主要銷售區(qū)域集中在福建、廣東、廣西、 四川、山東四川、山東5 5個(gè)石材主產(chǎn)區(qū)。為完成總廠的要求，個(gè)石材主產(chǎn)區(qū)。為完成總廠的要求， 公司決定一方面拿出公司決定一方面拿出10%10%的產(chǎn)量穩(wěn)定與前期各個(gè)客的產(chǎn)

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

45、利潤(rùn)為最大？ 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.4 4.4 運(yùn)輸問題應(yīng)用舉例運(yùn)輸問題應(yīng)用舉例 解：解：該問題數(shù)據(jù)較多，但是經(jīng)過分該問題數(shù)據(jù)較多，但是經(jīng)過分 析，其產(chǎn)量在最低需求和最高需求析，其產(chǎn)量在最低需求和最高需求 之間，并且目標(biāo)函數(shù)是最大利潤(rùn)，之間，并且目標(biāo)函數(shù)是最大利潤(rùn)， 可以化簡(jiǎn)為表可以化簡(jiǎn)為表4-134-13（P124P124） u數(shù)學(xué)模型數(shù)學(xué)模型P124P124 u電子表格模型電子表格模型P125P125 u求解結(jié)果求解結(jié)果P126P126 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyrigh

46、t 4.5 4.5 指派問題指派問題 u在現(xiàn)實(shí)生活中，經(jīng)常會(huì)遇到指派人員做某項(xiàng)在現(xiàn)實(shí)生活中，經(jīng)常會(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)化。形式上

47、，指派問題給定了一系率實(shí)現(xiàn)最優(yōu)化。形式上，指派問題給定了一系 列所要完成的工作以及一系列完成工作的人員列所要完成的工作以及一系列完成工作的人員 ，所需要解決的問題就是要確定出指派哪個(gè)人，所需要解決的問題就是要確定出指派哪個(gè)人 去完成哪項(xiàng)工作。去完成哪項(xiàng)工作。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 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è)人來完

48、成；來完成； （4 4）每個(gè)人和每項(xiàng)工作的組合都會(huì)有）每個(gè)人和每項(xiàng)工作的組合都會(huì)有 一個(gè)相關(guān)的成本（一個(gè)相關(guān)的成本（單位成本單位成本）；）； （5 5）目標(biāo)是要確定如何指派才能使）目標(biāo)是要確定如何指派才能使總總 成本最小成本最小。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 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é)模型

49、為 11 1 1 () Min z 1 (1,2,) s.t. 1 (1,2,) 0 ( ,1,2,) nn ijij ij n ij j n ij i ij i j c x xin xjn xi jn (第 人只能做一項(xiàng)工作) (第 項(xiàng)工作只能一人做) 非負(fù) L L L 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.5 4.5 指派問題指派問題 u需要說明的是：需要說明的是：指派問題指派問題實(shí)際上是一種實(shí)際上是一種特殊的特殊的 運(yùn)輸問題運(yùn)輸問題。其中出發(fā)地是人，目的地是工作。只。其中出發(fā)地是人，目的地是工作。只 不過，每一個(gè)出發(fā)地的不過，每一個(gè)出

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

51、el的的“規(guī)劃求解規(guī)劃求解”還是采用還是采用“ 單純形法單純形法”來求解。來求解。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 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) 工作：工作：A A、B B、

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

53、派問題和指派問題 Desence copyright 4.5 4.5 指派問題指派問題 解解：該問題是一個(gè)：該問題是一個(gè)典型的指派問題典型的指派問題。 u單位成本單位成本為每個(gè)人做每項(xiàng)工作的總為每個(gè)人做每項(xiàng)工作的總 工資工資 u目標(biāo)目標(biāo)是要確定哪個(gè)人做哪一項(xiàng)工作是要確定哪個(gè)人做哪一項(xiàng)工作 ，使總成本最小，使總成本最小 u供應(yīng)量為供應(yīng)量為1 1代表每個(gè)人都只能完成代表每個(gè)人都只能完成 一項(xiàng)工作一項(xiàng)工作 u需求量為需求量為1 1代表每項(xiàng)工作也只能有代表每項(xiàng)工作也只能有 一個(gè)人來完成一個(gè)人來完成 u總?cè)藬?shù)（總?cè)藬?shù)（4 4人）和總?cè)蝿?wù)數(shù)（人）和總?cè)蝿?wù)數(shù)（4 4項(xiàng)）項(xiàng)） 相等相等 第第4章章 運(yùn)輸問題運(yùn)

54、輸問題 和指派問題和指派問題 Desence copyright 4.5 4.5 指派問題指派問題 數(shù)學(xué)模型：數(shù)學(xué)模型： 設(shè)設(shè)xij為指派人員為指派人員i去做工作去做工作j（i，j1,2,3,4) 1,2,3,4) 1 11 21 31 4 2 12 22 32 4 3 13 23 33 4 4 14 24 34 4 1 11 21 31 4 2 12 2 M 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 5 1 s .t. xxxx

55、xxxx xxxx xxxx xxxx xx （ 小 張 要 完 成 一 項(xiàng) 工 作 ） 2 32 4 3 13 23 33 4 4 14 24 34 4 1 12 13 14 1 1 22 23 24 2 1 32 33 34 3 1 42 43 44 4 D 1 1 1 1 1 1 1 xx xxxx xxxx xxxx xxxx xxxx xxxx （ 小 王 要 完 成 一 項(xiàng) 工 作 ） （ 小 李 要 完 成 一 項(xiàng) 工 作 ） （ 小 劉 要 完 成 一 項(xiàng) 工 作 ） （ 工 作 A 要 有 1 人 完 成 ） （ 工 作 B 要 有 1 人 完 成 ） （ 工 作 C 要 有

56、 1 人 完 成 ） （ 工 作要 有 1 人 0 ( ,1, 2 , 3 , 4 ) ij xij 完 成 ） （ 非 負(fù) ） 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.5 4.5 指派問題指派問題 電子表格模型電子表格模型 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.6 4.6 各種變形的指派問題建模各種變形的指派問題建模 經(jīng)常會(huì)遇到指派問題的經(jīng)常會(huì)遇到指派問題的變形變形，之所以稱它們?yōu)樽冃?，之所以稱它們?yōu)樽冃危?是因?yàn)樗鼈兌疾粷M足平衡指派問題所有假設(shè)之中的一是因?yàn)樗鼈兌疾粷M足平衡指派問題所有

57、假設(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ù)比人多( (人少事多人少事多);); （3 3）雖然每一項(xiàng)任務(wù)只由一個(gè)人完成，但是人比任務(wù)多（）雖然每一項(xiàng)任務(wù)只由一個(gè)人完成，但是人比任務(wù)多（人人 多事少多事少）；）； （4 4）某人可以同時(shí)被指派給多個(gè)任務(wù)（）某人可以同時(shí)被指派給多個(gè)任務(wù)（一人可做幾件事一人可做幾件事）；）； （5 5）某事可以由多人共同完成（）某事可以由多人共

58、同完成（一事可由多人完成一事可由多人完成） ； （6 6）目標(biāo)是與指派有關(guān)的）目標(biāo)是與指派有關(guān)的總利潤(rùn)最大總利潤(rùn)最大而不是使總成本最?。欢皇鞘箍偝杀咀钚?； （7 7）實(shí)際需要完成任務(wù)數(shù)不超過總?cè)藬?shù)也不超過總?cè)蝿?wù)數(shù)。）實(shí)際需要完成任務(wù)數(shù)不超過總?cè)藬?shù)也不超過總?cè)蝿?wù)數(shù)。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.6 4.6 各種變形的指派問題建模各種變形的指派問題建模 例例4.94.9 題目見例題目見例4.44.4，即某公司需要安排三，即某公司需要安排三 個(gè)工廠來生產(chǎn)四種新產(chǎn)品，相關(guān)的數(shù)據(jù)在表個(gè)工廠來生產(chǎn)四種新產(chǎn)品，相關(guān)的數(shù)據(jù)在表 4-74-7中已

59、經(jīng)給出。在例中已經(jīng)給出。在例4.44.4中，允許產(chǎn)品生產(chǎn)中，允許產(chǎn)品生產(chǎn) 分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的隱分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的隱 性成本（包括額外的設(shè)置、配送和管理成本性成本（包括額外的設(shè)置、配送和管理成本 等）。因此，管理人員決定在等）。因此，管理人員決定在禁止產(chǎn)品生產(chǎn)禁止產(chǎn)品生產(chǎn) 分解分解發(fā)生的情況下對(duì)問題進(jìn)行分析。發(fā)生的情況下對(duì)問題進(jìn)行分析。 新問題描述為：已知如表新問題描述為：已知如表4-74-7所示的數(shù)所示的數(shù) 據(jù)，問如何把每一個(gè)工廠指派給至少一個(gè)新?lián)?，問如何把每一個(gè)工廠指派給至少一個(gè)新 產(chǎn)品（每一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)），產(chǎn)品（每一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)）

60、， 使總成本達(dá)到最??？使總成本達(dá)到最小？ 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.6 4.6 各種變形的指派問題建模各種變形的指派問題建模 解：解：該問題可視為該問題可視為指派工廠生產(chǎn)產(chǎn)品問指派工廠生產(chǎn)產(chǎn)品問 題題，工廠可以看作指派問題中的人，產(chǎn)，工廠可以看作指派問題中的人，產(chǎn) 品則可以看作需要完成的工作（任務(wù)）品則可以看作需要完成的工作（任務(wù)） 。由于有四種產(chǎn)品和三個(gè)工廠，所以就。由于有四種產(chǎn)品和三個(gè)工廠，所以就 有兩個(gè)工廠各只能生產(chǎn)一種新產(chǎn)品，第有兩個(gè)工廠各只能生產(chǎn)一種新產(chǎn)品，第 三個(gè)工廠生產(chǎn)兩種新產(chǎn)品。只有工廠三個(gè)工廠生產(chǎn)兩種新產(chǎn)品。只