运筹学讲义2

合工大考研第二讲运输问题11111,2,,..1,2,,0mnijijijnijijmijjiijMinZwxxaimstxbjnx产地约束销量约束定理1运输问题的数学模型必有最优解。运输问题基变量的个数为m+n－1。对于运输问题的基可行解，m×n个变量中至多只能有m+n－1个变量取正值，而其他的变量为零一、基本概念7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地③④①⑥③③1）数字格2）空格3）闭回路结论1：运输问题的一个可行解是基可行解的充要条件是：1）数字格的个数为m+n-1个2）m+n-1个数字格不构成闭回路（从数字格出发）结论2：对每一个空格处，有且仅有一条闭回路。合工大考研例：判断下表给出的调运方案能否作为表上作业法求解时的初始解B1B2B3B4产量A101515A2151025A355需求量5151510二、表上作业法（1）初始方案的确定：最小元素法；伏格尔法（2）最优性检验：闭回路法；位势法（3）闭回路内改进方案(1.1)最小元素法(就近供应)就进供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到求出初始基可行解为止。7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地(1.2)伏格尔法合工大考研7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地(2.1)闭回路法计算检验数σ偶奇ijijijcc注：1)数字格检验数均为02)空格检验数合工大考研7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地③④①⑥③③(2.2)位势法求检验数ijjicvu对数字格而言计算）行势、列势的定义与注：:13）行势、列势可不唯一，但检验数是一致的。0),()2σσijjiijijvuc数字格检验数的计算：空格0),()2σσijjiijijvuc数字格检验数的计算：空格7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地7410206563bj5810947ai1391123A3A2A1B4B3B2B1销地产地③④①⑥③③合工大考研（3）闭回路内改进方案741058101391123A3A2A1B4B3B2B1销地产地741058101391123A3A2A1B4B3B2B1销地产地③④①⑥③③121-11012（06年，第三题，20分）下表是一运输问题的表格，其中右上角数字是单位运价，方框内是运量。B1B2B3B4产量A126312255A2758242A3332573需求量2314(1)上表所给方案是否为该问题的可行解，是否为该问题的基本可行解，为什么？(2)上述方案是否是该问题最优解？若不是，如何用表上作业法继续迭代？解：(1)上表方案是该问题的可行解，因为该问题的数学模型是合工大考研设从Ai运往Bj的运量为为xij111213142122232431323334min632575843257zxxxxxxxxxxxx111213142122232431323334112131122232132333142434..52323140ijstxxxxxxxxxxxxxxxxxxxxxxxxx由上表方框内的运量可知，11131424322,1,2,2,3,xxxxx其余的xij等于零，将其代入约束条件中，显然都满足，因此上表方案是该问题的可行解。在运输问题中，数字格（基变量）有1mn个，而上表中只有五个数字格，若是基变量应该是3416个，因此上表方案不是该问题的基本可行解。(2)由位势法得上述方案的检验数为下表（圈中数字是检验数），B1B2B3B4uiA12631225A275824A3033257vj（1，2）格的检验数为负值，因此上述方案不是该问题的最合工大考研优解，继续以（1，2）格为调入格，以此格为出发点做一闭回路，=min{2，3}=2进行闭回路调整得可行解，然后再计算检验数，得下表B1B2B3B4uiA16231225A275824A3231257vj此时，所有检验数非负，即得最优解。例：已知运输问题的产销平衡表、单位运价表及最优调运方案分别见表1和表2，试回答下列问题表1B1B2B3B4产量A151015A20101525A355需求量5151510表2B1B2B3B4A11012011A2127920合工大考研A321416181）从A2B2的单位运价c22在什么范围内变化时，上述最优调运方案不发生变化？2）A2B4的单位运价c24变为何值时，有无穷多最有无穷多最优调运方案？至少再写出其他两个。解：1）B1B2B3B4A1A2A32）B1B2B3B4A1合工大考研A2A3例：某百货公司去外地采购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、400、300吨，有两个产地甲、乙可供应该原料500,、400吨，单位运价见表：合工大考研产地工厂ABC甲161014乙1212201）将该问题化为平衡问题，建立运输表，要求A地需求必须满足；2）简述平衡运输问题表上作业法步骤。解：1）根据题意，本题是销大于产的不平衡运输问题。虚设一个产地丙，其产量为100吨，转化为产销平衡问题，运输表如下产地工厂ABC生产量甲161014500乙121220400丙M00100需求量3004003001000（11年，第四题，15分）已知最小化运输问题如表2所示，表2中空格右上角数据为单位运价。表2销产B1B2B3aiA116109500合工大考研A214208400bj200400300(1)按最小元素法确定初始方案；(2)用位势法检验该初始方案是否最优；(3)如果产地A2产量减少200，但要保证B2的需求，给出其相应的产销平衡表。解：（1）初始方案见下图。销产B1B2B3aiA116109500100400A214208400100300bj200400300（2）销产B1B2B3uiA116109500100400-1合工大考研A21420840010012300vj161010因为(1,3)位置的检验数=－1，所以该初始方案不是最优。（3）虚拟一个产地A3，其产量为200，相应的产销平衡表如下销产B1B2B3aiA116109500A214208200A30M0200bj200400300例：甲、乙、丙三个城市每年需要煤炭分别为：320万吨、250万吨、350万吨，由A、B两处煤矿负责供应。已知煤矿年供应量分别为：A-400万吨，B-450万吨。由煤矿至各城市的单位运价（万元/万吨）见下表。由于需大于供，经研究平衡决定，甲城市供应量可减少0-30万吨，乙城市应全部满足，丙城市供应量不少于270万吨，试求将供应量分配完又使总运费最低的调运方案。合工大考研甲乙丙A151822B212516解：