運(yùn)籌學(xué) 北京郵電大學(xué) 課件4學(xué)習(xí)資料

設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型maxZ=CX

（1.1）AX=b

（1.2）X≥0（1.3）式中A是m×n矩陣，m≤n并且r（A）=m，顯然A中至少有一個(gè)m×m子矩陣B，使得r（B）=m?；鵄中m×m子矩陣B并且有r（B）=m，則稱(chēng)B是線性規(guī)劃的一個(gè)基（或基矩陣）。當(dāng)m=n時(shí)，基矩陣唯一，當(dāng)m<n時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過(guò)4/8/2025【例1.12】線性規(guī)劃求所有基矩陣?！窘狻考s束方程的系數(shù)矩陣為2×5矩陣容易看出r（A）=2，2階子矩陣有=10個(gè)，基矩陣只有9個(gè)，即4/8/2025由線性代數(shù)知，基矩陣B必為非奇異矩陣并且|B|≠0。當(dāng)矩陣B的行列式等式零即|B|=0時(shí)就不是基當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱(chēng)為基向量，其余列向量稱(chēng)為非基向量

基向量對(duì)應(yīng)的變量稱(chēng)為基變量，非基向量對(duì)應(yīng)的變量稱(chēng)為非基變量

在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量?；兞?、非基變量是針對(duì)某一確定基而言的，不同的基對(duì)應(yīng)的基變量和非基變量也不同。4/8/2025可行解滿足式（1.2）及（1.3）的解X=（x1,x2…，xn)T

稱(chēng)為可行解?；究尚薪?，若基本解是可行解則稱(chēng)為是基本可行解（也稱(chēng)基可行解）。例如，與X=（0，0，0，3，2，）都是例1的可行解?；窘鈱?duì)某一確定的基B，令非基變量等于零，利用式（1.２）解出基變量，則這組解稱(chēng)為基Ｂ的基本解。最優(yōu)解滿足式（1.1）的可行解稱(chēng)為最優(yōu)解，即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解，例如可行解

是例2的最優(yōu)解。4/8/2025顯然，只要基本解中的基變量的解滿足式（1.３）的非負(fù)要求，那么這個(gè)基本解就是基本可行解。在例1中，對(duì)Ｂ１來(lái)說(shuō)，x1,x2是基變量，x3,x4，x5是非基變量，令x3=x4=x5=0，則式（1.２）為因|Ｂ１|≠０，由克菜姆法則知，x1,x2有唯一解x2=1則基本解為對(duì)B2來(lái)說(shuō)，x1,x4,為基變量，令非變量x2,x3,x5為零，由式（1.2）得到

，x4=4，4/8/2025由于是基本解，從而它是基本可行解，在中x1<0,因此不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解例如

滿足式（1.2）～（1.3），但不是任何基矩陣的基本解?；窘鉃?/8/2025最優(yōu)基基可行解對(duì)應(yīng)的基稱(chēng)為可行基；基本最優(yōu)解對(duì)應(yīng)的基稱(chēng)為最優(yōu)基，如上述B3就是最優(yōu)基，最優(yōu)基也是可行基。當(dāng)最優(yōu)解唯一時(shí)，最優(yōu)解亦是基本最優(yōu)解，當(dāng)最優(yōu)解不唯一時(shí)，則最優(yōu)解不一定是基本最優(yōu)解。例如右圖中線段的點(diǎn)為最優(yōu)解時(shí)，Q1點(diǎn)及Q2點(diǎn)是基本最優(yōu)解,線段的內(nèi)點(diǎn)是最優(yōu)解而不是基本最優(yōu)解?；咀顑?yōu)解

最優(yōu)解是基本解稱(chēng)為基本最優(yōu)解。例如，滿足式（1.1）~(1.3)是最優(yōu)解,又是B3的基本解,因此它是基本最優(yōu)解.4/8/2025基本最優(yōu)解、最優(yōu)解、基本可行解、基本解、可行解的關(guān)系如下所示：基本最優(yōu)解基本可行解可行解最優(yōu)解基本解例如,B點(diǎn)和D點(diǎn)是可行解,不是基本解;C點(diǎn)是基本可行解;A點(diǎn)是基本最優(yōu)解,同時(shí)也是最優(yōu)解、基本可行解、基本解和可行解。4/8/2025凸集設(shè)K是n維空間的一個(gè)點(diǎn)集，對(duì)任意兩點(diǎn)

時(shí)，則稱(chēng)K為凸集。就是以X（1）、X（2）為端點(diǎn)的線段方程，點(diǎn)X的位置由α的值確定，當(dāng)α=0時(shí)，X=X（2），當(dāng)α=1時(shí)X=X（1）凸組合設(shè)是Rn中的點(diǎn)若存在使得成立，則稱(chēng)X為的凸組合。4/8/2025極點(diǎn)

設(shè)K是凸集，，若X不能用K中兩個(gè)不同的點(diǎn)的凸組合表示為則稱(chēng)X是K的一個(gè)極點(diǎn)或頂點(diǎn)。X是凸集K的極點(diǎn)即X不可能是K中某一線段的內(nèi)點(diǎn)，只能是K中某一線段的端點(diǎn)。4/8/2025【定理1.1】若線性規(guī)劃可行解K非空,則K是凸集.【定理1.2】線性規(guī)劃的可行解集合K的點(diǎn)X是極點(diǎn)的充要條件為X是基本可行解.【定理1.3】若線性規(guī)劃有最優(yōu)解,則最優(yōu)值一定可以在可行解集合的某個(gè)極點(diǎn)上到達(dá),最優(yōu)解就是極點(diǎn)的坐標(biāo)向量.定理1.2刻劃了可行解集的極點(diǎn)與基本可行解的對(duì)應(yīng)關(guān)系，極點(diǎn)是基本可行解，反之，基本可行解一定是極點(diǎn)，但它們并非一一對(duì)應(yīng)，有可能兩個(gè)或幾個(gè)基本可行解對(duì)應(yīng)于同一極點(diǎn)（退化基本可行解時(shí)）。線性規(guī)劃的基本定理4/8/2025定理1.3描述了最優(yōu)解在可行解集中的位置，若最優(yōu)解唯一，則最優(yōu)解只能在某一極點(diǎn)上達(dá)到，若具有多重最優(yōu)解，則最優(yōu)解是某些極點(diǎn)的凸組合，從而最優(yōu)解是可行解集的極點(diǎn)或界點(diǎn)，不可能是可行解集的內(nèi)點(diǎn)。若線性規(guī)劃的可行解集非空且有界，則一定有最優(yōu)解；若可行解集無(wú)界，則線性規(guī)劃可能有最優(yōu)解，也可能沒(méi)有最優(yōu)解。定理1.2及1.3還給了我們一個(gè)啟示，尋求最優(yōu)解不是在無(wú)限個(gè)可行解中去找，而是在有限個(gè)基本可行解