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

實(shí)用運(yùn)籌學(xué)

－運(yùn)用Excel建模和求解第4章運(yùn)輸問(wèn)題和指派問(wèn)題本章內(nèi)容要點(diǎn)運(yùn)輸問(wèn)題的根本概念及其各種變形的建模與應(yīng)用指派問(wèn)題的根本概念及其各種變形的建模與應(yīng)用本章節(jié)內(nèi)容4.1運(yùn)輸問(wèn)題根本概念4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型4.3各種運(yùn)輸問(wèn)題變形的建模4.4運(yùn)輸問(wèn)題應(yīng)用舉例4.5指派問(wèn)題4.6各種指派問(wèn)題變形的建模本章主要內(nèi)容框架圖4.1運(yùn)輸問(wèn)題根本概念運(yùn)輸問(wèn)題最初起源于人們?cè)谌粘Ｉ钪邪涯承┪锲坊蛉藗冏陨韽囊恍┑胤睫D(zhuǎn)移到另一些地方，要求所采用的運(yùn)輸路線或運(yùn)輸方案是最經(jīng)濟(jì)或本錢最低的，這就成為了一個(gè)運(yùn)籌學(xué)問(wèn)題。隨著經(jīng)濟(jì)的不斷開(kāi)展，現(xiàn)代物流業(yè)蓬勃開(kāi)展，如何充分利用時(shí)間、信息、倉(cāng)儲(chǔ)、配送和聯(lián)運(yùn)體系創(chuàng)造更多的價(jià)值，向運(yùn)籌學(xué)提出了更高的挑戰(zhàn)。要求科學(xué)地組織貨源、運(yùn)輸和配送使得運(yùn)輸問(wèn)題變得日益復(fù)雜，但是其根本思想仍然是實(shí)現(xiàn)現(xiàn)有資源的最優(yōu)化配置。4.1運(yùn)輸問(wèn)題根本概念一般的運(yùn)輸問(wèn)題就是解決如何把某種產(chǎn)品從假設(shè)干個(gè)產(chǎn)地調(diào)運(yùn)到假設(shè)干個(gè)銷地，在每個(gè)產(chǎn)地的供給量和每個(gè)銷地的需求量，并知道各地之間的運(yùn)輸單價(jià)的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。平衡運(yùn)輸問(wèn)題的條件：1. 明確出發(fā)地〔產(chǎn)地〕、目的地〔銷地〕、供給量〔產(chǎn)量〕、需求量〔銷量〕和單位本錢。2. 需求假設(shè)：每一個(gè)出發(fā)地都有一個(gè)固定的供給量，所有的供給量都必須配送到目的地。與之類似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須由出發(fā)地滿足。即“總供給＝總需求〞。3. 本錢假設(shè)：從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送本錢與所配送的數(shù)量成線性比例關(guān)系，因此本錢就等于配送的單位本錢乘以所配送的數(shù)量〔目標(biāo)函數(shù)是線性的〕。4.1運(yùn)輸問(wèn)題根本概念例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所示。問(wèn)該公司應(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銷量（噸）36564.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型〔1〕產(chǎn)銷平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型具有m個(gè)產(chǎn)地Ai〔i＝1,2,,m〕和n個(gè)銷地Bj〔j＝1,2,,n〕的運(yùn)輸問(wèn)題的數(shù)學(xué)模型為4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型對(duì)于例4.1，其數(shù)學(xué)模型如下：首先，三個(gè)產(chǎn)地A1、A2、A3的總產(chǎn)量為7＋4＋9＝20；四個(gè)銷地B1、B2、B3、B4的總銷量為3＋6＋5＋6＝20。由于總產(chǎn)量等于總銷量，故該問(wèn)題是一個(gè)產(chǎn)銷平衡的運(yùn)輸問(wèn)題。(1)決策變量設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量(i＝1,2,3;j=1,2,3,4)〔2〕目標(biāo)函數(shù)本問(wèn)題的目標(biāo)是使得總運(yùn)輸費(fèi)最小。4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型〔3〕約束條件①滿足產(chǎn)地產(chǎn)量〔3個(gè)產(chǎn)地的產(chǎn)品都要全部配送出去〕②滿足銷地銷量〔4個(gè)銷地的產(chǎn)品都要全部得到滿足〕③非負(fù)4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，一般采用“表上作業(yè)法〞求解運(yùn)輸問(wèn)題，但Excel的“規(guī)劃求解〞還是采用“單純形法〞來(lái)求解。例4.1的電子表格模型4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型需要注意的是：運(yùn)輸問(wèn)題有這樣一個(gè)性質(zhì)〔整數(shù)解性質(zhì)〕，只要它的供給量和需求量都是整數(shù)，任何有可行解的運(yùn)輸問(wèn)題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒(méi)有必要加上所有變量都是整數(shù)的約束條件。由于運(yùn)輸量經(jīng)常以卡車、集裝箱等為單位，如果卡車不能裝滿的話，就很不經(jīng)濟(jì)了。整數(shù)解性質(zhì)就防止了運(yùn)輸量〔運(yùn)輸方案〕為小數(shù)的麻煩。4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型〔2〕產(chǎn)大于銷〔供過(guò)于求〕運(yùn)輸問(wèn)題的數(shù)學(xué)模型〔以滿足小的銷量為準(zhǔn)〕4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型〔3〕銷大于產(chǎn)〔供不應(yīng)求〕運(yùn)輸問(wèn)題的數(shù)學(xué)模型〔以滿足小的產(chǎn)量為準(zhǔn)〕4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型例4.2某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10，15，25，20臺(tái)同一規(guī)格的柴油機(jī)。該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的本錢如表4－4所示。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨的，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用1500元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)〔包括儲(chǔ)存、維護(hù)〕費(fèi)用最小的決策。表4－4各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的本錢季度生產(chǎn)能力（臺(tái)）單位成本（萬(wàn)元）12510.823511.133011.041011.34.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型解：這是一個(gè)生產(chǎn)與儲(chǔ)存〔庫(kù)存〕問(wèn)題，除了采用第3章的方法外，還可以轉(zhuǎn)化為運(yùn)輸問(wèn)題來(lái)做。由于每個(gè)季度生產(chǎn)出來(lái)的柴油機(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)本錢+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ǔ)存問(wèn)題轉(zhuǎn)化為運(yùn)輸問(wèn)題，相關(guān)數(shù)據(jù)見(jiàn)表4－5。4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型表4－5柴油機(jī)生產(chǎn)的相關(guān)數(shù)據(jù)1234生產(chǎn)能力110.810.9511.1011.2525211.1011.2511.4035311.0011.1530411.3010需求量10152520由表4－5可知，總產(chǎn)量〔生產(chǎn)能力〕為25+35+30+10=100，總銷量〔需求量〕為10+15+25+20=70，因此是產(chǎn)大于銷的運(yùn)輸問(wèn)題。4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型該生產(chǎn)與儲(chǔ)存問(wèn)題〔轉(zhuǎn)化為產(chǎn)大于銷的運(yùn)輸問(wèn)題〕的數(shù)學(xué)模型為4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型例4.2的電子表格模型4.2運(yùn)輸問(wè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)如表4－6所示。問(wèn)應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小？表4－6例4.3的運(yùn)輸費(fèi)用表

B1B2B3產(chǎn)量A113151278A211292245銷量533665（銷大于產(chǎn)）4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型解：由表4－6知，總產(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)輸問(wèn)題數(shù)學(xué)模型和電子表格模型例4.3的電子表格模型4.3各種運(yùn)輸問(wèn)題變形的建?，F(xiàn)實(shí)生活中符合產(chǎn)銷平衡運(yùn)輸問(wèn)題每一個(gè)條件的情況很少。一個(gè)特征近似但其中的一個(gè)或者幾個(gè)特征卻并不符合產(chǎn)銷平衡運(yùn)輸問(wèn)題條件的運(yùn)輸問(wèn)題卻經(jīng)常出現(xiàn)。下面是要討論的一些特征：〔1〕總供給大于總需求。每一個(gè)供給量〔產(chǎn)量〕代表了從其出發(fā)地中配送出去的最大數(shù)量〔而不是一個(gè)固定的數(shù)值,≤〕?！?〕總供給小于總需求。每一個(gè)需求量〔銷量〕代表了在其目的地中所接收到的最大數(shù)量〔而不是一個(gè)固定的數(shù)值,≤〕?！?〕一個(gè)目的地同時(shí)存在著最小需求和最大需求，于是所有在這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的〔≥,≤〕?！?〕在配送中不能使用特定的出發(fā)地—目的地組合〔xij=0〕?！?〕目標(biāo)是使與配送數(shù)量有關(guān)的總利潤(rùn)最大而不是使總本錢最小?！睲in－>Max〕4.3各種運(yùn)輸問(wèn)題變形的建模例4.4某公司決定使用三個(gè)有生產(chǎn)余力的工廠進(jìn)行四種新產(chǎn)品的生產(chǎn)。每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任意種產(chǎn)品的數(shù)量來(lái)衡量〔見(jiàn)表4－7的最右列〕。而每種產(chǎn)品每天有一定的需求量〔見(jiàn)表4－7的最后一行〕。每家工廠都可以制造這些產(chǎn)品，除了工廠2不能生產(chǎn)產(chǎn)品3以外。然而，每種產(chǎn)品在不同工廠中的單位本錢是有差異的〔如表4－7所示〕。現(xiàn)在需要決定的是在哪個(gè)工廠生產(chǎn)哪種產(chǎn)品，可使總本錢最小。表4－7產(chǎn)品生產(chǎn)的有關(guān)數(shù)據(jù)單位成本（元）生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠24029－2375工廠33730272145需求量203030404.3各種運(yùn)輸問(wèn)題變形的建模解：指定工廠生產(chǎn)產(chǎn)品可以看作運(yùn)輸問(wèn)題來(lái)求解。此題中，工廠2不能生產(chǎn)產(chǎn)品3，這樣可以增加約束條件x23＝0；并且，總供給〔75+75+45=195〕>總需求〔20+30+30+40=120〕。其數(shù)學(xué)模型如下：設(shè)xij為工廠i生產(chǎn)產(chǎn)品j的數(shù)量4.3各種運(yùn)輸問(wèn)題變形的建模例4.4的電子表格模型產(chǎn)品4分在2個(gè)工廠生產(chǎn)4.3各種運(yùn)輸問(wèn)題變形的建模例4.5某公司在3個(gè)工廠中專門生產(chǎn)一種產(chǎn)品。在未來(lái)的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è)工廠供給哪個(gè)顧客〔見(jiàn)表4－8〕。問(wèn)應(yīng)向每一個(gè)顧客供給多少貨物，以使公司總利潤(rùn)最大？表4－8工廠供給顧客的相關(guān)數(shù)據(jù)單位利潤(rùn)（元）產(chǎn)量顧客1顧客2顧客3顧客4工廠1554246538000工廠2371832485000工廠3295951357000最小采購(gòu)量7000300020000最大采購(gòu)量70009000600080004.3各種運(yùn)輸問(wèn)題變形的建模解：該問(wèn)題要求滿足不同顧客的需求〔采購(gòu)量〕，解決方法：實(shí)際供給量最小采購(gòu)量實(shí)際供給量最大采購(gòu)量

目標(biāo)是利潤(rùn)最大，而不是本錢最小。其數(shù)學(xué)模型如下：設(shè)xij為工廠i供給給顧客j的產(chǎn)品數(shù)量4.3各種運(yùn)輸問(wèn)題變形的建模例4.5的電子表格模型4.4運(yùn)輸問(wèn)題應(yīng)用舉例例4.6某廠生產(chǎn)設(shè)備是以銷定產(chǎn)的。1～6月份各月的生產(chǎn)能力、合同銷量和單臺(tái)設(shè)備平均生產(chǎn)費(fèi)用，如表4－9所示。上年末庫(kù)存103臺(tái)。如果當(dāng)月生產(chǎn)出來(lái)的設(shè)備當(dāng)月不交貨，那么需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸本錢0.1萬(wàn)元，每臺(tái)設(shè)備每月的平均倉(cāng)儲(chǔ)費(fèi)、維護(hù)費(fèi)為0.2萬(wàn)元。7～8月份為銷售淡季，全廠停產(chǎn)1個(gè)月，因此在6月份完成銷售合同后還要留出庫(kù)存80臺(tái)。加班生產(chǎn)設(shè)備每臺(tái)增加本錢1萬(wàn)元。問(wèn)應(yīng)如何安排1～6月份的生產(chǎn)，使總的生產(chǎn)〔包括運(yùn)輸、倉(cāng)儲(chǔ)、維護(hù)〕費(fèi)用最少？月份正常生產(chǎn)能力（臺(tái)）加班生產(chǎn)能力（臺(tái)）合同銷量（臺(tái)）單臺(tái)費(fèi)用（萬(wàn)元）1月6010104152月501075143月902011513.54月10040160135月10040103136月80407013.54.4運(yùn)輸問(wèn)題應(yīng)用舉例解：這是一個(gè)生產(chǎn)與儲(chǔ)存問(wèn)題，但可以轉(zhuǎn)化為運(yùn)輸問(wèn)題來(lái)做?！彩欠窨梢圆捎玫?章的方法做？同學(xué)們可以試試，然后進(jìn)行比較〕生產(chǎn)方案不變，但總費(fèi)用為：8329.7萬(wàn)元根據(jù)條件可以列出生產(chǎn)能力〔正常生產(chǎn)能力和加班生產(chǎn)能力〕和銷量以及運(yùn)價(jià)表〔P120〕數(shù)學(xué)模型P120－121電子表格模型P122求解結(jié)果P1234.4運(yùn)輸問(wè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)系以保證將來(lái)的市場(chǎng)區(qū)域份額，另一方面，面臨如何將剩余的90%的產(chǎn)量合理分配給五個(gè)石材主產(chǎn)區(qū)和其他省區(qū)，以獲取最大的利潤(rùn)。各個(gè)銷售區(qū)的最低需求、銷售固定費(fèi)用、每片平均運(yùn)費(fèi)、每片從總廠庫(kù)房的購(gòu)進(jìn)價(jià)與當(dāng)?shù)氐匿N售價(jià)差奉獻(xiàn)等自然情況見(jiàn)表4－12。問(wèn)應(yīng)如何分配給各個(gè)銷售區(qū)，才能使得總利潤(rùn)為最大？4.4運(yùn)輸問(wèn)題應(yīng)用舉例解：該問(wèn)題數(shù)據(jù)較多，但是經(jīng)過(guò)分析，其產(chǎn)量在最低需求和最高需求之間，并且目標(biāo)函數(shù)是最大利潤(rùn)，可以化簡(jiǎn)為表4－13〔P124〕數(shù)學(xué)模型P124電子表格模型P125求解結(jié)果P1264.5指派問(wèn)題在現(xiàn)實(shí)生活中，經(jīng)常會(huì)遇到指派人員做某項(xiàng)工作〔任務(wù)〕的情況。指派問(wèn)題的許多應(yīng)用是用來(lái)幫助管理人員解決如何為一項(xiàng)即將開(kāi)展的工作指派人員的問(wèn)題。其他的一些應(yīng)用如為工作指派機(jī)器、設(shè)備或工廠等。指派問(wèn)題也稱分配問(wèn)題，主要研究人和工作〔任務(wù)〕間如何匹配，以使所有工作完成的效率實(shí)現(xiàn)最優(yōu)化。形式上，指派問(wèn)題給定了一系列所要完成的工作以及一系列完成工作的人員，所需要解決的問(wèn)題就是要確定出指派哪個(gè)人去完成哪項(xiàng)工作。4.5指派問(wèn)題指派問(wèn)題的假設(shè)：〔1〕人的數(shù)量和工作的數(shù)量相等；〔2〕每個(gè)人只能完成一項(xiàng)工作；〔3〕每項(xiàng)工作只能由一個(gè)人來(lái)完成；〔4〕每個(gè)人和每項(xiàng)工作的組合都會(huì)有一個(gè)相關(guān)的本錢〔單位本錢〕；〔5〕目標(biāo)是要確定如何指派才能使總本錢最小。4.5指派問(wèn)題設(shè)決策變量xij為第i個(gè)人做第j項(xiàng)工作，而目標(biāo)函數(shù)系數(shù)cij為第i個(gè)人完成第j項(xiàng)工作所需要的單位本錢。平衡指派問(wèn)題的數(shù)學(xué)模型為4.5指派問(wèn)題需要說(shuō)明的是：指派問(wèn)題實(shí)際上是一種特殊的運(yùn)輸問(wèn)題。其中出發(fā)地是人，目的地是工作。只不過(guò)，每一個(gè)出發(fā)地的供給量都為1〔因?yàn)槊總€(gè)人都要完成一項(xiàng)工作〕，每一個(gè)目的地的需求量都為1〔因?yàn)槊宽?xiàng)工作都要完成〕。由于運(yùn)輸問(wèn)題有“整數(shù)解性質(zhì)〞，因此，沒(méi)有必要加上所有決策變量都是0-1變量的約束。指派問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，有一種快捷的求解方法：匈牙利方法〔HungarianMethod〕，但Excel的“規(guī)劃求解〞還是采用“單純形法〞來(lái)求解。4.5指派問(wèn)題例4.8某公司的營(yíng)銷經(jīng)理將要主持召開(kāi)一年一度的由營(yíng)銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會(huì)議。為了更好地安排這次會(huì)議，他安排小張、小王、小李、小劉等四個(gè)人，每個(gè)人負(fù)責(zé)完成下面的一項(xiàng)工作：A、B、C和D。由于每個(gè)人完成每項(xiàng)任務(wù)的時(shí)間和工資不同〔如表4－14所示〕。問(wèn)如何指派，可使總本錢最小。人員每一項(xiàng)工作所需要的時(shí)間（小時(shí)）每小時(shí)工資（元）工作A工作B工作C工作D小張3541274014小王4745325112小李3956364313小劉32512546154.5指派問(wèn)題解：該問(wèn)題是一個(gè)典型的指派問(wèn)題。單位本錢為每個(gè)人做每項(xiàng)工作的總工資目標(biāo)是要確定哪個(gè)人做哪一項(xiàng)工作，使總本錢最小供給量為1代表每個(gè)人都只能完成一項(xiàng)工作需求量為1代表每項(xiàng)工作也只能有一個(gè)人來(lái)完成總?cè)藬?shù)〔4人〕和總?cè)蝿?wù)數(shù)〔4項(xiàng)〕相等4.5指派問(wèn)題數(shù)學(xué)模型：設(shè)xij為指派人員i去做工作j〔i，j＝1,2,3,4)4.5指派問(wèn)題電子表格模型4.6各種指派問(wèn)題變形的建模經(jīng)常會(huì)遇到指派問(wèn)題的變形，之所以稱它們?yōu)樽冃危且驗(yàn)樗鼈兌疾粷M足平衡指派問(wèn)題所有假設(shè)之中的一個(gè)或者多個(gè)。一般考慮下面的一些特征：〔1〕有些人并不能進(jìn)行某項(xiàng)工作〔相應(yīng)的xij＝0〕;〔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ù)不超過(guò)總?cè)藬?shù)也不超過(guò)總?cè)蝿?wù)數(shù)。4.6各種指派問(wèn)題變形的建模例4.9題目見(jiàn)例4.4，即某公司需要安排三個(gè)工廠來(lái)生產(chǎn)四種新產(chǎn)品，相關(guān)的數(shù)據(jù)在表4－7中已經(jīng)給出。在例4.4中，允許產(chǎn)品生產(chǎn)分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的隱性本錢〔包括額外的設(shè)置、配送和管理本錢等〕。因此，管理人員決定在禁止產(chǎn)品生產(chǎn)分解發(fā)生的情況下對(duì)問(wèn)題進(jìn)行分析。 新問(wèn)題描述為：如表4－7所示的數(shù)據(jù)，問(wèn)如何把每一個(gè)工廠指派給至少一個(gè)新產(chǎn)品〔每一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)〕，使總本錢到達(dá)最?。?.6各種指派問(wèn)題變形的建模解：該問(wèn)題可視為指派工廠生產(chǎn)產(chǎn)品問(wèn)題，工廠可以看作指派問(wèn)題中的人，產(chǎn)品那么可以看作需要完成的工作〔任務(wù)〕。由于有四種產(chǎn)品和三個(gè)工廠，所以就有兩個(gè)工廠各只能生產(chǎn)一種新產(chǎn)品，第三個(gè)工廠生產(chǎn)兩種新產(chǎn)品。只有工廠1和工廠2有生產(chǎn)兩種產(chǎn)品的能力。這里涉及如何把運(yùn)輸問(wèn)題轉(zhuǎn)換為指派問(wèn)題，關(guān)鍵所在是數(shù)據(jù)轉(zhuǎn)換。4.6各種指派問(wèn)題變形的建模數(shù)據(jù)轉(zhuǎn)換：〔1〕單位指派本錢:原來(lái)的單位本錢轉(zhuǎn)換成整批本錢〔＝單位本錢×需求量〕，即單位指派本錢為每個(gè)工廠生產(chǎn)每種產(chǎn)品的本錢?！?〕供給量和需求量的轉(zhuǎn)換問(wèn)題：三個(gè)工廠生產(chǎn)四種產(chǎn)品，但一種產(chǎn)品只能在一個(gè)工廠生產(chǎn)，根據(jù)生產(chǎn)能力，工廠3只能生產(chǎn)一種產(chǎn)品〔供給量為1〕，而工廠1和工廠2可以生產(chǎn)2種產(chǎn)品〔供給量為2〕，而產(chǎn)品的需求量為1。還有“總供給〔2+2+1=5〕>總需求〔1+1+1+1=4〕〞,為人多事少的指派問(wèn)題。4.6各種指派問(wèn)題變形的建模數(shù)學(xué)模型：設(shè)xij為指派工廠i生產(chǎn)產(chǎn)品j〔i=1,2,3;j=1,2,3,4)4.6各種指派問(wèn)題變形的建模電子表格模型4.6各種指派問(wèn)題變形的建模例4.10一家制藥公司，為了提升企業(yè)的競(jìng)爭(zhēng)力，決定加大科研力度。在研究了市場(chǎng)的需要，分析了當(dāng)前藥物的缺乏并且拜會(huì)了大量對(duì)有良好前景的醫(yī)藥領(lǐng)域進(jìn)行研究的科學(xué)家之后，決定由五位科學(xué)家開(kāi)發(fā)五個(gè)工程。為了保證這些科學(xué)家都能夠到他們感興趣的工程中去，為此建立了一個(gè)投標(biāo)系統(tǒng)。這五位科學(xué)家每個(gè)人都有1000點(diǎn)的投標(biāo)點(diǎn)。他們向每一個(gè)工程投標(biāo)，并且把較多的投標(biāo)點(diǎn)投向自己最感興趣的工程中。表4－15顯示了這5位科學(xué)家進(jìn)行投標(biāo)的情況。4.6各種指派問(wèn)題變形的建模表4－15科學(xué)家工程投標(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各種指派問(wèn)題變形的建模分析：決定要對(duì)一些可能發(fā)生的情況進(jìn)行評(píng)估?！?〕根據(jù)所給出的投標(biāo)情況，需要為每一個(gè)工程指派一位資深的科學(xué)家并且使得科學(xué)家的總滿意度最高。那么應(yīng)當(dāng)怎樣進(jìn)行指派？〔人數(shù)與工程數(shù)相等〕P133－134〔2〕羅林博士接到了北大醫(yī)學(xué)院的邀請(qǐng)去完成一個(gè)教學(xué)任務(wù)，而公司卻非常想把她留下來(lái)。但是北大的聲望會(huì)使她離開(kāi)公司。如果這種情況真的發(fā)生的話，公司就只有放棄那個(gè)最缺乏熱情的工程。公司應(yīng)當(dāng)放棄那一個(gè)工程？〔人少工程多〕P134－1354.6各種指派問(wèn)題變形的建?！?〕當(dāng)然公司并不愿意放棄任何一個(gè)工程。公司決定讓朱諾博士或者王凱博士同時(shí)領(lǐng)導(dǎo)兩個(gè)工程。在只有4位科學(xué)家的情況下，讓哪一位科學(xué)家領(lǐng)導(dǎo)哪一個(gè)工程才能使得對(duì)工程的熱情最大？〔有人可以同時(shí)領(lǐng)導(dǎo)兩個(gè)工程〕P134，136〔4〕還是來(lái)分析擁有5位科學(xué)家的情況，但由于各方面的原因，有三位科學(xué)家不能領(lǐng)導(dǎo)幾個(gè)特定的工程，具體如表4－16〔P137〕所示。由于不能領(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)全部投到他自己最感興趣的工程上。在這種情況下，讓哪個(gè)科學(xué)家領(lǐng)導(dǎo)哪個(gè)工程才能使得對(duì)工程的總熱情最大？〔有人不能領(lǐng)導(dǎo)幾個(gè)特