运筹学运输问题.ppt

《运筹学运输问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章运输与指派问题运输问题的表示运输问题模型、运价表运输问题的求解表上作业法指派问题运输、指派和转运问题，实际上都可以用L.P.模型加以描述，所以可以认为它们是L.P.的特例单列一章的原因在于：应用面极广，实践性很强，而特有的数学结构使得人们设计出了特别有效的方法对此类模型进行求解本章的重点在：掌握表格化方法求解运输简述提出问题有A1，A2，A3三个砖瓦厂月产量分别为14，27，19万块，供应B1，B2，B3，B4四个工地，月需要量分别为22，13，12，13万块，每万块运费如下表，求总运费最少的方案。A114A227A31

2、922131213B1B2B3B46(千元）753842759106运输问题运输问题线性规划模型供应地约束需求地约束3.1运输问题模型与性质一、运输问题的数学模型1、运输问题的一般提法：某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？运输问题的一般数学模型有m个产地生产某种物资，有n个地区需要该类物资令a1,a2,…,am表示各产地产量，b1,b2,…,bn表示各销地

3、的销量，ai=bj称为产销平衡设xij表示产地i运往销地j的物资量，cij表示对应的单位运费，则我们有运输问题的数学模型如下：运输问题二、运输问题的特点与性质1．约束方程组的系数矩阵具有特殊的结构写出式（3-1）的系数矩阵A，形式如下：m行n行矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0；列向量Pij=(0,…，0，1，0，…,0,1,0,…0)T，其中两个元素1分别处于第i行和第m+j行。三、运输问题的求解方法1、单纯形法（为什麽？）2、表上作业法由于问题的特殊形式而采用的更简洁、更方便的方法3.2

4、运输问题的表上作业法一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图3-1所示。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。确定初始方案(初始基本可行解)改进调整（换基迭代）否判定是否最优？是结束最优方案图3-1运输问题求解思路图二、初始方案的确定1、作业表（产销平衡表）初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。表3-3是两个产地、三个销地的运输问题作业表。调销地

5、运量产地B1B2B3产量A1c11X11c12X12c13X13a1A2c21X21c22X22c23X23a2销量b1b2b3表3-3运输问题作业表（运价表）3、举例例3-2甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4，求使总运输量最少的调运方案。表3-4例3-2有关信息表450200150100日销量（需求量）250756580乙2001007090甲日产量（供应量）CBA运距城市煤矿例3-2的数学模型初始解的确定一、最小元素法&最小元素法的基本思想是“就近供应”；

6、二、西北角法&西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同；三、沃格尔法（VOGLE）调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用最小元素法确定例3-2初始调运方案150100100100100100100调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用西北角法确定例3-2初

7、始调运方案1001001005050200200得到初始调运方案为：x11=100，x12=100，x22=50，x23=200元素差额法（Vogel近似法）最小元素法只考虑了局部运输费用最小。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案前一种按最小元素法求得，总运费是Z1=10×8+5×2+15×1=105后一种方案考虑到C11与C21之间的差额是8－2=6，先调运x

8、21，再是x22，其次是x12这时总运费Z2=10×5+15×2+5×1=85