最優(yōu)化-劉志斌-練習題一和二參考答案

練習題一1、建立優(yōu)化模型應考慮哪些要素?答：決策變量、目標函數(shù)和約束條件。2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停止準那么。答：針對一般優(yōu)化模型，討論解的可行域，假設存在一點，對于均有那么稱為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭代算法的收斂性是指迭代所得到的序列，滿足，那么迭代法收斂；收斂的停止準那么有，，，，等等。練習題二1、某公司看中了例中廠家所擁有的3種資源R1、R2、和R3，欲出價收購〔可能用于生產附加值更高的產品〕。如果你是該公司的決策者，對這3種資源的收購報價是多少？〔該問題稱為例的對偶問題〕。解：確定決策變量對3種資源報價作為本問題的決策變量。確定目標函數(shù)問題的目標很清楚——“收購價最小”。確定約束條件資源的報價至少應該高于原生產產品的利潤，這樣原廠家才可能賣。因此有如下線性規(guī)劃問題：*2、研究線性規(guī)劃的對偶理論和方法〔包括對偶規(guī)劃模型形式、對偶理論和對偶單純形法〕。答：略。3、用單純形法求解以下線性規(guī)劃問題：〔1〕；〔2〕解：〔1〕引入松弛變量x4，x5，x6cj→1-11000CB基bx1x2x3x4x5x60x421[1]-21000x532110100x64-101001cj-zj1-11000因檢驗數(shù)σ2<0，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x4作為換出的基變量。cj→1-11000CB基bx1x4x3x4x5x6-1x2211-21000x5110[3]-1100x64-101001cj-zj20-1100因檢驗數(shù)σ3<0，故確定x3為換入非基變量，以x3的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x5作為換出的基變量。cj→1-11000CB基bx1x2x5x4x5x6-1x28/35/3101/32/301x31/31/301-1/31/300x611/3-4/3001/3-1/31cj-zj7/3032/31/30因檢驗數(shù)σj>0，說明已求得最優(yōu)解：，去除添加的松弛變量，原問題的最優(yōu)解為：。〔2〕根據(jù)題意選取x1，x4，x5，為基變量：cj→0-1100CB基bx1x2x3x4x50x121-21000x420[1]-2100x5501101cj-zj0-1100因檢驗數(shù)σ2<0最小，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x4作為換出的基變量。cj→0-1100CB基bx1x2x3x4x50x1610-320-1x2201-2100x5300[3]-11cj-zj00-110因檢驗數(shù)σ3<0最小，故確定x3為換入非基變量，以x1的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x5作為換出的基變量。cj→0-1100CB基bx1x2x3x4x50x1910011-1x240101/32/31x31001-1/31/3cj-zj0002/31/3因檢驗數(shù)σj>0，說明已求得最優(yōu)解：。4、分別用大法、兩階段法和Matlab軟件求解以下線性規(guī)劃問題：〔1〕；〔2〕解：〔1〕大M法根據(jù)題意約束條件1和2可以合并為1，引入松弛變量x3，x4，構造新問題。cj→41M0CB基bx1x2x3x4Mx33[3]1100x431201cj-zj4-3M1-M004x1111/31/300x420[5/3]-1/31cj-zj0-1/3M-4/304x13/5102/5-1/51x26/501-1/53/5cj-zj00M-7/51/5因檢驗數(shù)σj>0，說明已求得最優(yōu)解：。Matlab調用代碼：f=[4;1];A=[-9,-3;1,2];b=[-6;3];Aeq=[3,1];beq=3;lb=[0;0];[x,fval]=linprog(f,A,b,Aeq,beq,lb)輸出結果：Optimizationterminated.x=fval=〔2〕大M法引入松弛變量x4，x5，x6，x7構造新問題。單純形表計算略；當所有非基變量為負數(shù)，人工變量=0.5，所以原問題無可行解。請同學們自己求解。Matlab調用代碼：f=[-10;-15;-12];A=[5,3,1;-5,6,15;-2,-1,-1];b=[9;15;-5];lb=[0;0;0];x=linprog(f,A,b,[],[],lb)輸出結果：原題無可行解。5、用內點法和Matlab軟件求解以下線性規(guī)劃問題：解：用內點法的過程自己書寫，參考答案：最優(yōu)解；最優(yōu)值5Matlab調用代碼：f=[2;1;1];Aeq=[1,2,2;2,1,0];beq=[6;5];lb=[0;0;0];[x,fval]=linprog(f,[],[],Aeq,beq,lb)輸出結果：Optimizationterminated.x=fval=6、用分支定界法求解以下問題：〔1〕；〔2〕解：〔1〕調用matlab編譯程序bbmethodf=[-5;-8];G=[11;59];h=[6;45][x,y]=bbmethod(f,G,h,[],[],[0;0],[],[1;1],1)x=33y=-39最優(yōu)解[33]；最優(yōu)值39〔2〕調用matlab編譯程序bbmethodf=[-7;-9];G=[-13;71];h=[6;35][x,y]=bbmethod(f,G,h,[],[],[0;0],[],[1;0],1)x=50y=-35最優(yōu)解[50]；最優(yōu)值357、用隱枚舉法和Matlab軟件求解以下問題：〔1〕；〔2〕解：隱枚舉法：〔1〕將〔0，0，0〕〔0，0，1〕〔0，1，0〕〔1，0，0〕〔0，1，1〕〔1，0，1〕〔1，1，0〕〔1，1，1〕分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是〔0，0，1〕，目標函數(shù)最優(yōu)值2.〔2〕將〔0，0，0，0，0〕〔0，0，0，0，1〕〔0，0，0，1，0〕〔0，0，1，0，0〕….〔1，1，1，1，1〕分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是〔1，1，0，0，0〕，目標函數(shù)最優(yōu)值-5。Matlab軟件求解：〔1〕調用代碼：f=[4;3;2];%價值向量fA=[2,-5,3;-4,-1,-3;0,-1,-1];%不等式約束系數(shù)矩陣A，[]中的分號“；”%為行分隔符b=[4;-3;-1];%不等式約束右端常數(shù)向量b[x,fval]=bintprog(f,A,b,[],[]);%調用函數(shù)bintprog。注意兩個空數(shù)組的占位作用。輸出結果x=001fval=2〔2〕調用代碼：f=[-3;-2;5;2;3];%價值向量fA=[1,1,1,2,1;7,0,3,-4,3;-11,6,0,-3,3];%不等式約束系數(shù)矩陣A，[]中的分號“；”%為行分隔符b=[4;8;-1];%不等式約束右端常數(shù)向量b[x,fval]=bintprog(f,A,b,[],[]);%調用函數(shù)bintprog。注意兩個空數(shù)組的占位作用。輸出結果x=11000fval=-5最優(yōu)值5。8、某地區(qū)有A、B、C三個化肥廠，供給本地甲、乙、丙、丁四個產糧區(qū)。各化肥廠可供給化肥的數(shù)量和各產糧區(qū)對化肥的需要量，以及各廠到各區(qū)每噸化肥的運價如表2-28所示。試制定一個使總運費最少的化肥調撥方案。表2-SEQ表2-\*ARABIC28運價/產糧(元/噸)區(qū)化肥廠甲乙丙丁各廠供給量/萬噸A158737A2491078A384293各區(qū)需要量/萬噸6633解：設A、B、C三個化肥廠為A1、A2、A3，甲、乙、丙、丁四個產糧區(qū)為B1、B2、B3、B4；cij為由Ai運化肥至Bj的運價，單位是元/噸；xij為由Ai運往Bj的化肥數(shù)量〔i=1,2,3;j=1,2,3,4〕單位是噸；z表示總運費，單位為元，依題意問題的數(shù)學模型為：該題可以用單純形法或matlab自帶工具箱命令〔linprog〕求解。*9、求解以下不平衡運輸問題〔各數(shù)據(jù)表中，方框內的數(shù)字為單位價格，框外右側的一列數(shù)為各發(fā)點的供給量，框底下一行數(shù)是各收點的需求量〕：〔1〕51710要求收點3的需求必須正好滿足。6468032515752050〔2〕51020要求收點1的需求必須由發(fā)點4供給。32410752159601551015解答略。10、一公司經理要分派4位推銷員去4個地區(qū)推銷某種商品。推銷員各有不同的經驗和能力，因而他們在不同地區(qū)能獲得的利潤不同，其獲利估計值如表2-29所示。公司經理應怎樣分派才使總利潤最大？表2-SEQ表2-\*ARABIC29地區(qū)推銷員1234135272837228342940335243233424322528解：用求極大值的“匈牙利