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