02運(yùn)輸問題表上作業(yè)法(已修改)
2025-01-06 19:06 本頁(yè)面
【正文】 運(yùn)輸問題的 表上作業(yè)法 單純形法（為什麼？） 表上作業(yè)法 由于問題的特殊形式而采用的更簡(jiǎn)潔、更方便的方法 一 、 表上作業(yè)法的基本思想 先設(shè)法給出一個(gè)初始方案 ,然后根據(jù)確定的判別準(zhǔn)則對(duì)初始方案進(jìn)行檢查 、 調(diào)整 、 改進(jìn) ， 直至求出最優(yōu)方案 ， 如圖 31所示 。 表上作業(yè)法和單純形法的求解思想完全一致 ，但是具體作法更加簡(jiǎn)捷 。 確定初始 方案 ( 初 始 基本可行解 ) 改進(jìn)調(diào)整 （ 換基迭代 ） 否 判定是否 最 優(yōu) ？ 是 結(jié) 束 最優(yōu)方案 圖 1 運(yùn)輸問題求解思路圖 二 、 初始方案的確定 作業(yè)表（產(chǎn)銷平衡表） 初始方案就是初始基本可行解。 將運(yùn)輸問題的有關(guān)信息表和決策變量 —— 調(diào)運(yùn)量結(jié)合在一起構(gòu)成“ 作業(yè)表 ”（ 產(chǎn)銷平衡表 ）。 表 2是兩個(gè)產(chǎn)地、三個(gè)銷地的運(yùn)輸問題作業(yè)表。 調(diào) 銷地 運(yùn) 量 產(chǎn)地 B1 B2 B3 產(chǎn) 量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 銷 量 b1 b2 b3 ?????3121 jjii ba表 2 運(yùn)輸問題作業(yè)表（產(chǎn)銷平衡表） 其中 xij是決策變量，表示待確定的從第 i個(gè)產(chǎn)地到第 j個(gè)銷地的調(diào)運(yùn)量， cij為從第 i個(gè)產(chǎn)地到第 j個(gè)銷地的單位運(yùn)價(jià)。 確定初始方案的步驟： （ 1）選擇一個(gè) xij，令 xij= min{ai， bj}= ?????個(gè)銷地需求滿足第個(gè)銷地第個(gè)產(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)到各個(gè)銷地 ， 需求全部滿足 ，xij的取值構(gòu)成初始方案 。 否則 ， 在作業(yè)表剩余的格子中 選擇 下一個(gè)決策變量 ， 返回步驟 （ 2） 。 按照上述步驟產(chǎn)生的一組 變量必定不構(gòu)成閉回路 ， 其取值非負(fù) ， 且 總數(shù)是 m+n1個(gè) ，因此構(gòu)成 運(yùn)輸問題的基本可行解 。 對(duì) xij的選擇采用不同的規(guī)則就形成各種不同的方法 ， 比如每次總是在作業(yè)表剩余的格子中選擇運(yùn)價(jià) （ 或運(yùn)距 ） 最小者對(duì)應(yīng)的 xij，則構(gòu)成 最小元素法 ， 若每次都選擇 左上角格子 對(duì)應(yīng)的 xij就形成 西北角法 （ 也稱 左上角法 ） 。 舉例 例 32 甲 、 乙兩個(gè)煤礦供應(yīng) A、 B、 C三個(gè)城市用煤 ， 各煤礦產(chǎn)量及各城市需煤量 、 各煤礦到各城市的運(yùn)輸距離見表 34， 求使總運(yùn)輸量最少的調(diào)運(yùn)方案 。 表 34 例 32有關(guān)信息表 450 200 150 100 日銷量 （需求量） 250 75 65 80 乙 200 100 70 90 甲 日產(chǎn)量 （供應(yīng)量） C B A 運(yùn)距 城市 煤礦 例 32 的數(shù)學(xué)模型 ????????????????????????????????。3,2,1。2,1,0200150100250200..7565801007090m in231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxZij需求約束日產(chǎn)量約束總運(yùn)輸量 分別使用最小元素法和西北角法求出初始方案。 最小元素法的基本思想是“就近供應(yīng)” ； 西北角法則不考慮運(yùn)距（或運(yùn)價(jià)），每次都選剩余表格的左上角（即西北角）元素作為基變量，其它過程
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1