6运输问题.ppt

最优化理论与算法 §6， 运输问题 帅天平 北京邮电大学数学系 Email:tpshuai@, Tel Rm:主楼814 * 1 运输问题的一般数学模型 有m个产地生产某种物资，有n个地区需要该类物资 令a1, a2, …, am表示各产地产量， b1, b2, …, bn表示各销地的销量，?ai=?bj 称为产销平衡 设xij表示产地 i 运往销地 j 的物资量，wij表示对应的单位运费，则我们有运输问题的数学模型如下： 运输问题有m?n个决策变量，m+n 个约束条件。由于产销平衡条件，只有m+n–1个相互独立，因此，运输问题的基变量只有m+n–1 个 * 1 运输问题的基本性质 定理5.1.1： 产销平衡的运输问题 必存在最优解。 定理5.1.2：运输问题的系数矩阵及其增广矩阵的秩均为m+n-1 定理5.1.3：运输问题的系数矩阵A中任何方子阵的行列式值为1，-1，或0 定理5.1.4：运输问题中的一组变量{xij}对应的列向量{pij}线性无关当且仅当{xij}不包含闭回路。 闭回路定义见后 * 1 运输问题的基本性质 定义5.1.1：上表中变量序列{xij}称为闭回路，若序列{xij}由互不相同的变量组成，且沿水平或垂直方向延伸，每个变量所在的行与列均恰好有该序列中二个变量（不在序列中变量除外）。 * 2 运输问题的求解方法 约束条件非常有规律，技术系数非 0 即 1 基变量的个数远小于决策变量的个数 采用表上作业法，称为位势法和踏石法 运算中涉及两个表：运费表和产销平衡表(分配表) * 2.1 寻找初始可行解的方法 1、西北角法 从 x11开始分配，从西北向东南方向逐个分配 xij 的分配公式 例3.2.1 * 例1 西北角法 * 2、最低费用法（最小元素法） 采用最小费用优先分配的原则，看一步 f(x)=121，比 西北角法低 84 * 3、运费差额法 采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分配的原则，看两步 f(x)=98，比 最低费用法 又低了23 * 2.2 利用位势法检验分配方案是否最优 不采用单纯型法，如何获得xij的检验数 找到原问题的基础可行解，保持互补松弛条件，求出对应对偶问题的解，若该对偶问题的解非可行，则原问题的解不是最优解；否则，达到最优解 * * 位势法的原理 为满足互补松弛条件，原问题中xij被选为基变量，即xij?0，则要求对偶问题中ui+vj=wij，即该行的松弛变量为0 共有m+n?1个基变量xij ，因此可得m+n?1个等式 ui+vj=wij m+n?1个等式只能解出 m+n?1个 ui 和 vj ，而一共有m+n个 ui 和 vj ，但可令任一个ui 或 vj =0，从而解出其它 m+n?1个的值；这就是位势法 令 zij= ui + vj ，其相当原问题xij的机会费用 若对所有非基变量有 zij ? wij ? 0，即 ui + vj ? wij，表明当前ui 和 vj 是对偶问题的可行解，由互补松弛定理可知当前m+n?1个基变量xij 是最优解，否则 从 zij ? wij 0 中找最大者，对应 xij 就是入变量 * 2.3 踏石法 1、找入变量 从 zij ? wij 0 中找最大者，对应 xij 就是入变量 2、以 xij 为起点，寻找由原基变量构成的闭合回路 该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回路中必有偶数个变量(包括 xij )，且回路中每行每列只有两个变量 3、求入变量 xi*j* 的最大值及新基变量的解 从 xij出发，沿任一个方向对回路拐角上的基变量依此标“?”和“+”，表示“?”和“+” xij ，从而迭代后仍满足分配的平衡 标有“?”的变量中最小者就是出变量xi*j* ，对应 xi*j*的值就是所求入变量 xij 的最大值 标有“?”的变量减去 xi*j*，标有“+”的变量加上 xi*j* 4、用位势法求新基变量的检验数 若所有 zij ? wij ? 0，则达到最优，算法停止；否则返回 1 * 例2 踏石法，以最低费用法所得初始解开始 答：最优解如上分配表，OBJ=98 OBJ=121 OBJ=101 * 3 运输问题迭代中的一些具体问题 3.3.1 闭合回路的画法 从入变量xij出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变量，则返回上一拐角，换一个方向走，采用深探法 闭合回路不一定是矩形 3.3.2 产销不平衡 供过于求，即 ?ai ?bj ，增加一个虚收点Dn+1，bn+1= ?ai - ?bj , 令 wi,n+1=0, i=1,2,…,m 供小于求，即