3.2 表上作业法.pptVIP

(1) 给出初始调运方案。——初始基可行解： 即在有(m×n)个空格的产销平衡表上给出 (m+n-1)个数字格。 一般用最小元素法，Vogel法，西北角法; (2) 求各非基变量的检验数， 即在表上计算空格的检验数。 从而判断检验方案是否达到最优, 若是最优解,则停止计算; 否则转下一步。 用闭回路法、位势法求检验数； (3) 调整调运方案，得新的方案。 ——即改进当前的基本可行解 (确定入基和出基变量)， 找出新的基可行解。 在表上用闭回路调整法； (4) 重复(2),(3)直到求出最优方案。 用最小元素法给出的初始解是运输问题的基可行解，其理由为： 最小元素法中的退化情况 第一次划去第1列B1，第二次最小运价为2，对应的销地B2销量和产地A3的产量未分配量皆为6，故同时划去B2列和A3行。非零的数字格小于(m+n-1)个。 出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为数字格。 基本思想： 一产地的产品假如不能按最小运费就近供应， 就应考虑次小运费。 这就有一个差额， 差额越大，说明不能按最小运费调运时，运费 增加越多。 因而对差额最大处，就应当采用最小运费调运。 由以上可见： 伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。 伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。 最优性检验的判别方法: 表格中有调运量的地方（数字格）为基变量， 空格处为非基变 量。 基变量的检验数σij＝0， 非基变量 (空格)的检验数 cij – CB B-1 Pij。 因运输问题的目标函数是要求实现最小化， 故当所有的 cij – CB B-1 Pij≥0时，为最优解。 用闭回路法求检验数时， 需给每一空格找一条闭回路。 当产销点很多时，这种计算很繁。 下面介绍较为简便的方法——位势法。 位势法的原理 共有m+n?1个基变量xij ， 因此可得m+n?1个等式 ui +vj=cij 而一共有m+n个 ui 和 vj ， 但可令任一个ui 或 vj =0， 从而解出其它 m+n?1个的值，这就是位势法. 若对所有非基变量有 cij ? zij ≥ 0，即 ui + vj ?cij， 表明当前ui 和 vj 是对偶问题的可行解， 当前m+n?1个基变量xij 是原问题最优解， 否则,从 cij ? zij 0 中找最小者，对应xij 就是入基变量。 当表中空格处出现负检验数时， 表明当前平衡表给出的调运方案不是最优的， 需调整调运量，改进原调运方案，使总运费减少。 改进原理同单纯形法一样。 调整方法： 1. 确定进基变量。 为使方案有较大的改进， 先确定非基变量（空格）中最小的检验数， 即min{σij | σij 0}=σLK , 则x LK 入基; 注意： 多个空格（非基变量）的检验数为负， 任一个都可作为进基变量。 一般选σij0中最小的负检验数所对应变量作为换入变量， 目的是使运费尽可能的减少。 2. 确定出基变量。 在进基变量x LK 的闭回路中，取偶点的最小 运量为调整量θ），θ对应的变量为出基变量； 3.调整调运量. 在进基变量x LK 的闭回路中， 奇点对应的变量加上调整量θ， 偶点对应的变量减去调整量θ， 其余变量不变，得到一组新的可行解 然后求此时所有非基变量的检验数重新检验 （b）闭回路调整中： 闭回路中，在需要减少运量的地方，基变量同时有多个达到最小, 调整后原先空格处填上这个最小数，而有多个 原基变量变为 0，就要把其中之一变为空格. 原则是选运费最大者变为空格，即为出基变量， 其余均保留在新的基解中，即均补添0，并看 作数字格，使数字格数=m+n-1 练习 ： 1、用表上作业法求出最优解。 这是一个产销平衡的问题 3)调整调运方案，得新的方案。 以(22)格为调入格，以此格为出发点，作一闭回路。经检验，所有检验数都大于0，该调运方案是最优的方案。总运费为395元。 σ11=c11-c12+c22-c21=c22-3≥0 σ13=c13-c23+c22-c21=c22+10 ≥0 σ24=c24-c22+c21-c14=10-c22 ≥0 σ32=c32-c31+c21-c22=24-c22 ≥0 σ34=c34-c31+c21-c22+c12-c14