第七章運(yùn)輸問題

第七章運(yùn)輸問題一、運(yùn)輸問題模型及其求解思路二、幾種特殊情況三、運(yùn)輸問題的應(yīng)用一、運(yùn)輸問題模型及其求解思路1、問題的提出：某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3。各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示。問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。恳?、運(yùn)輸問題模型及其求解思路B1B2B3產(chǎn)量A1646200A2655300銷量150150200運(yùn)價表銷量和＝產(chǎn)量和產(chǎn)銷平衡一、運(yùn)輸問題模型及其求解思路B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200為建立模型，設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下表：運(yùn)量表一、運(yùn)輸問題模型及其求解思路據(jù)題意，可建立線性規(guī)劃模型：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）一、運(yùn)輸問題模型及其求解思路2、產(chǎn)銷平衡運(yùn)輸問題模型的特點(diǎn)從模型的建立可知：列數(shù)為2（產(chǎn)地數(shù)）×3（銷地數(shù)）＝6；行數(shù)為2（產(chǎn)地數(shù)）+3（銷地數(shù)）＝5；再觀察模型的系數(shù)矩陣：一、運(yùn)輸問題模型及其求解思路111000200

000111300100100150

010010150

001001200前2行之和＝后3行之和一、運(yùn)輸問題模型及其求解思路對于產(chǎn)銷平衡的運(yùn)輸問題，若產(chǎn)地為m個，銷地為n個，則變量個數(shù)為m×n個，線性無關(guān)的約束條件個數(shù)為m+n-1，故基本解中的基變量個數(shù)為m+n-1。一、運(yùn)輸問題模型及其求解思路3、運(yùn)輸問題求解思路——表上作業(yè)法由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計算，則無法利用這些有利條件。人們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對運(yùn)輸問題的表上作業(yè)法。（表上作業(yè)法略）運(yùn)輸問題的應(yīng)用1、產(chǎn)銷不平衡的運(yùn)輸問題例：某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示。問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。夸N量<產(chǎn)量運(yùn)輸問題的應(yīng)用B1B2B3產(chǎn)量A1646300A2655300銷量150150200運(yùn)輸問題的應(yīng)用100x24x14庫存量200150150銷量300x23x22x21A2300x13x12x11A1產(chǎn)量B3B2B1多余的產(chǎn)量100作為庫存，A1和A2各庫存多少待定。運(yùn)輸問題的應(yīng)用10000庫存量200150150銷量300556A2300646A1產(chǎn)量B3B2B1在運(yùn)價表中也增加庫存的相應(yīng)列：庫存量運(yùn)價為0。運(yùn)輸問題的應(yīng)用結(jié)論：對于產(chǎn)量大于銷量的運(yùn)輸問題，在運(yùn)輸作業(yè)表上增加一列，其銷量等于總產(chǎn)量和總銷量之差，運(yùn)價均為0。可以將增加的一列理解為假想銷地，其銷量即庫存量。思考：對于銷量大于產(chǎn)量的問題怎么辦？銷量>產(chǎn)量運(yùn)輸問題的應(yīng)用B1B2B3產(chǎn)量A1646200A2655300銷量250150200運(yùn)輸問題的應(yīng)用辦法：增加一行表示缺貨量。100000缺貨量200150250銷量300556A2200646A1產(chǎn)量B3B2B1運(yùn)輸問題的應(yīng)用實(shí)際應(yīng)用中，可能出現(xiàn)的其他情況：（1）某些運(yùn)輸線路上的運(yùn)輸能力有限制；處理辦法：直接在約束條件中增加該約束，即保證X14的取值不超過產(chǎn)量、銷量和線路最大運(yùn)輸能力。（2）目標(biāo)函數(shù)求最大值不是最小值；運(yùn)輸問題的應(yīng)用（3）銷量大于產(chǎn)量，但某些銷地的銷量必須完全滿足，不能有缺貨；處理辦法：對缺貨量到該銷地的運(yùn)價定為一個充分大的值M。（類似于大M法）運(yùn)輸問題的應(yīng)用如表中B2銷量不能短缺：1000M0缺貨量200150250銷量300556A2200646A1產(chǎn)量B3B2B1運(yùn)輸問題的應(yīng)用（4）銷量大于產(chǎn)量時，若某地的銷量可以有一定量缺貨，但供應(yīng)量必須不小于某個值p；處理辦法：將該銷地分解為兩個銷地Bj1和Bj2，Bj1對應(yīng)必須滿足的銷量p，Bj2對應(yīng)缺貨的銷量bj-p。其中，缺貨量到Bj1的運(yùn)價為“大M”。運(yùn)輸問題的應(yīng)用如表中B2銷量不能低于100：10000缺貨量200150250銷量300556A2200646A1產(chǎn)量B3B2B1B21B22100504455M0運(yùn)輸問題的應(yīng)用例1：石家莊北方研究院有一、二、三，三個區(qū)。每年分別需要用煤3000、1000、2000t，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價格、質(zhì)量相同。供應(yīng)能力分別為1500、4000t，運(yùn)價如下表。由于需大于求，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0—300t，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1500t，試求總費(fèi)用為最低的調(diào)運(yùn)方案。一區(qū)二區(qū)三區(qū)產(chǎn)量臨城1.801.701.554000盂縣1.601.501.751500銷量300010002000運(yùn)輸問題的應(yīng)用一區(qū)一區(qū)二區(qū)三區(qū)三區(qū)產(chǎn)量臨城1.801.801.701.551.554000盂縣1.601.601.501.751.751500假想產(chǎn)地M0MM0500銷量270030010001500500解：根據(jù)題意，作出產(chǎn)銷平衡的運(yùn)價表，取M代表一個很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的x31、x33、x34取值為0。運(yùn)輸問題的應(yīng)用1234產(chǎn)量A1613221750B1413191560C192023——50最低需要量3070010最高需要量507030不限例2：設(shè)有A、B、C三個化肥廠供應(yīng)1、2、3、4四個地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表。試求總費(fèi)用為最低的化肥調(diào)撥方案。運(yùn)輸問題的應(yīng)用1’1’’234’4’’產(chǎn)量A16161322171750B14141319151560C19192023MM50DM0M0M050銷量302070301050解：根據(jù)題意，作出產(chǎn)銷平衡的運(yùn)價表運(yùn)輸問題的應(yīng)用2、生產(chǎn)與儲存問題例1：某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如下表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)等費(fèi)用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：交貨：

生產(chǎn)：x11

=10x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35

x13+x23+x33

=25x33+x34≤30

x14+x24+x34+x44=20x44≤10

運(yùn)輸問題的應(yīng)用把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個銷售點(diǎn)的銷量；成本加儲存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)?？蓸?gòu)造下列產(chǎn)銷平衡問題：例2：光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表：運(yùn)輸問題的應(yīng)用已知上年末庫存103臺繡花機(jī)，如果當(dāng)月生產(chǎn)出來的機(jī)器當(dāng)月不交貨，則需要運(yùn)到分廠庫房，每臺增加運(yùn)輸成本0.1萬元,每臺機(jī)器每月的平均倉儲費(fèi)、維護(hù)費(fèi)為0.2萬元。在7—8月份銷售淡季，全廠停產(chǎn)1個月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)機(jī)器每臺增加成本1萬元。問應(yīng)如何安排1—6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉儲、維護(hù)）最少？運(yùn)輸問題的應(yīng)用解：這個生產(chǎn)存儲問題可化為運(yùn)輸問題來做?？紤]：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地。1）1-6月份合計生產(chǎn)能力（包括上年末儲存量）為743臺，銷量為707臺。設(shè)一假想銷地銷量為36；2）上年末庫存103臺，只有倉儲費(fèi)和運(yùn)輸費(fèi)，把它列為的0行；3）6月份的需求除70臺銷量外，還要80臺庫存，其需求應(yīng)為70+80=150臺；4）1-6表示1-6月份正常生產(chǎn)情況，1’-6’表示1-6月份加班生產(chǎn)情況。運(yùn)輸問題的應(yīng)用產(chǎn)銷平衡的運(yùn)價表：運(yùn)輸問題的應(yīng)用3、轉(zhuǎn)運(yùn)問題原運(yùn)輸問題上增加若干轉(zhuǎn)運(yùn)站。運(yùn)輸方式有：產(chǎn)地轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站銷地、產(chǎn)地產(chǎn)地、產(chǎn)地銷地、銷地轉(zhuǎn)運(yùn)站、銷地產(chǎn)地等。例：某公司有A1、A2、A3三個分廠生產(chǎn)某種物質(zhì)，分別供應(yīng)B1、B2、B3、B4四個地區(qū)的銷售公司銷售。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下表：運(yùn)輸問題的應(yīng)用假設(shè)：

1、每個分廠的物資不一定直接發(fā)運(yùn)到銷地,可以從其中幾個產(chǎn)地集中一起運(yùn)；

2、運(yùn)往各銷地的物資可以先運(yùn)給其中幾個銷地，再轉(zhuǎn)運(yùn)給其他銷地；

3、除產(chǎn)銷地之外，還有幾個中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。運(yùn)價