北方食品公司投资方案规划

北方食品公司投资方案规划 一、 背景 北方食品公司为北京市大型现代化肉类食品加工企业，其主营业务为屠宰、加工、批发鲜冻猪肉．公司位于北京南郊．目前公司主要向市区 106 个零售商店批发猪肉，并负责送货．公司经营中存在的主要问题是客户反映公司送货不及时，有时商店营业后货仍未送到，影响客户经营．问题产生的主要原因是冷藏车数量不足，配置不合理，该公司拥有的均为 4 t 冷藏车，每辆车送货 6 ～ 8 个点，送货时间较长，特别是 7 点以后，交通难以保障，致使送货延迟．但准时送货是客户十分看重的服务问题，几次送货不及时就能丢失 1 个客户．公司在 1998 年经营中因此问题曾丢失 10 多个客户．因此，如何保障准时送货成为制约企业发展的瓶颈．为此，公司准备增加冷藏车数量．现就该公司如何在保障送货的前提下最优配置冷藏车问题做一简要探讨． 二、 问题简述 北方公司 106 个零售点中，有 50 个点在距工厂半径 5 km 内，送货车 20 min 可以到达； 36 个在 10 km 内，送货车 40 min 可以到达； 20 个在 10 km 以上，送货车 60 min 可以到达．冷藏车种类有 2 t ， 4 t 两种．该问题实际是如何用最少的投资 ( 冷藏车 ) 在指定时间内以最少的成本 ( 费用 ) 完成运输任务．该问题包括运输问题、最短路线问题，且各点间距离不等，销量不等．为便于计算，对该问题各类条件做如下简化： (1) 106 个零售点日销量在 0.3 ～ 0.6 t ，但大多数在 0.4 ～ 0.5 t ．为简化计算，设定每个点日销量 0.5 t ． (2) 将 5 km 内点设为 A 类点， 10 km 内点设为 B 类点， 10 km 以上设为 C 类点．从工厂到 A 类点的时间为 20 min ，到 B 类点的时间为 40 min ，到 C 类点的时间为 60 min ． A 类点间运输时间为 5 min ， B 类点间运输时间为 10 min ， C 类点间运输时间为 20 min ．不同类型点间时间为 20 min ．每点卸货、验收时间为 30 min ． (3) 工厂从凌晨 4 点开始发货 ( 过早无人接货 ) ，车辆发车先后时间忽略不计．因 7 点后交通没有保障，故要求冷藏车必须在 7 点前到达零售点，所以最迟送完货时间为 7 ∶ 30 ．全程允许时间为 210 min ． (4) 可将该问题看作线性规划中的裁剪问题，将冷藏车可能运输方案作为裁剪方案处理．已知 4 t 车每台 18 万元， 2 t 车每台 12 万元．求出投资最少的配车方案． 解：由于总的时间为210分钟，因此每种类型车可能的路线是有限的，不妨穷举出来： 2吨车可能的路线(2吨车每点的卸货，验收时间为30min)： 路线 1 2 3 4 5 6 7 8 9 10 11 12 A 4 3 3 2 2 2 1 1 1 0 0 0 B 0 1 0 2 1 0 3 2 1 4 3 2 C 0 0 1 0 1 2 0 1 2 0 1 2 time 155 170 190 175 185 205 180 190 200 190 200 210                           4吨车可能的路线(4吨车每点卸货，验收时间为15min)： 路线 13 14 15 16 17 18 19 20 21       A 8 7 7 6 6 5 5 4 3       B 0 1 0 2 1 3 2 4 5       C 0 0 1 0 1 0 1 0 0       time 175 190 190 195 205 200 210 205 210                                 设Xi为跑路线i的车的数量。 2吨车数量为：Q2=   4吨车数量为：Q4= 总成本TC为：TC=12 Q2+18 Q4 目标函数： MIN  TC=12 Q2+18 Q4 约束条件为： 4X1+3X2+3X3+2X4+2X5+2X6+X7+X8+X9+8X13+7X14+7X15+6X16+6X17+5X18+5X19+4X20+3X21≥50 X2+2X4+X5+3X7+2X8+X9+4X10+3X11+2X12+X14+2X16+X17+3X18+2X19+4X20+5X21≥36 X3+X5+2X6+X8+2X9+X11+2X12+X15+X17+X19≥20 利用管理运筹学软件中线性规划模块求得结果如下： **********************最优解如下************************* 目标函数最优值为 : 254.736 变量 最优解 相差值 ------- -------- -------- x1 0 4.364 x2 0 3.818 x3 0 2.727 x4 0 3.273 x5 0 2.182 x6 0 1.091 x7 0 2.727 x8 0 1.636 x9 0 .545 x10 0 2.182 x11 0 1.091 x12 5.409 0 x13 0 2.727 x14 0 2.182 x15 0 1.091 x16 0 1.636 x17 0 .545 x18 0 1.091 x19 9.182 0 x20 0 .545 x21 1.364 0 约束 松弛/剩余变量 对偶价格 ------- ------------------- -------- 1 0 -1.909 2 0 -2.455 3 0 -3.545 目标函数系数范围 : 变量 下限 当前值 上限 ------- -------- -------- -------- x1 7.636 12 无上限 x2 8.182 12 无上限 x3 9.273 12 无上限 x4 8.727 12 无上限 x5 9.818 12 无上限 x6 10.909 12 无上限 x7 9.273 12 无上限 x8 10.364 12 无上限 x9 11.455 12 无上限 x10 9.818 12 无上限 x11 10.909 12 无上限 x12 9 12 12.667 x13 15.273 18 无上限 x14 15.818 18 无上限 x15 16.909 18 无上限 x16 16.364 18 无上限 x17 17.455 18 无上限 x18 16.909 18 无上限 x19 14 18 18.4 x20 17.455 18 无上限 x21 16 18 18.75 常数项数范围 : 约束 下限 当前值 上限 ------- -------- -------- -------- 1 9.6 50 80 2 30 36 103.333 3 7.474 20 26 但是：因为Xi为跑路线i的车的数量，所以Xi应该是整数。因此该问题应该是纯整数规划问题。 用工具计算该纯整数规划问题，可得结果： 目标函数值＝ 264.0000 变量 值 相差值 X1 0.000000 12.000000 X2 0.000000 12.000000 X3 0.000000 12.000000 X4 0.000000 12.000000 X5 0.000000 12.000000 X6 0.000000 12.000000 X7 0.000000 12.000000 X8 0.000000 12.000000 X9 4.000000 12.000000 X10 0.000000 12.000000 X11 0.000000 12.000000 X12 3.000000 12.000000 X13 0.000000 18.000000 X14 0.000000 18.000000 X15 0.000000 18.000000 X16 0.000000 18.000000 X17 0.000000 18.000000 X18 0.000000 18.000000 X19 8.000000 18.000000 X20 0.000000 18.000000 X21 2.000000 18.000000 约束 松弛/剩余变量 对偶价格 1 0.000000 0.000000 2 0.000000 0.000000 3 2.000000 0.000000