北郵運(yùn)籌學(xué)ch線性規(guī)劃解的概念

1、 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型max Z=CX （1.1）AX=b （1.2）X0 （1.3）式中A是mn矩陣，mn并且r（A）=m，顯然A中至少有一個(gè)mmB，使得r（B）=m。基 A中mmB并且有r（B）=m，則稱B是線性規(guī)劃的一個(gè)基（或基矩陣 ）。當(dāng)m=n時(shí)，基矩陣唯一，當(dāng)mn時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過7/25/2022【例1.12】線性規(guī)劃 求所有基矩陣。 【解】約束方程的系數(shù)矩陣為25矩陣 容易看出r（A）=2，2階子矩陣有 =10個(gè)，基矩陣只有9個(gè)，即7/25/2022由線性代數(shù)知，基矩陣B必為非奇異矩陣并且|B|0。當(dāng)矩陣B的行列式等式零即|B|=0時(shí)就不是基 當(dāng)確定某一矩陣為基矩

2、陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱為基向量，其余列向量稱為非基向量 基向量對(duì)應(yīng)的變量稱為基變量，非基向量對(duì)應(yīng)的變量稱為非基變量 在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量?；兞?、非基變量是針對(duì)某一確定基而言的，不同的基對(duì)應(yīng)的基變量和非基變量也不同。7/25/2022可行解 滿足式（1.2）及（1.3）的解X=（x1,x2，xn)T 稱為可行解 。基本可行解，若基本解是可行解則稱為是基本可行解（也稱基可行解）。 例如， 與X=（0，0，0，3，2，）都是例1 的可行解。 基本解 對(duì)某一確定的基B，令非基變量等于零，利用式（1.）

3、解出基變量，則這組解稱為基的基本解。 最優(yōu)解 滿足式 （1 .1）的可行解稱為最優(yōu)解，即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解，例如可行解 是例2的最優(yōu)解。7/25/2022顯然，只要基本解中的基變量的解滿足式（1.）的非負(fù)要求，那么這個(gè)基本解就是基本可行解。 在例1中，對(duì)來說，x1,x2是基變量，x3,x4，x5是非基變量，令x3=x4=x5=0，則式（1.）為因|，由克菜姆法則知，x1,x2有唯一解x2=1則基本解為對(duì)B2來說，x1,x4,為基變量，令非變量x2,x3,x5為零，由式（1.2）得到 ，x4=4，7/25/2022由于 是基本解，從而它是基本可行解，在 中x10,因此不是

4、可行解，也就不是基本可行解。 反之，可行解不一定是基本可行解例如 滿足式（1.2）（1.3），但不是任何基矩陣的基本解?；窘鉃?/25/2022最優(yōu)基 基可行解對(duì)應(yīng)的基稱為可行基；基本最優(yōu)解對(duì)應(yī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)解是基本解稱為基本最優(yōu)解。例如，滿足式（1.1）(1.3)是最優(yōu)解,又是B3的基本解,因此它是基本最優(yōu)解.7/25/2022基本最優(yōu)解、最優(yōu)解、基

5、本可行解、基本解、可行解的關(guān)系如下所示：基本最優(yōu)解基本可行解可行解最 優(yōu) 解基本解例如,B點(diǎn)和D點(diǎn)是可行解,不是基本解;C點(diǎn)是基本可行解;A點(diǎn)是基本最優(yōu)解,同時(shí)也是最優(yōu)解、基本可行解、基本解和可行解。7/25/2022凸集設(shè)K是n維空間的一個(gè)點(diǎn)集，對(duì)任意兩點(diǎn) 時(shí)，則 稱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)若存在 使得 成立， 則稱X為 的凸組合。7/25/2022極點(diǎn) 設(shè)K是凸集， ，若X不能用K中兩個(gè)不同的 點(diǎn) 的凸組合表示為則稱X是K的一個(gè)極點(diǎn)或頂點(diǎn)。 X是凸集K的極點(diǎn)即X不可能是K

6、中某一線段的內(nèi)點(diǎn)，只能是K中某一線段的端點(diǎn)。 7/25/2022【定理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ī)劃的基本定理7/25/2022 定理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)解；若可行解集無界，則線性規(guī)劃可能有最優(yōu)解，也可能沒有最優(yōu)解。 定理1.2及1.3還給了我們一個(gè)啟示，尋求最優(yōu)解不是在無限個(gè)可行解中去找，而是在有限個(gè)基本可行解中去尋求。下一節(jié)將介紹一種有效地尋找最優(yōu)解的方法。7/25/20221. 線性規(guī)劃常用的