《运筹学：教案8_运输问题》由会员分享，可在线阅读，更多相关《运筹学：教案8_运输问题（32页珍藏版）》请在金锄头文库上搜索。
1、本本章章重重点点 产销平衡运输问题的数学模型产销平衡运输问题的数学模型 产销平衡运输问题的产销平衡运输问题的表上作业法表上作业法 本本章章内内容容运输问题的数学模型运输问题的数学模型表上作业法表上作业法运输问题的扩展运输问题的扩展1 1 运输问题的数学模型运输问题的数学模型bnb2b1需求量需求量BnB2B1 需方需方供方供方AmA2A1ama2a1供应量供应量供需平衡供需平衡运价运价1 1 运输问题的数学模型运输问题的数学模型bnb2b1需求量需求量BnB2B1 需方需方供方供方AmA2A1ama2a1供应量供应量cmncm2cm1c2nc22c21c1nc12c11如何建立供需搭配，使总的
2、运输费用最小？如何建立供需搭配，使总的运输费用最小？供供需需 平平衡衡表表平衡表、运价表和二为一：平衡表、运价表和二为一：数学模型数学模型设从设从Ai到到Bj的的物资运量为物资运量为xij ，产销平衡产销平衡运输问题的数学模型。运输问题的数学模型。Ai的产品全部的产品全部供应出去供应出去Bj的需求全的需求全部得到满足部得到满足mn约束条件或解可用产销平衡表表示约束条件或解可用产销平衡表表示: uivj无约束无约束 （i=1,2, ,m;j=1,2, ,n)uivj设设u ui i, ,v vj j为对偶变量，对偶问题模型为为对偶变量，对偶问题模型为m个个 n个个2 2 表上作业法表上作业法计算
3、步骤：计算步骤：(1) 找出初始调运方案找出初始调运方案。即在即在(mn)产销平衡表产销平衡表上给出上给出m+n- -1个数字格。个数字格。(最小元素法或差值法）最小元素法或差值法）(2) 求检验数。（闭回路法或位势法）求检验数。（闭回路法或位势法） 判别是否判别是否达到最优解。如已是最优解，则停止计算，否则达到最优解。如已是最优解，则停止计算，否则转到下一步。转到下一步。(3) 对方案进行改善，找出新的调运方案。（表上对方案进行改善，找出新的调运方案。（表上闭回路法调整）闭回路法调整）确定确定m+n-1个基变量个基变量 (4) (4) 重复（重复（2 2）、（）、（3 3），直到求得最优调运
4、方案。），直到求得最优调运方案。空格空格 例例 运输问题供需平衡表和运价表如下，求最优调运输问题供需平衡表和运价表如下，求最优调运方案。运方案。 供 需B1B2B3B4供应量（T）A13113107A219284A3741059需求量（T）3656最小元素法最小元素法314 633Z=43+310+31+12+64+35=86Z=43+310+31+12+64+35=86该方案总运费：该方案总运费：. 差额法差额法 分别计算各行、各列次小、最小运价的差额，分别计算各行、各列次小、最小运价的差额，优先在最大差额处进行供需搭配。优先在最大差额处进行供需搭配。步骤：步骤：10 计算未划去行、列的差额
5、；计算未划去行、列的差额； 20 找出最大差额对应的最小元素找出最大差额对应的最小元素cij进行供需分配；进行供需分配；30 在未被划去的行、列重新计算差额。在未被划去的行、列重新计算差额。 销销产产B1B2B3B4供量供量A17A24A39销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A3741051列差额列差额2513 销销产产B1B2B3B4供量供量A17A24A3 9销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A3741052列差额列差额213 3 销销产产B1B2B3B4供量供量A17A24A3 9销量销量 3
6、656 6B1B2B3B4行差额行差额A13113100A219281A374105列差额列差额212 3 3 销销产产B1B2B3B4供量供量A17A24A3 39销量销量 3656 6B1B2B3B4差额差额A13113107A219286A374105差额差额12 3 5 1 22.1 最优解的判别最优解的判别 （检验数的求法）（检验数的求法） 闭闭回路法回路法 闭回路：从空格出发顺时针闭回路：从空格出发顺时针(或逆时针或逆时针)画水画水(或或垂直垂直)直线，遇到填有运量的方格直线，遇到填有运量的方格可转可转90，然后继续，然后继续前进，直到到达出发的空格所形成的闭合回路。前进，直到到达
7、出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。调运方案的任意空格存在唯一闭回路。 销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656差差额额法法方方案案2.1 最优解的判别最优解的判别 （检验数的求法）（检验数的求法） 闭闭回路法回路法 闭回路：从空格出发顺时针闭回路：从空格出发顺时针(或逆时针或逆时针)画水平画水平(或或垂直垂直)直线，遇到填有运量的方格直线，遇到填有运量的方格可转可转90，然后继续前，然后继续前进，直到到达出发的空格所形成的闭合回路。进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。调运方案的任
8、意空格存在唯一闭回路。 销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656314 633最最小小元元素素法法+-+- x11为换入变量，为换入变量，x11增加增加1，运费的变化为，运费的变化为3- -1+2- -3=1。这个变化就是。这个变化就是x11的检验数，故的检验数，故 11=1 基变量的检验数为零基变量的检验数为零( 基变量基变量xij)， ij=cij-(ui+vj), ui,vj自由变量自由变量. 位势法位势法标准型运输问题的对偶问题是：标准型运输问题的对偶问题是： XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y检验数检验数
9、 得得m+n- -1个方程，令某个个方程，令某个ui ( 或或vj)=0，可解出可解出m+n个个ui 和和vj；由此得非基变量的检验数。由此得非基变量的检验数。对偶变量值等于原问题对偶变量值等于原问题的检验数的检验数松弛变量松弛变量314 633位位势势法法 令令v1=0, 由由c21=3= u2 +v1，得得 u2=3 0 1 1 2 0 1 1 28-3 7位位势势表表2989-3-2检验数检验数 0 1 1 28-3 7检检验验数数表表121-11012 24=-10，当前方案，当前方案 不是最优方案。不是最优方案。21闭回路调整法改进方案闭回路调整法改进方案pqijj , i)(min
10、 = = 0xpq为换入变量为换入变量 从从( (p,q)p,q)空格开始画闭回路，其它转角点都是空格开始画闭回路，其它转角点都是填有运量的方格，并从填有运量的方格，并从( (p,q)p,q)空格开始给闭回路上空格开始给闭回路上的点按的点按+1+1，-1-1，+1+1，-1-1编号，编号，-1-1格的最小运量格的最小运量为为调整量。调整量。换出换出变量变量运量运量 新的调运方案为：新的调运方案为：得到的一个解得到的一个解 需供B1B2B3B4uiA10210A2218A39125Vj -7-1-70713491110231085对应上述解的非基变量检验数对应上述解的非基变量检验数例题例题 销地产地B1 B2 B3 B4产量A1A2A32 9 10 7 1 3 4 28 4 2 5957销量3 8 4 6参见黑板参见黑板
