運籌學(xué)課件第3章運輸問題-第1，2節(jié)-文庫吧資料
2024-10-22 13:00本頁面
【正文】 b),(c)等所示。用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時可以轉(zhuǎn) 90176。 ? ； ? ? 在給出調(diào)運方案的計算表上，如表 313，從每一空格出發(fā)找一條閉回路。因運輸問題的目標(biāo)函數(shù)是要求實現(xiàn)最小化，故當(dāng)所有的cijCBB1Pij≥0時，為最優(yōu)解。 ? 本例用伏格爾法給出的初始解就是最優(yōu)解 。 ? 由以上可見：伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同外 ， 其余步驟相同 。直到給出初始解為止。 銷地 加工廠 B 1 B 2 B 3 B 4 行差額 A 1 A 2 A 3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 2 列差額 2 1 3 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 3 6 5 2 1 3 7 4 9 銷量 3 6 5 6 第三步：對表 312中未劃去的元素再分別計算出各行、各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。得表 311 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 6 7 4 9 銷量 3 6 5 6 同時將運價表中的 B2列數(shù)字劃去。在表 310中 B2列是最大差額所在列。 伏格爾法的步驟是： ? 第一步 ：在表 33中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行，見表 310。差額越大，說明不能按最小運費調(diào)運時，運費增加越多。 2. 伏格爾法 ? 最小元素法的缺點是：為了節(jié)省一處的費用，有時造成在其他處要多花幾倍的運費。這時就出現(xiàn)退化。故這 (m+n1)個向量是線性獨立的。 類似地給出第二個， … ，第 (m+n1)個。 (2) 這 (m+n1)個基變量對應(yīng)的系數(shù)列向量是線性獨立的。 此時把單價表上所有元素都劃去了 ， 相應(yīng)地在產(chǎn)銷平衡表上填了 (m+n1)個數(shù)字 。 表中共有 m行n列 ， 總共可劃 (n+m)條直線 。 然后在未劃去的元素中再找最小元素 ，再確定供應(yīng)關(guān)系 。 當(dāng)產(chǎn)大于銷 ， 劃去該元素所在列 。這方案的總運費為 86元。 表 35 .表 36 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 3 7 4 9 銷量 3 6 5 6 銷地 加工廠 B 1 B 2 B 3 B 4 A 1 A 2 A 3 3 1 7 11 9 4 3 2 10 10 8 5 第二步 ：在表 36未劃去的元素中再找出最小運價 2，確定 A2多余的 1噸供應(yīng) B3，并給出表 37，表 38。 并將表 33的 B1列運價劃去 。 在表 34的 (A2， B1)的交叉格處填上 3。 第一步 ：從表 33中找出最小運價為 1， 這表示先將 A2的產(chǎn)品供應(yīng)給 B1。 一直到給出初始基可行解為止 。一般希望的方法是既簡便，又盡可能接近最優(yōu)解。又因 0≤x ij≤min(a j， bj) 故運輸問題必存在最優(yōu)解。 產(chǎn)銷平衡的運輸問題總是存在可行解 。問該公司應(yīng)如何調(diào)運產(chǎn)品，在滿足各銷點的需要量的前提下，使總運費為最少 。各銷售點每日銷量為： B1為 3噸，B2為 6噸， B3為 5噸， B4為 6噸。每日的產(chǎn)量分別是： A1為 7噸， A2為 4噸， A3為 9噸。 例 1 某公司經(jīng)銷甲產(chǎn)品。在表上用閉回路法調(diào)整 。 如已是最優(yōu)解 ， 則停止計算 ， 否則轉(zhuǎn)到下一步 。 。 即在 (m n)產(chǎn)銷平衡表上 用西北角法或最小元素法 ， Vogel法給出 m+n1個數(shù)字 ，稱為數(shù)字格 。 但具體計算和術(shù)語有所不同 。 行行nmvvvuuuxxxxxxxxxnmmnmmnn????????????????????????????????????????1111111111111111112121212222111211?????????????????該系數(shù)矩陣中對應(yīng)于變量 xij的系數(shù)向量 Pij， 其分量中除第 i個和第 m+j個為 1以外，其余的都為零。它包含 m n個變量， (m+n)個約束方程。有時可把這兩表合二為一。 第 1節(jié)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1