第四章运输最优化
第四章 运输最优化
本章将讨论以下几个方面的内容: 线性规划与单纯形法简介 运输问题 指派问题 今最短路问题 转运问题 中国邮递员问题
本章将讨论以下几个方面的内容： ❖ 线性规划与单纯形法简介 ❖ 运输问题 ❖ 指派问题 ❖ 最短路问题 ❖ 转运问题 ❖ 中国邮递员问题
线性规划简 令线性规划问题的标准型式 maxz=C1X1+C2X十…+C,x 11x1 Ixn=6, 十a,xX++a m1x1+am2x2+……+amxn X1.x
线性规划简介 ❖ 线性规划问题的标准型式 n n z = c x + c x ++ c x max 1 1 2 2 + + + = + + + = + + + = , , , 0 ( ) 1 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 n m m mn n n n n n n x x x a x a x a x b a x a x a x b a x a x a x b M
X≥0 用矩阵描述时为 max z=CX AX=b X≥0 A (P12 m2 mn b为资源向量; C为价值向量; x为决策变量的向量
❖ 用矩阵描述时为 ❖ b为资源向量； ❖ c为价值向量； ❖ x为决策变量的向量 max z =CX AX = b X 0 X 0 ( , , , ) 1 2 1 2 1 1 1 2 1 n m m mn n p p p a a a a a a A = =
单纯形法简 ☆单纯形法的基本思路:根据问题的标准,从可行 域中某个基可行解(一个顶点)开始,转换到 个基可行解(顶点),并且使目标函数达到最大 值时,问题就得到了最优解
单纯形法简介 ❖ 单纯形法的基本思路:根据问题的标准,从可行 域中某个基可行解(一个顶点)开始,转换到一 个基可行解(顶点),并且使目标函数达到最大 值时,问题就得到了最优解
例如以下问题 maxz=2x1+3x2+0x3+0x4+0x x1+2x 8 4x1 16 x,≥0.j=1,2.…,5 经变换,得到一个基可行解X(3)=(4,2,0,0,4) 此时,目标函数的表达式z=14-1.5x2-0.125x 这说明若要用剩余资源x3,X4,就必须支付附加费用。 所以x3=对0即不再利用这些资源时,目标函 数达到最大值。所以慧翬优解
❖ 例如以下问题 ❖ 经变换，得到一个基可行解 ❖ 此时，目标函数的表达式 ❖ 这说明若要用剩余资源 ，就必须支付附加费用。 所以 时，即不再利用这些资源时，目标函 数达到最大值。所以 是最优解。 max 2 1 3 2 0 3 0 4 0 5 z = x + x + x + x + x + = + = + + = 4 12 4 16 2 8 2 5 1 4 1 2 3 x x x x x x x x j 0, j =1,2, ,5 T X (4,2,0,0,4) (3) = 3 125 4 z =14−1.5x −0. x 3 4 x , x x3 = x4 = 0 (3) X
运输问题 已知有m个供应地点A2,=1,2,…,m。可供应 某种物资,其供应量分别为a,i=1.2…,m,有 n个销地B,j=12,…n,其需要量分别 为b,=1,2,…,n,从41到B,运输单位物资的 运价(单价)为c,这些数据可以汇总到 销平衡表和单位运价表中。若用x表示从A 到B,的运量,那么供需平衡的条件下,要求 得总运费最小的调运方案,可求解以下数学 模型:
运输问题 ❖ 已知有m个供应地点 。可供应 某种物资，其供应量分别为 ，有 n个销地 ，其需要量分别 为 ，从 到 运输单位物资的 运价（单价）为 ，这些数据可以汇总到产 销平衡表和单位运价表中。若用 表示从 到 的运量，那么供需平衡的条件下，要求 得总运费最小的调运方案，可求解以下数学 模型： Ai ,i =1,2, ,m ai ,i =1,2, ,m Bj , j = 1,2, ,n b j n j , = 1,2, , Ai Bj ij c ij x Ai Bj
mn ∑∑cnx ∑ x.20
ij m i n j ij z c x = = = 1 1 minx b j n j m i ij , 1,2, , 1 = = = x ai i m n j ij , 1,2, , 1 = = = xij 0
表上作业法 令例题:某物流公司有三个仓库,每天向四个 超市供应某种货物。已知三个仓库A1、A2 和A3的此货物储藏量分别为7箱、4箱和9箱。 该物流公司把这些货物分别送往B1、B2 B3和B4四个超市,各超市每日销量分别为3 箱、6箱、5箱和6箱。试用表上作业法求解 满足供需要求的最佳调运方案,使总运费最
表上作业法 ❖ 例题：某物流公司有三个仓库，每天向四个 超市供应某种货物。已知三个仓库A1 、A2 和A3的此货物储藏量分别为7 箱、 4箱和 9箱。 该物流公司把这些货物分别送往B1 、B2 、 B3 和B4四个超市，各超市每日销量分别为3 箱、 6箱、 5箱和6箱。试用表上作业法求解 满足供需要求的最佳调运方案，使总运费最 少
第一步,画出该问题的供销平衡表和单位运价表 超市 B B B 仓库 B A 10
第一步，画出该问题的供销平衡表和单位运价表 超市 仓库 B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5