【正文】 量 100 150 200 450 用最小元素法確定例 32初始調(diào)運方案 150 100 100 100 100 100 100 得到初始調(diào)運方案為： x11=100， x13=100， x22=150， x23=100 最小元素法實施步驟口訣 《 運價表 》 上找最小， 《 平衡表 》 上定產(chǎn)銷； 滿足銷量劃去“列”，修改“行產(chǎn)”要記牢； （滿足產(chǎn)量劃去“行”，修改“列銷”要記牢） 劃去列 (行 )對 《 運價 》 ， 修改“行產(chǎn) (列銷 )”在 《 產(chǎn)銷 》 ； 余表再來找最小，方案很快就找到。 表上作業(yè)法和單純形法的求解思想完全一致 ，但是具體作法更加簡捷 。 定義 凡是能排成 (34) 或 (35) 形式的 變量集合 稱為一個 閉回路 ,并稱式中 變量 為該 閉回路的頂點 ；其中 互不相同 , 互不相同 。 ?按照下面的方法調(diào)整調(diào)運量： 閉回路上 ， 奇數(shù)次頂點 的 調(diào)運量 減去 ε， 偶數(shù)次頂點 （ 包括起始頂點 ） 的調(diào)運量 加上 ε；閉回路之外的變量調(diào)運量不變 。 然后構(gòu)造下面的方程組： iu jv???????????????????7565100902332222213311111cvucvucvucvu（ 37） 例 32初始調(diào)運方案位勢變量對應(yīng)表 調(diào) 銷地 運 量 產(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 位勢變量 vj v1 v2 v3 100 100 100 150 位勢變量 ui u1 u2 方程組的特點： ? 方程個數(shù)是 m+n1=2+31=4個 ， 位勢變量共有 m+n=2+3=5個 ， 通常稱 ui為第 i行的位勢 ， 稱vj為第 j列的位勢； ? 初始方案的每一個基變量 xij對應(yīng)一個方程 —— — 所在行和列對應(yīng)的位勢變量之和等于該基變量對應(yīng)的運距 （ 或運價 ） ： ui+vj=cij； ?方程組恰有一個自由變量， 可以證明 方程組中任意一個變量均可取作自由變量。2,1,0200150100250200..7565801007090m in231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxZij需求約束日產(chǎn)量約束總運輸量 分別使用最小元素法和西北角法求出初始方案。 確定初始 方案 ( 初 始 基本可行解 ) 改進(jìn)調(diào)整 （ 換基迭代 ） 否 判定是否 最 優(yōu) ？ 是 結(jié) 束 最優(yōu)方案 圖 1 運輸問題求解思路圖 二 、 初始方案的確定 作業(yè)表（產(chǎn)銷平衡表） 初始方案就是初始基本可行解。 132222111 , jijijijijiji sss xxxxxx ? sss jijijijijiji xxxxxx 123221211 , ?siii , 21 ? sjjj , 21 ? 閉回路法 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到銷地 Bj的調(diào)運