第四章运输最优化
第四章 运输最优化
本章将讨论以下几个方面的内容: 线性规划与单纯形法简介 运输问题 指派问题 今最短路问题 转运问题 中国邮递员问题
本章将讨论以下几个方面的内容： ❖ 线性规划与单纯形法简介 ❖ 运输问题 ❖ 指派问题 ❖ 最短路问题 ❖ 转运问题 ❖ 中国邮递员问题
线性规划简 令线性规划问题的标准型式 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 = =
单纯形法简 ☆单纯形法的基本思路:根据问题的标准,从可行 域中某个基可行解(一个顶点)开始,转换到 个基可行解(顶点),并且使目标函数达到最大 值时,问题就得到了最优解
单纯形法简介 ❖ 单纯形法的基本思路:根据问题的标准,从可行 域中某个基可行解(一个顶点)开始,转换到一 个基可行解(顶点),并且使目标函数达到最大 值时,问题就得到了最优解