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

运筹学试卷2011级营升本2班第2组关于运输问题与指派问题的建模及其求解考生名单：石琦、程培培、曾凯、桑佳丽、王菁、薛苗苗、郝园、付长宇、孙丽媛、杜晓宇问题：某公司决定使用三个有生产余力的工厂进行四种新产品的生产。下面表中给出了每种产品在不同工厂中的单位成本，以及各工厂每天生产的每种产品的数量，每种产品每天的需求量。每家工厂都可以制造这些产品，除了工厂2不能生产产品3以外。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。产品生产的有关数据单位成本（元）生产能力产品1产品2产品3产品4工厂14127282478工厂24029－2370工厂33830272240需求量25353040（1）如果允许产品的生产分解，请建模并求解。（2）如果不允许产品的生产分解，请建模并求解。分析：（1）如果允许产品的生产分解，可以将生产产品问题看作运输问题来求解。三个工厂1、2、3的总产量为78+70+40=188；四种产品1、2、3、4的总需求量为：25+35+30+40=115.由于总产量大于总需求量，所以该问题是一个供大于求的运输问题。①决策变量运筹学试卷2011级营升本2班第2组设𝑥𝑖𝑗为工厂𝑖生产产品𝑗的数量（𝑖=1,2,3;𝑗=1,2,3,4）。②目标函数本问题的目标函数是使得总成本最小。即Minz=41𝑥11+27𝑥12+28𝑥13+24𝑥14+40𝑥21+29𝑥22+23𝑥24+38𝑥31+30𝑥32+27𝑥33+22𝑥34③约束条件根据上表可以写出此问题的约束条件ⅰ各厂产量（生产能力）限制工厂1：𝑥11+𝑥12+𝑥13+𝑥14≤78工厂2：𝑥21+𝑥22+𝑥23+𝑥24≤70工厂3：𝑥31+𝑥32+𝑥33+𝑥34≤40ⅱ各种产品需求量的约束产品1：𝑥11+𝑥21+𝑥31=25产品2：𝑥12+𝑥22+𝑥32=35产品3：𝑥13+𝑥23+𝑥33=30产品4：𝑥14+𝑥24+𝑥34=40ⅲ由于工厂2不能生产产品3，所以𝑥23=0ⅳ非负：𝑥𝑖𝑗≥0；（𝑖=1,2,3;𝑗=1,2,3,4）。所以该供大于求的运输问题的线性规划模型如下：Minz=41𝑥11+27𝑥12+28𝑥13+24𝑥14+40𝑥21+29𝑥22+23𝑥24+38𝑥31+30𝑥32+27𝑥33+22𝑥34s.t.{𝑥11+𝑥12+𝑥13+𝑥14≤78𝑥21+𝑥22+𝑥23+𝑥24≤70𝑥31+𝑥32+𝑥33+𝑥34≤40𝑥11+𝑥21+𝑥31=25𝑥12+𝑥22+𝑥32=35𝑥13+𝑥23+𝑥33=30𝑥14+𝑥24+𝑥34=40𝑥23=0𝑥𝑖𝑗≥0；（𝑖=1,2,3;𝑗=1,2,3,4）运筹学试卷2011级营升本2班第2组（2）如果不允许产品的生产分解，可以将该问题视为指派工厂生产产品问题，工厂可以看作指派问题中的人，产品则可以看作需要完成的工作（任务）。由于有四种产品和三个工厂，所以就有两个工厂各只能生产一种新产品，第三个工厂生产两种新产品。只有工厂1和工厂2有生产两种产品的能力。这里涉及如何把运输问题转换为指派问题，关键所在是数据转换。单位指派成本：原来的单位成本转换成整批成本（=单位成本×需求量），即单位指派成本为每个工厂生产每种产品的成本。供应量和需求量的转换问题：三个工厂生产四种产品，但一种产品只能在一个工厂生产，根据生产能力，工厂3只能生产一种产品（供应量为1），而工厂1和工厂2可以生产两种产品（供应量为2），而产品的需求量为1。还有“总供应（2+2+1=5）总需求（1+1+1+1=4）”，为人多事少的指派问题。①决策变量设𝑥𝑖𝑗为指派工厂𝑖生产产品𝑗的数量（𝑖=1,2,3;𝑗=1,2,3,4）。②目标函数本问题的目标函数是使得总成本最小。即Minz=41×25𝑥11+27×35𝑥12+28×30𝑥13+24×40𝑥14+40×25𝑥21+29×35𝑥22+23×40𝑥24+38×25𝑥31+30×35𝑥32+27×30𝑥33+22×40𝑥34③约束条件ⅰ由上面分析表明工厂1和工厂2最多只能生产两种产品，工厂3只能生产一种产品。即工厂1：𝑥11+𝑥12+𝑥13+𝑥14≤2工厂2：𝑥21+𝑥22+𝑥23+𝑥24≤2工厂3：𝑥31+𝑥32+𝑥33+𝑥34=1ⅱ由于一种产品只能由一个工厂生产，所以产品1：𝑥11+𝑥21+𝑥31=1（𝑥11、𝑥21、𝑥31中只有一个发生为1，其余为0）产品2：𝑥12+𝑥22+𝑥32=1（𝑥12、𝑥22、𝑥32中只有一个发生为1，其余为0）产品3：𝑥13+𝑥23+𝑥33=1（𝑥13、𝑥23、𝑥33中只有一个发生为1，其余为0）运筹学试卷2011级营升本2班第2组产品4：𝑥14+𝑥24+𝑥34=1（𝑥14、𝑥24、𝑥34中只有一个发生为1，其余为0）ⅲ由于工厂2不能生产产品3，所以𝑥23=0ⅳ非负：𝑥𝑖𝑗≥0；（𝑖=1,2,3;𝑗=1,2,3,4）。所以该指派问题的线性规划模型如下：Minz=41×25𝑥11+27×35𝑥12+28×30𝑥13+24×40𝑥14+40×25𝑥21+29×35𝑥22+23×40𝑥24+38×25𝑥31+30×35𝑥32+27×30𝑥33+22×40𝑥34s.t.{𝑥11+𝑥12+𝑥13+𝑥14≤2𝑥21+𝑥22+𝑥23+𝑥24≤2𝑥31+𝑥32+𝑥33+𝑥34=1𝑥11+𝑥21+𝑥31=1𝑥12+𝑥22+𝑥32=1𝑥13+𝑥23+𝑥33=1𝑥14+𝑥24+𝑥34=1𝑥23=0𝑥𝑖𝑗≥0；（𝑖=1,2,3;𝑗=1,2,3,4）求解：目标单元格I13总成本14=SUMPRODUCT(C4:F6,C9:F11)运筹学试卷2011级营升本2班第2组数据单元格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)运筹学试卷2011级营升本2班第2组目标单元格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=E6*$E$8=F6*$F$8G15实际指派16=SUM(C16:F16)17=SUM(C17:F17)18=SUM(C18:F18)BCDEF19实际分配=SUM(C16:C18)=SUM(D16:D18)=SUM(E16:E18)=SUM(F16:F18)运筹学试卷2011级营升本2班第2组