运筹学基础(第2版)何坚勇运输问题.ppt

运输问题是线性规划问题 由于其约束条件的特殊性 产生了特殊的解法 第五章运输问题 例 从3个发点A1 A2 A3 向4个收点B1 B2 B3 B4发送某种货物 Ai供应量为14 27 19 Bj收点的收量为22 13 12 13 由Ai运往Bj单位货物的运费为Cij 由Ai运往Bj货物的运量为Xij 问如何调配 才能使运费最省 2 3 2 1 3 4 1 运输问题网络图 s2 A2 s3 A3 B1 B2 B3 B4 s1 A1 供应量 供应地 运价 需求量 需求地 6 7 5 3 8 4 2 7 5 9 10 6 B1 运输问题线性规划模型 供应地约束 需求地约束 5 1运输问题数学模型和特点 5 1 1产销平衡问题的数学模型 问题的提出从m个发点A1 A2 Am向n个收点B1 B2 Bn发送某种货物 Ai发点的发量为ai Bj收点的收量为bj 由Ai运往Bj单位货物的运费为Cij 由Ai运往Bj货物的运量为Xij 问如何调配 才能使运费最省 当发点的发量总和为 ai 收点的收量总和为 bj相等时 称此运输问题为平衡运输问题 否则称此运输问题为非平衡运输问题 若没有特别说明 均假定运输问题为平衡的运输问题 续 MinZ cijxijij xij ai i 1 2 m xij bj j 1 2 n xij 0 i 1 2 m j 1 2 n 5 1 1运输问题的数学模型 m n j i n m 运输问题的数学模型 其中ai 0 bj 0 cij 0且共有m n个约束方程 并成立 ai bjij m n X X11 X12 X1n X21 X22 X2n Xm1 Xm2 Xmn TC C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn A P11 P12 P1n P21 P22 P2n Pm1 Pm2 Pmn 由于 ai bj成立其m n个约束方程并不是独立的 实际上只有m n 1个是独立的 即约束方程系数矩阵的秩为m n 1 运输问题解的结构 n m i j Pij Pij ei em j i 1 m j 1 n ei为第i个分量为1其余分量为0的m n维向量 em j为第m j个分量为1其余分量为0的m n维分量 运输问题矩阵描述 minCX S TAX b 5 1 3 x 0 其中A为 A m n mn X11X12 X1nX21X22 X2n Xm1Xm2 Xmn1 1111 11111111 111 A n a1a2 amb1b1 bn 5 1 2运输问题数学模型的特点 1 有m n列 每列有 m n 个元素 其中有两个1 其余为0 对于列Pij来说 两个1的位置为i与m j个分量Pij ei em jei为第i个分量为1其余分量为0的m n维单位向量em j为第m j分量为1 其余分量为0的m j分量为0的m n维单位向量 如 2 A有 m n 行 每行前m行有n个1并连在一起 其余为零 E0 00E 0 00 EII I A E 1 1 1 3 运输问题有最优解 证明由于 ai bj d成立 令Xij aibj d5 1 6I 1 2 mJ 1 2 n代入5 1 1 n m i j 续 Xij aibj d bj ai d ai i 1 2 m Xij aibj d ai bj d bj j 1 2 n ai 0 bj 0 所以Xij 0 n j 1 n j 1 n j 1 m m m i 1 i 1 i 1 xu 5 1 6是运输问题的可行解 由定理2 4 6可得运输问题必有基本可行解 由Xij的定义知 Xij min ai bj 可行域是有界的 必有最优解 4 矩阵A的秩为 m n 1 A是一个 m n m n 型矩阵一般来说 m n m n 因此秩最大为 m n 又前m方程与后n个方程和相等 故r A 实际是等于 m n 1 A m n mn X11X12 X1nX21X22 X2n Xm1Xm2 Xmn1 1111 11111111 111 A n a1a2 amb1b1 bn A m n mn p 11p 12 p 1np 21p 31 p m100 011 111 11 1 A 证明 p 11p 12 p 1np 21p 31 p m1线性无关 而pij与p ij只差一个分量 由向量相关理论可知 一组线性无关向量组在相同的位置上加相同多的分量后得到的新向量也线性无关 因此p11p12 p1np21p31 pm1也线性无关 r A m n 1 5 2表上作业法 由于运输问题的特殊性 因此求解运输问题往往不用单纯形法 而用表上作业法 1 用西北角法或最小元素法确定基本可行解 2 用位势法求解检验数3 用闭回路调整法求最优解 调运表 发点 收点 例5 2 1表5 3 收点 发点 5 2运价表 收点 发点 1 西北角法 I j 从 1 1 开始 比较a1 b1 X11 min a1 b1 b1 3 表5 3 收点 发点 表5 4 X11 min a1 b1 b1 3X12 min a 1 b2 a 1 4X22 min a2 b 2 b 2 2X23 min a 2 b3 min 2 5 a 2 2X33 min a3 b 3 min 9 3 b 3 3X34 min a 3 b4 6 表5 5 Z 3 3 4 11 2 9 2 2 3 10 6 5 133 万 2 最小元素法 表5 6 7 3 6 4 1 3 3 C21 1 X21 min a2 b1 b1 3C23 2 X23 min a 2 b3 min 1 5 a 2 1C13 3 X13 min a1 b 3 min 7 4 b 3 4C32 4 X32 min a2 b2 b2 6C34 5 X34 min a 3 b4 min 3 6 a 3 3C14 10 X14 min a 1 b 4 a 1 b 4 3Z 4 3 3 10 3 1 1 2 6 4 3 5 86 元 5 2 2位势法求检验数 ij Cij Zij Cij CBB 1Pij5 2 1 i 1 2 m j 1 2 n Maxf aiui bjvjstui vj Cij i 1 2 m j 1 2 n ui vj无正负 W u1 um v1 vn 5 2 3Ui xi1 xi2 xi3 xi4 xin vj x1j x2j x xmj m I 1 j 1 n MinZ cijxijij xij ai i 1 2 m xij bj j 1 2 n xij 0 i 1 2 m j 1 2 n 5 1 1运输问题的数学模型 m n j i n m 运输问题线性规划模型 供应地约束 需求地约束 5 2 3代5 2 1 ij Cij WPij Cij u1 um v1 vn ei em j Cij ui vj 5 2 4 i 1 2 m j 1 2 n A n X11X12 X1nX21X22 X2n Xm1Xm2 Xmn1 1111 11111111 111 基变量的 Cij ui vj 0 i j JB 5 2 5 因为为已知 而 5 2 5 有 m n 个未知量令Vn 0 5 2 6 非基变量检验数 ij Cij ui vj i j JN 5 2 7 A 公式求检验数 表5 5 Z 3 3 4 11 2 9 2 2 3 10 6 5 133 万 5 2 1例表5 5 基变量 X11 X12 X22 X23 X33 X34C11 u1 v1 0C12 u1 v2 0C22 u2 v2 0C23 u2 v3 0C33 u3 v3 0C34 u3 v4 0V4 0 代入Cij 3 u1 v1 011 u1 v2 09 u2 v2 02 u2 v3 010 u3 v3 05 u3 v4 0V4 0解出 u1 1 u2 3 u3 5 v1 4 v2 12 u3 5 代入公式5 2 7 ij Cij ui vj i j JN5 2 7 13 C13 u1 v3 3 1 5 1 14 C14 u1 v4 10 1 0 11 21 C21 u2 v1 1 3 4 0 代入公式5 2 7 ij Cij ui vj I j JN5 2 7 24 C24 u2 v4 8 3 0 11 31 C31 u3 v1 7 5 4 2 32 C32 u3 v2 4 5 12 13 ij 0 故不是最优解 B 检验数表格求解 1 作表格 3 1 4 1 的表2 第 3 1 行为vj行 4 1 列为ui列3 右上角标出Cij 其中非基变量用 框住 表5 8 7 1 7 4非 3 10 8 V4 0 基变量 X11 X12 X22 X23 X33 X34Cij ui vj 0 i j JB 5 2 5 Cij ui vj ui Cij vj 5 2 10 因为 V4 0 C34 u3 v4 u3 5 V3 C33 u3 10 5 5C23 u2 v3 u2 C23 v3 2 5 3 计算 V4 0 基变量 X11 X12 X22 X23 X33 X34Cij ui vj 0 I j JB5 2 5Cij ui vj 5 2 10因为 V4 0 C34 u3 v4 u3 5 表5 9 7 1 7非 4 3 10 8 Cij ui vj 5 2 10C22 u2 v2 v2 C22 u2 9 3 12u1 C12 v2 11 12 1V1 C11 u1 3 1 4 表5 10 7 1 7 4 3 10 8 ij Cij ui vj i j JN 5 2 7 13 C13 u1 v3 3 1 5 1 14 C14 u1 v4 10 1 0 11 21 C21 u2 v1 1 3 4 0 24 C24 u2 v4 8 3 0 11 31 C31 u3 v1 7 5 4 2 32 C32 u3 v2 4 5 12 13有 ij 0 故不是最优解 例5 2 2 以例5 2 1的最小元素法求得的基本可行解为例 见表5 7用位势法计算检验数 最小元素法 表5 6 7 3解 6 4 1 3 3 表5 11 7 7非 8 3 11 9 10 5 2 3用闭回路法调整当前基本可行解 定义5 2 将变量Xij在调运表中所对应的空格记做 i j 称为格点 而Xij系数列向量Pij也称作格点 i j 所对应的系数列向量 若Xij为基变量 则 i j 称为基格 否则为非基格 表5 6 7 基格 1 3 1 4 2 1 2 3 非基格 1 1 2 4 3 1 2 3 表5 6 7 3 6 4 1 3 3 定义5 2 2 定义5 2 2若一组格点经过适当的排序后 能写成以下形式 I1 j1 I1 j2 I2 j2 I2 j3 I3 j3 Is js Is ji 1则这组格点构成了闭回路 闭回路特点 1 格点数大于4 2 形式A 第1格与第2格行号同 第2与第3格列号同 第3 第4格行号同 第4 第5格列号同 最后一格与第一格列号同 形式B 第1格 第2格列号同 第2格 第3格行号同 最后一格与第一格行号同 3 连线构成闭回路 一行或一列只包含两个格点 都处在每条边的端点上 5 12 格组 1 1 1 2 3 2 3 1 格组 1 3 1 4 2 4 2 5 3 5 3 3 格组 1 6 1 7 4 7 4 9 2 9 2 6 表5 12 格组 1 1 1 2 3 2 3 1 格组 1 3 1 4 2 4 2 5 3 5 3 3 格组 1 6 1 7 4 7 4 9 2 9 2 6 5 13 包含了闭回路 非构成闭回路成 格组 1 1 1 2 1 4 3 4 3 2 格组 2 5 2 6 2 7 3 7 3 6 3 5 表5 10 7 1 7 4 3 10 8 表5 5 Z 3 3 4 11 2 9 2 2 3 10 6 5 133 万 表5 14 Z 3 3 4 11 2 9 2 2 3 10 6 5 133 元 ij min ij ij 0 32 13 I j JN 表5 5初始方案 5 10检验数不大于0 32 13 min Xij i j 为闭回路上所有偶数号格点 min 2 3 2 X22 表5 15 X 1 3 4 0 0 0 0 4 0 0 2 1 6 TZ 1 3 3 11 4 2 4 4 2 10 1 5 6 109 元 Z 0 133 元 产销平衡运输问题的算法其步骤如下 第l步 用西北角规则或最小元素法求初始基本可行解 第2步 用位势法求非基变量的检验数 若最优准则 ij 0得到满足 则当前基本可行解就是最优解 当前调运方案就是最优调运方案 计算停止 否则转第3步 第3步 取一个检验数最小的非基变量作进基变量 其对应的格为进基格 编号为第1格 以进基格为起始点作出一个其余顶点均为基格的闭回路 在该闭回路上 从所有偶数号格点的调运量中选出最小值 作为调整量 该格即为离基格 对应的变量为离基变量 第4步 对闭回路上的运输量作出调整 所有奇数号格的调运量加上调整量 所有偶数号格的调运量减去调整量 其余的Xij取值不变 这样就得到了一个新的调运方案转第2步 例5 2 3 判断以表5 15所体现的X 1 是否为最优解 若不是 试求出最优解 解 对X 1 用位势法求其检验数 为此建立表5 16 计算ui vj及 ij 表5 15 X 1 3 4 0 0 0 0 4 0 0 2 1 6 TZ 1 3 3 11 4 2 4 4 2 10 1 5 6 109 元 Z 0 133 元 表5 16 1 7 1 7 3 10 8 9 ij min ij ij 0 13 14 i j JN非优 建闭回路 表5 17 X 2 3 3 1 0 0 0 4 0 0 3 0 6 TZ 2 3 3 11 3 3 1 2 4 4 3 5 6 95 元 Z 1 109 元 min Xij I j 为闭回路上所有偶数号格点 min 1 4 1 X33 再判断X 2 是否为最优解 建立表5 18 计算ui vj及 ij 表5 18 7 1 7 10 8 9 10 不都大于0 也不是最优解 ij min ij ij 0 24 3 i j JN非优 建闭回路 表5 19 X 3 3 0 4 0 0 0 1 3 0 6 0 3 TZ 3 3 3 3 4 2 1 8 3 4 6 5 3 86 元 Z 2 95 元 min Xij i j 为闭回路上所有偶数号格点 min 6 3 4 3 X12 再判断X 3 是否为最优解 建立表5 20 计算ui vj及 ij 表5 20 7 1 7 10 9 11 10 不都大于0 也不是最优解 ij min ij ij 0 21 1 i j JN非优 建闭回路 表5 21 X 4 2 0 5 0 1 0 0 3 0 6 0 3 TZ 4 3 2 3 5 1 1 8 3 4 6 5 3 85 元 Z 3 86 元 表5 22 7 7 10 9 11 10 2 都大于0 是最优解 X11 2 X13 5 X21 1 X24 3 X32 6 X34 3 XI4 0 5 2 4表上作业法计算中的两个问题 1 无穷多个最优解2 退化问题 1 无穷多个最优解 某个非基变量检验数等于零 表5 23 X 5 0 0 5 2 3 0 0 1 0 6 0 3 TZ 5 3 5 10 2 1 3 8 1 4 6 5 3 85 元 表22中 14 0 作闭回路 2 退化问题 1 在确定初始可行解时 若已确定的空格 i j 处要填上调运量Xij 而此时刚好有a i b j Xij a i b j 说明此时Ai的发运量已经用完 而Bi的需求已满足 因此要画掉第i行 j列 x 为了保证调运表上有 m n 1 个基变量的值 就要在第i行 j列中任找一个空格 i j1 或 i1 j 设置调运量为Xij1 0 或Xi1j 0 例5 2 4 下表为3 4运输问题的Cij及发运量和需求量 试用最小素法求该问题的一个可行解 例5 2 4调运表 例5 2 4调运方案 2 在用闭回路调整时出现退化 min Xij i j 为闭回路上所有偶数号格点 如果两个或两个以上偶数格点Xij都为极小值 则只能取一个为离基格 其余作为基格 出现了退化问题 例5 2 5 表5 26为3 4问题的基本可行解及发运量和需求量 表5 27为基本可行解的检验数 用闭回路法对其作出调整 表5 26 表5 27 表5 28 min ij 24闭回路如图 min Xij i j 为闭回路上所有偶数号格点 min X34 X12 X23 X12 X23 3 表5 28 min ij 24闭回路如图 min Xij i j 为闭回路上所有偶数号格点 min X34 X12 X23 X12 X23 3 作业答案 P170 5 2 题5 11基本可行解 X11 min a1 b1 b1 6X12 min a 1 b2 a 1 1X22 min a2 b 2 b 2 5X23 min a 2 b3 min 2 5 a 2 3X33 min a3 b 3 0X34 min a 3 b4 3 表5 11 7 4 8 4非 7 3 7 V4 0 基变量 X11 X12 X22 X23 X33 X34Cij ui vj 0 I j JB5 2 5Cij ui vj ui Cij vj 5 2 10因为 V4 0 C34 u3 v4 u3 9 V3 C33 u3 2 9 7C23 u2 v3 u2 C23 v3 10 7 17 表5 12检验数 7 4 8 4非 7 3 7 ij Cij ui vj I j JN5 2 7 13 C13 u1 v3 7 7 16 2 14 C14 u1 v4 3 16 0 13 21 C21 u2 v1 4 11 17 2 24 C24 u2 v4 7 17 0 10 31 C31 u3 v1 8 9 11 10 32 C32 u3 v2 4 9 8 3有 ij 0 故不是最优解 题5 13闭回路 min Xij I j 为闭回路上所有偶数号格点 min 1 3 3 1 表5 14VU 7 4 8 4非 7 8 7 V4 0 基变量 X11 X12 X22 X23 X33 X34Cij ui vj 0 I j JB5 2 5Cij ui vj ui Cij vj 5 2 10因为 V4 0 C34 u3 v4 u3 9 V3 C33 u3 2 9 7C23 u2 v3 u2 C23 v3 10 7 17 表5 15检验数 7 4 8 4非 7 7 ij Cij ui vj I j JN5 2 7 13 C13 u1 v3 7 7 3 11 12 C12 u1 v2 8 3 8 13 21 C21 u2 v1 4 2 17 15 24 C24 u2 v4 7 17 0 10 31 C31 u3 v1 8 9 2 3 32 C32 u3 v2 4 9 8 3有 ij 0 故不是最优解 8非 题5 16闭回路 min Xij I j 为闭回路上所有偶数号格点 min 2 2 6 2 表5 17检验数 7 8 4非 7 7 ij Cij ui vj I j JN5 2 7 13 C13 u1 v3 7 7 3 11 12 C12 u1 v2 8 3 7 2 23 C23 u2 v3 10 2 7 15 24 C24 u2 v4 7 2 0 5 31 C31 u3 v1 8 9 2 3 32 C32 u3 v2 4 9 7 12有 ij 0 故不是最优解 8非 10 题5 18闭回路 min Xij I j 为闭回路上所有偶数号格点 min 0 4 6 0 表5 19检验数 7 8 7 7 ij Cij ui vj I j JN5 2 7 13 C13 u1 v3 7 5 3 1 12 C12 u1 v2 8 3 7 2 23 C23 u2 v3 10 2 5 3 24 C24 u2 v4 7 2 0 5 31 C31 u3 v1 8 2 3 9 34 C34 u3 v4 9 0 3 12有 ij 0 故不是最优解 8非 10 9 题5 20闭回路 min Xij I j 为闭回路上所有偶数号格点 min 4 6 4 表5 21检验数 7 8 7 7 ij Cij ui vj I j JN5 2 7 13 C13 u1 v3 7 5 3 1 11 C11 u1 v1 5 3 0 2 23 C23 u2 v3 10 2 5 3 24 C24 u2 v4 7 4 0 3 31 C31 u3 v1 8 0 1 9 34 C34 u3 v4 9 0 1 10有 ij 0 故是最优解 10 9 5 题5 22闭回路 X 1 0 4 0 0 6 2 0 0 0 0 3 0 TZ 1 8 4 3 3 6 4 9 2 3 2 89 5 2最小元素法 题5 21基本可行解 1 2 3 4 5 6 7 表5 22UV 20 30 20 40 20 30 40 55 V5 0 基变量 X11 X12 X22 X23 X24 X32 X35Cij ui vj 0 I j JB5 2 5Cij ui vj ui Cij vj 5 2 10因为 V5 0 C35 u3 v4 u3 25 V2 C32 u3 35 25 10C22 u2 v2 u2 C22 v2 40 10 30V3 C23 u2 15 30 15 表5 23检验数 20 30 20 40 ij Cij ui vj I j JN5 2 7 13 C13 u1 v3 20 15 5 30 14 C14 u1 v4 20 5 0 15 15 C15 u1 v5 40 5 0 35 21 C21 u2 v1 20 5 30 15 25 C25 u2 v5 30 30 0 0 31 C31 u3 v1 30 25 5 0 33 C33 u3 v3 40 25 15 30 34 C34 u3 v4 55 25 0 30有 ij 0 故不是最优解 20 30 40 55 题5 24基本可行解 ij min ij ij 0 21 15 I j JN非优 建闭回路 X 1 15 35 0 0 0 10 0 60 30 0 0 80 0 0 70 TZ 1 15 10 35 15 10 25 60 15 30 30 80 35 70 25 7225 表5 25检验数 40 30 20 40 ij Cij ui vj I j JN5 2 7 13 C13 u1 v3 20 0 5 15 14 C14 u1 v4 20 5 15 0 15 C15 u1 v5 40 5 0 35 22 C22 u2 v2 40 15 10 15 25 C25 u2 v5 30 15 0 15 31 C31 u3 v1 30 25 5 0 33 C33 u3 v3 40 25 0 15 34 C34 u3 v4 55 25 15 15有 ij 0 故是最优解 20 30 40 55 题5 11 基本可行解 表5 11 7 4 8 4非 7 3 2 V4 0 基变量 X11 X12 X22 X23 X33 X