蘭州大學(xué)運(yùn)籌學(xué)——線性規(guī)劃問題的計算機(jī)求解課后習(xí)題題解.doc

《蘭州大學(xué)運(yùn)籌學(xué)——線性規(guī)劃問題的計算機(jī)求解課后習(xí)題題解.doc》由會員分享，可在線閱讀，更多相關(guān)《蘭州大學(xué)運(yùn)籌學(xué)——線性規(guī)劃問題的計算機(jī)求解課后習(xí)題題解.doc（8頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第四章 線性規(guī)劃問題的計算機(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)解是什么？此時最大目標(biāo)函數(shù)值是多少？ 3、 四個約束條件中，哪些約束條件起到了作用？各約束條件的剩余量或松弛量及對偶價格是多少？ 4、 目標(biāo)函數(shù)中各變量系數(shù)在什么范圍內(nèi)變化時，最優(yōu)解不變？ 5、 確定各給定條件中的常數(shù)項的上限和下限。 解： 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 　 　 　 　 　 　 　 約束 　 　 　 　 　 　 　 　 　 終 陰影 約束 允許的 允許的 單元格 名字 值 價格 限制值 增量 減量 $R$11 實際值 10 1.5 10 1.2 2 $R$12 實際值 13 0 4 9 1E+30 $R$13 實際值 24 0.5 24 6 6 $R$14 實際值 13 0 16 1E+30 3 3、 對于求最大化的問題，對偶價格=陰影價格 松弛量/剩余量 對偶價格 xl+ x2≤10 0 1.5 2xl+ x2≥4 9 0 xl+3 x2≤24 0 0.5 2xl+ x2≤16 13 0 因第一、第三個約束條件的松弛量/剩余量為0 ，所以這兩個約束條件起到了約束作用。 4、目標(biāo)函數(shù)中各變量系數(shù) 1≤ C1≤3 2≤ C1≤6 5、常數(shù)項 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)解是什么？此時最大目標(biāo)函數(shù)值是多少？ 3、各約束條件的剩余量或松弛量及對偶價格是多少？分別解釋其含義。 4、目標(biāo)函數(shù)中各變量系數(shù)在什么范圍內(nèi)變化時，最優(yōu)解不變？ 5、確定各給定條件中的常數(shù)項的上限和下限。 解： 本問題無解。 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)解是什么？此時最大目標(biāo)函數(shù)值是多少？ 3、分別解釋“遞減成本”欄中各數(shù)據(jù)的含義。 4、各約束條件的剩余量或松弛量及對偶價格是多少？分別解釋其含義。 5、C2再增加2，同時C3再減少2，其最優(yōu)解是否會變化？為什么？ 6、b1再增加3，同時b2再減少3，其對偶價格是否會變化？為什么？ 解： 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 約束 　 　 終 陰影 約束 允許的 允許的 單元格 名字 值 價格 限制值 增量 減量 $R$11 實際值 15 1 15 1.666666667 3 $R$12 實際值 20 0 20 5 3.75 $R$13 實際值 7.857142857 0 10 1E+30 2.142857143 遞減成本欄中的數(shù)據(jù)的絕對值，分別表示四個變量在目標(biāo)函數(shù)中系數(shù)，當(dāng)最優(yōu)解中不為0的變量，其遞減成本必為0，最優(yōu)解中變量值為0時，要使其解不為0時要使相應(yīng)系數(shù)增加遞減成本的絕對值，其解不為0。本問題中，x1為0 ，遞減成本的絕對值也為0 ，說明c1=1就能使x1<>0; x4為0，遞減成本的絕對值為1，說明c4=0才能使x4<>0。 4、 松弛量 對偶價格 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，同時C3再減少2，其最優(yōu)解必將發(fā)生變化。 6、b1的允許增量是1.667,所以b1再增加3，同時b2再減少3，其對偶價格必將發(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)解是什么？此時最大目標(biāo)函數(shù)值是多少？ 3、分別解釋“遞減成本”欄中各數(shù)據(jù)的含義。 4、各約束條件的剩余量或松弛量及對偶價格是多少？分別解釋其含義。 5、C1再減少5，同時C3再增加5，其最優(yōu)解是否會變化？為什么？ 6、b1再減少5，同時b3再增加5，其對偶價格是否會變化？為什么？ 解： 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 　 　 終 陰影 約束 允許的 允許的 單元格 名字 值 價格 限制值 增量 減量 $R$11 實際值 -6 0 6 1E+30 12 $R$12 實際值 18 -4 18 1E+30 12 $R$13 實際值 4 -1 4 4 4 遞減成本欄中的數(shù)據(jù)的絕對值，分別表示四個變量在目標(biāo)函數(shù)中系數(shù)，當(dāng)最優(yōu)解中不為0的變量，其遞減成本必為0，最優(yōu)解中變量值為0時，要使其解不為0時要使相應(yīng)系數(shù)增加遞減成本的絕對值，其解不為0。本問題中，x1為0 ，遞減成本的絕對值為7 ，說明c1由現(xiàn)在的-2變?yōu)?1時，就能使x1<>0; x2為0，遞減成本的絕對值為12，說明c2=0由現(xiàn)在的-1變?yōu)?1時才能使x2<>0。 4、 松弛量 對偶價格 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時其最優(yōu)解必將發(fā)生改變。 6、b3只能增加4，所以當(dāng)b3只能增加5時，其對偶價格必將發(fā)生改變。 4.5 某公司根據(jù)訂單安排生產(chǎn)。已知半年內(nèi)對某產(chǎn)品的需求量、單位生產(chǎn)費(fèi)用和單位存儲費(fèi)用如下表： 月份 1 2 3 4 5 6 需求量（件） 50 40 50 45 55 30 單位生產(chǎn)費(fèi)用（元/件） 825 775 850 850 775 825 單位存儲費(fèi)用（元/件） 40 30 35 20 40 40 又知公司每月的生產(chǎn)能力為100件，每月倉庫的容量為50件。問：如何確定產(chǎn)品未來半年內(nèi)每月最佳生產(chǎn)量和存儲量才能使總的費(fèi)用為最少？ 若設(shè)未來6個月每月的生產(chǎn)量分別為 xl、 x2、 x3、 x4、 x5、 x6 每月的存儲量分別為 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)解是什么？此時最大目標(biāo)函數(shù)值是多少？ 3、分別解釋“遞減成本”欄中各數(shù)據(jù)的含義 4、各約束條件的剩余量或松馳量及對偶價格是多少？其中一些約束條件的對偶價格為負(fù)，其意義是什么？。 5、后12個約束條件中，大部分約束條件的對偶價格為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 約束 　 　 終 陰影 約束 允許的 允許的 單元格 名字 值 價格 限制值 增量 減量 $R$11 實際值 50 825 50 50 50 $R$12 實際值 40 775 40 10 90 $R$13 實際值 50 850 50 100 0 $R$14 實際值 45 850 45 55 45 $R$15 實際值 55 775 55 15 85 $R$16 實際值 30 815 30 15 30 $R$17 實際值 50 0 100 1E+30 50 $R$18 實際值 90 0 100 1E+30 10 $R$19 實際值 0 0 100 1E+30 100 $R$20 實際值 45 0 100 1E+30 55 $R$21 實際值 85 0 100 1E+30 15 $R$22 實際值 0 0 100 1E+30 100 $R$23 實際值 0 0 50 1E+30 50 $R$24 實際值 50 -45 50 0 50 $R$25 實際值 0 0 50 1E+30 50 $R$26 實際值 0 0 50 1E+30 50 $R$27 實際值 30 0 50 1E+30 20 $R$28 實際值 0 0 50 1E+30 50 從這個靈敏度分析表： 遞減成本欄表示的是：對于解為0的變量，其目標(biāo)函數(shù)系數(shù)在現(xiàn)在基礎(chǔ)上再減少的量，使其對應(yīng)的解不為0 。 4、 約束 松弛量 對偶價格 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 其中對偶價格為負(fù)的意思是這些約束條件中，每增加一個常數(shù)項值，將會使目標(biāo)函數(shù)值增加量，因為是求最小數(shù)點化的問題，所以目標(biāo)函數(shù)的增大，對偶價格為負(fù)。 5、后12個約束條件中，大部分約束條件的對偶價格為0是因為這些約束中，其松弛量都不為0，也就是說在前6個約束中，生產(chǎn)量沒有達(dá)到最大量（最大生產(chǎn)能力）的要求，再擴(kuò)大生產(chǎn)能力不會對最優(yōu)目標(biāo)產(chǎn)生影響；后6個約束中，說明倉庫沒有放滿，再擴(kuò)建立倉庫也不會改變總的存儲存用。 6、目標(biāo)函數(shù)中有些變量系數(shù)的取值范圍為無上限一般表示其解為0 ，而不為的相關(guān)值是應(yīng)減少的數(shù)，所以對于增加的值，無論多大都不會影響相應(yīng)的解。