《41运输问题的数学模型》由会员分享，可在线阅读，更多相关《41运输问题的数学模型（15页珍藏版）》请在装配图网上搜索。
1、第一节第一节 运输问题及其数学模型运输问题及其数学模型 运输问题是一类特殊的线性规划运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特及其约束方程组的系数矩阵结构的特殊性，运输问题的对偶问题及其对偶殊性，运输问题的对偶问题及其对偶变量。变量。12021/6/42典型背景：单一物资的运输调度问题典型背景：单一物资的运输调度问题设某种物品有设某种物品有:m个产地：个产地：产量产量：n个销地：个销地：销量销量：从产地从产地 到销地到销地 的单位运价是的单位运价是 。求求总运费最小总运费最小的调度方案。的调度方案。mAAA,21
2、nBBB,21maaa,21nbbb,21iAjBijc3n决策变量决策变量 表示由表示由 到到 的运量。的运量。iAjBijx12c11cnc121c22cnc21mc2mcmncnmmnmmmnnnbbbaxxxAaxxxAaxxxABBB21212222212111211121销地产地销量销量产量产量4n产销平衡问题产销平衡问题总产量总产量=总销量总销量 即即n产销不平衡问题产销不平衡问题总产量总产量=总销量总销量11mnijijab5 njmixnjbxmiaxxczijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111产地产地i运到运到n个销地的
3、运量的总个销地的运量的总和，应该等于产地和，应该等于产地i的产量。的产量。m个产地运到销地个产地运到销地j的运量的总的运量的总和，应该等于销地和，应该等于销地j的销量。的销量。6举例说明举例说明 某部门三个工厂生产同一产品的产量某部门三个工厂生产同一产品的产量,四个四个销售点的销量及单位运价如下表：销售点的销量及单位运价如下表：412285439611111012341231 61 02 281 41 21 44 8BBBBAAA销量销量产量产量销地产地7运输问题数学模型的特点运输问题数学模型的特点n运输问题肯定有运输问题肯定有最优解最优解n运输问题约束条件的系数矩阵运输问题约束条件的系数矩阵
4、（下页）（下页）约束条件系数矩阵每一列只有两个约束条件系数矩阵每一列只有两个1，其余，其余为为0；对产销平衡问题对产销平衡问题 约束条件均为等式，且约束条件均为等式，且产量之和产量之和=销量之和销量之和；约束条件的独立方程最多有约束条件的独立方程最多有m+n-1个，即个，即1)(nmAr8把把m+n个约束分别展开，个约束分别展开，11121121222212nnmmmnmxxxaxxxamxxxa 个11211112222212mmnnmnnxxxbxxxbnxxxb 个写出其写出其(m+n)*(m*n)维的维的系数系数矩阵矩阵9111111111111111111mnmmnnxxxxxxxx
5、x212222111211mnnP21000100100ijijPx 的列向量im+jimjee00100ie其中11运输问题的对偶问题运输问题的对偶问题 对产销平衡运输问题对产销平衡运输问题 前前m个约束等式相应的对偶变量个约束等式相应的对偶变量 后后n个约束等式相应的对偶变量个约束等式相应的对偶变量即对偶变量为即对偶变量为12,muuu12,nvvv1212(,)mnYu uuv vv1211121121222212nnmmmnmxxxaxxxamxxxa 个11211112222212mmnnmnnxxxbxxxbnxxxb 个12muuu12nvvv1311max,1,;.1,.,mniijjijijijijza ub vuvcims tjnuv 无约束运输问题的对偶问题可写为运输问题的对偶问题可写为运输问题的对偶问题运输问题的对偶问题下一节下一节 表上作业法表上作业法n 最小元素法最小元素法n 伏格尔法伏格尔法142021/6/4部分资料从网络收集整理而来，供大家参考，感谢您的关注！
41运输问题的数学模型
