運籌學中的運輸問題演示文稿

運籌學中的運輸問題演示文稿第一頁，共四十六頁。本章內容要點運輸問題的基本概念及其各種變形的建模與應用指派問題的基本概念及其各種變形的建模與應用第二頁，共四十六頁。本章節(jié)內容1運輸問題基本概念2運輸問題數(shù)學模型和電子表格模型3各種變形的運輸問題建模4運輸問題應用舉例5指派問題6各種變形的指派問題建模第三頁，共四十六頁。產(chǎn)大于銷（總產(chǎn)量大于總銷量）運輸問題數(shù)學模型和電子表格模型各種變形的建模應用舉例指派問題數(shù)學模型和電子表格模型本章主要內容框架圖產(chǎn)銷平衡（總產(chǎn)量等于總銷量）銷大于產(chǎn)（總產(chǎn)量小于總銷量）運輸問題和指派問題平衡指派問題（總人數(shù)等于總任務數(shù)）各種變形的建模第四頁，共四十六頁。1運輸問題運輸問題最初起源于人們在日常生活中把某些物品或人們自身從一些地方轉移到另一些地方，要求所采用的運輸路線或運輸方案是最經(jīng)濟或成本最低的，這就成為了一個運籌學問題。隨著經(jīng)濟的不斷發(fā)展，現(xiàn)代物流業(yè)蓬勃發(fā)展，如何充分利用時間、信息、倉儲、配送和聯(lián)運體系創(chuàng)造更多的價值，向運籌學提出了更高的挑戰(zhàn)。要求科學地組織貨源、運輸和配送使得運輸問題變得日益復雜，但是其基本思想仍然是實現(xiàn)現(xiàn)有資源的最優(yōu)化配置。第五頁，共四十六頁。1運輸問題基本概念一般的運輸問題就是解決如何把某種產(chǎn)品從若干個產(chǎn)地調運到若干個銷地，在每個產(chǎn)地的供應量和每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。平衡運輸問題的條件：

1.明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應量（產(chǎn)量）、需求 量（銷量）和單位成本。

2.需求假設：每一個出發(fā)地都有一個固定的供應量，所有的供應量 都必須配送到目的地。與之類似，每一個目的地都有一個固定的 需求量，整個需求量都必須由出發(fā)地滿足。即“總供應＝總需 求”。

3.成本假設：從任何一個出發(fā)地到任何一個目的地的貨物配送成本 與所配送的數(shù)量成線性比例關系，因此成本就等于配送的單位成 本乘以所配送的數(shù)量（目標函數(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所示。問該公司應如何調運這些產(chǎn)品，在滿足各銷售點的需要量的前提下，使總運費最少？

表1各工廠到各銷售點的單位產(chǎn)品運價（元/噸）B1B2B3B4產(chǎn)量（噸）749A1A2A3銷量（噸）3173119463210510856第七頁，共四十六頁。對于例1，其數(shù)學模型如下：

首先，三個產(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)決策變量設xij為從產(chǎn)地Ai運往銷地Bj的運輸量(i＝1,2,3;j=1,2,3,4)（2）目標函數(shù)本問題的目標是使得總運輸費最小Minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34第八頁，共四十六頁。（3）約束條件①滿足產(chǎn)地產(chǎn)量 （3個產(chǎn)地的產(chǎn) 品都要全部配 送出去）②滿足銷地銷量 （4個銷地的產(chǎn) 品都要全部得 到滿足）③非負第九頁，共四十六頁。2運輸問題數(shù)學模型和電子表格模型運輸問題是一種特殊的線性規(guī)劃問題，一般采用“表上作業(yè)法”求解運輸問題，但Excel的“規(guī)劃求解”工具還是采用“單純形法”來求解。例1的電子表格模型第十頁，共四十六頁。2運輸問題數(shù)學模型和電子表格模型（1）產(chǎn)銷平衡運輸問題的數(shù)學模型 具有m個產(chǎn)地Ai（i＝1,2,…,m）和n個銷地

Bj（j＝1,2,…,n）的運輸問題的數(shù)學模型為第十一頁，共四十六頁。2運輸問題數(shù)學模型和電子表格模型需要注意的是：運輸問題有這樣一個性質（整數(shù)解性質），只要它的供應量和需求量都是整數(shù)，任何有可行解的運輸問題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件。由于運輸量經(jīng)常以卡車、集裝箱等為單位，如果卡車不能裝滿的話，就很不經(jīng)濟了。整數(shù)解性質就避免了運輸量（運輸方案）為小數(shù)的麻煩。第十二頁，共四十六頁。第十三頁，共四十六頁。（以滿足小的產(chǎn)量為準）ij=（3）銷大于產(chǎn)（供不應求）運輸問題第十四頁，共四十六頁。

2運輸問題數(shù)學模型和電子表格模型例2某廠按合同規(guī)定須于當年每個季度末分別提供10，15，25，20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如表所示。如果生產(chǎn)出來的柴油機當季不交貨的，每臺每積壓一個季度需儲存、維護等費用1500元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)（包括儲存、維護）費用最小的決策。

各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本季度生產(chǎn)能力（臺）單位成本（萬元）12342535301010.811.111.011.3第十五頁，共四十六頁。2運輸問題數(shù)學模型和電子表格模型解：這是一個生產(chǎn)與儲存（庫存）問題，可以轉化為運輸問題來做。由于每個季度生產(chǎn)出來的柴油機不一定當季交貨，所以設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)與儲存問題轉化為運輸問題，相關數(shù)據(jù)見表。第十六頁，共四十六頁。2運輸問題數(shù)學模型和電子表格模型

柴油機生產(chǎn)的相關數(shù)據(jù)

由表可知，總產(chǎn)量（生產(chǎn)能力）為

25+35+30+10=100，總銷量（需求量）為10+15+25+20=70，因此是產(chǎn)大于銷的運輸問題。1234生產(chǎn)能力10.810.9511.1012311.1011.2511.0011.2511.40113010需求量10152520第十七頁，共四十六頁。該生產(chǎn)與儲存問題（轉化為產(chǎn)大于銷的運輸問題）的數(shù)學模型為2運輸問題數(shù)學模型和電子表格模型

Minz=10.80x11+10.95x12+11.10x13+11.25x14

+11.10x22+11.25x23+11.40x24

+11.00x33+11.15x34+11.30x44第十八頁，共四十六頁。2運輸問題數(shù)學模型和電子表格模型例2的電子表格模型第十九頁，共四十六頁。

2運輸問題數(shù)學模型和電子表格模型例3某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表所示。問應如何調運，可使得總運輸費最?。?/p>

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

單位成本（元） 生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4757545工廠1工廠2工廠3需求量414037202729303028－273024232140第二十四頁，共四十六頁。解：指定工廠生產(chǎn)產(chǎn)品可以看作運輸問題來求解。本題中，工廠2不能生產(chǎn)產(chǎn)品3，這樣可以增加約束條件；并且，總供應x23＝0（75+75+45=195）>總需求（20+30+30+40=120）。其數(shù)學模型如下： 設xij為工廠i生產(chǎn)產(chǎn)品j的數(shù)量3各種變形的運輸問題建模第二十五頁，共四十六頁。3各種變形的運輸問題建模例4的電子表格模型產(chǎn)品4分在2個工廠生產(chǎn)第二十六頁，共四十六頁。

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

例6某廠生產(chǎn)設備是以銷定產(chǎn)的。已知1～6月份各月的生產(chǎn)能力、合 同銷量和單臺設備平均生產(chǎn)費用，如表所示。 已知上年末庫存103臺。如果當月生產(chǎn)出來的設備當月不交貨，則 需要運到分廠庫房，每臺增加運輸成本0.1萬元，每臺設備每月的平均 倉儲費、維護費為0.2萬元。7～8月份為銷售淡季，全廠停產(chǎn)1個月， 因此在6月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)設備每臺增 加成本1萬元。問應如何安排1～6月份的生產(chǎn)，使總的生產(chǎn)（包括運輸、 倉儲、維護）費用最少？月份1月2月3月4月5月6月正常生產(chǎn)能力（臺）60509010010080加班生產(chǎn)能力（臺）101020404040合同銷量（臺）1047511516010370單臺費用（萬元）151413.5131313.5第三十頁，共四十六頁。4運輸問題應用舉例例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ū)的最低需求、銷售固定費用、每片平均運費、每片從總廠庫房的購進價與當?shù)氐匿N售價差貢獻等自然情況見表。問應如何分配給各個銷售區(qū)，才能使得總利潤為最大？第三十一頁，共四十六頁。4運輸問題應用舉例第三十二頁，共四十六頁。5指派問題在現(xiàn)實生活中，經(jīng)常會遇到指派人員做某項工作（任務）的情況。指派問題的許多應用是用來幫助管理人員解決如何為一項即將開展的工作指派人員的問題。其他的一些應用如為工作指派機器、設備或工廠等。指派問題也稱分配問題，主要研究人和工作（任務）間如何匹配，以使所有工作完成的效率實現(xiàn)最優(yōu)化。形式上，指派問題給定了一系列所要完成的工作以及一系列完成工作的人員，所需要解決的問題就是要確定出指派哪個人去完成哪項工作。第三十三頁，共四十六頁。5指派問題指派問題的假設：

（1）人的數(shù)量和工作的數(shù)量相等； （2）每個人只能完成一項工作； （3）每項工作只能由一個人來完成； （4）每個人和每項工作的組合都會有一 個相關的成本（單位成本）； （5）目標是要確定如何指派才能使總成 本最小。第三十四頁，共四十六頁。設決策變量xij為第i個人做第j項工作，而已知5指派問題目標函數(shù)系數(shù)cij為第i個人完成第j項工作所需要的單位成本。平衡指派問題的數(shù)學模型為第三十五頁，共四十六頁。5指派問題需要說明的是：指派問題實際上是一種特殊的運輸問題。其中出發(fā)地是人，目的地是工作。只不過，每一個出發(fā)地的供應量都為1（因為每個人都要完成一項工作），每一個目的地的需求量都為1（因為每項工作都要完成）。由于運輸問題有“整數(shù)解性質”，因此，沒有必要加上所有決策變量都是0-1變量的約束。指派問題是一種特殊的線性規(guī)劃問題，有一種快捷的求解方法：匈牙利方法（HungarianMethod），但Excel的“規(guī)劃求解”工具還是采用“單純形法”來求解。第三十六頁，共四十六頁。5指派問題

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