搜索
1第5章各种运输模型2运输模型是一类特殊的线性规划，研究如何把商品从起点（如工厂）运算到终点（如商场），目标是确定一项运输计划，在满足供需约束的条件下，使得总的运输费用最小。运输模型的应用可以扩展到库存控制、招聘计划、人员指派等领域。35.1运输模型的定义12m12m1a2ama1b2b3b1111:cx:mnmncx每单位运输费用cij，运输量xij。起点i的供应量为ai，终点j的需求量为bj。该模型的目标是确定未知变量xij，在满足供应量和需求量约束的情况下，使得总的运输费用最小。4MG汽车有3个工厂，分布位于洛杉矶、底特律和新奥尔良，这三个工厂下季度的生产能力分别是1000，1500，1200辆汽车。在丹佛和迈阿密有2个主要分销中心，其季度需求为2300和1400辆汽车。汽车厂与销售中心的距离里程（下左）与对应的价格（下右）如表运输距离丹佛迈阿密洛杉矶10002690底特律12501350新奥尔良1275850运车单价丹佛迈阿密洛杉矶80215底特律100108新奥尔良10268运输里程运输价格例5.1-15本问题的线性规划模型为111221223132111221223132112131122232min80215100108102681000()1500()1200()2300()1400()0,1,2,3,1,2ijzxxxxxxstxxxxxxxxxxxxxij洛杉矶底特律新奥尔良丹佛迈阿密6因为3个起点的总供给量(=1000+1500+1200=3700辆)等于2个分销中心的总需求(=2300+1400辆)，这些约束都是等式。这个线性规划模型可以用单纯形方法求解，然而由于特殊的结构可以采用运输表的方法来求解该问题运车单价丹佛迈阿密供应量洛杉矶80x11215x121000底特律100x21108x221500新奥尔良102x3168x321200需求量2300140012m1210001500120023001400100012001300洛杉矶底特律新奥尔良2007运输模型的平衡运输算法假定模型是平衡的，即总需求等于总供给。如果模型不平衡，我们可以通过增加一个虚设起点或一个虚设终点以使得模型达到平衡。在MG汽车模型中，假设底特律汽车生产量为1300（而非1500）。总供应量(=3500)小于总需求(=3700),这意味着丹佛和迈阿密的部分需求得不到满足。由于需求量大于供应量，我们增加一个生产能力为200辆(3700-3500)的虚拟工厂来平衡运输模型。因为该工厂不存在，单位运输费用从起点到终点的运输费为0.8运车单价丹佛迈阿密供应量洛杉矶8010002151000底特律10013001081500新奥尔良1026812001200虚拟工厂00200200需求量230014009类似地，如果供应量大于需求量，假设丹佛的需求只有1900，我增加一个虚拟的分销中心来“接收多余”的汽车。假设运输费用为0。运车单价丹佛迈阿密虚设终点供应量洛杉矶80100021501000底特律10090010820004001500新奥尔良10268120001200需求量1900140040010习题有3个发电厂向3个城市供电，其发电量为25，40和30兆千瓦时。3个城市的最大需求量为30，35和25兆千瓦。这3个城市的每兆千瓦电价如表所示.城市电厂123160070040023203003503500480450在8月份期间，这个城市的每一个都会增加20%的用电需求，这部分的电量可以从别的电网以每兆千瓦1000的价格额外采购。这个电网不与第3个城市相连，电力公司希望确定增加爱电量的最经济的销售和采购计划。(a)把此问题表达为一个运输模型(b)为电力公司制定一个最优销售计划(c)确定3个城市每个额外购电费用115.2非传统运输模型运输模型不仅限于起讫点之间的货物运输，它还可以在生产-库存控制等领域。例5.2-1（生产-库存）Boralis公司生产专业徒步背包。产品需求通常出现在3-6月，该公司估计这4个月的需求为100，200，180和300个。由于该公司雇用兼职人员生产背包，因此每个月生产能力不一样，3-6月期间能够生产50，180，280，270个，因为各月的生产能力和需求不匹配。各月份需求可以通过如下办法满足：(1)当月生产，40元/个(2)以前某个月剩余的产品，存储费用0.5元/个/月(3)以后某个月多余的产品(延期交货)，惩罚费用2元/个/月。确定Boralis公司的最优生产计划。12通过找出生产-控制问题与运输模型要素之间的对应关系，把该问题建立为一个运输模型：运输生产库存(1)起点i(1)生产周期i(2)终点j(2)需求周期j(3)起点i的供应量(3)生产周期i的生产能力(4)终点j的需求量(4)需求周期j的需求量(5)从起点i终点j的单位运输费用(5)周期i为周期j的生产的单位费用(生产+库存+惩罚)13下表给出了建立的运输模型1234生产能力14040.54141.5502424040.541180344424040.5280446444240270需求量100200180300从周期i到周期j的单位“运输”费用可以计算为ijiijciijijiijij周期的生产费用，周期的生产费用+从到的库存费用，周期的生产费用+从到的库存费用，1412234431供应周期需求周期供应需求5018028027010020018030050501307018030270最优解如下图所示。虚线表示延期交货，红色点线表示为后期生产，实线表示为本周期生产。15锯木厂由于锯木的品种差异，其需要的锯片需求表如下：日周一周二周三周四周五周六周日锯片需求量24121420181422工厂可以通过以下方式满足每天需求:(1)以每片12元的价格购买新锯片；(2)利用一种通宵打磨服务，其打磨价格为6元/片；(3)使用慢一点的2天打磨服务，打磨价格为3元/片.本问题可以表示成为8个起点和7终点的运输模型。终点表示一个星期的7天。模型的起点定义如下：起点1对应于购买新锯片，在极端情况下，可以提供足够多的锯片以满足所有7天的需求(=24+…+22=124).起点2到8对应于一个星期中的7天.这些起点的供应量等于相应每天所使用锯片数量.1612345678周一周二周三周四周五周六周日处理1新锯片122412212121212120981242周一M61068363330243周二MM66636330124周三MMM6146330145周四MMMM612630206周五MMMMM61460187周六MMMMMM6140148周日MMMMMMM022222412142018142212417例如，起点2(周一)可以提供用过的锯片数量等于周一对锯片的需求量.本模型中的单位“运输费用”，依据是否购买新锯片、通宵打磨服务或晚2天打磨服务分别为12，6或3元。需要注意的是，通宵打磨服务意味着第i天结束时所用过的锯片可以在第(i+1)或(i+2)天的开始时使用，慢的打磨服务的锯片可以在(i+3)天的开始时使用。“处理”列是平衡模型所需要的一个虚设终点。18星期锯片数（当前日）处理新锯片通宵磨2天磨周一24(一)10(一)+8(三)6(四)0周二2(二)6(三)6(五)0周三014(四)00周四012(五)8(五)0周五014(六)04周六014(日)00周日00022评注：上表的模型仅适用于第一个星期的运行，因为没有考虑每个星期每天轮流的特性，即这个星期的每一天可以作为下星期需求的起点和“处理”终点.总的费用为840元19第i周第i周总计周一周二周三周四周五周六周日2周一M663633318243周二3M6638334124周三3123M66323145周四383123M663206周五3433143M66187周六6333143M6148周日6633310312M22总计24121420181422总的费用为372元20习题未来4个月对某种已过期物品的需求量分别为400，300，420，380吨，相应这4个月的供应能力为500，600，200，300吨.每个月每吨的采购费不同，分别为100、140、120和150吨.由于物品容易过期，当月生产的物品必须在3个月内(包括生产月)消费完.每吨物品每月的存储费用为3元，这种物品不能延期交货。请确定未来4个月的最优生产安排。215.3运输算法运输算法完全采用单纯形的步骤，但是由于运输模型的特殊结构，运输算法可以构造特殊形式，进行更为简单的求解。鉴于运输算法是早期建立的手工算法，目前计算式的使用，不在强调这些简单方法。例5.3-1(SunRay运输问题)SunRay运输公司从3个粮仓把粮食运到4个加工厂。运输费用和运输模型见下表，运输费用为cij，确定运输费用最低的运输计划量221234供应量仓库110x112x1220x1311x1415仓库212x217x229x2320x2425仓库34x314x3216x3318x3410需求量515151523运输算法运输算法的步骤与单纯形法完全一致第1步确定一个初始的基本可行解，转到第2步.第2步利用单纯形算法的最优性条件，在所有的非基变量中确定进基变量，如果最优性条件满足，停止。否则，转到第3步。第2步利用单纯形算法的可行性条件，在所有现有的基变量中确定离基变量，寻找新的基本解。返回第2步。245.3.1初始解的确定一个具有m个起点和n个终点的一般运输模型包含(m+n)个约束方程，每一个起点和终点都对应一个约束方程。然而，因为运输模型总是平衡的（供需相等），这些约束方程中有一个是冗余的。因此，运输模型有(m+n-1)个独立的约束方程，即初始基本解由(m+n-1)个基变量组成，因此在例5.3-1中有3+4-1个基变量。运输问题可以采用西北角法（左上角法）、最小费用法、Vogel法（福格尔法）找到非人工的初始基本解。一般来说，Vogel法能够产生最好的初始基本解。25西北角法最后得的初始基可行解。销地运价产地B1B2B3B4产量A13113107A219284A3741059销量36562034422223366总运费135.26最小元素法最后得的初始基可行解。销地运价产地B1B2B3B4产量A13113107A219284A3741059销量36562031144363333总运费86.27Vogel近似法(VAM)第1步对每一行(列)确定惩罚量：在每一行(列)中找到一个最小的以及次小的单位费用单元，惩罚量即为次小的单位费用减去最小的单位费用。第2步找出惩罚量最大的行或列。尽量分配给最小单位费用的单元最多的粮车，调整供应和需求，删去已满足的行或列。如果行和列同时满足，删去两者之一，分配给剩下的那个行(列)为零供应(需求)。第3步(a)如果仅有一个未被删去的零供应的行或零需求的列，则停止。(b)如果具有一个未被删去的大于零供应(需求)的行(列)，那么采用最小费用方法确定行(列)的基变量，停止(c)如果所有的未被删除的行和列都有零供应和零需求，那么采用最小费用方法确定零基变量。停止(d)否则，转到第1步。28Vogel法求初始解销地运价产地B1B2B3B4行差A129107A21342A38425列差•求每行(列)次小和最小运价的差：7-25121123•差中最大的先安排：第一行的x11x1129销地运价产地B1B2B3B4行差产量A1291075A213421A384252列差销量11239573846Vogel法求初始解在最小运价的行或列中优先安排运量36514522521815331530Vogel法Vogel法的初始运输方案总运价：销地运价产地B1B2B3B4行差产量A1291078A213423A384256列差销量7685957384634531511010088315.3.2运输算法的迭代计算确定初始解后，采用下面的算法确定最优解：第1步采用单纯形法的最优性条件，来确定能够改进解的作为当前非基变量