运输问题课件

12五月2024运输问题2.1运输问题及其模型例某公司经销一种产品，它下设三个工厂、四个销售部。三个工厂的日产量分别为：A1—7吨，A2—4吨，A3—9吨；各销售部的日销量分别为：B1—3吨，B2—6吨，B3—5吨，B4—6吨。各厂到各销售部的单位产品的运价如右表。问该公司应如何调运产品，才能完成运输任务而使运费最省。用线性规划法处理此问题。设由产地i到销地j的运量为xij，模型为：minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,2,3;j=1,2,3,4)运输问题一般用表上作业法求解，需建立表格模型：单位运价表产销平衡表2.2表上作业法表上作业法的步骤类似于单纯形法:(1)给出初始调运方案。(2)检验方案是否最优,若是最优解,则停止计算;否则转下一步。(3)调整调运方案，得新的方案。(4)重复(2),(3)直到求出最优方案。2.2.1给出初始调运方案最常用的方法——最小元素法表上作业法要求，调运方案的数字格必须为m+n-1个，且有数字格不构成闭回路。一般，用最小元素法给出的方案符合这一要求。314633最小元素法中的退化情况360542出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为有数字格。位势表10219-48（2）（9）（8）（9）（-3）（-2）检验数表若所有检验数非负则是最优解2.2.2最优性检验的方法——位势法（1）从一个检验数为负数且最小的空格出发，和其它数字格构成闭回路。可证，此闭回路存在且唯一。（2）在闭回路上进行运量调整，使选定空格处的运量尽可能地增加。（3）运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。2.2.3方案调整的方法闭回路法位势表10219-48（2）（9）（8）（9）（-3）（-2）检验数表有检验数为负,不是最优解。2.2.4表上作业法举例位势表10128-37（3）（9）（7）（1）（-2）（-2）检验数表表上作业法举例(续)检验数都非负，得最优解。表上作业法是以产销平衡为前提的，即当实际问题产销不平衡时，需要转化为产销平衡的运输问题，具体来说有两种情况：（1）产大于销，即此时增加一个假想的销地n+1，该销地的销量为，而各产地到假想销地的单位运价定为0，就转化成产销平衡的运输问题。（2）销大于产，即此时增加一个假想的产地m+1，该产地的产量为，而假想产地到各销地的单位运价定为0，就转化成产销平衡的运输问题。2.3产销不平衡的运输问题产销不平衡的运输问题举例设有三个化肥厂供应四个地区的农用化肥。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送化肥的单位运价如又表：试求出总运费最省的花费调运方案。解：三个厂的总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。地区Ⅳ每年最多能分配到60万吨，这样四个地区最高需求为210万吨，销大于产。于是，增加虚产地D，产量为50万吨。还要把地区Ⅰ和Ⅳ的产量分为两部分。建立如下表格模型：

50201030302003020例某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。又知如果生产出来的柴油机当季度不交货，每台每季度的存储维护费为0.15万元。试安排全年生产计划，使总费用最低。2.4应用举例解：各季度都产出产品，都可看作产地；各季度都有定货，都可看作销地。这是一个产大于销的运输问题，需增加虚销地D。表格模型如下：产销平衡表10.810.9511.1011.250M11.1011.2511.400MM11.0011.150MMM11.300单位运价表101505302010