運(yùn)輸問題和指派問題課件

1、3.3 網(wǎng)絡(luò)配送問題通過配送網(wǎng)絡(luò)能以最小的成本完成貨物的配送，稱之為網(wǎng)絡(luò)配送問題。在網(wǎng)絡(luò)配送問題中，必須確定需求以及相應(yīng)地確定需求的約束條件。確定需求約束的形式如下：提供的數(shù)量需求的數(shù)量3.3 網(wǎng)絡(luò)配送問題C2F2C1F1C3700元/個(gè)900元/個(gè)800元/個(gè)800元/個(gè)900元/個(gè)700元/個(gè)10個(gè)8個(gè)9個(gè)12個(gè)15個(gè)實(shí)用運(yùn)籌學(xué)運(yùn)用Excel建模和求解第4章運(yùn)輸問題和指派問題本章內(nèi)容要點(diǎn)運(yùn)輸問題的基本概念及其各種變形的建模與應(yīng)用指派問題的基本概念及其各種變形的建模與應(yīng)用本章節(jié)內(nèi)容4.1 運(yùn)輸問題基本概念4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型4.3 各種運(yùn)輸問題變形的建模4.4 運(yùn)輸問題應(yīng)用

2、舉例4.5 指派問題4.6 各種指派問題變形的建模本章主要內(nèi)容框架圖4.1 運(yùn)輸問題基本概念運(yùn)輸問題最初起源于人們?cè)谌粘Ｉ钪邪涯承┪锲坊蛉藗冏陨韽囊恍┑胤睫D(zhuǎn)移到另一些地方，要求所采用的運(yùn)輸路線或運(yùn)輸方案是最經(jīng)濟(jì)或成本最低的，這就成為了一個(gè)運(yùn)籌學(xué)問題。隨著經(jīng)濟(jì)的不斷發(fā)展，現(xiàn)代物流業(yè)蓬勃發(fā)展，如何充分利用時(shí)間、信息、倉儲(chǔ)、配送和聯(lián)運(yùn)體系創(chuàng)造更多的價(jià)值，向運(yùn)籌學(xué)提出了更高的挑戰(zhàn)。要求科學(xué)地組織貨源、運(yùn)輸和配送使得運(yùn)輸問題變得日益復(fù)雜，但是其基本思想仍然是實(shí)現(xiàn)現(xiàn)有資源的最優(yōu)化配置。4.1 運(yùn)輸問題基本概念一般的運(yùn)輸問題就是解決如何把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，在每個(gè)產(chǎn)地的供應(yīng)量和每個(gè)銷地的

3、需求量已知，并知道各地之間的運(yùn)輸單價(jià)的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。平衡運(yùn)輸問題的條件：1.明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應(yīng)量（產(chǎn)量）、需求量（銷量）和單位成本。2.需求假設(shè)：每一個(gè)出發(fā)地都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。與之類似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須由出發(fā)地滿足。即“總供應(yīng)總需求”。3.成本假設(shè)：從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送成本與所配送的數(shù)量成線性比例關(guān)系，因此成本就等于配送的單位成本乘以所配送的數(shù)量（目標(biāo)函數(shù)是線性的）。4.1 運(yùn)輸問題基本概念例4.1 某公司有三個(gè)加工廠A1、A2、A3生產(chǎn)某產(chǎn)品，每

4、日的產(chǎn)量分別為：7噸、4噸、9噸；該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)B1、B2、B3、B4，各銷售點(diǎn)每日銷量分別為：3噸、6噸、5噸、6噸；從各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如表4-1所示。問該公司應(yīng)如何調(diào)運(yùn)這些產(chǎn)品，在滿足各銷售點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)最少？ 表4-1 各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)（元/噸）B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059銷量（噸）3656B2A2B1A1B3806585A3B475125100704.1 運(yùn)輸問題基本概念4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型 銷售點(diǎn)銷售點(diǎn)加工廠A1A2AmB1 B2 Bn產(chǎn)量 a1a2am銷量

5、b1 b2 bnc11 c12 c1nc21 c22 c2n cij cm1 cm2 cmn4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型（1）產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型 4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型對(duì)于例4.1，其數(shù)學(xué)模型如下： 首先，三個(gè)產(chǎn)地A1、A2、A3的總產(chǎn)量為74920；四個(gè)銷地B1、B2、B3、B4的總銷量為365620。由于總產(chǎn)量等于總銷量，故該問題是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。(1)決策變量 設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量(i1,2,3;j=1,2,3,4) （2）目標(biāo)函數(shù) 本問題的目標(biāo)是使得總運(yùn)輸費(fèi)最小4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型（3）約束條件滿足產(chǎn)地產(chǎn)量

6、（3個(gè)產(chǎn)地的產(chǎn)品都要全部配送出去）滿足銷地銷量（4個(gè)銷地的產(chǎn)品都要全部得到滿足）非負(fù)4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型運(yùn)輸問題是一種特殊的線性規(guī)劃問題，一般采用“表上作業(yè)法”求解運(yùn)輸問題，但Excel的“規(guī)劃求解”還是采用“單純形法”來求解。例4.1的電子表格模型4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型需要注意的是：運(yùn)輸問題有這樣一個(gè)性質(zhì)（整數(shù)解性質(zhì)），只要它的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運(yùn)輸問題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件。由于運(yùn)輸量經(jīng)常以卡車、集裝箱等為單位，如果卡車不能裝滿的話，就很不經(jīng)濟(jì)了。整數(shù)解性質(zhì)就避免了運(yùn)輸量（運(yùn)輸方

7、案）為小數(shù)的麻煩。4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型（2）產(chǎn)大于銷（供過于求）運(yùn)輸問題的數(shù)學(xué)模型（以滿足小的銷量為準(zhǔn)）4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型（3）銷大于產(chǎn)（供不應(yīng)求）運(yùn)輸問題的數(shù)學(xué)模型（以滿足小的產(chǎn)量為準(zhǔn)）4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型例4.2 某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10，15，25，20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如表44所示。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨的，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用1500元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)（包括儲(chǔ)存、維護(hù)）費(fèi)用最小的決策。表44 各季度的生產(chǎn)能力及

8、生產(chǎn)每臺(tái)柴油機(jī)的成本季度生產(chǎn)能力（臺(tái)）需求量（臺(tái)）單位成本（萬元）1251010.82351511.13302511.04102011.3例3.7 某公司根據(jù)訂單進(jìn)行生產(chǎn)。已知半年內(nèi)對(duì)某產(chǎn)品的需求量、單位生產(chǎn)費(fèi)用和單位存儲(chǔ)費(fèi)用,還已知公司每月的生產(chǎn)能力為100，每月倉庫容量為50。問：如何確定產(chǎn)品未來半年內(nèi)每月最佳生產(chǎn)量和存儲(chǔ)量，以使總費(fèi)用最少。表3-10 生產(chǎn)與庫存的有關(guān)數(shù)據(jù)月份123456需求量504050455530單位生產(chǎn)費(fèi)用825775850850775825單位存儲(chǔ)費(fèi)用4030352040404.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型解： (1)決策變量 設(shè)每月生產(chǎn)量為xi(i=1,2

9、,6)，每月月末庫存量為si(i=1,2,6) 。 上月庫存量（si-1）本月生產(chǎn)量（xi）-市場(chǎng)需求本月月末庫存量（si）4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型數(shù)學(xué)模型（線性規(guī)劃模型）4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型例3.7的電子表格模型4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型解：這是一個(gè)生產(chǎn)與儲(chǔ)存（庫存）問題，除了采用第3章的方法外，還可以轉(zhuǎn)化為運(yùn)輸問題來做。 由于每個(gè)季度生產(chǎn)出來的柴油機(jī)不一定當(dāng)季交貨，所以設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)。則第i季度生產(chǎn)的第j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本cij為： cij=第i季度每臺(tái)的生產(chǎn)成本+

10、0.15(j-i)（儲(chǔ)存、維護(hù)等費(fèi)用） 把第i季度生產(chǎn)的柴油機(jī)數(shù)看作第i個(gè)生產(chǎn)廠商的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)看作第j個(gè)銷售點(diǎn)的銷量；生產(chǎn)成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。將生產(chǎn)與儲(chǔ)存問題轉(zhuǎn)化為運(yùn)輸問題，相關(guān)數(shù)據(jù)見表45。4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型1234生產(chǎn)能力110.810.9511.1011.2525211.1011.2511.4035311.0011.1530411.3010需求量10152520 由表45可知，總產(chǎn)量（生產(chǎn)能力）為25+35+30+10=100，總銷量（需求量）為10+15+25+20=70，因此是產(chǎn)大于銷的運(yùn)輸問題季度生產(chǎn)能力（臺(tái)）需求量（臺(tái)）單位成本

11、（萬元）1251010.82351511.13302511.04102011.34.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型該生產(chǎn)與儲(chǔ)存問題（轉(zhuǎn)化為產(chǎn)大于銷的運(yùn)輸問題）的數(shù)學(xué)模型為4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型例4.2的電子表格模型4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型例4.3 某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地 B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如表46所示。問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最??？表46 例4.3的運(yùn)輸費(fèi)用表 B1B2B3產(chǎn)量A113151278A211292245銷量533665（銷大于產(chǎn)）4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格

12、模型解：由表46知，總產(chǎn)量為78+45=123，總銷量為53+36+65=154，銷大于產(chǎn)(供不應(yīng)求)。數(shù)學(xué)模型如下： 設(shè)xij為產(chǎn)地Ai運(yùn)往銷地Bj的物品數(shù)量4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型例4.3的電子表格模型4.3 各種運(yùn)輸問題變形的建模 現(xiàn)實(shí)生活中符合產(chǎn)銷平衡運(yùn)輸問題每一個(gè)條件的情況很少。一個(gè)特征近似但其中的一個(gè)或者幾個(gè)特征卻并不符合產(chǎn)銷平衡運(yùn)輸問題條件的運(yùn)輸問題卻經(jīng)常出現(xiàn)。下面是要討論的一些特征：（1）總供應(yīng)大于總需求。每一個(gè)供應(yīng)量（產(chǎn)量）代表了從其出發(fā)地中配送出去的最大數(shù)量（而不是一個(gè)固定的數(shù)值,）。（2）總供應(yīng)小于總需求。每一個(gè)需求量（銷量）代表了在其目的地中所接收到的最大

13、數(shù)量（而不是一個(gè)固定的數(shù)值,）。（3）一個(gè)目的地同時(shí)存在著最小需求和最大需求，于是所有在這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的（,）。（4）在配送中不能使用特定的出發(fā)地目的地組合（xij=0）。（5）目標(biāo)是使與配送數(shù)量有關(guān)的總利潤(rùn)最大而不是使總成本最小。（Min Max）4.3 各種運(yùn)輸問題變形的建模例4.4 某公司決定使用三個(gè)有生產(chǎn)余力的工廠進(jìn)行四種新產(chǎn)品的生產(chǎn)。每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任意種產(chǎn)品的數(shù)量來衡量（見表47的最右列）。而每種產(chǎn)品每天有一定的需求量（見表47的最后一行）。每家工廠都可以制造這些產(chǎn)品，除了工廠2不能生產(chǎn)產(chǎn)品3以外。然而，每種產(chǎn)品在不同工

14、廠中的單位成本是有差異的（如表47所示）?，F(xiàn)在需要決定的是在哪個(gè)工廠生產(chǎn)哪種產(chǎn)品，可使總成本最小?表47 產(chǎn)品生產(chǎn)的有關(guān)數(shù)據(jù)單位成本（元）生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠240292375工廠33730272145需求量203030404.3 各種變形的運(yùn)輸問題建模解：指定工廠生產(chǎn)產(chǎn)品可以看作運(yùn)輸問題來求解。本題中，工廠2不能生產(chǎn)產(chǎn)品3，這樣可以增加約束條件x230 ；并且，總供應(yīng)（75+75+45=195）總需求（20+30+30+40=120）。其數(shù)學(xué)模型如下： 設(shè)xij為工廠i生產(chǎn)產(chǎn)品j的數(shù)量4.3 各種運(yùn)輸問題變形的建模例4.4的電子表格模型產(chǎn)品4分在2個(gè)

15、工廠生產(chǎn)4.3 各種運(yùn)輸問題變形的建模例4.5 某公司在3個(gè)工廠中專門生產(chǎn)一種產(chǎn)品。在未來的4個(gè)月中，有四個(gè)處于國(guó)內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能大量訂購(gòu)。顧客1是公司最好的顧客，所以他的全部訂購(gòu)量都應(yīng)該滿足；顧客2和顧客3也是公司很重要的顧客，所以營(yíng)銷經(jīng)理認(rèn)為作為最低限度至少要滿足他們訂單的1/3；對(duì)于顧客4，銷售經(jīng)理認(rèn)為并不需要進(jìn)行特殊考慮。由于運(yùn)輸成本上的差異，銷售一個(gè)產(chǎn)品得到的凈利潤(rùn)也不同，很大程度上取決于哪個(gè)工廠供應(yīng)哪個(gè)顧客（見表48）。問應(yīng)向每一個(gè)顧客供應(yīng)多少貨物，以使公司總利潤(rùn)最大？表48 工廠供應(yīng)顧客的相關(guān)數(shù)據(jù)單位利潤(rùn)（元）產(chǎn)量顧客1顧客2顧客3顧客4工廠155424653

16、8000工廠2371832485000工廠3295951357000最小采購(gòu)量7000300020000最大采購(gòu)量70009000600080004.3 各種運(yùn)輸問題變形的建模解：該問題要求滿足不同顧客的需求（采購(gòu)量），解決辦法：實(shí)際供給量最小采購(gòu)量實(shí)際供給量最大采購(gòu)量 目標(biāo)是利潤(rùn)最大，而不是成本最小。其數(shù)學(xué)模型如下： 設(shè)xij為工廠i供應(yīng)給顧客j的產(chǎn)品數(shù)量4.3 各種運(yùn)輸問題變形的建模例4.5的電子表格模型4.4 運(yùn)輸問題應(yīng)用舉例例4.6 某廠生產(chǎn)設(shè)備是以銷定產(chǎn)的。已知16月份各月的生產(chǎn)能力、合同銷量和單臺(tái)設(shè)備平均生產(chǎn)費(fèi)用，如表49所示。 已知上年末庫存103臺(tái)。如果當(dāng)月生產(chǎn)出來的設(shè)備當(dāng)月不

17、交貨，則需要運(yùn)到分廠庫房，每臺(tái)增加運(yùn)輸成本0.1萬元，每臺(tái)設(shè)備每月的平均倉儲(chǔ)費(fèi)、維護(hù)費(fèi)為0.2萬元。78月份為銷售淡季，全廠停產(chǎn)1個(gè)月，因此在6月份完成銷售合同后還要留出庫存80臺(tái)。加班生產(chǎn)設(shè)備每臺(tái)增加成本1萬元。問應(yīng)如何安排16月份的生產(chǎn)，使總的生產(chǎn)（包括運(yùn)輸、倉儲(chǔ)、維護(hù)）費(fèi)用最少？月份正常生產(chǎn)能力（臺(tái)）加班生產(chǎn)能力（臺(tái)）合同銷量（臺(tái)）單臺(tái)費(fèi)用（萬元）1月6010104152月501075143月902011513.54月10040160135月10040103136月80407013.54.4 運(yùn)輸問題應(yīng)用舉例解：這是一個(gè)生產(chǎn)與儲(chǔ)存問題，但可以轉(zhuǎn)化為運(yùn)輸問題來做。（是否可以采用第3章的方法

18、做？同學(xué)們可以試試，然后進(jìn)行比較）生產(chǎn)方案不變，但總費(fèi)用為：8329.7萬元根據(jù)已知條件可以列出生產(chǎn)能力（正常生產(chǎn)能力和加班生產(chǎn)能力）和銷量以及運(yùn)價(jià)表（P120）數(shù)學(xué)模型P120121電子表格模型P122求解結(jié)果P1234.4 運(yùn)輸問題應(yīng)用舉例例4.7 華中金剛石鋸片廠有兩條生產(chǎn)線，分別生產(chǎn)直徑900-1800mm大鋸片基體20000片，直徑350-800mm中小鋸片基體40000片。公司在全國(guó)有25個(gè)銷售網(wǎng)點(diǎn)，主要銷售區(qū)域集中在福建、廣東、廣西、四川、山東5個(gè)石材主產(chǎn)區(qū)。為完成總廠的要求，公司決定一方面拿出10%的產(chǎn)量穩(wěn)定與前期各個(gè)客戶的聯(lián)系以保證將來的市場(chǎng)區(qū)域份額，另一方面，面臨如何將剩余

19、的90%的產(chǎn)量合理分配給五個(gè)石材主產(chǎn)區(qū)和其他省區(qū)，以獲取最大的利潤(rùn)。各個(gè)銷售區(qū)的最低需求、銷售固定費(fèi)用、每片平均運(yùn)費(fèi)、每片從總廠庫房的購(gòu)進(jìn)價(jià)與當(dāng)?shù)氐匿N售價(jià)差貢獻(xiàn)等自然情況見表412。問應(yīng)如何分配給各個(gè)銷售區(qū)，才能使得總利潤(rùn)為最大？4.4 運(yùn)輸問題應(yīng)用舉例解：該問題數(shù)據(jù)較多，但是經(jīng)過分析，其產(chǎn)量在最低需求和最高需求之間，并且目標(biāo)函數(shù)是最大利潤(rùn)，可以化簡(jiǎn)為表413（124）數(shù)學(xué)模型P124電子表格模型P125求解結(jié)果P1264.4 運(yùn)輸問題應(yīng)用舉例轉(zhuǎn)運(yùn)問題 （轉(zhuǎn)運(yùn)問題）小麥?zhǔn)崭钣谟軜浜筒龍D，然后運(yùn)往大連、營(yíng)口和錦州，再運(yùn)往?？?、廣州以及珠海的面粉加工廠。每地收獲300噸，海口、廣州以及珠海的需求量

20、分別是200、100和300.運(yùn)費(fèi)如表，求最小運(yùn)輸成本的運(yùn)輸量。大連營(yíng)口錦州榆樹161012昌圖151417大連營(yíng)口錦州大連海口6746廣州81158珠海10111210例4.1 某公司有三個(gè)加工廠A1、A2、A3生產(chǎn)某產(chǎn)品，每日的產(chǎn)量分別為：7噸、4噸、9噸；該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)B1、B2、B3、B4，各銷售點(diǎn)每日銷量分別為：3噸、6噸、5噸、6噸；從各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如表4-1所示。問該公司應(yīng)如何調(diào)運(yùn)這些產(chǎn)品，在滿足各銷售點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)最少？ 表4-1 各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)（元/噸）B1B2B3B4產(chǎn)量（噸）A13113107A219284

21、A3741059銷量（噸）3656補(bǔ)充：運(yùn)輸問題的悖論4.2 運(yùn)輸問題數(shù)學(xué)模型和電子表格模型例4.1的電子表格模型例4.8 （下料問題）用長(zhǎng)1米的條鋼來做4套鋼筋架子，每套架子有0.9米條鋼一根，0.18米的條鋼各二根，問最少需要多少根定長(zhǎng)為1米的條鋼才能做成？【分析】：本例共有2種下料方式，具體截法和余料見下表下料規(guī)格下料方式需求量方式1方式20.91040.18058余料0.10.1補(bǔ)充：運(yùn)輸問題的悖論下料規(guī)格下料方式需求量方式1方式20.91040.18058余料0.10.1補(bǔ)充：運(yùn)輸問題的悖論4.5 指派問題在現(xiàn)實(shí)生活中，經(jīng)常會(huì)遇到指派人員做某項(xiàng)工作（任務(wù)）的情況。指派問題的許多應(yīng)用是

22、用來幫助管理人員解決如何為一項(xiàng)即將開展的工作指派人員的問題。其他的一些應(yīng)用如為工作指派機(jī)器、設(shè)備或工廠等。指派問題也稱分配問題，主要研究人和工作（任務(wù)）間如何匹配，以使所有工作完成的效率實(shí)現(xiàn)最優(yōu)化。形式上，指派問題給定了一系列所要完成的工作以及一系列完成工作的人員，所需要解決的問題就是要確定出指派哪個(gè)人去完成哪項(xiàng)工作。4.5 指派問題（平衡）指派問題的假設(shè)：（1）人的數(shù)量和工作的數(shù)量相等；（2）每個(gè)人只能完成一項(xiàng)工作；（3）每項(xiàng)工作只能由一個(gè)人來完成；（4）每個(gè)人和每項(xiàng)工作的組合都會(huì)有一個(gè)相關(guān)的成本（單位成本）；（5）目標(biāo)是要確定如何指派才能使總成本最小。4.5 指派問題設(shè)決策變量xij為第i

23、個(gè)人做第j項(xiàng)工作，而已知目標(biāo)函數(shù)系數(shù)cij為第i個(gè)人完成第j項(xiàng)工作所需要的單位成本。平衡指派問題的數(shù)學(xué)模型為4.5 指派問題需要說明的是：指派問題實(shí)際上是一種特殊的運(yùn)輸問題。其中出發(fā)地是人，目的地是工作。只不過，每一個(gè)出發(fā)地的供應(yīng)量都為1（因?yàn)槊總€(gè)人都要完成一項(xiàng)工作），每一個(gè)目的地的需求量都為1（因?yàn)槊宽?xiàng)工作都要完成）。由于運(yùn)輸問題有“整數(shù)解性質(zhì)”，因此，沒有必要加上所有決策變量都是0-1變量的約束。指派問題是一種特殊的線性規(guī)劃問題，有一種快捷的求解方法：匈牙利方法（Hungarian Method），但Excel的“規(guī)劃求解”還是采用“單純形法”來求解。4.5 指派問題例4.8 某公司的營(yíng)銷

24、經(jīng)理將要主持召開一年一度的由營(yíng)銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會(huì)議。為了更好地安排這次會(huì)議，他安排小張、小王、小李、小劉等四個(gè)人，每個(gè)人負(fù)責(zé)完成下面的一項(xiàng)工作：A、B、C和D。 由于每個(gè)人完成每項(xiàng)任務(wù)的時(shí)間和工資不同（如表414所示）。問如何指派，可使總成本最小。人員每一項(xiàng)工作所需要的時(shí)間（小時(shí)）每小時(shí)工資（元）工作A工作B工作C工作D小張3541274014小王4745325112小李3956364313小劉32512546154.5 指派問題解：該問題是一個(gè)典型的指派問題。單位成本為每個(gè)人做每項(xiàng)工作的總工資目標(biāo)是要確定哪個(gè)人做哪一項(xiàng)工作，使總成本最小供應(yīng)量為1代表每個(gè)人都只能完成一項(xiàng)工

25、作需求量為1代表每項(xiàng)工作也只能有一個(gè)人來完成總?cè)藬?shù)（4人）和總?cè)蝿?wù)數(shù)（4項(xiàng)）相等4.5 指派問題數(shù)學(xué)模型：設(shè)xij為指派人員i去做工作j（i，j1,2,3,4) 4.5 指派問題電子表格模型4.6 各種指派問題變形的建模經(jīng)常會(huì)遇到指派問題的變形，之所以稱它們?yōu)樽冃?，是因?yàn)樗鼈兌疾粷M足平衡指派問題所有假設(shè)之中的一個(gè)或者多個(gè)。平衡指派問題假設(shè)：（1）人的數(shù)量和工作的數(shù)量相等；（2）每個(gè)人只能完成一項(xiàng)工作；（3）每項(xiàng)工作只能由一個(gè)人來完成；（4）每個(gè)人和每項(xiàng)工作的組合都會(huì)有一個(gè)相關(guān)的成本（單位成本）；（5）目標(biāo)是要確定如何指派才能使總成本最小。4.6 各種指派問題變形的建模變形的指派問題一般具有下面

26、的一些特征：（1）有些人并不能進(jìn)行某項(xiàng)工作（相應(yīng)的xij0）;（2）雖然每個(gè)人完成一項(xiàng)任務(wù)，但是任務(wù)比人多(人少事多);（3）雖然每一項(xiàng)任務(wù)只由一個(gè)人完成，但是人比任務(wù)多（人多事少）；（4）某人可以同時(shí)被指派給多個(gè)任務(wù)（一人可做幾件事）；（5）某事可以由多人共同完成（一事可由多人完成） ；（6）目標(biāo)是與指派有關(guān)的總利潤(rùn)最大而不是使總成本最??；（7）實(shí)際需要完成任務(wù)數(shù)不超過總?cè)藬?shù)也不超過總?cè)蝿?wù)數(shù)。 4.6 各種指派問題變形的建模例4.9 題目見例4.4（P115），即某公司需要安排三個(gè)工廠來生產(chǎn)四種新產(chǎn)品，相關(guān)的數(shù)據(jù)在表47中已經(jīng)給出。在例4.4中，允許產(chǎn)品生產(chǎn)分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)

27、的隱性成本（包括額外的設(shè)置、配送和管理成本等）。因此，管理人員決定在禁止產(chǎn)品生產(chǎn)分解發(fā)生的情況下對(duì)問題進(jìn)行分析。 新問題描述為：已知如表47所示的數(shù)據(jù)，問如何把每一個(gè)工廠指派給至少一個(gè)新產(chǎn)品（每一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)），使總成本達(dá)到最??？4.3 各種運(yùn)輸問題變形的建模產(chǎn)品4分在2個(gè)工廠生產(chǎn)單位成本（元）生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠240292375工廠33730272145需求量203030404.6 各種指派問題變形的建模解： 該問題可視為指派工廠生產(chǎn)產(chǎn)品問題，工廠可以看作指派問題中的人，產(chǎn)品則可以看作需要完成的工作（任務(wù)）。由于有四種產(chǎn)品和三個(gè)工廠，所

28、以就有兩個(gè)工廠各只能生產(chǎn)一種新產(chǎn)品，第三個(gè)工廠生產(chǎn)兩種新產(chǎn)品。只有工廠1和工廠2有生產(chǎn)兩種產(chǎn)品的能力。這里涉及如何把運(yùn)輸問題轉(zhuǎn)換為指派問題，關(guān)鍵所在是數(shù)據(jù)轉(zhuǎn)換。4.6 各種指派問題變形的建模數(shù)據(jù)轉(zhuǎn)換：（1）單位指派成本: 原來的單位成本轉(zhuǎn)換成整批成本（單位成本需求量），即單位指派成本為每個(gè)工廠生產(chǎn)每種產(chǎn)品的成本。（2）供應(yīng)量和需求量的轉(zhuǎn)換問題：三個(gè)工廠生產(chǎn)四種產(chǎn)品，但一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)，根據(jù)生產(chǎn)能力，工廠3只能生產(chǎn)一種產(chǎn)品（供應(yīng)量為1），而工廠1和工廠2可以生產(chǎn)2種產(chǎn)品（供應(yīng)量為2），而產(chǎn)品的需求量為1。還有“總供應(yīng)（2+2+1=5）總需求（1+1+1+1=4）”, 為人多事少的指派問

29、題。4.3 各種運(yùn)輸問題變形的建模單位成本（元）生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠240292375工廠33730272145需求量20303040整批成本（元）產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠1820810840960工廠2800870920工廠37409008108404.6 各種指派問題變形的建模數(shù)學(xué)模型：設(shè)xij為指派工廠i生產(chǎn)產(chǎn)品j（i=1,2,3;j=1,2,3,4) 4.6 各種指派問題變形的建模4.6 各種指派問題變形的建模例4.10 一家制藥公司，為了提升企業(yè)的競(jìng)爭(zhēng)力，決定加大科研力度。在研究了市場(chǎng)的需要，分析了當(dāng)前藥物的不足并且拜會(huì)了大量對(duì)有良好前景

30、的醫(yī)藥領(lǐng)域進(jìn)行研究的科學(xué)家之后，決定由五位科學(xué)家開發(fā)五個(gè)項(xiàng)目。為了保證這些科學(xué)家都能夠到他們感興趣的項(xiàng)目中去，為此建立了一個(gè)投標(biāo)系統(tǒng)。這五位科學(xué)家每個(gè)人都有1000點(diǎn)的投標(biāo)點(diǎn)。他們向每一個(gè)項(xiàng)目投標(biāo)，并且把較多的投標(biāo)點(diǎn)投向自己最感興趣的項(xiàng)目中。表415顯示了這5位科學(xué)家進(jìn)行投標(biāo)的情況。4.6 各種指派問題變形的建模表415 科學(xué)家項(xiàng)目投標(biāo)表投標(biāo)點(diǎn)a項(xiàng)目b項(xiàng)目c項(xiàng)目d項(xiàng)目e項(xiàng)目李爾博士100400200200100朱諾博士020080000劉哲博士100100100100600王凱博士2671539945130羅林博士1003333348004.6 各種指派問題變形的建模分析：決定要對(duì)一些可能發(fā)生

31、的情況進(jìn)行評(píng)估。（1）根據(jù)所給出的投標(biāo)情況，需要為每一個(gè)項(xiàng)目指派一位資深的科學(xué)家并且使得科學(xué)家的總滿意度最高。那么應(yīng)當(dāng)怎樣進(jìn)行指派？ （人數(shù)與項(xiàng)目數(shù)相等）P133134（2）羅林博士接到了北大醫(yī)學(xué)院的邀請(qǐng)去完成一個(gè)教學(xué)任務(wù)，而公司卻非常想把她留下來。但是北大的聲望會(huì)使她離開公司。如果這種情況真的發(fā)生的話，公司就只有放棄那個(gè)最缺乏熱情的項(xiàng)目。公司應(yīng)當(dāng)放棄那一個(gè)項(xiàng)目？（人少項(xiàng)目多）P1341354.6 各種指派問題變形的建模（3）當(dāng)然公司并不愿意放棄任何一個(gè)項(xiàng)目。公司決定讓朱諾博士或者王凱博士同時(shí)領(lǐng)導(dǎo)兩個(gè)項(xiàng)目。在只有4位科學(xué)家的情況下，讓哪一位科學(xué)家領(lǐng)導(dǎo)哪一個(gè)項(xiàng)目才能使得對(duì)項(xiàng)目的熱情最大？ （有人可以同時(shí)領(lǐng)導(dǎo)兩個(gè)項(xiàng)目）P134，136（4）還是來分析擁有5位科學(xué)家的情況，但由于各方面的原因，有三位科學(xué)家不能領(lǐng)導(dǎo)幾個(gè)特定的項(xiàng)目，如表4-16所示。由于不能領(lǐng)導(dǎo)，需重新調(diào)整這三位科學(xué)家的投標(biāo)點(diǎn)，使其總投標(biāo)點(diǎn)還是1000點(diǎn)，具體的調(diào)整方法是將不能領(lǐng)導(dǎo)的投標(biāo)點(diǎn)全部投到他自己最感興趣的項(xiàng)目上。在這種情況下，讓哪個(gè)科學(xué)家領(lǐng)導(dǎo)哪個(gè)項(xiàng)目才能使得對(duì)項(xiàng)目的總熱情最大