《运筹学》第三章 运输问题.ppt

整理课件 Min z= ? ? cij· xij n i=1 j=1 m 一、产销不平衡问题 1?产?销(?ai?bj) Min z= ? ? cij·xij+?0?xi,n+1 n i=1 j=1 m i=1 m 产地 销地 A1 A2 ┊ Am B1 B2 ┈　 Bn C11 C12 ┈ C1n C21 C22 ┈ C2n ┆ ┊ ┈ ┊ Cm1 Cm2 ┈ Cmn Bn+1 ０ ０ ┆ ０ 产＞销问题单位运价表 销量 产量 b1 b2 ┈　 bn a1 a2 ┊ am ?ai??bj Min z= ? ? cij· xij n i=1 j=1 m 2?销?产(?bj?ai) Min z= ? ?cij·xij +?0?xm+1,j n i=1 j=1 m j=1 n 产地 销地 A1 A2 ┊ Am B1 B2 ┈　 Bn C11 C12 ┈ C1n C21 C22 ┈ C2n ┆ ┊ ┈ ┊ Cm1 Cm2 ┈ Cmn Am+1 销＞产问题单位运价表 0 0 ┈ 0 销量 产量 b1 b2 ┈　 bn a1 a2 ┊ am ?bj??ai 第3章 运输问题 3.1 运输问题的典例和数学模型 3.2 运输问题的求解方法：表上作业法 3.3 几类特殊的运输问题 3.4 运输问题的应用 运输问题： 根据已有的交通网，如何制定运输方案，使得这些物资被运送到各个销售地，并保证某个指标最优(例如总运费最小)。 3.1 运输问题的典例和数学模型 一、典例 某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？ 生产量：A1——7吨， A2 —— 4吨， A3 —— 9吨 销售量：B1 —— 3吨，B2 —— 6吨，B3 —— 5吨，B4 —— 6吨 产地 单位运价 销地 B1 B2 B3 B4 A1 A2 A3 3 11 3 10 1 9 2 8 7 4 10 5 调运示意图 A1 A2 A3 B1 B2 B3 B4 7吨 4吨 9吨 3吨 6吨 5吨 6吨 x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 产地 销地 二、建立模型 设 xij——第i产地到第j销地之间的调运量，则有 Min z = ? ? cij· xij 3 4 i=1 j=1 x11+x12+x13+x14=7 x11+x21+x31=3 xij?0,(i=1,2,┄,3；j=1,2,┄,4) 产量限制 销量限制 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x12+x22+x32=6 x13+x23+x33=5 x14+x24+x34=6 单位运价表 产销平衡表 一般模型表示(??ai=?bj) 三、模型的特点 1.变量数：m?n个 2.约束方程数：m+n个 最大独立方程数：m+n-1 3.系数列向量结构： Pij= ——第i个分量 ——第m+j个分量 0 1 1 0 … … … x11 x12 ······ x1n x21 x22 ······ x2n ,············, xm1 xm2 ······ xmn 1 1 ······ 1 0 0 ······ 0 ············ 0 0 ······ 0 0 0 ······ 0 1 1 ······ 1 ············ 0 0 ······ 0 0 0 ······ 0 0 0 ······ 0 ············ 1 1 ······ 1 1 0 ······ 0 1 0 ······ 0 ············ 1 0 ······ 0 0 1 ······ 0 0 1 ······ 0 ············ 0 1 ······ 0 0 0 ······ 1 0 0 ······ 1 ············ 0 0 ······ 1 i=1 i=2 i=m j=1 j=2 j=n ······ ······ ······ ······ ······ ······ ······ ······ ······ ······