(1.8)-运筹学运输问题

1.模型约束矩阵m

行n

行性质1.运输问题的m

+

n个约束只有m

+

n

-

1个是独立的。且任意m

+

n

-

1个约束是独立的。性质2.运输问题一定有可行解。销地产地供应量需求量由于目标值有下界零，性质2表明运输问题一定有最优解，用单纯形算法求解运输问题可以在下面的运输表格上实现。**

*

****

独立格子集**

*****非独立格子集性质3.运输问题的基对应运输表格上含m+n-1个

格子的独立格子集。推论：独立格子集对应的约束矩阵列向量线性独立。2.求初始基本可行解A.西北角法原则：优先安排编号小的发点和收点之间的运输业务（运输表格上西北角）。ji供应量需求量510010例.用西北角法求初始基本可行解ji供应量需求量510050520例.用西北角法求初始基本可行解ji供应量需求量5100050例.用西北角法求初始基本可行解1520ji供应量需求量5100050例.用西北角法求初始基本可行解15505ji供应量需求量5100050例.用西北角法求初始基本可行解1500555ji供应量需求量51051555西北角法求得的初始基本可行解注：事实上，在求初始基本可行解时，可从运输表格的任何位置开始分配运量，B.最小元素法原则：优先安排单位运费最小的发点与收点之间的运输业务。如ji供应量需求量15例.用最小元素法求初始基本可行解00500151000010ji供应量需求量15最小元素法求得的初始基本可行解5150010C.伏格尔法首先计算各行、各列最小与次小运价的差额，选出差额最大的行或列，选择该行或列的最小运价，优先安排相应的运输业务。（差额越大说明不按最小运费运输时，运费增加越多，因而应优先采用最小运费运输。）ji供应量需求量4284177500例.用伏格尔法求初始基本可行解ji供应量需求量522177500例.用伏格尔法求初始基本可行解15100ji供应量需求量513417500例.用伏格尔法求初始基本可行解1510010ji供应量需求量513417500例.用伏格尔法求初始基本可行解1501005ji供应量需求量54500例.用伏格尔法求初始基本可行解150100587510ji供应量需求量54500例.用伏格尔法求初始基本可行解15010087510010ji供应量需求量54500例.用伏格尔法求初始基本可行解150100875010000ji供应量需求量5伏格尔法求得的初始基本可行解151051003.用位势法计算检验数运输问题的对偶问题：因为运输问题有一个约束是多余的，应删去，相应地，对偶问题中应删去一个变量，于是令该变量取值为0，比如u1=0。由对偶理论，有由于基变量的检验数为0，得m+n-1个方程：进而可计算出非基变量的检验数，最优性准则要求所有检验数大于等于0。注：由于对偶解也称为位势，所以上述方法称为位势法。ji供应量需求量5105155501061819-

14.迭代ji5105155512199*ji供应量需求量55101550121115106111878*ji供应量需求量51015001212111085611187-111已为最优解。5.不平衡运输问题6.转运问题产地生产的产品不一定直接运到销地，而是先运往几个产品集散地集中，再转运至各销地，这些产品集散地（转运点）可能是专门的转运站，也可能就是某几个产地或销地，这类运输问题称为转运问题。转运点将既是发点，也是收点，而纯粹的产地只是发点，纯粹的销地只是收点。注：非转运点的转运量为零，各转运点的转运量是实际发生的转运量的一个上限，由各自的仓储设备、运输条件等决定。由于转运量同时计算在ai、bj

中，所以如果各产地的总产量等于各销地的总销量（即产销平衡），那么否则可参照不平衡运输问题处理。关于运价，可假设同一个转运点间的运价为零。计算结果中发生在同一个转运点之间的转运实际上不发生，转运量上限减去它之后就是实际的转运量。例.产地A1,A2

的产量皆为15吨，销地B1,B2

的销量也皆为15吨，A1,B1

可作为转运点，转运量上限皆为10吨，另有转运点T1

，转运量不能超过20吨。则运输表格为发点发量收量收点7.多品种物资运输问题发点

E1

有某原材料一等品200单位、二等品300单位，E2有该原材料一等品100单位、三等品150单位。收点

F1

将该原材料供应三个消费部门：部门I可将三种原材料互相代用，需求量为150单位；部门II只用一等品，需求量为50单位；部门III只用二或三等品，需求量为50单位。收点

F2

将该原材料供应两个消费部门：部门i使用一或二等品，需求量为200单位；部门ii只用一等品，需求量为300单位。单位运价：F2F1E1E25786将E1拆为两个发点：A1输出一等品200单位，A2输出二等品300单位。将E2也拆为两个发点：A3输出一等品100单位，A4输出三等品150单位。类似地，将F1拆为三个收点B1、B2、B3

，分别对应三个消费部门；将F2拆为两个收点B4、B5

，对应两个消费部门。该问题的产销是不平衡的，如：一等品总产量300单位，而需求量至少50+300=350单位；二、三等品总产量450单位，而需求量至多150+50+200=400单位。因此引入虚发点A5和虚收点B6，它们与实际的发点、收点之间的运价很大（为M），而它们之间的运价为零，这样，只有在实际的发点、收点之间的运输安排不了时才考虑与A5、B6间的运输。由于事先不知道有多少运量安排不了，因此假设A5的输出量和B6的需求量足够大（该问题中750已足够）。B1B2B3B4