关于运输问题与指派问题的建模及其求解.docx

关于运输问题与指派问题的建模及其求解考生名单：石琦、程培培、曾凯、桑佳丽、王菁、 薛苗苗、郝园、付长宇、孙丽媛、杜晓宇问题：某公司决定使用三个有生产余力的工厂进行四种新产品的生产。下面表中给出了每种产品在不同工厂中的单位成本，以及各工厂每天生产的每种产品的数量，每种产品每天的需求量。每家工厂都可以制造这些产品，除了工厂2不能生产产品3以外。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。 产品生产的有关数据单位成本（元）生产能力产品1产品2产品3产品4工厂240292370工厂33830272240需求量25353040 （1）如果允许产品的生产分解，请建模并求解。（2）如果不允许产品的生产分解，请建模并求解。分析：（1）如果允许产品的生产分解，可以将生产产品问题看作运输问题来求解。三个工厂1、2、3的总产量为78+70+40=188；四种产品1、2、3、4的总需求量为：25+35+30+40=115.由于总产量大于总需求量，所以该问题是一个供大于求的运输问题。 决策变量设xij为工厂i生产产品j的数量（i=1,2,3; j=1,2,3,4）。 目标函数本问题的目标函数是使得总成本最小。即Min z=41x11+27x12+28x13+24x14+ 40x21+29x22 +23x24+ 38x31+30x32+27x33+22x34 约束条件根据上表可以写出此问题的约束条件各厂产量（生产能力）限制工厂1：x11+x12+x13+x1478工厂2：x21+x22+x23+x2470工厂3：x31+x32+x33+x3440各种产品需求量的约束产品1：x11+x21+x31=25产品2：x12+x22+x32=35产品3：x13+x23+x33=30产品4：x14+x24+x34=40由于工厂2不能生产产品3，所以x23=0非负：xij0；（i=1,2,3; j=1,2,3,4）。所以该供大于求的运输问题的线性规划模型如下：Min z=41x11+27x12+28x13+24x14+ 40x21+29x22 +23x24+38x31+30x32+27x33+22x34s.t.x11+x12+x13+x1478 x21+x22+x23+x2470 x31+x32+x33+x3440 x11+x21+x31=25 x12+x22+x32=35 x13+x23+x33=30 x14+x24+x34=40 x23=0 xij0；（i=1,2,3; j=1,2,3,4）（2）如果不允许产品的生产分解，可以将该问题视为指派工厂生产产品问题，工厂可以看作指派问题中的人，产品则可以看作需要完成的工作（任务）。由于有四种产品和三个工厂，所以就有两个工厂各只能生产一种新产品，第三个工厂生产两种新产品。只有工厂1和工厂2有生产两种产品的能力。这里涉及如何把运输问题转换为指派问题，关键所在是数据转换。l 单位指派成本：原来的单位成本转换成整批成本（=单位成本需求量），即单位指派成本为每个工厂生产每种产品的成本。l 供应量和需求量的转换问题：三个工厂生产四种产品，但一种产品只能在一个工厂生产，根据生产能力，工厂3只能生产一种产品（供应量为1），而工厂1和工厂2可以生产两种产品（供应量为2），而产品的需求量为1。还有“总供应（2+2+1=5）总需求（1+1+1+1=4）”，为人多事少的指派问题。 决策变量设xij为指派工厂i生产产品j的数量（i=1,2,3; j=1,2,3,4）。 目标函数本问题的目标函数是使得总成本最小。即Min z=4125x11+2735x12+2830x13+2440x14 +4025x21+2935x22 + 2340x24 +3825x31+3035x32+2730x33+2240x34 约束条件由上面分析表明工厂1和工厂2最多只能生产两种产品，工厂3只能生产一种产品。即工厂1：x11+x12+x13+x142工厂2：x21+x22+x23+x242工厂3：x31+x32+x33+x34=1由于一种产品只能由一个工厂生产，所以产品1：x11+x21+x31=1（x11、x21、x31中只有一个发生为1，其余为0）产品2：x12+x22+x32=1（x12、x22、x32中只有一个发生为1，其余为0）产品3：x13+x23+x33=1（x13、x23、x33中只有一个发生为1，其余为0）产品4：x14+x24+x34=1（x14、x24、x34中只有一个发生为1，其余为0）由于工厂2不能生产产品3，所以x23=0非负：xij0；（i=1,2,3; j=1,2,3,4）。所以该指派问题的线性规划模型如下：Min z=4125x11+2735x12+2830x13+2440x14 +4025x21+2935x22 + 2340x24 +3825x31+3035x32+2730x33+2240x34s.t.x11+x12+x13+x142 x21+x22+x23+x242 x31+x32+x33+x34=1 x11+x21+x31=1 x12+x22+x32=1 x13+x23+x33=1 x14+x24+x34=1 x23=0 xij0；（i=1,2,3; j=1,2,3,4）求解：目标单元格I13总成本14=SUMPRODUCT(C4:F6,C9:F11)数据单元格G8实际产量9=SUM(C9:F9)10=SUM(C10:F10)11=SUM(C11:F11)BCDEF12实际销量=SUM(C9:C11)=SUM(D9:D11)=SUM(E9:E11)=SUM(F9:F11)目标单元格I20总成本21=SUMPRODUCT(C11:F13,C16:F18)数据单元格10日成品产品1产品2产品3产品411工厂1=C4*$C$8=D4*$D$8=E4*$E$8=F4*$F$812工厂2=C5*$C$8=D5*$D$8-=F5*$F$813工厂3=C6*$C$8=D6*$D$8