運輸問題和指派問題TheTransportationandAssignmentProblems本章內(nèi)容要點運輸問題的基本概念及其各種變形的建模與應(yīng)用指派問題的基本概念及其各種變形的建模與應(yīng)用本章節(jié)內(nèi)容1運輸問題基本概念2運輸問題數(shù)學(xué)模型和電子表格模型3各種變形的運輸問題建模4運輸問題應(yīng)用舉例5指派問題6各種變形的指派問題建模本章主要內(nèi)容框架圖1運輸問題運輸問題最初起源于人們在日常生活中把某些物品或人們自身從一些地方轉(zhuǎn)移到另一些地方，要求所采用的運輸路線或運輸方案是最經(jīng)濟或成本最低的，這就成為了一個運籌學(xué)問題。隨著經(jīng)濟的不斷發(fā)展，現(xiàn)代物流業(yè)蓬勃發(fā)展，如何充分利用時間、信息、倉儲、配送和聯(lián)運體系創(chuàng)造更多的價值，向運籌學(xué)提出了更高的挑戰(zhàn)。要求科學(xué)地組織貨源、運輸和配送使得運輸問題變得日益復(fù)雜，但是其基本思想仍然是實現(xiàn)現(xiàn)有資源的最優(yōu)化配置。1運輸問題基本概念一般的運輸問題就是解決如何把某種產(chǎn)品從若干個產(chǎn)地調(diào)運到若干個銷地，在每個產(chǎn)地的供應(yīng)量和每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。平衡運輸問題的條件：1. 明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應(yīng)量（產(chǎn)量）、需求量（銷量）和單位成本。2. 需求假設(shè)：每一個出發(fā)地都有一個固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。與之類似，每一個目的地都有一個固定的需求量，整個需求量都必須由出發(fā)地滿足。即“總供應(yīng)＝總需求”。3. 成本假設(shè)：從任何一個出發(fā)地到任何一個目的地的貨物配送成本與所配送的數(shù)量成線性比例關(guān)系，因此成本就等于配送的單位成本乘以所配送的數(shù)量（目標(biāo)函數(shù)是線性的）。1運輸問題基本概念例1某公司有三個加工廠A1、A2、A3生產(chǎn)某產(chǎn)品，每日的產(chǎn)量分別為：7噸、4噸、9噸；該公司把這些產(chǎn)品分別運往四個銷售點B1、B2、B3、B4，各銷售點每日銷量分別為：3噸、6噸、5噸、6噸；從各工廠到各銷售點的單位產(chǎn)品運價如表1所示。問該公司應(yīng)如何調(diào)運這些產(chǎn)品，在滿足各銷售點的需要量的前提下，使總運費最少？

表1各工廠到各銷售點的單位產(chǎn)品運價（元/噸）B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059銷量（噸）3656對于例1，其數(shù)學(xué)模型如下：首先，三個產(chǎn)地A1、A2、A3的總產(chǎn)量為7＋4＋9＝20；四個銷地B1、B2、B3、B4的總銷量為3＋6＋5＋6＝20。由于總產(chǎn)量等于總銷量，故該問題是一個產(chǎn)銷平衡的運輸問題。(1)決策變量設(shè)xij為從產(chǎn)地Ai運往銷地Bj的運輸量(i＝1,2,3;j=1,2,3,4)

（2）目標(biāo)函數(shù)本問題的目標(biāo)是使得總運輸費最?。?）約束條件①滿足產(chǎn)地產(chǎn)量（3個產(chǎn)地的產(chǎn)品都要全部配送出去）②滿足銷地銷量（4個銷地的產(chǎn)品都要全部得到滿足）③非負(fù)2運輸問題數(shù)學(xué)模型和電子表格模型運輸問題是一種特殊的線性規(guī)劃問題，一般采用“表上作業(yè)法”求解運輸問題，但Excel的“規(guī)劃求解”工具還是采用“單純形法”來求解。例1的電子表格模型2運輸問題數(shù)學(xué)模型和電子表格模型（1）產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型具有m個產(chǎn)地Ai（i＝1,2,,m）和n個銷地

Bj（j＝1,2,,n）的運輸問題的數(shù)學(xué)模型為2運輸問題數(shù)學(xué)模型和電子表格模型需要注意的是：運輸問題有這樣一個性質(zhì)（整數(shù)解性質(zhì)），只要它的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運輸問題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件。由于運輸量經(jīng)常以卡車、集裝箱等為單位，如果卡車不能裝滿的話，就很不經(jīng)濟了。整數(shù)解性質(zhì)就避免了運輸量（運輸方案）為小數(shù)的麻煩。2運輸問題數(shù)學(xué)模型和電子表格模型（2）產(chǎn)大于銷（供過于求）運輸問題的數(shù)學(xué)模型（以滿足小的銷量為準(zhǔn)）2運輸問題數(shù)學(xué)模型和電子表格模型（3）銷大于產(chǎn)（供不應(yīng)求）運輸問題的數(shù)學(xué)模型（以滿足小的產(chǎn)量為準(zhǔn)）2運輸問題數(shù)學(xué)模型和電子表格模型例2某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10，15，25，20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如表所示。如果生產(chǎn)出來的柴油機當(dāng)季不交貨的，每臺每積壓一個季度需儲存、維護等費用1500元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)（包括儲存、維護）費用最小的決策。各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本季度生產(chǎn)能力（臺）單位成本（萬元）12510.823511.133011.041011.32運輸問題數(shù)學(xué)模型和電子表格模型解：這是一個生產(chǎn)與儲存（庫存）問題，可以轉(zhuǎn)化為運輸問題來做。由于每個季度生產(chǎn)出來的柴油機不一定當(dāng)季交貨，所以設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機數(shù)。則第i季度生產(chǎn)的第j季度交貨的每臺柴油機的實際成本cij為：

cij=第i季度每臺的生產(chǎn)成本+0.15(j-i)（儲存、維護等費用）把第i季度生產(chǎn)的柴油機數(shù)看作第i個生產(chǎn)廠商的產(chǎn)量；把第j季度交貨的柴油機數(shù)看作第j個銷售點的銷量；生產(chǎn)成本加儲存、維護等費用看作運費。將生產(chǎn)與儲存問題轉(zhuǎn)化為運輸問題，相關(guān)數(shù)據(jù)見表。2運輸問題數(shù)學(xué)模型和電子表格模型

柴油機生產(chǎn)的相關(guān)數(shù)據(jù)由表可知，總產(chǎn)量（生產(chǎn)能力）為25+35+30+10=100，總銷量（需求量）為10+15+25+20=70，因此是產(chǎn)大于銷的運輸問題。1234生產(chǎn)能力110.810.9511.1011.2525211.1011.2511.4035311.0011.1530411.3010需求量101525202運輸問題數(shù)學(xué)模型和電子表格模型該生產(chǎn)與儲存問題（轉(zhuǎn)化為產(chǎn)大于銷的運輸問題）的數(shù)學(xué)模型為2運輸問題數(shù)學(xué)模型和電子表格模型例2的電子表格模型2運輸問題數(shù)學(xué)模型和電子表格模型例3

某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表所示。問應(yīng)如何調(diào)運，可使得總運輸費最小？例3運輸費用表

B1B2B3產(chǎn)量A113151278A211292245銷量533665（銷大于產(chǎn)）2運輸問題數(shù)學(xué)模型和電子表格模型解：由表知，總產(chǎn)量為78+45=123，總銷量為53+36+65=154，銷大于產(chǎn)(供不應(yīng)求)。數(shù)學(xué)模型如下：設(shè)xij為產(chǎn)地Ai運往銷地Bj的物品數(shù)量2運輸問題數(shù)學(xué)模型和電子表格模型例3的電子表格模型3各種變形的運輸問題建?，F(xiàn)實生活中符合產(chǎn)銷平衡運輸問題每一個條件的情況很少。一個特征近似但其中的一個或者幾個特征卻并不符合產(chǎn)銷平衡運輸問題條件的運輸問題卻經(jīng)常出現(xiàn)。下面是要討論的一些特征：（1）總供應(yīng)大于總需求。每一個供應(yīng)量（產(chǎn)量）代表了從其出發(fā)地中配送出去的最大數(shù)量（而不是一個固定的數(shù)值,≤）。（2）總供應(yīng)小于總需求。每一個需求量（銷量）代表了在其目的地中所接收到的最大數(shù)量（而不是一個固定的數(shù)值,≤）。（3）一個目的地同時存在著最小需求和最大需求，于是所有在這兩個數(shù)值之間的數(shù)量都是可以接收的（≥,≤）。（4）在配送中不能使用特定的出發(fā)地—目的地組合（xij=0）。（5）目標(biāo)是使與配送數(shù)量有關(guān)的總利潤最大而不是使總成本最小。（Min－>Max）3各種變形的運輸問題建模例4

某公司決定使用三個有生產(chǎn)余力的工廠進行四種新產(chǎn)品的生產(chǎn)。每單位產(chǎn)品需要等量的工作，所以工廠的有效生產(chǎn)能力以每天生產(chǎn)的任意種產(chǎn)品的數(shù)量來衡量（見表的最右列）。而每種產(chǎn)品每天有一定的需求量（見表的最后一行）。每家工廠都可以制造這些產(chǎn)品，除了工廠2不能生產(chǎn)產(chǎn)品3以外。然而，每種產(chǎn)品在不同工廠中的單位成本是有差異的（如表所示）。現(xiàn)在需要決定的是在哪個工廠生產(chǎn)哪種產(chǎn)品，可使總成本最小。表

產(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需求量203030403各種變形的運輸問題建模解：指定工廠生產(chǎn)產(chǎn)品可以看作運輸問題來求解。本題中，工廠2不能生產(chǎn)產(chǎn)品3，這樣可以增加約束條件

；并且，總供應(yīng)x23＝0（75+75+45=195）>總需求（20+30+30+40=120）。其數(shù)學(xué)模型如下：設(shè)xij為工廠i生產(chǎn)產(chǎn)品j的數(shù)量3各種變形的運輸問題建模例4的電子表格模型產(chǎn)品4分在2個工廠生產(chǎn)3各種變形的運輸問題建模例5

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

最小采購量實際供給量

最大采購量

目標(biāo)是利潤最大，而不是成本最小。其數(shù)學(xué)模型如下：設(shè)xij為工廠i供應(yīng)給顧客j的產(chǎn)品數(shù)量3各種變形的運輸問題建模例5的電子表格模型4運輸問題應(yīng)用舉例例6

某廠生產(chǎn)設(shè)備是以銷定產(chǎn)的。已知1～6月份各月的生產(chǎn)能力、合同銷量和單臺設(shè)備平均生產(chǎn)費用，如表所示。已知上年末庫存103臺。如果當(dāng)月生產(chǎn)出來的設(shè)備當(dāng)月不交貨，則需要運到分廠庫房，每臺增加運輸成本0.1萬元，每臺設(shè)備每月的平均倉儲費、維護費為0.2萬元。7～8月份為銷售淡季，全廠停產(chǎn)1個月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)設(shè)備每臺增加成本1萬元。問應(yīng)如何安排1～6月份的生產(chǎn)，使總的生產(chǎn)（包括運輸、倉儲、維護）費用最少？月份正常生產(chǎn)能力（臺）加班生產(chǎn)能力（臺）合同銷量（臺）單臺費用（萬元）1月6010104152月501075143月902011513.54月10040160135月10040103136月80407013.54運輸問題應(yīng)用舉例例7

華中金剛石鋸片廠有兩條生產(chǎn)線，分別生產(chǎn)直徑900-1800mm大鋸片基體20000片，直徑350-800mm中小鋸片基體40000片。公司在全國有25個銷售網(wǎng)點，主要銷售區(qū)域集中在福建、廣東、廣西、四川、山東5個石材主產(chǎn)區(qū)。為完成總廠的要求，公司決定一方面拿出10%的產(chǎn)量穩(wěn)定與前期各個客戶的聯(lián)系以保證將來的市場區(qū)域份額，另一方面，面臨如何將剩余的90%的產(chǎn)量合理分配給五個石材主產(chǎn)區(qū)和其他省區(qū)，以獲取最大的利潤。各個銷售區(qū)的最低需求、銷售固定費用、每片平均運費、每片從總廠庫房的購進價與當(dāng)?shù)氐匿N售價差貢獻(xiàn)等自然情況見表。問應(yīng)如何分配給各個銷售區(qū)，才能使得總利潤為最大？4運輸問題應(yīng)用舉例5指派問題在現(xiàn)實生活中，經(jīng)常會遇到指派人員做某項工作（任務(wù)）的情況。指派問題的許多應(yīng)用是用來幫助管理人員解決如何為一項即將開展的工作指派人員的問題。其他的一些應(yīng)用如為工作指派機器、設(shè)備或工廠等。指派問題也稱分配問題，主要研究人和工作（任務(wù)）間如何匹配，以使所有工作完成的效率實現(xiàn)最優(yōu)化。形式上，指派問題給定了一系列所要完成的工作以及一系列完成工作的人員，所需要解決的問題就是要確定出指派哪個人去完成哪項工作。5指派問題指派問題的假設(shè)：（1）人的數(shù)量和工作的數(shù)量相等；（2）每個人只能完成一項工作；（3）每項工作只能由一個人來完成；（4）每個人和每項工作的組合都會有一個相關(guān)的成本（單位成本）；（5）目標(biāo)是要確定如何指派才能使總成本最小。5指派問題設(shè)決策變量xij為第i個人做第j項工作，而已知目標(biāo)函數(shù)系數(shù)cij為第i個人完成第j項工作所需要的單位成本。平衡指派問題的數(shù)學(xué)模型為5指派問題需要說明的是：指派問題實際上是一種特殊的運輸問題。其中出發(fā)地是人，目的地是工作。只不過，每一個出發(fā)地的供應(yīng)量都為1（因為每個人都要完成一項工作），每一個目的地的需求量都為1（因為每項工作都要完成）。由于運輸問題有“整數(shù)解性質(zhì)”，因此，沒有必要加上所有決策變量都是0-1變量的約束。指派問題是一種特殊的線性規(guī)劃問題，有一種快捷的求解方法：匈牙利方法（HungarianMethod），但Excel的“規(guī)劃求解”工具還是采用“單純形法”來求解。5指派問題例8

某公司的營銷經(jīng)理將要主持召開一年一度的由營銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會議。為了更好地安排這次會議，他安排小張、小王、小李、小劉等四個人，每個人負(fù)責(zé)完成下面的一項工作：A、B、C和D。由于每個人完成每項任務(wù)的時間和工資不同（如表所示）。問如何指派，可使總成本最小。人員每一項工作所需要的時間（小時）每小時工資（元）工作A工作B工作C工作D小張3541274014小王4745325112小李3956364313小劉32512546155指派問題解：該問題是一個典型的指派問題。單位成本為每個人做每項工作的總工資目標(biāo)是要確定哪個人做哪一項工作，使總成本最小供應(yīng)量為1代表每個人都只能完成一項工作需求量為1代表每項工作也只能有一個人來完成總?cè)藬?shù)（4人）和總?cè)蝿?wù)數(shù)（4項）相等5指派問題數(shù)學(xué)模型：設(shè)xij為指派人員i去做工作j（i，j＝1,2,3,4)5指派問題電子表格模型6各種變形的指派問題建模經(jīng)常會遇到指派問題的變形，之所以稱它們?yōu)樽冃?，是因為它們都不滿足平衡指派問題所有假設(shè)之中的一個或者多個。一般考慮下面的一些特征：（1）有些人并不能進行某項工作（相應(yīng)的xij＝0）;（2）雖然每個人完成一項任務(wù)，但是任務(wù)比人多(人少事多);（3）雖然每一項任務(wù)只由一個人完成，但是人比任務(wù)多（人多事少）；（4）某人可以同時被指派給多個任務(wù)（一人可做幾件事）；（5）某事可以由多人共同完成（一事可由多人完成）；（6）目標(biāo)是與指派有關(guān)的總利潤最大而不是使總成本最??；（7）實際需要完成任務(wù)數(shù)不超過總?cè)藬?shù)也不超過總?cè)蝿?wù)數(shù)。6各種變形的指派問題建模例9

題目見例4，即某公司需要安排三個工廠來生產(chǎn)四種新產(chǎn)品，相關(guān)的數(shù)據(jù)在例4表4中已經(jīng)給出。在例4中，允許產(chǎn)品生產(chǎn)分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的隱性成本（包括額外的設(shè)置、配送和管理成本等）。因此，管理人員決定在禁止產(chǎn)品生產(chǎn)分解發(fā)生的情況下對問題進行分析。 新問題描述為：已知如表所示的數(shù)據(jù)，問如何把每一個工廠指派給至少一個新產(chǎn)