第四章--運(yùn)輸問題(共12頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第四章 運(yùn)輸問題主要內(nèi)容：1、運(yùn)輸問題及其數(shù)學(xué)模型； 2、表上作業(yè)法； 3、運(yùn)輸問題的進(jìn)一步討論。重點(diǎn)與難點(diǎn)：表上作業(yè)法的原理、求解步驟，產(chǎn)銷不平衡運(yùn)輸問題的求解方法。要 求：理解運(yùn)輸問題的基本概念及表上作業(yè)法的原理，掌握表上作業(yè)法確定初始可行解、最優(yōu)解的判別與改進(jìn)的方法。§1 運(yùn)輸問題及其數(shù)學(xué)模型一、運(yùn)輸問題引例，設(shè)有m個(gè)生產(chǎn)地，可供應(yīng)（產(chǎn)量）分別為;有n個(gè)銷地其需要量分別為。已知從到運(yùn)輸單位物資的運(yùn)價(jià)（單價(jià)）為，試問如何調(diào)運(yùn)物資才能使總費(fèi)用最??？設(shè)用表示從到的運(yùn)量，可將這些數(shù)據(jù)匯總于下表：產(chǎn)銷平衡表 銷地產(chǎn)地 產(chǎn)量銷量 單價(jià)運(yùn)價(jià)表銷地產(chǎn)地 注：有時(shí)將兩表

2、合二為一。（1）若各產(chǎn)地的總產(chǎn)量等于各銷地的總銷量，即，則稱之為產(chǎn)銷平衡的運(yùn)輸問題（或平衡運(yùn)輸問題）；（2）若所有產(chǎn)地的總產(chǎn)量不等于所有銷地的總銷量，即，則稱之為產(chǎn)銷不平衡的運(yùn)輸問題（或不平衡的運(yùn)輸問題）；（3）若在運(yùn)輸途中，還存在中間轉(zhuǎn)運(yùn)點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)即是產(chǎn)地，又是銷地），則稱之為有轉(zhuǎn)運(yùn)的運(yùn)輸問題（或擴(kuò)大的運(yùn)輸問題）。二、平衡運(yùn)輸問題的數(shù)學(xué)模型在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小，可建立以下數(shù)學(xué)模型：該運(yùn)輸問題也屬于線性規(guī)劃問題，包括：（1）個(gè)決策變量；（2）m+n個(gè)約束條件；由于有，所以模型只有m+n1個(gè)獨(dú)立約束條件，基變量中含有m+n1個(gè)變量；（3）系數(shù)矩陣的秩（4）系數(shù)矩陣為階矩陣，該系數(shù)

3、矩陣中對(duì)應(yīng)于變量的系數(shù)向量，其分量中除第i個(gè)和第m+j個(gè)為1以外，其余的都為零。§2 表上作業(yè)法求解步驟：（1）找出初始可行解，即在產(chǎn)銷平衡表上給出個(gè)數(shù)字格；（2）求各非基變量的檢驗(yàn)數(shù)，即在表上計(jì)算空格的檢驗(yàn)數(shù)。判別是否達(dá)到最優(yōu)解，如已是最優(yōu)解，則停止計(jì)算；（3）確定換入變量和換出變量，找出新的基可行解，在表上用閉回路法調(diào)整；（4）重復(fù)（2）、（3）直至得到最優(yōu)解為止。例1 某公司有三個(gè)工廠生產(chǎn)一種產(chǎn)品，每日的產(chǎn)量分別為7T、4T、9T。該公司把這些產(chǎn)品運(yùn)往四個(gè)銷點(diǎn)，各銷點(diǎn)的日銷量為-3T、-6T、-5T、-6T。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)見下表。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，

4、在滿足各銷點(diǎn)需要量的前提下，使總運(yùn)費(fèi)最少？單位運(yùn)價(jià)表 單位：元/T銷地加工廠311310192874105（二） 確定初始基可行解（初始調(diào)運(yùn)方案）（一）最小元素法思路：就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小，直到給出初始基可行解為止。以例1為例進(jìn)行討論：第一步：從單位運(yùn)價(jià)表中找出最小運(yùn)價(jià)為1，表示先將的產(chǎn)品供應(yīng)給。因，除滿足全部需要外，還多余1T產(chǎn)品。在與的交叉格處填上3，并將列的運(yùn)價(jià)劃去。第二步：在未劃去的元素中再找出最小運(yùn)價(jià)2，確定多余的1噸供應(yīng)，并將行的運(yùn)價(jià)劃去。第三步：在未劃去的元素中劃出最小運(yùn)價(jià)3，直到單位運(yùn)價(jià)表上的所有元素都劃去為止，最后在產(chǎn)銷平衡表上得到一

5、個(gè)調(diào)運(yùn)方案，空格為非基變量。單位運(yùn)價(jià)表 單位：T銷地加工廠311310192874105產(chǎn)銷平衡表 單位：T銷地加工廠產(chǎn)量437314639銷量3656注意：（1）在用最小元素法確定初始方案時(shí)，在產(chǎn)銷平衡表上每填一個(gè)數(shù)，在單位運(yùn)價(jià)表上劃去一行或一列（當(dāng)產(chǎn)大于銷時(shí)；劃去元素所在列；當(dāng)產(chǎn)小于銷時(shí)，劃去元素所在行）。運(yùn)價(jià)表中有行和列，需要?jiǎng)?條線，填最后一個(gè)數(shù)劃去一行和一列，這樣共填上個(gè)數(shù)。（2）當(dāng)在產(chǎn)銷平衡表上填上某個(gè)數(shù)時(shí)，行和列都平衡，需在單位運(yùn)價(jià)表上劃去一行和一列（這就出現(xiàn)了退化問題），為保持個(gè)基變量，需在行或列的任一空格處填上零，表示該基變量取值為零。（二）伏格爾法思路：一產(chǎn)地的產(chǎn)品，假如不

6、能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這樣就要有一差額。差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因而對(duì)差額最大處，就采用最小運(yùn)費(fèi)調(diào)運(yùn)。第一步：計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額銷地加工廠行差額311310019281741051列差額2513第二步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素，在上表中，列是最大差額所在列，列中最小元素為4，可確定的產(chǎn)品先供應(yīng)的需要，同時(shí)將運(yùn)價(jià)表中的列數(shù)字劃去。單位運(yùn)價(jià)表銷地產(chǎn)地311310192874105產(chǎn)銷平衡表銷地產(chǎn)地產(chǎn)量7469銷量3656第三步：對(duì)表中未劃去的元素再分別計(jì)算出各行、各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，重復(fù)第一

7、、二步，直到給出初始解為止。最后結(jié)果見下表。產(chǎn)銷平衡表銷地產(chǎn)地產(chǎn)量527314639銷量3656注意：（1）伏格爾法與最小元素法除確定供求關(guān)系的原則不同外，其余相同；（2）伏格爾法給出的初始解更接近最優(yōu)解。二、最優(yōu)解的判別判別方法：計(jì)算空格檢驗(yàn)數(shù)，當(dāng)時(shí)，為最優(yōu)解。下面介紹兩種求空格檢驗(yàn)數(shù)的方法：（一）閉回路法在給出調(diào)運(yùn)方案的表上，從每一空格出發(fā)找一條閉回路。它是以某一空格為起點(diǎn)。用水平或垂直線向前劃，每碰到一數(shù)字格轉(zhuǎn)90度后，繼續(xù)前進(jìn)，直到回到開始空格為止。對(duì)用最小元素法確定的方案：銷地加工廠產(chǎn)量4373114639銷量3656不是最優(yōu)解，需要調(diào)整。（二）位勢(shì)法（對(duì)偶變量法）設(shè)是對(duì)應(yīng)運(yùn)輸問題的

8、對(duì)偶變量，其中-行位勢(shì)，-列位勢(shì)。檢驗(yàn)數(shù)所有基變量的檢驗(yàn)數(shù) 即由此求出，再計(jì)算。第一步：在按最小元素法給出的初始解的數(shù)字處填入單位運(yùn)價(jià)銷地產(chǎn)地310012145529310第二步：在表上增加一行一列，填入。對(duì)基變量有 第三步：計(jì)算空格的可直接在表上進(jìn)行銷地產(chǎn)地3113100121928111741055101229310三、調(diào)整-閉回路法當(dāng)<0時(shí)，表明未得到最優(yōu)解，選取<0中最小的所對(duì)應(yīng)的變量為進(jìn)基變量，以此格為出發(fā)點(diǎn)，作一閉回路，確定調(diào)整量（其原理與單純形法中按規(guī)則確定換出變量相同），然后，按閉回路上的正、負(fù)號(hào)，加入或減去此值，得到新的調(diào)運(yùn)方案。檢驗(yàn)表：銷地產(chǎn)地12111012新

9、調(diào)運(yùn)方案：銷地產(chǎn)地產(chǎn)量72+_7522143-1+92963銷量3656對(duì)上表求空格的檢驗(yàn)數(shù)，見上表。因?yàn)樗?gt;0，所以此解為最優(yōu)解，總費(fèi)用的最小值z(mì)=85注意：（1）若對(duì)某方案所有，且有某一個(gè)=0，則此問題有無窮多最優(yōu)解，（兩個(gè)最優(yōu)解的組合，也一定是最優(yōu)解）。（2）在用閉回路法調(diào)整時(shí)，若有兩個(gè)具有“-”標(biāo)記的數(shù)同時(shí)為最小值，把其中一個(gè)作為調(diào)出變量，另一個(gè)仍為基變量，其值為0；若有某個(gè)有“-”標(biāo)記的數(shù)為0，調(diào)整量為零，把此格作為空格，原空格處填入零。如：13調(diào)整后變?yōu)?41114調(diào)整后變?yōu)?400§3 產(chǎn)銷不平衡問題1、若產(chǎn)大于銷，需增加一個(gè)假想的銷地，各產(chǎn)地到此的運(yùn)價(jià)都為零，該地的銷量為。2、若產(chǎn)小于銷，需增加一個(gè)假想的產(chǎn)地，由此到各銷地的運(yùn)價(jià)都為零，該地的產(chǎn)量為。例2 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)同一種化肥，其產(chǎn)、銷量和運(yùn)價(jià)如下表，試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。運(yùn)價(jià)單位：萬元/萬噸需求地區(qū)化肥廠IIIIIIIV產(chǎn)量（萬噸）ABC1614191313202219231715506050最低需求（萬噸）最高需求（萬噸）3050707003010不限解： 產(chǎn)銷平衡表和單位運(yùn)價(jià)表：銷地產(chǎn)地IIIIIIIIVIV產(chǎn)量ABCD161419M1614190131320M22192301715MM1715M050605050銷量3020703