运输问题的表上作业法 1.ppt

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

1、第3章运输问题（TP）学习目标了解运输问题模型的特点。掌握产销平衡运输问题的表上作业法。学会产销不平衡运输问题的转化。学习表上作业法在物流管理中的典型应用。3运输问题（TP）2运输问题的模型3.1运输问题的表上作业法3.2产销不平衡的运输问题3.3运输问题的应用案例3.4运输问题的Excel处理3.53运输问题（TP）33.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法4利用表上作业法求解运输问题时，与单纯形法类似，首先要求出一个初始方案（即线性规划问题的初始基本可行解）。一般来讲这个方案不一定

2、是最优的，因此需要给出一个判别准则，并对初始方案进行调整、改进。每进行一次调整，我们就得到一个新的方案（基本可行解），而这个新方案一般比前一个方案要合理些，也就是对应的目标函数z值比前一个方案要小些。经过若干次调整，我们就得到一个使目标函数达到最小值的方案—最优方案（最优解），而这些过程都可在产销矩阵表（运输表）上进行，故称为表上作业法。其实质是单纯形法步骤描述方法第一步求初始基行可行解（初始调运方案）最小元素法、元素差额法、第二步求检验数并判断是否得到最优解当非基变量的检验数σij全都非负时得到最优解，若存

3、在检验数σij<0，说明还没有达到最优，转第三步。闭回路法和位势法第三步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步3.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法5例3.1设有3个产煤基地A1、A2、A3，4个销煤基地B1、B2、B3、B4，产地的产量、销地的销量以及从各产地至各销地煤炭的单位运价列于表3.4中，试求出使总运费最低的煤炭调拨方案。63.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法（1）列出运输问题的产销矩阵表。73.2运输问题

4、的表上作业法3.2.1产销平衡运输问题的表上作业法其中：xij为产地Ai到销地Bj的运量（i=1,2,3；j1,2,3,4），而将Ai到Bj的单位运价cij用小型字写在每格的右上角，以便直观地制定和修改调运方案。从表3.5的数据可知，例3.1是个满足产销平衡条件的产销平衡问题。（2）初始方案确定的方法—最小元素法。最小元素法：就近供应，运价数小的尽可能优先分配。83.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法93.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法这样，我们便得到

5、这样问题的一个初始基本可行x11=0x12=0x13=4x14=3x21=3x22=0x23=1x24=0x31=0x32=6x33=0x34=3它所对应的目标函数z值为z=3×0+11×0+3×4+10×3+1×3+9×0+2×1+8×0+7×0+4×6+10×0+5×3=86（万元）因此，在应用最小元素法确定初始方案时，必须注意以下两点。103.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法1.当选定最小元素（不妨假定为cst）后，如果发现该元素所在行的产地的产量as恰好等于它所在列的销地的

6、销量bt（即as=bt），可在产销矩阵表上xst处填上一个数as，并画上圈。为了保证调运方案中画圈的数字为m+n−1个，只能在s行的其他格子里都打上“×”（或在t列的其他格子里都打上“”），不可以同时把s行和t列的其他格子里都打上“×”。2.当最后只剩下一行（或一列）还存在没有填数和打“×”的格子时，规定只允许填数，不允许打“×”，其目的也是为了保证画圈数字的个数恰为m+n −1个。3.在特殊情况下可填“0”并画上圈，这个“0”应与其他画圈的数字同样看待。（不限于最后一行或最后一列）。113.2运输问题的表

7、上作业法3.2.1产销平衡运输问题的表上作业法例在表3.7中，第一步最小元素为c31=1，在x31处填上数字min(13,19)=13，并在x11、x21处打上“×”。123.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法3.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法13第二步的最小元素为c32=2，可在x32处填上数字min(6,6)=6，并在x12、x22处打上“×”（或在x33、x34处打上“×”），由上面的注意（1）可知，不能同时在x12、x22、x33、x34处都打上

8、“×”。继续运用前面所述的方法，再经过两步计算，可得到表3.8。143.2运输问题的表上作业法3.2.4确定初始方案的其他方法1.西北角法153.2运输问题的表上作业法3.2.4确定初始方案的其他方法2．沃格尔法单位销地运价产地产量311310719284741059销量36563.2运输问题的表上作业法16方法1：最小元素法基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后