運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用(第五版)-(第三章運(yùn)輸問題)復(fù)習(xí)過程

1、運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用(第五版)-(第三章運(yùn)輸問題)1 1 運(yùn)輸問題的典例及數(shù)學(xué)模型運(yùn)輸問題的典例及數(shù)學(xué)模型一、一、 引例引例某公司從三個(gè)產(chǎn)地某公司從三個(gè)產(chǎn)地 ， ， 將產(chǎn)品運(yùn)往四個(gè)銷地將產(chǎn)品運(yùn)往四個(gè)銷地 ， ， ，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最?。康氐倪\(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？ 1A2A1B2B3B3A4B 銷地 運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059 銷量（噸）3656解：解：從表中可知：總產(chǎn)量從表中可知：總產(chǎn)量 = = 總銷量。這是一

2、個(gè)產(chǎn)銷平衡的總銷量。這是一個(gè)產(chǎn)銷平衡的 運(yùn)輸問題。假設(shè)運(yùn)輸問題。假設(shè) 表示從產(chǎn)地表示從產(chǎn)地 運(yùn)往銷地運(yùn)往銷地 的產(chǎn)的產(chǎn) 品數(shù)量，品數(shù)量， 建立如下表格：建立如下表格：ijxij. 4 , 3 , 2 , 1; 3 , 2 , 1ji于是可建立如下的數(shù)學(xué)模型于是可建立如下的數(shù)學(xué)模型： 銷地 運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059 銷量（噸）365611x12x13x21x22x23x31x32x33x14x24x34x目標(biāo)函數(shù)目標(biāo)函數(shù)：34333231242322211413121151047829103113xxxxxxxxxxxxMinZ約束條

3、件：約束條件：947343332312423222114131211xxxxxxxxxxxx產(chǎn)量約束產(chǎn)量約束銷量約束銷量約束20204 , 3 , 2 , 1; 3 , 2 , 1, 06563342414332313322212312111jixxxxxxxxxxxxxij設(shè)有設(shè)有m個(gè)產(chǎn)地，分別為個(gè)產(chǎn)地，分別為 ; n 個(gè)銷地，分別是個(gè)銷地，分別是 ；從產(chǎn)地從產(chǎn)地 運(yùn)往銷地運(yùn)往銷地 的單位運(yùn)價(jià)是的單位運(yùn)價(jià)是 ，運(yùn)量，運(yùn)量 是產(chǎn)地是產(chǎn)地 的產(chǎn)量；的產(chǎn)量； 是銷地是銷地 的銷量。的銷量。 mAAA,.,21nBBB,.,21iAjBijcijxisiAjdjB二、二、一般運(yùn)輸問題數(shù)學(xué)模型一般運(yùn)輸

4、問題數(shù)學(xué)模型則該運(yùn)輸問題的模型如下：則該運(yùn)輸問題的模型如下：njmixmisxnjdxtsxcfMinijinjijjmiijminjijij,.,1,.1,0,.1,.,1.1111 說明說明：當(dāng)：當(dāng) 時(shí)，稱其為產(chǎn)銷平衡的運(yùn)輸問題，時(shí)，稱其為產(chǎn)銷平衡的運(yùn)輸問題，否則產(chǎn)銷不平衡。否則產(chǎn)銷不平衡。njjmiids11說明說明：從上述模型可以看出：從上述模型可以看出：（1）這是一個(gè)線性規(guī)劃的模型；）這是一個(gè)線性規(guī)劃的模型；（2）變量有）變量有mn個(gè)；個(gè)；（3）約束條件有）約束條件有 m+n 個(gè)；個(gè)；（4）系數(shù)矩陣非常稀疏；系數(shù)矩陣的秩一般為（系數(shù)矩陣非常稀疏；系數(shù)矩陣的秩一般為（m+n-1),m+

5、n-1), 而非而非m+n 。若直接用單純形法求解，顯然單純形表比較龐大，于是在若直接用單純形法求解，顯然單純形表比較龐大，于是在單純形法的基礎(chǔ)上創(chuàng)建了表上作業(yè)法求解運(yùn)輸問題這一特單純形法的基礎(chǔ)上創(chuàng)建了表上作業(yè)法求解運(yùn)輸問題這一特殊的線性規(guī)劃問題殊的線性規(guī)劃問題 從第一節(jié)的運(yùn)輸問題的數(shù)學(xué)模型可知，運(yùn)輸問題實(shí)際上從第一節(jié)的運(yùn)輸問題的數(shù)學(xué)模型可知，運(yùn)輸問題實(shí)際上也屬于線性規(guī)劃，但由也屬于線性規(guī)劃，但由于于運(yùn)輸問題的特殊性（變量個(gè)數(shù)較多，運(yùn)輸問題的特殊性（變量個(gè)數(shù)較多，系數(shù)矩陣的特點(diǎn)），如果用單純形表格方法迭代，計(jì)算量很系數(shù)矩陣的特點(diǎn)），如果用單純形表格方法迭代，計(jì)算量很大。今天介紹的大。今天介紹的

6、 “表上作業(yè)法表上作業(yè)法”，是針對運(yùn)輸問題的特殊求解，是針對運(yùn)輸問題的特殊求解方法，實(shí)質(zhì)還是單純形法，但減少了計(jì)算量。方法，實(shí)質(zhì)還是單純形法，但減少了計(jì)算量。 表上作業(yè)法表上作業(yè)法適用于求解產(chǎn)銷平衡的運(yùn)輸問題。（產(chǎn)銷不平適用于求解產(chǎn)銷平衡的運(yùn)輸問題。（產(chǎn)銷不平衡的問題可轉(zhuǎn)化為平衡問題）衡的問題可轉(zhuǎn)化為平衡問題）2 2 運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法表上作業(yè)法表上作業(yè)法 一般步驟一般步驟：1、找出初始基本可行解；、找出初始基本可行解；2、檢查各非基變量的檢驗(yàn)數(shù)，是否達(dá)到最優(yōu)性條件，若達(dá)到，則得最優(yōu)、檢查各非基變量的檢驗(yàn)數(shù)，是否達(dá)到最優(yōu)性條件，若達(dá)到，則得最優(yōu)解；否則解；否則 轉(zhuǎn)第三步；

7、轉(zhuǎn)第三步；3、確定出基變量、進(jìn)基變量，用閉回路方法進(jìn)行調(diào)整，得到新的基可、確定出基變量、進(jìn)基變量，用閉回路方法進(jìn)行調(diào)整，得到新的基可 行解；行解；4、重復(fù)第二、第三步，直至得到最優(yōu)解。、重復(fù)第二、第三步，直至得到最優(yōu)解。 銷地 運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059 銷量（噸）3656一、確定初始基本可行解：一、確定初始基本可行解： 對于有對于有m m個(gè)產(chǎn)地個(gè)產(chǎn)地n n個(gè)銷地的產(chǎn)銷平衡問題，有個(gè)銷地的產(chǎn)銷平衡問題，有m m個(gè)關(guān)于產(chǎn)量個(gè)關(guān)于產(chǎn)量的約束方程和的約束方程和n n個(gè)關(guān)于銷量的約束方程。表面上，共有個(gè)關(guān)于銷量的約束方程。表面上，共有m+nm

8、+n個(gè)個(gè)約束方程。約束方程。 但由于產(chǎn)銷平衡，其模型最多只有但由于產(chǎn)銷平衡，其模型最多只有m+n-1m+n-1個(gè)獨(dú)立的約束方個(gè)獨(dú)立的約束方程，所以運(yùn)輸問題實(shí)際上有程，所以運(yùn)輸問題實(shí)際上有m+n-1m+n-1個(gè)基變量個(gè)基變量。在。在m mn n的產(chǎn)銷的產(chǎn)銷平衡表上給出平衡表上給出m+n-1m+n-1個(gè)數(shù)字格，其相對應(yīng)的調(diào)運(yùn)量的值即為個(gè)數(shù)字格，其相對應(yīng)的調(diào)運(yùn)量的值即為基變量的值?；兞康闹怠?那么在該例中，應(yīng)有那么在該例中，應(yīng)有 3+4-1=63+4-1=6個(gè)基變量。個(gè)基變量。1.最小元素法最小元素法 最小元素法的思想是就近供應(yīng)，即對單位運(yùn)價(jià)最小最小元素法的思想是就近供應(yīng)，即對單位運(yùn)價(jià)最小的變量分

9、配運(yùn)輸量。的變量分配運(yùn)輸量。 在表上找到單位運(yùn)價(jià)最小的在表上找到單位運(yùn)價(jià)最小的x x2121，并使，并使x x2121取盡可能大取盡可能大的值，即的值，即x x2121=3,=3,把把A A1 1的產(chǎn)量改為的產(chǎn)量改為1 1，B B1 1的銷量改為的銷量改為0 0，并，并把把B B1 1列劃去。在剩下的列劃去。在剩下的3 33 3矩陣中再找最小運(yùn)價(jià)，同矩陣中再找最小運(yùn)價(jià)，同理可得其他的基本可行解。理可得其他的基本可行解。 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 37 3 0 A2 3 1 4 1 0 A3 6 39 3 0 銷量 3 0 6 0 5 4 0 6 3 0 20203113

10、10851029471表中填表中填有數(shù)字的格有數(shù)字的格對應(yīng)于對應(yīng)于基變量基變量( (取值即為格中數(shù)字），而取值即為格中數(shù)字），而空格空格對應(yīng)對應(yīng)的是的是非基變量非基變量（取值為零）（取值為零）. .n在求初始基本可行解時(shí)要在求初始基本可行解時(shí)要注意注意的一個(gè)問題：的一個(gè)問題： 當(dāng)我們?nèi)《ó?dāng)我們?nèi)《▁ xijij的值之后，會出現(xiàn)的值之后，會出現(xiàn)A Ai i的產(chǎn)量與的產(chǎn)量與B Bj j的銷量都改為零的情的銷量都改為零的情況，這時(shí)只能劃去況，這時(shí)只能劃去A Ai i行或行或B Bj j列，但不能同時(shí)劃去列，但不能同時(shí)劃去A Ai i行與行與B Bj j列。列。（或者在同時(shí)劃去（或者在同時(shí)劃去A Ai

11、 i行與行與B Bj j列時(shí)，在該行或該列的任意空格處填加一列時(shí)，在該行或該列的任意空格處填加一個(gè)個(gè)0 0。）。） 這樣可以保證填過數(shù)或零的格為這樣可以保證填過數(shù)或零的格為m+n-1m+n-1個(gè)，即保證基變量的個(gè)數(shù)為個(gè)，即保證基變量的個(gè)數(shù)為m+n-1m+n-1個(gè)。個(gè)。2.Vogel法法 Vogel法的思想是法的思想是:一地的產(chǎn)品如果不能按照最小運(yùn)一地的產(chǎn)品如果不能按照最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有差額，差額越大，費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有差額，差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加得越多。因而差說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加得越多。因而差額越大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)

12、調(diào)運(yùn)。額越大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。 銷地產(chǎn)地 B1 B2 B3 B4 A1 5 20 0 0 7 A2 3 11 1 1 6 A36 31 2222 5 1111 3322 2020311310294711085二二、最優(yōu)解的判別、最優(yōu)解的判別 判別解的最優(yōu)性需要：判別解的最優(yōu)性需要：計(jì)算檢驗(yàn)數(shù)。計(jì)算檢驗(yàn)數(shù)。方法有兩種方法有兩種 閉回路：閉回路：是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，遇到代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，遇到代表基變量的填入數(shù)字的格可轉(zhuǎn)基變量的填入數(shù)字的格可轉(zhuǎn)9090度（當(dāng)然也

13、可以不改變方向）度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做此形成的封閉折線叫做閉回路閉回路。一個(gè)空格存在唯一的閉回一個(gè)空格存在唯一的閉回路。路。1 1.閉回路法閉回路法因?yàn)槿我夥腔蛄烤杀硎緸榛蛄康奈ㄒ痪€性組因?yàn)槿我夥腔蛄烤杀硎緸榛蛄康奈ㄒ痪€性組合，因此對于任意空格都合，因此對于任意空格都能夠找到、并且只能找到能夠找到、并且只能找到唯一的唯一的一條閉回路。一條閉回路。 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1（+）1 4 （-） 3 7 A2（-） 3 1 （+） 4 A363

14、 9 銷量 3 6 5 6 108531131029471從非基變量從非基變量 出發(fā)，找到一個(gè)閉回路如上表所示?；芈酚兴某霭l(fā)，找到一個(gè)閉回路如上表所示?；芈酚兴膫€(gè)頂點(diǎn)，除個(gè)頂點(diǎn)，除 外，其余都為基變量。外，其余都為基變量。調(diào)整調(diào)運(yùn)量：調(diào)整調(diào)運(yùn)量： ，運(yùn)費(fèi)增加了，運(yùn)費(fèi)增加了3 3元；元； ，運(yùn)費(fèi)減少，運(yùn)費(fèi)減少3 3元元 ，運(yùn)費(fèi)增加，運(yùn)費(fèi)增加2 2元；元； ，運(yùn)費(fèi)減少，運(yùn)費(fèi)減少1 1元元調(diào)整后，調(diào)整后，總運(yùn)費(fèi)增加總運(yùn)費(fèi)增加：3-3+2-1=13-3+2-1=1元。元。說明如果讓說明如果讓 為基變量，運(yùn)費(fèi)就會增加，其增加值為基變量，運(yùn)費(fèi)就會增加，其增加值1 1作為作為 的的檢驗(yàn)數(shù)檢驗(yàn)數(shù)，111x12

15、3x113x11x121x11x11x11x閉回路法計(jì)算檢驗(yàn)數(shù)：閉回路法計(jì)算檢驗(yàn)數(shù)：就是對于代表非基變量的空格就是對于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1 1，由于產(chǎn)銷平衡的，由于產(chǎn)銷平衡的要求要求, ,必須對這個(gè)空格的閉回路中的各頂點(diǎn)的調(diào)運(yùn)量加上或減必須對這個(gè)空格的閉回路中的各頂點(diǎn)的調(diào)運(yùn)量加上或減少少1 1。最后計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來。最后計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化。以這個(gè)變化的數(shù)值，作為各空格（非基變量）的檢的變化。以這個(gè)變化的數(shù)值，作為各空格（非基變量）的檢驗(yàn)數(shù)。驗(yàn)數(shù)。判別最優(yōu)解準(zhǔn)則：判

16、別最優(yōu)解準(zhǔn)則：如果所有代表非基變量的空格的檢驗(yàn)如果所有代表非基變量的空格的檢驗(yàn)數(shù)都大于等于零，則已求得最優(yōu)解；否則繼續(xù)改進(jìn)找出最優(yōu)數(shù)都大于等于零，則已求得最優(yōu)解；否則繼續(xù)改進(jìn)找出最優(yōu)解。解。2.2.位勢法位勢法 （1 1）對運(yùn)輸表上的每一行賦予一個(gè)數(shù)值）對運(yùn)輸表上的每一行賦予一個(gè)數(shù)值 ，對每一列賦予一個(gè)數(shù)值對每一列賦予一個(gè)數(shù)值 ，稱為行（列，稱為行（列) )位勢。位勢。（2 2）行（列）行（列) )位勢的數(shù)值是由基變量的檢驗(yàn)數(shù)所決位勢的數(shù)值是由基變量的檢驗(yàn)數(shù)所決定的，即定的，即基變量基變量要滿足：要滿足： 非基變量非基變量 的檢驗(yàn)數(shù)就可以用公式的檢驗(yàn)數(shù)就可以用公式 求出。求出。0jiijijv

17、ucjiijijvuciujvijx 我們先給我們先給u u1 1賦個(gè)任意數(shù)值，不妨設(shè)賦個(gè)任意數(shù)值，不妨設(shè)u u1 1=0=0，則從基變，則從基變量量x x1111的檢驗(yàn)數(shù)求得的檢驗(yàn)數(shù)求得 v v3 3=c=c1313-u-u1 1=3-0=3 =3-0=3 。同理可以求得同理可以求得 v v4 4=10=10，u u2 2= -1= -1，等等見上表。，等等見上表。檢驗(yàn)數(shù)的求法，即用公式檢驗(yàn)數(shù)的求法，即用公式 ，如如 。 銷地產(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 3113108510

18、29471jiijijvuc1203111111vuc位勢法計(jì)算檢驗(yàn)數(shù)：位勢法計(jì)算檢驗(yàn)數(shù)： 檢驗(yàn)數(shù)：檢驗(yàn)數(shù)： ijnmijijijijBijijPvvuucYPcPBCc),.,(1,.,11又因?yàn)榛兞康臋z驗(yàn)數(shù)為又因?yàn)榛兞康臋z驗(yàn)數(shù)為0 0，于是由（，于是由（m+n-1)m+n-1)個(gè)基變個(gè)基變 量的檢驗(yàn)數(shù)量的檢驗(yàn)數(shù)可解出可解出 ，進(jìn)而計(jì)算其他非基，進(jìn)而計(jì)算其他非基變量的檢驗(yàn)數(shù)。變量的檢驗(yàn)數(shù)。0jiijvuc),.,(1,.,1nmvvuu其中其中 TijP)0.0, 1.,0, 1,.0(第第i i個(gè)分量個(gè)分量第第m+jm+j個(gè)分個(gè)分量量三、改進(jìn)運(yùn)輸方案的辦法三、改進(jìn)運(yùn)輸方案的辦法閉回路調(diào)

19、整法閉回路調(diào)整法當(dāng)表中的某個(gè)檢驗(yàn)數(shù)小于零時(shí)，方案不為最優(yōu)，需要調(diào)整。當(dāng)表中的某個(gè)檢驗(yàn)數(shù)小于零時(shí)，方案不為最優(yōu)，需要調(diào)整。方法是：選取所有負(fù)檢驗(yàn)數(shù)中最小的非基變量作為入基變量，方法是：選取所有負(fù)檢驗(yàn)數(shù)中最小的非基變量作為入基變量，以求盡快實(shí)現(xiàn)最優(yōu)。以求盡快實(shí)現(xiàn)最優(yōu)。（1 1）確定調(diào)整量確定調(diào)整量：例：?。豪喝?，表明增加一個(gè)單位的，表明增加一個(gè)單位的 運(yùn)輸量，可使得總運(yùn)費(fèi)減少運(yùn)輸量，可使得總運(yùn)費(fèi)減少1 1。在以。在以 為出發(fā)點(diǎn)的閉為出發(fā)點(diǎn)的閉回路中，找出所有偶數(shù)頂點(diǎn)的調(diào)運(yùn)量：回路中，找出所有偶數(shù)頂點(diǎn)的調(diào)運(yùn)量： ，則調(diào)整量則調(diào)整量 （2 2）調(diào)整方法調(diào)整方法：把所有閉回路上為偶數(shù)頂點(diǎn)的運(yùn)輸量都減

20、：把所有閉回路上為偶數(shù)頂點(diǎn)的運(yùn)輸量都減少這個(gè)值，奇數(shù)頂點(diǎn)的運(yùn)輸量都增加這個(gè)值少這個(gè)值，奇數(shù)頂點(diǎn)的運(yùn)輸量都增加這個(gè)值( (見下表見下表) )。12424x314x123x1)3 , 1min(24x24x 銷地產(chǎn)地 B1 B2 B3 B4 ui A1 4(+1) 3(-1) 0 A2 3 1 (-1) +1 -1 A3 6 3 -5 vj 2 9 3 10 311310851029471調(diào)整運(yùn)量后的新方案：調(diào)整運(yùn)量后的新方案： 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 5 2 7 A2 3 1 4 A3 6 3 9 銷量 3 6 5 6 銷地產(chǎn)地 B1 B2 B3 B4 ui A1 0 2

21、5 2 0 A2 3 2 1 1 -2 A3 9 6 12 3 -5 vj 3 9 3 10 311310851029471對上表用位勢法進(jìn)行檢驗(yàn)如下表，可知已達(dá)最優(yōu)解。對上表用位勢法進(jìn)行檢驗(yàn)如下表，可知已達(dá)最優(yōu)解。表上作業(yè)法表上作業(yè)法的一般步驟：的一般步驟：1 1、用最小元素法或、用最小元素法或VogelVogel法確定初始基可行解；法確定初始基可行解；2 2、判斷是否為最優(yōu)：用閉回路法或位勢法計(jì)算空格檢驗(yàn)數(shù)，、判斷是否為最優(yōu)：用閉回路法或位勢法計(jì)算空格檢驗(yàn)數(shù)，若所有檢驗(yàn)數(shù)均非負(fù)，則已得到最優(yōu)解；否則進(jìn)入第三步；若所有檢驗(yàn)數(shù)均非負(fù)，則已得到最優(yōu)解；否則進(jìn)入第三步；3 3、 從所有負(fù)檢驗(yàn)數(shù)中選

22、擇最小者對應(yīng)空格作為進(jìn)基變量，從所有負(fù)檢驗(yàn)數(shù)中選擇最小者對應(yīng)空格作為進(jìn)基變量，從此點(diǎn)出發(fā)作閉回路，確定調(diào)整量從此點(diǎn)出發(fā)作閉回路，確定調(diào)整量 ，奇點(diǎn)處增加，奇點(diǎn)處增加 ，偶點(diǎn)處減少偶點(diǎn)處減少 。例：例：用表上作業(yè)法，求解下面的用表上作業(yè)法，求解下面的 運(yùn)輸問題運(yùn)輸問題 ： 銷地 產(chǎn)地甲乙丙丁產(chǎn)量137645224322343853銷量3322解解: :用最小元素法確定初始基可行解，如下表所示：用最小元素法確定初始基可行解，如下表所示： 銷地 產(chǎn)地甲乙丙丁產(chǎn)量1 33 70 62 405 （0）2 2 4 3 2 2 2 (-2）3 4 33 8 53 （-4）銷量3 （3）3 （7）2 （6）2

23、 （4） 銷地 產(chǎn)地甲乙丙丁產(chǎn)量1 3 0 2 05 （0）21 -1 -1 2 2 (-2）35 36 5 3 （-4）銷量3 （3）3 （7）2 （6）2 （4）+- 銷地 產(chǎn)地甲乙丙丁產(chǎn)量1 33 70 6 425 （0）2 2 4 32 2 0 2 (-2）3 4 33 8 53 （-4）銷量3 （3）3 （7）2 （5）2 （4） 銷地 產(chǎn)地甲乙丙丁產(chǎn)量1 3 01 25 （0）21 -12 0 2 (-2）35 3753 （-4）銷量3 （3）3 （7）2 （5）2 （4）+- 銷地 產(chǎn)地甲乙丙丁產(chǎn)量1 33 7 6 425 （0）2 2 40 32 2 0 2 (-2）3 4 3

24、3 8 53 （-3）銷量3 （3）3 （6）2 （5）2 （4）1 31 1 25 （0）21 0 2 0 2 (-2）34 36 4 3 （-3）銷量3 （3）3 （6）2 （5）2 （4）此時(shí)所有非基變量的檢驗(yàn)數(shù)均非負(fù)，故已達(dá)最優(yōu)解。此時(shí)所有非基變量的檢驗(yàn)數(shù)均非負(fù)，故已達(dá)最優(yōu)解。一、產(chǎn)銷不平衡的運(yùn)輸問題一、產(chǎn)銷不平衡的運(yùn)輸問題例例1 1：某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地 ， ，將產(chǎn)品運(yùn)往三個(gè)銷地，將產(chǎn)品運(yùn)往三個(gè)銷地 ， ， ， 各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。 應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最?。繎?yīng)如何調(diào)

25、運(yùn)可使運(yùn)費(fèi)最小？ 1A2A1B2B3B 銷地 運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3產(chǎn)量（件）A1646200A2655300 銷量（件）250200200 5006503 產(chǎn)銷不平衡的運(yùn)輸問題及應(yīng)用產(chǎn)銷不平衡的運(yùn)輸問題及應(yīng)用1A3B2A1A3B1B2A1A3B2B1B2A1A3B例例1 1：某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地 ， ，將產(chǎn)品運(yùn)往三個(gè)銷地，將產(chǎn)品運(yùn)往三個(gè)銷地 ， ， ， 各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。 應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最?。繎?yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最?。?2A1A例例1 1：某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)

26、產(chǎn)地 ， ，將產(chǎn)品運(yùn)往三個(gè)銷地，將產(chǎn)品運(yùn)往三個(gè)銷地 ， ， ， 各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。 應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？ 2A1A例例1 1：某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地 ， ，將產(chǎn)品運(yùn)往三個(gè)銷地，將產(chǎn)品運(yùn)往三個(gè)銷地 ， ， ， 各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。 應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？ 2A1A例例1 1：某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地 ， ，將產(chǎn)

27、品運(yùn)往三個(gè)銷地，將產(chǎn)品運(yùn)往三個(gè)銷地 ， ， ， 各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。 應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？ 2A1A例例1 1：某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地 ， ，將產(chǎn)品運(yùn)往三個(gè)銷地，將產(chǎn)品運(yùn)往三個(gè)銷地 ， ， ， 各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。 應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？ 2A1A例例1 1：某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地 ， ，將產(chǎn)品運(yùn)往三個(gè)銷地，

28、將產(chǎn)品運(yùn)往三個(gè)銷地 ， ， ， 各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。 應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？ 2A1A易知這個(gè)問題中：總產(chǎn)量總銷量，即易知這個(gè)問題中：總產(chǎn)量總銷量，即3121200200250650500300200jjiids這時(shí)可考慮增加一個(gè)假想產(chǎn)地，其產(chǎn)量是（總銷量總產(chǎn)量這時(shí)可考慮增加一個(gè)假想產(chǎn)地，其產(chǎn)量是（總銷量總產(chǎn)量150)150)他到各銷地的單位運(yùn)費(fèi)是于是得到如下的表格：他到各銷地的單位運(yùn)費(fèi)是于是得到如下的表格：3A 銷地 運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3產(chǎn)量（件）A164

29、6200A2655300A 銷量（件）250200200650例例2 2：某單位有三個(gè)區(qū)，一區(qū)、二區(qū)、三區(qū)；每年需要生活某單位有三個(gè)區(qū)，一區(qū)、二區(qū)、三區(qū)；每年需要生活用煤和取暖用煤各用煤和取暖用煤各30003000噸，噸，10001000噸，噸，20002000噸；由河北臨城、噸；由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，兩地價(jià)格和煤質(zhì)相同，兩煤山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，兩地價(jià)格和煤質(zhì)相同，兩煤礦的供應(yīng)能力分別是礦的供應(yīng)能力分別是15001500噸，和噸，和40004000噸。由煤礦至該單位噸。由煤礦至該單位三個(gè)區(qū)的單位運(yùn)價(jià)如表所示。三個(gè)區(qū)的單位運(yùn)價(jià)如表所示。 銷地 運(yùn)費(fèi)單價(jià)產(chǎn)地一區(qū)二區(qū)三區(qū)供應(yīng)量

30、（噸）盂縣1.81.71.554000臨城1.61.51.751500 需要量（噸）300010002000由于供應(yīng)能力限制，經(jīng)研究決定，一區(qū)供應(yīng)量可減少由于供應(yīng)能力限制，經(jīng)研究決定，一區(qū)供應(yīng)量可減少03000300噸，噸，二區(qū)全部滿足，三區(qū)不能少于二區(qū)全部滿足，三區(qū)不能少于15001500噸，試求使得運(yùn)費(fèi)最小的運(yùn)噸，試求使得運(yùn)費(fèi)最小的運(yùn)輸方案？輸方案？根據(jù)題意，添加虛擬產(chǎn)地后，可作出產(chǎn)銷平衡的運(yùn)價(jià)表：根據(jù)題意，添加虛擬產(chǎn)地后，可作出產(chǎn)銷平衡的運(yùn)價(jià)表： 銷地 運(yùn)費(fèi)單價(jià)產(chǎn)地一區(qū)B1一區(qū)1B1二區(qū)B2三區(qū)B3三區(qū)1B3供應(yīng)量（噸）盂縣1.81.81.71.551.554000臨城1.61.61.5

31、1.751.751500虛擬產(chǎn)地M0MM0500 需要量（噸）2700300100015005006000 銷地 運(yùn)費(fèi)單價(jià)產(chǎn)地供應(yīng)量（萬噸）A1613221750B1413191560C192023_50最低需求萬噸3070010最高需求萬噸507030不限例：例：設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的化肥，假設(shè)等量的化設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的化肥，假設(shè)等量的化肥在這個(gè)地區(qū)的使用效果相同。各廠的產(chǎn)量、各地區(qū)的需肥在這個(gè)地區(qū)的使用效果相同。各廠的產(chǎn)量、各地區(qū)的需要量、單位運(yùn)價(jià)如表所示。求出運(yùn)費(fèi)最省的調(diào)撥方案。要量、單位運(yùn)價(jià)如表所示。求出運(yùn)費(fèi)最省的調(diào)撥方案。解：無論考慮需求的上限還是下限，這都是一個(gè)產(chǎn)銷

32、不平衡的問題。解：無論考慮需求的上限還是下限，這都是一個(gè)產(chǎn)銷不平衡的問題。 當(dāng)考慮下限時(shí)，產(chǎn)當(dāng)考慮下限時(shí)，產(chǎn)銷；當(dāng)考慮需求上限時(shí)，產(chǎn)銷；當(dāng)考慮需求上限時(shí)，產(chǎn)銷。銷。 于是可以考慮在滿足最低需求的情況下，兼顧最高需求。即將每于是可以考慮在滿足最低需求的情況下，兼顧最高需求。即將每 個(gè)地區(qū)的需求分為個(gè)地區(qū)的需求分為最低需求最低需求和和（最高（最高- -最低）需求最低）需求，最低部分必須，最低部分必須 滿足，高出的部分可滿足也可不滿足。雖然銷地滿足，高出的部分可滿足也可不滿足。雖然銷地的需求無上限，的需求無上限， 但根據(jù)生產(chǎn)能力，最多可以給她分配但根據(jù)生產(chǎn)能力，最多可以給她分配6060萬噸。萬噸。

33、另外若將最高需求考慮進(jìn)來，則需添加虛擬產(chǎn)地另外若將最高需求考慮進(jìn)來，則需添加虛擬產(chǎn)地D D，其產(chǎn)量應(yīng)為，其產(chǎn)量應(yīng)為 5050萬噸。萬噸。 于是可給出如下的產(chǎn)銷平衡及運(yùn)價(jià)表。于是可給出如下的產(chǎn)銷平衡及運(yùn)價(jià)表。 銷地 運(yùn)費(fèi)單價(jià)產(chǎn)地供應(yīng)量（噸）A1616132222171750B1414131919151560C1919202323MM50假想DM0MM0M050最高需求萬噸3020700301050210二、生產(chǎn)與存儲問題二、生產(chǎn)與存儲問題例例4 4：某廠按照合同規(guī)定須于當(dāng)年每季度末分別提供某廠按照合同規(guī)定須于當(dāng)年每季度末分別提供1010，1515，2525，2020臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表所示。又如果生產(chǎn)產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表所示。又如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個(gè)季度，存儲出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個(gè)季度，存儲維護(hù)費(fèi)用維護(hù)費(fèi)用0.150.15萬元。要求在完成合同的情況下，使得全萬元。要求在完成合同的情況下，使得全年生產(chǎn)（存儲）費(fèi)用最小的決策。年生產(chǎn)（存儲）費(fèi)用最小的決策。季度生產(chǎn)能力/