运输问题例题

雷切尔是斯特兰运输公司南大西洋办公处的经理。目前，她正和一家名叫化聚的工业用化学品制造公司谈一份新的运输合同。化聚公司想让斯特兰公司负责将其6个工厂的废物装载并运送到3个垃圾处理点。雷切尔非常担心化聚公司的这份提议。这些将被运输的化学废品一旦泄露将会给人类和环境带来极大的伤害。雷切尔估计出了从每个工厂运输一桶废物到每个垃圾处理点的运输成本如下表：工厂\处理厂白水罗斯堪洛杜拉斯金斯波特121517丹维尔14910美肯132011塞尔玛171619哥伦布71412亚兰敦2216186个工厂每周产生的废物量如下：工厂每周废物量(桶)金斯波特35丹维尔26美肯42塞尔玛53哥伦布29亚兰敦38位于白水、罗斯堪洛和杜拉斯的三个垃圾处理点每周最多可容纳的废物量分别为65桶、80桶和105桶。除了考虑将废品从每个工厂直接运到每个垃圾处理点之外，雷切尔还考虑将每个工厂和垃圾处理点当做中间运输点的运输方式。汽车可以将废品卸到某个工厂或垃圾处理点，然后再由另一辆车将废品转载上并运往目的地，反之亦然。斯特兰德公司不承担任何处理成本，只承担运输成本。雷切尔估计了6个工厂之间每桶废品的运输成本，如下表所示：工厂\工厂金斯波特丹维尔美肯塞尔玛哥伦布亚兰敦金斯波特\64978丹维尔6\1110127美肯511\3715塞尔玛9103\316哥伦布71273\14亚兰敦87151614\三个垃圾处理点两两之间每桶废品的运输成本估计如下：处理点\处理点白水罗斯堪洛杜拉斯白水\1210罗斯堪洛12\15杜拉斯1015\(1)请简述处理完所有的垃圾最少需要多少个处理站，写出分析过程。（5分）(2)请建立直接从工厂运输到垃圾处理点的成本最小的模型。（5分）(3)请建立从工厂运输到垃圾处理点，每箱废物至多可以经过工厂转运一次的成本最小的模型（5分）(4)请建立可以从任何工厂和垃圾处理点转运，且每箱废物经过转运次数不限的成本最小的模型。（5分）提示：对于(2),(3),(4)问，所有约束条件可以为等式约束，也可以为不等式约束，模型合理即可。解：(1)至少需要3个(2)Min12x11+15x12+17x13+14x21+9x22+10x23+13x31+20x32+11x33+17x41+16x42+19x43+7x51+14x52+12x53+22x61+16x62+18x63s.tx11+x12+x13=35x21+x22+x23=26x31+x32+x33=42x41+x42+x43=53x51+x52+x53=29x61+x62+x63=38x11+x21+x31+x41+x51+x61=65x12+x22+x32+x42+x52+x62=80x13+x23+x33+x43+x53+x63=105xij=0,fori=1,2,…6,j=1,2,3.xij为整数,fori=1,2,…6,j=1,2,3.(3)设从工厂到工厂运量为向量y,从工厂到处理场运量为向量x设工厂到工厂成本为c1,从工厂到处理场成本为c2则目标函数为Minc1y+c2x第一组约束条件为对于任何的工厂来讲运出的量等于其产量第二组约束条件为对于任何作为转运工厂来讲，运出量等于运入量第三组约束条件为对于任何垃圾处理场来讲，运入量小于或等于其处理能力。(4)将工厂和处理场合并，都作为工厂和处理场看待，如果原本是工厂的，处理能力为0，如果原本是处理场的，产生的废物为0。若六家工厂产生废物向量为T，则另T’=[T,0,0,0]T。若三家处理场的处理能力向量为S，则另S’=[0,0,0,0,0,0,S]。令工厂到处理场之间矩阵为C1,工厂到工厂之间矩阵为C2,处理场到处理场之间矩阵为C3,则令。设决策变量为xij为i点产生的废物被运送到j处理场的量，i=1,2,…9,j=1,2,…9。令X=[xij]则目标函数为约束(1)为，X[1,1,….1]T=T’约束(2)为，[1,1,….1]X=S’xij为整数fori=1,2,…9,j=1,2,…9.