运筹学案例:光明市的菜篮子工程
光明市的菜篮子工程 一、问题提出 二、问题求解 三、问题(1)的求解 四、问题(2)的求解 五、问题(3)的求解
一、问题提出 光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况,分别在花市(A)、城乡路口(B)和下塘街(C)设三个收购点。清晨5点前菜农将蔬菜送至各收购点,再由各收购点分别送到全市的8个菜市场。该市道路情况、各路段距离(单位:100m)及各收购点、菜市场①,②,…,⑧的具体位置见图。 按常年情况,A、B、C三个收购点每天收购量分别为200、170和160(单位:100kg),各菜市场每天的需求量及发生供应短缺时带来的损失(元/100 kg)见下表,设从收购点至各菜市场蔬菜调运费用为1元/(100 kg·100m)
① ② ③ ④ ⑤ ⑥ ⑧ ⑦ A B C 4 5 6 7 8 3 11 10
菜市场 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 每天需求(100kg) 75 60 80 70 100 55 90 短缺损失(元/100 kg) 10 8 5 (1)为该市设计一个从各收购点至各菜市场的定点供应方案,使用于蔬菜调运及预期的短缺损失为最小; (2)若规定各菜市场短缺量一律不超过需求量的20%,重新设计定点供应方案; (3)为满足城市居民的蔬菜供应,光明市的领导规划增加蔬菜种植面积,试问增产的蔬菜每天应分别向A、B、C三个收购点各供应多少最经济合理。
二、问题求解 先用确定最短路的方法求出三个收购点至八个菜市场的最短路,距离如下表 : 菜市场 收购点 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ A 4 8 19 11 6 22 20 B 14 7 16 12 23 17 C 15 5 10 由于3个收购点的收购量小于8个菜市场的供应量,出现供应短缺。发生供应短缺时会带来损失 ,因此增加一个虚的收购点D,由虚的收购点D供应的蔬菜就是供应短缺。将供应短缺的单位损失代替供应成本,考虑产销平衡的运输问题。
分别对于(1)、(2)、(3)建立不同的运输问题数学模型,解决相应的问题。 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 供 A 200 4 8 19 11 6 22 20 B 170 14 7 16 12 23 17 C 160 15 5 10 D 80 需 75 60 70 100 55 90 分别对于(1)、(2)、(3)建立不同的运输问题数学模型,解决相应的问题。
三、问题(1)的求解 问题(1):为该市设计一个从各收购点至各菜市场的定点供应方案,使用于蔬菜调运及预期的短缺损失为最小。
Min=4. x11+8. x12+8. x13+19. x14+11. x15+6. x16+22. x17+20. x18+14 Min=4*x11+8*x12+8*x13+19*x14+11*x15+6*x16+22*x17+20*x18+14*x21+7*x22+7*x23+16*x24+12*x25+16*x26+23*x27+17*x28+20*x31+19*x32+11*x33+14*x34+6*x35+15*x36+5*x37+10*x38+10*x41+8*x42+5*x43+10*x44+10*x45+8*x46+5*x47+8*x48; 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;
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,10,8,5,10,10,8,5,8; ENDDATA
求解结果 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 供应量 A 75 40 30 55 200 B 20 80 70 170 C 90 160 虚产地 需求量 60 100 最小费用是: 4610.00元 菜市场①—⑦都能满足供应,但是菜市场⑧完全没有供应。附近居民无法买到菜,显然是不合适的。因此考虑问题(2),每个菜市场至少要满足其需求量的80%。
四、问题(2)的求解 (2)若规定各菜市场短缺量一律不超过需求量的20%,重新设计定点供应方案 。 8个菜市场的需求量分别为75,60,80,70,100,55,90,80;需求量的80%分别为60,48,64,56,80,44,72,64.因此,可以建立如下的运输问题数学模型。
Min=4*x11+8*x12+8*x13+19*x14+11*x15+6*x16+22*x17+20*x18+14*x21 +7*x22+7*x23+16*x24+12*x25+16*x26+23*x27+17*x28+20*x31+19*x32+11*x33 +14*x34+6*x35+15*x36+5*x37+10*x38+10*x41+8*x42+5*x43+10*x44+10*x45 +8*x46+5*x47+8*x48; 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;
求解结果 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 供应量 A 75 10 60 55 200 B 50 64 56 170 C 24 72 160 虚产地 16 14 18 80 需求量 70 100 90 各菜市场至少满足其需求量的80%,这时的最小费用是:4806.00元
五、问题(3)的求解 问题(3):为满足城市居民的蔬菜供应,光明市的领导规划增加蔬菜种植面积,试问增产的蔬菜每天应分别向A、B、C三个收购点各供应多少最经济合理。 将约束条件中各菜市场的需求约束取等号,各收购点的供应约束改为分别不小于200,170和160. 重新建立运输问题数学模型求解,即可求出各收购点分别增加的供应量。
Min=4. x11+8. x12+8. x13+19. x14+11. x15+6. x16+22. x17+20. x18+14 Min=4*x11+8*x12+8*x13+19*x14+11*x15+6*x16+22*x17+20*x18+14*x21+7*x22+7*x23+16*x24+12*x25+16*x26+23*x27+17*x28+20*x31+19*x32+11*x33 +14*x34+6*x35+15*x36+5*x37+10*x38; 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;
求解结果 最小费用是:4770.00元 增产的蔬菜不供应A收购点,也不供应B收购点,供应C收购点80个单位(100kg)。 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 供应量 A 75 40 30 55 200 B 20 80 70 170 C 90 240 需求量 60 100 最小费用是:4770.00元 增产的蔬菜不供应A收购点,也不供应B收购点,供应C收购点80个单位(100kg)。 光明市的领导在该市的南部郊区规划增加蔬菜种植面积 ,增加供应蔬菜80百公斤,即8000公斤,供应C收购点最经济合理。