5、量、非基向量、基解、基可行解、可行基例行列式基變量非基變量基向量非基向量對應(yīng)于基B1的基解X1非基可行解例行列式基變量非基變量基變量非基變量對應(yīng)于基B2的基解X2基可行解線性規(guī)劃解的關(guān)系圖非可行解可行解基可行解基解線性規(guī)劃問題解的概念最優(yōu)解？2.線性規(guī)劃問題的幾何意義基本概念凸集：線性規(guī)劃問題的幾何意義頂點:若K是凸集，X∈K；若X不能用不同的兩點的線性組合表示為：則X為K的一個頂點。凸集線性規(guī)劃問題的幾何意義頂點定理1:若線性規(guī)劃問題存在可行域,則其可行域:是凸集.基本定理證明:線性規(guī)劃問題的幾何意義只要驗證X在D中即可引理：線性規(guī)劃問題的可行解X為基可
6、行解的充要條件是X的正分量對應(yīng)的系數(shù)列向量是線性獨立的。定理3：若可行域有界，線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點上達(dá)到最優(yōu)。定理2：線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點。證明：反證法。分兩步。幾點結(jié)論：線性規(guī)劃問題的可行域是凸集。若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解?；尚薪馀c可行域的頂點一一對應(yīng)，可行域有有限多個頂點。最優(yōu)解必在頂點上得到。單純形法單純形法求解步驟：1、找一個基可行解作為X0初始解最容易得到的可行基是標(biāo)準(zhǔn)型線性規(guī)劃的系數(shù)矩陣的單位矩陣。2、求檢驗數(shù)，檢驗X0是否為最優(yōu)解（１）求檢驗數(shù)將約束方程組的基變量
7、的系數(shù)矩陣化為單位矩陣；通過代入或加減乘除消元法將目標(biāo)函數(shù)中的基變量消去，則非基變量的系數(shù)即為檢驗數(shù)．（２）最優(yōu)解的判別當(dāng)檢驗數(shù)全部小于或等于0時，該基可行解為最優(yōu)解,求解可結(jié)束.當(dāng)存在正的檢驗數(shù)時,該基可行解就不是最優(yōu)解,就要換到一個新的(與X0相鄰的)基可行解（X1）．3、換基（迭代）(1)確定進(jìn)基變量:凡是檢驗數(shù)大于0的非基變量都可進(jìn)基;但一般選擇最大的檢驗數(shù)對應(yīng)的變量進(jìn)基。(2)按最小比原則確定出基變量，就可得一新的（更接近于最優(yōu)解的）基可行解（X1），對（X1）重復(fù)２－３的過程就可在有限步得到最優(yōu)解，或判斷出無最優(yōu)解。求解下列的線性規(guī)劃maxz=
8、2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1+x4=161.124x2+x5=12x1,x2,x3,x4,x5≥0解：1、求一個初始基可行解可以看到x3,x4,x5的系數(shù)列向量組成一個單位矩陣，是約束方程組的一個可行基。這些向量構(gòu)成一個可行解基，對應(yīng)的基可行解為x0=（0，0，8，16，12），基對應(yīng)于基B0的變量x3,x4,x5為基變量。為求檢驗數(shù)，將約束方程組的基變量的系數(shù)矩陣化為單位矩陣可以得到x3+x1+2x2=8x4+4x1=16x5+4x2=12或x3=8-x1-2x2x4=16-4x1x5=12-4x2將上式代入目標(biāo)函數(shù)
9、z=2x1+3x2+0x3+0x4+0x5得到z=0+2x1+3x2。于是非基變量x1，x2的系數(shù)就為檢驗數(shù)，分別為2，3。2、求對應(yīng)于X0的檢驗數(shù)最優(yōu)性判別從目標(biāo)函數(shù)可以看出，該基可行解X0=(0,0,8,16,12,)對應(yīng)的目標(biāo)值為0，但是非基變量x1,x2的系數(shù)為正，因此只要增加x1或x2的值，（最大化的）目標(biāo)函數(shù)就可以增加。只要有正的檢驗數(shù)，該基可行解就不會是最優(yōu)解，只有當(dāng)全部的檢驗數(shù)都小于或等于零時，對應(yīng)的基可行解才為最優(yōu)解。3、換基（1）確定進(jìn)基變量凡是檢驗數(shù)大于0的非基變量都可進(jìn)基;但一般選擇最大的檢驗數(shù)對應(yīng)的變量進(jìn)基。由于x2的系數(shù)為正，顯
10、然當(dāng)x2增大，則目標(biāo)函數(shù)z的值也增大。當(dāng)x2定為換入變量后，必須從
