線性規(guī)劃解的概念

1

線性規(guī)劃的基、基本解與基本可行解

在一般情況下，由于圖解法無法解決三個(gè)變量以上的線性規(guī)劃問題，對(duì)于n個(gè)變量的線性規(guī)劃問題，我們必須用解方程的辦法來求得可行域的極點(diǎn)。

2

求解線性規(guī)劃問題，就是從滿足約束條（2.3b）、（2.3c）的方程組中找出一個(gè)解，使目標(biāo)函數(shù)（2.3a）達(dá)到最大值。線性規(guī)劃標(biāo)準(zhǔn)形式的約束條件：3

線性規(guī)劃標(biāo)準(zhǔn)形式的約束條件可表示為：

Ax=B，x≥0

其中A為m×n的矩陣，n>m，秩(A)

=m，b

Rm

。4

可行解：滿足約束條件的解稱為可行解。全部可行解的集合稱為可行域。

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解。5

關(guān)于線性規(guī)劃標(biāo)準(zhǔn)形式的基、基本解、基本可行解的概念，我們通過實(shí)例講解

6[例2.9]

在下述線性規(guī)劃問題中，舉例說明什么是基、基變量、基解、基可行解和可行基7[解]

寫出約束方程組的系數(shù)矩陣矩陣A的秩不大于4，而8是一個(gè)4*4的滿秩矩陣，故（P3，P4，P5，P6）是上述線形規(guī)劃問題的一個(gè)基。因而與P3、P4、P5、P6對(duì)應(yīng)的變量x3、x4、x5、x6是基變量，x1、x2是非基變量。在約束方程組中如果令x1=x2=0，即可解得x3=12，x4=8，x5=16，x6=12，由此X=（0，0，12，8，16，12）T是線性規(guī)劃問題的一個(gè)基解。因該基解中所有變量取值為非負(fù)，故它又是基可行解。因而與這個(gè)基可行解對(duì)應(yīng)的基（P3，P4，P5，P6）是一個(gè)可行基。9

基：設(shè)A為約束方程組（2.3b）m*n階系數(shù)矩陣，（設(shè)n>m），其秩為m。B是矩陣A中的一個(gè)m*m階的滿秩子矩陣，稱B是線性規(guī)劃問題的一個(gè)基。不失一般性，設(shè)B中的每一個(gè)列向量Pj（j=1，…，m）稱為基向量，與基向量Pj對(duì)應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的其他的變量稱為非基變量。10基可行解：滿足變量非負(fù)約束條件（2.3c）的基解稱為基可行解?；猓涸诩s束方程組（2.3b）中，令所有非基變量Xm+1=Xm+2=…=Xn=0，將這個(gè)解加上非基變量取0的值有X=（x1，x2，…，xm，0，…，0）T，稱X為線性規(guī)劃問題的基解。在基解中變量取非零值的個(gè)數(shù)不大于方程數(shù)m，又基解的總數(shù)不超過個(gè)。可行基：對(duì)應(yīng)于基可行解的基稱為可行基。11

線性規(guī)劃的基本解、基本可行解（極點(diǎn)）和可行基只與線性規(guī)劃問題標(biāo)準(zhǔn)形式的約束條件有關(guān)。注意12

線性規(guī)劃的基本定理：線性規(guī)劃的基本可行解就是可行域的極點(diǎn)。

它的重要性在于把可行域的極點(diǎn)這一幾何概念與基本可行解這一代數(shù)概念聯(lián)系起來，因而可以通過求基本可行解的線性代數(shù)的方法來得到可行域的一切極點(diǎn)，從而有可能進(jìn)一步獲得最優(yōu)極點(diǎn)。13

[例2.10]求下列線性規(guī)劃模型

Maxz=1500x1

+2500x2s.t.3x1

+2x2

+x3=652x1

+x2

+x4=403x2

+x5

=75

x1,x2,x3,x4,x5

≥0

的基本解、基本可行解、可行基。14

32100A=[P1,P2,P3,P4,P5]=2101003001

A矩陣包含以下10個(gè)3×3的子矩陣：

B1=[p1，p2，p3]B2=[p1，p2，p4]

B3=[p1，p2，p5]B4=[p1，p3，p4]

B5=[p1，p3，p5]B6=[p1，p4，p5]

B7=[p2，p3，p4]B8=[p2，p3，p5]

B9=[p2，p4，p5]B10=[p3，p4，p5]

15

其中

B4

=0，因而B4不是該線性規(guī)劃問題的基。其余均為非奇異方陣，因此該問題共有9個(gè)基。對(duì)于基B3=[p1，p2，p5]，令非基變量x3

=0，x4=0，在等式約束中令x3=0，x4

=0，解線性方程組：

3x1

+2x2

+0x5

=652x1

+x2

+0x5

=400x1

+3x2

+x5

=75

得到x1

=15，x2

=10，x5=45，對(duì)應(yīng)的基本可行解：

x=(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T。于是對(duì)應(yīng)的基B3是一個(gè)可行基。16

類似可得到

x(2)=(5,25,0,5,0)T（對(duì)應(yīng)B2）

x(7)=(20,0,5,0,75)T（對(duì)應(yīng)B5）

x(8)=(0,25,15,15,0)T（對(duì)應(yīng)B7）

x(9)=(0,0,65,40,75)T（對(duì)應(yīng)B10）是基本可行解；而x(3)=(0,32.5,0,7.5,-22.5)T（對(duì)應(yīng)B9）

x(4)=(65/3,0,0,-10/3,75)T（對(duì)應(yīng)B6）

x(5)=(7.5,25,-7.5,0,0)T（對(duì)應(yīng)B1）

x(6)=(0,40,-15,0,-45)T（對(duì)應(yīng)B8）是基本解。17

因此，對(duì)應(yīng)