關于運輸問題與指派問題的建模及其求解.docx

《關于運輸問題與指派問題的建模及其求解.docx》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、運籌學試卷2011級營升本2班第2組關于運輸問題與指派問題的建模及其求解考生名單：石琦、程培培、曾凱、桑佳麗、王菁、薛苗苗、郝園、付長宇、孫麗媛、杜曉宇問題：某公司決定使用三個有生產(chǎn)余力的工廠進行四種新產(chǎn)品的生產(chǎn)。下面表中給出了每種產(chǎn)品在不同工廠中的單位成本，以及各工廠每天生產(chǎn)的每種產(chǎn)品的數(shù)量，每種產(chǎn)品每天的需求量。每家工廠都可以制造這些產(chǎn)品，除了工廠2不能生產(chǎn)產(chǎn)品3以外?，F(xiàn)在需要決定的是在哪個工廠生產(chǎn)哪種產(chǎn)品，可使總成本最小。產(chǎn)品生產(chǎn)的有關數(shù)據(jù)單位成本（元）生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠14127282478工廠24029－2370工廠

2、33830272240需求量25353040（1）如果允許產(chǎn)品的生產(chǎn)分解，請建模并求解。（2）如果不允許產(chǎn)品的生產(chǎn)分解，請建模并求解。分析：（1）如果允許產(chǎn)品的生產(chǎn)分解，可以將生產(chǎn)產(chǎn)品問題看作運輸問題來求解。三個工廠1、2、3的總產(chǎn)量為78+70+40=188；四種產(chǎn)品1、2、3、4的總需求量為：25+35+30+40=115.由于總產(chǎn)量大于總需求量，所以該問題是一個供大于求的運輸問題。①決策變量運籌學試卷2011級營升本2班第2組設xij為工廠i生產(chǎn)產(chǎn)品j的數(shù)量（i=1,2,3;j=1,2,3,4）。①目標函數(shù)本問題的目標函數(shù)是使得總成本最小

3、。即Minz=41x11+27x12+28x13+24x14+40x21+29x22+23x24+38x31+30x32+27x33+22x34③約束條件根據(jù)上表可以寫出此問題的約束條件ⅰ各廠產(chǎn)量（生產(chǎn)能力）限制工廠1：x11+x12+x13+x14≤78工廠2：x21+x22+x23+x24≤70工廠3：x31+x32+x33+x34≤40ⅱ各種產(chǎn)品需求量的約束產(chǎn)品1：x11+x21+x31=25產(chǎn)品2：x12+x22+x32=35產(chǎn)品3：x13+x23+x33=30產(chǎn)品4：x14+x24+x34=40ⅲ由于工廠2不能生產(chǎn)產(chǎn)品3，所以x23=

4、0ⅳ非負：xij≥0；（i=1,2,3;j=1,2,3,4）。所以該供大于求的運輸問題的線性規(guī)劃模型如下：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）如果不允許產(chǎn)品的生產(chǎn)分解，可以將該問題視為指派工廠生產(chǎn)產(chǎn)品問題，工廠可以看作指派問題中的人，產(chǎn)品則可以看作需要完成的工作（任務）。由于有四種產(chǎn)品和三個工廠，所以就有兩個工廠各只能生產(chǎn)一種新產(chǎn)品，第三個工廠生產(chǎn)兩種新產(chǎn)品。只有工廠1和工廠2有生產(chǎn)兩種產(chǎn)品的能力。這里涉及如何把運輸問題轉換為指派問題，關鍵所在是數(shù)據(jù)轉換。l單位指派成本：原來的單位成本轉換成整批成本（=單位成本×需求量），即單位指派成本為每個工廠生產(chǎn)每種產(chǎn)品的成本。l供應量和需求量的轉換問題：三個工廠生產(chǎn)四種產(chǎn)品，但一種產(chǎn)品只能在一個工廠生產(chǎn)，根據(jù)生產(chǎn)能力，

6、工廠3只能生產(chǎn)一種產(chǎn)品（供應量為1），而工廠1和工廠2可以生產(chǎn)兩種產(chǎn)品（供應量為2），而產(chǎn)品的需求量為1。還有“總供應（2+2+1=5）>總需求（1+1+1+1=4）”，為人多事少的指派問題。①決策變量設xij為指派工廠i生產(chǎn)產(chǎn)品j的數(shù)量（i=1,2,3;j=1,2,3,4）。②目標函數(shù)本問題的目標函數(shù)是使得總成本最小。即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最多只能生產(chǎn)兩種產(chǎn)品，工廠3只能生產(chǎn)一種產(chǎn)品。即工廠1：x11+x12+x13+x14≤2工廠2：x21+x22+x23+x24≤2工廠3：x31+x32+x33+x34=1ⅱ由于一種產(chǎn)品只能由一個工廠生產(chǎn)，所以產(chǎn)品1：x11+x21+x31=1（x11、x21、x31中只有一個發(fā)生為1，其余為0）產(chǎn)品2：x12+x22+x32=1（x12、x22、x32中只有一個發(fā)生為1，其余為0）產(chǎn)品3：x13+x23+x33=1（x13、x23、x33中只有一個發(fā)生為1，其余為0）產(chǎn)品4：x14+x24+x34=1（x14、x24、x

8、34中只有一個發(fā)生為1，其余為0）運籌學試卷2011級營升本2班第2組ⅲ由于工廠2不能生產(chǎn)產(chǎn)品3，所以x23=0ⅳ非負：xij≥0；（i=1,2,3;