運輸問題ppt課件(2)(編輯修改稿)
2025-05-30 18:36 本頁面
【文章內(nèi)容簡介】 3 5 2022/5/31 18 表上作業(yè)法 單位 銷地 運價 產(chǎn)地 產(chǎn)量 行差額 3 11 3 10 7 1 9 2 8 4 7 4 10 5 9 銷量 3 6 5 6 列差額 4321 BBBB321AAA6 3 3 5 1 2022/5/31 19 表上作業(yè)法 第 2步 最優(yōu)解的判別（檢驗數(shù)的求法） 求出一組基可行解后 ， 判斷是否為最優(yōu)解 ， 仍然是用檢驗數(shù)來判斷 ， 記 xij的檢驗數(shù)為 σij由第一章知 ， 求最小值的運輸問題的最優(yōu)判別準(zhǔn)則是： 所有非基變量的檢驗數(shù)都非負(fù) ， 則運輸方案最優(yōu) 求檢驗數(shù)的方法有兩種： 閉回路法 位勢法 （ ▲ ） 2022/5/31 20 表上作業(yè)法 ? 閉回路的概念 },,{ 132222111 jsisjsijijijiji xxxxxx ?稱集合),,( 2121 互不相同；其中 ss jjjiii ??為一個閉回路 ，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表 2022/5/31 21 表上作業(yè)法 例 下表中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35, x31}共有 8個頂點，這 8個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。 B1 B2 B3 B4 B5 A1 X11 X12 A2 X23 X25 A3 X31 X35 A4 X42 X43 一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉(zhuǎn) 90度與另一頂點連接，表 3－ 3中的變量 x 32及 x33不是閉回路的頂點，只是連線的交點。 2022/5/31 22 表上作業(yè)法 閉回路 },,{ 123233434111 xxxxxxB1 B2 B3 A1 X11 X12 A2 A3 X32 X33 A4 X41 X43 例如變量組 不能構(gòu)成一條閉回路，但 A中包含有閉回路 },,{ 121131352521 xxxxxxA ?},{ 31352521 xxxx變量組 變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路； },{ 2111123233 xxxxxB ?2022/5/31 23 表上作業(yè)法 用位勢法對初始方案進行最優(yōu)性檢驗： 1）由 ?ij=Cij（ Ui+Vj）計算位勢 Ui ， Vj ，因?qū)兞慷杂??ij=0， 即Cij（ Ui+Vj） = 0，令 U1=0 2）再由 ?ij=Cij（ Ui+Vj）計算非基變量的檢驗數(shù) ?ij B1 B2 B3 B4 Ui A1 A2 A3 Vj 3 11 3 10 1 9 2 7 4 10 5 8 4 3 6 3 1 3 0 1 5 3 10 2 9 （ 1） （ 2） （ 1） （ 1） （ 10） （ 12） 當(dāng)存在非基變量的檢驗數(shù) ?kl ≥0，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進一步減小。 2022/5/31 24 表上作業(yè)法 當(dāng)存在非基變量的檢驗數(shù) ?kl 0 且 ?kl =min{?ij}時，令Xkl 進基。從表中知可選 X24進基。 第 3步 確定換入基的變量 第 4步 確定換出基的變量 以進基變量 xik為起點的閉回路中，標(biāo)有負(fù)號的最小運量作為調(diào)整量 θ， θ對應(yīng)的基變量為出基變量，并打上“ ”以示換出作為非基變量。 2022/5/31 25 表上作業(yè)法 B1 B2 B3 B4 Ui A1 A2 A3 Vj 3 11 3 10 1 9 2 7 4 10 5 8 4 3 6 3 1 3 (＋ ) (－ ) (＋ ) (－ ) ? ? ? ? 13,1m i nm i n 14,23 ???? xx調(diào)整步驟為： 在進基變量的閉回路中標(biāo)有正號的變量加上調(diào)整量θ，標(biāo)有負(fù)號的變量減去調(diào)整量 θ，其余變量不變，得到一組新的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1