运输问题软件求解

1、一、运输问题与数学模型一、运输问题与数学模型 二、运输问题的二、运输问题的LINGO求解法求解法 三、应用案例分析三、应用案例分析 引例： 某公司有三个分厂生产某种物资，分别运往四个地区的销售公司去销售，有关分厂的产量（吨）、各销售公司的销量（吨）及单位物资的运价（千元/吨）如下表所示，求总的运费最小的调运方案？ 销地产地B1B2B3B4产 量A13113107A219284A3741059销 量3656 销地销地产地产地 B1 B2 Bn产量产量 A1c11c21 c1n a1 A2c21c22 c2n a2 Amcm1cm2 cmn am销量销量 b1 b2 bn 运输表运输表1 1、产销

2、平衡问题、产销平衡问题即即11mnijijab 设设 xij 表示产地表示产地 Ai 运往销地运往销地 Bj (i=1,2,m; j=1,2,n) 的运量的运量.11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn 销地销地产地产地 B1 B2 Bn产量产量 A1 x11c11 x12c12 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am销量销量 b1 b2 bn一、运输问题与数学模型一、运输问题与数学模型 2 2、产销不平衡问题

3、、产销不平衡问题（1） 11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn（2） 11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn二、运输问题的二、运输问题的LINGOLINGO求解方法求解方法针对产销平衡的运输问题模型，给出一般的针对产销平衡的运输问题模型，给出一般的LINGO模型如下模型如下 model:sets:row/1.m/: a; !m表示数组维数,即为生产地的个数 ar

4、range/1.n/:b; !n表示数组维数,即为销售地的个数link (row, arrange): c,x; !系数矩阵形状endsetsData:a=a1,a2,am ; ! 各生产地的实际产量;b=b1,b2,bn ; ! 各销售地的实际销量;c=c(1,1),c(1,2),c(1,n),c(m,1),c(m,2),c(m,n); !单位运价系数矩阵；EnddataOBJmin=sum(link(i,j):c(i,j)*x(i,j); !目标函数求最小for(row(i):sum(arrange(j):x(i,j)=a(i);); !约束条件for(arrange(j):sum(row

5、(i):x(i,j)=b(j);); !约束条件for(link(i,j):x(i,j)=0;); !非负约束END1. .nijijs txa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn11minmnijijijzc x例例1 1：某公司有三个分厂生产某种物资，分别运往四个地区的销某公司有三个分厂生产某种物资，分别运往四个地区的销售公司去销售，有关分厂的产量、各销售公司的销量（吨）及运售公司去销售，有关分厂的产量、各销售公司的销量（吨）及运价（千元价（千元/ /吨）如下表所示，求总的运费最小的调运方案？吨）如下表所示，求总的运费最小的调运方案？ B B1 1B

6、 B2 2B B3 3B B4 4产产 量量A A1 13 311113 310107 7A A2 21 19 92 28 84 4A A3 37 74 410105 59 9销销 量量3 36 65 56 6 解：解：设设 xij 表示产地表示产地 Ai 运往销地运往销地 Bj (i=1,2,3;j=1,2,4) 的运量的运量.则则3411minijijijzc x41. .ijijstxa，1,2,3i 31ijjixb，1,2,4j 01,2,3;1,2,4ijxij其中，其中，123(,)(7,4,9)a a a其中，其中，1234( ,)(3,6,5,6)b b b b分析：分析：由

7、于三个产地总产量为由于三个产地总产量为7+4+9=20； 四个销地的总销四个销地的总销量为量为3+6+5+6=20，所以这是，所以这是一个产销平衡问题。一个产销平衡问题。求解该问题的LINGO程序如下model:sets:row/1.3/: a; arrange/1.4/:b; link (row, arrange): c,x; endsetsData:a=7,4,9 ;b=3,6,5,6;c=3,11,3,10,1,9,2,8,7,4,10,5; EnddataOBJmin=sum(link(i,j):c(i,j)*x(i,j); for(row(i):sum(arrange(j):x(i,

8、j)=a(i);); for(arrange(j):sum(row(i):x(i,j)=b(j);); for(link(i,j):x(i,j)=0;); ENDB B1 1B B2 2B B3 3B B4 4产产 量量A A1 13 311113 310107 7A A2 21 19 92 28 84 4A A3 37 74 410105 59 9销销 量量3 36 65 56 6三、应用案例分析三、应用案例分析 某制冰厂每年某制冰厂每年1 4 季度必须供季度必须供应冰块应冰块 15、20、25、10（千吨）（千吨）. .已知该厂各季度冰已知该厂各季度冰 块的生产能力及冰块的单位成本如表块的

9、生产能力及冰块的单位成本如表. . 如果生产出来如果生产出来的冰块不在当季度使用，每千吨冰块存储一个季度的冰块不在当季度使用，每千吨冰块存储一个季度费用为费用为4（千元）（千元）. .又设该制冰厂每年第又设该制冰厂每年第3季度末对贮季度末对贮冰库进行清库维修冰库进行清库维修. .问应如何安排冰块的生产，可使问应如何安排冰块的生产，可使该厂全年生产、该厂全年生产、存储费用最少？存储费用最少？试建立该问题试建立该问题的运输模型。的运输模型。季季 度度 生产能力（千吨）生产能力（千吨） 单位成本（千元）单位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 5例例 1 (生产调度问题生

10、产调度问题)季季 度度 生产能力（千吨）生产能力（千吨） 单位成本（千元）单位成本（千元） 1 25 52 18 7 3 16 8 4 15 5解：解：设设xij表示第表示第i季度生产季度生产第第j季度销季度销售的冰块量售的冰块量（千吨）（千吨） 1 4 季度冰块需求季度冰块需求量分别为：量分别为： 15、20、25、10（千吨）（千吨） 第第3季度末对贮季度末对贮冰库进行清库维修，且冰库进行清库维修，且每千吨冰块存储一个季每千吨冰块存储一个季度费用为度费用为 4（千元）（千元） Bj Ai B1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25

11、105913MMMMMM5118179137求解该问题的LINGO程序如下model:sets:row/1.4/: a; arrange/1.4/:b; link (row, arrange): c,x; endsetsData:a=25,18,16,15;b=15,20,25,10 ;c=5,9,13,10000, 10000,7,11,10000,10000,10000,8,10000,9,13,17,5; EnddataOBJmin=sum(link(i,j):c(i,j)*x(i,j); for(row(i):sum(arrange(j):x(i,j)=0;); END Bj Ai B

12、1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25 105913MMMMMM5118179137程序运行结果为：10, 1,16, 9, 9,11,1444413323221211xxxxxxx其余的)4 , 1; 4 , 1(0jixij且.518minz 所以，生产安排为：第一季度生产25吨冰，其中14吨当季使用，11吨在第二季度使用；第二季度生产18吨冰，其中9吨当季使用，9吨在第三季度使用；第三季度生产16吨冰，全部当季使用；第四季度生产11吨冰，其中10吨当季使用，1吨在下一年的第一季度使用。生产和存储总费用为518千元。例例2 ( (

13、空车调度问题空车调度问题) ) 某航运公司承担六个港口城市某航运公司承担六个港口城市 A、B、C、D、E、F 的四条固定航线的物资运输任的四条固定航线的物资运输任务务. . 已知各条航线的起点、终点城市及每天航班数见已知各条航线的起点、终点城市及每天航班数见表表1，假定各条航线使用相同型号的船只，又各城市间，假定各条航线使用相同型号的船只，又各城市间的航程天数见表的航程天数见表2. 又知每条船只每次装卸货的时间各又知每条船只每次装卸货的时间各需一天，则该航运公司至少应配备多少条船，才能满足需一天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？所有航线的运货需求？航航线线起点起点城

14、市城市终点终点城市城市每天航班每天航班数数1ED32BC23AF14DB1表表1 1 到到从从ABCDEFA0121477B1031388C23015557851703F7852030表表2 2解解： 该公司所需配备船只分两部分该公司所需配备船只分两部分. .1 1载货航程需要的周转船只数载货航程需要的周转船只数航航线线起点起点城市城市终点终点城市城市每天航班每天航班数数1ED32BC23AF14DB1表表1 1 到到从从ABCDEFA0121477B1031388C23015557851703F7852030表表2 2 如航线如航线1，在港

15、口，在港口E 装货装货1 天，天，E 至至 D 航程航程17天，天，在在D 卸货卸货1天，总计天，总计19天天. . 每天每天3 航班，故该航线周转航班，故该航线周转船只需船只需5757条条. .航线航线装货天数装货天数航程天数航程天数卸货天数卸货天数小计小计航班数航班数需周转船只数需周转船只数11171193572131521031719194113115115累计共需周转船只数累计共需周转船只数91条条.2 2、各港口间调度所需船只数、各港口间调度所需船只数港口城市港口城市每天到达每天到达每天需求每天需求余缺数余缺数A01-1B12-1C202D312E03-3F101 港口每天到达与需要

16、的船只不同，如表港口每天到达与需要的船只不同，如表. .为使配备船只数最少，应做到周转的空船数为最少为使配备船只数最少，应做到周转的空船数为最少. . 建立运输模型，建立运输模型，C、D、F 为空船的产地为空船的产地，A、B、E 为销地，单位运价为相应各港口之间的船只航程天数为销地，单位运价为相应各港口之间的船只航程天数. 港港 口口 A B E每天多余船只每天多余船只 C2 35 2 D141317 2 F783 1每天缺少船只每天缺少船只 1 1 3 用用 LINGOLINGO软件软件求出空船的最优调求出空船的最优调度方案度方案. . 最少需周转的最少需周转的空船数为空船数为 ？条条. .

17、40model:sets:row/1.3/: a; arrange/1.3/:b; link (row, arrange): c,x; endsetsData:a=2,2,1; b=1,1,3; c=2,3,5,14,13,17,7,8,3; EnddataOBJmin=sum(link(i,j):c(i,j)*x(i,j);for(row(i):sum(arrange(j):x(i,j)=a(i);); for(arrange(j):sum(row(i):x(i,j)=b(j);); for(link(i,j):x(i,j)=0;); END附：例附：例2的的LINGO程序程序运行得结果：运

18、行得结果：40; 1, 1, 1, 1,xxxxx（1 1）载货航程需要的周转船只数）载货航程需要的周转船只数9191条条航航线线起点起点城市城市终点终点城市城市每天航班每天航班数数1ED32BC23AF14DB1表表1 1 到到从从ABCDEFA0121477B1031388C23015557851703F7852030表表2 2航线航线装货天数装货天数航程天数航程天数卸货天数卸货天数小计小计航班数航班数需周转船只数需周转船只数11171193572131521031719194113115115（2 2）空船调运需要的周转船只数）空船调运

19、需要的周转船只数4040条条航航线线起点起点城市城市终点城终点城市市每天航每天航班数班数1E（19）D32B（5） C23A（9） F14D（15） B1表表1 1 到到从从ABCDEFA0121477B1031388C23015557851703F7852030表表2 2 港港 口口 A B E每天多余船只每天多余船只 C 12 3 15 2 D14 113 117 2 F78 13 1每天缺少船只每天缺少船只 1 1 3练习：练习：( (设备的生产计划问题设备的生产计划问题) ) 设某制造企业根据合同要求设某制造企业根据合同要求, ,从当年起连续三年在年末各从当年起连续三年在年末各提供三套型号规格