蘭州大學(xué)運(yùn)籌學(xué)——線性規(guī)劃問題的計(jì)算機(jī)求解課后習(xí)題題解.doc
《蘭州大學(xué)運(yùn)籌學(xué)——線性規(guī)劃問題的計(jì)算機(jī)求解課后習(xí)題題解.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《蘭州大學(xué)運(yùn)籌學(xué)——線性規(guī)劃問題的計(jì)算機(jī)求解課后習(xí)題題解.doc(8頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
第四章 線性規(guī)劃問題的計(jì)算機(jī)求解 4.1 有以下線性規(guī)劃數(shù)學(xué)問題: max Z=2xl+3 x2 S.T. xl+ x2≤10 2xl+ x2≥4 xl+3 x2≤24 2xl+ x2≤16 xl 、 x2≥0 1、 用EXCEL線性規(guī)劃求解模板求解該數(shù)學(xué)模型。 2、 本問題的最優(yōu)解是什么?此時(shí)最大目標(biāo)函數(shù)值是多少? 3、 四個(gè)約束條件中,哪些約束條件起到了作用?各約束條件的剩余量或松弛量及對(duì)偶價(jià)格是多少? 4、 目標(biāo)函數(shù)中各變量系數(shù)在什么范圍內(nèi)變化時(shí),最優(yōu)解不變? 5、 確定各給定條件中的常數(shù)項(xiàng)的上限和下限。 解: 1、 2、最優(yōu)解:(3,7),最優(yōu)值:27 可變單元格 終 遞減 目標(biāo)式 允許的 允許的 單元格 名字 值 成本 系數(shù) 增量 減量 $C$34 x1 3 0 2 1 1 $D$34 x2 7 0 3 3 1 約束 終 陰影 約束 允許的 允許的 單元格 名字 值 價(jià)格 限制值 增量 減量 $R$11 實(shí)際值 10 1.5 10 1.2 2 $R$12 實(shí)際值 13 0 4 9 1E+30 $R$13 實(shí)際值 24 0.5 24 6 6 $R$14 實(shí)際值 13 0 16 1E+30 3 3、 對(duì)于求最大化的問題,對(duì)偶價(jià)格=陰影價(jià)格 松弛量/剩余量 對(duì)偶價(jià)格 xl+ x2≤10 0 1.5 2xl+ x2≥4 9 0 xl+3 x2≤24 0 0.5 2xl+ x2≤16 13 0 因第一、第三個(gè)約束條件的松弛量/剩余量為0 ,所以這兩個(gè)約束條件起到了約束作用。 4、目標(biāo)函數(shù)中各變量系數(shù) 1≤ C1≤3 2≤ C1≤6 5、常數(shù)項(xiàng) 8≤ b1≤9.2 無限≤ b2≤13 18≤ b3≤30 13≤ b4≤無限 4.2 有以下線性規(guī)劃數(shù)學(xué)問題: min f=8xl+3 x2 S.T. 500xl+100 x2≤1200000 5xl+4 x2≥60000 100xl≥300000 xl 、 x2≥0 1、用EXCEL線性規(guī)劃求解模板求解該數(shù)學(xué)模型。 2、本問題的最優(yōu)解是什么?此時(shí)最大目標(biāo)函數(shù)值是多少? 3、各約束條件的剩余量或松弛量及對(duì)偶價(jià)格是多少?分別解釋其含義。 4、目標(biāo)函數(shù)中各變量系數(shù)在什么范圍內(nèi)變化時(shí),最優(yōu)解不變? 5、確定各給定條件中的常數(shù)項(xiàng)的上限和下限。 解: 本問題無解。 4.3 有以下線性規(guī)劃數(shù)學(xué)問題: max Z=xl+2 x2+3 x3- x4 S.T. xl+2 x2+3 x3≤15 2xl+ x2+5 x3≤20 xl+2 x2+ x3+ x4≤10 xl 、 x2、 x3、 x4≥0 1、用EXCEL線性規(guī)劃求解模板求解該數(shù)學(xué)模型。 2、本問題的最優(yōu)解是什么?此時(shí)最大目標(biāo)函數(shù)值是多少? 3、分別解釋“遞減成本”欄中各數(shù)據(jù)的含義。 4、各約束條件的剩余量或松弛量及對(duì)偶價(jià)格是多少?分別解釋其含義。 5、C2再增加2,同時(shí)C3再減少2,其最優(yōu)解是否會(huì)變化?為什么? 6、b1再增加3,同時(shí)b2再減少3,其對(duì)偶價(jià)格是否會(huì)變化?為什么? 解: 1、 2、最優(yōu)解:(0,2.143,3.571,0),最優(yōu)值:15 (本問題可能是多解問題) 3、 可變單元格 終 遞減 目標(biāo)式 允許的 允許的 單元格 名字 值 成本 系數(shù) 增量 減量 $C$34 x1 0 0 1 0 1E+30 $D$34 x2 2.142857143 0 2 0 1.4 $E$34 x3 3.571428571 0 3 7 0 $F$34 x4 0 -1 -1 1 1E+30 約束 終 陰影 約束 允許的 允許的 單元格 名字 值 價(jià)格 限制值 增量 減量 $R$11 實(shí)際值 15 1 15 1.666666667 3 $R$12 實(shí)際值 20 0 20 5 3.75 $R$13 實(shí)際值 7.857142857 0 10 1E+30 2.142857143 遞減成本欄中的數(shù)據(jù)的絕對(duì)值,分別表示四個(gè)變量在目標(biāo)函數(shù)中系數(shù),當(dāng)最優(yōu)解中不為0的變量,其遞減成本必為0,最優(yōu)解中變量值為0時(shí),要使其解不為0時(shí)要使相應(yīng)系數(shù)增加遞減成本的絕對(duì)值,其解不為0。本問題中,x1為0 ,遞減成本的絕對(duì)值也為0 ,說明c1=1就能使x1<>0; x4為0,遞減成本的絕對(duì)值為1,說明c4=0才能使x4<>0。 4、 松弛量 對(duì)偶價(jià)格 xl+2 x2+3 x3≤15 0 1 2xl+ x2+5 x3≤20 0 0 xl+2 x2+ x3+ x4≤10 2.143 0 5、上表中 0.6≤C2≤2 3≤C3≤10 可見C2沒有增加允許,C3沒有減少允許,所以C2再增加2,同時(shí)C3再減少2,其最優(yōu)解必將發(fā)生變化。 6、b1的允許增量是1.667,所以b1再增加3,同時(shí)b2再減少3,其對(duì)偶價(jià)格必將發(fā)生變化。 4.4 有以下線性規(guī)劃數(shù)學(xué)問題: min f=-2xl- x2+3 x3-4 x4 S.T. xl+2 x2+4 x3- x4≤6 2xl+3 x2- x3+ x4≤18 xl+ x2+ x3≤4 xl 、 x2、 x3、 x4≥0 1、用EXCEL線性規(guī)劃求解模板求解該數(shù)學(xué)模型。 2、本問題的最優(yōu)解是什么?此時(shí)最大目標(biāo)函數(shù)值是多少? 3、分別解釋“遞減成本”欄中各數(shù)據(jù)的含義。 4、各約束條件的剩余量或松弛量及對(duì)偶價(jià)格是多少?分別解釋其含義。 5、C1再減少5,同時(shí)C3再增加5,其最優(yōu)解是否會(huì)變化?為什么? 6、b1再減少5,同時(shí)b3再增加5,其對(duì)偶價(jià)格是否會(huì)變化?為什么? 解: 1、 2、最優(yōu)解:(0,0,4,22),最優(yōu)值:-76。 3、 終 遞減 目標(biāo)式 允許的 允許的 單元格 名字 值 成本 系數(shù) 增量 減量 $C$34 x1 0 7 -2 1E+30 7 $D$34 x2 0 12 -1 1E+30 12 $E$34 x3 4 0 3 1 1E+30 $F$34 x4 22 0 -4 1 1E+30 終 陰影 約束 允許的 允許的 單元格 名字 值 價(jià)格 限制值 增量 減量 $R$11 實(shí)際值 -6 0 6 1E+30 12 $R$12 實(shí)際值 18 -4 18 1E+30 12 $R$13 實(shí)際值 4 -1 4 4 4 遞減成本欄中的數(shù)據(jù)的絕對(duì)值,分別表示四個(gè)變量在目標(biāo)函數(shù)中系數(shù),當(dāng)最優(yōu)解中不為0的變量,其遞減成本必為0,最優(yōu)解中變量值為0時(shí),要使其解不為0時(shí)要使相應(yīng)系數(shù)增加遞減成本的絕對(duì)值,其解不為0。本問題中,x1為0 ,遞減成本的絕對(duì)值為7 ,說明c1由現(xiàn)在的-2變?yōu)?1時(shí),就能使x1<>0; x2為0,遞減成本的絕對(duì)值為12,說明c2=0由現(xiàn)在的-1變?yōu)?1時(shí)才能使x2<>0。 4、 松弛量 對(duì)偶價(jià)格 xl+2 x2+4 x3- x4≤6 12 0 2xl+3 x2- x3+ x4≤18 0 4 xl+ x2+ x3≤4 0 1 5、上表中 -9≤C1≤無限 無限≤C3≤4 可見C3只能允許增加1,當(dāng)增加5時(shí)其最優(yōu)解必將發(fā)生改變。 6、b3只能增加4,所以當(dāng)b3只能增加5時(shí),其對(duì)偶價(jià)格必將發(fā)生改變。 4.5 某公司根據(jù)訂單安排生產(chǎn)。已知半年內(nèi)對(duì)某產(chǎn)品的需求量、單位生產(chǎn)費(fèi)用和單位存儲(chǔ)費(fèi)用如下表: 月份 1 2 3 4 5 6 需求量(件) 50 40 50 45 55 30 單位生產(chǎn)費(fèi)用(元/件) 825 775 850 850 775 825 單位存儲(chǔ)費(fèi)用(元/件) 40 30 35 20 40 40 又知公司每月的生產(chǎn)能力為100件,每月倉庫的容量為50件。問:如何確定產(chǎn)品未來半年內(nèi)每月最佳生產(chǎn)量和存儲(chǔ)量才能使總的費(fèi)用為最少? 若設(shè)未來6個(gè)月每月的生產(chǎn)量分別為 xl、 x2、 x3、 x4、 x5、 x6 每月的存儲(chǔ)量分別為 x7、 x8、 x9、 x10、 x11、 x12 可得線性規(guī)劃數(shù)學(xué)模型: min f=825xl+775 x2+850 x3+850 x4+775 x5+825 x6+40x7+30 x8+35 x9+20 x10+40 x11+40 x12 S.T. xl- x7=50 x2+ x7- x8=40 x3+ x8- x9=50 x4+ x9- x10=45 x5+ x10- x11=55 x6+ x11- x12=30 xl≤100 x2≤100 x3≤100 x4≤100 x5≤100 x6≤100 x7≤50 x8≤50 x9≤50 x10≤50 x11≤50 x12≤50 xi ≥0 (i=1,2,.......12) 1、用EXCEL線性規(guī)劃求解模板求解該數(shù)學(xué)模型。 2、本問題的最優(yōu)解是什么?此時(shí)最大目標(biāo)函數(shù)值是多少? 3、分別解釋“遞減成本”欄中各數(shù)據(jù)的含義 4、各約束條件的剩余量或松馳量及對(duì)偶價(jià)格是多少?其中一些約束條件的對(duì)偶價(jià)格為負(fù),其意義是什么?。 5、后12個(gè)約束條件中,大部分約束條件的對(duì)偶價(jià)格為0是什么意思?不為0的又具有什么含義? 6、為什么目標(biāo)函數(shù)中有些變量系數(shù)的取值范圍為無上限? 解: 1、Excel求解 2、本問題的最優(yōu)解:(50,90,0,45,85,0,0,50,0,0,30,0) 最優(yōu)值:217825 3、 可變單元格 終 遞減 目標(biāo)式 允許的 允許的 單元格 名字 值 成本 系數(shù) 增量 減量 $C$34 x1 50 0 825 1E+30 90 $D$34 x2 90 0 775 45 1E+30 $E$34 x3 0 0 850 1E+30 35 $F$34 x4 45 0 850 35 95 $G$34 x5 85 0 775 10 855 $H$34 x6 0 10 825 1E+30 10 $I$34 x7 0 90 40 1E+30 90 $J$34 x8 50 0 30 45 1E+30 $K$34 x9 0 35 35 1E+30 35 $L$34 x10 0 95 20 1E+30 95 $M$34 x11 30 0 40 10 855 $N$34 x12 0 855 40 1E+30 855 約束 終 陰影 約束 允許的 允許的 單元格 名字 值 價(jià)格 限制值 增量 減量 $R$11 實(shí)際值 50 825 50 50 50 $R$12 實(shí)際值 40 775 40 10 90 $R$13 實(shí)際值 50 850 50 100 0 $R$14 實(shí)際值 45 850 45 55 45 $R$15 實(shí)際值 55 775 55 15 85 $R$16 實(shí)際值 30 815 30 15 30 $R$17 實(shí)際值 50 0 100 1E+30 50 $R$18 實(shí)際值 90 0 100 1E+30 10 $R$19 實(shí)際值 0 0 100 1E+30 100 $R$20 實(shí)際值 45 0 100 1E+30 55 $R$21 實(shí)際值 85 0 100 1E+30 15 $R$22 實(shí)際值 0 0 100 1E+30 100 $R$23 實(shí)際值 0 0 50 1E+30 50 $R$24 實(shí)際值 50 -45 50 0 50 $R$25 實(shí)際值 0 0 50 1E+30 50 $R$26 實(shí)際值 0 0 50 1E+30 50 $R$27 實(shí)際值 30 0 50 1E+30 20 $R$28 實(shí)際值 0 0 50 1E+30 50 從這個(gè)靈敏度分析表: 遞減成本欄表示的是:對(duì)于解為0的變量,其目標(biāo)函數(shù)系數(shù)在現(xiàn)在基礎(chǔ)上再減少的量,使其對(duì)應(yīng)的解不為0 。 4、 約束 松弛量 對(duì)偶價(jià)格 xl- x7=50 0 -825 x2+ x7- x8=40 0 -775 x3+ x8- x9=50 0 -815 x4+ x9- x10=45 0 -850 x5+ x10- x11=55 0 -775 x6+ x11- x12=30 0 -815 xl≤100 50 0 x2≤100 10 0 x3≤100 100 0 x4≤100 55 0 x5≤100 15 0 x6≤100 100 0 x7≤50 50 0 x8≤50 0 45 x9≤50 50 0 x10≤50 50 0 x11≤50 20 0 x12≤50 50 0 其中對(duì)偶價(jià)格為負(fù)的意思是這些約束條件中,每增加一個(gè)常數(shù)項(xiàng)值,將會(huì)使目標(biāo)函數(shù)值增加量,因?yàn)槭乔笞钚?shù)點(diǎn)化的問題,所以目標(biāo)函數(shù)的增大,對(duì)偶價(jià)格為負(fù)。 5、后12個(gè)約束條件中,大部分約束條件的對(duì)偶價(jià)格為0是因?yàn)檫@些約束中,其松弛量都不為0,也就是說在前6個(gè)約束中,生產(chǎn)量沒有達(dá)到最大量(最大生產(chǎn)能力)的要求,再擴(kuò)大生產(chǎn)能力不會(huì)對(duì)最優(yōu)目標(biāo)產(chǎn)生影響;后6個(gè)約束中,說明倉庫沒有放滿,再擴(kuò)建立倉庫也不會(huì)改變總的存儲(chǔ)存用。 6、目標(biāo)函數(shù)中有些變量系數(shù)的取值范圍為無上限一般表示其解為0 ,而不為的相關(guān)值是應(yīng)減少的數(shù),所以對(duì)于增加的值,無論多大都不會(huì)影響相應(yīng)的解。- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
5 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 蘭州大學(xué) 運(yùn)籌學(xué) 線性規(guī)劃 問題 計(jì)算機(jī) 求解 課后 習(xí)題 題解
鏈接地址:http://appdesigncorp.com/p-12771985.html