管理運籌學7運輸問題課件

1第七章運輸問題§1運輸模型§2運輸問題的計算機求解§3運輸問題的應用§4*運輸問題的表上作業(yè)法1第七章運輸問題§1運輸模型2例1、某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最小？解：產銷平衡問題：總產量=總銷量設xij

為從產地Ai運往銷地Bj的運輸量，得到下列運輸量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）

§1運輸模型2例1、某公司從兩個產地A1、A2將物品運往三個銷地B1、B3§1運輸模型一般運輸模型：產銷平衡

A1、A2、…、Am

表示某物資的m個產地；B1、B2、…、Bn

表示某物質的n個銷地；si

表示產地Ai的產量；dj

表示銷地Bj的銷量；cij

表示把物資從產地Ai運往銷地Bj的單位運價。設xij

為從產地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：

mnMinf=cijxiji=1j=1n

s.t.

xij=sii=1,2,…,m

j=1m

xij=djj=1,2,…,ni=1

xij≥0(i=1,2,…,m;j=1,2,…,n)變化：

1）有時目標函數(shù)求最大。如求利潤最大或營業(yè)額最大等；

2）當某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)；

3）產銷不平衡時，可加入假想的產地（銷大于產時）或銷地（產大于銷時）。3§1運輸模型一般運輸模型：產銷平衡4§2運輸問題的計算機求解例2、某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最?。拷猓涸黾右粋€虛設的銷地運輸費用為04§2運輸問題的計算機求解例2、某公司從兩個產地A1、A25§2運輸問題的計算機求解例3、某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最?。拷猓涸黾右粋€虛設的產地運輸費用為05§2運輸問題的計算機求解例3、某公司從兩個產地A1、A26§3運輸問題的應用一、產銷不平衡的運輸問題例4、石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負責供應，價格、質量相同。供應能力分別為1500、4000噸，運價為：由于需大于供，經(jīng)院研究決定一區(qū)供應量可減少0--300噸，二區(qū)必須滿足需求量，三區(qū)供應量不少于1500噸，試求總費用為最低的調運方案。解：根據(jù)題意，作出產銷平衡與運價表：這里M代表一個很大的正數(shù)，其作用是強迫相應的x31、x33、x34取值為0。6§3運輸問題的應用一、產銷不平衡的運輸問題7§3運輸問題的應用一、產銷不平衡的運輸問題例5、設有A、B、C三個化肥廠供應1、2、3、4四個地區(qū)的農用化肥。假設效果相同，有關數(shù)據(jù)如下表：

試求總費用為最低的化肥調撥方案。解：根據(jù)題意，作出產銷平衡與運價表：

最低要求必須滿足，因此把相應的虛設產地運費取為M，而最高要求與最低要求的差允許按需要安排，因此把相應的虛設產地運費取為0。對應4”的銷量

50是考慮問題本身適當取的數(shù)據(jù)，根據(jù)產銷平衡要求確定D的產量為50。

7§3運輸問題的應用一、產銷不平衡的運輸問題8§3運輸問題的應用二、生產與儲存問題例6、某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產能力及生產每臺柴油機的成本如右表。如果生產出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產總費用為最小的決策方案。8§3運輸問題的應用二、生產與儲存問題9§3運輸問題的應用解：設xij為第i季度生產的第j季度交貨的柴油機數(shù)目，那么應滿足：交貨：x11=10生產：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10

把第i季度生產的柴油機數(shù)目看作第i個生產廠的產量；把第j季度交貨的柴油機數(shù)目看作第j個銷售點的銷量；成本加儲存、維護等費用看作運費。可構造下列產銷平衡問題：目標函數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x449§3運輸問題的應用解：設xij為第i季度生產的第10§3運輸問題的應用二、生產與儲存問題例7、光明儀器廠生產電腦繡花機是以產定銷的。已知1至6月份各月的生產能力、合同銷量和單臺電腦繡花機平均生產費用見下表：已知上年末庫存103臺繡花機，如果當月生產出來的機器當月不交貨，則需要運到分廠庫房，每臺增加運輸成本0.1萬元,每臺機器每月的平均倉儲費、維護費為0.2萬元。在7--8月份銷售淡季，全廠停產1個月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產機器每臺增加成本1萬元。問應如何安排1--6月份的生產，可使總的生產費用（包括運輸、倉儲、維護）最少？10§3運輸問題的應用二、生產與儲存問題11§3運輸問題的應用解：這個生產存儲問題可化為運輸問題來做?？紤]：各月生產與交貨分別視為產地和銷地

1）1--6月份合計生產能力（包括上年末儲存量）為743臺，銷量為707臺。設一假想銷地銷量為36；

2）上年末庫存103臺，只有倉儲費和運輸費，把它列為第0行；

3）6月份的需求除70臺銷量外，還要80臺庫存，其需求應為70+80=150臺；

4）1--6表示1--6月份正常生產情況，1’--6’表示1--6月份加班生產情況。產銷平衡與運價表：11§3運輸問題的應用解：這個生產存儲問題可化為運輸問題12§3運輸問題的應用

用“管理運籌學”軟件解得的結果是：1-6月最低生產費用為8307.5萬元，每月的銷售安排如下表所示12§3運輸問題的應用用“管理運籌學”軟13§3運輸問題的應用三、轉運問題：在原運輸問題上增加若干轉運站。運輸方式有：產地轉運站、轉運站銷地、產地產地、產地銷地、銷地轉運站、銷地產地等。例8、騰飛電子儀器公司在大連和廣州有兩個分廠生產同一種儀器，大連分廠每月生產400臺，廣州分廠每月生產600臺。該公司在上海和天津有兩個銷售公司負責對南京、濟南、南昌、青島四個城市的儀器供應。另外因為大連距離青島較近，公司同意大連分廠向青島直接供貨，運輸費用如圖，單位是百元。問應該如何調運儀器，可使總運輸費用最低？圖中1-廣州、2-大連、3-上海、4-天津、5-南京、6-濟南、7-南昌、8-青島13§3運輸問題的應用三、轉運問題：14§3運輸問題的應用解：設xij

為從i到j的運輸量，可得到有下列特點的線性規(guī)劃模型：目標函數(shù)：Minf=所有可能的運輸費用（運輸單價與運輸量乘積之和）約束條件：對產地（發(fā)點）i：輸出量-輸入量=產量對轉運站（中轉點）：輸入量-輸出量=0

對銷地（收點）j：輸入量-輸出量=銷量例8．（續(xù)）目標函數(shù)：Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48

約束條件：

s.t.x13+x14≤600(廣州分廠供應量限制）

x23+x24+x28≤400(大連分廠供應量限制）

-x13-x23+x35+x36+x37+x38=0（上海銷售公司，轉運站）

-x14-x24+x45+x46+x47+x48=0（天津銷售公司，轉運站）

x35+x45=200（南京的銷量）

x36+x46=150（濟南的銷量）

x37+x47=350（南昌的銷量）

x38+x48+x28=300（青島的銷量）

xij≥0,i,j=1,2,3,4,5,6,7,814§3運輸問題的應用解：設xij為從i到j的15§3運輸問題的應用用“管理運籌學”軟件求得結果：

x13=550x14=50；

x23=0x24=100x28=300；

x35=200x36=0x37=350x38=0；

x45=0x46=150x47=0x48=0。最小運輸費用為：4600百元例9、某公司有A1、A2、A3三個分廠生產某種物資，分別供應B1、B2、B3、B4四個地區(qū)的銷售公司銷售。假設質量相同，有關數(shù)據(jù)如下表：

試求總費用為最少的調運方案。假設：

1.每個分廠的物資不一定直接發(fā)運到銷地，可以從其中幾個產地集中一起運；

2.運往各銷地的物資可以先運給其中幾個銷地，再轉運給其他銷地；

3.除產銷地之外，還有幾個中轉站，在產地之間、銷地之間或在產地與銷地之間轉運。15§3運輸問題的應用用“管理運籌學”軟件求得結果：16§3運輸問題的應用運價如下表：解：把此轉運問題轉化為一般運輸問題：

1、把所有產地、銷地、轉運站都同時看作產地和銷地；

2、運輸表中不可能方案的運費取作M，自身對自身的運費為0；

3、Ai：產量為20+原產量，銷量為20；Ti

：產量、銷量均為20；Bi：產量為20，銷量為20+原銷量，其中20為各點可能變化的最大流量；

4、對于最優(yōu)方案，其中xii

為自身對自身的運量，實際上不進行運作。16§3運輸問題的應用運價如下表：17§3運輸問題的應用

擴大的運輸問題產銷平衡與運價表：17§3運輸問題的應用擴大的運輸問題產銷平衡與運價表：18§4*運輸問題的表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其實質是單純形法。運輸問題都存在最優(yōu)解。計算過程（假設產銷平衡）：1.找出初始基本可行解。對于有m個產地n個銷地的產銷平衡問題，則有m個關于產量的約束方程和n個關于銷量的約束方程。由于產銷平衡，其模型最多只有m+n-1個獨立的約束方程，即運輸問題有m+n-1個基變量。在m×n的產銷平衡表上給出m+n-1個數(shù)字格，其相對應的調運量的值即為基變量的值。2.求各非基變量的檢驗數(shù)，即檢驗除了上述m+n-1個基變量以外的空格的檢驗數(shù)判別是否達到最優(yōu)解，如果已是最優(yōu)，停止計算，否則轉到下一步。3.確定入基變量和出基變量，找出新的基本可行解。在表上用閉回路法調整。4.重復2、3直到得到最優(yōu)解。18§4*運輸問題的表上作業(yè)法表上作業(yè)法是一種求解運輸問題19§4*運輸問題的表上作業(yè)法例10.喜慶食品公司有三個生產面包的分廠A1，A2，A3，有四個銷售公司B1，B2，B3，B4，其各分廠每日的產量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運價如表所示，在表中產量與銷量的單位為噸，運價的單位為百元/噸。問該公司應如何調運產品在滿足各銷點的需求量的前提下總運費最少？這是一個產銷平衡的運輸問題，因此不需要再設假想產地和銷地了。

銷地產地B1B2B3B4產量A13113107A219284A3741059銷量3656202019§4*運輸問題的表上作業(yè)法例10.喜慶食品公司有三個生20§4*運輸問題的表上作業(yè)法一、確定初始基本可行解

為了把初始基本可行解與運價區(qū)分開，我們把運價放在每一欄的右上角，每一欄的中間寫上初始基本可行解（調運量）。

1.西北角法：先從表的左上角（即西北角）的變量x11開始分配運輸量，并使x11取盡可能大的值，即x11=min(7,3)=3,則x21與x31必為零。同時把B1的銷量與A1的產量都減去3填入銷量和產量處，劃去原來的銷量和產量。同理可得余下的初始基本可行解。

銷地產地B1B2B3B4

產量A134740A222420A336960

銷量3062053060202031131085102947120§4*運輸問題的表上作業(yè)法一、確定初始基本可行解21§4*運輸問題的表上作業(yè)法2.最小元素法

西北角法是對西北角的變量分配運輸量，而最小元素法是就近供應，即對單位運價最小的變量分配運輸量。在表上找到單位運價最小的x21，并使x21取盡可能大的值，即x21=min(4,3)=3,把A1的產量改為1，B1的銷量改為0，并把B1列劃去。在剩下的3×3矩陣中再找最小運價，同理可得其他的基本可行解。一般來說用最小元素法求得的初始基本可行解比西北角法求得的總運價要少。這樣從用最小元素法求得的初始基本可行解出發(fā)求最優(yōu)解的迭代次數(shù)可能少一些。

銷地產地B1B2B3B4

產量A1

43730A23

1410A363930

銷量3060

540630202031131085102947121§4*運輸問題的表上作業(yè)法2.最小元素法22§4*運輸問題的表上作業(yè)法在求初始基本可行解時要注意的兩個問題：1.當我們取定xij的值之后，會出現(xiàn)Ai的產量與Bj的銷量都改為零的情況，這時只能劃去Ai行或Bj列，但不能同時劃去Ai行與Bj列。2.用最小元素法時，可能會出現(xiàn)只剩下一行或一列的所有格均未填數(shù)或未被劃掉的情況，此時在這一行或者一列中除去已填上的數(shù)外均填上零，不能按空格劃掉。這樣可以保證填過數(shù)或零的格為m+n-1個，即保證基變量的個數(shù)為m+n-1個。22§4*運輸問題的表上作業(yè)法在求初始基本可行解時要注意的23§4*運輸問題的表上作業(yè)法二、最優(yōu)解的判別1.閉回路法所謂閉回路是在已給出的調運方案的運輸表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉90度（當然也可以不改變方向）繼續(xù)前進，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉回路。一個空格存在唯一的閉回路。所謂閉回路法，就是對于代表非基變量的空格（其調運量為零），把它的調運量調整為1，由于產銷平衡的要求,我們必須對這個空格的閉回路的頂點的調運量加上或減少1。最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。23§4*運輸問題的表上作業(yè)法二、最優(yōu)解的判別24§4*運輸問題的表上作業(yè)法從非基變量x11出發(fā)，找到一個閉回路如上表所示。回路有四個頂點，除x11外，其余都為基變量?，F(xiàn)在把x11的調運量從零增加為1噸，運費也增加了3元，為了使A1產量平衡，x13必須減少1噸，運費減少3元。為了B3的銷量平衡，x23必須增加1噸，運費增加2元。同理把x21減少1噸，運費減少1元。調整后，總運費增加了3-3+2-1=1元。說明如果讓x11為基變量，運費就會增加，其增加值1作為x11的檢驗數(shù)，為了區(qū)別調整量，我們把1加圈。用同樣的方法可以找出所有空格（即非基變量）的檢驗數(shù)。

銷地產地B1B2B3B4

產量A11

47A23

14A39

銷量3656202031131085102947124§4*運輸問題的表上作業(yè)法銷地25§4*運輸問題的表上作業(yè)法2.位勢法所謂位勢法，我們對運輸表上的每一行賦予一個數(shù)值ui，對每一列賦予一個數(shù)值vj，它們的數(shù)值是由基變量xij的檢驗數(shù)所決定的，則非基變量xij的檢驗數(shù)就可以用公式求出。我們先給u1賦個任意數(shù)值，不妨設u1=0，則從基變量x13的檢驗數(shù)求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1等等見上表。檢驗值的求法即用公式，如。

銷地產地B1B2B3B4uiA1

1

2430A23

11

-1-1A3

106

123-5vj29310202031131085102947125§4*運輸問題的表上作業(yè)法2.位勢法26§4*運輸問題的表上作業(yè)法三、改進運輸方案的辦法——閉回路調整法當表中的某個檢驗數(shù)小于零時，方案不為最優(yōu)，需要調整。方法是：選取所有負檢驗數(shù)最小的非基變量作為入基變量，以求盡快實現(xiàn)最優(yōu)。本例中取，表明增加一個單位的x24運輸量，可使得總運費減少1。在以x24為出發(fā)點的閉回路中，找出所有偶數(shù)的頂點的調運量：x14=3，x23=1，x24=min(3,1)=1。把所有閉回路上為偶數(shù)頂點的運輸量都減少這個值，奇數(shù)頂點的運輸量都增加這個值(見下表)。

銷地產地B1B2B3B4uiA1

4(+1)3(-1)0A23

1(-1)

+1-1A3

6

3-5vj29310202031131085102947126§4*運輸問題的表上作業(yè)法三、改進運輸方案的辦法——閉27§4*運輸問題的表上作業(yè)法對上表用位勢法進行檢驗如下表

銷地產地B1B2B3B4

產量A1

527A23

14A3

6

39

銷量36562020

銷地產地B1B2B3B4uiA1

0

2520A23

2

1

1-1A3

96

123-5vj29310202031131085102947127§4*運輸問題的表上作業(yè)法銷地28§4*運輸問題的表上作業(yè)法四、如何找多個最優(yōu)方案識別是否有多個最優(yōu)解的方法和單純形表法一樣，只需看最優(yōu)方案中是否存在非基變量的檢驗數(shù)為零。如在本題中給出的最優(yōu)運輸方案中x11的檢驗數(shù)為0，可知此運輸問題有多個最優(yōu)解。只要把x11作為入基變量，調整運輸方案，就可得到另一個最優(yōu)方案。

銷地產地B1B2B3B4A1

(+2)

52(-2)A23(-2)

1(+2)A3

6

3

銷地產地B1B2B3B4A12

5

A21

3A3

6

328§4*運輸問題的表上作業(yè)法四、如何找多個最優(yōu)方案29第七章運輸問題§1運輸模型§2運輸問題的計算機求解§3運輸問題的應用§4*運輸問題的表上作業(yè)法1第七章運輸問題§1運輸模型30例1、某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最小？解：產銷平衡問題：總產量=總銷量設xij

為從產地Ai運往銷地Bj的運輸量，得到下列運輸量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）

§1運輸模型2例1、某公司從兩個產地A1、A2將物品運往三個銷地B1、B31§1運輸模型一般運輸模型：產銷平衡

A1、A2、…、Am

表示某物資的m個產地；B1、B2、…、Bn

表示某物質的n個銷地；si

表示產地Ai的產量；dj

表示銷地Bj的銷量；cij

表示把物資從產地Ai運往銷地Bj的單位運價。設xij

為從產地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：

mnMinf=cijxiji=1j=1n

s.t.

xij=sii=1,2,…,m

j=1m

xij=djj=1,2,…,ni=1

xij≥0(i=1,2,…,m;j=1,2,…,n)變化：

1）有時目標函數(shù)求最大。如求利潤最大或營業(yè)額最大等；

2）當某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)；

3）產銷不平衡時，可加入假想的產地（銷大于產時）或銷地（產大于銷時）。3§1運輸模型一般運輸模型：產銷平衡32§2運輸問題的計算機求解例2、某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最??？解：增加一個虛設的銷地運輸費用為04§2運輸問題的計算機求解例2、某公司從兩個產地A1、A233§2運輸問題的計算機求解例3、某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最小？解：增加一個虛設的產地運輸費用為05§2運輸問題的計算機求解例3、某公司從兩個產地A1、A234§3運輸問題的應用一、產銷不平衡的運輸問題例4、石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負責供應，價格、質量相同。供應能力分別為1500、4000噸，運價為：由于需大于供，經(jīng)院研究決定一區(qū)供應量可減少0--300噸，二區(qū)必須滿足需求量，三區(qū)供應量不少于1500噸，試求總費用為最低的調運方案。解：根據(jù)題意，作出產銷平衡與運價表：這里M代表一個很大的正數(shù)，其作用是強迫相應的x31、x33、x34取值為0。6§3運輸問題的應用一、產銷不平衡的運輸問題35§3運輸問題的應用一、產銷不平衡的運輸問題例5、設有A、B、C三個化肥廠供應1、2、3、4四個地區(qū)的農用化肥。假設效果相同，有關數(shù)據(jù)如下表：

試求總費用為最低的化肥調撥方案。解：根據(jù)題意，作出產銷平衡與運價表：

最低要求必須滿足，因此把相應的虛設產地運費取為M，而最高要求與最低要求的差允許按需要安排，因此把相應的虛設產地運費取為0。對應4”的銷量

50是考慮問題本身適當取的數(shù)據(jù)，根據(jù)產銷平衡要求確定D的產量為50。

7§3運輸問題的應用一、產銷不平衡的運輸問題36§3運輸問題的應用二、生產與儲存問題例6、某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產能力及生產每臺柴油機的成本如右表。如果生產出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產總費用為最小的決策方案。8§3運輸問題的應用二、生產與儲存問題37§3運輸問題的應用解：設xij為第i季度生產的第j季度交貨的柴油機數(shù)目，那么應滿足：交貨：x11=10生產：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10

把第i季度生產的柴油機數(shù)目看作第i個生產廠的產量；把第j季度交貨的柴油機數(shù)目看作第j個銷售點的銷量；成本加儲存、維護等費用看作運費?？蓸嬙煜铝挟a銷平衡問題：目標函數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x449§3運輸問題的應用解：設xij為第i季度生產的第38§3運輸問題的應用二、生產與儲存問題例7、光明儀器廠生產電腦繡花機是以產定銷的。已知1至6月份各月的生產能力、合同銷量和單臺電腦繡花機平均生產費用見下表：已知上年末庫存103臺繡花機，如果當月生產出來的機器當月不交貨，則需要運到分廠庫房，每臺增加運輸成本0.1萬元,每臺機器每月的平均倉儲費、維護費為0.2萬元。在7--8月份銷售淡季，全廠停產1個月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產機器每臺增加成本1萬元。問應如何安排1--6月份的生產，可使總的生產費用（包括運輸、倉儲、維護）最少？10§3運輸問題的應用二、生產與儲存問題39§3運輸問題的應用解：這個生產存儲問題可化為運輸問題來做。考慮：各月生產與交貨分別視為產地和銷地

1）1--6月份合計生產能力（包括上年末儲存量）為743臺，銷量為707臺。設一假想銷地銷量為36；

2）上年末庫存103臺，只有倉儲費和運輸費，把它列為第0行；

3）6月份的需求除70臺銷量外，還要80臺庫存，其需求應為70+80=150臺；

4）1--6表示1--6月份正常生產情況，1’--6’表示1--6月份加班生產情況。產銷平衡與運價表：11§3運輸問題的應用解：這個生產存儲問題可化為運輸問題40§3運輸問題的應用

用“管理運籌學”軟件解得的結果是：1-6月最低生產費用為8307.5萬元，每月的銷售安排如下表所示12§3運輸問題的應用用“管理運籌學”軟41§3運輸問題的應用三、轉運問題：在原運輸問題上增加若干轉運站。運輸方式有：產地轉運站、轉運站銷地、產地產地、產地銷地、銷地轉運站、銷地產地等。例8、騰飛電子儀器公司在大連和廣州有兩個分廠生產同一種儀器，大連分廠每月生產400臺，廣州分廠每月生產600臺。該公司在上海和天津有兩個銷售公司負責對南京、濟南、南昌、青島四個城市的儀器供應。另外因為大連距離青島較近，公司同意大連分廠向青島直接供貨，運輸費用如圖，單位是百元。問應該如何調運儀器，可使總運輸費用最低？圖中1-廣州、2-大連、3-上海、4-天津、5-南京、6-濟南、7-南昌、8-青島13§3運輸問題的應用三、轉運問題：42§3運輸問題的應用解：設xij

為從i到j的運輸量，可得到有下列特點的線性規(guī)劃模型：目標函數(shù)：Minf=所有可能的運輸費用（運輸單價與運輸量乘積之和）約束條件：對產地（發(fā)點）i：輸出量-輸入量=產量對轉運站（中轉點）：輸入量-輸出量=0

對銷地（收點）j：輸入量-輸出量=銷量例8．（續(xù)）目標函數(shù)：Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48

約束條件：

s.t.x13+x14≤600(廣州分廠供應量限制）

x23+x24+x28≤400(大連分廠供應量限制）

-x13-x23+x35+x36+x37+x38=0（上海銷售公司，轉運站）

-x14-x24+x45+x46+x47+x48=0（天津銷售公司，轉運站）

x35+x45=200（南京的銷量）

x36+x46=150（濟南的銷量）

x37+x47=350（南昌的銷量）

x38+x48+x28=300（青島的銷量）

xij≥0,i,j=1,2,3,4,5,6,7,814§3運輸問題的應用解：設xij為從i到j的43§3運輸問題的應用用“管理運籌學”軟件求得結果：

x13=550x14=50；

x23=0x24=100x28=300；

x35=200x36=0x37=350x38=0；

x45=0x46=150x47=0x48=0。最小運輸費用為：4600百元例9、某公司有A1、A2、A3三個分廠生產某種物資，分別供應B1、B2、B3、B4四個地區(qū)的銷售公司銷售。假設質量相同，有關數(shù)據(jù)如下表：

試求總費用為最少的調運方案。假設：

1.每個分廠的物資不一定直接發(fā)運到銷地，可以從其中幾個產地集中一起運；

2.運往各銷地的物資可以先運給其中幾個銷地，再轉運給其他銷地；

3.除產銷地之外，還有幾個中轉站，在產地之間、銷地之間或在產地與銷地之間轉運。15§3運輸問題的應用用“管理運籌學”軟件求得結果：44§3運輸問題的應用運價如下表：解：把此轉運問題轉化為一般運輸問題：

1、把所有產地、銷地、轉運站都同時看作產地和銷地；

2、運輸表中不可能方案的運費取作M，自身對自身的運費為0；

3、Ai：產量為20+原產量，銷量為20；Ti

：產量、銷量均為20；Bi：產量為20，銷量為20+原銷量，其中20為各點可能變化的最大流量；

4、對于最優(yōu)方案，其中xii

為自身對自身的運量，實際上不進行運作。16§3運輸問題的應用運價如下表：45§3運輸問題的應用

擴大的運輸問題產銷平衡與運價表：17§3運輸問題的應用擴大的運輸問題產銷平衡與運價表：46§4*運輸問題的表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其實質是單純形法。運輸問題都存在最優(yōu)解。計算過程（假設產銷平衡）：1.找出初始基本可行解。對于有m個產地n個銷地的產銷平衡問題，則有m個關于產量的約束方程和n個關于銷量的約束方程。由于產銷平衡，其模型最多只有m+n-1個獨立的約束方程，即運輸問題有m+n-1個基變量。在m×n的產銷平衡表上給出m+n-1個數(shù)字格，其相對應的調運量的值即為基變量的值。2.求各非基變量的檢驗數(shù)，即檢驗除了上述m+n-1個基變量以外的空格的檢驗數(shù)判別是否達到最優(yōu)解，如果已是最優(yōu)，停止計算，否則轉到下一步。3.確定入基變量和出基變量，找出新的基本可行解。在表上用閉回路法調整。4.重復2、3直到得到最優(yōu)解。18§4*運輸問題的表上作業(yè)法表上作業(yè)法是一種求解運輸問題47§4*運輸問題的表上作業(yè)法例10.喜慶食品公司有三個生產面包的分廠A1，A2，A3，有四個銷售公司B1，B2，B3，B4，其各分廠每日的產量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運價如表所示，在表中產量與銷量的單位為噸，運價的單位為百元/噸。問該公司應如何調運產品在滿足各銷點的需求量的前提下總運費最少？這是一個產銷平衡的運輸問題，因此不需要再設假想產地和銷地了。

銷地產地B1B2B3B4產量A13113107A219284A3741059銷量3656202019§4*運輸問題的表上作業(yè)法例10.喜慶食品公司有三個生48§4*運輸問題的表上作業(yè)法一、確定初始基本可行解

為了把初始基本可行解與運價區(qū)分開，我們把運價放在每一欄的右上角，每一欄的中間寫上初始基本可行解（調運量）。

1.西北角法：先從表的左上角（即西北角）的變量x11開始分配運輸量，并使x11取盡可能大的值，即x11=min(7,3)=3,則x21與x31必為零。同時把B1的銷量與A1的產量都減去3填入銷量和產量處，劃去原來的銷量和產量。同理可得余下的初始基本可行解。

銷地產地B1B2B3B4

產量A134740A222420A336960

銷量3062053060202031131085102947120§4*運輸問題的表上作業(yè)法一、確定初始基本可行解49§4*運輸問題的表上作業(yè)法2.最小元素法

西北角法是對西北角的變量分配運輸量，而最小元素法是就近供應，即對單位運價最小的變量分配運輸量。在表上找到單位運價最小的x21，并使x21取盡可能大的值，即x21=min(4,3)=3,把A1的產量改為1，B1的銷量改為0，并把B1列劃去。在剩下的3×3矩陣中再找最小運價，同理可得其他的基本可行解。一般來說用最小元素法求得的初始基本可行解比西北角法求得的總運價要少。這樣從用最小元素法求得的初始基本可行解出發(fā)求最優(yōu)解的迭代次數(shù)可能少一些。

銷地產地B1B2B3B4

產量A1

43730A23

1410A363930

銷量3060

540630202031131085102947121§4*運輸問題的表上作業(yè)法2.最小元素法50§4*運輸問題的表上作業(yè)法在求初始基本可行解時要注意的兩個問題：1.當我們取定xij的值之后，會出現(xiàn)Ai的產量與Bj的銷量都改為零的情況，這時只能劃去Ai行或Bj列，但不能同時劃去Ai行與Bj列。2.用最小元素法時，可能會出現(xiàn)只剩下一行或一列的所有格均未填數(shù)或未被劃掉的情況，此時在這一行或者一列中除去已填上的數(shù)外均填上零，不能按空格劃掉。這樣可以保證填過數(shù)或零的格為m+n-1個，即保證基變量的個數(shù)為m+n-1個。22§4*運輸問題的表上作業(yè)法在求初始基本可行解時要注意的51§4*運輸問題的表上作業(yè)法二、最優(yōu)解的判別1.閉回路法所謂閉回路是在已給出的調運方案的運輸表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉90度（當然也可以不改變方向）繼續(xù)前進，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉回路。一個空格存在唯一的閉回路。所謂閉回路法，就是對于代表非基變量的空格（其調運量為零），把它的調運量調整為1，由于產銷平衡的要求,我們必須對這個空格的閉回路的頂點的調運量加上或減少1。最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。23§4*運輸問題的表上作業(yè)法二、最優(yōu)解的判別52§4*運輸問題的表上作業(yè)法從非基變量x11出發(fā)，找到一個閉回路如上表所示?；芈酚兴膫€頂點，除x11外，其余都為基變量。現(xiàn)在把x11的調運量從零增加為1噸，運費也增加了3元，為了使A1產量平衡，x13必須減少1噸，運費減少3元。為了B3的銷量平衡，x23必須增加1噸，運費增加2元。同理把x21減少1噸，運費減少1元。調整后，總運費增加了3-3+2-1=1元。說明如果讓x11為基變量，運費就會增加，其增加值1作為x11的檢驗數(shù)，為了區(qū)別調整量，我們把1加圈。用同樣的方法可以找出所有空格（即非基變量）的檢驗數(shù)。

銷地產地B1B2B3B4

產量A11

47A23

14A39

銷量3656202031131085102947124§4*運輸問題的表上作業(yè)法銷地53§4*運輸問題的表上作業(yè)法2.位勢法所謂位勢法，我們對運輸表上的每一行賦予一個數(shù)值ui，對每一列賦予一個數(shù)值vj，它們的數(shù)值是由基變量xij的檢驗數(shù)所決定的，則非基變量xij的檢驗數(shù)就可以用公式求出。我們先給u1賦個任意數(shù)值，不妨設u1=0，則從基變量x13的檢驗數(shù)