第四章运輸问题 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