运筹学光明市的菜篮子工程讲述.pptx

光明市的菜篮子工程 导师：石小平 学生：潘建攻 吕一峰 张 芮 contents 目 录 问题重述 1 2 3 4 符号约定与假设 问题分析 模型建立与求解 1.问题重述 问题重述 光明市是一个人口不到15万人的小城市，根据该市的蔬菜种植情况分别在花市(A)、城乡路口(B)和下塘街(C)设三个收购点。清晨5点前菜农将蔬菜送至各收购点，再由各收购点分送到全市的8个菜市场。该市道路情况、各路段距离（单位：100m）及各收购点、菜市场①②…..⑧的具体位置如图： 问题重述 按常年情况，Ａ、Ｂ和Ｃ三个收购点每天收购量分别为200、170和160(单位：100kg)，各菜市场的每天需求量及发生供应短缺时带来的损失(元/100kg)见表。设从收购点至各菜市场蔬菜调运费用为1元/(100kg·100m)。 菜市场 每天需求(100Kg) 短缺损失(元/100Kg) ① 75 10 ② 60 8 ③ 80 5 ④ 70 10 ⑤ 100 10 ⑥ 55 8 ⑦ 90 5 ⑧ 80 8 请你解决以下问题： （1）为该市设计一个从各收购点至各菜市场的定点供应方案，使用于蔬菜调运及预期的短期损失最小。 （2）若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案。 （3）为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增加的蔬菜每天应分别向A、B、C三个采购点各供应多少最经济合理。 02 2.符号约定与假设 假设一：只考虑运输费用和短缺费用，不考虑装卸等其他费用。 假设二：假设运输的蔬菜路途中没有损。 假设三：假设各市场蔬菜只来源于三个收购站，无其他来源且三个收购站所收购蔬菜全部运往8个菜市场。 假设四：假设规划增加蔬菜种植面积后，蔬菜供应总量恰好能满足8个菜市场的需求量。 符号约定与假设 符号约定与假设 符号 符号说明 xij 第i个收购点向j市场供给的数量 (i=1,2,3, j=1,2 … 8) x4j 第j个市场因供给量小于需求量的单位短缺损失 (j=1,2 … 8) pij 第i个收购点向j 市场供给的单位运费 bi 第i个收购点供应量 (i=1,2,3,4) dj 第j个市场需求量 (j=1,2 … 8) 3.问题分析 问题分析 这是一个产销不平衡的规划问题(产小于销)，三个收购点每天蔬菜收购量530(100kg)，而8个菜市场每天共需610(100kg)，所以，8个菜市场每天将共短缺80(100kg)。可设一个虚拟的D，每天蔬菜收购量为80(100kg)，正好弥补8个菜市场每天短缺的那部分，则如下表：但虚拟收购点D运往8个菜市场的运费无法计算。在本题中，只考虑运费及蔬菜短缺时的总费用，考虑到虚拟收购点D运往8个菜市场的路径无法确定，及D所运往8个菜市场的蔬菜均为各个菜市场短缺的，故可将8个菜市场短缺所造成的损失等效于D运往8个菜市场的运费。 1 2 3 4 5 6 7 8 产量 A 200 B 170 C 160 D 80 销量 75 60 80 70 100 55 90 80 610 问题分析 为了求解模型，必须求出系数(pij)，其中每一 表示第i个收购点向j市场供给单位量蔬菜的运费。但因为从收购点至各菜市场单位量蔬菜单位路程的调运费用为1元/(100kg*100m)，而蔬菜的单位量为100kg，单位距离为100m ，则可求出第i个收购点到第j市场每单位蔬菜的单位距离运费为1元/(100m *100kg)*100m *100kg=1元。因而pij在数值上等于第i个收购点到第j市场的距离值，从而等价于一个求最短路的问题。对于x4j (j=1,…,8),因其每短缺100kg损失1元，而蔬菜的单位量为100kg，故p4j在数值上等于第j个市场供应短缺时带来的损失值。 从图中可以找出从第i个收购点到第j市场的最小距离值，也即单位最小运费 pij 。如下： 1 2 3 4 5 6 7 8 A 4 8 8 19 11 6 22 20 B 14 7 7 16 12 16 23 17 C 20 19 11 14 6 15 5 10 D 10 8 5 10 10 8 5 8 4.模型建立与求解 模型建立与求解 由上述分析，这是一道运输问题，我们建立目标函数以及给出约束条件即可求解。 目标函数的总费用Z包括两项:蔬菜调运费、各市场供给量小于需求量的短缺损失。由问题分析中，我们指出将短缺损失的费用等效算作运输费用。即可得下列式子： 目标函数：