运输问题表上作业法2

运输问题的表上作业法1、单纯形法（为什麽？）2、表上作业法

由于问题的特殊形式而采用的更简洁、更方便的方法一、表上作业法的基本思想

先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图3-1所示。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。

确定初始方案(初始基本可行解)

改进调整（换基迭代）否

判定是否最优？是结束最优方案图1运输问题求解思路图

二、初始方案的确定

1、作业表（产销平衡表）

初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。

表2是两个产地、三个销地的运输问题作业表。调销地运量产地

B1B2B3

产量A1c11

X11c12

X12

c13

X13a1

A2c21

X21c22

X22c23

X23a2

销量

b1b2b3表2运输问题作业表（产销平衡表）

其中xij是决策变量，表示待确定的从第i个产地到第j个销地的调运量，cij为从第i个产地到第j个销地的单位运价。2、确定初始方案的步骤：（1）选择一个xij，令xij=min{ai，bj}=将具体数值填入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

乙200100

7090

甲

日产量（供应量）CBA运距城市煤矿例3-2的数学模模型分别使用用最小元元素法和和西北角角法求出出初始方方案。&最小元素素法的基基本思想想是“就就近供应应”；；&西北角法法则不考考虑运距距（或运运价），，每次都都选剩余余表格的的左上角角（即西西北角））元素作作为基变变量，其其它过程程与最小小元素法法相同；；调销地运量产地

B1B2B3

产量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

销量

100

150

200

450用最小元元素法确确定例3-2初始调运运方案150100100100100100100得到初始始调运方方案为：：x11=100，x13=100，x22=150，x23=100最小元素素法实施施步骤口口诀《运价表》上找最小小，《平衡表》上定产销销；满足销量量划去““列”，，修改““行产””要记牢牢；（满足产产量划去去“行””，修改改“列销销”要记记牢）划去列(行)对《运价》，修改“行行产(列销)”在《产销》；余表再来来找最小小，方案案很快就就找到。。调销地运量产地

B1B2B3

产量A190

X1170

X12

100

X13200

A280

X21

65

X2275

X23250

销量

100

150

200

450用西北角角法确定定例3-2初始调运运方案1001001005050200200得到初始始调运方方案为：：x11=100，x12=100，x22=50，x23=200三、最优优性检验验检查当前前调运方方案是不不是最优优方案的的过程就就是最优优性检验验。检查的方方法：计算非基基变量（未填上上数值的的格，即即空格））的检验数数（也称为为空格的检检验数），若全全部大于于等于零零，则该该方案就就是最优优调运方方案，否否则就应应进行调调整。定义

凡是能排成

(3-4)或(3-5)形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中互不相同,互不相同。1、闭回路路法X11

X13

X21

X24

X33

B1

B2

B3

B4

A1

X12

X14

A2

X22

X23

A3X31

X32

X34例

设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路在表中的表示法——用折线连接起来的顶点变量。练习

请给出闭回路和在表中的表示法。X11

X13

X21

X24

X33

B1

B2

B3

B4

A1

X12

X14

A2

X22

X23

A3X31

X32

X34练习下面的折折线构成成的封闭闭曲线连连接的顶顶点变量量哪些不不可能是是闭回路路？为什什麽？（a）（b）（c）（d）（e）表中的折折线构成成一条封封闭曲线线，且所所有的边边都是水平或垂直的；表中的每一行和每一列由折线相相连的闭闭回路的的顶点只有两个个；有关闭回回路的一一些重要要结果定理1

设是一个闭回路，则该闭回路中的变量所对应的系数列向量具有下面的关系：注意：列向量Pij=(0,…,0,1,0,……,0,1,0,…0)T中两个元元素1分别处于于第i行和第m+j行，直接接计算即即可得到到结果。。定理的证证明可借助定理理3-1和高等代代数中““向量组组中，若若部分向量量线性相相关，则则整个向向量组就就线性相相关”的定理理得到。。定理2

若变量组中有一个部分组构成闭回路，则该变量组对应的系数列向量线性相关。约定作为为起始顶顶点的非非基变量量为偶数数次顶点点，其它它顶点从从1开始顺次次排列，，那么，，该非基基变量xij的检验数数：现在，在在用最小元元素法确确定例3-2初始调运运方案的的基础上上，计算非基基变量X12的检验数数：=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）（3-6）闭回路法法以确定了了初始调调运方案案的作业业表为基基础，以以一个非非基变量量作为起起始顶点点，寻求求闭回路路。该闭回路路的特点点是：除了起始始顶点是是非基变变量外，，其他顶顶点均为为基变量量（对应应着填上上数值的的格）。。可以证明明，如果对闭闭回路的的方向不不加区别别，对于于每一个个非基变变量而言言，以其其为起点点的闭回回路存在且唯唯一。调销地运量产地

B1B2B3

产量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

销量

100

150

200

450100100100150例3-2初始调运运方案中中以X12(X21)为起点的的闭回路路非基变量量X12的检验数数：非基变量量X21的检验数数：

=（c12+c23）-（c13+c22）

=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。经济含义义：在保持持产销平平衡的条条件下，，该非基基变量增增加一个个单位运运量而成成为基变变量时目标函数数值的变变化量。2、位势法法

以例3-2初始调运方案为例，设置位势变量和，在初始调运方案表的基础上增加一行和一列（见下页表格）。然后构造下面的方程组：（3-7）例3-2初始调运运方案位位势变量量对应表表调销地运量产地

B1B2B3产量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

销量

100

150

200

450位势变量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）=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）（3-6）闭回路法计算非基变量xij检验数的公式：复习比较较检验数数计算的的两种方方法思考：试试解释位位势变量量的含义义（提示示：写出出运输问问题的对对偶问题题）四、方案案调整当至少有有一个非基变量量的检验验数是负值时，说明明作业表表上当前前的调运运方案不不是最优优的，应应进行调调整。若检验数数σij小于零，则首先先在作业业表上以xij为起始变变量作出出闭回路路，并求出调整整量ε：ijε=min{该闭回路中奇数次顶点调运量xij}调销地运量产地

B1B2B3

产量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

销量

100

150

200

450100100100150++--继续上例例，因σ12=-20，画出以以x12为起始变变量的闭闭回路计算调整整量：ε=Min（100，150）=100。按照下面面的方法法调整调调运量：：闭回路上上，奇数次顶顶点的调运量减去ε，偶数次顶顶点（包括起起始顶点点）的调调运量加上ε；闭回路路之外的的变量调调运量不不变。得到新的的调运方方案：调销地运量产地

B1B2B3

产量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

销量

100

150

200

450100100200

50重复上面面的步骤骤，直至至求出最最优调运运方案：：调销地运量产地

B1B2B3

产量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

销量

100

150

200

450150

50200

50结果果最优调运运方案是是：x11=50，x12=150，x21=50，x23=200相应的最最小总运运输量为为：Zmin=90××50+70××150+80×50+75×200=34000（吨公里里）运输问题题的计算算机求解解——表上作业业法1、适用软软件Transportation/TransshipmentProblem（TRP）2、输入数数据：Maximize1minimize2<2>Numberofsources?<2>Numberofdestinations?<3>Numberoftransshipmentpoint?<0>Usethedefaultnames(S1…Sn,D1…Dn,T1…Tn)<Y>PresstheSpaceBartocontinueifyourentriesarecorrectCapacitiesofSourcesS1:200S2:250DemandsofdestinationsD1:100D2:150D3:200ENTERTHECost/ProfitCoefficientsoftheTRPModelMinimizationFromToS1D1:90D2:70D3:100S2D1:80D2:65D3:80(注意：该该例的输输入数据据与前例例不同)3、计算过过程中的的初始表表Initialsolutionby000V(j)+200

+150

+100Demands0+250

+80

+200

+65

+80

+50S20

+200

+100

+70+150

90

+50S1U(I)SuppliesD3D2D1SN\DN4、求解结结果报告告SummaryofResultsforTR2Page:1FromToShipment@costOpp.ct.FromToShi