實(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)輸問題最初起源于人們在日常生活中把運(yùn)輸問題最初起源于人們在日常生活中把 某些物品或人們自身從一些地方轉(zhuǎn)移到另某些物品或人們自身從一些地方轉(zhuǎn)移到另 一些地方，要

4、求所采用的一些地方，要求所采用的運(yùn)輸路線運(yùn)輸路線或或運(yùn)輸運(yùn)輸 方案是最經(jīng)濟(jì)或成本最低方案是最經(jīng)濟(jì)或成本最低的，這就成為了的，這就成為了 一個運(yùn)籌學(xué)問題。一個運(yùn)籌學(xué)問題。 u 隨著經(jīng)濟(jì)的不斷發(fā)展，現(xiàn)代隨著經(jīng)濟(jì)的不斷發(fā)展，現(xiàn)代物流業(yè)物流業(yè)蓬勃發(fā)蓬勃發(fā) 展，如何充分利用時間、信息、倉儲、配展，如何充分利用時間、信息、倉儲、配 送和聯(lián)運(yùn)體系創(chuàng)造更多的價值，向運(yùn)籌學(xué)送和聯(lián)運(yùn)體系創(chuàng)造更多的價值，向運(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)品從若干個一般的運(yùn)輸問題就是解決如何把某種產(chǎn)品從若干個產(chǎn)地產(chǎn)地 調(diào)運(yùn)到若干個調(diào)運(yùn)到若干個銷地銷地，在每個產(chǎn)地的，在每個產(chǎn)地的供應(yīng)量供應(yīng)量和每個銷地的和每個銷地的 需求量需求量已知，并知道各地之間的已知，并知道各地之間的運(yùn)輸單價運(yùn)輸單價的前提下，如的前提下，如 何確定一個使得總的運(yùn)輸費(fèi)用最小的方案。何確定一個使得總的運(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è)：每一個出發(fā)地都有一個固定的供應(yīng)量，所有的供應(yīng)需求假設(shè)：每一個出發(fā)地都有一個固定的供應(yīng)量，所有的供應(yīng) 量都必須配送到目的地。與之類似，每一個目的地都有一個固量都必須配送到目的地。與之類似，每一個目的地都有一個固 定的需求量，整個需求量都必須由出發(fā)地滿足。即定的需求量，整個需求量都必須由出發(fā)地滿足。即“總供應(yīng)總供應(yīng) 總需求總需求”。 3.3.成本假設(shè)：從任何一個出發(fā)地到任何一個目的地的貨物配送成成本假設(shè)：從任何一

7、個出發(fā)地到任何一個目的地的貨物配送成 本與所配送的數(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 某公司有三個加工廠某公司有三個加工廠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)往四個銷售點(diǎn)分別運(yùn)往四個銷售點(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)價如表的單位產(chǎn)品運(yùn)價如表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)價（元各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價（元/ /噸）噸） 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個產(chǎn)地個產(chǎn)地A Ai i（i1,2,1,2, ,m）和和n個銷地個銷地 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é)模型和電子表格模型 對于例對于例4.14.1，其數(shù)學(xué)模型如下：，其數(shù)學(xué)模型如下： 首先，三個產(chǎn)地首先，三個產(chǎn)地A1A1、A2A2、A3A3的總產(chǎn)量為的總產(chǎn)量為7 74 49 92020；四個；四

11、個 銷地銷地B1B1、B2B2、B3B3、B4B4的總銷量為的總銷量為3 36 65 56 62020。由于總。由于總 產(chǎn)量等于總銷量，故該問題是一個產(chǎn)銷平衡的運(yùn)輸問題。產(chǎn)量等于總銷量，故該問題是一個產(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個產(chǎn)地的個產(chǎn)地的 產(chǎn)品都要全部產(chǎn)品都要全部 配送出去）配送出去） 滿足銷地銷量滿足銷地銷量 （4 4個銷地的個銷地的 產(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)輸問題有這樣一個性需要注意的是：運(yùn)輸問題有這樣一個性 質(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)年每個季度末分別提某廠按合同規(guī)定須于當(dāng)年每個季度末分別提 供供1010，1515，2525，2020臺同一規(guī)格的柴油機(jī)。已知該廠臺同一規(guī)格的柴

18、油機(jī)。已知該廠 各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表4-44-4 所示。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨的，每臺所示。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨的，每臺 每積壓一個季度需儲存、維護(hù)等費(fèi)用每積壓一個季度需儲存、維護(hù)等費(fèi)用15001500元。要求元。要求 在完成合同的情況下，做出使該廠全年生產(chǎn)（包括在完成合同的情況下，做出使該廠全年生產(chǎn)（包括 儲存、維護(hù)）費(fèi)用最小的決策。儲存、維護(hù)）費(fèi)用最小的決策。 表表4-4 4-4 各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本 季度季度生產(chǎn)能力（臺）生產(chǎn)能力（臺）單位成本（萬元）

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é)模型和電子表格模型 解：解：這是一個這是一個生產(chǎn)與儲存（庫存）問題生產(chǎn)與儲存（庫存）問題，除了采用第，除了采用第 3 3章的方法外，還可以轉(zhuǎn)化為章的方法外，還可以轉(zhuǎn)化為運(yùn)輸問題運(yùn)輸問題來做。來做。 由于每個季度生產(chǎn)出來的柴油機(jī)不一定當(dāng)季交貨，由于每個季度生產(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季度交貨的每臺柴油機(jī)的實(shí)際成季度交貨的每臺柴油機(jī)的實(shí)際成 本本cij為：為： cij= =第第i季度每臺的生產(chǎn)成本季度每臺的生產(chǎn)成本+0.15(+0.15(j-i) )（儲存、維護(hù)等費(fèi)用）（儲存、維護(hù)等費(fèi)用） 把第把第i季度生產(chǎn)的柴油機(jī)數(shù)看作第季度生產(chǎn)的柴油機(jī)數(shù)看作第i個生產(chǎn)廠商的個生產(chǎn)廠商的 產(chǎn)量；把第產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)看作第季度交貨的柴油機(jī)數(shù)看作第j個銷售點(diǎn)的個銷售點(diǎn)的 銷量；生產(chǎn)成本加儲存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。將生銷量；生產(chǎn)成本加儲存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。將生 產(chǎn)與儲

21、存問題轉(zhuǎn)化為運(yùn)輸問題，相關(guān)數(shù)據(jù)見表產(chǎn)與儲存問題轉(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)與 儲存問題儲存問題 （轉(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 某公司從兩個產(chǎn)地某公司從兩個產(chǎn)地A1A1、A2A2將物品運(yùn)往將物品運(yùn)往 三個銷地三個銷地 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)輸問題每一個條件的情況很少。一現(xiàn)實(shí)生活中符合產(chǎn)銷平衡運(yùn)輸問題每一個條件的情況很少。一 個特征近似但其中的一個或者幾個特征卻并不符合產(chǎn)銷平衡運(yùn)個特征近似但其中的一個或者幾個特征卻并不符合產(chǎn)銷平衡運(yùn) 輸問題條件的運(yùn)輸問題卻經(jīng)常出現(xiàn)。輸問題條件的運(yùn)輸問題卻經(jīng)常出現(xiàn)。 下面是要討論的一些特征：下面是要討論的一些特征： （

28、1 1）總供應(yīng)大于總需求總供應(yīng)大于總需求。每一個供應(yīng)量（產(chǎn)量）代表了從其出。每一個供應(yīng)量（產(chǎn)量）代表了從其出 發(fā)地中配送出去的最大數(shù)量（而不是一個固定的數(shù)值發(fā)地中配送出去的最大數(shù)量（而不是一個固定的數(shù)值, ,）。）。 （2 2）總供應(yīng)小于總需求總供應(yīng)小于總需求。每一個需求量（銷量）代表了在其目。每一個需求量（銷量）代表了在其目 的地中所接收到的最大數(shù)量（而不是一個固定的數(shù)值的地中所接收到的最大數(shù)量（而不是一個固定的數(shù)值, ,）。）。 （3 3）一個目的地）一個目的地同時存在著最小需求和最大需求同時存在著最小需求和最大需求，于是所有在，于是所有在 這兩個數(shù)值之間的數(shù)量都是可以接收的（這兩個數(shù)值之

29、間的數(shù)量都是可以接收的（, ,）。）。 （4 4）在配送中）在配送中不能使用不能使用特定的出發(fā)地特定的出發(fā)地目的地組合（目的地組合（xij=0=0）。）。 （5 5）目標(biāo)是使與配送數(shù)量有關(guān)的）目標(biāo)是使與配送數(shù)量有關(guān)的總利潤最大總利潤最大而不是使總成本最而不是使總成本最 小。（小。（MinMin MaxMax） 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.3 4.3 各種變形的運(yùn)輸問題建模各種變形的運(yùn)輸問題建模 例例4.44.4 某公司決定使用三個有生產(chǎn)余力的工廠進(jìn)行四種新產(chǎn)品的生產(chǎn)。某公司決定使用三個有生產(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)在需要決定的是在哪個工

31、廠生產(chǎn)哪種產(chǎn)品，可使總成本最小。現(xiàn)在需要決定的是在哪個工廠生產(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個工廠生產(chǎn)個工廠生產(chǎn) 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.3 4.3 各種變形的運(yùn)輸問題建模各種變形的運(yùn)輸問題建模 例例4.54.5 某公司在某公司在3 3個工廠中專門生產(chǎn)一種產(chǎn)品。在未來的個工廠中專門生產(chǎn)一種產(chǎn)品。在未來的4 4個月中，有四個月中，有四 個處于國內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能大量訂購。顧客個處于國內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能大量訂購。顧客1 1是公是公 司最好的顧客，所以他的全部訂購量都應(yīng)該滿足；顧客司最好的顧客，所以他的全部訂購量都應(yīng)該滿足；顧客2 2和顧客和顧客3

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

36、供應(yīng)顧客的相關(guān)數(shù)據(jù)工廠供應(yīng)顧客的相關(guān)數(shù)據(jù) 單位利潤（元）單位利潤（元） 產(chǎn)量產(chǎn)量 顧客顧客1 1顧客顧客2 2顧客顧客3 3顧客顧客4 4 工廠工廠1 1555542424646535380008000 工廠工廠2 2373718183232484850005000 工廠工廠3 3292959595151353570007000 最小采購量最小采購量7000700030003000200020000 0 最大采購量最大采購量70007000900090006000600080008000 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.3 4.3 各

37、種變形的運(yùn)輸問題建模各種變形的運(yùn)輸問題建模 解：解：該問題要求滿足不該問題要求滿足不 同顧客的需求（采購量同顧客的需求（采購量 ），解決辦法：），解決辦法： 實(shí)際供給量實(shí)際供給量 最小采購量最小采購量 實(shí)際供給量實(shí)際供給量 最大采購量最大采購量 目標(biāo)是利潤最大，而目標(biāo)是利潤最大，而 不是成本最小。不是成本最小。 其數(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)能力、 合同銷量和單臺設(shè)備平均生產(chǎn)費(fèi)用，如表合同銷量和單臺設(shè)備平均生產(chǎn)費(fèi)用，如表4-94-9所示。所示。 已知上年末庫存已知上年末庫存103103臺。如果當(dāng)月生產(chǎn)出來的設(shè)備當(dāng)月不交貨，則臺。如果當(dāng)月生產(chǎn)出來的設(shè)備當(dāng)月不交貨，則 需要運(yùn)到分廠庫房，每臺增加運(yùn)輸成本需要運(yùn)到分廠庫房，每臺增加運(yùn)輸成本0.10.1萬元，每臺設(shè)備每月的平均萬元，每臺設(shè)備每月的平均 倉

40、儲費(fèi)、維護(hù)費(fèi)為倉儲費(fèi)、維護(hù)費(fèi)為0.20.2萬元。萬元。7 78 8月份為銷售淡季，全廠停產(chǎn)月份為銷售淡季，全廠停產(chǎn)1 1個月，個月， 因此在因此在6 6月份完成銷售合同后還要留出庫存月份完成銷售合同后還要留出庫存8080臺。加班生產(chǎn)設(shè)備每臺增臺。加班生產(chǎn)設(shè)備每臺增 加成本加成本1 1萬元。問應(yīng)如何安排萬元。問應(yīng)如何安排1 16 6月份的生產(chǎn)，使總的生產(chǎn)（包括運(yùn)輸月份的生產(chǎn)，使總的生產(chǎn)（包括運(yùn)輸 、倉儲、維護(hù)）費(fèi)用最少？、倉儲、維護(hù)）費(fèi)用最少？ 月份月份 正常生產(chǎn)能力正常生產(chǎn)能力 （臺）（臺） 加班生產(chǎn)能力加班生產(chǎn)能力 （臺）（臺） 合同銷量合同銷量 （臺）（臺） 單臺費(fè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)用舉例 解：解：這是一個生產(chǎn)與儲存問題，但可以轉(zhuǎn)化為運(yùn)這是一個生產(chǎn)與儲存問題，但可以轉(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)價表（力和加班生產(chǎn)能力）和銷量以及運(yùn)價表（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片。公司在全國有片。公司在全國有2525個銷個銷 售網(wǎng)點(diǎn)，主要銷售區(qū)域集中在福建、廣東、廣西、售網(wǎng)點(diǎn)，主要銷售區(qū)域集中在福建、廣東、廣西、 四川、山東四川、山東5 5個石材主產(chǎn)區(qū)。為完成總廠的要求，個石材主產(chǎn)區(qū)。為完成總廠的要求， 公司決定一方面拿出公司決定一方面拿出10%10%的產(chǎn)量穩(wěn)定與前期各個客的產(chǎn)

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

45、利潤為最大？ 第第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ù)是最大利潤，之間，并且目標(biāo)函數(shù)是最大利潤， 可以化簡為表可以化簡為表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)常會遇到指派人員做某項在現(xiàn)實(shí)生活中，經(jīng)常會遇到指派人員做某項 工作（任務(wù)）的情況。工作（任務(wù)）的情況。指派問題指派問題的許多應(yīng)用是的許多應(yīng)用是 用來幫助管理人員解決如何為一項即將開展的用來幫助管理人員解決如何為一項即將開展的 工作指派人員的問題。其他的一些應(yīng)用如為工工作指派人員的問題。其他的一些應(yīng)用如為工 作指派機(jī)器、設(shè)備或工廠等。作指派機(jī)器、設(shè)備或工廠等。 u指派問題也稱指派問題也稱分配問題分配問題，主要研究人和工作，主要研究人和工作 （任務(wù)）間如何匹配，以使所有工作完成的效（任務(wù)）間如何匹配，以使所有工作完成的效 率實(shí)現(xiàn)最優(yōu)化。形式上

47、，指派問題給定了一系率實(shí)現(xiàn)最優(yōu)化。形式上，指派問題給定了一系 列所要完成的工作以及一系列完成工作的人員列所要完成的工作以及一系列完成工作的人員 ，所需要解決的問題就是要確定出指派哪個人，所需要解決的問題就是要確定出指派哪個人 去完成哪項工作。去完成哪項工作。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.5 4.5 指派問題指派問題 u指派問題的假設(shè)：指派問題的假設(shè)： （1 1）人的數(shù)量和工作的數(shù)量）人的數(shù)量和工作的數(shù)量相等相等； （2 2）每個人）每個人只能完成一項只能完成一項工作；工作； （3 3）每項工作）每項工作只能由一個人只能由一個人來完

48、成；來完成； （4 4）每個人和每項工作的組合都會有）每個人和每項工作的組合都會有 一個相關(guān)的成本（一個相關(guān)的成本（單位成本單位成本）；）； （5 5）目標(biāo)是要確定如何指派才能使）目標(biāo)是要確定如何指派才能使總總 成本最小成本最小。 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.5 4.5 指派問題指派問題 u設(shè)決策變量設(shè)決策變量xij為為第第i個人個人做做第第j項工作項工作，而已，而已 知目標(biāo)函數(shù)系數(shù)知目標(biāo)函數(shù)系數(shù)cij為第為第i個人完成第個人完成第j項工作所項工作所 需要的需要的單位成本單位成本。 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 (第 人只能做一項工作) (第 項工作只能一人做) 非負(fù) L L L 第第4章章 運(yùn)輸問題運(yùn)輸問題 和指派問題和指派問題 Desence copyright 4.5 4.5 指派問題指派問題 u需要說明的是：需要說明的是：指派問題指派問題實(shí)際上是一種實(shí)際上是一種特殊的特殊的 運(yùn)輸問題運(yùn)輸問題。其中出發(fā)地是人，目的地是工作。只。其中出發(fā)地是人，目的地是工作。只 不過，每一個出發(fā)地的不過，每一個出

50、發(fā)地的供應(yīng)量都為供應(yīng)量都為1 1（因為每個（因為每個 人都要完成一項工作），每一個目的地的人都要完成一項工作），每一個目的地的需求量需求量 都為都為1 1（因為每項工作都要完成）。由于運(yùn)輸問（因為每項工作都要完成）。由于運(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 某公司的營銷經(jīng)理將要主持召開一年一度的某公司的營銷經(jīng)理將要主持召開一年一度的 由營銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會議由營銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會議 。為了更好地安排這次會議，他安排小張、小王、。為了更好地安排這次會議，他安排小張、小王、 小李、小劉等四個人，每個人負(fù)責(zé)完成下面的一項小李、小劉等四個人，每個人負(fù)責(zé)完成下面的一項 工作：工作：A A、B B、

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

53、派問題和指派問題 Desence copyright 4.5 4.5 指派問題指派問題 解解：該問題是一個：該問題是一個典型的指派問題典型的指派問題。 u單位成本單位成本為每個人做每項工作的總為每個人做每項工作的總 工資工資 u目標(biāo)目標(biāo)是要確定哪個人做哪一項工作是要確定哪個人做哪一項工作 ，使總成本最小，使總成本最小 u供應(yīng)量為供應(yīng)量為1 1代表每個人都只能完成代表每個人都只能完成 一項工作一項工作 u需求量為需求量為1 1代表每項工作也只能有代表每項工作也只能有 一個人來完成一個人來完成 u總?cè)藬?shù)（總?cè)藬?shù)（4 4人）和總?cè)蝿?wù)數(shù)（人）和總?cè)蝿?wù)數(shù)（4 4項）項） 相等相等 第第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 （ 小 張 要 完 成 一 項 工 作 ） 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 （ 小 王 要 完 成 一 項 工 作 ） （ 小 李 要 完 成 一 項 工 作 ） （ 小 劉 要 完 成 一 項 工 作 ） （ 工 作 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)常會遇到指派問題的經(jīng)常會遇到指派問題的變形變形，之所以稱它們?yōu)樽冃?，之所以稱它們?yōu)樽冃危?是因為它們都不滿足平衡指派問題所有假設(shè)之中的一是因為它們都不滿足平衡指派問題所有

57、假設(shè)之中的一 個或者多個。一般考慮下面的一些特征：個或者多個。一般考慮下面的一些特征： （1 1）有些人并）有些人并不能不能進(jìn)行某項工作（相應(yīng)的進(jìn)行某項工作（相應(yīng)的xij0 0）; ; （2 2）雖然每個人完成一項任務(wù)，但是任務(wù)比人多）雖然每個人完成一項任務(wù)，但是任務(wù)比人多( (人少事多人少事多);); （3 3）雖然每一項任務(wù)只由一個人完成，但是人比任務(wù)多（）雖然每一項任務(wù)只由一個人完成，但是人比任務(wù)多（人人 多事少多事少）；）； （4 4）某人可以同時被指派給多個任務(wù)（）某人可以同時被指派給多個任務(wù)（一人可做幾件事一人可做幾件事）；）； （5 5）某事可以由多人共同完成（）某事可以由多人共

58、同完成（一事可由多人完成一事可由多人完成） ； （6 6）目標(biāo)是與指派有關(guān)的）目標(biāo)是與指派有關(guā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，即某公司需要安排三，即某公司需要安排三 個工廠來生產(chǎn)四種新產(chǎn)品，相關(guān)的數(shù)據(jù)在表個工廠來生產(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ā)生的情況下對問題進(jìn)行分析。發(fā)生的情況下對問題進(jìn)行分析。 新問題描述為：已知如表新問題描述為：已知如表4-74-7所示的數(shù)所示的數(shù) 據(jù)，問如何把每一個工廠指派給至少一個新?lián)?，問如何把每一個工廠指派給至少一個新 產(chǎn)品（每一種產(chǎn)品只能在一個工廠生產(chǎn)），產(chǎn)品（每一種產(chǎn)品只能在一個工廠生產(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)品和三個工廠，所以就。由于有四種產(chǎn)品和三個工廠，所以就 有兩個工廠各只能生產(chǎn)一種新產(chǎn)品，第有兩個工廠各只能生產(chǎn)一種新產(chǎn)品，第 三個工廠生產(chǎn)兩種新產(chǎn)品。只有工廠三個工廠生產(chǎn)兩種新產(chǎn)品。只