第一章線性規(guī)劃基本性質(zhì)

1、123如何合理使用有限的人力，物力和資金，如何合理使用有限的人力，物力和資金，使得收到最好的經(jīng)濟效益。使得收到最好的經(jīng)濟效益。如何合理使用有限的人力，物力和資金，如何合理使用有限的人力，物力和資金，以達到最經(jīng)濟的方式，完成生產(chǎn)計劃的要以達到最經(jīng)濟的方式，完成生產(chǎn)計劃的要求。求。4 56 78910 1112比例性假定：決策變量變化引起的目標函比例性假定：決策變量變化引起的目標函數(shù)的改變量和決策變量的改變量成比例，同數(shù)的改變量和決策變量的改變量成比例，同樣，每個決策變量的變化引起約束方程左端樣，每個決策變量的變化引起約束方程左端值的改變量和該變量的改變量成比例。值的改變量和該變量的改變量成比例。

2、1314連續(xù)性假定：線性規(guī)劃問題中的決策變量連續(xù)性假定：線性規(guī)劃問題中的決策變量應(yīng)取連續(xù)值。應(yīng)取連續(xù)值。1516數(shù)學模型的標準型數(shù)學模型的標準型v求解目標函數(shù)的最小值求解目標函數(shù)的最小值v約束條件為等式約束約束條件為等式約束( (右端值非負）右端值非負）v變量非負變量非負171819202122若目標函數(shù)是求最大值若目標函數(shù)是求最大值 MaxS = CX 令令 S= - S, 則則 Min S= - CX23若目標函數(shù)是求最大若目標函數(shù)是求最大 值值 Max S = CX 令令 S= - S, 則則 Min S= - CX242526若約束條件右面的某一常數(shù)項若約束條件右面的某一常數(shù)項 bi0

3、這時只要在這時只要在bi相對應(yīng)的約束方程兩邊乘上相對應(yīng)的約束方程兩邊乘上-1。27若約束條件右面的某一常數(shù)項若約束條件右面的某一常數(shù)項 bi=0 令令xj= xj- xj”（可正可負）（可正可負）28:2930313233（1）滿足約束條件的變量的值，稱）滿足約束條件的變量的值，稱為可行解。為可行解。3435x2504030201010203040 x136x2504030201010203040 x137x2504030201010203040 x12x1+x2 504x1+3x2 12038x2504030201010203040 x1O（0，0）Q1（25，0）Q2（15，20）Q3（0

4、，40）39x2504030201010203040 x140 x2504030201010203040 x141x2504030201010203040 x1Q2（15，20）4243滿足約束條件的可行域一般都滿足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實可以構(gòu)成凸多邊形。這一事實可以推廣到更多變量的場合。推廣到更多變量的場合。44；45最優(yōu)解是唯一解最優(yōu)解是唯一解；46x2504030201010203040 x147x2504030201010203040 x1Q1（25，0）Q2（15，20）4849x2504030201010203040 x150515253545556 滿足約束

5、條件（滿足約束條件（1-10）的）的X，稱為，稱為 線性規(guī)劃問題的解。線性規(guī)劃問題的解。57 滿足約束條件（滿足約束條件（1-10）的）的X，稱為，稱為 線性規(guī)劃問題的解。線性規(guī)劃問題的解。 滿足約束條件（滿足約束條件（1-10）與（）與（1-11） 的的X，稱為線性規(guī)劃的問題可行解。，稱為線性規(guī)劃的問題可行解。5859 設(shè)設(shè)r(A)=m,并且并且B是是A的的m 階非奇異階非奇異 的子矩陣（的子矩陣（det(B)0),則稱矩陣則稱矩陣 B為線性規(guī)劃問題的一個基。為線性規(guī)劃問題的一個基。60 設(shè)設(shè)r(A)=m,并且并且B是是A的的m 階非奇異階非奇異 的子矩陣（的子矩陣（det(B)0),則稱矩

6、陣則稱矩陣 B為線性規(guī)劃問題的一個基。為線性規(guī)劃問題的一個基。 矩陣矩陣B=（P1，P2.Pm) ，其列向量，其列向量 Pj稱為對應(yīng)基稱為對應(yīng)基B的基向量。的基向量。6162 對于某一特定的基對于某一特定的基B，非基變量取，非基變量取 0值的解，稱為基本解。值的解，稱為基本解。63 對于某一特定的基對于某一特定的基B，非基變量取，非基變量取 0值的解，稱為基本解。值的解，稱為基本解。 滿足非負約束條件的基本解，稱滿足非負約束條件的基本解，稱 為基本可行解。為基本可行解。64656667686970717273747576 7778X7980818283 。848586 若若87 若若ZCXAX

7、bXmin0 證：證：XD XDXX(1)(2)(1)(2), AXb AXbXX(1)(2)(1)(2),0,0 (1)(2)(1)(2)(1-)01X, XX= X+X,令令線線段段上上任任意意一一點點為為 AX=AX+X(1)(2)1- 則則 = AX+AXAX(1)(2)(2)-= bX0 且且 ，XDD 即即 ， 由由定定義義， 為為凸凸集集。88 89 證：證：必必要要性性XX為為基基本本可可行行解解的的正正分分量量是是各各個個基基變變量量 基基變變量量對對應(yīng)應(yīng)基基向向量量 線線性性無無關(guān)關(guān)90 證：證：充充分分性性12kXkP ,PP,.不不妨妨設(shè)設(shè)可可行行解解 的的正正分分量量

8、為為前前 個個， 對對應(yīng)應(yīng)的的線線性性無無關(guān)關(guān)列列向向量量為為kAm 則則 的的秩秩 ，km 如如 ， 由由基基的的定定義義可可得得結(jié)結(jié)論論；kmn-km-k如如 ， 必必可可從從其其余余的的個個列列向向量量中中取取出出個個，構(gòu)構(gòu)成成最最大大線線性性無無關(guān)關(guān)組組，即即為為一一組組基基，對對應(yīng)應(yīng)的的解解為為基基本本可可行行解解。91 92證：證：TmXx xxD12(,0,0) 假假設(shè)設(shè) 是是一一個個基基本本可可行行解解，但但不不是是可可行行域域 的的頂頂點點，YD,ZD, YZ ,X= Y+ 1Z( -) 則則 （） 使使得得，0 01 1YZn-m由由上上式式， 的的后后個個分分量量為為0

9、0，mmjjjjjjP ybP zb11, mjjjjP yz10, 相相減減，（）jjyz0, 不不全全為為 ，由由線線性性相相關(guān)關(guān)定定義義可可知知X,正正分分量量對對應(yīng)應(yīng)的的系系數(shù)數(shù)列列向向量量線線性性相相關(guān)關(guān)X1,由由引引理理不不是是基基本本可可行行解解， 矛矛盾盾！93證：證：XD假假設(shè)設(shè) 是是可可行行域域 的的頂頂點點，但但不不是是一一個個基基本本可可行行解解，kjjjP xb1, kkjjjjjjjjP xbP xb110, 有有， 得得（）（）X=Y+ZY, Z,2211,00 則則且且 充充分分小小時時，有有X不不是是可可行行域域的的頂頂點點， 矛矛盾盾！XkX設(shè)設(shè) 的的前前

10、個個分分量量為為正正，其其余余為為0 0，是是可可行行解解，kjjjjP10, 由由引引理理1 1， 一一組組不不全全為為0 0的的數(shù)數(shù)，TkkTkkY = xxx Zxxx11221122(,(, 令令) ), ,( () ), , （）, ,0 0, ,0 0) ), ,( () ), , （）, ,0 0, ,0 0X即即可可用用可可行行域域內(nèi)內(nèi)不不同同兩兩點點的的凸凸組組合合表表示示，949596979899100101 102 證：證：2kX,X,XXZ(1)( )( )(0) 設(shè)設(shè)是是可可行行域域的的頂頂點點，且且最最優(yōu)優(yōu)解解在在可可行行點點處處達達到到最最優(yōu)優(yōu)值值，ZCX(0) = =k2kkiiiXXXXX(0)(0)(1)( )( )12101 由由引引理理2 2，假假設(shè)設(shè)不不是是可可行行域域的的頂頂點點則則，