【正文】 44） 運(yùn)輸問題模型及有關(guān)概念 于是得到 一般運(yùn)輸問題的模型 ： 在模型 （ 41） —（ 44） 中 ， 式 （ 42） 為 m 個(gè)產(chǎn)地的產(chǎn)量約束；式 （ 43） 為 n 個(gè)銷地的銷量約束 。j=1,2,…, n) 運(yùn)輸問題模型及有關(guān)概念 對(duì)于產(chǎn)銷平衡問題，可得到下列運(yùn)輸問題的模型： 14 在產(chǎn)銷平衡問題中 ， 式 （ 42） 、 （ 43） 分別變?yōu)?（ 45） 、 （ 46） ， 約束條件成為等式 。 當(dāng)銷量大于產(chǎn)量時(shí)可加入一個(gè)虛設(shè)的產(chǎn)地去生產(chǎn)不足的物資 ， 這相當(dāng)于在式 （ 42） 每一式中加上 1 個(gè)松弛變量 ， 共 m 個(gè)；當(dāng)產(chǎn)量大于銷量時(shí)可加入一個(gè)虛設(shè)的銷地去消化多余的物資 ， 這相當(dāng)于在式 （ 43） 每一式中加上 1 個(gè)松弛變量 ， 共 n 個(gè) 。 由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性 ， 如果直接使用線性規(guī)劃單純形法求解計(jì)算 ， 則無法利用這些有利條件 。 下面主要討論 基本可行解 、 檢驗(yàn)數(shù) 以及 基的轉(zhuǎn)換 等問題 。 運(yùn)輸問題的 m + n 1 個(gè)變量構(gòu)成基變量的充分必要條件是不含閉回路。 為了說明這個(gè)特征 ， 我們不加證明的給出一些概念和結(jié)論 。 運(yùn)輸問題模型及有關(guān)概念 22 例如 ， x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是閉回路 。 運(yùn)輸問題模型及有關(guān)概念 24 關(guān)于閉回路有如下的一些重要結(jié)論： (1) 設(shè) xab , xac , xdc , xde ,… , xst , xsb 是一個(gè)閉回路 ， 那么該閉回路中變量所對(duì)應(yīng)的系數(shù)列向量 pab , pac , pdc , pde ,… , pst , psb 線性相關(guān) ； (2) 若變量組 xab , xcd , xef ,… , xst 中包含一個(gè)部分組構(gòu)成閉回路 ， 那么該變量組所對(duì)應(yīng)的系數(shù)列向量 pab , pcd, pef ,… , pst 線性相關(guān) 。 運(yùn)輸問題模型及有關(guān)概念 定理 變量組 xab , xcd , xef ,… , xst 所對(duì)應(yīng)的系數(shù)列向量 pab , pcd , pef ,… , pst 線性無關(guān)的充分必要條件是這個(gè)變量組中 不包含閉回路 。 這個(gè)推論給出了運(yùn)輸問題基本解的重要性質(zhì) ， 也為尋求基本可行解提供了依據(jù) 。 表上作業(yè)法求解運(yùn)輸問題的思想和單純形法完全類似： 確定一個(gè)初始基本可行解 —— 根據(jù)最優(yōu)性判別準(zhǔn)則來檢查這個(gè)基本可行解是不是最優(yōu)的 ？ 如果是 ， 則計(jì)算結(jié)束； 如果不是 ， 則進(jìn)行換基 。 27 —表上作業(yè)法 一 、 初始基本可行解的確定 根據(jù)上面的討論 ， 要求得運(yùn)輸問題的初始基本可行解 ， 必須保證找到 m + n – 1 個(gè)不構(gòu)成閉回路的基變量 。 這樣 ， 運(yùn)輸平衡表中所有的行與列均被劃去 ， 則得到了一個(gè)初始基本可行解 。 31 上述計(jì)算過程可用流程圖描述如下（圖 42） 取未劃去的單元格 xij ,令 xij = min { ai , bj } ai’ = ai xij bj’ = bj xij ai’ = 0? 劃去第 i行 劃去第 j列 是 否 bj’ = 0 否 所有行列是 否均被劃去 是 找到初始基 本可行解 圖 42 求運(yùn)輸問題的初始基本可行解過程 注：為了方便，這里總記剩余的產(chǎn)量和銷量為 ai, bj 32 —表上作業(yè)法 按照上述方法所產(chǎn)生的一組變量的 取值將滿足下面條件： (1)所得的變量均為非負(fù) ， 且變量總 數(shù)恰好為 m + n – 1 個(gè)； (2)所有的約束條件均得到滿足； (3)所得的變量不構(gòu)成閉回路 。 在上面的方法中 ， xij 的選取方法并沒有給予限制 ， 若采取不同的規(guī)則來選取 xij ， 則得到不同的方法 ， 較常用的方法有西北角法和最小元素法 。 34 —表上作業(yè)法 初始基本可行解的確定 （ 1）西北角法 ：從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。 35 （ 2） 最小元素法 ：從運(yùn)價(jià)最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。 —表上作業(yè)法 36 注 :應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列，只有 最后一個(gè)元例外 （同時(shí)劃去一行和一列）。 —表上作業(yè)法 —表上作業(yè)法 例 4 .2 ：某食品公司下屬的 A 1 、 A 2 、 A 3 ， 3 個(gè)廠生產(chǎn)方便食品，要運(yùn)輸?shù)?B 1 、 B 2 、 B 3 、 B 4 ， 4個(gè)銷售點(diǎn)，數(shù)據(jù)如下： B 1 B 2 B 3 B 4 產(chǎn)量 a i A 1 3 11 3 10 7 A 2 1 9 2 8 4 A 3 7 4 10 5 9 銷量 b j 3 6 5 6 20 （產(chǎn)銷平衡） 求最優(yōu)運(yùn)輸方案。 檢查的方法與單純形方法中的原理相同 ， 即計(jì)算檢驗(yàn)數(shù) 。 下面介紹兩種求檢驗(yàn)數(shù)的方法 : 閉回路法 和 位勢(shì)法 二、基本可行解的最優(yōu)性檢驗(yàn) —表上作業(yè)法 41 閉回路法 為了方便 ， 我們以表 1給出的初始基本可行解方案為例 ， 考察初始方案的任意一個(gè)非基變量 ， 比如 x24。 如果現(xiàn)在改變初始方案 ， 把 A2 的產(chǎn)品運(yùn)送 1 個(gè)單位給 B4 ， 那么為了保持產(chǎn)銷平衡 ，就必須使 x14 或 x34 減少 1 個(gè)單位；而如果 x14 減少 1 個(gè)單位 ， 第 1 行的運(yùn)輸量就必須增加 1 個(gè)單位 ， 例如 x13 增加 1 個(gè)單位 ， 那么為了保持產(chǎn)銷平衡 ， 就必須使 x23 減少 1 個(gè)單位 。 容易計(jì)算出上述調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為 8 – 10 + 3 – 2 ＝ 1 ， 即總的運(yùn)費(fèi)減少 1 個(gè)單位 ， 這就說明原始方案不是最優(yōu)方案 ， 可以進(jìn)行調(diào)整以得到更好的方案 。因此， 對(duì)每一個(gè)非基變量可以找到而且只能找到唯一的一個(gè)閉回路。 —表上作業(yè)法 44 表 410 以非基變量 x22 為起始頂點(diǎn)的閉回路 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 3 [ ] 11 [ ] 3 4 10 3 7 1 3 9 [ ] 2 1 8 [ ] 4 7 [ ] 4 6 10 [ ] 5 3 9 銷量 3 6 5 6 20(產(chǎn)銷平衡 ) A1 A2 A3 45 可以計(jì)算出以非基變量 x22 為起始頂點(diǎn)的閉回路調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為 9 – 2 + 3 – 10 + 5 – 4 ＝ 1 即總的運(yùn)費(fèi)增加 1 個(gè)單位 ， 這就說明這個(gè)調(diào)整不能改善目標(biāo)值 。 —表上作業(yè)法 46 這樣 ， 利用單位產(chǎn)品變化 （ 運(yùn)輸?shù)膯挝毁M(fèi)用 ） 可計(jì)算出它們對(duì)目標(biāo)函數(shù)的綜合影響 ， 其作用與線性規(guī)劃單純形方法中的檢驗(yàn)數(shù)完全相同 。上面計(jì)算的兩個(gè)非基變量的檢驗(yàn)數(shù)為 ?24 = 1， ?22 = 1。 —表上作業(yè)法 47 如果規(guī)定作為起始頂點(diǎn)的非基變量為第 1 個(gè)頂點(diǎn) ， 閉回路的其他頂點(diǎn)依次為第 2 個(gè)頂點(diǎn) 、 第 3 個(gè)頂點(diǎn) …… 那么就有 ?ij = (閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和 ) (閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和 ) 其中 ij 為非基變量的下角指標(biāo) 。 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 3 [1] 11 [2] 3 4 10 3 7 A2 1 3 9 [1] 2 1 8 [1] 4 A3 7 [10] 4 6 10 [12] 5 3 9 銷量 3 6 5 6 20(產(chǎn)銷平衡 ) 表 411 初始基本可行解及檢驗(yàn)數(shù) 49 顯然 ， 當(dāng)所有非基變量的檢驗(yàn)數(shù)