02運(yùn)輸問題表上作業(yè)法(完整版)
【正文】 200 450 位勢變量 vj v1 v2 v3 100 100 100 150 位勢變量 ui u1 u2 方程組的特點(diǎn)： ? 方程個數(shù)是 m+n1=2+31=4個 ， 位勢變量共有 m+n=2+3=5個 ， 通常稱 ui為第 i行的位勢 ， 稱vj為第 j列的位勢； ? 初始方案的每一個基變量 xij對應(yīng)一個方程 —— — 所在行和列對應(yīng)的位勢變量之和等于該基變量對應(yīng)的運(yùn)距 （ 或運(yùn)價 ） ： ui+vj=cij； ?方程組恰有一個自由變量， 可以證明 方程組中任意一個變量均可取作自由變量。 對于產(chǎn)地和銷地也作類似的處理 。 ?按照下面的方法調(diào)整調(diào)運(yùn)量： 閉回路上 ， 奇數(shù)次頂點(diǎn) 的 調(diào)運(yùn)量 減去 ε， 偶數(shù)次頂點(diǎn) （ 包括起始頂點(diǎn) ） 的調(diào)運(yùn)量 加上 ε；閉回路之外的變量調(diào)運(yùn)量不變 。 可以證明 ， 如果對閉回路的方向不加區(qū)別 ， 對于每一個非基變量而言 ， 以其為起點(diǎn)的閉回路 存在且唯一 。 定義 凡是能排成 (34) 或 (35) 形式的 變量集合 稱為一個 閉回路 ,并稱式中 變量 為該 閉回路的頂點(diǎn) ；其中 互不相同 , 互不相同 。 對 xij的選擇采用不同的規(guī)則就形成各種不同的方法 ， 比如每次總是在作業(yè)表剩余的格子中選擇運(yùn)價 （ 或運(yùn)距 ） 最小者對應(yīng)的 xij，則構(gòu)成 最小元素法 ， 若每次都選擇 左上角格子 對應(yīng)的 xij就形成 西北角法 （ 也稱 左上角法 ） 。 表上作業(yè)法和單純形法的求解思想完全一致 ，但是具體作法更加簡捷 。 確定初始方案的步驟： （ 1）選擇一個 xij，令 xij= min{ai， bj}= ?????個銷地需求滿足第個銷地第個產(chǎn)地的產(chǎn)量全部運(yùn)到第jjbjiia將具體數(shù)值填入 xij在表中的位置； （ 2） 調(diào)整產(chǎn)銷剩余數(shù)量： 從 ai和 bj中分別減去xij的值 ， 若 aixij=0， 則劃去產(chǎn)地 Ai所在的行 ， 即該產(chǎn)地產(chǎn)量已全部運(yùn)出無剩余 ， 而銷地 Bj尚有需求缺口 bjai；若 bjxij =0， 則劃去銷地 Bj所在的列 ， 說明該銷地需求已得到滿足 ， 而產(chǎn)地 Ai尚有存余量 aibj； （ 3） 當(dāng)作業(yè)表中 所有的行或列均被劃去 ， 說明所有的產(chǎn)量均已運(yùn)到各個銷地 ， 需求全部滿足 ，xij的取值構(gòu)成初始方案 。 最小元素法的基本思想是“就近供應(yīng)” ； 西北角法則不考慮運(yùn)距（或運(yùn)價），每次都選剩余表格的左上角（即西北角）元素作為基變量，其它過程與最小元素法相同 ； 調(diào) 銷地 運(yùn) 量 產(chǎn)地 B1 B2 B3 產(chǎn) 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 銷 量 100 150 200 450 用最小元素法確定例 32初始調(diào)運(yùn)方案 150 100 100 100 100 100 100 得到初始調(diào)運(yùn)方案為： x11=100， x13=100， x22=150， x23=100 最小元素法實(shí)施步驟口訣 《 運(yùn)價表 》 上找最小， 《 平衡表 》 上定產(chǎn)銷； 滿足銷量劃去“列”，修改“行產(chǎn)”要記牢； （滿足產(chǎn)量劃去“行”，修改“列銷”要記牢） 劃去列 (行 )對 《 運(yùn)價 》 ， 修改“行產(chǎn) (列銷 )”在 《 產(chǎn)銷 》 ； 余表再來找最小，方案很快就找到。 定理 2 若變量組 中有一個部分組構(gòu)成閉回路 ， 則該變量組對應(yīng)的系數(shù)列向量線性相關(guān) 。 給定自由變量一個值 ， 解方程組式 （ 37） ，即可求得位勢變量的一組值 ， 根據(jù)式 （ 36） 結(jié)合方程組 （ 37） ， 推出計算非基變量 xij檢驗(yàn)數(shù)的公式 σij=cij（ ui+vj） （ 38） 在式 （ 37） 中 ， 令 u1=0， 則可解得 v1=90，v3=100， u2=25， v2=90， 于是 σ
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1