【文章內(nèi)容簡(jiǎn)介】 變量集合 稱(chēng)為一個(gè) 閉回路 ,并稱(chēng)式中 變量 為該 閉回路的頂點(diǎn) ；其中 互不相同 , 互不相同 。 132222111 ,, jijijijijiji sss xxxxxx ?sss jijijijijiji xxxxxx 123221211 ,, ?siii , 21 ?sjjj , 21 ?1)閉回路法 ① 什么是閉回路 ? 第三章 運(yùn)輸問(wèn)題 X11 X13 X21 X24 X33 B1 B2 B3 B4 A1 X12 X14 A2 X22 X23 A3 X31 X32 X34 例 設(shè) m=3， n=4，決策變量 xij表示從產(chǎn)地 Ai到銷(xiāo)地 Bj的調(diào)運(yùn)量，列表如下，給出閉回路 在表中的表示法 ——用折線連接起來(lái)的頂點(diǎn)變量 。 },,{ 212434331311 xxxxxx第三章 運(yùn)輸問(wèn)題 練習(xí) 請(qǐng)給出閉回路 和 在表中的表示法 。 },{ 14242212 xxxx},,{ 121131332322 xxxxxx X11 X13 X21 X24 X33 B1 B2 B3 B4 A1 X12 X14 A2 X22 X23 A3 X31 X32 X34 第三章 運(yùn)輸問(wèn)題 練習(xí) 下面的折線構(gòu)成的封閉曲線連接的頂點(diǎn)變量哪些不可能是閉回路？為什么？ （ a） （ b） （ c） （ d） （ e） ? 表中的折線構(gòu)成一條封閉曲線 ， 且所有的邊都是 水平 或 垂直 的；為什么 ？ ? 表中的 每一行 和 每一列 由折線相連的閉回路的頂點(diǎn) 只有兩個(gè) ；為什么 ？ 第三章 運(yùn)輸問(wèn)題 從每一空格出發(fā)一定存在和可以找到唯一的閉回路 . ? 證明 :因 (mn1)個(gè)數(shù)字格 (基變量 )對(duì)應(yīng)的系數(shù)向量是一個(gè)基 .任一空格 (非基變量 )對(duì)應(yīng)的系數(shù)向量是這個(gè)基的線性組合 .如 Pij,可表示為 : Pij=ei+em+j=ei+em+kem+k+elel+em+sem+s+eueu+em+j =(ei+em+k)(el+em+k)+(el+em+s)(eu+em+s)+(eu+em+j) =PikPlk+PlsPus+Puj 其中 Pik,Plk,Pls,Pus,Puj基矩陣 B中的向量 . 為什么是唯一的呢 ?假設(shè)存在另一個(gè)閉回路 ,則在 Pij某一行或某一列存在兩個(gè)非基變量 ,那么這些非基變量可自行組成閉回路 注意 :列向量 Pij =(0,…,0,1,0,…,0,1,0,…0) T中兩個(gè)元素 1 分別處于第 i行和第 m+j行，直接計(jì)算即可得到結(jié)果。 第三章 運(yùn)輸問(wèn)題 ② 閉回路法求檢驗(yàn)數(shù)求某一非基變量的檢驗(yàn)數(shù)的方法： 在基本可行解矩陣中，以該非基變量為起點(diǎn)，以基變量為其它頂點(diǎn)，找一條閉回路，由起點(diǎn)開(kāi)始，分別在頂點(diǎn)上交替標(biāo)上代數(shù)符號(hào)＋、－、＋、－、 … －，以這些符號(hào)分別乘以相應(yīng)的運(yùn)價(jià)，其代數(shù)和就是這個(gè)非基變量的檢驗(yàn)數(shù)。 該閉回路的特點(diǎn)是： 除了起始頂點(diǎn)是非基變量外，其他頂點(diǎn) 均為基變量（對(duì)應(yīng)著填上數(shù)值的格）。 可以證明， 如果對(duì)閉回路的方向不加區(qū)別，對(duì)于每一個(gè)非基變 量而言，以其為起點(diǎn)的閉回路 存在且唯一 。 第三章 運(yùn)輸問(wèn)題 現(xiàn)在，在 用最小元素法確定例 2初始調(diào)運(yùn)方案 的基礎(chǔ)上， 計(jì)算非基變量X11,X12,X22,X24,X31,X33的檢驗(yàn)數(shù) ： 閉回路法求檢驗(yàn)數(shù)經(jīng)濟(jì)含義：在保持產(chǎn)銷(xiāo)平衡的條件下 ，該非基變量增加一個(gè)單位運(yùn)量而成為基變量時(shí)目標(biāo)函數(shù)值的變化量 。 第三章 運(yùn)輸問(wèn)題 3 11 1 7 4 3 2 8 5 10 10 9 20 6 5 6 3 9 4 7 3 2 1 4 3 2 1 A A A B B B B 銷(xiāo)量 產(chǎn)量 3 1 4 6 3 3 860 ?z從初始表分析： 要保證產(chǎn)銷(xiāo)平衡，則 11*)1(2*)1(3*)1(3*)1(11 ?????????? ?1111 21231311 ??????? xxxx 稱(chēng)為閉回路 21231311 xxxx ???+1 1 +1 1 第三章 運(yùn)輸問(wèn)題 3 11 1 7 4 3 2 8 5 10 10 9 20 6 5 6 3 9 4 7 3 2 1 4 3 2 1 A A A B B B B 銷(xiāo)量 產(chǎn)量 3 1 4 6 3 3 245101112 ??????1451032922 ????????2 1 第三章 運(yùn)輸問(wèn)題 計(jì)算所有非基變量的檢驗(yàn)數(shù) 非基變量 X11的檢驗(yàn)數(shù)為 : σ 11=c11c13+c23c21=33+21=1 非基變量 X11的檢驗(yàn)數(shù)為 : σ 12=c12c14+c33c32=1110=+54=2 同理可找出其它非基變量的閉回路 ,然后計(jì)算其檢驗(yàn)數(shù)分別為 : σ 22=c22c23+c13c14+c34c32=92+310+54=1 σ 24=c24c23+c13c14=1 σ 31=c31c34+c14c13+c23c21 =10 σ 33=c33c34+c14c13=12 當(dāng)所有的非基變量的檢驗(yàn)數(shù)都計(jì)算出來(lái)之后 ,就可以判斷原方案是不是最優(yōu)解 . 第三章 運(yùn)輸問(wèn)題 檢驗(yàn)數(shù)表 3 11 1 7 4 3 2 8 5 10 10 9 20 6 5 6 3 9 4 7 3 2 1 4 3 2 1 A A A B B B B 銷(xiāo)量 產(chǎn)量 3 1 4 6 3 3 2 1 1 1 10 12 ???? ,0124?? 表中的解不是最優(yōu)解。 第三章 運(yùn)輸問(wèn)題 2)位勢(shì)法 (對(duì)偶變量法 ,dual variable method) ? 位勢(shì)法 : 位勢(shì)法求檢驗(yàn)數(shù)是根據(jù)對(duì)偶理論推導(dǎo)出來(lái)的一種方法。 產(chǎn)銷(xiāo)平衡運(yùn)輸模型 : 若用 u1,u2,…,u m分別表示前 m個(gè)約束等式相應(yīng)的對(duì)偶變量 。用v1,v2,…,v n表示后 n個(gè)等式約束的對(duì)偶變量 . ???????????????????? ???? ?njmixnjbxmiaxtsxcM i n Zijmijijnjiijminjijij,1。,1,0,1,1..111 1????第三章 運(yùn)輸問(wèn)題 則有對(duì)偶變量向量 Y=(u1,u2,…,u m, v1,v2,…, v n) 這時(shí)可得運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題 線性規(guī)則決策變量的檢驗(yàn)數(shù) ????? ?????? ????的符號(hào)不限jiijjinjjjmiiivunjmicvuvbuaw,1,1m a x11??第三章 運(yùn)輸問(wèn)題 故可得以下一組方程由基變量檢驗(yàn)數(shù)等于零其基變量是解運(yùn)輸問(wèn)題的一個(gè)基可行假設(shè)我們已得到了上述的檢驗(yàn)數(shù)如下變量從而可寫(xiě)出運(yùn)輸問(wèn)題某，nmsxxx，vucPvvvuuucYPczcxYPcPBCczcssjijijijiijijnmijijijijijijijjjjBjjjj1,)(),,(:221121211????????????????????????第三章 運(yùn)輸問(wèn)題 .v及u.v及u。的一 組v及u0 ， ， 可得u一般有一個(gè)自由 變.1jijiji122221111的值中求得已求得的非基變量的檢驗(yàn)數(shù)可從因此的解稱(chēng)為位勢(shì)求得解令故量故解不唯一多一個(gè)由于對(duì)偶變量比方程數(shù)個(gè)方程方程組有顯然，，nm，cvucvucvussssjijijijijiji?????????????????第三章 運(yùn)輸問(wèn)題 書(shū)上 :設(shè) u1,u2,…,u m。v1,v2,…,v n是對(duì)應(yīng)運(yùn)輸問(wèn)題的 m+n個(gè)約束條件 的對(duì)偶變量 . B是含有人工變量 xa的（ m+n) (m+n)初始基矩陣 (為什么 含有一個(gè) 人工變量 )． 人工變量 xa在目標(biāo)函數(shù)中的系數(shù) ca=0，從線性規(guī)劃的對(duì)偶理論可知． Ｃ Ｂ Ｂ １ ＝（ u1,u2,…,u m。v1,v2,…,v n)．而每個(gè)決策變量 xij的 系數(shù)向量 Pij=ei+em+j,所以Ｃ Ｂ Ｂ １ Pij=ui+vj. 則檢驗(yàn)數(shù) σ ij=cijCBB1Pij=cij (ui+vj) 由單純形法可知：所有基變量的檢驗(yàn)數(shù)等于０，即 cij (ui+vj)=0,i,j屬于 B 第三章 運(yùn)輸問(wèn)題 現(xiàn)在根據(jù)位勢(shì)法來(lái)計(jì)算非基變量的檢驗(yàn)數(shù) 由于基變量的檢驗(yàn)數(shù)等于０，故有 基變量 檢驗(yàn)數(shù) xa Cau1=0 Ca=0, u1=0 x23 C23(u2+v3)=0 2(u2+v3)=0 x34 C34(u3+v4)=0 5(u3+v4)=0 x21 C21(u2+v1)=0 1(u2+v1)=0 x32 C32(u3+v2)=0 4(u3+v2)=0 x13 C13(u1+v3)=0 3(u1+v3)=0 x14 C14(u1+v4)=0 10(u1+v4)=0 第三章 運(yùn)輸問(wèn)題 解得： u1=0,u2=1,u3=5，v1=2,v2=9,v3=3,v4=10 非基變量的檢驗(yàn)數(shù) σ ij=cij (ui+vj), i,j屬于Ｎ． 檢驗(yàn)數(shù)：目標(biāo)函數(shù)的系數(shù)減去對(duì)偶變量之和 第三章 運(yùn)輸問(wèn)題 3 11 1 7 4 3 2 8 5 10 10 9 10 3 9 2 5 1 0 3 2 1 4 3 2 1 A A A B B B B vj ui 設(shè)計(jì)表格 第三章 運(yùn)輸問(wèn)題 3 11 1 7 4 3 2 8 5 10 10 9 10 3 9 2 5 1 0 3 2 1 4 3 2 1 A A A B B B B vj ui 0 0 0 0 0 0 1 σ 11=c11 (u1+v1)=302=1 σ 12=c12 (u1+v2)=1109=2 …… 2 1 1 10 12 上表檢驗(yàn)數(shù)還存在負(fù)數(shù)，故沒(méi)有得到最優(yōu)解． 第三章 運(yùn)輸問(wèn)題