管理運(yùn)籌學(xué)7運(yùn)輸問題課件

1第七章運(yùn)輸問題§1運(yùn)輸模型§2運(yùn)輸問題的計(jì)算機(jī)求解§3運(yùn)輸問題的應(yīng)用§4*運(yùn)輸問題的表上作業(yè)法1第七章運(yùn)輸問題§1運(yùn)輸模型2例1、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地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)用最?。拷猓寒a(chǎn)銷平衡問題：總產(chǎn)量=總銷量設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：

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運(yùn)輸模型2例1、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B3§1運(yùn)輸模型一般運(yùn)輸模型：產(chǎn)銷平衡

A1、A2、…、Am

表示某物資的m個(gè)產(chǎn)地；B1、B2、…、Bn

表示某物質(zhì)的n個(gè)銷地；si

表示產(chǎn)地Ai的產(chǎn)量；dj

表示銷地Bj的銷量；cij

表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型：

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í)目標(biāo)函數(shù)求最大。如求利潤(rùn)最大或營(yíng)業(yè)額最大等；

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

3）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。3§1運(yùn)輸模型一般運(yùn)輸模型：產(chǎn)銷平衡4§2運(yùn)輸問題的計(jì)算機(jī)求解例2、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地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)用最小？解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為04§2運(yùn)輸問題的計(jì)算機(jī)求解例2、某公司從兩個(gè)產(chǎn)地A1、A25§2運(yùn)輸問題的計(jì)算機(jī)求解例3、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地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)用最小？解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為05§2運(yùn)輸問題的計(jì)算機(jī)求解例3、某公司從兩個(gè)產(chǎn)地A1、A26§3運(yùn)輸問題的應(yīng)用一、產(chǎn)銷不平衡的運(yùn)輸問題例4、石家莊北方研究院有一、二、三三個(gè)區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，運(yùn)價(jià)為：由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0--300噸，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1500噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。解：根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：這里M代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的x31、x33、x34取值為0。6§3運(yùn)輸問題的應(yīng)用一、產(chǎn)銷不平衡的運(yùn)輸問題7§3運(yùn)輸問題的應(yīng)用一、產(chǎn)銷不平衡的運(yùn)輸問題例5、設(shè)有A、B、C三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表：

試求總費(fèi)用為最低的化肥調(diào)撥方案。解：根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：

最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為M，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為0。對(duì)應(yīng)4”的銷量

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

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

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

把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個(gè)生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個(gè)銷售點(diǎn)的銷量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。可構(gòu)造下列產(chǎn)銷平衡問題：目標(biāo)函數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x449§3運(yùn)輸問題的應(yīng)用解：設(shè)xij為第i季度生產(chǎn)的第10§3運(yùn)輸問題的應(yīng)用二、生產(chǎn)與儲(chǔ)存問題例7、光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺(tái)電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表：已知上年末庫(kù)存103臺(tái)繡花機(jī)，如果當(dāng)月生產(chǎn)出來(lái)的機(jī)器當(dāng)月不交貨，則需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本0.1萬(wàn)元,每臺(tái)機(jī)器每月的平均倉(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)機(jī)器每臺(tái)增加成本1萬(wàn)元。問應(yīng)如何安排1--6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉(cāng)儲(chǔ)、維護(hù)）最少？10§3運(yùn)輸問題的應(yīng)用二、生產(chǎn)與儲(chǔ)存問題11§3運(yùn)輸問題的應(yīng)用解：這個(gè)生產(chǎn)存儲(chǔ)問題可化為運(yùn)輸問題來(lái)做。考慮：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地

1）1--6月份合計(jì)生產(chǎn)能力（包括上年末儲(chǔ)存量）為743臺(tái)，銷量為707臺(tái)。設(shè)一假想銷地銷量為36；

2）上年末庫(kù)存103臺(tái)，只有倉(cāng)儲(chǔ)費(fèi)和運(yùn)輸費(fèi)，把它列為第0行；

3）6月份的需求除70臺(tái)銷量外，還要80臺(tái)庫(kù)存，其需求應(yīng)為70+80=150臺(tái)；

4）1--6表示1--6月份正常生產(chǎn)情況，1’--6’表示1--6月份加班生產(chǎn)情況。產(chǎn)銷平衡與運(yùn)價(jià)表：11§3運(yùn)輸問題的應(yīng)用解：這個(gè)生產(chǎn)存儲(chǔ)問題可化為運(yùn)輸問題12§3運(yùn)輸問題的應(yīng)用

用“管理運(yùn)籌學(xué)”軟件解得的結(jié)果是：1-6月最低生產(chǎn)費(fèi)用為8307.5萬(wàn)元，每月的銷售安排如下表所示12§3運(yùn)輸問題的應(yīng)用用“管理運(yùn)籌學(xué)”軟13§3運(yùn)輸問題的應(yīng)用三、轉(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)地等。例8、騰飛電子儀器公司在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)400臺(tái)，廣州分廠每月生產(chǎn)600臺(tái)。該公司在上海和天津有兩個(gè)銷售公司負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器供應(yīng)。另外因?yàn)榇筮B距離青島較近，公司同意大連分廠向青島直接供貨，運(yùn)輸費(fèi)用如圖，單位是百元。問應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？圖中1-廣州、2-大連、3-上海、4-天津、5-南京、6-濟(jì)南、7-南昌、8-青島13§3運(yùn)輸問題的應(yīng)用三、轉(zhuǎn)運(yùn)問題：14§3運(yùn)輸問題的應(yīng)用解：設(shè)xij

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

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

約束條件：

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

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

-x13-x23+x35+x36+x37+x38=0（上海銷售公司，轉(zhuǎn)運(yùn)站）

-x14-x24+x45+x46+x47+x48=0（天津銷售公司，轉(zhuǎn)運(yùn)站）

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

x36+x46=150（濟(jì)南的銷量）

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

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

xij≥0,i,j=1,2,3,4,5,6,7,814§3運(yùn)輸問題的應(yīng)用解：設(shè)xij為從i到j(luò)的15§3運(yùn)輸問題的應(yīng)用用“管理運(yùn)籌學(xué)”軟件求得結(jié)果：

x13=550x14=50；

x23=0x24=100x28=300；

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

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

試求總費(fèi)用為最少的調(diào)運(yùn)方案。假設(shè)：

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

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

3.除產(chǎn)銷地之外，還有幾個(gè)中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。15§3運(yùn)輸問題的應(yīng)用用“管理運(yùn)籌學(xué)”軟件求得結(jié)果：16§3運(yùn)輸問題的應(yīng)用運(yùn)價(jià)如下表：解：把此轉(zhuǎn)運(yùn)問題轉(zhuǎn)化為一般運(yùn)輸問題：

1、把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時(shí)看作產(chǎn)地和銷地；

2、運(yùn)輸表中不可能方案的運(yùn)費(fèi)取作M，自身對(duì)自身的運(yùn)費(fèi)為0；

3、Ai：產(chǎn)量為20+原產(chǎn)量，銷量為20；Ti

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

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

為自身對(duì)自身的運(yùn)量，實(shí)際上不進(jìn)行運(yùn)作。16§3運(yùn)輸問題的應(yīng)用運(yùn)價(jià)如下表：17§3運(yùn)輸問題的應(yīng)用

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

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

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

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

銷地產(chǎn)地B1B2B3B4

產(chǎn)量A134740A222420A336960

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

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

銷地產(chǎn)地B1B2B3B4

產(chǎn)量A1

43730A23

1410A363930

銷量3060

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

銷地產(chǎn)地B1B2B3B4

產(chǎn)量A11

47A23

14A39

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

銷地產(chǎn)地B1B2B3B4uiA1

1

2430A23

11

-1-1A3

106

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

銷地產(chǎn)地B1B2B3B4uiA1

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

1(-1)

+1-1A3

6

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

銷地產(chǎn)地B1B2B3B4

產(chǎn)量A1

527A23

14A3

6

39

銷量36562020

銷地產(chǎn)地B1B2B3B4uiA1

0

2520A23

2

1

1-1A3

96

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

銷地產(chǎn)地B1B2B3B4A1

(+2)

52(-2)A23(-2)

1(+2)A3

6

3

銷地產(chǎn)地B1B2B3B4A12

5

A21

3A3

6

328§4*運(yùn)輸問題的表上作業(yè)法四、如何找多個(gè)最優(yōu)方案29第七章運(yùn)輸問題§1運(yùn)輸模型§2運(yùn)輸問題的計(jì)算機(jī)求解§3運(yùn)輸問題的應(yīng)用§4*運(yùn)輸問題的表上作業(yè)法1第七章運(yùn)輸問題§1運(yùn)輸模型30例1、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地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)用最小？解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：

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運(yùn)輸模型2例1、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B31§1運(yùn)輸模型一般運(yùn)輸模型：產(chǎn)銷平衡

A1、A2、…、Am

表示某物資的m個(gè)產(chǎn)地；B1、B2、…、Bn

表示某物質(zhì)的n個(gè)銷地；si

表示產(chǎn)地Ai的產(chǎn)量；dj

表示銷地Bj的銷量；cij

表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型：

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í)目標(biāo)函數(shù)求最大。如求利潤(rùn)最大或營(yíng)業(yè)額最大等；

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

3）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。3§1運(yùn)輸模型一般運(yùn)輸模型：產(chǎn)銷平衡32§2運(yùn)輸問題的計(jì)算機(jī)求解例2、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地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)用最小？解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為04§2運(yùn)輸問題的計(jì)算機(jī)求解例2、某公司從兩個(gè)產(chǎn)地A1、A233§2運(yùn)輸問題的計(jì)算機(jī)求解例3、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地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)用最?。拷猓涸黾右粋€(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為05§2運(yùn)輸問題的計(jì)算機(jī)求解例3、某公司從兩個(gè)產(chǎn)地A1、A234§3運(yùn)輸問題的應(yīng)用一、產(chǎn)銷不平衡的運(yùn)輸問題例4、石家莊北方研究院有一、二、三三個(gè)區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，運(yùn)價(jià)為：由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0--300噸，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1500噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。解：根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：這里M代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的x31、x33、x34取值為0。6§3運(yùn)輸問題的應(yīng)用一、產(chǎn)銷不平衡的運(yùn)輸問題35§3運(yùn)輸問題的應(yīng)用一、產(chǎn)銷不平衡的運(yùn)輸問題例5、設(shè)有A、B、C三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表：

試求總費(fèi)用為最低的化肥調(diào)撥方案。解：根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：

最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為M，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為0。對(duì)應(yīng)4”的銷量

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

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

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

把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個(gè)生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個(gè)銷售點(diǎn)的銷量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)?？蓸?gòu)造下列產(chǎn)銷平衡問題：目標(biāo)函數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x449§3運(yùn)輸問題的應(yīng)用解：設(shè)xij為第i季度生產(chǎn)的第38§3運(yùn)輸問題的應(yīng)用二、生產(chǎn)與儲(chǔ)存問題例7、光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺(tái)電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表：已知上年末庫(kù)存103臺(tái)繡花機(jī)，如果當(dāng)月生產(chǎn)出來(lái)的機(jī)器當(dāng)月不交貨，則需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本0.1萬(wàn)元,每臺(tái)機(jī)器每月的平均倉(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)機(jī)器每臺(tái)增加成本1萬(wàn)元。問應(yīng)如何安排1--6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉(cāng)儲(chǔ)、維護(hù)）最少？10§3運(yùn)輸問題的應(yīng)用二、生產(chǎn)與儲(chǔ)存問題39§3運(yùn)輸問題的應(yīng)用解：這個(gè)生產(chǎn)存儲(chǔ)問題可化為運(yùn)輸問題來(lái)做。考慮：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地

1）1--6月份合計(jì)生產(chǎn)能力（包括上年末儲(chǔ)存量）為743臺(tái)，銷量為707臺(tái)。設(shè)一假想銷地銷量為36；

2）上年末庫(kù)存103臺(tái)，只有倉(cāng)儲(chǔ)費(fèi)和運(yùn)輸費(fèi)，把它列為第0行；

3）6月份的需求除70臺(tái)銷量外，還要80臺(tái)庫(kù)存，其需求應(yīng)為70+80=150臺(tái)；

4）1--6表示1--6月份正常生產(chǎn)情況，1’--6’表示1--6月份加班生產(chǎn)情況。產(chǎn)銷平衡與運(yùn)價(jià)表：11§3運(yùn)輸問題的應(yīng)用解：這個(gè)生產(chǎn)存儲(chǔ)問題可化為運(yùn)輸問題40§3運(yùn)輸問題的應(yīng)用

用“管理運(yùn)籌學(xué)”軟件解得的結(jié)果是：1-6月最低生產(chǎn)費(fèi)用為8307.5萬(wàn)元，每月的銷售安排如下表所示12§3運(yùn)輸問題的應(yīng)用用“管理運(yùn)籌學(xué)”軟41§3運(yùn)輸問題的應(yīng)用三、轉(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)地等。例8、騰飛電子儀器公司在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)400臺(tái)，廣州分廠每月生產(chǎn)600臺(tái)。該公司在上海和天津有兩個(gè)銷售公司負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器供應(yīng)。另外因?yàn)榇筮B距離青島較近，公司同意大連分廠向青島直接供貨，運(yùn)輸費(fèi)用如圖，單位是百元。問應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？圖中1-廣州、2-大連、3-上海、4-天津、5-南京、6-濟(jì)南、7-南昌、8-青島13§3運(yùn)輸問題的應(yīng)用三、轉(zhuǎn)運(yùn)問題：42§3運(yùn)輸問題的應(yīng)用解：設(shè)xij

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

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

約束條件：

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

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

-x13-x23+x35+x36+x37+x38=0（上海銷售公司，轉(zhuǎn)運(yùn)站）

-x14-x24+x45+x46+x47+x48=0（天津銷售公司，轉(zhuǎn)運(yùn)站）

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

x36+x46=150（濟(jì)南的銷量）

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

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

xij≥0,i,j=1,2,3,4,5,6,7,814§3運(yùn)輸問題的應(yīng)用解：設(shè)xij為從i到j(luò)的43§3運(yùn)輸問題的應(yīng)用用“管理運(yùn)籌學(xué)”軟件求得結(jié)果：

x13=550x14=50；

x23=0x24=100x28=300；

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

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

試求總費(fèi)用為最少的調(diào)運(yùn)方案。假設(shè)：

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

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

3.除產(chǎn)銷地之外，還有幾個(gè)中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。15§3運(yùn)輸問題的應(yīng)用用“管理運(yùn)籌學(xué)”軟件求得結(jié)果：44§3運(yùn)輸問題的應(yīng)用運(yùn)價(jià)如下表：解：把此轉(zhuǎn)運(yùn)問題轉(zhuǎn)化為一般運(yùn)輸問題：

1、把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時(shí)看作產(chǎn)地和銷地；

2、運(yùn)輸表中不可能方案的運(yùn)費(fèi)取作M，自身對(duì)自身的運(yùn)費(fèi)為0；

3、Ai：產(chǎn)量為20+原產(chǎn)量，銷量為20；Ti

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

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

為自身對(duì)自身的運(yùn)量，實(shí)際上不進(jìn)行運(yùn)作。16§3運(yùn)輸問題的應(yīng)用運(yùn)價(jià)如下表：45§3運(yùn)輸問題的應(yīng)用

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

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

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

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

銷地產(chǎn)地B1B2B3B4

產(chǎn)量A134740A222420A336960

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

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

銷地產(chǎn)地B1B2B3B4

產(chǎn)量A1

43730A23

1410A363930

銷量3060

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

銷地產(chǎn)地B1B2B3B4

產(chǎn)量A11

47A23

14A39

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