運(yùn)輸問題(新)

1、第三章運(yùn)輸問題、運(yùn)輸問題數(shù)學(xué)模型示例：某公司銷售甲方產(chǎn)品，設(shè)有三個(gè)加工廠的四個(gè)銷售點(diǎn)，其加工廠的產(chǎn)量、銷售地的銷售量及各工廠到各銷售點(diǎn)的單位運(yùn)價(jià)見表，如何運(yùn)輸， 總運(yùn)輸費(fèi)最少的xij是從ai到bj的銷售量minz=3x 1111 x 123 x 1310 x 147 x 314 x 3210 x 335 x 34 x 11 x 12 x 13 x 14=7a1x 21 x 22 x 23 x 24=4a2x 31x 32 x 33 x 34=9a 3 i=1，2，3 j=1，2，3，4， x11x20 j=1、2、3、4，上述問題可以擴(kuò)展到m產(chǎn)地的n個(gè)大頭針地的運(yùn)輸問題，設(shè)ai為ai產(chǎn)量，bj

2、為bj大頭針地銷售量，從ai到bj單位運(yùn)輸價(jià)格cij，則生產(chǎn)銷售平衡的運(yùn)輸問題的數(shù)學(xué)模型是，i=1、2、 的m n個(gè)方程對(duì)于產(chǎn)銷平衡問題ai=bj運(yùn)輸問題(產(chǎn)銷平衡)始終是可行解和最優(yōu)解1，cij0 xij 0 cij xij 0運(yùn)輸問題必有有界，2，必有可行解xij=，3，因有界有可行解， 最佳解約束方程式系數(shù)矩陣具有稀疏結(jié)構(gòu)(參照下一頁(yè)為p 11 p 12 p1n p2p 22 pm1pm2pmn 11 a 111 a 233601 am1b 11 b 2336011 bm，m行，n行，第i個(gè)成分，第m個(gè)第j個(gè)成分。 關(guān)于系數(shù)矩陣pij，除了第i個(gè)和第m個(gè)j個(gè)分量為1以外，其馀分量都是0

3、a的前m行之和減去后n行之和后得到的是零向量、即a的行向量線性相關(guān)，其不等于零的子式的最大次數(shù)是m n-1， 表操作法步驟：1.確定初始基本可行解有3種方法進(jìn)行最佳解的判別，如果是最佳則停止，否則下一步驟3 .確定進(jìn)化學(xué)基距離化學(xué)基變量，查找新的基本可能解，返回2，重復(fù)2、3直到得到最佳解。 最小尺元素體、基本思想：步驟：1.從單位運(yùn)輸價(jià)目表中查找最小元素體ckt=min cij 2.根據(jù)與ckt對(duì)應(yīng)的產(chǎn)地生產(chǎn)量ak，根據(jù)銷售地銷售量bt決定運(yùn)輸量調(diào)整量xkt=min ak，bt，將xkt記入銷售平衡表中ak=ak-btakbt，xkt bt=bt-akakak=bt刪除第bt行或第t列，從b

4、t=0或ak=0 3 .未被刪除的要素中查找最小，3、1、4、6、3、3、注意：如果存在多個(gè)最小運(yùn)價(jià)，則任一保證數(shù)字格式的數(shù)量為(m n-1 )個(gè)， 可以選擇在產(chǎn)銷平衡表中填寫數(shù)字的格是數(shù)字格，螺栓凝膠法，思維方法：步驟：1.修正各行各列的最小元素和下一個(gè)最小元素cij的差，分別選擇最右邊的列和最下面的行2 .選擇差最大的行(或列)，該行(列)的最小元素cij 確定0的2，行差額，7，6，最佳解判別： 2個(gè)方法：閉回路法電位法1 .閉回路法：互不相同的2k個(gè)變量x 11 x 21 x kk x1k，閉回路求法：提出了調(diào)運(yùn)方案的生產(chǎn)銷售平衡表，從某個(gè)空格(k，t )格出發(fā)遇到合適的數(shù)字格，轉(zhuǎn)90

5、圈繼續(xù)前進(jìn)，再遇到一個(gè)合適的數(shù)字格，轉(zhuǎn)90圈，繼續(xù)前進(jìn)，最后返回原始的出發(fā)點(diǎn)(k，t )，注意：以空格為起點(diǎn)，以一部分?jǐn)?shù)字格為拐點(diǎn)，最終返回起點(diǎn)，構(gòu)成的路徑稱為閉路。閉合回路是唯一的！ 每個(gè)空間點(diǎn)都可以構(gòu)成閉合回路！ 從(k，t )格出發(fā)對(duì)閉環(huán)的各頂點(diǎn)依次編號(hào)，將(k，t )格作為第一頂點(diǎn)，對(duì)經(jīng)過的其他各頂點(diǎn)依次編號(hào)，將第二、第三頂點(diǎn)設(shè)為11=(c 11 c 23 )-(c 13 c 21 )=(32 )-(31 )=1， 電勢(shì)法設(shè)xij為從ai到bj的運(yùn)輸量，根據(jù)例1的運(yùn)輸問題數(shù)學(xué)模型，設(shè)u1、u2、u3的其對(duì)偶問題為max=ui ai vj bj ui vjcij、ui、vj無(wú)約束、i=1

6、、2、3j=1、2、3、4，同理：一般運(yùn)輸問題數(shù)學(xué)模型vn是與運(yùn)輸問題m的n個(gè)拘束方程式對(duì)應(yīng)的對(duì)偶變量對(duì)偶問題數(shù)學(xué)模型： max=ui ai vj bj ui vjcij ui，vj無(wú)拘束ui，vj也分別稱為與出發(fā)點(diǎn)(產(chǎn)地) i和收點(diǎn)(大頭針地) j對(duì)應(yīng)的電位，i=1，2， 如果將mj=1，2，n，化學(xué)基b作為運(yùn)輸問題的可執(zhí)行化學(xué)基，則雙對(duì)變量y=cbb-1=(u1，u2，um，v1，v2， vn )根據(jù)用于確定變量xij的系數(shù)列向量的簡(jiǎn)單算法的原理，基本變量檢驗(yàn)常數(shù)為零的cij-ui-vj=0 cij=ui vj xijxb可以將一個(gè)運(yùn)輸場(chǎng)景中所有基本變量的運(yùn)輸價(jià)格cij分解為對(duì)應(yīng)的行電勢(shì)和

7、列電勢(shì)兩者接下來(lái)的頁(yè)面：能夠求出基于基變量cij=ui vj的非基變量檢驗(yàn)常數(shù)ij=的ij例：例1初始傳送表如下表所示，該例： m=3、n=4、基變量為6個(gè)、對(duì)應(yīng)的cij方程式也為6個(gè)、電位量(雙對(duì)變量)為7個(gè)、6個(gè)方程式為對(duì)設(shè)u1為自由的u1=0c 13=u1v3=3v3=3c 14=u1v4=10 c 23=u2v3=2u2=-1 c 21=u2v1=2c 34=的非基礎(chǔ)變量的檢查數(shù)ij=cij-ui-vj進(jìn)行校正，上述的校正運(yùn)算過程能夠在表中進(jìn)行注：上表右上犄角旮旯的數(shù)字為單位運(yùn)費(fèi)，左下犄角旮旯的紅色數(shù)字為非基本變量檢驗(yàn)數(shù)，中間藍(lán)色數(shù)字說明運(yùn)量上表有負(fù)檢驗(yàn)數(shù)，不是最佳解。 1、2、1、-

8、1、10、12、勢(shì)能法的步驟除此之外的情況下，轉(zhuǎn)3、計(jì)劃調(diào)整。調(diào)試方案的改良閉路調(diào)整法1、將進(jìn)化學(xué)基格(進(jìn)化學(xué)基變量) min=ij ij 0=kt xkt進(jìn)行化學(xué)基格2、從進(jìn)化學(xué)基格(k，t )制作閉路，對(duì)各頂點(diǎn)依次決定編號(hào)、3、調(diào)整量和距離化學(xué)基格調(diào)整量4、閉路調(diào)整：閉路上：奇數(shù)頂點(diǎn)運(yùn)輸量q雙位數(shù)頂點(diǎn)運(yùn)輸量-q其本身5、2、3、1、6、3、0、3、10、-5、9，對(duì)于運(yùn)輸問題解： 1，無(wú)窮多最佳解：2，解：基本變量可能取零值。、31145、738、12106、3、6、4、1、6、0、31145、738、12106、第3 k行或第t列刪除，繼續(xù)查找其他數(shù)字，在云同步中刪除第k行和第t列，在刪

9、除的行或列中的某個(gè)空格中填入零作為數(shù)字格式2 ) 用閉環(huán)法改善調(diào)整方案時(shí)：閉環(huán)頂點(diǎn)出現(xiàn)2個(gè)以上的最小運(yùn)輸量，調(diào)整后從這些個(gè)的雙位數(shù)頂點(diǎn)減去調(diào)整量后，運(yùn)輸量為零，產(chǎn)銷不平衡運(yùn)輸問題及其解決方法1，產(chǎn)銷： ai bj，xijaiii=1，2 mxij=bj=1，2n，松弛變量4，2，3，3，3，3，2，2，3，ui，vj，0，2，4，0，- 2，3，0，3 xij=ai 1，21，j=1，n，ij=bjj=1，2 n，i=1，m 1，示例2:設(shè)有三個(gè)化學(xué)肥料工廠17、15、-、d、m、0、m、0、m、0、50、30、70、30、10、20、50，用表工藝要求的最佳方案如下。 1500、500、500、500、500、500、500、ui、vj、0、0、4、6、5、4、12 17、18-c22、-3c220、10-c220、24-c22018-c22