运筹学-表上作业法.ppt

1、运输故障排除表操作法，运输故障排除表操作法，1 .运输问题模型及其解法，2 .解决初始基本可行性，3 .最优化检查，4 .方案曹征，1。运输问题模型和解决方法，运输问题：将特定商品从多个产地运到多个销售地点的研究目标：1，总运费最小值，1。运输问题模型和解决方案构想，据悉M个产地ai(i=1，2，M)可以供应某种物资，其供应(产量)分别为Ai，N个销售地bj(如果代表从Ai产地到Bj第二个销售地的运输量，则生产销售平衡条件)运输问题模型及其解决方法，1 1，1，1，1，1，1。运输问题模型和解决思路，系数矩阵，2，1。运输问题模型和解决思路，生产和营销平衡运输问题的情况下，如果原产地为m，销售

2、地为n，则变量数为Mn，约束数为m n，生产总销售库线性无关约束数为m n，运输问题解决事故表工作法由于运输计划系数矩阵的特殊性，如果直接使用线性规划单纯形法解决计算，则不能利用这些有利条件。人们在运输计划系数矩阵特性分析的基础上，建立了运输问题的表工作方法。1 .运输问题模型及解决思路、表工作法是简单法解决生产平衡运输问题时的简化方法，其本质仍是简单法，但区别只是用于完成各个阶段的具体形式。具体操作步骤如下：(1)确定初始默认可行解决方案。也就是说，在Mn茶叶生产和营销台车对照表中提供了m n-1数字单元(默认变量)。(2)计算每个非基本变量(空格)的检查数，即表中的空格检查数。判别表达式是

3、否达到了最佳解。如果是最佳解决方案，则停止计算；否则，继续下一步。(3)确定变更变量和变更变量，以找到新的默认可执行解决方案。(4)重复(2)、(3)，直到获得最佳解决方案。1 .运输问题模型和解决思路，2 .确定初始基本可行的解决方案，1)最小元素方法，基本思路：根据最近供应、最小运费优先级发运原则确定初始方案，即从单位运算表中选择最小运费，以确定运输关系，小于下一个。如果某一行(列)的产量(销售)牙齿已经满足，就划该行(列)的另一栏。这样进行，直到初步基础实现。例如，某公司有A、B、C三家茄子生产工厂，有A、B、C、丁四家茄子销售店。公司每天将三家工厂生产的产品运输到四家销售点，各工厂到各

4、销售点的距离不同，单位产品的运费也不同。每个工厂的日产量、每个销售点的日产量、每个工厂到每个销售点的单位产品的运费如下表所示。询问牙齿公司如何运输商品，在满足各卖点要求的前提下，将总运费降至最低。2 .确定初始基本可行解决方案，、s.t、2。确定初始基本可行解决方案，从第I产地到第j产地的运输量(I=1，2，3)；J=1，2，3，4)，3，4，3，1，6，3，2。确定初始基本可行解决方案，z=43 310 31 12 64 35 2。使用最小元素方法时，如果基本变量的数量还不足两个或更多，但只剩下一行或一列，则不能空格划掉剩馀的行或列，必须在剩馀的空格中中标为零。(大卫亚设，美国电视电视剧)(

5、退化的基本可行解决方案)，2 .确定初始基本可行解决方案，注意：3，5，3，0，6，3，2。早期基本可行的解决方案决策)，也就是说，沃格尔法的基本思路差异越大，成本增加就越大。因此，对于差额最大的地方，优先采用最低运费运输。步骤：分别计算表格中每个资料列与栏位的最小与次要小运费成本差异，并植入表格最右侧栏位与最下方资料列。选择行与列之间的最大差异，选择该行或列中最小的元素，然后根据与最小元素方法类似的优先级划分该行或列。重复操作，直到表中未绘制的元素、所有行和列都绘制完毕为止。2 .确定初始基本可行解决方案，2 .确定初始基本可行解决方案，0，1，1，2，5，1，3，2。确定初始基本可行解决方

6、案，2 .确定初始基本可行解决方案在运输问题中，目标函数值要求最小，因此，当所有检查数大于或等于0时，牙齿运输方案是最佳解决方案。否则，情况并非如此。计算检查数的两种茄子方法为：1，闭合回路方法闭合回路：如果基本解决方案从给定运输表中的非基本变量水平或垂直方向前进，则必须撞击基本变量才能继续向右或向左前进90o(当然不需要改变方向)。这样继续下去，可以回到总是出发的那个非标准变量，牙齿路线形成的闭合曲线称为闭合环。3 .最佳测试，3 .允许最佳测试、11=1、x311会变更总运费：75 103 2-110。31=10，3。最佳测试，最佳标准：所有检查数ij 0，2，位法闭环方法的缺点：变量数大

7、时，找到闭环并进行计算容易出错。位元方法检查阶段：1)山地Ai的位元量为ui，针脚Bj的位元量为VJ。2)通过ij=Cij-(Ui Vj)将ij=0用于基础变量，计算潜在Ui，Vj，即Cij-(Ui Vj)=0，u1=0。3)通过ij=Cij-(Ui Vj)计算非默认变量的检查数ij，3。最佳检查，u1、U2、u3、v1、v2、v3、v4、0、1 12=c12-(u1 v2)=11-(0 9)=2，(1最佳检查，3 .最佳检查，33=12，11，3。最优化检查，1，计算闭合回路方法：ij=(闭合回路中奇数顶点运费的总和)-(闭合回路中偶数顶点运费的总和)2，计算位方法：ij=cij-ui VJ

8、，如果存在非基本变量，则为4。方案曹征，闭环曹征方法步骤：1，确定输入基准变量：如果选择负检查数中最小的rk，则xrk将用作输入基准变量。(尽快减少总运费)2，确定基本变量：在主变量xrk的闭合循环中选择偶数顶点，提高运输量最小的值，并将该运输量作为主变量。(正好有一个基本变量，其他基本变量为正数)，4 .模式曹征，即=Minxij求出闭环偶数顶点的xij=xpq。然后确定xpq为基本变量，调整量。3，基本变更曹征：封闭回路的奇数顶点交通量曹征：xij，每个偶数顶点交通量曹征：xij-，特殊xpq-=0，xpq成为非基本变数。重复以上步骤，直到所有检查的数目均为负数，以获得最佳解决方案。4 .方案曹征，最小检查数原则，基本变量确定，最小偶数原则，基本变量和调整量确定，1，-1，1，-1，-1，-4，方案曹征，获得新的基本变量：x13=5，x重新计算检查数，(1)，(2)，(2)，(1)，(9)，(12)，4，方案曹征，一次基本转换后的所有ij 0，最佳解决方案：X13=5最佳值：无限最优解最优方案中的空格(非最优变量)检验数为零，则该运输问题应存在多个最优解。2.退回、解、解、运问题最优化表中，如果水格(基本变量)运输量为零，则退化。1)如果需要绘制基本可行解决方案中的一行和一列，则需要在填充单元格数的行或列中写0栏。2)在封闭回路中调整时