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

《关于运输问题与指派问题的建模及其求解.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学试卷2011级营升本2班第2组关于运输问题与指派问题的建模及其求解考生名单：石琦、程培培、曾凯、桑佳丽、王菁、薛苗苗、郝园、付长宇、孙丽媛、杜晓宇问题：某公司决定使用三个有生产余力的工厂进行四种新产品的生产。下面表中给出了每种产品在不同工厂中的单位成本，以及各工厂每天生产的每种产品的数量，每种产品每天的需求量。每家工厂都可以制造这些产品，除了工厂2不能生产产品3以外。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。产品生产的有关数据单位成本（元）生产能力产品1产品2产品3产品4工厂14127282478工厂24029－2370工厂

2、33830272240需求量25353040（1）如果允许产品的生产分解，请建模并求解。（2）如果不允许产品的生产分解，请建模并求解。分析：（1）如果允许产品的生产分解，可以将生产产品问题看作运输问题来求解。三个工厂1、2、3的总产量为78+70+40=188；四种产品1、2、3、4的总需求量为：25+35+30+40=115.由于总产量大于总需求量，所以该问题是一个供大于求的运输问题。①决策变量运筹学试卷2011级营升本2班第2组设xij为工厂i生产产品j的数量（i=1,2,3;j=1,2,3,4）。①目标函数本问题的目标函数是使得总成本最小

3、。即Minz=41x11+27x12+28x13+24x14+40x21+29x22+23x24+38x31+30x32+27x33+22x34③约束条件根据上表可以写出此问题的约束条件ⅰ各厂产量（生产能力）限制工厂1：x11+x12+x13+x14≤78工厂2：x21+x22+x23+x24≤70工厂3：x31+x32+x33+x34≤40ⅱ各种产品需求量的约束产品1：x11+x21+x31=25产品2：x12+x22+x32=35产品3：x13+x23+x33=30产品4：x14+x24+x34=40ⅲ由于工厂2不能生产产品3，所以x23=

4、0ⅳ非负：xij≥0；（i=1,2,3;j=1,2,3,4）。所以该供大于求的运输问题的线性规划模型如下：Minz=41x11+27x12+28x13+24x14+40x21+29x22+23x24+38x31+30x32+27x33+22x34s.t.x11+x12+x13+x14≤78x21+x22+x23+x24≤70x31+x32+x33+x34≤40x11+x21+x31=25x12+x22+x32=35x13+x23+x33=30x14+x24+x34=40x23=0xij≥0；（i=1,2,3;j=1,2,3,4）运筹学试卷201

5、1级营升本2班第2组（2）如果不允许产品的生产分解，可以将该问题视为指派工厂生产产品问题，工厂可以看作指派问题中的人，产品则可以看作需要完成的工作（任务）。由于有四种产品和三个工厂，所以就有两个工厂各只能生产一种新产品，第三个工厂生产两种新产品。只有工厂1和工厂2有生产两种产品的能力。这里涉及如何把运输问题转换为指派问题，关键所在是数据转换。l单位指派成本：原来的单位成本转换成整批成本（=单位成本×需求量），即单位指派成本为每个工厂生产每种产品的成本。l供应量和需求量的转换问题：三个工厂生产四种产品，但一种产品只能在一个工厂生产，根据生产能力，

6、工厂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）。②目标函数本问题的目标函数是使得总成本最小。即Minz=41×25x11+27×35x12+28×30x13+24×40x14+40×25x21+29×35x22+23×40x24+38×25x31+30×35x32+27×30x33+22×40x34③约束条件ⅰ由上面分

7、析表明工厂1和工厂2最多只能生产两种产品，工厂3只能生产一种产品。即工厂1：x11+x12+x13+x14≤2工厂2：x21+x22+x23+x24≤2工厂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、x

8、34中只有一个发生为1，其余为0）运筹学试卷2011级营升本2班第2组ⅲ由于工厂2不能生产产品3，所以x23=0ⅳ非负：xij≥0；（i=1,2,3;