運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用(第一二章習(xí)題解答).doc

運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用 習(xí)題解答習(xí)題一 P46 1.1 (a)01234132該問(wèn)題有無(wú)窮多最優(yōu)解，即滿足的所有，此時(shí)目標(biāo)函數(shù)值。(b) 01423用圖解法找不到滿足所有約束條件的公共范圍，所以該問(wèn)題無(wú)可行解。1.2 (a) 約束方程組的系數(shù)矩陣基基解是否基可行解目標(biāo)函數(shù)值否是10是3否否是3否是0否最優(yōu)解。(b) 約束方程組的系數(shù)矩陣基基解是否基可行解目標(biāo)函數(shù)值否是否是5否是5最優(yōu)解。1.3 (a)(1) 圖解法01234132 最優(yōu)解即為的解，最大值(2)單純形法首先在各約束條件上添加松弛變量，將問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式則組成一個(gè)基。令得基可行解，由此列出初始單純形表 基 。 基 ，新的單純形表為 基 ，表明已找到問(wèn)題最優(yōu)解。最大值 (b) (1) 圖解法036912396最優(yōu)解即為的解，最大值(2) 單純形法首先在各約束條件上添加松弛變量，將問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式則，組成一個(gè)基。令得基可行解，由此列出初始單純形表2 1 0 0 0 基 0 150 240 50 5 1 0 06 2 0 1 01 1 0 0 12 1 0 0 0。2 1 0 0 0 基 0 152 40 10 5 1 0 01 0 00 0 10 0 0，新的單純形表為2 1 0 0 0 基 0 2 0 0 0 1 1 0 0 0 1 0 0 0 0 ，表明已找到問(wèn)題最優(yōu)解，。最大值 1.6(a) 在約束條件中添加松弛變量或剩余變量，且令，該問(wèn)題轉(zhuǎn)化為其約束系數(shù)矩陣為在中人為地添加兩列單位向量令得初始單純形表 基 (b) 在約束條件中添加松弛變量或剩余變量，且令，該問(wèn)題轉(zhuǎn)化為其約束系數(shù)矩陣為在中人為地添加兩列單位向量令得初始單純形表 基 1.7(a)解1：大M法在上述線性規(guī)劃問(wèn)題中分別減去剩余變量再加上人工變量得其中M是一個(gè)任意大的正數(shù)。據(jù)此可列出單純形表 由單純形表計(jì)算結(jié)果可以看出，且，所以該線性規(guī)劃問(wèn)題有無(wú)界解解2：兩階段法。現(xiàn)在上述線性規(guī)劃問(wèn)題的約束條件中分別減去剩余變量再加上人工變量得第一階段的數(shù)學(xué)模型據(jù)此可列出單純形表 第一階段求得的最優(yōu)解,目標(biāo)函數(shù)的最優(yōu)值。因人工變量，所以是原線性規(guī)劃問(wèn)題的基可行解。于是可以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量取消，并填入原問(wèn)題的目標(biāo)函數(shù)的系數(shù)，進(jìn)行第二階段的運(yùn)算，見(jiàn)下表。 由表中計(jì)算結(jié)果可以看出，且，所以原線性規(guī)劃問(wèn)題有無(wú)界解。(b)解1：大M法在上述線性規(guī)劃問(wèn)題中分別減去剩余變量再加上人工變量得其中M是一個(gè)任意大的正數(shù)。據(jù)此可列出單純形表 由單純形表計(jì)算結(jié)果可以看出，最優(yōu)解，目標(biāo)函數(shù)的最優(yōu)解值X存在非基變量檢驗(yàn)數(shù)，故該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。解2：兩階段法?，F(xiàn)在上述線性規(guī)劃問(wèn)題的約束條件中分別減去剩余變量再加上人工變量得第一階段的數(shù)學(xué)模型據(jù)此可列出單純形表 第一階段求得的最優(yōu)解,目標(biāo)函數(shù)的最優(yōu)值。因人工變量，所以是原線性規(guī)劃問(wèn)題的基可行解。于是可以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量取消，并填入原問(wèn)題的目標(biāo)函數(shù)的系數(shù)，進(jìn)行第二階段的運(yùn)算，見(jiàn)下表。 由單純形表計(jì)算結(jié)果可以看出，最優(yōu)解，目標(biāo)函數(shù)的最優(yōu)解值由于存在非基變量檢驗(yàn)數(shù)，故該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。1.8 表1-23 表1-241.10最后一個(gè)表為所求。習(xí)題二 P762.1 寫(xiě)出對(duì)偶問(wèn)題(a) 對(duì)偶問(wèn)題為：(b) 對(duì)偶問(wèn)題為： 2.2(a)錯(cuò)誤。原問(wèn)題存在可行解，對(duì)偶問(wèn)題可能存在可行解，也可能無(wú)可行解。(b)錯(cuò)誤。線性規(guī)劃的對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題可能無(wú)可行解，也可能為無(wú)界解。(c)錯(cuò)誤。(d)正確。2.6 對(duì)偶單純形法(a)解：先將問(wèn)題改寫(xiě)為求目標(biāo)函數(shù)極大化，并化為標(biāo)準(zhǔn)形式列單純形表，用對(duì)偶單純形法求解，步驟如下 基 最優(yōu)解為， 目標(biāo)值。(b) 解：先將問(wèn)題改寫(xiě)為求目標(biāo)函數(shù)極大化，并化為標(biāo)準(zhǔn)形式列單純形表，用對(duì)偶單純形法求解 基 最優(yōu)解為， 目標(biāo)值。2.8 將該問(wèn)題化為標(biāo)準(zhǔn)形式：用單純形表求解 基 基 由于，所以已找到最優(yōu)解，目標(biāo)函數(shù)值(a) 令目標(biāo)函數(shù)(1)令，將反映到最終單純形表中 基 表中解為最優(yōu)的條件：，從而(2)令，將反映到最終單純形表中 基 表中解為最優(yōu)的條件：， 從而 (3) 令，將反映到最終單純形表中 基 表中解為最優(yōu)的條件：， 從而(b) 令線性規(guī)劃問(wèn)題為(1)先分析的變化使問(wèn)題最優(yōu)基不變的條件是，從而(2)同理有，從而(c) 由于代入，所以將約束條件減去剩余變量后的方程直接反映到最終單純形表中2 -1 1 0 0 0 基 2 60 101 1 1 1 0 00 3 1 1 1 00 -21 0 -2 0 0 10 -3 -1 -2 0 0對(duì)表中系數(shù)矩陣進(jìn)行初等變換，得2 -1 1 0 0 0 基 2 60 10 1 1 0 00 3 1 1 1 00 -80 -1 -3 -1 0 10 -3 -1 -2 0 02 -1 1 0 0 0 基 2 0 1 0 0 0 0 1 0 0 1 0 0 0 0 因此增加約束條件后，新的最優(yōu)解為，最優(yōu)值為2.12 (a) 線性規(guī)劃問(wèn)題單純形法求解 基 最優(yōu)解為 ，目標(biāo)值。(a) 設(shè)產(chǎn)品A的利潤(rùn)為，線性規(guī)劃問(wèn)題變?yōu)閱渭冃畏ㄇ蠼?基 為保持最優(yōu)計(jì)劃不變，應(yīng)使，都小于等于0，解得。(b) 線性規(guī)劃問(wèn)題