案例 2：光明市的菜篮子工程 光明市是一个人口不到 15 万人的小城市。根据该市的蔬菜种植情况，分别在花市（A）、 城乡路口（B）和下塘街（C）设三个收购点。清晨 5 点前菜农将蔬菜送至各收购点，再由 各收购点分别送到全市的 8 个菜市场。该市道路情况、各路段距离（单位：100m）及各收 购点、菜市场①，②，…，⑧的具体位置见图。 7 8 4 A 4 ① 5 6 5 7 ⑥ 7 8 4 7 6 8 10 C 5 ⑦ ② 3 5 7 6 7 ③ 6 3 5 ⑤ 6 10 11 B 11 ④ 5 6 ⑧ 按常年情况，A、B、C 三个收购点每天收购量分别为 200、170 和 160（单位：100kg）， 各菜市场每天的需求量及发生供应短缺时带来的损失（元/100 kg）见下表，设从收购点至各 菜市场蔬菜调运费用为 1 元/（100 kg·100m） ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 菜市场 80 75 每天需求（100kg） 短缺损失（元/100 kg） 10 8 100 10 90 5 55 8 70 10 80 5 60 8 （1）为该市设计一个从各收购点至各菜市场的定点供应方案，使用于蔬菜调运及预期 的短缺损失为最小； （2）若规定各菜市场短缺量一律不超过需求量的 80%，重新设计定点供应方案； （3）为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增产的 蔬菜每天应分别向 A、B、C 三个收购点各供应多少最经济合理。 解：先用确定最短路的方法求出三个收购点至八个菜市场的最短路，距离如下 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 供应量 4 8 A 14 7 B C 20 19 虚产地 10 8 需求量 75 60 200 170 160 80 75 11 12 6 10 100 19 16 14 10 70 6 16 15 8 55 20 17 10 8 80 22 23 5 5 90 8 7 11 5 80 Min 4x11+8x12+8x13+19x14+11x15+6x16+22x17+20x18+14x21+7x22+7x23+16x24 +12x25+16x26+23x27+17x28+20x31+19x32+11x33+14x34+6x35+15x36+5x37+10x38 +10x41+8x42+5x43+10x44+10x45+8x46+5x47+8x48 st x11+x12+x13+x14+x15+x16+x17+x18=200 1 

x21+x22+x23+x24+x25+x26+x27+x28=170 x31+x32+x33+x34+x35+x36+x37+x38=160 x41+x42+x43+x44+x45+x46+x47+x48=80 x11+x21+x31+x41=75 x12+x22+x32+x42=60 x13+x23+x33+x43=80 x14+x24+x34+x44=70 x15+x25+x35+x45=100 x16+x26+x36+x46=55 x17+x27+x37+x47=90 x18+x28+x38+x48=80 end A B C 虚产地 需求量 75 60 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 供应量 75 60 200 170 160 80 75 30 70 100 40 40 80 70 70 90 90 80 80 55 55 最小费用是： 4610.00 元 （2）min 4x11+8x12+8x13+19x14+11x15+6x16+22x17+20x18+14x21+7x22 +7x23+16x24+12x25+16x26+23x27+17x28+20x31+19x32+11x33+14x34+6x35 +15x36+5x37+10x38+10x41+8x42+5x43+10x44+10x45+8x46+5x47+8x48 st x11+x12+x13+x14+x15+x16+x17+x18=200 x21+x22+x23+x24+x25+x26+x27+x28=170 x31+x32+x33+x34+x35+x36+x37+x38=160 x41+x42+x43+x44+x45+x46+x47+x48=80 x11+x21+x31+x41=75 x12+x22+x32+x42=60 x13+x23+x33+x43=80 x14+x24+x34+x44=70 x15+x25+x35+x45=100 x16+x26+x36+x46=55 x17+x27+x37+x47=90 x18+x28+x38+x48=80 x11+x21+x31>=60 x12+x22+x32>=48 x13+x23+x33>=64 x14+x24+x34>=56 x15+x25+x35>=80 x16+x26+x36>=44 x17+x27+x37>=72 x18+x28+x38>=64 end ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 供应量 75 10 50 A B C 虚产地 需求量 75 60 最小费用是： 4806.00 元 （3）min 4x11+8x12+8x13+19x14+11x15+6x16+22x17+20x18 +14x21+7x22+7x23+16x24+12x25+16x26+23x27+17x28 +20x31+19x32+11x33+14x34+6x35+15x36+5x37+10x38 200 170 160 80 75 60 24 16 100 64 16 80 56 14 70 72 18 90 64 16 80 55 55 2 

st x11+x12+x13+x14+x15+x16+x17+x18>=200 x21+x22+x23+x24+x25+x26+x27+x28>=170 x31+x32+x33+x34+x35+x36+x37+x38>=160 x11+x21+x31=75 x12+x22+x32=60 x13+x23+x33=80 x14+x24+x34=70 x15+x25+x35=100 x16+x26+x36=55 x17+x27+x37=90 x18+x28+x38=80 end A B C 需求量 75 60 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 供应量 75 40 20 80 80 70 70 30 70 100 55 55 90 90 80 80 200 170 240 75 最小费用是：4770.00 元 增产的蔬菜不供应 A 收购点，也不供应 B 收购点，供应 C 收购点 80 个单位（100kg）。 model: ! A 4 Warehouse, 8 Customer Transportation Problem; SETS: WAREHOUSE / WH1, WH2, WH3,WH4/ : CAPACITY; CUSTOMER / C1, C2, C3, C4,C5,C6,C7,C8/ : DEMAND; ROUTES( WAREHOUSE, CUSTOMER) : COST, VOLUME; ENDSETS ! The objective; [OBJ] MIN = @SUM( ROUTES: COST * VOLUME); ! The demand constraints; @FOR( CUSTOMER( J): [DEM] @SUM( WAREHOUSE( I): VOLUME( I, J)) >= DEMAND( J)); ! The supply constraints; @FOR( WAREHOUSE( I): [SUP] @SUM( CUSTOMER( J): VOLUME( I, J)) <= CAPACITY( I)); ! Here are the parameters; DATA: CAPACITY = 200,170,160,80; DEMAND = 75,60,80,70,100,55,90,80; COST = 4,8,8,19,11,6,22,20,14,7,7,16,12,16,23,17,20,19,11,14,6,15,5,10,1 0,8,5,10,10,8,5,8; ENDDATA end 3