運(yùn)籌學(xué)(第3章 運(yùn)輸問題)

運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用(OperationsResearch)主講：楊啟明運(yùn)輸問題的典例和數(shù)學(xué)模型1求解方法——表上作業(yè)法2產(chǎn)銷不平衡運(yùn)輸問題3第3章運(yùn)輸問題3.1運(yùn)輸問題的典例和數(shù)學(xué)模型例1.某食品公司經(jīng)銷的主要產(chǎn)品之一是糖果.它下面設(shè)有三個(gè)加工廠,每天的糖果產(chǎn)量分別為:A1-7t,A2-4t,A3-9t.該公司把這些糖果分別運(yùn)往四個(gè)地區(qū)的門市銷售,各地區(qū)每天的銷售量分別為：B1-3t,B2-6t，B3-5t,B3-6t.已知從每個(gè)加工廠到各銷售門市部每噸的運(yùn)價(jià)如表所示，問該食品公司應(yīng)如何調(diào)運(yùn),在滿足各門市部銷售需要的情況下，使得總的運(yùn)費(fèi)支出為最少。加工廠A17T加工廠A24T加工廠A39T門市B13t門市B26t門市B35t門市B46t1113109287410153表3-1單位：元/tB1B2B3B4生產(chǎn)能力A13113107A219284A3741059需求3656食品調(diào)運(yùn)問題：確定合理的調(diào)運(yùn)方案，使得總運(yùn)費(fèi)支出最少。B1B2B3B4生產(chǎn)能力A13113107A219284A3741059需求3656運(yùn)輸問題的數(shù)學(xué)模型設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的物資數(shù)量(i=1,…m;j=1,…n），建立規(guī)劃模型AiBj

運(yùn)輸問題的一般提法

現(xiàn)有一批貨物,從m個(gè)供應(yīng)地運(yùn)往n個(gè)銷售地,Ai(i=1,‥‥,m)處有貨物ai噸，Bj(j=1,‥‥,n)處需貨物bj噸,已知從Ai到Bj的運(yùn)價(jià)為cij

元/噸.

問如何安排，既可以滿足各銷地需要，又使總費(fèi)用最?。緼1A2Am︰︰B1B2Bn︰︰a1a2am︰︰b1b2bm︰︰供應(yīng)量需求地供應(yīng)地需求量調(diào)運(yùn)量xij運(yùn)輸問題的框圖表示產(chǎn)銷表運(yùn)輸問題的數(shù)學(xué)模型單位運(yùn)價(jià)表運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸表（運(yùn)價(jià)，運(yùn)量）作業(yè)表銷量產(chǎn)量銷地產(chǎn)地產(chǎn)銷平衡條件下設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的物資數(shù)量(i=1,…m;j=1,…n）從Ai運(yùn)出的物資總量應(yīng)等于Ai的產(chǎn)量ai，xij應(yīng)滿足：

運(yùn)到Bj的物資總量應(yīng)該等于Bj的銷量bj，xij還應(yīng)滿足：運(yùn)輸問題的數(shù)學(xué)模型總運(yùn)費(fèi)為：運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題的數(shù)學(xué)模型在產(chǎn)銷平衡條件下，線性規(guī)劃模型可寫為：1.約束條件都是等式約束2.總產(chǎn)量＝總銷量產(chǎn)銷平衡的運(yùn)輸問題的特點(diǎn)與性質(zhì)3.系數(shù)矩陣是一個(gè)結(jié)構(gòu)特殊的稀疏矩陣將約束方程組展開約束方程組共包含m×n個(gè)變量，(m+n)個(gè)約束條件產(chǎn)銷平衡的運(yùn)輸問題的特點(diǎn)與性質(zhì)產(chǎn)銷平衡的運(yùn)輸問題的特點(diǎn)與性質(zhì)系數(shù)矩陣A：m行n行

矩陣的元素均為1或0；每一列只有兩個(gè)元素為1，其余元素均為0；將矩陣分塊,特點(diǎn)是:前m行構(gòu)成m個(gè)m×n階矩陣,而且第k個(gè)矩陣只有第k行元素全為1,其余元素全為0（k=1,…,m）;后n行構(gòu)成m個(gè)n階單位陣。A的秩一般為m+n-1

m行n行為什么？第i行第m+j行

作業(yè)表（產(chǎn)銷平衡表）：將運(yùn)輸問題的有關(guān)信息表和決策變量——調(diào)運(yùn)量結(jié)合在一起構(gòu)成“作業(yè)表”（產(chǎn)銷平衡表）。表上作業(yè)法是單純形法求解運(yùn)輸問題的一種簡(jiǎn)化方法，實(shí)質(zhì)是單純形法。但是具體計(jì)算和術(shù)語有所不同。銷量產(chǎn)量銷地產(chǎn)地3.2表上作業(yè)法運(yùn)輸問題中尋找可行解1023206563銷量9563474829217101143

3產(chǎn)量銷地產(chǎn)地填有數(shù)字的格:對(duì)應(yīng)運(yùn)輸問題解中的基變量取值，這里為3+4-1=6個(gè)空格：對(duì)應(yīng)解中非基變量表上作業(yè)法的基本思想是:先設(shè)法給出一個(gè)初始方案(如典例所示),然后根據(jù)確定的判別準(zhǔn)則對(duì)初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案。表上作業(yè)法和單純形法的求解思想完全一致，但是具體作法更加簡(jiǎn)捷。3.2表上作業(yè)法

確定初始方案(初始基可行解)

改進(jìn)調(diào)整（換基迭代）否

判定是否最優(yōu)？是結(jié)束最優(yōu)方案——求解思路圖表上作業(yè)法1.最小元素法2.沃格爾（Vogel）法(一)初始方案的給定給定初始方案的方法很多(如前例)，一般來說，希望方法簡(jiǎn)便易行，并能給出較好的方案。減少迭代次數(shù)。這里介紹1.最小元素法基本思想：就近供應(yīng)，即優(yōu)先考慮單位運(yùn)價(jià)最?。ɑ蜻\(yùn)距最短）的供銷業(yè)務(wù)，最大限度地滿足其供銷量。銷地產(chǎn)地產(chǎn)量311310719284741059銷量3656203－3－31－1－1－4－4-6－66433－3－3-3-3銷地產(chǎn)地產(chǎn)量311310719284741059銷量365620316433Z=4*3+3*10+3*1+1*2+6*4+3*5=86最小元素法的說明退化現(xiàn)象：

部分產(chǎn)量和＝部分銷量和在迭代過程中，可能出現(xiàn)一行和一列同時(shí)被劃去。銷地產(chǎn)地產(chǎn)量31145777384121069銷量36562034－4－4－1－1-6－6616－3－3－6-60為使迭代過程中基變量的個(gè)數(shù)恰好為(m+n-1)個(gè)，應(yīng)在同時(shí)劃去的一行或一列中的某個(gè)格中填入數(shù)字0，表示這個(gè)格中的變量是取值為0的基變量。以便當(dāng)做有數(shù)字的格看待。銷地產(chǎn)地產(chǎn)量31145777384121069銷量365620346160基本思想：優(yōu)選考慮最大差額（最小運(yùn)價(jià)優(yōu)勢(shì)）方案行（列）差額（罰數(shù)）=次小運(yùn)價(jià)系數(shù)-最小運(yùn)價(jià)系數(shù)2.沃格爾（Vogel）法(差額法)行差額列差額1023206563銷量95474891710113產(chǎn)量

銷地產(chǎn)地0112513()6220071312121162()33()521108()1023206563銷量95474891710113產(chǎn)量

銷地產(chǎn)地633521一般當(dāng)產(chǎn)銷地?cái)?shù)量不多時(shí)，(Vogel)法給出的初始方案有時(shí)就是最優(yōu)方案。沃格爾法Z=5*3+2*10+3*1+1*8+6*4+3*5=85最小元素法Z=4*3+3*10+3*1+1*2+6*4+3*5=86>8529練習(xí).求下表給出的運(yùn)輸問題的初始基本可行解．

B1B2B3B4產(chǎn)量A14104420A2773815A31210615銷量510251050(一)初始方案的給定30

銷地產(chǎn)地B1B2B3B4aiA14104420A2773815A31210615銷量5102510505100151010(一)初始方案的給定31BjAiB1B2B3B4aiA14104420A2773815A31210615bj5102510505100151010(一)初始方案的給定

最小元素法或Vogel法給出的是一個(gè)運(yùn)輸問題的基可行解，需要通過最優(yōu)性檢驗(yàn)判別該解得目標(biāo)函數(shù)值是否最優(yōu)，當(dāng)為否時(shí)，應(yīng)進(jìn)行調(diào)整得到優(yōu)化.(二)最優(yōu)性檢驗(yàn)與方案的調(diào)整基本思想：計(jì)算非基變量（未填上數(shù)值的格，即空格）的檢驗(yàn)數(shù)（也稱為空格的檢驗(yàn)數(shù)），若全部大于等于零，則該方案就是最優(yōu)調(diào)運(yùn)方案，否則就應(yīng)進(jìn)行調(diào)整。1.閉回路法2.對(duì)偶變量法（位勢(shì)法）沿水平或垂直方向前，向左或右轉(zhuǎn)90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做閉回路。閉回路

x25x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12x31

x42表中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8個(gè)頂點(diǎn)，這8個(gè)頂點(diǎn)間用水平或垂直線段連接起來，組成一條封閉的回路。

運(yùn)輸問題中的閉回路有關(guān)閉回路的一些重要結(jié)果

定理3-設(shè)是一個(gè)閉回路，則該閉回路中的變量所對(duì)應(yīng)的系數(shù)列向量具有下面的關(guān)系：推論

若一組變量包含閉回路，則這組變量所對(duì)應(yīng)的系數(shù)列向量線性相關(guān)。

推論

m+n-1個(gè)變量構(gòu)成基變量的充要條件是該變量組不含閉回路。將如下表中6個(gè)頂點(diǎn)間用水平或垂直線段連接起來，組成一條封閉的回路。1023206563銷量95346748191371034113產(chǎn)量

銷地產(chǎn)地(A2,B1),(A3,B2)無法連入閉回路中閉回路孤立格是指在所在行或列中唯一出現(xiàn)的變量。孤立格一定不會(huì)成為閉回路的頂點(diǎn)最小元素法得初始方案

以確定了初始調(diào)運(yùn)方案的作業(yè)表為基礎(chǔ)，以一個(gè)非基變量作為起始頂點(diǎn)，尋求閉回路。

該閉回路的特點(diǎn)是：除了起始頂點(diǎn)是非基變量（對(duì)應(yīng)著空格）外，其他頂點(diǎn)均為基變量（對(duì)應(yīng)著填有數(shù)字的格）。對(duì)于每一個(gè)非基變量而言，以其為起點(diǎn)的閉回路存在且唯一。運(yùn)輸問題中的閉回路目的：計(jì)算解中各非基變量(空格)的檢驗(yàn)數(shù)基本思路：對(duì)于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1（每次調(diào)整一個(gè)非基變量）；由于產(chǎn)銷平衡的要求我們必須對(duì)這個(gè)空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少1(可行條件)；計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化，這里稱之為檢驗(yàn)數(shù)。閉回路法求檢驗(yàn)數(shù)4.如果所有代表非基變量的空格的檢驗(yàn)數(shù)也即非基變量的檢驗(yàn)數(shù)都大于等于零，則已求得最優(yōu)解，否則進(jìn)行方案調(diào)整（后續(xù)）23206563銷量9544

11

3710

產(chǎn)量

銷地產(chǎn)地64333同理可以找出所有空格（即非基變量）的檢驗(yàn)數(shù)。+1－1＋1－1總運(yùn)費(fèi)變化＝即此新可行解較原來解運(yùn)費(fèi)增加1元閉回路法求檢驗(yàn)數(shù)閉回路法求檢驗(yàn)數(shù)23206563銷量954411

3710

產(chǎn)量

銷地產(chǎn)地6433-1+1-1+1-1+1總運(yùn)費(fèi)變化＝7

約定作為起始頂點(diǎn)的非基變量為第一個(gè)奇數(shù)次頂點(diǎn)，相鄰頂點(diǎn)為偶次頂點(diǎn)，其它頂點(diǎn)依次排列，那么，該非基變量xij的檢驗(yàn)數(shù)：=（閉回路上奇數(shù)次頂點(diǎn)運(yùn)價(jià)之和）－（閉回路上偶數(shù)次頂點(diǎn)運(yùn)價(jià)之和）

-11A21210A321A1B4B3B2B1銷地產(chǎn)地檢驗(yàn)數(shù)表閉回路法求檢驗(yàn)數(shù)當(dāng)至少有一個(gè)非基變量的檢驗(yàn)數(shù)是負(fù)值時(shí)，說明作業(yè)表上當(dāng)前的調(diào)運(yùn)方案不是最優(yōu)的，應(yīng)進(jìn)行調(diào)整。請(qǐng)畫出下表空格(1,1)和(1,4)的閉回路10050120708090閉回路法求調(diào)整方案選一個(gè)非基變量變?yōu)榛兞窟M(jìn)基選一個(gè)基變量變?yōu)榉腔兞侩x基反映在運(yùn)輸表上就是要選一個(gè)空格填上大于0的數(shù)選擇入基的原則是：從絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)格(k,l)出發(fā)閉回路法求調(diào)整方案-11A21210A321A1B4B3B2B1銷地產(chǎn)地檢驗(yàn)數(shù)表在作業(yè)表上以（A2,B4）為起點(diǎn)作一條除該空格外其余頂點(diǎn)均為有數(shù)字格組成的閉回路閉回路法求調(diào)整方案206563銷量94

1

374

產(chǎn)量銷地產(chǎn)地

6

33

調(diào)運(yùn)方案（最小元素法得到）+1-1=min{3,1}=1離基？在作業(yè)表上以（A2,B4）為起點(diǎn)作一條除該空格外其余頂點(diǎn)均為有數(shù)字格組成的閉回路在這條閉回路上，在保持產(chǎn)銷平衡的條件下對(duì)偶數(shù)頂點(diǎn)格子的運(yùn)量做最大可能的調(diào)整+1-1閉回路法求調(diào)整方案（A2,B4）為起點(diǎn)作一條出該空格外其余頂點(diǎn)均為有數(shù)字各組成的閉回路206563銷量94

375

產(chǎn)量

銷地產(chǎn)地

6

32

調(diào)運(yùn)方案（最小元素法得到）1=min{3,1}=1繼續(xù)用閉回路檢驗(yàn)，直到檢驗(yàn)數(shù)σ≥01.在作業(yè)表上從絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)格(k,l)出發(fā),即xkl為起始變量作出閉回路。2.以空格(k,l)為第一個(gè)奇數(shù)頂點(diǎn)，沿閉回路的順（或逆）時(shí)針方向依次對(duì)頂點(diǎn)編號(hào)。3.在閉回路上的所有偶數(shù)頂點(diǎn)中，找出運(yùn)輸量最小的格子，以該格對(duì)應(yīng)的變量為離基變量。4.調(diào)整量5.將該閉回路上所有奇數(shù)頂點(diǎn)處的運(yùn)輸量都增加

所有偶數(shù)頂點(diǎn)處的運(yùn)輸量都減去ij

=min{該閉回路中偶數(shù)次頂點(diǎn)運(yùn)輸量xij}閉回路法求調(diào)整方案

在閉回路方法當(dāng)中，要判斷一個(gè)方案是否最優(yōu)，需要通過每一個(gè)空格來尋找回路，以及根據(jù)閉回路求出每個(gè)空格的檢驗(yàn)數(shù)，當(dāng)一個(gè)運(yùn)輸問題的產(chǎn)地和銷地很多時(shí)，用此方法工作量十分繁重.位勢(shì)法位勢(shì)法是根據(jù)對(duì)偶理論推導(dǎo)出來的一種求解檢驗(yàn)數(shù)方法。運(yùn)輸方案的調(diào)整同前面的閉回路法.49位勢(shì)法求檢驗(yàn)數(shù)原問題對(duì)偶問題50記原問題基變量XB的下標(biāo)集合為I，有如下式子成立：解上面第一個(gè)方程，將ui、vj代入第二個(gè)方程求出檢驗(yàn)數(shù),稱ui(i=1,…,m),vj(j=1,…,n)分別成為第i行和第j列的位勢(shì)回憶：這里Pij有如何特殊形式?位勢(shì)法求檢驗(yàn)數(shù)對(duì)偶變量uiu1u2u3對(duì)偶變量vjv1v2v3v4不妨令v1=1，則u2=0;v3=2;u1=1;v4=9;u3=-4;v2=8.(1)(0)(-4)(1)(8)(2)(9)1023206563銷量95346748191371034113產(chǎn)量

銷地產(chǎn)地注意：由于這些位勢(shì)的數(shù)值是相互關(guān)聯(lián)的，所以填寫時(shí)可以先任意決定其中的一個(gè)，然后推導(dǎo)出其他位勢(shì)的數(shù)值。A2A3A1B4B3B2B1銷地產(chǎn)地檢驗(yàn)數(shù)表121-11012uiu1u2u3vjv1v2v3v4(1)(0)(-4)(1)(8)(2)(9)1023206563銷量95346748191371034113產(chǎn)量

銷地產(chǎn)地位勢(shì)法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式σij=cij-（ui+vj）=（閉回路上奇數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）-（閉回路上偶數(shù)次頂點(diǎn)運(yùn)距或運(yùn)價(jià)之和）閉回路法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式：復(fù)習(xí)比較檢驗(yàn)數(shù)計(jì)算的兩種方法思考：試解釋位勢(shì)變量的含義（提示：寫出運(yùn)輸問題的對(duì)偶問題）表

上

作

業(yè)

法得到最優(yōu)方案算出的總運(yùn)價(jià)分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表求檢驗(yàn)數(shù)（閉回路法或位勢(shì)法）

是確定初始調(diào)運(yùn)方案（最小元素法或Vogel法）

找出絕對(duì)值最大的負(fù)的檢驗(yàn)數(shù)用閉回路調(diào)整，得出新的調(diào)運(yùn)方案否循環(huán)所有檢驗(yàn)數(shù)≥0求

解步驟1產(chǎn)銷2銷產(chǎn)3.擴(kuò)大的運(yùn)輸問題（中轉(zhuǎn)站）3.3產(chǎn)銷不平衡運(yùn)輸問題及其應(yīng)用Minz=cij·xijni=1j=1mMinz=cij·xij+0xi,n+1ni=1j=1mi=1m相當(dāng)于：增加一個(gè)假想銷地1.產(chǎn)銷問題ai>bj產(chǎn)地銷地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnBn+1０

０┆０銷量產(chǎn)量b1 b2 ┈

bna1a2┊a(chǎn)maibj相當(dāng)于：增加一個(gè)假想銷地產(chǎn)銷問題單位運(yùn)價(jià)表Minz=cij·xijni=1j=1mMinz=cij·xij+0xm+1,jni=1j=1mj=1n銷產(chǎn)問題相當(dāng)于：增加一個(gè)假想產(chǎn)地ai<bj產(chǎn)地銷地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnAm+10 0 ┈ 0銷量產(chǎn)量b1 b2 ┈

bna1a2┊a(chǎn)mbjai銷產(chǎn)問題單位運(yùn)價(jià)表相當(dāng)于：增加一個(gè)假想產(chǎn)地例一：某工廠按合同規(guī)定必須于當(dāng)年的每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如表示。又如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需要存儲(chǔ)維護(hù)費(fèi)用0.15萬元。要求在完成合同的情況下，做出使全年生產(chǎn)費(fèi)用最小的決策。季度生產(chǎn)能力(臺(tái))單位成本(萬元/臺(tái))ⅠⅡⅢⅣ2535301010.811.111.011.3運(yùn)輸問題案例1數(shù)學(xué)模型：設(shè)xij第i季度生產(chǎn)，用于第j季度交貨的數(shù)量。目標(biāo)函數(shù)：

minz=cijxiji=1j=1

44x11+x12+x13+x1425

x22+x23+x2435

x33+x3430

x4410x11=10x12+x22

=15x13+x23+x33

=25x14+x24+x34+x44=20xij0,(i=1,····,4;j=1,····,4)供應(yīng)：ⅠⅡⅢⅣⅠⅡⅢⅣ需求：季度生產(chǎn)能力(臺(tái))單位成本(萬元/臺(tái))ⅠⅡⅢⅣ2535301010.811.111.011.3某工廠按合同規(guī)定必須于當(dāng)年的每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。合同要求交貨不得超過生產(chǎn)力產(chǎn)>銷數(shù)學(xué)模型：季度生產(chǎn)能力(臺(tái))單位成本(萬元/臺(tái))ⅠⅡⅢⅣ2535301010.811.111.011.3每臺(tái)每積壓一個(gè)季度需要存儲(chǔ)維護(hù)費(fèi)用0.15萬元。單位運(yùn)價(jià)表：ⅠⅡⅢⅣ銷量ⅠⅡ Ⅲ ⅣD產(chǎn)量10.8 10.95 11.1011.25025

M11.1011.25

11.40035

M

M 11.00

11.15030單位：萬元供應(yīng)需求10 15 25

2030M MM

11.30010當(dāng)i>j時(shí)，必須xij=0，令cij=M(很大的正數(shù))，加以懲罰產(chǎn)>銷

例二有A、B、C三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)Ⅰ、Ⅱ、Ⅲ、Ⅳ的農(nóng)用化肥，三個(gè)工廠每年各自的產(chǎn)量為A--50萬噸，B--60萬噸，C--50萬噸。四個(gè)地區(qū)的需求量分別是Ⅰ地區(qū)最高50萬噸，最低30萬噸，Ⅱ地區(qū)為70萬噸，Ⅲ地區(qū)為30萬噸以下，Ⅳ地區(qū)不低于10萬噸。問：如何調(diào)運(yùn)，可使總的調(diào)運(yùn)費(fèi)用最??？單位調(diào)運(yùn)費(fèi)用如下表所示。產(chǎn)地銷地A1A2A3B1B2B3B4產(chǎn)量銷量1613221714131915192023―單位運(yùn)價(jià)表50605030-50700-3010-單位：萬元/萬噸設(shè)xij--第i工廠調(diào)至第j需求地區(qū)的化肥數(shù)量運(yùn)輸問題案例2銷產(chǎn)上限50運(yùn)輸問題案例2ABCDⅠ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ

16 16 13 22 17 1714 14 13 19 15 1519 19 20 23 M MM 0 M 0 M 0供應(yīng)需求產(chǎn)量銷量50605050

30

20

70

30

10

50修正運(yùn)價(jià)表產(chǎn)地銷地A1A2A3B1B2B3B4產(chǎn)量銷量1613221714131915192023―單位運(yùn)價(jià)表50605030-50700-3010-單位：萬元/萬噸設(shè)xij--第i工廠調(diào)至第j需求地區(qū)的化肥數(shù)量銷產(chǎn)擴(kuò)大的運(yùn)輸問題例：在前面的糖果例題中，若既可以從Ai運(yùn)到Bj，也可以經(jīng)過中間站T1、T2、T3、T4或者Ai、Bj轉(zhuǎn)運(yùn)，稱擴(kuò)大的運(yùn)輸問題。幾點(diǎn)說明：1.所有的產(chǎn)地、銷地、中間站均視作產(chǎn)地、銷地；2.所有中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量等于總的產(chǎn)量之和；3.不能出現(xiàn)循環(huán)倒運(yùn)現(xiàn)象，允許自身往自身最多調(diào)運(yùn)一次，運(yùn)價(jià)為Cij=0；4.實(shí)際產(chǎn)地產(chǎn)量為轉(zhuǎn)運(yùn)量與該產(chǎn)地實(shí)際產(chǎn)量之和，實(shí)際銷地銷量為轉(zhuǎn)運(yùn)量與實(shí)際銷量之和。A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130產(chǎn)銷產(chǎn)量銷量27242920202020202020202020202020202023262526產(chǎn)銷平衡表

某餐館承辦宴會(huì)，每晚連續(xù)舉行，共舉行五次。宴會(huì)上需用特殊的餐巾，根據(jù)參加的人數(shù)，預(yù)計(jì)