运输问题表述课件.ppt
《运输问题表述课件.ppt》由会员分享,可在线阅读,更多相关《运输问题表述课件.ppt(67页珍藏版)》请在三一文库上搜索。
1、1,第三章 运输问题,本章主要内容: 运输问题的数学模型 运输问题的求解表上作业法 运输问题应用建模,2,第一节 运输问题的数学模型 第二节 表上作业法 第三节 产销不平衡的运输问题 第四节 应用举例,3,第一节 运输问题的数学模型,一、数学模型,例1,产地:货物发出的地点 销地:货物接收的地点 产量:各产地的可供货量 销量:各销地的货物需求量,运输问题就是研究如何组织调运,既满足各产地的产量和各销地的需求,又使得总运费最小。,4,二、运输问题的一般数学模型,设xij表示产地 i 运往销地 j 的物资量,cij表示对应的单位运费,令a1, a2, , am表示各产地产量, b1, b2, ,
2、bn表示各销地的销量,有m个地区生产某种物资,有n个地区需要该类物资,产销平衡表,单位运价表,5,一般满足产销平衡:,产量约束:由某一产地运往各个销售地的物品数 量之和等于该产地的产量。,销量约束:由各个产地运往某一销售地的物品数 量之和等于该销售地的销量。,6,产大于销,7,产小于销(销大于产),8,定理1 运输问题的数学模型必有最优解。 首先,运输问题一定有可行解;其次,任何单位运价cij0,从而对于任一可行解,必有目标函数值大于或等于零,即目标函数有下界。 所以,求解运输问题时,不需要进行无最优解的判别。,产量平衡(m个),销量平衡(n个),9,在例1中,运输问题的系数矩阵为:,1.一般
3、情况下,运输问题 决策变量xij的系数列向量为:,三、变量xij的系数列向量的特征,2.系数矩阵的元素等于0或1。,10,3.运输问题系数矩阵的秩为m+n-1。,3.运输问题基变量的个数为m+n-1。,11,概念,例2,1)数字格,2)空格,3)闭回路,四、闭回路,闭回路:以某空格为起点,用水平或垂直线划,只有当碰到某恰当的数字格后,才能转900继续前进,直到回到起始空格为止。,12,13,14,15,16,17,18,2.闭回路与变量所对应的系数列向量组线性相关性的关系,结论1 运输问题一组变量构成闭回路的充要条件是这组变量所对应的系数列向量线性相关,例如,闭回路(x11, x21, x23
4、, x13),19,闭回路与变量所对应的系数列向量组线性相关性的关系,结论2 运输问题的一个可行解是基可行解的充要条件是:,1)数字格的个数为m+n-1个;,2) 这m+n-1个数字格不构成闭回路。,结论3 对每一个空格处,有且仅有一条闭回路。,20,一、表上作业法的步骤,第二节 表上作业法,最优性检验,结 束,Y,调 整,N,确定初始 基可行解,在mn维产销平衡表上找到m+n-1个数字格,确定进基变量和出基变量,21,表上作业法步骤:初始方案、最优性检验、改进方案 一、初始方案的确定 1.最小元素法 2.伏格尔法 二、最优性检验 1.闭回路法 2.位势法 三、改进方案 在闭回路内改进,22,
5、1.最小元素法(就近供应) 就近供应,即从单位运价表中最小的运价开始确定供销关系,然后次小,一直到求出初始基可行解为止。,例3,二、初始基可行解的确定,23,例3,最小元素法给出的初始解是运输问题的基可行解。,24,2.伏格尔法(Vogel),第一步:求出每行次小运价与最小运价之差;同时求出每列次小运价和最小运价之差; 第二步:找出所有行、列差额的最大值,差额最大值所对应的行或列中的最小运价处先调运; 第三步:这时必有一列或一行调运完毕,划去该列或该行,在剩下的运价中再求最大差额,进行第二次调运,依次进行下去,直到最后全部调运完毕,得到一个调运方案。,25,2.伏格尔法(Vogel),例4,2
6、6,在以上两种方法中,有几点需要注意:,这两种方法得出的解均为初始可行解。,一般由伏格尔法得出的解比最小元素法得出的解更接近最优解。,在以上方法过程中,不可同时划去行和列。,27,1.闭回路法 例5,注: 1)数字格检验数均为0,显然该问题至此尚未达到最优解。,三、求检验数并进行最优解的判定,1,2,1,-1,10,12,28,29,30,31,32,33,34,2.位势法,例6 由最小元素法得出初始解,如下表,3)行势、列势可不唯一,但检验数是一致的。,35,位势法的计算过程,令u1=0,按ui+vj=cij相继确定其他数字格的ui和vj,计算空格的检验数。如 11=3-(0+2)=1,因为
7、24=-10,因而该问题至此尚未达到最优解.,0,3,10,-1,-5,2,9,1,2,1,-1,10,12,36,位势法的理论依据(互补松弛定理),37,位势法的理论依据,运输问题,设B为一可行基,则相应的基可行解的各变量的检验数为,运输问题的对偶问题,由对偶理论有 Y=CBB-1,基变量的检验数等于0,(I:基变量下标集),38,位势法的步骤,对于每一个基变量(数字格)都按照公式 ui+vj=cij 列出一个位势方程,形成位势方程组(m+n1个); 任意决定其中一个位势的数值,然后求出其他位势的数值; 按照公式 计算非基变量(空格处)的检验数(mn-(m+n1)个)。,39,从最小负检验数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运输 问题 表述 课件
链接地址:https://www.31doc.com/p-4200410.html