第八节 运输问题.ppt

第八节 运输问题的表上作业法 一、运输问题的数学模型 系数矩阵 ? 1 1 1 0 0 0 ? ? 0 0 0 1 1 1 ? ? 1 0 0 1 0 0 ? ? 0 1 0 0 1 0 ? ? 0 0 1 0 0 1 ? 特点： 1、共有2+3=5行，表示2个产地和3个销地； 有2×3=6列，恰好对应6个变量； 2、每列只有两个1，其余为0，表示只有一个产地 和一个销地被使用； 设 为从产地 运往销地 的运输量， 得到下列一般运输问题的模型： 变化： 1）有时目标函数求最大，如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束； 3）产销不平衡时，可加入虚设的产地（产大于销时）或销地（销大于产时）。 求解思路 是 基本可行解 最优否 结束 否 换基 运输问题基变量的特点 * 运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。 * 运输问题的 可行解一定存在。 * 运输问题的最优解一定存在。 二、表上作业法 1、求初始方案： 1、初始基本可行解的确定： （1）西北角法：从西北角（左上角）格开始，在格 内的右下角标上允许取得的最大数。然后按行（列） 标下一格的数。若某行（列）的产量（销量）已满 足，则把该行（列）的其他格划去。如此进行下去， 直至得到一个基本可行解。 （2）最小元素法：从运价最小的格开始，在格内的 右下角标上允许取得的最大数。然后按运价从小到大 顺序填数。若某行（列）的产量（销量）已满足，则 把该行（列）的其他格划去。如此进行下去，直至得 到一个基本可行解。 从每一空格出发一定存在和可以找到唯一的闭回路。因(m+n-1)个数字格(基变量)对应的系数向量是一个基。任一空格(非基变量)对应的系数向量是这个基的线性组合。如Pij, i,j∈N可表示为 其中Pik,Plk,Pls,Pus,Puj∈B。而这些向量构成了闭回路。 用下述方法找检验数 Step 1：写出初始基解的运价； Step 2：利用“对角和相等”填空格，得新表； Step 3：老运价表-新运价表=检验数表 如上例的最小元素法所得初始解的检验数 （2）位势法： 根据单纯形法中检验数的定义，从约束条件中解出基变量，代入目标函数中，消去目标函数中的基变量，得到的非基变量的系数就是检验数。 位势：设对应基变量 xij 的 m + n - 1 个 i、j ，存在 ui , vj 满足 ui + vj = cij ，i = 1, … , m ; j = 1, … , n . 称这些 ui , vj 为该基本可行解对应的位势。 由于有 m + n 个变量（ ui , vj ），m + n - 1 个方程（基变量个数），故有一个自由变量，位势不唯一。 利用位势求检验数： ?ij = cij - ui - vj i = 1, … , m ; j = 1, … , n 前例，位势法求检验数： step 1 从任意基变量对应的 cij 开始，任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 个 ui , vj ；从 c14 = 10 开始 step 2 计算非基变量的检验数 ?ij = cij - ui - vj ；填入圆圈内