运输问题(1)

运输问题2.1运输问题及其数学模型2.2表上作业法2.2.1最小元素法2.2.2位势法2.2.3闭回路法2.3产销不平衡的运输问题2.4应用举例2.1运输问题及其模型例某公司经销一种产品，它下设三个工厂、四个销售部。三个工厂的日产量分别为：A1—7吨，A2—4吨，A3—9吨；各销售部的日销量分别为：B1—3吨，B2—6吨，B3—5吨，B4—6吨。各厂到各销售部的单位产品的运价如右表。问该公司应如何调运产品，才能完成运输任务而使运费最省。销地产地B1B2B3B4A1A2A3317119433101085用线性规划法处理此问题。设由产地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)运输问题一般用表上作业法求解，需建立表格模型：单位运价表销地产地B1B2B3B4产量A1A2A3749销量3656产销平衡表销地产地B1B2B3B4A1A2A33171194331010852.2表上作业法表上作业法的步骤类似于单纯形法:(1)给出初始调运方案。(2)检验方案是否最优,若是最优解,则停止计算;否则转下一步。(3)调整调运方案，得新的方案。(4)重复(2),(3)直到求出最优方案。2.2.1给出初始调运方案最常用的方法——最小元素法表上作业法要求，调运方案的数字格必须为m+n-1个，且有数字格不构成闭回路。一般，用最小元素法给出的方案符合这一要求。销地产地B1B2B3B4产量A1A2A3749销量3656销地产地B1B2B3B4A1A2A3317119432101085314633最小元素法中的退化情况销地产地B1B2B3B4产量A1A2A3749销量3656销地产地B1B2B3B4A1A2A3331119234101085360542出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为有数字格。销地产地B1B2B3B4uiA1A2A31432105vj位势表10219-48（2）（9）（8）（9）（-3）（-2）销地产地B1B2B3B4A1A2A3317119432101085检验数表若所有检验数非负则是最优解2.2.2最优性检验的方法——位势法销地产地B1B2B3B4产量A1A2A3364133749销量3656销地产地B1B2B3B4A1A2A31102112-1（1）从一个检验数为负数且最小的空格出发，和其它数字格构成闭回路。可证，此闭回路存在且唯一。（2）在闭回路上进行运量调整，使选定空格处的运量尽可能地增加。销地产地B1B2B3B4产量A1A2A3364133749销量3656销地产地B1B2B3B4产量A1A2A33650213749销量3656（3）运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。2.2.3方案调整的方法闭回路法销地产地B1B2B3B4产量A1A2A31432105销量位势表10219-48（2）（9）（8）（9）（-3）（-2）销地产地B1B2B3B4A1A2A3317119432101085检验数表销地产地B1B2B3B4产量A1A2A3364133749销量3656销地产地B1B2B3B4A1A2A31102112-1有检验数为负,不是最优解。2.2.4表上作业法举例销地产地B1B2B3B4产量A1A2A31431085销量位势表10128-37（3）（9）（7）（1）（-2）（-2）销地产地B1B2B3B4A1A2A3317119432101085检验数表销地产地B1B2B3B4产量A1A2A3365213749销量3656销地产地B1B2B3B4A1A2A30922112表上作业法举例(续)检验数都非负，得最优解。表上作业法是以产销平衡为前提的，即当实际问题产销不平衡时，需要转化为产销平衡的运输问题，具体来说有两种情况：（1）产大于销，即njjmiiba11此时增加一个假想的销地n+1，该销地的销量为，而各产地到假想销地的单位运价定为0，就转化成产销平衡的运输问题。njjmiiba11（2）销大于产，即njjmiiba11此时增加一个假想的产地m+1，该产地的产量为，而假想产地到各销地的单位运价定为0，就转化成产销平衡的运输问题。miinjjab112.3产销不平衡的运输问题产销不平衡的运输问题举例设有三个化肥厂供应四个地区的农用化肥。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送化肥的单位运价如又表：地区化费厂ⅠⅡⅢⅣ产量ABC1613221714131915192023-506050最低需求最高需求3070020507030不限试求出总运费最省的花费调运方案。解：三个厂的总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。地区Ⅳ每年最多能分配到60万吨，这样四个地区最高需求为210万吨，销大于产。于是，增加虚产地D，产量为50万吨。还要把地区Ⅰ和Ⅳ的产量分为两部分。建立如下表格模型：销地产地Ⅰ′Ⅰ″ⅡⅢⅣ′Ⅳ″ABCD16161322171714141319151519192023MMM0M0M0产地销地Ⅰ′Ⅰ″ⅡⅢⅣ′Ⅳ″产量ABCD50605050销量30207030105050201030302003020例某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。又知如果生产出来的柴油机当季度不交货，每台每季度的存储维护费为0.15万元。试安排全年生产计划，使总费用最低。季度生产能力单位成本ⅠⅡⅢⅣ25台35台30台10台10.8万元11.1万元11.0万元11.3万元2.4应用举例解：各季度都产出产品，都可看作产地；各季度都有定货，都可看作销地。这是一个产大于销的运输问题，需增加虚销地D。表格模型如下：产销平衡表销地产地ⅠⅡⅢⅣD产量ⅠⅡⅢⅣ25353010销量1015252030销地产地ⅠⅡⅢⅣDⅠⅡⅢⅣ10.810.9511.1011.250M11.1011.2511.400MM11.0011.150MMM11.300单位运价表10150530201010例某航运公司承担六个港口城市A,B,C,D，E,F间四条航线的货物运输任务。各航线的起点、终点、日航班数如下：航线起点终点日航班数1234EBADDCFB3211假定各航线使用的船只相同，各城市间的航程天数如下：到从ABCDEFABCDEF0121477103138823015551413150172078517037852030又知每条船每次装卸货时间各需1天，问该公司至少应配备多少条船？城市到达发出余缺数ABCDEF012301120130-1-122-31为使配备船只数尽可能少，建立如下运输模型:ABE产量CDF221销量113ABECDF23515131778311111调度需要的船只数为2+5+13+17+3=40条解所需船只分成两部分：(1)载货航行需要的船只数.3*19+2*5+9+15=91条.(2)各港口间调度需要的船只数.各港口每天船只的余缺数为: