运输问题v运输问题及其数学模型v运输问题的表上作业法v运输问题的进一步讨论例1：某部门有3个消费同类产品的工厂产地，消费的产品由4个销售点销地出卖，各工厂的消费量、各销售点的销售量假定单位均为t以及各工厂到各销售点的单位运价元/t示于下表中要求研讨产品如何调运才干使总运费最小 4.1 运输问题及其数学模型单位 销地 运价产地产量2910291342584257销量3846A2A3B2A1B3B4B1s2=5s3=7d1=3d2=8d3=4d4=6s1=9供应量供应地运价需求量需求地2910213428425运输问题网络图运输问题网络图产量约束销量约束运输问题的普通提法是：设某种物资有 个产地各产地的产量是有 个销地各销地的销量是假定从产地 到销地运输单位物品的运价是 ，问怎样调运这些物品才干使总运费最小？ 销地产地产量销 量运价表当产销平衡时，其模型如下：当产大于销时，其模型是：当产小于销时，其模型是： 1 1、平衡运输问题必有可行解，也、平衡运输问题必有可行解，也必有最优解；必有最优解；运输问题数学模型的特点运输问题数学模型的特点证明 记那么令那么 为运输问题的一个可行解。现实上：又因所以故 是一组可行解。又由于总费用不会为负值存在下界。这阐明，运输问题既有可行解，又必然有下界存在，因此一定有最优解存在。 2 2、运输问题约束条件的系数矩阵、运输问题约束条件的系数矩阵运输问题数学模型的特点运输问题数学模型的特点对运输问题数学模型的构造约束加以整理，可知其系数矩阵具有下述方式：m行n行1运输问题是一个具有mn个变量和n+m个等型约束的线性规划问题。 412运输问题约束方程组的系数矩阵是一个只需0和1两个数值的稀疏矩阵,其中1的总数为 2mn 个。3、约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次4、约束条件系数矩阵的秩是m+n-1。即运输问题的基变量总数是m+n-1证明：因A的前m行对应元素的和与后n行对应元素的和相等，恰好都是：所以A的行向量是线性相关的。从而 r(A)m+n.去掉A的第一行，并取如下m+n-1列，得到m+n-1阶子式所以 r(A)=m+n-1.对于产销平衡运输问题，除了上述特点外，还有以下特点： 1 一切构造约束条件都是等式约束 2 各产地产量之和等于各销地销量之和 3 3、运输问题的解、运输问题的解运输问题数学模型的特点运输问题数学模型的特点运输问题是一种线性规划问题。前面讲述的单纯形法是求解线性规划问题非常有效的普通方法，因此可用单纯形法求解运输问题。但是当用单纯形法求解运输问题时，先得在每个约束条件中引入一个人工变量，这样一来，即使对于m=3、n=4这样简单的运输问题，变量数目也会到达19个之多。因此，我们利用运输问题数学模型的特点，引入了表上作业法来求解运输问题 4.2 用表上作业法求解运输问题表上作业法的根本思想：先设法给出一个初始方案,然后根据确定的判别准那么对初始方案进展检查、调整、改良，直至求出最优方案，如以下图所示。初始化最优性检验迭代Iteration最优？yesSTOPno这和单纯形法的求解思想完全一致，但是详细的作法那么更加简捷。例1 某部门有3个同类型的工厂产地，消费的产品由4个销售点出卖，各工厂的消费量、各销售点的销售量假定单位为t以及各工厂到销售点的单位运价元/t示于表4-2中，问如何调运才干使总运费最小？ 销地产地产量4124111621039108511622销 量814121448表 4-2该运输问题的数学模型为：可以证明：约束矩阵的秩 r (A) = m +n -1.基变量的个数为 m+n-1.表上作业法v计算步骤：v1、给出初始方案v2、检验能否最优v3、调整调运方案 , Go to 2表上作业法v计算步骤：v1、给出初始方案v2、检验能否最优v3、调整调运方案 , Go to 2下面引见三种常用的方法。一、给出运输问题的初始可行解初始调运方案l最小元素法l西北角法l沃格尔(Vogel)法1。最小元素法思想：优先满足运价或运距最小的供销业务。 销地产地产量 4124111610398511622销 量14121448表 3-2 销地产地产量 412411162109108511622销 量 8141448表 3-2 销地产地产量 412112109108511622销 量 814121448表 3-2 销地产地产量 4121182109108116销 量 8121448表 3-2 销地产地产量 412118210910811销 量 81248表 3-2 销地产地产量 4128210910811销 量 81248表 3-2此时得到一个初始调运方案初始可行解：其他变量全等于零。总运费为目的函数值此解满足一切约束条件，且基变量非零变量的个数为6等于m+n-1=3+4-1=6). 西北角法西北角法是优先满足运输表中西北角左上角上空格的供销需求。 销地产地产量41241121039108511622销 量14121448表 3-2 销地产地产量 41241121039108511622销 量14121448表 3-2 销地产地产量 41241121039108511622销 量121448表 3-2 销地产地产量 41241121039108511622销 量14121448表 3-2 销地产地产量 412411210398511622销 量14121448表 3-2 销地产地产量 412411210398511622销 量14121448表 3-2 销地产地产量 412411210398511622销 量141448表 3-2 销地产地产量 412411210398511622销 量14121448表 3-2 销地产地产量 4124112103985116销 量14121448表 3-2 销地产地产量 4124112103985116销 量14121448表 3-2 销地产地产量 4124112103985116销 量141248表 3-2 销地产地产量 4124112103985116销 量14121448表 3-2此时得到一个初始调运方案初始可行解：其他变量全等于零。总运费为目的函数值此解满足一切约束条件，且基变量非零变量的个数为6等于m+n-1=3+4-1=6). 沃格尔Vogel)法初看起来，最小元素法非常合理。但是，有时按某一最小单位运价安排物品调运时，却能够导致不得不采用运费很高的其他供销点，从而使整个运输费用添加。沃格尔法的思想： 对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。假设罚数的值不大，当不能按最小运价安排运输时呵斥的运费损失不大；反之，假设罚数的值很大，不按最小运价组织运输就会呵斥很大的损失，故应尽量按最大罚数安排运输。销 地产地产量行罚数1234124111602103910181161销 量8121448列罚数1251323销 地产地产量行罚数123 412411160021039101185112212销 量8141248列罚数1251322133销 地产地产量行罚数123 41241116000103911185112212销 量141248列罚数125132213321销 地产地产量行罚数456 41211710396851122销 量1448列罚数41256销 地产地产量行罚数456 412117010360851122销 量1448列罚数4125 26此时得到一个初始调运方案初始可行解：其他变量全等于零。总运费为目的函数值此解满足一切约束条件，且基变量非零变量的个数为6等于m+n-1=3+4-1=6).比较上述三种方法给出的初始基可行解，以沃格尔法给出的解的目的函数值最小，最小元素法次之，西北角法解的目的函数值最大。 普通说来，沃格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似值。 销地产地产量 414681250837514销 量656320课堂练习课堂练习表上作业法v计算步骤：v1、给出初始方案v2、检验能否最优v3、调整调运方案 , Go to 2二、解的最优性检验前面得到了初始基可行解，普通来说此解并非最优。下面引见最优性检验的两种方法。1 闭回路法(Cycle method)2 对偶变量法dual variable method也称为位势法 闭回路法cycle method)下面用最小元素法所确定的初始根本可行解来阐明。与单纯性原理一样，现目的是运费最少，故检验每一个非基变量对应于运输表中的空格的检验数能否假设一切空格的检验数全非负，那么不论怎样均不能使运输费用降低，即目的函数值已无法改良，这个解就是最优解 销地产地产量412104611168210239108145118622销 量814121448思索空格(A1,B1),想象由产地A1供应一个单位的物品给销地B1，为使运入销地B1的物品总量不大于它的销量，应将A2运到B1的物品数量减1，即将格子A2,B1中填入的数字8改为7；另一方面，为使产地A2运出的物品数量正好等于它的产量(保证新得到的解仍为基可行解)，应将A2运到B3的物品数量增1。同理A1运往B3的物品数量减1，A1运出的物品数量正好等于其产量按照上述想象，由产地A1供应1个单位物品给销地B1,由此引起的总运费变化是：根据检验数的定义，它正是非基变量x11(或者说空格(A1,B1)的检验数定义1：基变量有数字的对应的格为基格；非基变量空格对应的顶点为非基格。定义2：从每一空格非基格出发，沿程度或垂直方向前进，每碰到数字格转90o有些情况也可以不改动方向继续前进，直到回到出发的空格为止，由此构成的封锁的折线称为闭回路。规定：起始顶点的空格为第一顶点，那么 =闭回路上奇数次顶点运价之和 闭回路上偶数次顶点运价之和 销地产地产量412104611168210239108145118622销 量814121448表 3-2 销地产地产量 412104611168210239108145118622销 量814121448表 3-2 销地产地产量 412104611168210239108145118622销 量814121448表 3-2 销地产地产量 412104611168210239108145118622销 量814121448表 3-2 销地产地产量 412104611168210239108145118622销 量814121448表 3-2 销地产地产量 412104611168210239108145118622销 量814121448表 3-2 销地产地产量 412104611168210239108145118622销 量814121448表 3-2检验数中有负数，阐明原方案不是最优解。 对偶变量法位势法(dual variable method) 用闭回路法断定一个运输方案能否最优，需求找出一切空格的闭回路，并计算其检验数。当运输问题的产地和销地很多时，空格的数目很大，计算检验数的任务量很大，而用对偶变量法就简便得多。 对产销平衡运输问题，假设用u1,u2,um分别表示前m个约束等式相对应的对偶变量，用v1,v2vn 分别表示后n个等式相对应的对偶变量，即有对偶向量这时可将运输问题的对偶规划写成：前面学习知道，线性规划问题变量xj的检验数可表示为：由此可写出运输问题某变量xij(对应于运输表中(Ai,Bj)的检验数如下：其中 分别称为行位势、列位势。有基变量所对应的检验数为零，可从m+n-1个等式2.2解出一切的行位势、列位势。2.1可以证明，不论令 为何值， 一直不变。即 将不会随 的取值而改动。 为此，在求解方程组2.2时，为计算简便，可指定一个位势等于一个较小的整数或零。 销地产地产量412104611168210239108145118622销 量814121448表 3-2行位势列位势设u1=1当然，也可用采用解方程组的方法来求位势：两种方法任选一种 销地产地产量 412104611168210239108145118622销 量814121448表 3-2三。解的改良用闭回路法调整选择进基变量的原那么：即选择非基变量中检验数最小的一个进基。在进基格点所对应的闭回路上，定义顶点的序号：自进基格点起选定一个方向比如顺时针方向，依次为第一格、第二格、在奇数格点上减少调整量 ，在偶数格点上添加调整量 。其中调整量为为闭回路中偶数格点 销地产地产量 41241116821039108145118622销 量814121448表 3-2 销地产地产量 412124411168210329108145118622销 量814121448表 3-2四。表上作业法计算中的两个问题 无穷多个最优解假设在最优解中，某个非基变量的检验数为零，那么该问题有无穷多个最优解此时得到一个最优解：其他变量全等于零。总运费为目的函数值 销地产地产量 412124411168210329108145118622销 量814121448表 3-2 销地产地产量 412124111621039108145118622销 量814121448表 3-2 销地产地产量 441212411164210369108145118622销 量814121448表 3-2此时得另一个最优解：其他变量全等于零。总运费为目的函数值 退化情况与普通LP问题类似，运输问题也能够出现退化了的根本可行解。有以下两种情况：1在确定初始根本可行解时，假设已确定在空格 处要添上调运量 ，而此时发点的当前可发送量与收点的当前需求量恰好相等。即发点的当前发送量已全部用完，而收点的需求量已全部满足。因此应同时划掉发送的行及接受的列。为了使调运表上确保有(m+n-1)个基变量的值，就需求在所划掉的行或列的任一空格添上调运量0。这样就得到有一个基变量取值为0的根本可行解退化解。例如：下表给出一个34运输的运价及发送量与需求量。试用最小元素法求该问题的一个初始根本可行解。 销地产地产量3114577738121069销 量365648表 4-2此时得到一个退化了的初始根本可行解：其他变量全等于零。 在用闭回路调整当前根本可行解时，有多个偶数格值相等且都是极小值点 。此时只能取一个离基，其他的仍作为基格。例如：下表给出一个34运输问题的根本可行解及发送量与需求量、根本可行解的检验数。试用闭回路法对其做出调整。 销地产地产量 317339销 量364648表 4-5 销地产地产量 347369销 量364648表 4-53 运输问题的进一步讨论一、产销不平衡运输问题对产销不平衡问题，可转化为平衡问题，然后按表上作业法求解。转换方法： 假设产大于销，添加一个假想的销地可视为库存地其销量设定为余量，相应的运价设为0。 假设销大于产，添加一个虚拟的产地，其产量设定为缺乏量，相应的运价也设为0。例4 某市有3个造纸厂 ， 和 ，有4个集中用户 和 ，各工厂的消费量、各用户的需用量以及各工厂到用户的单位运价元/t示于表3-14中，问如何调运才干使总运费最小？ 销地产地产量31234811259567159销 量4356表 3-142218可添加一个假想的销地 销地产地产量 31234081125905671509销 量43564表 3-14补充：闭回路的数学定义定义：凡是能排成或方式的变量的集合称为一个闭回路，并将这些变量称为这个闭回路的顶点。由此可以看出闭回路的几何特点：闭回路都是一条封锁折线，每个顶点格子都是转角点每一行或每一列只需且仅有两个顶点格子每两个顶点格子的连线都是程度的或垂直的。可以证明的一个重要结论：m+n-1个变量构成基变量的充要条件是它不含闭回路，即不存在以这些变量为顶点的闭回路例题例题5：弹性需求问题：弹性需求问题v设有三煤矿供应四地域，资料如下：设有三煤矿供应四地域，资料如下：运价运价 地域地域煤矿煤矿甲甲乙乙丙丙丁丁产量产量 A B C161419131320221923171525506050最低需求最低需求最高需求最高需求3050707003010不限不限解题思绪：v设法转化为规范型设法转化为规范型v此题产量此题产量160万吨，最低需求万吨，最低需求110万吨，最高需求无万吨，最高需求无限。本质上比较现实的最高需求限。本质上比较现实的最高需求210万吨万吨v产量大于最小需求；小于最大需求。而规范型是：产量大于最小需求；小于最大需求。而规范型是：产量产量=销量。销量。v处置方法：想象一个虚拟煤矿处置方法：想象一个虚拟煤矿D，消费，消费50万吨，但万吨，但这个产量只能供应可有可无的最高需求部分，于是这个产量只能供应可有可无的最高需求部分，于是各地的需求也应分为两个部分：根本需求、机动需各地的需求也应分为两个部分：根本需求、机动需求求v虚拟产量的运输费用为零，但它对于根本需求来讲，虚拟产量的运输费用为零，但它对于根本需求来讲，运费为无穷大。运费为无穷大。建模：运价 地域煤矿甲1甲2乙丙丁1丁2产量 A B C D161419M1614190131320M2219230171225M1712250 50 60 50 50需求量302070301050 210210最优解：运价 地域煤矿甲1甲2乙丙丁1丁2产量 A B C D30205020030103020 50 60 50 50 需求量302070301050 210210运输模型的运用运输模型的运用v例题例题5：某机床厂定下一年：某机床厂定下一年合同分别于各季度末交货。合同分别于各季度末交货。知各季度消费本钱不同，允知各季度消费本钱不同，允许存货，存储费许存货，存储费0.12万元万元/台季，三、四季度可以加班台季，三、四季度可以加班消费，加班消费才干消费，加班消费才干8台台/季，加班费用季，加班费用3万元万元/台台季度正常消费才干单位本钱万元交货台数12343032202810.5510.81111.125301545分析：分析：v可用线性规划，但用运输问题更简单可用线性规划，但用运输问题更简单v要决策的问题是各季度消费量和交货量设要决策的问题是各季度消费量和交货量设xij表示第表示第i季度消费第季度消费第j季度交货的台数季度交货的台数v因加班时间消费本钱不同，故要区别开来，因加班时间消费本钱不同，故要区别开来，三四季度可加班，视同添加两个季度三四季度可加班，视同添加两个季度v需求量合计需求量合计115台，消费才干合计台，消费才干合计126台，供台，供需不平衡，因此，添加一项闲置才干。需不平衡，因此，添加一项闲置才干。建模：建模： 本钱本钱 交货交货消费消费 闲置闲置 1 2 3 4 才干才干产量产量1季度正常消费季度正常消费2季度正常消费季度正常消费3季度正常消费季度正常消费3季度加班消费季度加班消费4季度正常消费季度正常消费4季度加班消费季度加班消费10.55 10.67 10.79 10.91 0 M 10.8 10.92 11.04 0 M M 11 11.12 0 M M 14 14.12 0 M M M 11.1 0 M M M 14.1 0 30 32 20 8 28 8 需求量需求量 25 30 15 45 11 126126结果：结果： 消费消费 交货交货消费消费 闲置闲置 1 2 3 4 才干才干产量产量1季度正常消费季度正常消费2季度正常消费季度正常消费3季度正常消费季度正常消费3季度加班消费季度加班消费4季度正常消费季度正常消费4季度加班消费季度加班消费 25 5 30 2 10 10 8 28 5 3 30 32 20 8 28 8 需求量需求量 25 30 15 45 11 126126例题例题5 航运调度问题航运调度问题v某航运公司承当六个城市某航运公司承当六个城市A、B、C、D、E、F之间的四之间的四条航线，知各航线的起点、条航线，知各航线的起点、终点及每天所需的航班数如终点及每天所需的航班数如下表。又知各城市之间的航下表。又知各城市之间的航行天数，假定船只型号一样，行天数，假定船只型号一样，装卸货时间各一天，问该公装卸货时间各一天，问该公司至少要配备多少条船才干司至少要配备多少条船才干满足需求？满足需求？航线起点终点每天航班数1234EBADDCFB 3 2 1 1城市之间航行天数表城市之间航行天数表Cij A B C D E FABCDEF 0 1 2 14 7 7 1 0 3 13 8 8 2 3 0 15 5 5 14 13 15 0 17 20 7 8 5 17 0 3 7 8 5 20 3 0问题分析问题分析问题要求的是在保证需求的前问题要求的是在保证需求的前提下，至少需多少船只。提下，至少需多少船只。 所需船只包括两个部分：载所需船只包括两个部分：载货船、空驶船货船、空驶船 。航线航行天数装卸天数合计航班数载货船数1234173713222219591532115710915问题分析续问题分析续1v上表显示：载货船共需上表显示：载货船共需91条，此船何来？条，此船何来？ABCDEF121 3调度中心港口到达开出余缺ABCDEF012301120130-1-122-31假设无空驶，那么假设无空驶，那么91条船刚条船刚好够用，但虚线箭头都是空好够用，但虚线箭头都是空驶驶问题分析续问题分析续2v所需91条货船要经调度而来，有的可在一个港口卸货后装运如一条船从E到D后再起程赴B。假设港口没有空船，那么要从其它港口调度而来。规模效益v由上表可知：C、D、F港口有多余船只可供调出，而A、B、E港口那么需求调入空船。v问题的中心是：如何使空驶船的数量为最少？亦即如何按照最近原那么调度船只问题分析续问题分析续3v为此建立运此建立运输问题数学模型。数学模型。设xij表示每天从表示每天从i港口港口调往往j港口的空船数，那么港口的空船数，那么cijxij就表示就表示 i j航航线上上周周转的船只数，的船只数，cijxij表示各条表示各条线上周上周转的船只的船只总数数 A B E每天多余船只 C D F 2 14 7 3 13 8 5 17 3 2 2 1每天短少船只 1 1 3解题结果解题结果 A B E每天多每天多余船只余船只 C D F 1 1 1 1 1 2 2 1每天短每天短少船只少船只 1 1 3空船总需求量空船总需求量2+5+13+17+3=40条条空驶船空驶船40条条+载重船载重船91条条=131条条