运筹学课件三运输问题.ppt

第三章 运输问题 ?第一节 运输问题及其数学模型 一、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？ 2、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足： 运输问题的数学模型 3、举例 例某部门有3个生产同类产品的工厂，生产的产品由4个地点销售，各个供应地、目的地的生产量、销售量以及各个供应地到目的地的运费见表，求使总运输量最少的调运方案。 1、最小元素法 Z=10X4+6X11+8X2+2X3+14X5+8X6=246 网络作业: 作业1:下载 lingo软件,安装使用。 将下载网址存放在一个word文件，以附件形式发到下列邮箱： 1+0501：yunchouxue1_0501@163.com 1+0502： yunchouxue1_0502@163.com 要求： 主题：学号姓名1（052820528刘学菊1） 附件文件名称：学号姓名1 （052820528刘学菊1） 作业1的截止日期：第7周 作业2:上网查询一个生产计划或混合配料或资金分配线性规划问题，内容包括：问题的提出；数据表格的建立；数学模型的建立；lingo软件求解；灵敏度分析。 将形成的文件为word文档 ，以附件形式发到下列邮箱： 1+0501：yunchouxue1_0501@163.com 1+0502： yunchouxue1_0502@163.com 要求： 1、数学模型用数学公式编辑器写。 2、标题3号宋体加粗；小标题小3号黑体；正文小4号宋体；行距固定值18磅； 3、主题：学号姓名2（052820528刘学菊2） 4、附件文件名称：学号姓名2 （052820528刘学菊2） 作业2的截止日期：第8周 作业3:将作业2做成ppt，数量不小于15幅，将形成的文件以附件形式发到下列邮箱： 1+0501：yunchouxue1_0501@163.com 1+0502： yunchouxue1_0502@163.com 要求： 1、数学模型用数学公式编辑器写。 2、主题：学号姓名3（052820528刘学菊3） 3、附件文件名称：学号姓名3 （052820528刘学菊3） 作业3的截止日期：第9周 * 运筹学教程 * 模型及其特点 求解思路及相关理论 求解方法——表上作业法 运输问题的推广 1 、产销不平衡的运输问题 2 、转运问题 单位根据具体问题选择确定。 表 有关信息 单位 运价 销 或运距 地产地 ? B1 B2 … Bn ? 产 量 A1 A2 ┆ Am x11c11 x12c12 … x13c1 n X21 c21 x22c22 … c2n … … … xm1cm1 xm2cm2 xmncm n a1 a2 ┆ am ? 销 量 ? ? b1 b2 … bn 同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足： 总运费为： 二、运输问题数学模型的特点 1．约束方程组的系数矩阵具有特殊的结构 系数矩阵A，形式如下： m行 n行 2.运输问题的基变量总数是m + n -1 写出增广矩阵 每一列只有两个元素为1，其余元素均为0； 列向量Pij =(0,…，0，1，0，…,0,1,0,…0)T，其中两个元素1分别处于第i行和第m+j行。 将该矩阵分块，特点是：前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0(k=1，…，m）；后n行构成m个n阶单位阵 证明系数矩阵A及其增广矩阵的秩都是m+n-1 前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此 的秩小于m+n； ？ 因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1 由 的第二至m+n行和前n列及