运输问题表上作业法.ppt

《运输问题表上作业法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§7.4表上作业法一、表上作业法迭代步骤1．按某种规则找出一个初始基可行解；2．对现行解作最优性判断，即求各非基变量的检验数，判别是否达到最优解，如已是最优解，则停止计算，如不是最优解，则进行下一步骤；3．在表上对初始方案进行改进，找出新的基可行解，再按第二步进行判别，直至找出最优解。确定初始方案(初始基本可行解)改进调整（换基迭代）否判定是否最优？是结束最优方案图1运输问题求解思路图二、初始基本可行解的确定例2：甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输单价见表所示，求使总运输费用最少的调运方案。例题有关信息表450200150100日销量（需

2、求量）250756580乙2001007090甲日产量（供应量）CBA运距城市煤矿例题数学模型（1）最小元素法：从运价最小的格开始，在格内的标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用最小元素法确定初始调运方案150100100100100100100得到初始调运方案为：x11=100，x13=100，x22=150，x23=100（2）西北角法不

3、是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销要求调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用西北角法确定初始调运方案1001001005050200200得到初始调运方案为：x11=100，x12=100，x22=50，x23=200三、最优性检验根据最小元素法或西北角法求得运输问题的初始基可行解之后，按照表上作业法的第二步，下面需对这个解进行最优性判别，看它是否为本运输问题的最优解.１、闭回路法思路：要判定运输问题的初始基可行解是否为最优解，可仿照一般

4、单纯形法，检验这个解的各非基变量（对应于运输表中的空格）的检验数。检验数：运输问题中非基变量（对应于空格）的检验数定义为给某空格增加单位运量导致总费用的增加量。如果有某空格（Ａi、Bj）的检验数为负，说明将Xij变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全为非负，则不管怎样变换，均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。闭回路：在给出的调运方案的运输表上，从一个空格（非基变量）出发，沿水平或垂直方向前进，只有碰到代表基变量的数字格才能向左或向右转90°继续前进，直至最终回到初始空格而形成的一条回路。从每一空格出发，一定可以找到一条且只存在唯一

5、一条闭回路。以xij空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号；非基变量xij的检验数：现在，在用最小元素法确定例2初始调运方案的基础上，计算非基变量X12的检验数：=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450100100100150初始调运方案中以X12(X21)为起点的闭回路非基变量X12的检验数：非基变量X21的检验数：=（c12+c23）-（c13+c22）=70+75-（

6、100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。2、对偶变量法（位势法）检验数公式：分别表示前m个约束等式对应的对偶变量；分别表示后n个约束等式对应的对偶变量。初始调运方案对偶变量对应表调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450对偶变量vjv1v2v3100100100150对偶变量uiu1u2以初始调运方案为例，设置对偶变量和，然后构造下面的方程组

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与前面用闭回路法求得的结果相同。方程组的特点：方程个数是m+n-1=2+3-1=4个，对偶变量共有m+n=2+3=5。初始方案的每一个基变量xij对应一个方程——-—所在行和列对应的对偶变量之和等于该基变