《运筹学》课程电子教案（PPT课件讲稿）第四章 运输问题

第四章运輸问题 41运输问题 4.2运输问题的表上作业法 43运输问题的进一步讨论

第四章 运输问题 4.1 运输问题 4.2 运输问题的表上作业法 4.3 运输问题的进一步讨论

第一节运输问题 及其数学模型 运输问题是一类特殊的线性规划 问題,本节介绍运输问题的教学模型 及其约束方程组的糸数矩阵结构的特 殊性,运输问题的对偶问题及其对偶 变量与原问题检验数的关糸

第一节 运输问题 及其数学模型 运输问题是一类特殊的线性规划 问题，本节介绍运输问题的数学模型 及其约束方程组的系数矩阵结构的特 殊性，运输问题的对偶问题及其对偶 变量与原问题检验数的关系

典型背景——单一物资运输调度问题 设某种物品有: m个产地:A,A2,……,An 产量:a1242,…,m n个销地:B1,B2,…,Bn 销量:b,b2,…,bn 从产地A到销地B的单位运价是 求总运费最小的调度方案。 运输问题 上回

运输问题 典型背景——单一物资运输调度问题 设某种物品有: m个产地： 产量： n个销地： 销量： 从产地 到销地 的单位运价是 。 求总运费最小的调度方案。 A1 , A2 ,  , Am B B Bn , , , 1 2  a1 ,a2 ,  ,am b b bn , , , 1 2  Ai Bi cij

決策变量x;表示由A到B的物品数量。 X X X 2 4|x X 22 X 2n m2 X 销量 6. b b 12 上回

运输问题 决策变量 xij 表示由 Ai 到 Bi 的物品数量。 c11 c12 c1n c21 c22 c2n cm1 cm2 cmn n m m m m n m n n n b b b A x x x a A x x x a A x x x a B B B 1 2 1 2 2 2 1 2 2 2 2 1 1 1 1 2 1 1 1 2   销量 产量

产销平衡问题——总产量=总销量 产销不平衡问题——总产量总销量 运输问题 上回

运输问题 产销平衡问题——总产量=总销量 即 产销不平衡问题——总产量=总销量   = = = n i j m i ai b 1 1

产销平衡问题的数学模型 772 b ≥0,i=12 ,17 运输问题 上回

运输问题          =  = = = = = =    = = = = j n x i m x b j n x a i m z c x i j j m i i j i n j i j m i n j i j i j     1,2, 0, 1,2, , , 1,2, , , 1,2, , min 1 1 1 1 产销平衡问题的数学模型

运输问题数学模型的特点 运输问题有有限最优解 运输问题约束条件的系数矩阵(下页 约束条件系数矩阵每一列只有两个1,其余 为0 对产销平衡问题 约束条件均为等式,且产量之和=销量之和 约束条件的独立方程最多有m+n-1个,即 r(A)≤m+n-1 运输问题 上回

运输问题 运输问题数学模型的特点 运输问题有有限最优解 运输问题约束条件的系数矩阵（下页） – 约束条件系数矩阵每一列只有两个1，其余 为0； 对产销平衡问题 – 约束条件均为等式，且产量之和=销量之和； – 约束条件的独立方程最多有m+n-1个，即 r(A)  m + n −1

112 n 21 Nm2 1 1 m 2n n 运输问题 上回

运输问题   1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1         x11 x12  x1n x21 x22  x2n  xm1 xm2  xmn mn P2 n =

x的列向量P 0:010:010:0 =e;+e 其中 运输问题 上回

运输问题                         = 0 0 1 0 0 1 0 0    xi j的列向量Pi j i j = ei + ej                 = 0 0 1 0 0   其中 ei

运输问题的对偶问题 对偶变量与原问题检验数的关系 对产销平衡运输问题,若用l1,2…,ln 分别表示前m个约束等式相应的对偶变量, 用V,V2分别表示后n个约束等式相应的对 偶变量,即对偶变量为 Y=(l1,l2,…,nv,V2…Vn) 运输问题 上回

运输问题 运输问题的对偶问题 ——对偶变量与原问题检验数的关系 对产销平衡运输问题，若用 分别表示前m个约束等式相应的对偶变量， 用 分别表示后n个约束等式相应的对 偶变量，即对偶变量为 m u ,u , ,u 1 2  m v ,v , ,v 1 2  Y = ( ( , , , , , , , ) 1 2 m 1 2 m Y = u u  u v v  v