蘭州大學運籌學——線性規(guī)劃問題的計算機求解課后習題題解.doc

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

第四章 線性規(guī)劃問題的計算機求解4.1 有以下線性規(guī)劃數(shù)學問題： max Z=2xl+3 x2 S.T. xl+ x210 2xl+ x24xl+3 x2242xl+ x216 xl 、 x201、 用EXCEL線性規(guī)劃求解模板求解該數(shù)學模型。2、 本問題的最優(yōu)解是什么？此時最大目標函數(shù)值是多少？3、 四個約束條件中，哪些約束條件起到了作用？各約束條件的剩余量或松弛量及對偶價格是多少？4、 目標函數(shù)中各變量系數(shù)在什么范圍內變化時，最優(yōu)解不變？5、 確定各給定條件中的常數(shù)項的上限和下限。解：1、 2、最優(yōu)解：（3，7），最優(yōu)值：27可變單元格終遞減目標式允許的允許的單元格名字值成本系數(shù)增量減量$C$34x130211$D$34x270331約束終陰影約束允許的允許的單元格名字值價格限制值增量減量$R$11 實際值101.5101.22$R$12 實際值130491E+30$R$13 實際值240.52466$R$14 實際值130161E+303 3、 對于求最大化的問題，對偶價格=陰影價格 松弛量/剩余量 對偶價格xl+ x210 0 1.5 2xl+ x24 9 0 xl+3 x224 0 0.52xl+ x216 13 0 因第一、第三個約束條件的松弛量/剩余量為0 ，所以這兩個約束條件起到了約束作用。 4、目標函數(shù)中各變量系數(shù) 1 C13 2 C16 5、常數(shù)項 8 b19.2 無限 b213 18 b33013 b4無限4.2 有以下線性規(guī)劃數(shù)學問題： min f=8xl+3 x2 S.T. 500xl+100 x21200000 5xl+4 x260000100xl300000 xl 、 x201、用EXCEL線性規(guī)劃求解模板求解該數(shù)學模型。2、本問題的最優(yōu)解是什么？此時最大目標函數(shù)值是多少？3、各約束條件的剩余量或松弛量及對偶價格是多少？分別解釋其含義。4、目標函數(shù)中各變量系數(shù)在什么范圍內變化時，最優(yōu)解不變？5、確定各給定條件中的常數(shù)項的上限和下限。解：本問題無解。4.3 有以下線性規(guī)劃數(shù)學問題： max Z=xl+2 x2+3 x3- x4 S.T. xl+2 x2+3 x315 2xl+ x2+5 x320xl+2 x2+ x3+ x410 xl 、 x2、 x3、 x401、用EXCEL線性規(guī)劃求解模板求解該數(shù)學模型。2、本問題的最優(yōu)解是什么？此時最大目標函數(shù)值是多少？3、分別解釋“遞減成本”欄中各數(shù)據的含義。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、可變單元格終遞減目標式允許的允許的單元格名字值成本系數(shù)增量減量$C$34x100101E+30$D$34x22.1428571430201.4$E$34x33.5714285710370$F$34x40-1-111E+30約束終陰影約束允許的允許的單元格名字值價格限制值增量減量$R$11 實際值151151.6666666673$R$12 實際值2002053.75$R$13 實際值7.8571428570101E+302.142857143遞減成本欄中的數(shù)據的絕對值，分別表示四個變量在目標函數(shù)中系數(shù)，當最優(yōu)解中不為0的變量，其遞減成本必為0，最優(yōu)解中變量值為0時，要使其解不為0時要使相應系數(shù)增加遞減成本的絕對值，其解不為0。本問題中，x1為0 ，遞減成本的絕對值也為0 ，說明c1=1就能使x10; x4為0，遞減成本的絕對值為1，說明c4=0才能使x40。4、 松弛量 對偶價格xl+2 x2+3 x315 0 1 2xl+ x2+5 x320 0 0xl+2 x2+ x3+ x410 2.143 05、上表中 0.6C22 3C310 可見C2沒有增加允許，C3沒有減少允許，所以C2再增加2，同時C3再減少2，其最優(yōu)解必將發(fā)生變化。6、b1的允許增量是1.667,所以b1再增加3，同時b2再減少3，其對偶價格必將發(fā)生變化。 4.4 有以下線性規(guī)劃數(shù)學問題： min f=-2xl- x2+3 x3-4 x4 S.T. xl+2 x2+4 x3- x46 2xl+3 x2- x3+ x418xl+ x2+ x34 xl 、 x2、 x3、 x401、用EXCEL線性規(guī)劃求解模板求解該數(shù)學模型。2、本問題的最優(yōu)解是什么？此時最大目標函數(shù)值是多少？3、分別解釋“遞減成本”欄中各數(shù)據的含義。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、終遞減目標式允許的允許的單元格名字值成本系數(shù)增量減量$C$34x107-21E+307$D$34x2012-11E+3012$E$34x340311E+30$F$34x4220-411E+30終陰影約束允許的允許的單元格名字值價格限制值增量減量$R$11 實際值-6061E+3012$R$12 實際值18-4181E+3012$R$13 實際值4-1444遞減成本欄中的數(shù)據的絕對值，分別表示四個變量在目標函數(shù)中系數(shù)，當最優(yōu)解中不為0的變量，其遞減成本必為0，最優(yōu)解中變量值為0時，要使其解不為0時要使相應系數(shù)增加遞減成本的絕對值，其解不為0。本問題中，x1為0 ，遞減成本的絕對值為7 ，說明c1由現(xiàn)在的-2變?yōu)?1時，就能使x10; x2為0，遞減成本的絕對值為12，說明c2=0由現(xiàn)在的-1變?yōu)?1時才能使x20。4、 松弛量 對偶價格xl+2 x2+4 x3- x46 12 0 2xl+3 x2- x3+ x418 0 4xl+ x2+ x34 0 1 5、上表中 -9C1無限 無限C34 可見C3只能允許增加1，當增加5時其最優(yōu)解必將發(fā)生改變。6、b3只能增加4，所以當b3只能增加5時，其對偶價格必將發(fā)生改變。4.5 某公司根據訂單安排生產。已知半年內對某產品的需求量、單位生產費用和單位存儲費用如下表：月份123456需求量（件）504050455530單位生產費用（元/件）825775850850775825單位存儲費用（元/件）403035204040又知公司每月的生產能力為100件，每月倉庫的容量為50件。問：如何確定產品未來半年內每月最佳生產量和存儲量才能使總的費用為最少？若設未來6個月每月的生產量分別為 xl、 x2、 x3、 x4、 x5、 x6 每月的存儲量分別為 x7、 x8、 x9、 x10、 x11、 x12可得線性規(guī)劃數(shù)學模型：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=40x3+ x8- x9=50x4+ x9- x10=45x5+ x10- x11=55x6+ x11- x12=30xl100x2100x3100x4100x5100x6100x750x850x950x1050x1150x1250 xi 0 (i=1,2,.12)1、用EXCEL線性規(guī)劃求解模板求解該數(shù)學模型。2、本問題的最優(yōu)解是什么？此時最大目標函數(shù)值是多少？3、分別解釋“遞減成本”欄中各數(shù)據的含義4、各約束條件的剩余量或松馳量及對偶價格是多少？其中一些約束條件的對偶價格為負，其意義是什么？。5、后12個約束條件中，大部分約束條件的對偶價格為0是什么意思？不為0的又具有什么含義？6、為什么目標函數(shù)中有些變量系數(shù)的取值范圍為無上限？解：1、Excel求解2、本問題的最優(yōu)解：（50，90，0，45，85，0，0，50，0，0，30，0） 最優(yōu)值：2178253、可變單元格終遞減目標式允許的允許的單元格名字值成本系數(shù)增量減量$C$34x15008251E+3090$D$34x2900775451E+30$E$34x3008501E+3035$F$34x44508503595$G$34x585077510855$H$34x60108251E+3010$I$34x7090401E+3090$J$34x850030451E+30$K$34x9035351E+3035$L$34x10095201E+3095$M$34x113004010855$N$34x120855401E+30855約束終陰影約束允許的允許的單元格名字值價格限制值增量減量$R$11實際值50825505050$R$12實際值40775401090$R$13實際值50850501000$R$14實際值45850455545$R$15實際值55775551585$R$16實際值30815301530$R$17實際值5001001E+3050$R$18實際值9001001E+3010$R$19實際值001001E+30100$R$20實際值4501001E+3055$R$21實際值8501001E+3015$R$22實際值001001E+30100$R$23實際值00501E+3050$R$24實際值50-4550050$R$25實際值00501E+3050$R$26實際值00501E+3050$R$27實際值300501E+3020$R$28實際值00501E+3050從這個靈敏度分析表：遞減成本欄表示的是：對于解為0的變量，其目標函數(shù)系數(shù)在現(xiàn)在基礎上再減少的量，使其對應的解不為0 。4、 約束 松弛量 對偶價格xl- x7=50 0 -825 x2+ x7- x8=40 0 -775x3+ x8- x9=50 0 -815x4+ x9- x10=45 0 -850x5+ x10- x11=55 0 -775x6+ x11- x12=30 0 -815xl100 50 0x2100 10 0x3100 100 0x4100 55 0x5100 15 0x6100 100 0x750 50 0x850 0 45x950 50 0x1050 50 0x1150 20 0x1250 50 0 其中對偶價格為負的意思是這些約束條件中，每增加一個常數(shù)項值，將會使目標函數(shù)值增加量，因為是求最小數(shù)點化的問題，所以目標函數(shù)的增大，對偶價格為負。5、后12個約束條件中，大部分約束條件的對偶價格為0是因為這些約束中，其松弛量都不為0，也就是說在前6個約束中，生產量沒有達到最大量（最大生產能力）的要求，再擴大生產能力不會對最優(yōu)目標產生影響；后6個約束中，說明倉庫沒有放滿，再擴建立倉庫也不會改變總的存儲存用。6、目標函數(shù)中有些變量系數(shù)的取值范圍為無上限一般表示其解為0 ，而不為的相關值是應減少的數(shù)，所以對于增加的值，無論多大都不會影響相應的解。