搜索
整数规划专题-----东方服装集团的童衣配送系统设计【题目】东方服装集团考虑生产一种童衣系列。童衣产品将先运至配送中心，再由配送中心将产品运至分销店。该集团有5家工厂可生产这类童衣，有3家配送中心可以分配童衣产品，有4家分销店可以经营童衣产品。这些工厂和配送中心的下一年度的年固定成本如下表1。表1工厂与配送中心的固定成本单位工厂1工厂2工厂3工厂4工厂5配送中心1配送中心2配送中心3年固定成本（元）3500045000400004200040000400002000060000下一年度工厂的生产能力、工厂到被选的配送中心的单位运价如表2所示。表2各工厂至配送中心的运输成本与生产能力终点起点运输成本（元/箱）生产能力（箱）配送中心1配送中心2配送中心3工厂1工厂2工厂3工厂4工厂580070080050070010005006006006001200700500700500300200300200400从配送中心运至分销店的运输成本和各分销店的需求量如表3所示。表3终点起点运输成本（元/箱）分销店1分销店2分销店3分销店4配送中心1配送中心2配送中心3407080804030906050508060需求量（箱）200300150250假定各配送中心的库存政策为零库存，即配送中心从工厂得到的产品均分配给分销店，不留作库存。集团要设计一种童衣分配系统，在满足需求的前提下，确定使用哪些工厂与配送中心进行童衣的生产与配送，以使得总成本最小。【解题思路】据题意，所要确定的问题是：如何选择生产厂和分配中心，如何确定从各生产厂运至各分配中心的产品数量以及从各分配中心运至分销店的产品数量，才能在满足所要求的条件下使得总成本最小。该问题可以用0-1整数规划解决。对生产厂和分配中心的选择，实际上就是对它们“使用”或“不使用”的决策，这种逻辑关系可以用0-1变量表示。设本问题的决策变量为Xij（i=1,…,5；j=1,2,3），Fi（i=1,…,5）,Yij（i=1,2,3;j=1,2,3,4）,Di（i=1,2,3）。其中Xij表示从生产厂i运至分配中心j的产品数量；Fi为0-1变量，表示使用或不使用第i个生产厂得决策，当变量为1时，表示“使用”，当变量为0时，表示“不使用”；Yij表示从分配中心i运至分销店j的产品数量；Di为0-1变量，表示使用或不使用第i个分配中心的决策，当变量为1时，表示“使用”，当变量为0时，表示“不使用”。本问题的目标函数是总成本最小，这里的总成本包含四个部分：第一部分是从各工厂至分配中心的运输费用，第二部分是从各分配中心至各分销店的运输费用，这两部分费用均与所运输的产品数量有关。将各工厂至各分配中心的运输成本分别乘以相应的运输量，其总和就是从各工厂至各分配中心的运输费。所有工厂至分配中心的运输费用之和就是第一部分成本，即：=800X11+1000X12+1200X13+700X21+500X22+700X23+800X31+600X32+500X33+500X41+600X42+700X43+700X51+600X52+500X53同样地，将各分配中心至各分销店的运输成本分别乘以相应的运输量，其总和就是从各分配中心至各分销店的运输费用，这就是第二部分成本，即：=40Y11+80Y12+90Y13+50Y14+70Y21+40Y22+60Y23+80Y24+80Y31+30Y32+50Y33+60Y34第三部分是所使用的工厂的固定成本，第四部分是所使用的分配中心的固定成本。这两部分费用与所运输的产品数量无关，而仅取决于是否选择了该工厂或该分配中心。所以，工厂固定成本产生的费用=35000F1+45000F2+40000F3+42000F4+40000F5，这就是第三部分成本。同理可得，分配中心固定成本产生的费用=40000D1+20000D2+60000D3，这就是第四部分成本。综上所述，总成本的表达式为：800X11+1000X12+1200X13+700X21+500X22+700X23+800X31+600X32+500X33+500X41+600X42+700X43+700X51+600X52+500X53+40Y11+80Y12+90Y13+50Y14+70Y21+40Y22+60Y23+80Y24+80Y31+30Y32+50Y33+60Y34+35000F1+45000F2+40000F3+42000F4+40000F5+40000D1+20000D2+60000D3依题意可知，五个工厂的总生产能力=300+200+300+200+400=1400（箱/年），分配中心的吞吐能力无限定，分销店的总需求量=200+300+150+250=900（箱/年），可见分销店的产品总需求可以全部满足，而工厂的总生产能力则尚未完全使用、本问题的约束条件有六个。第一个约束是工厂生产能力约束，即各工厂运出的产品数量不得超过其实际生产能力。可得：X11+X12+X13≤300F1X21+X22+X23≤200F2X31+X32+X33≤300F3X41+X42+X43≤200F4X51+X52+X53≤300F5第二个约束为分配中心的“零库存”约束，即分配中心的接收量等于运出量可得：X11+X21+X31+X41=Y11+Y12+Y13+Y14X12+X22+X32+X42=Y21+Y22+Y23+Y24X13+X23+X33+X43=Y31+Y32+Y33+Y34第三个约束为分配中心运出量得约束，即各分配中心的运出量不得超过所有分销店的总需求量（前面已经计算出所有分销店的总需求量为900）可得：Y11+Y12+Y13+Y14≤900D1Y21+Y22+Y23+Y24≤900D2Y31+Y32+Y33+Y34≤900D3第四个约束是满足需求约束，即各分销店的接收量应不小于其需求量。可得：Y11+Y21+Y31≥200Y12+Y22+Y32≥300Y13+Y23+Y33≥150Y14+Y24+Y34≥250第五个约束是0-1约束，即决策变量F1,F2,F3,F4,D1,D2,D3只能取1或0；第六个约束是非负约束。【整数规划模型】由此得到整数规划模型如下：o.b.min800X11+1000X12+1200X13+700X21+500X22+700X23+800X31+600X32+500X33+500X41+600X42+700X43+700X51+600X52+500X53+40Y11+80Y12+90Y13+50Y14+70Y21+40Y22+60Y23+80Y24+80Y31+30Y32+50Y33+60Y34+35000F1+45000F2+40000F3+42000F4+40000F5+40000D1+20000D2+60000D3s.t.X11+X12+X13≤300F1X21+X22+X23≤200F2X31+X32+X33≤300F3X41+X42+X43≤200F4X51+X52+X53≤300F5X11+X21+X31+X41=Y11+Y12+Y13+Y14X12+X22+X32+X42=Y21+Y22+Y23+Y24X13+X23+X33+X43=Y31+Y32+Y33+Y34Y11+Y12+Y13+Y14≤900D1Y21+Y22+Y23+Y24≤900D2Y31+Y32+Y33+Y34≤900D3Y11+Y21+Y31≥200Y12+Y22+Y32≥300Y13+Y23+Y33≥150Y14+Y24+Y34≥250Fi=0或1（i=1,…,5），Di=0或1（i=1,2,3）Xij≥0（i=1,…,5；j=1,2,3）Yij≥0（i=1,2,3;j=1,2,3,4）【Excel求解及计算结果】由于目标函数和约束条件复杂，我们小组采用Excel求解。如下图【结论】从各工厂运至各分配中心的产品产量如下表所示工厂分配中心1分配中心2分配中心3工厂130000工厂2000工厂300300工厂4000工厂500300从各分配中心运至各分销店的产品产量如下表所示分配中心分销店1分销店2分销店3分销店4分配中心120000100分配中心20000分配中心30300150150在最优解中，0-1决策变量F1=1，F2=0，F3=1，F4=0，F5=1，D1=1，D2=0，D3=1，说明使用第一、第三、第五个工厂，不使用第二、第四个工厂；使用第一、第三个分配中心，不使用第二个分配中心。从个工厂至各分配中心的产品产量与从各分配中心运至各分销店的产品产量分别如上表所示。这时，总成本最小。为703500元。