光明市的菜篮子工程

光明市的菜篮子工程 李伟一 问题背景 光明市是一个人口不到15万人的小城市 根据该市的蔬菜种植情况 分别在花市 A 城乡路口 B 和下塘街 C 设三个收购点 再有个收购点分别送到全市的8个菜市场 该市道路情况 各路段距离 单位 100m 及各收购点 菜市场 的具体位置见图3 2 按常年情况 A B C三个收购点每天收购量分别为200 170 160 单位 100kg 各菜市场的每天需求量及发生供应短缺时带来的损失 元 100kg 见表3 设从收购点至各菜市场蔬菜调运费为1元 100kg 100m a 为该市设计一个从收购点至各个菜市场的定点供应方案 使用于蔬菜调运及预期的短期损失为最小 b 若规定各菜市场短缺量一律不超过需求量的20 重新设计定点供应方案 c 为满足城市居民的蔬菜供应 光明市的领导规划增加蔬菜种植面积 试问增加的蔬菜每天应分别向A B C三个采购点各供应多少最经济合理 问题分析 本题旨在解决如何减少菜篮子工程的开销 即蔬菜调运费用和短缺损失两部分的费用总和 蔬菜调运费用主要取决于蔬菜调运路径的选取 这是典型的旅行商问题 采用弗洛伊德算法和蚁群算法 用MATLAB软件编程求解即可得到最路径 短缺损失主要取决于调运到各菜市场的收购量 菜篮子工程的开销取决于这两部分 对两部分的方案进行线性规划 用LINGO软件进行求解即可得到最优分配方案 1 只考虑蔬菜调运费用和短缺损失费用 不考虑装卸等其他费用 2 假设蔬菜在调运路途中没有损耗 3 假设各菜市场蔬菜只来源于A B C三个收购站 而无其他来源 4 假设各收购站供应蔬菜质量以及单位运价相同 5 假设各收购站可以作为中转站 基本假设 符号说明 模型的建立 目标函数蔬菜运输和短缺损失的总费用Z包括两部分 蔬菜调运费用P 短缺损失费用P Xij 第i个收购点向第j个菜市场运输蔬菜的数量 i 1 2 3 j 1 8 Dij 调运路径中 第i个收购点到第j个菜市场的距离 i 1 2 3 j 1 8 A 从收购点至各菜市场蔬菜调运费单价 则蔬菜调运总费用P为 ai 第i个收购点的供应量 i 1 2 3 bj 第j个菜市场的需求量 j 1 8 B 第j个菜市场因供给小于需求量的单位短缺损失 则短缺损失总费用为Q 则蔬菜运输和短缺损失的总费用Z Z P Q 返回 A i j 488191162220 14771612162317 20191114615510 适当改变符号x i j 为 x 1 j 记为xj x 2 j 记为yj x 3 j 记为zj 那么 各菜市场的短缺量分别为 75 x1 y1 z1 60 x2 y2 z2 80 x3 y3 z3 70 x4 y4 z4 100 x5 y5 z5 55 x6 y6 z6 90 x7 y7 z7 80 x8 y8 z8 那么短缺损失为10 75 x1 y1 z1 8 60 x2 y2 z2 5 80 x3 y3 z3 10 70 x4 y4 z4 10 100 x5 y5 z5 8 55 x6 y6 z6 5 90 x7 y7 z7 8 80 x8 y8 z8 运费为4x1 8x2 8x3 19x4 11x5 6x6 22x7 20 x8 14y1 7y2 7y3 16y4 12y5 16y6 23y7 17y8 20z1 19z2 11z3 14z4 6z5 15z6 5z7 10z8 问题 a 的模型 那么总费用即为Z 6x1 3x3 9x4 x5 2x6 17x7 12x8 4y1 y2 2y3 6y4 2y5 8y6 18y7 9y8 10z1 11z2 6z3 4z4 4z5 7z6 2z8 4860 约束条件表示为 结果分析 在该题目的假设下 最经济合理的蔬菜定点供应方案是 收购点A每天向菜市场1运送蔬菜75千克 向5运送70千克 向6运送55千克 收购点B每天向菜市场2运送蔬菜60千克 向3运送80千克 向4运送30千克 收购点C每天向菜市场5运送蔬菜30千克 向7运送90千克 8运送40千克 在这种情况下使用于蔬菜调运及预期的短缺损失为 4610元 在这种供应方案下 除了菜市场4和8外 其余的菜市场的蔬菜供应都得到满足 其中菜市场4和8都短缺40千克 若规定各菜市场短缺量一律不超过需求量的20 重新设计定点供应方案 对于该问题 目标函数并没有任何变化 总费用仍然是调运费用以及短缺损失 该问题只是在原问题的基础上加上各菜市场短缺量一律不超过需求量的20 这一约束条件 各菜市场的短缺量在以上问题中已求出 该问题只需要在原问题的基础上加上以下约束即可 方案b 利用Matlab实现过程 目标函数 Z 6x1 3x3 9x4 x5 2x6 17x7 12x8 4y1 y2 2y3 6y4 2y5 8y6 18y7 9y8 10z1 11z2 6z3 4z4 4z5 7z6 2z8 4860 x1 x2 x3 x4 x5 x6 x7 x8 200 y1 y2 y3 y4 y5 y6 y7 y8 170 z1 z2 z3 z4 z5 z6 z7 z8 160 x1 y1 z1 0 8 75 x2 y2 z2 0 8 60 x3 y3 z3 0 8 80 x4 y4 z4 0 8 70 x5 y5 z5 0 8 100 x6 y6 z6 0 8 55 x7 y7 z7 0 8 90 x8 y8 z8 0 8 80 约束条件 返回 f 目标函数的系数 目标函数必须求最小值 A 线性不等式约束的约束系数b 11 3 线性不等式的不等号右边数字Aeq 201 线性等式约束的约束系数beq 1 线性等式的不等号右边数字lb 0 0 0 变量的边界约束 下界的约束ub Inf Inf Inf 下界的约束由于无上界 故设ub Inf Inf Inf x fval exitflag output lambda linprog f A b Aeq beq lb ub 利用Matlab实现语言 在该题目的假设下 最经济合理的蔬菜定点供应方案是 收购点A向菜市场1运送蔬菜75千克 向3运送10千克 向5运送60千克 向6运送55千克 收购点B向菜市场2运送蔬菜60千克 向3运送54千克 向4运送56千克 收购点C向菜市场5运送蔬菜24千克 向7运送72千克 向8运送64千克 在这种情况下使用于蔬菜调运及预期的短缺损失为 4806元 其中 只有菜市场1 2 6的需求得到满足 其余菜市场的短缺量分别为 市场3短缺80 10 54 16千克 市场4短缺70 56 14千克 市场5短缺100 60 24 16千克 市场7短缺90 72 18千克 市场8短缺80 64 16千克 说明 x linprog c A b Aeq beq lb ub x0 options 用options指定的优化参数进行最小化 可以使用optimset来设置这些参数 x fval linprog 在优化计算结束之时返回线性规划问题在解x处的目标函数值fval x fval exitflag linprog 在优化计算结束之时返回exitflag值 描述函数计算的退出条件 x fval exitflag output linprog 在优化计算结束之时返回返回结构变量output x fval exitflag output lambda linprog 在优化计算结束之时返回线性规划问题最优解x处的拉格朗日乘子lambda 为满足城市居民的蔬菜供应 光明市的领导规划增加蔬菜种植面积 试问增加的蔬菜每天应分别向A B C三个采购点各供应多少最经济合理 为满足城市居民的需求 增种的蔬菜量应使得菜市场1到8都达到每天的需求量 另外显然有 x1 x2 x3 x4 x5 x6 x7 x8 200 y1 y2 y3 y4 y5 y6 y7 y8 170 z1 z2 z3 z4 z5 z6 z7 z8 160 方案C 目标函数和前两个题是一样的 应用 软件求解 在运行窗口中输入以下内容 min 6 x1 3 x3 9 x4 x5 2 x6 17 x7 12 x8 4 y1 y2 2 y3 6 y4 2 y5 8 y6 18 y7 9 y8 10 z1 11 z2 6 z3 4 z4 4 z5 7 z6 2 z8 4860 x1 x2 x3 x4 x5 x6 x7 x8 200 y1 y2 y3 y4 y5 y6 y7 y8 170 z1 z2 z3 z4 z5 z6 z7 z8 160 x1 y1 z1 75 x2 y2 z2 60 x3 y3 z3 80 x4 y4 z4 70 x5 y5 z5 100 x6 y6 z6 55 x7 y7 z7 90 x8 y8 z8 80 结果分析增种后的定点供应方案是 收购点A向菜市场1输送蔬菜75千克 向3输送40千克 向5输送30千克 向6输送55千克 该收购点每天共向外运送蔬菜 即每天收购量 200千克