运输运输(yùnshū)问题问题——表上作业法表上作业法单纯形法与表上作业法的关系(guānxì)：（1）找出初始基可行解（2）求各非基变量的检验数（3）判断是否最优解计算表中空格检验数计算表中空格检验数表上给出表上给出m+n-1个数字格个数字格判断方法相同判断方法相同第1页/共54页第一页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法换基换基: :（4）确定换入变量(biànliàng)和换出变量(biànliàng)找出新的基可行解5）重复（2）、（3）直至求出最优解表上调整（闭回路调整）表上调整（闭回路调整）（运输问题必有最优解）（运输问题必有最优解）停止停止(tíngzhǐ)最优解？是是否否第2页/共54页第二页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法举例说明表上作业举例说明表上作业(zuòyè)(zuòyè)法法某部门(bùmén)三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表：4122854396111110销量销量产量产量销地产地第3页/共54页第三页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法第一步：确定初始基可行第一步：确定初始基可行(kěxíng)(kěxíng)解解————最小元素法、伏格最小元素法、伏格尔法尔法【1】最小元素法思路：就近供应，从单价中最小运价确定供应量，逐步次小，直至(zhízhì)得到m+n-1个数字格。
第4页/共54页第四页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法最小元素(yuánsù)法举例4122854396111110销量产量销地产地822010100614868000060第5页/共54页第五页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法最小元素法得到的初始(chūshǐ)调运方案4122854396111110销量产量销地产地82101468第6页/共54页第六页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法练习练习(liànxí)(liànxí)某部门三个工厂生产同一(tóngyī)产品的产量,四个销售点的销量及单位运价如下表：311174328510109销量产量销地产地第7页/共54页第七页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法最小元素(yuánsù)法练习31117432851010 9销量产量销地产地31104 403 6333000030第8页/共54页第八页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法初始(chūshǐ)调运方案311174328510109销量产量销地产地31 4 633最小元素(yuánsù)法缺点：会出现顾此失彼（运费差额问题）考虑考虑运价差运价差第9页/共54页第九页，共55页。
运输问题运输问题(wèntí)——表上作业法表上作业法罚数（即差额(chāé)）=次小运价-最小运价对差额最大处，采用最小运费调运2】伏格尔法思路(sīlù)：第一步：确定初始基可行解——最小元素法、伏格尔法第10页/共54页第十页，共55页 伏格尔法思路伏格尔法思路(sīlù)(sīlù)¢罚数（即差额）的解释(jiěshì)：¢差额大，则不按最小运费调运，运费增加大¢差额小，则不按最小运费调运，运费增加不大运输问题运输问题(wèntí)——表上作业法表上作业法第11页/共54页第十一页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法结合例1说明(shuōmíng)这种方法4122854396111110销量产量销地销地产地产地行罚数①①04-4=0第一次第一次第12页/共54页第十二页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法4122854396111110销量产量销地销地产地产地行罚数①①013-2=1第一次第一次第13页/共54页第十三页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法4122854396111110销量产量销地销地产地产地行罚数①①011第一次第一次第14页/共54页第十四页，共55页。
运输运输(yùnshū)问题问题——表上作业法表上作业法4122854396111110销量产量销地销地产地产地行罚数①①011 列 罚 数2153①①第一次第一次第15页/共54页第十五页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法4122854396111110销量产量销地销地产地产地行罚数①①011 列 罚 数2153①①1480优先安排销地优先安排销地 ，否则运价会，否则运价会更高更高下次下次(xià cì)不考虑该列不考虑该列第一次第一次第16页/共54页第十六页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法第二次第二次行罚数②②012 列 罚 数213②②优先安排销地优先安排销地 ，否则运价会，否则运价会更高更高84122854396111110销量产量销地销地产地产地148006下次(xià cì)不考虑该行第17页/共54页第十七页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法行罚数③③01 列 罚 数212③③84122854396111110销量产量销地销地产地产地148006下次(xià cì)不考虑该列802第三次第三次第18页/共54页第十八页，共55页。
运输运输(yùnshū)问题问题——表上作业法表上作业法行罚数④④76 列 罚 数12④④84122854396111110销量产量销地销地产地产地1480068024120下次(xià cì)不考虑该列第四次第四次第19页/共54页第十九页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法行罚数⑤⑤00 列 罚 数2⑤⑤4284122854396111110销量产量销地销地产地产地1480068024120004第五次第五次0第20页/共54页第二十页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法例1用伏格尔法得到(dédào)的初始基可行解4122854396111110销量产量销地销地产地产地48148122目标函数值目标函数值用最小元素法求出的目标(mùbiāo)函数z=246一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解第21页/共54页第二十一页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法 列 罚 数1352①①31117432851010 9销量产量销地销地产地产地练习(liànxí)行罚数①①0第一次第一次11优先安排销地优先安排销地 ，否则运价会，否则运价会更高更高630第22页/共54页第二十二页，共55页。
运输问题运输问题(wèntí)——表上作业法表上作业法31117432851010 9销量产量销地销地产地产地行罚数②②0第二次第二次12 列 罚 数132630优先安排销地优先安排销地 ，否则运价会，否则运价会更高更高303②②第23页/共54页第二十三页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法31117432851010 9销量产量销地销地产地产地行罚数③③0第三次第三次1 列 罚 数122630303③③310第24页/共54页第二十四页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法31117432851010 9销量产量销地销地产地产地行罚数④④7第四次第四次6 列 罚 数12630303④④310502第25页/共54页第二十五页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法31117432851010 9销量产量销地销地产地产地行罚数⑤⑤0第五次第五次0 列 罚 数2630303⑤⑤310502120200第26页/共54页第二十六页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法练习题用伏格尔法得到(dédào)的初始基可行解311174328510109销量(xiāo liànɡ)产量销地产地31 5 623用最小元素法求出的目标函数z=86第27页/共54页第二十七页，共55页。
运输运输(yùnshū)问题问题——表上作业法表上作业法第二步：解的最优性检验第二步：解的最优性检验(jiǎnyàn)(jiǎnyàn)•思路：计算空格（非基变量）的检验数•两种方法：•【1】闭回路法•每一空格出发一定(yīdìng)存在且可以找到唯一的闭回路•【2】位势法•由对偶理论，得检验数为第28页/共54页第二十八页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法【【1 1】闭回路】闭回路(huílù)(huílù)法法•在给出调运方案的计算表上，从每一空格(kōnɡɡé)出发找一条闭回路•以某空格(kōnɡɡé)为起点，用水平或垂直线向前划，当碰到一数字格时，可以转90度（也可以越过）后，继续前进，直到回到起始空格(kōnɡɡé)为止第29页/共54页第二十九页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法每一空格出发一定每一空格出发一定(yīdìng)(yīdìng)存在存在且可以找到唯一的闭回路且可以找到唯一的闭回路因m+n-1个数字格（基变量(biànliàng)）对应的系数向量是一个基。
则任一空格（非基变量(biànliàng)）对应的系数向量均可由这个基线性表示第30页/共54页第三十页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法闭回路闭回路(huílù)(huílù)法的经济解释法的经济解释若令若令分析：分析：——运费的增量运费的增量即增加1个单位的检验数=相应的运费增量第31页/共54页第三十一页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法4122854396111110销量产量销地产地82101468从初始从初始(chū shǐ)表分析：表分析：要保证产销(chǎnxiāo)平衡，则 称为闭回路 +1-1+1-1第32页/共54页第三十二页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法4122854396111110销量产量销地产地8210146821第33页/共54页第三十三页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法检验( jiǎnyàn)数表4122854396111110销量产量销地产地82101468211-11012表中的解不是最优解。
第34页/共54页第三十四页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法•或称对偶或称对偶(duì ǒu)变量法变量法【【2 2】位势】位势(wèishì)(wèishì)法法第35页/共54页第三十五页，共55页 运输运输(yùnshū)问题问题运输问题运输问题(wèntí)(wèntí)的对偶问题的对偶问题(wèntí)(wèntí)可写为可写为运输运输(yùnshū)(yùnshū)问题的对偶问问题的对偶问题题————对偶变量与原问题检验数对偶变量与原问题检验数的关系的关系第36页/共54页第三十六页，共55页 运输运输(yùnshū)问题问题线性规划问题变量的检验数为运输问题运输问题(wèntí)(wèntí)的对偶问题的对偶问题(wèntí)(wèntí)————对偶变量与原问题对偶变量与原问题(wèntí)(wèntí)检验数的关系检验数的关系变量的检验数为第37页/共54页第三十七页，共55页 运输运输(yùnshū)问题问题设运输(yùnshū)问题的一组基变量为运输问题的对偶问题运输问题的对偶问题————对偶变量与原问题检验对偶变量与原问题检验(jiǎnyàn)(jiǎnyàn)数的关系数的关系第38页/共54页第三十八页，共55页。
运输运输(yùnshū)问题问题由于基变量(biànliàng)的检验数为零，故有运输问题的对偶运输问题的对偶(duìǒu)(duìǒu)问题问题————对偶对偶(duìǒu)(duìǒu)变量与原问题变量与原问题检验数的关系检验数的关系m+n-1m+n-1个方程个方程m+nm+n个变量个变量有一个自由未知量第39页/共54页第三十九页，共55页 运输运输(yùnshū)问题问题方程组有解，且不唯一求出方程组的解（称为(chēnɡwéi)位势）而其他变量的检验数为运输问题运输问题(wèntí)(wèntí)的对偶问题的对偶问题(wèntí)(wèntí)————对偶变量与原问题对偶变量与原问题(wèntí)(wèntí)检验数的关系检验数的关系求运输问题求运输问题检验数的一检验数的一种方法种方法第40页/共54页第四十页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法最小元素法得到的初始最小元素法得到的初始(chū(chūshǐ)shǐ)基可行解基可行解311174328510109销量产量销地产地31 4 633为基变量则有为基变量则有第41页/共54页第四十一页，共55页。
运输问题运输问题(wèntí)——表上作业法表上作业法第42页/共54页第四十二页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法销地产地(chǎndì)00 0 000311174328510109-11021211存在负检验(jiǎnyàn)数，说明不是最优解检验数表检验数表第43页/共54页第四十三页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法第三步：解的调整第三步：解的调整(tiáozhěng)(tiáozhěng)•当在表中空格处出现负检验数时，表示未得最优解•若有两个和两个以上的负检验数，一般选其中最小的负检验数，以它对应的空格为调入格•即选择(xuǎnzé)最小检验数对应的非基变量为换入变量第44页/共54页第四十四页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法第三步：解的调整第三步：解的调整(tiáozhěng)(tiáozhěng)调整(tiáozhěng)位置（A2，B4）非空，回路角上的格至少为空，且保证数字的非负性4122854396111110销量产量销地产地82101468-1（（- ））（（- ））（（+ ））（（+ ））2222第45页/共54页第四十五页，共55页。
运输问题运输问题(wèntí)——表上作业法表上作业法调整(tiáozhěng)后的解为：4122854396111110销量产量销地产地821214482209112此时的解为最优解此时的解为最优解有有无无穷穷(wúqióng)多多最最优优解解第46页/共54页第四十六页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法几点说明几点说明(shuōmíng)(shuōmíng)：：•当检验数为负的变量超过两个(liǎnɡɡè)，选择最小者对应的变量换入；•在最优解的表中，若有非基变量的检验数=0，则该运输问题有无穷多最优解；第47页/共54页第四十七页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法几点说明几点说明(shuōmíng)(shuōmíng)：：•退化一•迭代过程中，若某一格填数时需同时划去一行和一列，此时(cǐshí)出现退化为保证m+n-1个非空格，需在上述的行或列中填入数字0第48页/共54页第四十八页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法退化退化(tuìhuà)(tuìhuà)情况一：情况一：某部门三个工厂生产(shēngchǎn)同一产品的产量,四个销售点的销量及单位运价如下表：4122854396111110销量销量产量产量销地产地8800第49页/共54页第四十九页，共55页。
运输问题运输问题(wèntí)——表上作业法表上作业法几点说明几点说明(shuōmíng)(shuōmíng)：：•退化二•闭回路上(lùshɑng)出现两个或两个以上的具有（-）标记的相等的最小值只能选一个作为调入格，经调整后，得退化解则在另一数字格上填入0第50页/共54页第五十页，共55页 运输运输(yùnshū)问题问题——表上作业法表上作业法退化退化(tuìhuà)(tuìhuà)情况二：情况二：闭回路法调整(tiáozhěng)，回路角上的格至少为空，且保证数字的非负性4122854396111110销量产量销地产地82101468-1（- ）（（- ））（（+ ））（（+ ））22222第51页/共54页第五十一页，共55页 运输问题运输问题(wèntí)——表上作业法表上作业法退化退化(tuìhuà)(tuìhuà)情况二：情况二：只能选一个作为(zuòwéi)调入格，另一个数字格填入04122854396111110销量产量销地产地812148020第52页/共54页第五十二页，共55页 下一节下一节 产销产销(chǎnxiāo)(chǎnxiāo)不平不平衡的运输问题衡的运输问题n产大于销n产小于销第53页/共54页第五十三页，共55页。
感谢您的观看(guānkàn)！第54页/共54页第五十四页，共55页 内容(nèiróng)总结运输问题——表上作业法运输问题——表上作业法运输问题——表上作业法4）确定(quèdìng)换入变量和换出变量找出新的基可行解5）重复（2）、（3）直至求出最优解表上调整（闭回路调整）某部门三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表：第一步：确定(quèdìng)初始基可行解 ——最小元素法、伏格尔法就近供应，从单价中最小运价确定(quèdìng)供应量，逐步次小，直至得到m+n-1个数字格 ）第五十五页，共55页。