[理学]运筹学06-运输问题

《[理学]运筹学06-运输问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章运输问题6.1运输问题的数学模型6.2初始基可行解的确定6.3最优性检验与基可行解的改进6.4其他运输问题运输问题（纺纱厂）工厂123库存仓121350222430库334210需求401535运输单价求：运输费用最小的运输方案。解：设xij为i仓库运到j工厂的原棉数量其中：i＝1，2，3j＝1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x1350x21+x22+x2330x31+x32+x3310x11+x21+x31≥40x12+x22+x32≥15x13+x23+x3

2、3≥35xij0s.t类似的例子：教材P6-P7，例36.1运输问题的数学模型若一家公司拥有多个工厂，这些工厂位于不同的地点，并且生产同一种产品。这些产品要运输到不同的地点，以满足用户的需求（或者如前例中类似的问题）。供应节点：这些工厂，它们是运输的起点；需求节点：用户所在点，它们是运输的终点或目的地。同时假定产品不能在供应节点之间运输，也不能在需求节点之间运输。公司面临的问题是：应如何组织运输，才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下，使得运输成本最低。这类问题就是运输问题。(1)运输问题数学模型xij——供应节点i至需求节点j的运输量

3、；ai——供应节点i的可供应量，i=1,2,…,m；bj——需求节点j的需求量，j=1,2,…,n；cij——供应节点i至需求节点j的单位运输成本。根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：平衡型运输问题和不平衡型运输问题。平衡型运输问题：不平衡型运输问题：对于不平衡型运输问题通常通过设立虚拟供应节点或虚拟需求节点将其转化为平衡型运输问题求解。(2)运输问题的分类平衡型运输问题的数学模型模型包含变量：m×n个约束方程：m+n个秩：r(A)=m+n-1m行n行(3)运输问题的特征定理：平衡运输问题必有可行解与最优解。证：对于平衡运输问题令：则有

4、所以是运输问题的一个可行解。又由于所以且为极小化问题，故一定存在最优解。运输问题是一类特殊的线性规划问题对于平衡型运输问题：约束方程数为m+n个，但有一个冗余方程，所以独立方程数为m+n-1个，即秩r(A)=m+n-1。存在最优解当供应量和需求量均为整数时，存在整数最优解。基可行解中基变量个数为m+n-1个运输问题的基本性质例：海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分厂生产同一个设备，设每月的生产能力分别为14台、27台和19台。海华设备厂有四个固定的用户，该四个用户下月的设备需求量分别为22台、13台、12台和13台。设各分厂的生产成本相同，

5、从各分厂到各用户的单位设备运输成本如下表所示，而且各分厂本月末的设备库存量为零。问该厂应如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。2321341sB=27sC=19d1=22d2=13d3=12d4=13sA=14供应量供应节点运输成本需求量需求节点6753842759106海华设备厂运输问题网络图海华设备厂运输问题的表格表示供应量约束需求量约束海华设备厂运输问题线性规划模型不平衡运输问题(1)：供过于求设置虚拟需求节点232131sB=27sC=19d1=22d2=13d3=12sA=14供应量需求量6758425910供应节

6、点运输成本需求节点4d4=13000不平衡运输问题(2)：供不应求设置虚拟供应节点221341sB=27d1=22d2=13d3=12d4=13sA=14供应量需求量67538427供应节点运输成本需求节点3sC=1900006.2初始基可行解的确定两种获得基可行解的常用方法：西北角法最小元素法813131466(1)西北角法(2)最小元素法(0)(2)最小元素法(1)(2)最小元素法(2)(2)最小元素法(3)(2)最小元素法(4)(2)最小元素法(5)(2)最小元素法(6)6.3最优性检验与基可行解的改进(1)最优性检验充要条件由于基变量的检验数σij=0

7、,只需确定非基变量的检验数！确定非基变量检验数的常用方法主要是：闭回路法——一个非基变量与某些基变量构成唯一闭回路,基可行解中基变量不含闭回路。位势法——利用对偶变量定义：凡能排列成形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个闭回路。构成回路的诸变量称为闭回路的顶点；连接相邻两个顶点的线段称为闭回路的边。或每个顶点都是转角点；每一条边都是水平线段或垂直线段；每一行或列若有闭回路的顶点，则必有两个几何性质(1)x12,x13,x33,x32(2)x23,x13,x14,x34,x31,x21转角点转角点(2)闭回路法(0)5(2)闭回路法(1

8、)σ12=c12-c11+c21-c2