运输问题表上作业法ppt课件

7.4表作业法，一、表作业法反复步骤1 .在某规则中找到初始基的可行解2 .对当前解进行最优性的判断，即求出各非基底变量的检验常数，判别是否达到最佳解，如果达到最佳解则停止计算，如果不是最佳解则进入下一步骤3 .表中改善初始方案，生成新基的1、图1的运输问题的解决构想图，2，2，初期的基本可能解的确定，例2 :甲、乙两个煤矿供给a、b、c三个城市用煤，如表示各煤矿的产量和各城市的必要煤量，从各煤矿到各城市的运输单价那样，求出了使总运输费用最小化的运输方案。 3、有关例题的信息表、4、例题数学模型、5、(1)最小要素法：从运费价格最小的格中可取得格内标签的最大数量。 然后按运费从小到大的顺序计算。 如果满足某行(列)的产量(销售量)，则删除该行(列)的其他格式。 这样，进行到基本上得到可行的解为止。 用6，最小元素法确定初期运输方案，150，100，100，100，7，x11=100，x13=100，x22=150，x 23=100，8， (2)西北方法优先满足运输表中西北角(左上角)不优先考虑具有最小单位运价的销售业务的空间供给要求，用9，西北方法确定初期运输方案，100，100，50，50，200，200，10，x11=100，x22=50 x23=200，11，3，得到最优性检验，用最小要素法或西北方法求运输问题的初期基本可行解后，根据表作业法的第二阶段，判别该解的最优性，看它是否为本运输问题的最佳解。 12，1，闭环法，想法：判定运动问题的初期基可执行解是否为最佳解，按照一般简单形式法，验证该解的各非基变量(与运动表中的空间对应)的检验常数。 检验数：运输问题的非基本变量(对应于空间)检验数定义为通过在空间中增加单位运输量而增加总成本的量。 如果某个空间(Ai，Bj )的检测数为负的话，由于将Xij作为基础变量表示运用费用会减少，所以现在这个解不是最佳解。 如果所有空间的检测数均为非负，无论如何变换都不能降低运输费用，也就是说不能改善目标函数值，这个解是最佳解。 13、闭合回路：在给定运输方案的运输表中，从一个空间(非基本变量)开始，沿水平或垂直方向前进，只要碰到代表基本变量的数字单元就可以向左或向右前进90次，最终返回到初始空间中形成的一个回路。 在所有空间中，一定能找到一个闭环，只有一个闭环。 以14、xij空间为最初的奇数顶点，向闭合电路的顺序(或相反)的顺时针方向前进，对闭合电路上的各点依次赋予编号的非基变量xij的检测常数：现在，在用最小要素法决定例2的初始调运方案的基础上，非基变量X12的检测常数：15 : 初始调运方案中，以X12(X21 )为起点的闭合回路、16、非基变量X12的检测常数：非基变量X21的检测常数：=(c 12 c 23 )-(c 13 c 22 )=70-(10065 )=-20、=(c 21 c 13 )-(c 11 c 23 )=80-(9075 )=15。 经济意义：在保持生产销售平衡的条件下，该非基变量是将单位运输量增加1作为基变量时目标函数值的变化量。 17、2、双对变量法(电势法)、检验公式：分别表示与表示与前m个约束方程式对应的双对变量的后n个约束公式对应的双对变量。18、初始调运方案对偶变量对应表、19、以初始调运方案为例设置对偶变量和，构建以下方程式：20、式中u1=0时，v1=90、v3=100、u2=-25、v2=90，因此12=c 12-(u1v2)=70-(090 )=-2021=c 21-.21、方程特征：方程的个数为m n-1=2 3-1=4个，对偶变量为m n=2 3=5. 初始方案中的每一基变量xij等于方程-对应于一行与一列的对称变量之和对应于基变量的运输距离(或运输价格):ui vj=cij； 方程式中正好有自由变量，可以证明方程式中的任何变量都可以作为自由变量取出。 此时方程的解可以称为势。 在、22、式中，若设u1=0，则可以解释为v1=90、v3=100、u2=-25、v2=90，因此12=c 12-(u1v2)=70-(090 )=-2021=c 21-(u2v1)=80-(-25 )=15与先前用闭合电路法求出结果相同. 复习、23、势法计算非基变量xij检验常数的公式ij=cij-(ui vj )，复习比较检验常数计算的两种方法，尝试说明势变量的含义(提示：写运动问题的对偶问题)、24、4、解的改善、初始解不是最佳解，即某非基变量检验常数为根据表作业法的第三阶段，有必要改善初期方案。 25、(1)解改善的顺序是：1.(在具有多个非基变量的检查数为负的情况下，与具有最小负检查数的空间对应的变量)作为代入变量，找出运输表中的闭环2 .将该空间作为最初的奇数的顶点，按闭环的顺序(或相反)前进，对闭环上的各拐点依次编号解的改善步骤：3 .在闭合回路的所有偶数点中，找出运输量最小的点，将该格的变量作为换算变量4 .将闭合回路上所有奇数点的运输量增加该换算变量的值，从所有偶数点的运输量中减去该数值，最终提出新的运输方案对得到的新方案进行最优性检查，如果不是最优解，重复以上步骤继续调整直到得到最优解。 另外，因为27，12=-20，所以画出以x12为开始变量的闭环，计算0、200、50、100、28、调整量：=min(100、150)=100。 用以下方法调整调整量。 在闭合回路中，奇数次顶点的调整量加上，偶数次顶点的调整量减去。闭合回路以外的变量的运算量不变。 得到新运输方案：29，重复求出最佳运输方案的步骤：30，31，结果最佳运输方案相当于x1=50，x12=150，x21=50，x23=200的最小总运输费用为zmin=90507015075200=34000，32，授课练习：33，5，什么通常，将与中最小者对应变量作为代入变量(2)重复运输问题的最佳解时，在某个非基变量的检验常数等于0的情况下，说明在该运输问题中存在多重最佳解，34、(3)运输问题的产地的