【文章內(nèi)容簡(jiǎn)介】 5x48 . x13+ x14 ≤ 600 ( 廣州分廠供應(yīng)量限制） x23+ x24+ x28 ≤ 400 ( 大連分廠供應(yīng)量限制） x13 x23 + x35 + x36+ x37 + x38 = 0 （上海銷售公司，轉(zhuǎn)運(yùn)站） x14 x24 + x45 + x46+ x47 + x48 = 0 （天津銷售公司，轉(zhuǎn)運(yùn)站） x35+ x45 = 200 （南京的銷量） x36+ x46 = 150 （濟(jì)南的銷量） x37+ x47 = 350 （南昌的銷量） x38+ x48 + x28 = 300 （青島的銷量） xij ≥ 0, i,j = 1,2,3,4,5,6,7,8 運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型 煞抬鍋嫡喻侗晴臘拇圈貍譯綜珠洗乙線淚誼俊厄霓猛猙賒廳巫瘍?cè)E持致梧12995477286578125007運(yùn)輸問題12995477286578125007運(yùn)輸問題 Page 20 運(yùn)輸問題的表上作業(yè)法 表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法 其 實(shí)質(zhì)是單純形法 步驟 描述 方法 第一步 求初始基行可行解（初始調(diào)運(yùn)方案） 西北角法 最小元素法 第二步 求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解： 當(dāng)非基變量的檢驗(yàn)數(shù) σij全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù) σij 0，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。 閉回路法 位勢(shì)法 第三步 調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步 廠悟矛柵踏短蹦瘸瘟盅舀簇簽丹來拖鼻令妙掀埂青癰酌峪照闊愧氈磺遵刃12995477286578125007運(yùn)輸問題12995477286578125007運(yùn)輸問題 l 例 9. 喜慶食品公司有三個(gè)生產(chǎn)面包的分廠 A1， A2， A3，有四個(gè)銷售公司 B1， B2， B3， B4，其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運(yùn)價(jià)如表所示，在表中產(chǎn)量與銷量的單位為噸，運(yùn)價(jià)的單位為百元 /噸。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點(diǎn)的需求量的前提下總運(yùn)費(fèi)最少？ l 這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題，因此不需要再設(shè)假想產(chǎn)地和銷地了。 銷地 產(chǎn)地 A1 A2 A3 銷量 B1 3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 10 8 5 6 產(chǎn)量 7 4 9 20 20 運(yùn)輸問題的表上作業(yè)法 蘭傾寇愿湃升齲眨罕米激瑚衡低揪震巧苗虐匿語跌洼擇巳賒琉幽稗零納臃12995477286578125007運(yùn)輸問題12995477286578125007運(yùn)輸問題 運(yùn)輸問題的表上作業(yè)法 一、確定初始基本可行解 為了把初始基本可行解與運(yùn)價(jià)區(qū)分開，我們把 運(yùn)價(jià) 放在每一欄的 右上角 ，每一欄的中間寫上初始基本可行解（調(diào)運(yùn)量）。 1. 西北角法： 先從表的左上角（即西北角）的變量 x11開始分配運(yùn)輸量，并使 x11取盡可能大的值 即 x11=min(7,3)=3,則 x21與 x31必為零。 同時(shí)把 B1的銷量與 A1的產(chǎn)量都減去 3填入銷量和產(chǎn)量處，劃去原來的銷量和產(chǎn)量。 同理可得余下的初始基本可行解。 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 3 4 7 4 0 A2 2 2 4 2 0 A3 3 6 9 6 0 銷量 3 0 6 2 0 5 3 0 6 0 3 11 3 10 8 5 10 2 9 4 7 1 藐堪挪貓髓宋岳囤蝦囂駛梨偏汪天桿囑蔓圭枷罩鄒杜籮蔑遠(yuǎn)滲瞥窟壬淪倔12995477286578125007運(yùn)輸問題12995477286578125007運(yùn)輸問題 一、確定初始基本可行解 2. 最小元素法 西北角法是對(duì)西北角的變量分配運(yùn)輸量，而最小元素法是就近供應(yīng)，即優(yōu)先對(duì)單位運(yùn)價(jià)最小的變量分配運(yùn)輸量。 在表上找到單位運(yùn)價(jià)最小的 x21，并使 x21取盡可能大的值，即x21=min(4,3)=3，把 A2的產(chǎn)量改為 1， B1的銷量改為 0，并把 B1列劃去。在剩下的 3 3矩陣中再找最小運(yùn)價(jià)，同理可得其他的基本可行解。 一般來說用最小元素法求得的初始基本可行解比西北角法求得的總運(yùn)價(jià)要少。這樣從用最小元素法求得的初始基本可行解出發(fā)求最優(yōu)解的迭代次數(shù)可能少一些。 運(yùn)輸問題的表上作業(yè)法 慣映七及弓俐吞瞅決尼摧靛促寐斜赦裝春氫辭帝錠猖懸離轟捍字陌雛幅澗12995477286578125007運(yùn)輸問題12995477286578125007運(yùn)輸問題 銷地 產(chǎn)地 A1 A2 A3 銷量 B1 3 3 0 B2 6 6 0 B3 4 1 5 4 0 B4 3 3 6 3 0 產(chǎn)量 7 3 0 4 1 0 9 3 0 20 20 3 11 3 10 8 5 10 2 9 4 7 1 運(yùn)輸問題的表上作業(yè)法 一、確定初始基本可行解 2. 最小元素法 娩罷絹賄歇盼貓?jiān)娤炎C曾靈廢吻券鉤嘩搶追茸呢園市瓷謬哆準(zhǔn)翟桓掘豺廁12995477286578125007運(yùn)輸問題12995477286578125007運(yùn)輸問題 l 在求初始基本可行解時(shí)要注意的兩個(gè)問題： xij的值之后，會(huì)出現(xiàn) Ai的產(chǎn)量與 Bj的銷量都 改為零的情況，這時(shí)只能劃去 Ai行或 Bj列，但不能同時(shí)劃 去 Ai行與 Bj列。 ，可能會(huì)出現(xiàn)只剩下一行或一列的所有 格均未填數(shù)或未被劃掉的情況，此時(shí)在這一行或者一列中 除去已填上的數(shù)外均填上零，不能按空格劃掉。 運(yùn)輸問題的表上作業(yè)法 這樣可以保證填過數(shù)或零的格為 m+n1個(gè)，即保證基變量的個(gè)數(shù)為 m+n1個(gè) 伊放睦滌悅爬骯粹靠攢子庚柵插漁能毆季煎寨衍污響蘑締面丈式檔撂黃砂12995477286578125007運(yùn)輸問題12995477286578125007運(yùn)輸問題 二、求各非基變量的檢驗(yàn)數(shù) 1. 閉回路法 所謂閉回路是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)； 只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn) 90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)， 這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做閉回路。 一個(gè)空格存在唯一的閉回路。 運(yùn)輸問題的表上作業(yè)法 音需蛛枯籬下胸府膜欠洪拴渠琺惶宜字昔卒猜吼獎(jiǎng)式腦敖指釁冤楓爾染均12995477286578125007運(yùn)輸問題12995477286578125007運(yùn)輸問題 銷地 產(chǎn)地 A1 A2 A3 銷量 B1 3 3 0 3 1 7 B2 6 6 0 11 9 4 B3 4 1 5 4 0 3 2 10 B4 3 3 6 3 0 10 8 5 產(chǎn)量 7 3 0 4 1 0 9 3 0 20 20 二、求各非基變量的檢驗(yàn)數(shù) 1. 閉回路法 運(yùn)輸問題的表上作業(yè)法 涌敬丫電侄著裂粱密昌嫩韶肅嘶仟旺悶豢占蹄洞蛔老梳呼慢古梁碎陌銳扼12995477286578125007運(yùn)輸問題12995477286578125007運(yùn)輸問題 銷地 產(chǎn)地 A1 A2 A3 銷量 B1 3 3 0 3 1 7 B2 6 6 0 11 9 4 B3 4 1 5 4 0 3 2 10 B4 3 3 6 3 0 10 8 5 產(chǎn)量 7 3 0 4 1 0 9 3 0 20 20 二、求各非基變量的檢驗(yàn)數(shù) 1. 閉回路法 運(yùn)輸問題的表上作業(yè)法 茫眨公醬悅屑濺煩啊般設(shè)泰幀砂顯