[工學(xué)]第7章運輸問題-閱讀頁
2024-10-31 18:49本頁面
【正文】 M 2 6 20 B1 3 1 7 2 4 1 1 0 1 4 2 20 B2 11 9 4 8 5 8 M 1 0 2 1 20 B3 3 2 10 4 2 2 2 4 2 0 3 20 B4 10 8 5 6 7 4 6 2 1 3 0 20 銷量 20 20 20 20 20 20 20 23 26 25 26 240 管 理 運 籌 學(xué) 20 167。 ? 運輸問題都存在最優(yōu)解。對于有 m個產(chǎn)地 n個銷地的產(chǎn)銷平衡問題，則有 m個關(guān)于產(chǎn)量的約束方程和 n個關(guān)于銷量的約束方程。在 m n的產(chǎn)銷平衡表上給出 m+n1個數(shù)字格，其相對應(yīng)的調(diào)運量的值即為基變量的值。 – ，找出新的基本可行解。 – 3直到得到最優(yōu)解。問該公司應(yīng)如何調(diào)運產(chǎn)品在滿足各銷點的需求量的前提下總運費最少？ ? 這是一個產(chǎn)銷平衡的運輸問題，因此不需要再設(shè)假想產(chǎn)地和銷地了。 ：先從表的左上角（即西北角）的變量 x11開始分配運輸量，并使 x11取盡可能大的值，即 x11=min(7,3)=3,則 x21與 x31必為零。同理可得余下的初始基 本可行解。在表上找到單位運價最小的 x21，并使 x21取盡可能大的值，即 x21=min(4,3)=3,把 A1的產(chǎn)量改為 1， B1的銷量改為 0，并把 B1列劃去。 一般來說用最小元素法求得的初始基本可行解比西北角法求得的總運價要少。 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 3 7 3 0 A2 3 1 4 1 0 A3 6 3 9 3 0 銷量 3 0 6 0 5 4 0 6 3 0 20 20 3 11 3 10 8 5 10 2 9 4 7 1 管 理 運 籌 學(xué) 24 ? 在求初始基本可行解時要注意的兩個問題： – xij的值之后，會出現(xiàn) Ai的產(chǎn)量與 Bj的銷量都改為零的情況，這時只能劃去 Ai行或 Bj列，但不能同時劃去 Ai行與 Bj列。這樣可以保證填過數(shù)或零的格為 m+n1個，即保證基變量的個數(shù)為 m+n1個。一個空格存在唯一的閉回路。最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。 管 理 運 籌 學(xué) 26 ? 從非基變量 x11出發(fā)，找到一個閉回路如上表所示?，F(xiàn)在把 x11的調(diào)運量從零增加為 1噸，運費也增加了 3元，為了使 A1產(chǎn)量平衡， x13必須減少 1噸，運費減少 3元。同理把 x21減少 1噸，運費減少 1元。說明如果讓 x11為基變量，運費就會增加，其增加值 1作為 x11的 檢驗數(shù) ，為了區(qū)別調(diào)整量，我們把 1加圈。 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 1 4 7 A2 3 1 4 A3 9 銷量 3 6 5 6 20 20 3 11 3 10 8 5 10 2 9 4 7 1 管 理 運 籌 學(xué) 27 所謂位勢法，我們對運輸表上的每一行賦予一個數(shù)值 ui，對每一列賦 予一個數(shù)值 vj，它們的數(shù)值是由基變量 xij的檢驗數(shù) 所決 定的，則非基變量 xij的檢驗數(shù)就可以用公式 求出。同理可以求得 v4=10， u2=1等等見上表。 銷地 產(chǎn)地 B1 B2 B3 B4 ui A1 1 2 4 3 0 A2 3 1 1 1 1 A3 10 6 12 3 5 vj 2 9 3 10 20 20 3 11 3 10 8 5 10 2 9 4 7 1 0???? jiijij vuc?jiijij vuc ????jiijij vuc ???? 1203111111 ??????? vuc?管 理 運 籌 學(xué) 28 三、改進運輸方案的辦法 ——閉回路調(diào)整法 當(dāng)表中的某個檢驗數(shù)小于零時，方案不為最優(yōu)，需要調(diào)整。本例中取 ， 表明增加一個單位的 x24運輸量，可使得總運費減少 1。把所有閉回 路上為偶數(shù)頂點的運輸量都減少這個值，奇數(shù)頂點的運輸量都增加這個值 (見下 表 )。如在本題中給出的最優(yōu)運輸方案中 x11的檢驗數(shù)為0，可知此運輸問題有多個最優(yōu)解。 銷地 產(chǎn)地 B1 B2 B3 B4 A1 (+2) 5 2(2) A2 3(2) 1(+2) A3 6 3 銷地 產(chǎn)地 B1 B2 B3 B4 A1 2 5 A2 1 3 A3 6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1