上海交通大學(xué)管理科學(xué)運(yùn)籌學(xué)教學(xué)案例

上海交通大學(xué)管理科學(xué)運(yùn)籌學(xué)教學(xué)案例第1頁(yè)/共39頁(yè)某企業(yè)計(jì)劃用三種原材料生產(chǎn)五種產(chǎn)品，其有關(guān)資料如下：

第2頁(yè)/共39頁(yè)

原材料可利用數(shù)量（斤）每萬(wàn)件產(chǎn)品所用材料數(shù)（斤）

ABCDE甲1012101乙2410132丙2112222每萬(wàn)件產(chǎn)品利潤(rùn)（萬(wàn)元）820102021

第3頁(yè)/共39頁(yè)

（1）

如何確定最滿意的生產(chǎn)計(jì)劃（2）

如果A和D兩種產(chǎn)品的目標(biāo)利潤(rùn)發(fā)生變化，在什么范圍內(nèi)，生產(chǎn)計(jì)劃不需要改變。（3）

如果甲和乙兩種原材料的可利用數(shù)量發(fā)生變化，在什么范圍內(nèi)，生產(chǎn)計(jì)劃不需要改變。如果超過(guò)這個(gè)范圍，怎樣調(diào)整生產(chǎn)計(jì)劃。（4）

如果引進(jìn)新產(chǎn)品Y，已知生產(chǎn)新產(chǎn)品Y一萬(wàn)件要使用原材料甲、乙、丙分別為1、2、1（斤），而每單位新產(chǎn)品Y可得利潤(rùn)10萬(wàn)元。問(wèn)新產(chǎn)品Y是否有利于投產(chǎn)？它的利潤(rùn)多少時(shí)才有利于投產(chǎn)。（5）

如果又新增加煤耗不許超過(guò)20噸的限制，而生產(chǎn)每萬(wàn)件A、B、C、D、E產(chǎn)品，分別需用煤3、2、1、2、1（噸），問(wèn)是否需要改變?cè)瓉?lái)的最優(yōu)生產(chǎn)計(jì)劃。第4頁(yè)/共39頁(yè)

解：（1）設(shè)生產(chǎn)這五種產(chǎn)品的數(shù)量分別為x1、x2、x3、x4、x5萬(wàn)件，所以這個(gè)問(wèn)題的數(shù)學(xué)模型是：求一組變量xi（i=1、2，…5）的值，使它滿足下列約束條件：

第5頁(yè)/共39頁(yè)并使目標(biāo)函數(shù)取到最大值第6頁(yè)/共39頁(yè)引進(jìn)松馳變量把問(wèn)題化為標(biāo)準(zhǔn)形式求滿足

第7頁(yè)/共39頁(yè)利用單純形法解此問(wèn)題顯然是一個(gè)可行基，對(duì)應(yīng)于基B1的單純形表為第8頁(yè)/共39頁(yè)

x1x2x3x4x5x6x7x8

820102021000x61012101100x72410132010x82112222001第9頁(yè)/共39頁(yè)表中有正檢驗(yàn)數(shù)，進(jìn)行換基迭代

x1x2x3x4x5x6x7x8-210-13-22-11200-2100x51012101100x74-1-4-130-210x81-1-2020-201

第10頁(yè)/共39頁(yè)表中仍有正檢驗(yàn)數(shù)，繼續(xù)進(jìn)行換基迭代

x1x2x3x4x5x6x7x8-220-3-2-1100-10-10x51012101100x75/21/2-1-10011-3/2x41/2-1/2-1010-101/2

第11頁(yè)/共39頁(yè)表中已沒(méi)有正檢驗(yàn)數(shù)，所以B=（p5p7p4）為最優(yōu)基，它對(duì)應(yīng)的基礎(chǔ)最優(yōu)解為x1=x2=x3=x6=x8=0x4=1/2x5=10x7=5/2目標(biāo)函數(shù)最小值為=-220，故原問(wèn)題的最優(yōu)解為x1=x2=x3=0x4=1/2x5=10目標(biāo)函數(shù)最大值為220即計(jì)劃生產(chǎn)五種產(chǎn)品分別為0件、0件、0件100000件5000件、才能獲最大利潤(rùn)為220萬(wàn)元。

第12頁(yè)/共39頁(yè)（2）因?yàn)锽=（p5p7p4）cB=(21020)c=(820102021)假設(shè)目標(biāo)函數(shù)中c1=8c4=20有波動(dòng)，令，當(dāng)C1、C4有波動(dòng)時(shí)，如果仍要上面的解為最優(yōu)，那么根據(jù)最優(yōu)判別準(zhǔn)則，應(yīng)有所以應(yīng)有：第13頁(yè)/共39頁(yè)第14頁(yè)/共39頁(yè)即即第15頁(yè)/共39頁(yè)即當(dāng)時(shí)，即每萬(wàn)件產(chǎn)品A的利潤(rùn)小于、等于11萬(wàn)元時(shí)，原問(wèn)題的解仍是最優(yōu)解：最大利潤(rùn)仍為220萬(wàn)元。假設(shè)目標(biāo)函數(shù)中c4=20有波動(dòng)，令當(dāng)c4波動(dòng)時(shí)，如果仍要上面的解為最優(yōu)，那么根據(jù)最優(yōu)判別準(zhǔn)則應(yīng)有第16頁(yè)/共39頁(yè)第17頁(yè)/共39頁(yè)解第18頁(yè)/共39頁(yè)得也就是每萬(wàn)件產(chǎn)品D的利潤(rùn)在[0，21]內(nèi)變化時(shí)，原問(wèn)題的解仍是最優(yōu)解，最大利潤(rùn)仍為220萬(wàn)元。第19頁(yè)/共39頁(yè)

3因?yàn)榈?0頁(yè)/共39頁(yè)假設(shè)有變動(dòng)所以第21頁(yè)/共39頁(yè)解得所以即當(dāng)時(shí)，原來(lái)的基仍為最優(yōu)基。假設(shè)b1，b2同時(shí)變動(dòng)，,,第22頁(yè)/共39頁(yè)所以第23頁(yè)/共39頁(yè)

即解得第24頁(yè)/共39頁(yè)即當(dāng)，即原材料甲的可利用數(shù)為35/4斤至21/2斤，原材料乙的可利用數(shù)為91/4至49/2斤，其它條件不變，這時(shí)間題的最優(yōu)基仍是原問(wèn)題的最優(yōu)基。第25頁(yè)/共39頁(yè)（3）

對(duì)原模型引進(jìn)一個(gè)新變量x9表示生產(chǎn)x9萬(wàn)件則問(wèn)題變?yōu)椋呵鬂M足

第26頁(yè)/共39頁(yè)

由前面已知是原問(wèn)題的一個(gè)最優(yōu)解。那么是這個(gè)問(wèn)題可行解第27頁(yè)/共39頁(yè)而第28頁(yè)/共39頁(yè)故是最優(yōu)解，即新產(chǎn)品Y不利于投產(chǎn)只有當(dāng)

第29頁(yè)/共39頁(yè)即即所以只有當(dāng)生產(chǎn)新產(chǎn)品Y一萬(wàn)件可得利潤(rùn)超過(guò)11萬(wàn)元時(shí)才有利于投產(chǎn)。第30頁(yè)/共39頁(yè)

（5）

原模型現(xiàn)在必須添加一個(gè)用煤的約束條件添加松馳變量x9

使上式變成：

則在最優(yōu)方案對(duì)應(yīng)的單純形表中添加一個(gè)新行和一個(gè)新列，并把松馳變量x9指定為新行的基變量，如下表第31頁(yè)/共39頁(yè)

x1x2x3x4x5x6x7x8x9-220-3-2-1100-10-100x510121011000x75/21/2-1-10011-3/20x41/2-1/2-1010-101/20x920321210001

第32頁(yè)/共39頁(yè)

x1x2x3x4x5x6x7x8x9-220-3-2-1100-10-100x510121011000x75/21/2-1-10011-3/20x41/2-1/2-1010-101/20x993200010-11第33頁(yè)/共39頁(yè)由此表可知