《运筹学第3章 运输问题—08讲.ppt》由会员分享，可在线阅读，更多相关《运筹学第3章 运输问题—08讲.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、手机：手机：13551284516院系：交通与汽车学院，交通运输系院系：交通与汽车学院，交通运输系主讲主讲:罗罗 建建 一、运输问题的数学表达一、运输问题的数学表达 生产某种产品，生产某种产品，m m个产地：个产地：A A1 1,，A Am m,产量：产量：a a1 1,，a am m n n个销地：个销地：B B1 1,，B Bn n,销量：销量：b b1 1,，b bn n已知：已知：A Ai i至至B Bj j的运输单价为的运输单价为c cijij问题：确定问题：确定A Ai i运往运往B Bj j的数量的数量x xijij，使总运费最低？使总运费最低？二、运输问题的表示二、运输问题的表
2、示网络图网络图运输表运输表线性规划模型线性规划模型A2A3B2A1B3B4B1运输问题网络图运输问题网络图a2=4a3=9b1=3b2=6b3=5b4=6a1=7供供应应量量供应地供应地运价运价需需求求量量需求地需求地311310192874105运输问题的表格表示运输问题的表格表示运输问题线性规划模型运输问题线性规划模型产产量量约约束束销销量量约约束束三、运输问题的分类三、运输问题的分类产销平衡问题：产销平衡问题：a ai i=b bj j产销不平衡问题：产销不平衡问题：供大于求：供大于求：ai bj供不应求：供不应求：ai bj四、运输问题的求解四、运输问题的求解表上作业法表上作业法确定初
3、始可行调运方案确定初始可行调运方案最小元素法最小元素法判别当前可行方案是否最优判别当前可行方案是否最优闭回路法闭回路法对现有方案进行调整对现有方案进行调整 闭回路法闭回路法用最小元素法确定初始可行调运方案用最小元素法确定初始可行调运方案 最小元素法的基本思想：就近尽量满足供应最小元素法的基本思想：就近尽量满足供应31 346 301 040303 0300用闭回路法进行最优性检验用闭回路法进行最优性检验 1 1、找空格的闭回路、找空格的闭回路：以某空格为起点，用水平线或垂以某空格为起点，用水平线或垂直线向前划，只能在碰到某一数字格时才能转弯，按照这一直线向前划，只能在碰到某一数字格时才能转弯，
4、按照这一规则继续前进，直到回到起始的空格为止。规则继续前进，直到回到起始的空格为止。31 34 6 32 2、根据闭回路计算空格的检验数：、根据闭回路计算空格的检验数：检验数检验数 =奇数顶点的单位运价之和奇数顶点的单位运价之和 偶数顶点的单位运价之和偶数顶点的单位运价之和 31 346 3121-11012检验数检验数的经济的经济含义：含义：当由产当由产地地Ai往往销地销地Bj增运一增运一个单位个单位货物时货物时所引起所引起的总运的总运输成本输成本的变化的变化数数结论：若所有检验数都大于等于结论：若所有检验数都大于等于0 0，则当前方案最优，则当前方案最优31 346 3-11211012对
5、现有方案进行调整对现有方案进行调整 在负的检验数中选择绝对值最大的空格，在方案表中从该空在负的检验数中选择绝对值最大的空格，在方案表中从该空格出发，沿着其闭回路依次标上格出发，沿着其闭回路依次标上“+q+q”、“-q-q”，+q-q+q-q 其中其中q q表示最大调整量，它的取值为标表示最大调整量，它的取值为标“-q-q”的数字中最小的数值。的数字中最小的数值。于是于是q=min3,1=1q=min3,1=1调整后的方案为调整后的方案为 31 3 56 20221912 五、应用举例五、应用举例 例例、甲乙丙三座城市所需煤炭由、甲乙丙三座城市所需煤炭由A,B两个煤矿供两个煤矿供应，有关数据如表
6、所示，单位运费为万元应，有关数据如表所示，单位运费为万元/万吨，万吨，产销关系为如下图所示。由于需求大于供应，经研产销关系为如下图所示。由于需求大于供应，经研究，甲城市供应量可减少究，甲城市供应量可减少030万吨，乙城市必须万吨，乙城市必须全部满足，丙城市供应量不少于全部满足，丙城市供应量不少于270万吨，求将供万吨，求将供应量全部分完又使总运费最低的调运方案应量全部分完又使总运费最低的调运方案?甲甲乙乙丙丙产量产量A151822400B212516450销量销量320250350甲甲乙乙丙丙产量产量A151822400B212516450最高最高最低最低320290250250350270甲甲甲甲乙乙丙丙丙丙产量产量A1515182222400B2121251616450CM0MM0702903025027080甲甲甲甲乙乙丙丙丙丙产量产量A1515015182502222400B211402125162701640450CM030MM04070销量销量2903025027080