运筹学06-运输问题

《运筹学06-运输问题》由会员分享，可在线阅读，更多相关《运筹学06-运输问题（76页珍藏版）》请在金锄头文库上搜索。

1、第六章 运输问题6.1 运输问题的数学模型6.2 初始基可行解的确定6.3 最优性检验与基可行解的改进6.4 其他运输问题*16.1 运输问题的数学模型n若一家公司拥有多个工厂，这些工厂位于不同的地点 ，并且生产同一种产品。这些产品要运输到不同的地 点，以满足用户的需求。n供应节点：这些工厂，它们是运输的起点；n需求节点：用户所在点，它们是运输的终点或目的地 。n同时假定产品不能在供应节点之间运输，也不能在需 求节点之间运输。n公司面临的问题是：应如何组织运输，才能在满足供 应节点的供应量约束和需求节点的需求量约束的前提 下，使得运输成本最低。n这类问题就是运输问题。Date2(1) 运输问题

2、数学模型xij 供应节点i至需求节点j的运输量；aij 供应节点i的可供应量，i=1,2, ,m；bij 需求节点j的需求量，j=1,2,n；cij 供应节点i至需求节点j的单位运输成本。Date3n根据运输问题中总供应量与总需求量的关系可将运输 问题分为两类：n平衡型运输问题和不平衡型运输问题。平衡型运输问题：不平衡型运输问题：l对于不平衡型运输问题通常通过设立虚拟供应节点或 虚拟需求节点将其转化为平衡型运输问题求解。(2) 运输问题的分类Date4平衡型运输问题的数学模型模型包含变量：mn个约束方程：m+n个秩：r(A)=m+n-1 m 行n 行稀疏矩阵Date5(3) 运输问题的特征定理

3、：平衡运输问题必有可行解与最优解。证：对于平衡运输问题令：Date6则有所以 是运输问题的一个可行解。又由于所以且为极小化问题，故一定存在最优解。Date7定义：凡能排列成形式的变量集合，用一条封闭折线将它们连接起来形成 的图形称之为一个闭回路。构成回路的诸变量称为闭回路的顶点；连接相邻两个顶点的线段称为闭回路的边。或每个顶点都是转角点；每一条边都是水平线段或垂直线段；每一行或列若有闭回路的顶点，则必有两个几何 性质Date8(1) x12,x13,x33,x32(2) x23,x13,x14 ,x34 ,x31 , x21转角点转角点Date9n运输问题是一类特殊的线性规划问题n对于平衡型运

4、输问题：q约束方程数为m+n个，但有一个冗余方程，所 以独立方程数为m+n-1个，即秩r(A)=m+n-1。q存在最优解q当供应量和需求量均为整数时，存在整数最优 解。q基可行解中基变量个数为m+n-1个q基可行解中基变量的重要特征：不含闭回路。q任何一个非基变量与基变量含且仅含一个闭回 路。运输问题的基本性质Date10(4) 平衡型运输问题的对偶问题由于r(A)=m+n-1， 独立的约束方程 个数为m+n-1; 而变量个数为m+n， 则其中有一个自 由变量Date11例：海华设备厂下设三个位于不同地点的分厂A，B，C，该 三个分厂生产同一个设备，设每月的生产能力分别为14台、 27台和19

5、台。海华设备厂有四个固定的用户，该四个用户下 月的设备需求量分别为22台、13台、12台和13台。设各分厂 的生产成本相同，从各分厂到各用户的单位设备运输成本如 下表所示，而且各分厂本月末的设备库存量为零。l问该厂应如何安排下月的生产与运输，才能在满足四个用 户需求的前提下使总运输成本最低。Date122321341sB=27sC=19d1=22d2=13d3=12d4=13sA=14供应量供应节点运输成本需求量需求节点6 7 53 8 4 2 759 10 6海华设备厂运输问题网络图运输问题网络图Date13海华设备厂运输问题的表格表示Date14供应量约束需求量约束海华设备厂运输问题线性规

6、划模型Date15不平衡运输问题不平衡运输问题(1)(1)：供过于求：供过于求设置虚拟需求节点设置虚拟需求节点232131sB=27sC=19d1=22d2=13d3=12sA=14供应量需求量6 7 58 4 259 10供应节点运输成本需求节点4d4=13000Date16不平衡运输问题不平衡运输问题(2)(2)：供不应求：供不应求设置虚拟供应节点设置虚拟供应节点221341sB=27d1=22d2=13d3=12d4=13sA=14供应量需求量6 7 53 8 4 2 7供应节点运输成本需求节点3sC=1900 0 0Date176.2 初始基可行解的确定获得初始基可行解的常用方法：n西

7、北角法n最小元素法nVogel法Date18813131466(1) 西北角法Date19(2) 最小元素法(0)Date20(2) 最小元素法(1)Date21(2) 最小元素法(2)Date22(2) 最小元素法(3)Date23(2) 最小元素法(4)Date24(2) 最小元素法(5)Date25(2) 最小元素法(6)Date26(3) Vogel 法2211333123311331314413131912Date276.3 最优性检验与基可行解的改进(1) 最优性检验充要条件l由于基变量的检验数ij= 0,只需确定非基变量的检验 数！l确定非基变量检验数的常用方法主要是：l闭回路法

8、非基变量与基变量构成唯一闭回路l位势法利用对偶变量Date28(2) 闭回路法(0)Date295(2) 闭回路法(1)12= c12-c11+c21-c22=7-6+8-4=5Date30-55(2) 闭回路法(2)13= c13-c11+c21-c23=5-6+8-2=5Date31557(2) 闭回路法(3)14= c14-c11+c21-c23 +c33-c34 =3-6+8-2+10-6=7Date32755924= c24-c23+c33-c34=7-2+10-6=9(2) 闭回路法(4)Date337955-1131= c31-c33+c23-c21=5-10+2-8=-11(2

9、) 闭回路法(5)Date347559-11-332= c32-c33+c23-c22=9-10+2-4=-3(2) 闭回路法(6)Date35(3) 位势法对偶规划由于对偶变 量的个数为 m+n，而系 数矩阵的秩 为m+n-1， 我们可以通 过设定自由 变量的值得 到所有对偶 变量。Date36(3) 位势法(0)Date37选择含基变量最多的行或列，令相应的u或v为零。(3) 位势法(1)Date38v1=c21- u2=8-0=8, v2=c22- u2=4-0=4, v3=c23- u2=2-0=2(3) 位势法(2)Date39u1=c11-v1=6-8=-2, u3 =c33- v

10、3=10-2=8(3) 位势法(3)Date40v4=c34-u3=6-8=-2(3) 位势法(4)Date41(3) 位势法(5)512 =c12-(u1+ v2) =7-(-2+4)=5Date425(3) 位势法(6)513 =c13-(u1+ v3) =5-(-2+2)=5Date43(3) 位势法(7)75514 =c14-(u1+ v4) =3-(-2-2)=7Date44(3) 位势法(8)75524 =c24-(u2+ v4) =7-(0-2)=99Date45(3) 位势法(9)755931 =c31-(u3+ v1) =5-(8+8)=-11-11Date46(3) 位势法

11、(10)7559-1132 =c32-(u3+ v2) =9-(8+4)=-3-3Date47(4) 基可行解的改进l选择检验数绝对值最大的非基变量为 进基变量(存在多个时任选一个)确定进基变量确定离基变量l选择包含进基变量的闭回路上距进 基变量奇次的变量中运量最小的基变 量为离基变量。运量调整重复上述步骤直至所有检验数大于零，即获得最优解。Date489755-11-3确定进基变量选择检验数绝对值最大的非基变量为进基变量Date499755-11-3确定闭回路Date509755-11-3确定离基变量Date519755-3调整运量6x31=6, x21=8-6=2, x23=6+6=12D

12、ate52-2-4558进一步优化(0)11Date53-2-4558进一步优化(1)11x13 进基， x34离基。Date5424558进一步优化(2)11所有非基变量的检验数均大于零，即为最优解。Date55(1) 产销不平衡的运输问题例：有三个化肥厂供应四个地区的农用化肥。等量化肥在 这些地区使用效果相同。相关数据如下表，试分析总运 费最节省的化肥调运方案。 需求地区 化肥厂B1B2B3B4产量（万吨）A11613221750A21413191560A3192023-50最低需求（万吨） 最高需求（万吨）30 5070 700 3010不限运价：万元/万吨6.4 其他运输问题Date5

13、6分析：这是一个产销不平衡的运输问题，总产量为160万吨 ，四个地区的最低需求为110万吨，最高需求为无限。 根据现有产量，地区B4每年最多能分配到60万吨，这 样最高总需求为210万吨，大于产量。为了求得平衡， 在产销平衡表中增加一个虚拟的化肥厂D ，其年产量 为50万吨。由于各个地区的需要量包含两部分，如地 区B1，其中30万吨是最低需求，故不能由虚拟的化肥 厂D供给，令其相应的运输价格为M（任意大正数）， 而另一部分20万吨满足或不满足均可，因此可以由虚 拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡是需求分两种情况的地区，实际 上可按照两个地区看待。这样可以建立这个

14、问题的产 销平衡表Date57产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 产量销量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716131340132014196015M131520 50MDate58产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 UiVj13501430132019015102330M2002003001301419154-4+M4-M-4+M220-M3221-M18-M19-M119-M3M-192M-182M-17M-232

15、M-19162217171415191920MMM0M16030202030Date59产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 UiVj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M16Date60产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 UiVj16135022171714101420132019151015192019202330MM0M0M0M05016 0055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+M-23+M-20+2M10200Date61产销平衡表A1A2A3DB1 B1 B2 B3 B4