1、第二章線性規劃的基本性質在生產、經濟、技術領域，許多工程技術和管理問題實際上是線性的，或者是可以用線 性函數近似表達的，所以線性規劃的研究是很有意義的。而且對線性規劃的理論的研究要比 非線性規劃領域成熟的多。掌握線性規劃的基本理論和求解方法是本課程最重要的目標之 一。2.1線性規劃解的幾何特征借助于平面圖形可以直觀地了解線性規劃解的幾何特征，具體介紹一個實例。設有兩個決策變量和的線性規劃：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所示，它是一個由四條直線組成的凸多邊形。任何一個含兩個變量 的線性規劃的可行域都是以直線為邊的凸多邊形。觀察目標函數：f(x) = - 2 x1 - x2對于任一給定的實數a，方程-2 x1 - x2 =a表示一條直線，稱為f的等值線。變動a 可以得到一族相互平行的直線。把f的等值線向函數值a減小的方向移動，它與凸多邊形K 的最后一個交點即為的最優解。最優解是凸多邊形的一個頂點

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

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

5、究方便，定義下列形式為線性規劃的標準形：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對于目標函數，一律定義為求最小值，決策變量一律定義為非負變量，約束條件除變 量的非負條件之外，一律為等式約束。各種形式的線性規劃模型都可以化為標準形。1、若問題的目標函數是求最大值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，則可以引進一個新變量x，并用下ij j iij=1 面兩個約束條件來代替原有的不等式約束：乙 a x - x = b , x 0 ij j i i i稱變量x為剩余變量4、如果約束條件中出現x. h （h豐0），則可以引進一個新變量y. = x .- h替代原 問題中的變量x,，于是，問題中原有的約束就化為七0。5、如果變量x的符號不受約束，則可以引進兩個新變量y和y”，并以x = y- y”代j j j j j j入原問題的目標函數和約束條件消去x，同時在約束條件中增加y 0, y” 0。j j j例2.1把線性規劃max z = x + xs.t

7、.2x + 3x 42 x 一 x = 3x 0化為標準形。解該題有四個地方與標準形不符，a.目標函數是求最大值；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，從而將原問題化為標準形: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線性規劃解的基本定理觀察(2.1)式，其相應的標準形為:min 一 2x - xs .t. 3 x 4 x x = 12x + 2 x x = 2x. 0, j = 1,2, 3,4它的可行域有四個頂點，在標準形的形式下所對應的解為:(0, 0,12, 2) t ,(0, 3, 0, 8) t ,(堂,3,0,0) t ,(2, 0, 6, 0) t5 5四個頂點的共同之處是所對應的變量值中均有兩個的坐標為0。仔細分析后可知，作為 平面上凸多邊形的頂點必然是兩條邊界直線的交點。若邊界直線為坐標軸，則相應的一個坐 標為0，若邊界直線

9、非坐標軸，則化標準形時所引進的松弛變量或剩余變量就應為0，因此 在僅有兩個決策變量的線性規劃標準形的形式下，頂點所對應的變量的值為0的個數不少于 兩個是一般規律。這里的變量可以是決策變量、松弛變量或剩余變量。我們利用代數的這個特征引入基本可行解這個概念來替代幾何意義上頂點這個名詞，并用以表述線性規劃的基本定理。線性規劃的標準形(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不妨設矩陣A的秩r(A) = m，即線性方程組Ax = B沒有多余的方程。于是線性規劃(2.2)的可行解就等價于求線性方程組Ax = B的非負解。線性方程組Ax = B有n個變量，且r(A) = m，因此當Ax = B的一個解中非零分量都是線性無關時，則非零分量的個數不會超過r(A) = m，即零分量的個數不少于n-m。線性方程組Ax = B中對應非零分量呈線性無關的解就是式(2.3)的基本解；其中非負 基本解稱為基本可行