線性規(guī)劃及其解法

1、第一章 線性規(guī)劃及其解法1 線性規(guī)劃問(wèn)題及其一般數(shù)學(xué)模型（掌握）2 線性規(guī)劃問(wèn)題的圖解法（掌握）3 線性規(guī)劃問(wèn)題的單純形解法（了解）3.1 單純形法的基本思路確定初始基本可行解檢查是否為最優(yōu)解？求最優(yōu)解的目標(biāo)函數(shù)值確定改善方向求新的基本可行解是否3.2 單純形法的計(jì)算步驟第一步：求出LP的初始基本可行解，列出初始單純形表。確定初始基本可行解：約束條件全部是“”時(shí)，為每個(gè)約束條件加上一個(gè)松弛變量，化為標(biāo)準(zhǔn)形，則系數(shù)矩陣中含有一個(gè)單位矩陣，以此為基，得到初始基本可行解為： X=（0，0，b1,b2,bm)約束條件為=或時(shí)，化標(biāo)準(zhǔn)形后，一般不含單位矩陣，可以添加人工變量構(gòu)造一個(gè)單位矩陣作為基（人工基

2、）。如例1：系數(shù)矩陣為： 1 1 1 0 0 2 1 0 1 0 初始可行基 0 1 0 0 1X=（0，0，300，400，250）基本可行解初始單純形表：cj50100000CBXBbx1x2x3x4x50 x3300111000 x4400210100 x525001001zj00000j =cj-zj50100000第二步：最優(yōu)性檢驗(yàn)最優(yōu)解判別定理： max型問(wèn)題，對(duì)于某個(gè)基本可行解，如果所有檢驗(yàn)數(shù)j0，則現(xiàn)有基本可行解為最優(yōu)解。第三步：基變換確定入基變量 若j 0，對(duì)應(yīng)的變量xj就可作為入其變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于零時(shí)，從中找出最大的一個(gè)。k=maxj|j 0 。確定出基變量 x

3、l稱為出基變量 alk稱為主元素迭代。 用入基變量替換出基變量，得到一個(gè)新的基和基本可行解，畫(huà)出一個(gè)新的單純形表。行變換：初始單純形表：cj50100000CBXBbx1x2x3x4x50 x3300111000 x4400210100 x525001001zj00000j =cj-zj50100000第四步：重復(fù)二、三步直到計(jì)算結(jié)束為止。cj50100000CBXBbx1x2x3x4x50 x3501010-10 x41502001-1100 x22500 1001zj010000100j =cj-zj50000-100cj50100000CBXBbx1x2x3x4x550 x1501010

4、-10 x45000-211100 x22500 1001zj5010050050j =cj-zj00-500-50習(xí)題1：下表為用單純形法計(jì)算時(shí)某一步的表格。已知該線性規(guī)劃的目標(biāo)函數(shù)為maxz=5x1+3x2，約束形式為，x3,x4為松馳變量，表中解代入目標(biāo)函數(shù)后得z=101、求a-g的值；2、表中給出的解是否為最優(yōu)解？a=2,b=0,c=0,d=1,e=4/5,f=0,g=-5表中給出的解為最優(yōu)解。習(xí)題2：目標(biāo)函數(shù)為max Z =28x4+x5+2x6，約束形式為“”，且x1，x2，x3為松弛變量，表中的解代入目標(biāo)函數(shù)中得Z=14，求出a-g的值，并判斷是否最優(yōu)解？Cj0002812XBC

5、BbX1X2X3X4X5X6X62a30-14/3011X2056d205/20X42800ef100Cj-Zjbc00-1ga=7,b=-6,c=0,d=1,e=0,f=1/3,g=0最優(yōu)解。 復(fù)習(xí)單純型法的幾種特殊情況作業(yè)：P25（6）第6小題當(dāng)c1值從2變?yōu)?.5，c2值從3變?yōu)?.5時(shí)，其最優(yōu)解是否變化？為什么?正確方法用只有當(dāng)計(jì)算機(jī)求解時(shí)，才用百分百法則。P36（4）最優(yōu)解為x1=8.5 x2=1.5 x3=0 x4=0目標(biāo)函數(shù)為：maxZ=2x1+x2-x3+x4(4)當(dāng)c1,c2,c4值不變時(shí)，C3在-到5.5范圍內(nèi)變化時(shí)，最優(yōu)解不變，此時(shí)最優(yōu)目標(biāo)函數(shù)值不變。因?yàn)閤3=0，目標(biāo)函

6、數(shù)系數(shù)變化，不影響目標(biāo)函數(shù)值的變化。（5）當(dāng)c2, c3,c4值不變時(shí)， c1在0到+范圍內(nèi)變化時(shí)，最優(yōu)解不變，此時(shí)最優(yōu)目標(biāo)函數(shù)值改變。 在一個(gè)已得到最優(yōu)解的單純形表中，如果存在某個(gè)非基變量的檢驗(yàn)數(shù)為零，說(shuō)明有無(wú)窮多最優(yōu)解。一、無(wú)窮多最優(yōu)解 若j0，線性規(guī)劃的最優(yōu)解里還有人工變量，則此線性規(guī)劃問(wèn)題無(wú)可行解。二、 存在一個(gè)大于零的檢驗(yàn)數(shù)j，并且該列系數(shù)向量每個(gè)元素都0，則線性規(guī)劃問(wèn)題是無(wú)界的。一般地說(shuō)此類問(wèn)題的出現(xiàn)是由于建模錯(cuò)誤所引起的。三、無(wú)界解 在單純形法計(jì)算過(guò)程中，基變量有時(shí)存在兩個(gè)以上相同的最小比值，這稱之為退化。四、 如果是退化現(xiàn)象，可能經(jīng)過(guò)6次迭代后得到的單純形表與第0次單純形表一樣

7、，這樣就出現(xiàn)了循環(huán)。 為了避免這種現(xiàn)象，當(dāng)存在兩個(gè)和兩個(gè)以上最小比值時(shí)，選一個(gè)下標(biāo)最小的基變量為出基變量。1、表中解為唯一最優(yōu)解2、表中解為最優(yōu)解，但存在無(wú)窮多最優(yōu)解3、該線性規(guī)劃問(wèn)題具有無(wú)界解4、表中解非最優(yōu)，為對(duì)解改進(jìn)，換入變量為x1，換出變量為x5。習(xí)題一、下表是求某極大化線性規(guī)劃問(wèn)題計(jì)算得到的單純形表，表中無(wú)人工變量，a1,a2,d,c1,c2為待定常數(shù)，試說(shuō)明這些常數(shù)分別取何值時(shí)，以下結(jié)論成立。4-a012a-221Z-a+80-12a014x11-201-1101x22-1121002x50 x6x5x4x3x2x1bxBcB000221cj1、把表中缺少的項(xiàng)目填上適當(dāng)?shù)臄?shù)或式子2

8、、要使上表成為最優(yōu)表，a應(yīng)滿足什么條件3、何時(shí)有唯一最優(yōu)解4、何時(shí)有無(wú)窮多最優(yōu)解5、何時(shí)以x3替換x1習(xí)題二、下表是求某極大化線性規(guī)劃問(wèn)題計(jì)算得到的單純形表，表中無(wú)人工變量，a為待定常數(shù)， a取何值時(shí)，以下結(jié)論成立。1Z-a+8-12a4x1-21-11x22-1212x5x6x5x4x3x2x1bxBcB22cj1、把表中缺少的項(xiàng)目填上適當(dāng)?shù)臄?shù)或式子2、要使上表成為最優(yōu)表，a應(yīng)滿足什么條件3、何時(shí)有唯一最優(yōu)解4、何時(shí)有無(wú)窮多最優(yōu)解5、何時(shí)以x3替換x12、2a 43、2a44、 2a 4 a=2或a=45、1a4/2a 0a0無(wú)界解無(wú)可行解無(wú)窮多最優(yōu)解找出主元素，迭代是是否否否是是3.5 單

9、純形法的靈敏度分析-目標(biāo)函數(shù)中ck的靈敏度分析當(dāng)ck變成ck +ck原規(guī)劃最優(yōu)解不變的條件是： j 0在最終的單純形表中，xk是非基變量時(shí)k = ck+ck- zk= ck +k 0即： ck -k 例在最終的單純形表中，xk是基變量時(shí)j = cj-zj=cj-（zj+ckakj ）0 即：j+ckakj0 例C3變化：cj50100c300CBXBbx1x2x3x4x550 x1501010-10 x45000-211100 x22500 1001zj5010050050j =cj-zj00C3-500-50C1變化：cjc1100000CBXBbx1x2x3x4x5c1x1501010-1

10、0 x45000-211100 x22500 1001zjc1100c10100-c1j =cj-zj00-c10c1-100C2變化：cj50c2000CBXBbx1x2x3x4x550 x1501010-10 x45000-211c2x22500 1001zj50c2500C2-50j =cj-zj00-50050-c2約束方程右端常數(shù)項(xiàng)靈敏度分析原規(guī)劃最優(yōu)基不變的條件：B-1(b+b)= B-1 b+ B-1 b0原規(guī)劃最優(yōu)基改變的條件：B-1(b+b)至少有一個(gè)分量小于零。約束方程系數(shù)矩陣A靈敏度分析非基變量xk的系數(shù)pk變成pk k =ck-cB B-1 pk 0 最優(yōu)解不變，否則繼

11、續(xù)進(jìn)行迭代?；兞康南禂?shù)發(fā)生變化 通常需要重新計(jì)算復(fù)習(xí)：關(guān)于靈敏度分析當(dāng)目標(biāo)函數(shù)系數(shù)ck變化時(shí)： 原規(guī)劃最優(yōu)解不變的條件是： j 0 （情況一；情況二）P30圖3-4當(dāng)右端項(xiàng)bi變化時(shí)： 原規(guī)劃最優(yōu)基不變的條件是： 新解的每一個(gè)分量大于等于零。即： B-1(b+b)= B-1 b+ B-1 b0系數(shù)矩陣A變化時(shí) 非基變量系數(shù)變化時(shí)，最優(yōu)解不變的條件是k 0 基變量系數(shù)變化時(shí)，需重新計(jì)算軟件中如何識(shí)別無(wú)窮多最優(yōu)解情況P112如果在最終表上檢驗(yàn)數(shù)為零的非基變量是松弛變量或剩余變量： 計(jì)算機(jī)輸出的約束條件欄中有一個(gè)約束條件的松弛變量或剩余變量為零，且其對(duì)偶價(jià)格也為零，表明有無(wú)窮多最優(yōu)解。如果在最終單純形表上，檢驗(yàn)數(shù)為零的非基變量是一般決策變量。 在計(jì)算機(jī)輸出中，若有一個(gè)取值為零的決策變量其相差值也為零，說(shuō)明有無(wú)窮多最優(yōu)解。對(duì)偶價(jià)格：約束條件右端項(xiàng)增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量，稱為這個(gè)約束條件對(duì)偶價(jià)格（yi)。約束條件中的松弛變量（剩余變量）不為零時(shí)，這個(gè)約束條件對(duì)偶價(jià)格為零。單純形表中對(duì)偶價(jià)格： 約束類型 對(duì)偶價(jià)格的取值 等于對(duì)應(yīng)的松弛變量的zj值 等于對(duì)應(yīng)的剩余變量的zj值相反數(shù) 等于對(duì)應(yīng)的人工變量的zj值對(duì)偶價(jià)格大于零，會(huì)使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)。（求最大時(shí)更大，求最小時(shí)更?。?duì)偶價(jià)格小于零，會(huì)使最優(yōu)目標(biāo)函數(shù)值變壞。 （求最大時(shí)變小，求最小時(shí)變大）