运筹学讲义2.docx

1、运筹学讲义2运筹学讲义2第二讲 运输问题定理1 运输问题的数学模型必有最优解。运输问题基变量的个数为m+n1 。对于运输问题的基可行解，mn个变量中至多只能有m+n1个变量取正值，而其他的变量为零一、基本概念1）数字格 2）空格 3）闭回路结论1： 运输问题的一个可行解是基可行解的充要条件是：1）数字格的个数为m+n-1个2） m+n-1个数字格不构成闭回路（从数字格出发）结论2： 对每一个空格处，有且仅有一条闭回路。例：判断下表给出的调运方案能否作为表上作业法求解时的初始解B1B2B3B4产量A101515A2151025A355需求量5151510二、表上作业法（1）初始方案的确定：最小元

2、素法；伏格尔法（2）最优性检验：闭回路法；位势法（3）闭回路内改进方案最小元素法(就近供应)就进供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到求出初始基可行解为止。伏格尔法闭回路法计算检验数注：1)数字格检验数均为02)空格检验数位势法求检验数（3）闭回路内改进方案（06年，第三题，20分）下表是一运输问题的表格，其中右上角数字是单位运价，方框内是运量。B1B2B3B4产量A12 63 1 22 55A27582 42A333 2573需求量2314(1) 上表所给方案是否为该问题的可行解，是否为该问题的基本可行解，为什么(2) 上述方案是否是该问题最优解若不是，如何用表上

3、作业法继续迭代解：(1) 上表方案是该问题的可行解，因为该问题的数学模型是设从Ai运往Bj的运量为为xij由上表方框内的运量可知，其余的xij等于零，将其代入约束条件中，显然都满足，因此上表方案是该问题的可行解。在运输问题中，数字格（基变量）有个，而上表中只有五个数字格，若是基变量应该是个，因此上表方案不是该问题的基本可行解。(2) 由位势法得上述方案的检验数为下表（圈中数字是检验数），B1B2B3B4uiA12 6 3 1 22 5A2 7 5 82 4A30 33 2 5 7vj（1，2）格的检验数为负值，因此上述方案不是该问题的最优解，继续以（1，2）格为调入格，以此格为出发点做一闭回路

4、，=min2，3=2进行闭回路调整得可行解，然后再计算检验数，得下表B1B2B3B4uiA1 6 2 3 1 22 5A2 7 5 82 4A32 31 2 5 7vj此时，所有检验数非负，即得最优解。例：已知运输问题的产销平衡表、单位运价表及最优调运方案分别见表1和表2，试回答下列问题表1B1B2B3B4产量A151015A20101525A355需求量5151510表2B1B2B3B4A11012011A2127920A321416181）从A2 B2的单位运价c22在什么范围内变化时，上述最优调运方案不发生变化2）A2 B4的单位运价c24变为何值时，有无穷多最有无穷多最优调运方案至少再

5、写出其他两个。解：1）B1B2B3B4A1A2A32）B1B2B3B4A1A2A3例：某百货公司去外地采购A、B、C、D四种规格的服装，数量分别为：A-1500套，B-2000套，C-3000套，D-3500套。有三个城市可供应上述规格服装，各城市供应数量分别为：I-2500套，II-2500套，III-5000套。由于这些城市的服装质量、运价和销售情况不同，预计售出后的利润（元/套）也不同，见下表，请帮该公司确定一个预期盈利最大的采购方案。ABCDI10567II8276III9348三、不平衡运输问题转化（10年，第二题，15分）有三个工厂A、B、C，它们需要同一种资源，数量分别是300、

6、400、300吨，有两个产地甲、乙可供应该原料500,、400吨，单位运价见表：产地 工厂ABC甲161014乙1212201）将该问题化为平衡问题，建立运输表，要求A地需求必须满足；2）简述平衡运输问题表上作业法步骤。解：1）根据题意，本题是销大于产的不平衡运输问题。虚设一个产地丙，其产量为100吨，转化为产销平衡问题，运输表如下产地 工厂ABC生产量甲161014500乙121220400丙M00100需求量3004003001000（11年，第四题，15分）已知最小化运输问题如表2所示，表2中空格右上角数据为单位运价。表2销产B1B2B3aiA116109500A214208400bj2

7、00400300(1) 按最小元素法确定初始方案；(2) 用位势法检验该初始方案是否最优；(3) 如果产地A2产量减少200，但要保证B2的需求，给出其相应的产销平衡表。解：（1）初始方案见下图。销产B1B2B3aiA116109500100400A214208400100300bj200400300（2）销产B1B2B3uiA116109500100400-1A21420840010012300vj161010因为(1,3)位置的检验数=1，所以该初始方案不是最优。（3）虚拟一个产地A3，其产量为200，相应的产销平衡表如下销产B1B2B3aiA116109500A214208200A30M0200bj200400300例：甲、乙、丙三个城市每年需要煤炭分别为：320万吨、250万吨、350万吨，由A、B两处煤矿负责供应。已知煤矿年供应量分别为：A-400万吨，B-450万吨。由煤矿至各城市的单位运价（万元/万吨）见下表。由于需大于供，经研究平衡决定，甲城市供应量可减少0-30万吨，乙城市应全部满足，丙城市供应量不少于270万吨，试求将供应量分配完又使总运费最低的调运方案。甲乙丙A151822B212516解：