【正文】 A1 3 8 5 9 75 A2 2 6 4 8 90 A3 6 5 7 5 30 銷量 35 40 55 65 195（平衡） Page 51 of 9 B1 B2 B3 B4 產(chǎn)量 A1 3 8 5 9 75 A2 2 6 4 8 90 A3 6 5 7 5 30 銷量 35 40 55 65 195（平衡） 35 [ ] [ ] 55 [ ] [ ] 0 30 45 Page 52 of 9 B1 B2 B3 B4 產(chǎn)量 A1 3 [ ] 8 10 5 [ ] 9 65 75 A2 2 35 6 0 4 55 8 [ ] 90 A3 6 [ ] 5 30 7 [ ] 5 [ ] 30 銷量 35 40 55 65 195（平衡） Page 53 of 9 53 由于目標(biāo)要求極小 ， 因此 ， 當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則就不是最優(yōu) ， 需要進(jìn)行調(diào)整 。如此進(jìn)行下去，直至得到一個(gè)基本可行解。如此進(jìn)行下去，直至得到一個(gè)基本可行解 。 下面分別舉例予以說(shuō)明 。 這樣 ， 運(yùn)輸平衡表中所有的行與列均被劃去 ， 則得到了一個(gè)初始基本可行解 。 推論 產(chǎn)銷平衡運(yùn)輸問(wèn)題 的 m + n 1 個(gè) 變量構(gòu)成基變量的充分必要條件是它 不含閉回路 。 閉回路 Page 23 of 9 23 例如 ， x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是閉回路 。 1 2 1 1 1 2 1 , 1, , , ,n n m n nx x x x x x ?， ， ，1 1 1 2 1 2 1 2 2 2 1 2, , , , , , , , , , , ,n n m m m nP P P P P P P P Pm個(gè) n個(gè) m*n Page 20 of 9 1 1 1 1110111?故 r(A)=m+n－ 1所以運(yùn)輸問(wèn)題有 m+n－ 1個(gè)基變量 。 由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性 ， 如果直接使用線性規(guī)劃單純形法求解計(jì)算 ， 則無(wú)法利用這些有利條件 。 產(chǎn)銷平衡 Page 11 of 9 11 表 43 運(yùn)輸問(wèn)題變量表 銷地 產(chǎn)地 B1 B2 … Bn 產(chǎn)量 A1 A2 ┇ Am x11 x12 … x1n x21 x22 … x2n ┇ ┇ ┇ xm1 xm2 … xmn s1 s2 ┇ sm 銷量 d1 d2 … dn 產(chǎn)銷平衡 m n Min f = ? ? cij xij i=1 j=1 n . ? xij = si i = 1,2,…, m (45) j =1 m ? xij = dj j = 1,2,…, n (46) i =1 xij ≥ 0 (i=1,2,…, m。 1 , 2 , 3 , 4 )ijs t x x xx x x xx x x xxxx x xx x xx x xxixxj? ? ? ?? ? ? ?? ? ? ?? ? ?? ? ?? ? ?? ? ?? ? ?}產(chǎn)量 ( 3個(gè) ) }銷量（ 4個(gè)） Page 7 of 9 7 系數(shù)矩陣 1 1 1 1 0 0 0 0 0 0 0 00 0 0 0 1 1 1 1 0 0 0 000000000 11111 0 0 0 1 0 0 0 1 0 0 00 1 0 0 0 1 0 0 0 1 0 00 0 1 0 0 0 1 0 0 0 1 00 0 0 1 0 0 0 1 0 0 0 1??????????????11 12 13 14 21 12 23 24 31 32 33 34, , , , , , , , , , ,x x x x x x x x x x x x11 12 13 14 21 22 23 24 31 32 33 34, , , , , , , , , , ,P P P P P P P P P P P P Page 8 of 9 8 模型系數(shù)矩陣特征 m+n(3+4)行，分別表示各產(chǎn)地和銷地； m?n(3*4)列，分別表示各決策變量； 1，其余為 0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用。 Page 4 of 9 4 例 :某公司從三個(gè)產(chǎn)地 A A2， A3將物品運(yùn)往四個(gè)銷地 B B B B4 ，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？ B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷量 3 6 5 6 20 （產(chǎn)銷平衡） Page 5 of 9 5 解： 產(chǎn)銷平衡問(wèn)題： 總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地 Ai運(yùn)往銷地 Bj的運(yùn)輸量，得到下列運(yùn)輸量表： B1 B2 B3 B4 產(chǎn)量 A1 x11 x12 x13 x14 7 A2 X21 X22 X23 X24 4 A3 X31 X32 X33 X34 9 銷量 3 6 5 6 20 （產(chǎn)銷平衡） Page 6 of 9 6 1 1 1 2 1 3 1 4 2 1 2 22 3 2 4 3 1 3 2 3 3 3 4m in 3 1 1 3 1 0 92 8 7 4 1 0 5f x x x x x xx x x x x x? ? ? ? ? ?? ? ? ? ? ?12 13 1421 22 23 2431 32 33 3421 3112 22 3213 23 3314111124 34. . 74936560 ( 1 , 2 , 3 。 一般運(yùn)輸問(wèn)題的線性規(guī)劃模型及求解思路 Page 10 of 9 10 表 42 運(yùn)輸問(wèn)題數(shù)據(jù)表 銷地 產(chǎn)地 B1 B2 … Bn 產(chǎn)量 A1 A2 ┇ Am c11 c12 … c1n c21 c22 … c2n ┇ ┇ ┇ ┇ cm1 cm2 … cmn s1 s2 ┇ sm 銷量 d1 d2 … dn 設(shè) xij 為從產(chǎn)地 Ai 運(yùn)往銷地 Bj 的運(yùn)輸量 ， 根據(jù)這個(gè)運(yùn)輸問(wèn)題的要求 ， 可以建立運(yùn)輸變量表 （ 表 43） 。 Page 15 of 9 15 運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題 ， 在求解時(shí)依然可以采用單純形法的思路 ，如圖 41所示 。 續(xù)下頁(yè) Page 16 of 9 16 基本可行解 是否最優(yōu)解 結(jié)束 換基 是 否 圖 41 運(yùn)輸問(wèn)題的求解思路 返回 轉(zhuǎn) 28頁(yè) Page 17 of 9 17 考慮 產(chǎn)銷平衡問(wèn)題 ， 由于我們關(guān)心的量均在表 42與表 43中 ， 因此考慮把表 42與表 43合成一個(gè)表 , 如下表 44 (下頁(yè) ） 運(yùn)輸問(wèn)題求解的有關(guān)概念 (產(chǎn)銷平衡 ) Page 18 of 9 18 銷地 產(chǎn)地 B1 B2 … Bn 產(chǎn)量 A1 c11 x11 c12 x12 … c1n x1n a1 A2 c21 x21 c22 x22 … c2n x2n a2 ┇ ┇ ┇ ┇ ┇ Am cm1 xm1 cm2 xm2 … cmn xmn am 銷量 b1 b2 … bn 銷地產(chǎn)地… 產(chǎn)量……┇ ┇ ┇…銷量 …銷地產(chǎn)地… 產(chǎn)量… s… s┇ ┇ ┇… s銷量 d d … d表 44 運(yùn)輸問(wèn)題求解作業(yè)數(shù)據(jù)表 平衡 轉(zhuǎn) 31 Page 19 of 9 11 12 1 21 22 2 1 21 1 11 1 11 1 11 1 11 1 11 1 1n n m m m nx x x x x x x x xA ? 中任意 m+n階子式等于零，取第一行到 m+n－ 1行與 對(duì)應(yīng)的列（共 m+n1列）組成的 m+n－ 1階子式。 運(yùn)輸問(wèn)題的基變量 Page 22 of 9 22 定義 在表 44的決策變量格中，凡是能夠排列成下列形式的 xab ,xac ,xdc ,xde ,… ,xst ,xsb (47) 或 xab ,xcb ,xcd ,xed ,… ,xst ,xat (48) 其中 ， a,d,… ,s 各不相同； b,c,… ,t 各不相同 ， 我們稱之為變量集合的 一個(gè)閉回路 ， 并將式 （ 47） 、 式 （ 48） 中的變量稱為這個(gè) 閉回路的頂點(diǎn) 。 關(guān)于閉回路有如下的一些重要結(jié)論： Page