【文章內容簡介】 .. ... ... ......mm m m ma a aa a a????????? 稱 Pj ( j = 1,2,, m )為基向量 , 線性規(guī)劃的基本概念 矩陣 B 是由 m 個線性無關的列向量組成 , de t 0B ?則 A中 稱 B是 不失一般性 ,可假設 : 12= ( , , ..., )mP P PB與基向量 Pj 相對應的變量 xj ( j = 1,2,, m )為基變量 , 其他的變量稱為非基變量。 為了進一步討論線性規(guī)劃的解 , 研究 Ax=b的求解問題。 設 A 的秩為 m , 則 B=(P1, P2, , Pm)是一個基， 11 1 1 1 11111... ... ... ... ... ...m m nm m nm m m m m m na a a ax x b x xa a a a???? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?線性規(guī)劃的基本概念 因 m n,所以它有無窮多個解。 11mnj j j jj j mP x b P x? ? ?????即 xB = ( x1, x2, , xm )T, 則 Ax=b 可改寫為： 不妨假設 A =(P1, P2, , Pn)中前 m 列線性無關， 設 xB 是對應于基 B的基變量 , +j j j jj j mP x P x b? ? ??()5. 基本解： 若令 ()式中的非基變量 xm+1 = = xn = 0 , 求出一個解 x = ( x1, x2, , xm , 0, , 0 )T ,這個解的非 0分量的數目不大于方程個數 m ,稱 x 為基本解。 線性規(guī)劃的基本概念 當基本解中有一個或者一個以上的基變量是 0時，稱這個基本解是 退化的基本解 ；否則稱為 非退化的基本解 。 11( )mnj j j jj j mP x b P x? ? ?????6. 基本可行解 : 滿足非負約束條件的基本解稱為基本可行解 . 基本可行解的非 0分量的數目不大于 m , 都是非負的。 7. 可行基 : 基本可行解對應的基稱為可行基 . 約束方程組 Ax=b基本可行解的數目 以上提到的幾種解的概念 ,可用如下圖來表示 : 基解 可行解 基 本 可行解 線性規(guī)劃的基本概念 至多是 個 . 基本可行解的個數不超過基本解的個數， mnC mnC基本解至多 個 =？例 求 解 : 約束方程的系數矩陣 為 2 5矩陣 r(A)=2， 2階子矩陣有 10個，其中基矩陣只有 9個，即 線性規(guī)劃的基本概念 1 2 31 2 3 41 2 3 5425310 6 2 20 , 1 , , 5jm in z x x xx x x xx x x xxj? ? ?? ? ? ? ??? ? ? ? ??? ???5 1 1 1 010 6 2 0 1A?????????345 0 1 110 1 6 0BB? ? ? ???? ? ? ??? ? ? ?的所有基矩陣和基本解。 565 1 1 010 0 2 1?? ? ? ?? ? ? ??? ? ? ?9 1001B ??? ????125 1 1 110 6 6 2?? ? ? ?? ? ? ??? ? ? ?781 1 1 02 0 6 1?? ? ? ?? ? ? ?? ? ? ?線性規(guī)劃的基本概念 1 2 31 2 3 41 2 3 5425310 6 2 20 , 1 , , 5jm in z x x xx x x xx x x xxj? ? ?? ? ? ? ??? ? ? ? ??? ???5 1 1 1 010 6 2 0 1A?????????5 5110 0B ??? ?????取定基矩陣 , 相應的基變量是 x1, x4 ,非基變 量是 x2, x3, x5, 在約束條件中令非基變量 x2, x3, x5 都取 0，從中解出基變量 從而得到一個基本解 141 ,45xx? ? ? ，1 , 0 , 0 , 4 , 05Tx ????????不是可行解 55110 0B????????不是可行基 線性規(guī)劃的基本概念 1 2 31 2 3 41 2 3 5425310 6 2 20 , 1 , , 5jm in z x x xx x x xx x x xxj? ? ?? ? ? ? ??? ? ? ? ??? ???5 1 1 1 010 6 2 0 1A?????????取定基矩陣 相應的基變量是 x4, x5 ,非基變 量是 x1, x2, x3, 在約束條件中令非基變量 x1, x2, x3, 都取 0，從中解出基變量 從而得到一個基本解 453 , 2xx?? ，? ?0 , 0 , 0 3 , 2Tx ? ，可行解 是可行基 . 91001B???????91001B???????基本可行解 ? ?0 , 0 , 0 3 , 2 Tx ，對于其他基矩陣對應的基本解，可以類似的求出。 閉半空間： 稱 為正閉半空間， 稱 為負閉半空間。 H+和 H統(tǒng)稱為閉半空間。 多面體或多面凸集： 有限個閉半空間的交 多胞形或多面凸體： 有界且非空的多面體。 線性規(guī)劃的基本性質 閉半空間是凸的 { : }nTH x R c x ?? ? ? ?: }c x ?? ?{ : }nS x R Ax b? ? ?多胞形 極點： 設 S是凸集， , 不存在 S 中的另外兩個點 和 ， 及 ，使 , 則稱 x是凸集 S的 極點，或稱頂點。 定理： 設 ,秩為 m, 且 則 x為凸集 的頂點 的充要條件是 R是凸集 線性規(guī)劃的基本性質 (0 ,1)? ? 12( 1 )x x x??? ? ?xS1x2x ()ij m nAa ?? ,mn? 12( , , ..., ) Tmb b b b? ，{ , 0 }R x Ax b x? ? ?,0A x b x??闡明了基本可行解與可行域的頂點之間一一對應的關系 ( , , ..., ) Tnx x x x? ， x 為 的一個基本可行解。 推論 1： 若線性規(guī)劃的可行域 R = { x |Ax = b , x ? 0 } 是非空 的， 推論 2: 若線性規(guī)劃存在有限的最優(yōu)解， 推論 3: 線性規(guī)劃的可行域 R有有限多個頂點 。 線性規(guī)劃的基本性質 定理 (線性規(guī)劃的基本定理 ) (1) 若線性規(guī)劃存在可行解 ,則一定存在基本可行解 。 (2) 若線性規(guī)劃存在最優(yōu)解 ,則一定存在最優(yōu)的 。 基本可行解 R的頂點 ?基本可行解 R的頂點 ?基本可行解最多 個 mnC若線性規(guī)劃存在最優(yōu)解 ,必定在某頂點取到 可行域 R的頂點 基本可行解 則它至少有一個頂點。 R 的頂點是有限最優(yōu)解。 則至少存在一個 根據以上討論得到如下的結論： 結論 1： 線性規(guī)劃的可行域是凸集 ,它 可以是有界的 ,也可以是無界的區(qū)域 。僅有有限個頂點 (至多 )。 結論 2： 線性規(guī)劃的每一個基 本 可行解對應于可行域的一個頂點 .若線性規(guī)劃有最優(yōu)解 ,必定可在某頂點取到。 結論 3： 如果一個線性規(guī)劃存在多個最優(yōu)解 ,那么至少有兩個相鄰的頂點處是線性規(guī)劃的最優(yōu)解。 結論 4： 如果有一個頂點處可行解的目標值比其它相鄰頂點的可行解的目標值小的話，那么它就是最優(yōu)解。 線性規(guī)劃的基本性質 { , 0 }R x Ax b x? ? ?mnC 可行域的頂點個數是有限的 (不超過 Cnm 個 )，采用“枚舉法”找出所有基 本 可行解，然后一一比較它們的目標函數值的大小，最終可以找到最優(yōu)解。 但當 m、 n的數目相當大時，這種辦法實際上是行不通的。 線性規(guī)劃的基本性質 因此，我們還要繼續(xù)討論一種方法，通過逐步迭代保證能 逐步改進并最終求出最優(yōu)解。 ? 1947年 , 美國學者 Gee Dantzig(丹齊格 ) 提出了求解線性規(guī)劃的單純形法 , 為線性規(guī)劃的推廣奠定了基礎。 ? 從可行域的 一個頂點 (基本可行解 )開始 , 轉移到另一個頂點 (另一個基本可行解 )。 轉移的條件是 使目標函數值得到改善 (逐步變優(yōu) ) 當目標函數達到最優(yōu)值時 , 也就得到了最優(yōu)解。 基本思想 單純形法 對于標準線性規(guī)劃問題 (簡寫為 LP): m in..0Tf c xs t Ax bx???A = ( aij)m?n , rank(A)= m 12( , , ..., )nA P P P? ，單純形法的基本原理 ? ?1 2 1, ( , , ... , , ..., )m m nA B N P P P P P??? ，將 A 分解成 [B,N],使 B為基矩陣 , N為非基矩陣， 10???? ????Bbx BNxxx???????， 設 求基本解 ? ?, B BNNxAx B N Bx N xx??? ? ????? ，1 ,??Bx B b是基本可行解。 令 xN=0 ?b是基本解。 1 0,???Bx B b若 10???????Bb(0) ?x相應的目標函數值為 1( 0 )0Bbx ????????，( 0 )0 Tf c x?記 現在分析如何從一個基本可行解 x(0)出發(fā)，求一個改進的基本可行解 x(1) 。 單純形法的基本原理 假設已知一個基本可行解 x(0)， 11,0T T TB N BBbc c c B b? ??????????? ?? ，,??? ????BNccc 若初始基本可行解 x(0)不是最優(yōu)解，找一個新的基本可行解。 1 2 1 2( , , ..., ) , ( , , ..., ) .???? TTB m N m m nc c c c c c c c任意可行解 x x ?形式 找到基本可行解并使 ?fx(1) 找改進的基本可行解： 設 x是任意可行解， 目標函數 f 在點 x 處的值為 Tf c x?單純形法的基本原理 11()TTB N N Nc B b B N x c x??? ? ?0f?11()TTTB B N Nc B b c B N c x??? ? ?()NB B j j jjRc B b c B p c x?? ? ??11BNx B b B N x????? ?,??? ? ?????BBNNxAx B N Bx N xx, BT T T TB N B B N N