4-02运输问题表上作业法

运输问题的表上作业法1、单纯形法（为什麽？）2、表上作业法由于问题的特殊形式而采用的更简洁、更方便的方法一、表上作业法的基本思想先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图3-1所示。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。确定初始方案(初始基本可行解)改进调整（换基迭代）否判定是否最优？是结束最优方案图1运输问题求解思路图二、初始方案的确定1、作业表（产销平衡表）初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。表2是两个产地、三个销地的运输问题作业表。调销地运量产地B1B2B3产量A1c11X11c12X12c13X13a1A2c21X21c22X22c23X23a2销量b1b2b33121jjiiba表2运输问题作业表（产销平衡表）其中xij是决策变量，表示待确定的从第i个产地到第j个销地的调运量，cij为从第i个产地到第j个销地的单位运价。2、确定初始方案的步骤：（1）选择一个xij，令xij=min{ai，bj}=个销地需求满足第个销地第个产地的产量全部运到第jjbjiia将具体数值填入xij在表中的位置；（2）调整产销剩余数量：从ai和bj中分别减去xij的值，若ai-xij=0，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai；若bj-xij=0，则划去销地Bj所在的列，说明该销地需求已得到满足，而产地Ai尚有存余量ai-bj；（3）当作业表中所有的行或列均被划去，说明所有的产量均已运到各个销地，需求全部满足，xij的取值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（2）。按照上述步骤产生的一组变量必定不构成闭回路，其取值非负，且总数是m+n-1个，因此构成运输问题的基本可行解。对xij的选择采用不同的规则就形成各种不同的方法，比如每次总是在作业表剩余的格子中选择运价（或运距）最小者对应的xij，则构成最小元素法，若每次都选择左上角格子对应的xij就形成西北角法（也称左上角法）。3、举例例3-2甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4，求使总运输量最少的调运方案。表3-4例3-2有关信息表450200150100日销量（需求量）250756580乙2001007090甲日产量（供应量）CBA运距城市煤矿例3-2的数学模型;3,2,1;2,1,0200150100250200..7565801007090min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxZij需求约束日产量约束总运输量分别使用最小元素法和西北角法求出初始方案。&最小元素法的基本思想是“就近供应”；&西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同；调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用最小元素法确定例3-2初始调运方案150100100100100100100得到初始调运方案为：x11=100，x13=100，x22=150，x23=100最小元素法实施步骤口诀《运价表》上找最小，《平衡表》上定产销；满足销量划去“列”，修改“行产”要记牢；（满足产量划去“行”，修改“列销”要记牢）划去列(行)对《运价》，修改“行产(列销)”在《产销》；余表再来找最小，方案很快就找到。调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用西北角法确定例3-2初始调运方案1001001005050200200得到初始调运方案为：x11=100，x12=100，x22=50，x23=200三、最优性检验检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。定义凡是能排成(3-4)或(3-5)形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中互不相同,互不相同。132222111,,,,,jijijijijijisssxxxxxxsssjijijijijijixxxxxx123221211,,,,,siii,,,21sjjj,,,211、闭回路法X11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34例设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路在表中的表示法——用折线连接起来的顶点变量。},,,,,{212434331311xxxxxx练习请给出闭回路和在表中的表示法。},,,{14242212xxxx},,,,,{121131332322xxxxxxX11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34练习下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？（a）（b）（c）（d）（e）表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的；表中的每一行和每一列由折线相连的闭回路的顶点只有两个；有关闭回路的一些重要结果定理1设是一个闭回路，则该闭回路中的变量所对应的系数列向量具有下面的关系：132222111,,,,,jijijijijijisssxxxxxx132222111,,,,,jijijijijijisssPPPPPP0132222111jijijijijijisssPPPPPP注意：列向量Pij=(0,…,0,1,0,…,0,1,0,…0)T中两个元素1分别处于第i行和第m+j行，直接计算即可得到结果。定理的证明可借助定理3-1和高等代数中“向量组中，若部分向量线性相关，则整个向量组就线性相关”的定理得到。定理2若变量组中有一个部分组构成闭回路，则该变量组对应的系数列向量线性相关。rrjijijixxx,,,2211约定作为起始顶点的非基变量为偶数次顶点，其它顶点从1开始顺次排列，那么，该非基变量xij的检验数：现在，在用最小元素法确定例3-2初始调运方案的基础上，计算非基变量X12的检验数：ij=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）（3-6）闭回路法以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450100100100150例3-2初始调运方案中以X12(X21)为起点的闭回路非基变量X12的检验数：非基变量X21的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，12=（c21+c13）-（c11+c23）=80+100-（90+75）=15。21经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。2、位势法以例3-2初始调运方案为例，设置位势变量和，在初始调运方案表的基础上增加一行和一列（见下页表格）。然后构造下面的方程组：iujv7565100902332222213311111cvucvucvucvu（3-7）例3-2初始调运方案位势变量对应表调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450位势变量vjv1v2v3100100100150位势变量uiu1u2方程组的特点：方程个数是m+n-1=2+3-1=4个，位势变量共有m+n=2+3=5个，通常称ui为第i行的位势，称vj为第j列的位势；初始方案的每一个基变量xij对应一个方程——-—所在行和列对应的位势变量之和等于该基变量对应的运距（或运价）：ui+vj=cij；方程组恰有一个自由变量，可以证明方程组中任意一个变量均可取作自由变量。给定自由变量一个值，解方程组式（3-7），即可求得位势变量的一组值，根据式（3-6）结合方程组（3-7），推出计算非基变量xij检验数的公式σij=cij-（ui+vj）（3-8）在式（3-7）中，令u1=0，则可解得v1=90，v3=100，u2=-25，v2=90，于是σ12=c12-（u1+v2）=70-（0+90）=-20σ21=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。位势法计算非基变量xij检验数的公式σij=cij-（ui+vj）（3-8）ij=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）（3-6）闭回路法计算非基变量xij检验数的公式：复习比较检验数计算的两种方法思考：试解释位势变量的含义（提示：写出运输问题的对偶问题）四、方案调整当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。若检验数σij小于零，则首先在作业表上以xij为起始变量作出闭回路，并求出调整量ε：ijε=min{该闭回路中奇数次顶点调运量xij}调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450100100100150++--继续上例，因σ12=-20，画出以x12为起始变量的闭回路计算调整量：ε=Min（100，150）=100。按照下面的方法调整调运量：闭回路上，奇数次顶点的调运量减去ε，偶数次顶点（包括起始顶点）的调运量加上ε；闭回路之外的变量调运量不变。得到新的调运方案：调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量10015020045010010020050重复上面的步骤，直至求出最优调运方案：调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量1001502004501505020050结果最优调运方案是：x11=50，x12=150，x21=50，x23=200相应的最小总运输量为：Zmin=90×50+70×150+80×50+75×200=34000（吨公里）运输问题的计算机求解——表上作业法1、适用软件Transportation/TransshipmentProblem（TRP）2、输入数据：Maximize1minimize22Numberofsources?2Numberofdestinations?3Numberoftransshipmentpoint?0Usethedefaultnames(S1…Sn,D1…Dn,T1…Tn)YPresstheSpaceBartocontinueifyourentriesarecorrectCapacitiesofSourcesS1:200S2:250DemandsofdestinationsD1:100D2:150D3:200ENTERTHECost/ProfitCoefficientsoftheTRPModel-----Minimization------Fro