《第三章：cplex在运输问题中的应用资料》由会员分享，可在线阅读，更多相关《第三章：cplex在运输问题中的应用资料（19页珍藏版）》请在金锄头文库上搜索。
1、CPLEX在运输问题中的应用 一、运输问题的概述一、运输问题的概述 标准的运输问题：就是解决把某种产品从标准的运输问题：就是解决把某种产品从 若干个产地调运到若干个销地，在每个产若干个产地调运到若干个销地，在每个产 地的供应量与每个销地的需求量已知，并地的供应量与每个销地的需求量已知，并 且供应总量与需求总量相等，且知道各地且供应总量与需求总量相等，且知道各地 之间的运输单价的前提下，如何确定一个之间的运输单价的前提下，如何确定一个 使得总的运输费用最小的方案的问题。使得总的运输费用最小的方案的问题。 例例1. 某公司从两个产地A1，A2将物品运往 三个销地B1，B2，B3，各生产地的产量、
2、各销售地的销量和各生产地运往各销售地 的每件物品的运费如下表所示： 问应如何调运，使得总运输费最小？ B1B1 B2B2 B3B3 产量产量 A1 6 4 6 200 A2 6 5 5 300 销量 150 150 200 二、运输问题的数学模型：二、运输问题的数学模型： 设从产地Ai运输到销地Bj的物资数量为xij， 从产地Ai运输到销地Bj的单位运费为Cij，各 产地的产量是ai（i=1,2，m），各销地 的销量是bj（j=1,2，n）则标准运输问 题的数学模型为： 三、运输问题在三、运输问题在CPLEXCPLEX中建模与求中建模与求 解解 因此如果只建立一个mod文件的话，假如命名的为
3、“trans1.mod”，例1的OPL建模语言可以是： string SCities =“A1“, “A2“; string DCities =“B1“, “ B2“, “ B3“; float SupplySCities = 200, 300; float DemandDCities = 150, 150, 200; assert sum(o in SCities) Supplyo = sum(d in DCities) Demandd; float CostSCitiesDCities = 6, 4, 6, 6, 5, 5 ; dvar float+ TransSCitiesDCities
4、; minimize sum( o in SCities ,d in DCities ) Costod * Transod; subject to forall( o in SCities ) ctSupply: sum( d in DCities ) Transod = Supplyo; forall(d in DCities ) ctDemand: sum( o in SCities ) Transod = Demandd; execute DISPLAY writeln(“trans = “,Trans); 四、非标准运输问题的建模与求解四、非标准运输问题的建模与求解 运输问题的一般模型
5、会发生一些如下变化： 1.当某些运输线路的运输能力有一定限制时， 这时要在线性规划的模型的约束条件上要 加上运输能力限制的约束条件。例如 A2 运 到 B3的物品的数量受到运输能力的限制， 最多运送180单位，这时只要在原来的模型 上加上约束条件x23180 即可。也有这种情 况：有些线路规定不能运输。 2.当生产总量不等于销售总量，即产销不平衡 时，这时将通过增加一个假想仓库或假想生产 地来化成产销平衡的问题。对于产销不平衡的 运输问题，我们可以先化为产销平衡的运输问 题然后再求解。 3.转运问题 所谓转运就是运输网络中的物品，并不一定直 接从产地运往销地，而是可以通过其他节点周 转后间接运
6、往销地。带有转运问题具有以下特 征：通常存在中转点，这些点在运输网络中既 不生产也不消耗运输的物品；可以在网络中的 任何两个节点之间生产运输行为，甚至允许销 地向产地反向运输。 产销不平衡例子产销不平衡例子 例例2：某公司从两个产地A1、A2将物品运往 三个销售地B1、B2、B3，各产地的产量、 各销地的销量和各产地运往各销地每件物 品的运费如下表所示，问：应如何调运可 使总运输费用最小？ B1B1 B2B2 B3B3 产量产量 A1 6 4 6 200 A2 6 5 5 300 销量 250 200 200 解：解： 先增加一个虚拟产地A3，运输费用为0，因 此变成了一个标准的运输问题，其新
7、表为 B1B1 B2B2 B3B3 产量产量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 销量 250 200 200 例例3： 某公司从产地将物品运往销地，各产地的 产量、各销地的销量和各产地运往各销地 每件物品的运费如下表所示，问：应如何 调运可使总运输费用最小？ B1B1 B2B2 B3B3 B4B4 产量产量 A1 5 9 2 3 60 A2 - 4 7 8 40 A3 3 6 4 2 30 A4 4 8 10 11 50 销量 20-60 50-70 35 45 总产量为180，最低需求量为20+50+35+45=150， 最高需求量为210. 设一
8、个虚拟的厂A5，其产量为210-180=30，并且 令A5只能供应B1或B2. 将B1和B2进行拆分，得到的产销平衡表如下： B1B1 B1B1 B2B2 B2B2 B3B3 B4B4 产量产量 A1 5 5 9 9 2 3 60 A2 M M 4 4 7 8 40 A3 3 3 6 6 4 2 30 A4 4 4 8 8 10 11 50 A5 M 0 M 0 M M 30 销量 20 40 50 20 35 45 转运问题转运问题 （1）一般转运问题的描述： 有m个产地和n个销地，s个中转点，在每个产地的供应量与每个销地 的需求量已知，并且供应总量与需求总量相等，且知道各地之间的运 输单价
9、的前提下，如何确定一个使得总的运输费用最小的方案的问题。 （2）分析： 可以做以下处理：将所有的节点（产地、销地和中转站）打破产地或 销地的狭义概念，构造出一个行列均是（m+n+s）个节点的运输效率 矩阵，以及同样阶数的运输方案矩阵。由此可见，转运问题的决策变 量是（m+n+s）2个。 假设所有产地的产量和等于所有销地的销量和，设为Q。 将各个节点做以下处理：（1）将原来是产地的发送量设置为Q+ai， 中转点和和销地的发送地的发送量设置为Q；（2）将原来是销地的接 收量设置为Q+bj，中转点和产地的接收量设置为Q。 因此又变成了一个标准的运输问题了。 例例4： 光明公司是一家专门提供盒装早餐的
10、企业， 现在该公司的经营方式是通过全市不同未 知的三个生产车间（设为Ai，i=1,2,3）为4 个配送站（设为Bj，j=1,2,3,4）提供质量一 致的早餐。光明公司现在拥有自己的运输 车队，并在每天4点前必须完成所有的配送 业务。公司还有4个中转站（Tk， k=1,2,3,4），其运价表如下表： A1A1 A2A2 A3A3 T1T1 T2T2 T3T3 T4T4 B1B1 B2B2 B3B3 B4B4 A1 0 2 4 3 2 2 4 4 8 8 4 A2 2 0 禁止 5 3 禁止 3 9 5 6 3 A3 4 禁止 0 1 禁止 3 2 3 11 4 2 T1 3 5 1 0 3 2
11、1 2 8 4 6 T2 2 3 禁止 3 0 1 2 4 5 2 7 T3 2 禁止 3 2 1 0 4 1 8 2 4 T4 4 3 2 1 2 4 0 1 禁止 2 6 B1 4 9 3 2 4 1 1 0 3 4 1 B2 8 5 11 8 5 8 禁止 3 0 1 2 B3 8 6 4 4 2 2 2 4 1 0 3 B4 4 3 2 6 7 4 6 1 2 3 0 产销情况如下表： 问：如何安排运输使得总运费最小？ B1B1 B2B2 B3B3 B4B4 产量产量 A1 6 A2 4 A3 12 销量 6 2 7 7 解： 按照上面的分析得到产销平衡表如下：（这无穷大取一个相对大的
12、值100) A1A1 A2A2 A3A3 T T 1 1 T2T2 T3T3 T4T4 B B 1 1 B2B2 B3B3 B4B4 产量产量 A1 0 2 4 3 2 2 4 4 8 8 4 28 A2 2 0 100 5 3 100 3 9 5 6 3 26 A3 4 100 0 1 100 3 2 3 11 4 2 34 T1 3 5 1 0 3 2 1 2 8 4 6 22 T2 2 3 100 3 0 1 2 4 5 2 7 22 T3 2 100 3 2 1 0 4 1 8 2 4 22 T4 4 3 2 1 2 4 0 1 100 2 6 22 B1 4 9 3 2 4 1 1
13、0 3 4 1 22 B2 8 5 11 8 5 8 100 3 0 1 2 22 B3 8 6 4 4 2 2 2 4 1 0 3 22 B4 4 3 2 6 7 4 6 1 2 3 0 22 销量 22 22 22 2 2 22 22 22 2 8 24 29 29 五、练习题五、练习题 运输问题的延伸： 现有三种产品bands、coils和plate需要从三 个供应地（GARY、CLEV、PITT）向七个需 求地（FRA、DET、LAN、WIN、STL、FRE、 LAF）供应，各种产品在各地之间的单位运 费及各地的供应量和需求总量如下三个表。 要求每个供应地到每个需求地三个产品的 总运量
14、不超过625。 问：如何安排运输使得总运费最小？ bandsbands FRA FRA DET DET LAN LAN WIN WIN STL STL FRE FRE LAFLAF 供应量供应量 GARY 30 10 8 10 11 71 6 400 CLEV 22 7 10 7 21 82 13 700 PITT 19 11 12 10 25 83 15 800 需求量 300 300 100 75 650 225 250 coilscoils FRA FRA DET DET LAN LAN WIN WIN STL STL FRE FRE LAFLAF 供应量供应量 GARY 39 14 11 14 16 82 8 800 CLEV 27 9 12 9 26 95 17 1600 PITT 24 14 17 13 28 99 20 1800 需求量 500 750 200 250 950 850 500 plateplate FRA FRA DET DET LAN LAN WIN WIN STL STL FRE FRE LAFLAF 供应量供应量 GARY 41 15 12 16 17 86 8 200 CLEV 29 9 13 9 28 99 18 300 PITT 26 14 17 13 31 104 20 300 需求量 100 100 0 50 200 100 250
