本章重点第三章 运输问题产销平衡运输问题的数学模型产销平衡运输问题的表上作业法 本章内容运输问题的数学模型表上作业法运输问题的扩展1 运输问题的数学模型bnb2b1需求量BnB2B1 需方 供方AmA2A1ama2a1供应量供需平衡运价1 运输问题的数学模型bnb2b1需求量BnB2B1 需方 供方AmA2A1ama2a1供应量cmncm2cm1c2nc22c21c1nc12c11如何建立供需搭配，使总的运输费用最小？供 需 平 衡 表数学模型 设从Ai到Bj的物资运量为xij ，产销平衡运输问题的数学模型。Ai的产品全部 供应出去Bj的需求全 部得到满足mn平衡表、运价表和二为一：约束条件或解可用产销平衡表表示:uivj无约束 （i=1,2, ,m;j=1,2, ,n)uivj设ui,vj为对偶变量，对偶问题模型为m个n个2 表上作业法计算步骤： (1) 找出初始调运方案。即在(mn)产销平衡表上 给出m+n-1个数字格。(最小元素法或差值法）(2) 求检验数。（闭回路法或位势法） 判别是否 达到最优解。如已是最优解，则停止计算，否则 转到下一步。(3) 对方案进行改善，找出新的调运方案。（表上 闭回路法调整）确定m+n-1个基变量(4) 重复（2）、（3），直到求得最优调运方案。空格例 运输问题供需平衡表和运价表如下，求最优调 运方案。供需B1B2B3B4供应量 （T）A13113107A219284A3741059需求量（T ）3656最小元素法314633Z=43+310+31+12+64+35=86该方案总运费：. 差额法分别计算各行、各列次小、最小运价的差额， 优先在最大差额处进行供需搭配。步骤： 10 计算未划去行、列的差额； 20 找出最大差额对应的最小元素cij进行供需分配；30 在未被划去的行、列重新计算差额。销销 产产B1B2B3B4供量A17A24 A39销销量 36566B1B2B3B4行差额额 A13113100 A219281A3741051 列差额额2513销销 产产B1B2B3B4供量A17A24 A3 9销销量 36566B1B2B3B4行差额额 A13113100 A219281A3741052 列差额额2133销销 产产B1B2B3B4供量A17A24 A3 9销销量 36566B1B2B3B4行差额额 A13113100 A219281A374105 列差额额21233销销 产产B1B2B3B4供量A17A24 A3 39销销量 36566B1B2B3B4差额额 A13113107 A219286A374105 差额额1235122.1 最优解的判别 （检验数的求法） 闭回路法闭回路：从空格出发顺时针(或逆时针)画水(或垂 直)直线，遇到填有运量的方格可转90，然后继续前 进，直到到达出发的空格所形成的闭合回路。 调运方案的任意空格存在唯一闭回路。销销 产产B1B2B3B4供量A1 5 27 A23 14A3 6 39 销销量 3656差额法方案2.1 最优解的判别 （检验数的求法） 闭回路法闭回路：从空格出发顺时针(或逆时针)画水平(或 垂直)直线，遇到填有运量的方格可转90，然后继续前 进，直到到达出发的空格所形成的闭合回路。 调运方案的任意空格存在唯一闭回路。销销 产产B1B2B3B4供量A1 5 27 A23 14 A3 6 39 销销量 3656314633最小元素法+-+-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检验数得m+n-1个方程，令某个ui ( 或vj)=0，可解出 m+n个ui 和vj；由此得非基变量的检验数。对偶变量值等于原问题 的检验数松弛变量314633位势法令v1=0, 由c21=3= u2 +v1，得 u2=3011201128-37位势表2989-3-2检验数01128-37检验数表121-1101224=-10，当前方案 不是最优方案。21闭回路调整法改进方案pqijj , i)(min = 0xpq为换入变量从(p,q)空格开始画闭回路，其它转角点都是 填有运量的方格，并从(p,q)空格开始给闭回路上 的点按+1，-1，+1，-1编号，-1格的最小运量为 调整量。换出变量运量新的调运方案为：得到的一个解需 供B1B2B3B4uiA10210A2218A39125Vj -7-1-70713491110231085对应上述解的非基变量检验数例题销地 产地B1 B2 B3 B4产量A1 A2 A32 9 10 7 1 3 4 2 8 4 2 59 5 7 销量3 8 4 6参见黑板销地 产地B1 B2 B3 B4产量A1 A2 A31. 7 8 1 4 2 6 5 3 1 4 2 73 5 8销量2 1 7 6练习