4-1运输问题的数学模型

1、1第一节 运输问题及其数学模型 运输问题是一类特殊的线性规划运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特及其约束方程组的系数矩阵结构的特殊性，运输问题的对偶问题及其对偶殊性，运输问题的对偶问题及其对偶变量。变量。2运输问题运输问题典型背景：单一物资的运输调度问题设某种物品有: m个产地： 产量： n个销地： 销量： 从产地 到销地 的单位运价是 。 求总运费最小的调度方案。mAAA,21nBBB,21maaa,21nbbb,21iAjBijc3运输问题运输问题n决策变量决策变量 表示由表示由 到到 的运量。的运量。

2、iAjBijx12c11cnc121c22cnc21mc2mcmncnmmnmmmnnnbbbaxxxAaxxxAaxxxABBB21212222212111211121销地产地销量销量产量产量4运输问题运输问题n产销平衡问题总产量=总销量 即n产销不平衡问题总产量=总销量11mnijijab5运输问题运输问题 njmixnjbxmiaxxczijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111产地i运到n个销地的运量的总和，应该等于产地i的产量。m个产地运到销地j的运量的总和，应该等于销地j的销量。6运输问题运输问题举例说明 某部门三个工厂生产同一产品

3、的产量,四个销售点的销量及单位运价如下表：412285439611111012341231 61 02 281 41 21 44 8BBBBAAA销量销量产量产量销地产地7运输问题运输问题运输问题数学模型的特点n运输问题肯定有最优解n运输问题约束条件的系数矩阵（下页） 约束条件系数矩阵每一列只有两个1，其余为0；对产销平衡问题对产销平衡问题 约束条件均为等式，且产量之和=销量之和； 约束条件的独立方程最多有m+n-1个，即1)(nmAr8运输问题运输问题把m+n个约束分别展开，11121121222212nnmmmnmxxxaxxxamxxxa 个11211112222212mmnnmnnxx

4、xbxxxbnxxxb 个写出其写出其(m+n)*(m*n)维的维的系数系数矩阵矩阵9运输问题运输问题111111111111111111mnmmnnxxxxxxxxx212222111211mnnP210运输问题运输问题00100100ijijPx 的列向量im+jimjee00100ie其中11运输问题运输问题运输问题的对偶问题 对产销平衡运输问题 前m个约束等式相应的对偶变量 后n个约束等式相应的对偶变量即对偶变量为12,muuu12,nvvv1212( , ,)mnYu uuv vv12运输问题运输问题11121121222212nnmmmnmxxxaxxxamxxxa 个11211112222212mmnnmnnxxxbxxxbnxxxb 个12muuu12nvvv13运输问题运输问题11max,1,;. .1, .,mniijjijijijijza ub vuvcim