02第二章 線性規(guī)劃的基本性質(zhì)

1、第二章線性規(guī)劃的基本性質(zhì)在生產(chǎn)、經(jīng)濟(jì)、技術(shù)領(lǐng)域，許多工程技術(shù)和管理問題實際上是線性的，或者是可以用線 性函數(shù)近似表達(dá)的，所以線性規(guī)劃的研究是很有意義的。而且對線性規(guī)劃的理論的研究要比 非線性規(guī)劃領(lǐng)域成熟的多。掌握線性規(guī)劃的基本理論和求解方法是本課程最重要的目標(biāo)之 一。2.1線性規(guī)劃解的幾何特征借助于平面圖形可以直觀地了解線性規(guī)劃解的幾何特征，具體介紹一個實例。設(shè)有兩個決策變量和的線性規(guī)劃：min - 2 x1 - x2s.t.-3 x1 -4 x2 K12(2.1)-x1 + 2 x2 N -2 x1,x2, N 0首先在x1Ox2平面上畫出(2.1)的可行域：K = (x , x )T 1-

2、3 x - 4 x -12, - x + 2 x -2, x , x 012121212為此，只要畫出K的邊界：-3 x1 -4 x2 N-12-x1 + 2 x2 N -2x1 = 0, x2 = 0該可行域如圖2.1所示，它是一個由四條直線組成的凸多邊形。任何一個含兩個變量 的線性規(guī)劃的可行域都是以直線為邊的凸多邊形。觀察目標(biāo)函數(shù)：f(x) = - 2 x1 - x2對于任一給定的實數(shù)a，方程-2 x1 - x2 =a表示一條直線，稱為f的等值線。變動a 可以得到一族相互平行的直線。把f的等值線向函數(shù)值a減小的方向移動，它與凸多邊形K 的最后一個交點即為的最優(yōu)解。最優(yōu)解是凸多邊形的一個頂點

3、。設(shè)目標(biāo)函數(shù)f(x) = C1玉+c2 %它是玉和x2的函數(shù)，它的斜率是-賓，它在任意一點 c2的梯度：/)T以=海1J =W C 2)、12 7它與目標(biāo)函數(shù)的等值線垂直，由高等數(shù)學(xué)的有關(guān)知識可知，當(dāng)點(氣,X2)T沿著梯度方向 移動時，f的值將隨之增大，沿著梯度負(fù)方向移動時，f的值將隨之減小。對于式(2.1)，不妨在原點做梯度Vf = (C1c2)t = (-2, -1)T，從原點至點(-2, -1)T作 一個向量即為該梯度。過原點作梯度向量的垂直線(用虛線表示)，它為過原點且a=0的等 值線：-2 % - x2=0因為我們的問題是求目標(biāo)函數(shù)的最小值minf，因此讓等值線逆梯度方向移動，于是

4、目 標(biāo)函數(shù)值逐步減小，在等值線剛好要離開可行域的時候，這時等值線在可行域的的一個頂點，一. (16 3、T,頂點X*= 16,- 就是線性規(guī)劃的最優(yōu)解，f (X*) = -7是線性規(guī)劃的最優(yōu)值。15 5 J結(jié)論：若兩個變量的線性規(guī)劃有最優(yōu)解，則必能在可行域凸多邊形的頂點中得到。推廣之，對于有n個變量的線性規(guī)劃，其可行域是一個以超平面為邊界的凸多邊體。如果線性規(guī)劃有最優(yōu)解，則該最優(yōu)解一定能在凸多邊體的頂點中得到。圖2.1以上的結(jié)論對于求解線性規(guī)劃有重大的價值，因為原本我們要在可行域的無窮多個點中去尋找最優(yōu)解，現(xiàn)在根據(jù)結(jié)論我們只要在可行域的有限個頂點中尋找最優(yōu)解即可。2.2線性規(guī)劃解的標(biāo)準(zhǔn)形為了研

5、究方便，定義下列形式為線性規(guī)劃的標(biāo)準(zhǔn)形：min z = Y c x j j j=1s.t. a x = b , i = 1,2,., m（2.2）j=1Xj 0,j = 1,2,., n對于目標(biāo)函數(shù)，一律定義為求最小值，決策變量一律定義為非負(fù)變量，約束條件除變 量的非負(fù)條件之外，一律為等式約束。各種形式的線性規(guī)劃模型都可以化為標(biāo)準(zhǔn)形。1、若問題的目標(biāo)函數(shù)是求最大值max z = lcx，那么可以令：f = -z，把原問題=1化為在相同的約束條件下求最小值：min f，顯然，新問題和原問題是同解的。2、如果約束條件中有不等式約束：Ha x 0 ij j i i i j=1稱變量x：為松弛變量3、

6、如果約束條件中有不等式約束：ILa x b，則可以引進(jìn)一個新變量x，并用下ij j iij=1 面兩個約束條件來代替原有的不等式約束：乙 a x - x = b , x 0 ij j i i i稱變量x為剩余變量4、如果約束條件中出現(xiàn)x. h （h豐0），則可以引進(jìn)一個新變量y. = x .- h替代原 問題中的變量x,，于是，問題中原有的約束就化為七0。5、如果變量x的符號不受約束，則可以引進(jìn)兩個新變量y和y”，并以x = y- y”代j j j j j j入原問題的目標(biāo)函數(shù)和約束條件消去x，同時在約束條件中增加y 0, y” 0。j j j例2.1把線性規(guī)劃max z = x + xs.t

7、.2x + 3x 42 x 一 x = 3x 0化為標(biāo)準(zhǔn)形。解該題有四個地方與標(biāo)準(zhǔn)形不符，a.目標(biāo)函數(shù)是求最大值；b.決策變量x的符號沒有2約束；C.第一、第二約束條件為不等式。1、令：f = -z = -(x1 + x2)，求max z 改為求 min f2、令：x = x - x , where x 0, x 0 TOC o 1-5 h z 234343、對不等式約束條件分別引入為松弛變量x5和剩余變量x6，從而將原問題化為標(biāo)準(zhǔn)形:min f = -x - x + xs .t.2 x + 3 x 一 3 x + x = 61345x + 7 x 一 7 x 一 x = 413462x -x

8、 +x =3x . 0, j = 1,3, 4, 5, 62.3線性規(guī)劃解的基本定理觀察(2.1)式，其相應(yīng)的標(biāo)準(zhǔn)形為:min 一 2x - xs .t. 3 x 4 x x = 12x + 2 x x = 2x. 0, j = 1,2, 3,4它的可行域有四個頂點，在標(biāo)準(zhǔn)形的形式下所對應(yīng)的解為:(0, 0,12, 2) t ,(0, 3, 0, 8) t ,(堂,3,0,0) t ,(2, 0, 6, 0) t5 5四個頂點的共同之處是所對應(yīng)的變量值中均有兩個的坐標(biāo)為0。仔細(xì)分析后可知，作為 平面上凸多邊形的頂點必然是兩條邊界直線的交點。若邊界直線為坐標(biāo)軸，則相應(yīng)的一個坐 標(biāo)為0，若邊界直線

9、非坐標(biāo)軸，則化標(biāo)準(zhǔn)形時所引進(jìn)的松弛變量或剩余變量就應(yīng)為0，因此 在僅有兩個決策變量的線性規(guī)劃標(biāo)準(zhǔn)形的形式下，頂點所對應(yīng)的變量的值為0的個數(shù)不少于 兩個是一般規(guī)律。這里的變量可以是決策變量、松弛變量或剩余變量。我們利用代數(shù)的這個特征引入基本可行解這個概念來替代幾何意義上頂點這個名詞，并用以表述線性規(guī)劃的基本定理。線性規(guī)劃的標(biāo)準(zhǔn)形(2.2)用矩陣表示為：min z = CTxs .t. Ax = Bx 0(2.3)其中，C = (c , c ,., c )T, x = (x , x ,., x )T, 12n12nA = (a ), B = (b , b ,., b )tij m x n1 2m不妨設(shè)矩陣A的秩r(A) = m，即線性方程組Ax = B沒有多余的方程。于是線性規(guī)劃(2.2)的可行解就等價于求線性方程組Ax = B的非負(fù)解。線性方程組Ax = B有n個變量，且r(A) = m，因此當(dāng)Ax = B的一個解中非零分量都是線性無關(guān)時，則非零分量的個數(shù)不會超過r(A) = m，即零分量的個數(shù)不少于n-m。線性方程組Ax = B中對應(yīng)非零分量呈線性無關(guān)的解就是式(2.3)的基本解；其中非負(fù) 基本解稱為基本可行