西安做网站,湖南企业网络推广平台,如何高效建设品牌网站?,科技成果转化网站建设文章目录 引言二、表上作业法2.3 改进的方法 —— 闭回路调整法2.4 表上作业法中的特殊情况#xff08;一#xff09;无穷多最优解#xff08;二#xff09;退化 三、产销不平衡的运输问题3.1 产量大于销量3.2 销量大于产量 写在最后 引言
接下来我们学习表上作业法的最后… 文章目录 引言二、表上作业法2.3 改进的方法 —— 闭回路调整法2.4 表上作业法中的特殊情况一无穷多最优解二退化 三、产销不平衡的运输问题3.1 产量大于销量3.2 销量大于产量 写在最后 引言
接下来我们学习表上作业法的最后一步改进以及表上作业法中一些特殊的情况还有关于产销不平衡问题的讨论。 二、表上作业法
表上作业法的求解工作在运输表上进行运输问题解的每一个分量都唯一对应其在运输表中的一个格子。它是一种迭代法迭代步骤为
先按某种规则找出一个初始解初始调运方案得出运输问题的一个基本可行解后就可将基变量的值 x i j x_{ij} xij 填入运输表相应的格子内并将这种格子称为填有数字格可以含 0 非基变量对应格不填称为空格。
接着对现有的解作最优性判别若不是最优解就在运输表上对其进行改进得出一个新解再判别再改进直至得到运输问题的最优解为止。
2.3 改进的方法 —— 闭回路调整法
闭回路调整法是改进当前基本可行解的方法当表中空格处出现负检验数时表明未得到最优解。
若有两个和两个以上的检验数一般选其中最小的以它对应的空格为调入格即以它对应的非基变量为换入变量。在以此非基变量为顶点的闭回路中选取偶数次顶点中最小的值对应的基变量为换出变量此基变量的值作为调整量。 可以类比单纯形法中换出变量的确定。 闭回路中奇数次顶点的值加上调整量偶数次顶点的值减去调整量得到新运输方案。
再次利用闭回路法或位势法求各空格的检验数若仍有负的检验数重复上述步骤直至所有检验数为非负。
2.4 表上作业法中的特殊情况
一无穷多最优解
产销平衡问题必存在最优解那么有唯一解还是有无穷多最优解依据线性规划单纯形法最优解判别标准即某个非基变量空格的检验数为 0 时该问题有无穷多最优解。
二退化
在单纯形法确定换出变量时有时存在两个或以上相同的最小比值 θ \theta θ 这样在下一次迭代中就有一个或多个基变量的取值为 0 出现退化解。
在运输问题中主要有以下两种情况
1当确定初始解的各供求关系时在 ( i , j ) (i,j) (i,j) 格填入数字后出现 A i A_i Ai 处的余量等于 B j B_j Bj 处的需量这时在产销平衡表上填一个数而在单位运价表上相应地要划去一行和一列。为了使得最后有 ( m n − 1 ) (mn-1) (mn−1) 个数字格需要添加一个 “0” 它的位置可能在对应同时划去的那一行或那一列的任一空格处。
2在用闭回路法调整时在闭回路偶数次顶点上出现两个和两个以上相等的最小值。这时只能选择一个作为调入格而经过调整后得到退化解。这时有一个数字格则必须填入一个 0 表明它是基变量。当出现退化解后可能在某闭回路偶数次顶点上有取值为 0 的数字格应取调整量为 0 。 三、产销不平衡的运输问题
之前所介绍了表上作业法是以产销平衡为前提的但是实际问题中产销往往是不平衡的因此需要把产销不平衡问题转化为产销平衡问题。
3.1 产量大于销量
总产量大于总销量时约束条件不再全是等式。关于销量仍需为等式但是关于产量的约束为 ≤ \leq ≤ 其数学模型如下 在前 m m m 个不等式中加入松弛变量则有 ∑ j 1 n x i j x i , n 1 a i ( i 1 , 2 , … , m ) \sum_{j1}^nx_{ij}x_{i,n1}a_i(i1,2,\dots,m) j1∑nxijxi,n1ai(i1,2,…,m) 接着虚拟一个销售地 B n 1 B_{n1} Bn1 其需求量为 b n 1 ∑ i 1 m a i − ∑ j 1 n b j b_{n1}\sum_{i1}^ma_i-\sum_{j1}^nb_j bn1i1∑mai−j1∑nbj 于是松弛变量 x i , n 1 x_{i,n1} xi,n1 可以看作是产地 A i A_i Ai 运往销售地 B n 1 B_{n1} Bn1 的物品数量相应的运费取 0 。这样一来就转化为了一个产销平衡的运输问题
3.2 销量大于产量
此时关于产量约束取不等式其数学模型如下 可假设一个虚拟产地 A m 1 A_{m1} Am1 其产量为总销量和总产量之差到各个销地的运费取 0 即可化为一个产销平衡的运输问题。
若求解后得到 x m 1 , j 0 x_{m1,j}0 xm1,j0 表明销售地 B j B_j Bj 需求满足若 x m 1 , j 0 x_{m1,j}0 xm1,j0 表明销售地 B j B_j Bj 需求未得到满足需要自行解决解决的数量为 x m 1 , j . x_{m1,j}. xm1,j.
有时候可能出现一个销售地的需求有好几部分比如最低需求是 a a a 最高需求是 b b b 等等。实际上可以将这个销售地看作两个地区第一个地区的需求为 a a a 第二个地区的需求为 b − a . b-a. b−a.
但此时虚拟产地到第一个地区的运费应设为 M M M无限大因为其约束方程为 ≥ \geq ≥ 。 写在最后
完完整整的表上作业法做下来可不轻松比较费时间重要的应该还是其思想以及和之前的单纯形法互通的地方。
