运筹学-.运输问题

1、运筹学.运输问题第1页，共42页，2022年，5月20日，18点42分，星期三一、运输问题的数学模型1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？3.1 运输问题的典例和数学模型第2页，共42页，2022年，5月20日，18点42分，星期三例1：产量：A1-7t，A2-4t，A3-9t 销量：B1-3t，B2-6t，B3-5t，B4-6t BjAiB1B2B3B4产量A13113107A219284A37

2、41059需量365620第3页，共42页，2022年，5月20日，18点42分，星期三单位根据具体问题选择确定。 产销平衡、单位运价表（表3-1）单位 运价 销 或运距 地产地 B1 B2 Bn 产 量 A1 A2 Am c11 c12 c1 n c21 c22 c2n cm1 cm2 cm n a1 a2 am 销 量 b1 b2 bn 第4页，共42页，2022年，5月20日，18点42分，星期三 2、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量（i=1，m；j=1，n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足： 第5页，共42页，2022年，5

3、月20日，18点42分，星期三同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足： 总运费为： 第6页，共42页，2022年，5月20日，18点42分，星期三运输问题的数学模型第7页，共42页，2022年，5月20日，18点42分，星期三二、运输问题的特点与性质1约束方程组的系数矩阵具有特殊的结构写出式（3-1）的系数矩阵A，形式如下：m行n行第8页，共42页，2022年，5月20日，18点42分，星期三 矩阵的元素均为1或0； 每一列只有两个元素为1，其余元素均为0； 列向量Pij =(0,，0，1，0，,0,1,0,0)T，其中两个元素1分别处于第i行和第m+j行。 将该矩

4、阵分块，特点是：前m行构成m个mn阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，m）；后n行构成m个n阶单位阵。第9页，共42页，2022年，5月20日，18点42分，星期三例1 的数学模型第10页，共42页，2022年，5月20日，18点42分，星期三三、运输问题的求解方法1、单纯形法（为什么？）2、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法第11页，共42页，2022年，5月20日，18点42分，星期三3.2 运输问题的表上作业法 一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案

5、，如图3-1所示。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。第12页，共42页，2022年，5月20日，18点42分，星期三 确定初始方案( 初 始 基本可行解) 改进调整（换基迭代）否 判定是否 最 优？是结 束最优方案图3-1 运输问题求解思路图第13页，共42页，2022年，5月20日，18点42分，星期三 二、 初始方案的确定 1、作业表（产销平衡表） 初始方案就是初始基本可行解。 将运输问题的有关信息表和决策变量调运量结合在一起构成“作业表”（产销平衡表）。 表3-2是两个产地、三个销地的运输问题作业表。 第14页，共42页，2022年，5月20日，18点42分，

6、星期三调 销地 运 量产地 B1 B2 B3 产 量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销 量 b1 b2 b3表3-2 运输问题作业表（产销平衡表） 第15页，共42页，2022年，5月20日，18点42分，星期三其中xij是决策变量，表示待确定的从第i个产地到第j个销地的调运量，cij为从第i个产地到第j个销地的单位运价或运距。2、确定初始方案的步骤：（1）选择一个xij，令xij= minai，bj= 将具体数值填入xij在表中的位置；第16页，共42页，2022年，5月20日，18点42分，星期三（2

7、）调整产销剩余数量：从ai和bj中分别减去xij的值，若ai-xij=0，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai；若bj-xij =0，则划去销地Bj所在的列，说明该销地需求已得到满足，而产地Ai尚有存余量ai-bj；（3）当作业表中所有的行或列均被划去，说明所有的产量均已运到各个销地，需求全部满足，xij的取值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（2）。第17页，共42页，2022年，5月20日，18点42分，星期三 按照上述步骤产生的一组变量必定不构成闭回路，其取值非负，且总数是m+n-1个，因此构成运输问题的

8、基本可行解。 对xij的选择采用不同的规则就形成各种不同的方法，比如每次总是在作业表剩余的格子中选择运价（或运距）最小者对应的xij，则构成最小元素法，若每次都选择左上角格子对应的xij就形成西北角法（也称左上角法）。第18页，共42页，2022年，5月20日，18点42分，星期三3、举例 例1： 产量：A1-7t，A2-4t，A3-9t 销量：B1-3t，B2-6t，B3-5t，B4-6t ；求使总运输量最少的调运方案。 第19页，共42页，2022年，5月20日，18点42分，星期三 BjAiB1B2B3B4产量A13113107A219284A3741059需量365620第20页，共4

9、2页，2022年，5月20日，18点42分，星期三1、最小元素法: 求出初始方案。& 最小元素法的基本思想是“就近供应” 第21页，共42页，2022年，5月20日，18点42分，星期三 BjAiB1B2B3B4产量A13113107A219284A3741059需量365620用最小元素法确定例1初始调运方案 3114436333第22页，共42页，2022年，5月20日，18点42分，星期三最小元素法实施步骤口诀运价表上找最小，平衡表上定产销； 满足销量划去“列”，修改“行产”要记牢；（满足产量划去“行”，修改“列销”要记牢） 划去列(行)对运价， 修改“行产(列销)”在产销； 余表再来找

10、最小，方案很快就找到。第23页，共42页，2022年，5月20日，18点42分，星期三2、Vogel法(元素差额法): 求出初始方案。第一步：在表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。 第24页，共42页，2022年，5月20日，18点42分，星期三用Vogel法确定初始调运方案 BjAiB1B2B3B4产量行差额A13113107A219284A3741059需量36562 0列差额 Bj AiB1B2B3B4产量A1527A2314A3639需量365620第25页，共42页，2022

11、年，5月20日，18点42分，星期三 三、最优性检验 检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。第26页，共42页，2022年，5月20日，18点42分，星期三1、闭回路法 以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。第27页，共42

12、页，2022年，5月20日，18点42分，星期三闭回路法计算非基变量xij检验数的公式：=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和） 当检验数还存在负数时，说明原方案还不是最优解。第28页，共42页，2022年，5月20日，18点42分，星期三闭回路法最小元素法初始方案 B1B2B3B4产量A13113107A219284A3741059需量365620 B1B2B3B4产量A1437A2314A3（10）639需量365620第29页，共42页，2022年，5月20日，18点42分，星期三检验数 B1B2B3B4产量A1（1）（2）437A23（1）1（1）4

13、A3（10）6（12）39需量365620第30页，共42页，2022年，5月20日，18点42分，星期三2、位势法 以例1初始调运方案为例，设置位势变量 和 ， 在初始调运方案表的基础上增加一行和一列。 BjAiB1B2B3B4ujA1311310u1A21928u2A374105u3viv1v2v3v4第31页，共42页，2022年，5月20日，18点42分，星期三检验数 各空格的检验数，令 代表空格（Ai ,Bj）的检验数。当检验数还存在负检验数时，说明未得到最优解，还可以改进。如果表中出现有负的检验数时，对方案进行改进和调整的访求同前面闭回路法调整一样。第32页，共42页，2022年，

14、5月20日，18点42分，星期三方案调整闭回路法 B1B2B3B4产量A1（1）（2）437A23（1）1（1）4A3（10）6（12）39需量365620第33页，共42页，2022年，5月20日，18点42分，星期三调整结果 B1B2B3B4产量A1（0）（2）527A23（2）（1）14A3（9）6（12）39需量365620第34页，共42页，2022年，5月20日，18点42分，星期三位势法计算非基变量xij检验数的公式=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和） 闭回路法计算非基变量xij检验数的公式：复习比较检验数计算的两种方法第35页，共42页，

15、2022年，5月20日，18点42分，星期三 四、方案调整 当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。 若检验数 小于零，则首先在作业表上以xij为起始变量作出闭回路，并求出调整量：ij=min该闭回路中奇数次顶点调运量xij第36页，共42页，2022年，5月20日，18点42分，星期三3.3 运输问题的推广一、产销不平衡的运输问题供大于求供不应求增加虚拟销地 增加虚拟产地 产销平衡的运输问题对应的运距（或运价） ？转化第37页，共42页，2022年，5月20日，18点42分，星期三二、转运问题特点是所调运的物资不是由产地直接运送到销地，而是经过若干中转站送达。求解思路：转化成一个等价的产销平衡运输问题，再用表上作业法求出最优调运方案。 如何转化 ？第38页，共42页，2022年，5月20日，18点42分，星期三第一步，将产地、转运点、销地重新编排，转运点既作为产地又作为销地；第二步，各地之间的运距（或运价）在原问题运距（运价）表基础上进行扩展：从一地运往自身的单位运距（运价）记为零，不存在运输线路的则记为M（一个足够大的正数）；第39页，共42页，2