表上作業(yè)法在貨物運(yùn)輸組織中的應(yīng)用分析課程設(shè)計(jì)-wenkub.com
2024-08-22 20:30 本頁(yè)面
【正文】 感謝老師和同學(xué)們的幫助，相信我會(huì)把收獲運(yùn)用到以后的學(xué)習(xí)、生活中。表上作業(yè)發(fā)是物品運(yùn)輸問題中最常用的一種方法。通過分析影響制造企業(yè)運(yùn)輸環(huán)節(jié)費(fèi)用 的主客觀因素可知，短期內(nèi)產(chǎn)品特點(diǎn)、運(yùn)輸方式、產(chǎn)量、運(yùn)輸距離和市場(chǎng)需求都不會(huì)發(fā)生太大變化，因此制造業(yè)只有在單位運(yùn)費(fèi)一定的情況下充分考慮市場(chǎng)需求和產(chǎn)地產(chǎn)量從而確定合理的運(yùn)輸量才能有效減少運(yùn)輸費(fèi)用。即系數(shù)矩陣的秩 m+n+1。從 Ai 到 Bj運(yùn)輸單位物資的運(yùn)價(jià)為 cij 這些問題可以匯總到產(chǎn)銷平衡表（ ） 和單位運(yùn)價(jià)表（ ）中。顯然，調(diào)運(yùn)方案可以有很多個(gè)，但最優(yōu)方案只有一個(gè)，表上作業(yè)法可以找到這個(gè)最優(yōu)方案。 可以證明，在任何可行方案中，以空格（ i,j）為一個(gè)頂點(diǎn)，其余頂點(diǎn)全是數(shù)字格的閉回路存在而且唯一。 閉回路法 為了確定空格（ i,j）的檢驗(yàn)數(shù)，可以先找出以該空格為一個(gè)頂點(diǎn)，其余頂點(diǎn)全是數(shù)字格的閉回路。 表 檢驗(yàn)數(shù)表（ 1） B1 B2 B3 B4 供應(yīng)量 ui A1 8【 10】 9【 20】 0【 5】 3【 7】 10 u1（ 0） A2 13【 13】 0【 9】 9【 12】 6【 8】 20 u2（ .2） A3 0【 4】 2【 15】 0【 7】 3【 9】 30 u3（ 2） A4 16【 14】 0【 7】 0【 1】 0【 0】 40 u4（ .4） A5 0【 3】 0【 12】 .1【 5】 14【 19】 50 u5（ 1） 需求量 60 60 20 10 150 vi v1（ 2） v2（ 11） v3（ 5） v4（ 4） 當(dāng)表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時(shí)，表明未得到最優(yōu)解。若有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)數(shù)，一般選擇其中較小的負(fù)檢驗(yàn)數(shù)，以它對(duì)應(yīng)的空格為調(diào)入格，即以它對(duì)應(yīng)的非基變量為換入變量。有了位勢(shì)之后，即可由公式計(jì)算出各空格 的檢驗(yàn)數(shù)，如表 所示。 B1 B2 B3 B4 供應(yīng)量 A1 10 10 A2 20 20 A3 30 30 A4 10 20 10 40 A5 20 30 50 需求量 60 60 20 10 150 表 （ 1） B1 B2 B3 B4 供應(yīng)量 ui A1 10【 10】 【 20】 【 5】 【 7】 10 u1（ 0） A2 【 13】 20【 9】 【 12】 【 8】 20 u2（ .10） A3 30【 4】 【 15】 【 7】 【 9】 30 u3（ .6） A4 【 14】 10【 7】 20【 1】 10【 0】 40 u4（ .12） A5 20【 3】 30【 12】 【 5】 【 19】 50 u5（ .7） 需求量 60 60 20 10 150 vi v1（ 10） v2（ 19） v3（ 13） v4（ 12） 然后，計(jì)算位勢(shì)。 位勢(shì)法 位勢(shì)法是一種檢驗(yàn)數(shù)的簡(jiǎn)便方法， 設(shè) 是運(yùn)輸問題的 m+n個(gè)約束條件對(duì)應(yīng)的對(duì)偶變量，決策變量 對(duì)應(yīng)的列向量 ，對(duì)于一個(gè)基可行解，由單純形法得知所有基變量 （數(shù)字格）的檢驗(yàn)數(shù)等于 0 ，即,所以由 m+ 個(gè)數(shù)字格對(duì)應(yīng)的 及 即可確定所有 的值。本例題用最大差額法給出的初始解就是最優(yōu)解繼續(xù)判別。 B1 B2 B3 B4 供應(yīng)量 A1 10 A2 20 A3 30 A4 20 10 40 A5 50 需求量 60 60 20 10 150 B1 B2 B3 B4 行差額 A1 10 20 5 7 2 A2 13 9 12 8 1 A3 4 15 7 9 3 A4 14 7 1 0 1 A5 3 12 5 19 2 列差額 1 2 4 7 表 （ 13） 表 （ 14） 表 （ 15） 一直重復(fù)步驟（ 1），（ 2），可得最終結(jié)果，如表 。 在表 中， A4 為最大差額所在行，所對(duì)應(yīng)的最小元素為 B3 列，則 A4 的成品供應(yīng)給 B3， A3 里還有 30 個(gè)， B3 需求 30 個(gè)，得表 。 B4列最小元素為 0，可確定 A4 產(chǎn)品先供應(yīng) B4 的需要。因而對(duì)差額最大處，要優(yōu)先考慮，應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。 可以證明，用西北角法確定的初始方案是運(yùn)輸問題的一個(gè)初始基可行解，它也恰好包含 m+。求解步驟如下： （ 1） 先決定產(chǎn)銷平衡表左上角變量 的值。然后按行（列）標(biāo)下一格的數(shù)。 a5b1,所以 A5里面的 50 全部供應(yīng)給 B1,還缺少 10 需求量， 在從表中找出最小運(yùn)價(jià) 4， 而 B1 只需求 10，因此 A3 中止供應(yīng)10 給 BI，還剩余 20， 由此的表 。在表 中的（ A4,B4）的交叉處填上 10，得表 。 表 表 量 B1 B2 B3 B4 供應(yīng)量 A1 10 20 5 7 10 A2 13 9 12 8 20 A3 4 15 7 9 30 A4 14 7 1 0 40 A5 3 12 5 19 50 需求量 60 60 20 10 150 B1 B2 B3 B4 供應(yīng)量 A1 10 A2 20 A3 30 A4 40 A5 50 需求量 60 60 20 10 150 確定初始基本可行解 確定初始基本可行解一般的方法是既簡(jiǎn)便，有盡可能接近最優(yōu)解，下面介紹最小元素法和 Vogel 法。如以是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。 這個(gè)方法的基本思想是就近供應(yīng)，即從運(yùn)價(jià)表中最小運(yùn)價(jià)開始確定調(diào)運(yùn)量，然后次小，一直到給出初始調(diào)運(yùn)方案為止 .可歸納為： （ 1） 找出基本可行解。 從運(yùn)價(jià)最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。 課題意義 物品運(yùn)輸問題在當(dāng)今經(jīng)濟(jì)建設(shè)中是十分常見的問題，運(yùn)輸問題及運(yùn)輸成本的優(yōu)化是運(yùn)輸企業(yè)制定調(diào)運(yùn)方案時(shí)必須要考慮的內(nèi)容，如何選擇一個(gè)合理的運(yùn)輸方案使的 運(yùn)輸費(fèi)用最低是十分關(guān)鍵的。運(yùn)輸問題是特殊的線性規(guī)劃問題，它是現(xiàn)行網(wǎng)絡(luò)最優(yōu)化的一
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1