【文章內(nèi)容簡介】 兩點 表示為 則稱 x 為 S 的一個極點（或頂點）。 ,nS R x S x S?? 如 果 不 能 用 中 不 同 的(1 ) ( 2 )xx， ( 1 ) ( 2 )( 1 ) ( 0 1 )x x x? ? ?? ? ? ? ?定理 4 LP 問題的可行解集 ? ?,0D x A x b x? ? ? 是 凸 集 。 第一章 線性規(guī)劃及單純形法 定理 5 設 D 為 LP 問題的可行解集， ，則 x 是 D 的極點的充分必要條件是 x 為 LP 問題的基可行解。 xD?prove 推論 1 如果 LP 問題的可行解集非空，則極點集合也 一定非空，且極點的個數(shù)是有限的 。 推論 2 如果 LP 問題有最優(yōu)解，則一定可在可行解集 D 的極點上達到。 定理 6 設 LP 問題在多個極點 x(1),x(2),…x (k) 處取到最優(yōu) 解，則它們的凸組合，即 * ( )110 , 1kkii i iiixx ? ? ???? ? ???也是 LP 問題的最優(yōu)解 . （此時，該 LP 問題有無窮多最優(yōu)解） 167。 3 線性規(guī)劃問題解的基本性質(zhì) Note: 如何判斷 LP 問題有最優(yōu)解； 計算復雜性問題。 設有一個 50個變量、 20個約束等式的 LP 問題，則 最多可能有 個基。 20 135050 ! 1020 ! 30 !C ? ? ?即約 150萬年 如果計算一個基可行解只需要 1 秒，那么計算所有 的基可行解需要： 13 6 360024365 180。 ?180。 180。180。 （ 年 ） 167。 4 單純形法的基本原理 單純形法 （ Simplex Method） 是 1947年由 . Dantzig 提出，是解 LP 問題最有效的算法之一， 且已成為整數(shù)規(guī)劃和非線性規(guī)劃某些算法的基礎 。 基本思路： 基于 LP 問題的標準形式，先設法找到一個基可 行解，判斷它是否是最優(yōu)解，如果是則停止計算；否 則，則轉(zhuǎn)換到相鄰的目標函數(shù)值不減的一個基可行解 . （兩個基可行解相鄰是指它們之間僅有一個基變量不 相同）。 第一章 線性規(guī)劃及單純形法 單純形法引例 首先，化原問 題為標準形式： ? ?1 2 3 41 3 1 0 , , ,1 1 0 1A p p p p????????x3, x4 是基變量 . ? ?34,B p p? 是 可 行 基 ，基變量用非基變量表示： x3 = 60 x1 3x2 x4 = 40 x1 x2 代入目標函數(shù)： z =15 x1+25 x2 令非基變量 x1= x2=0 z=0 基可行解 x(0)=(0,0,60,40)T 是最優(yōu)解嗎？ max z = 15x1 +25x2 . x1 + 3x2 ≤ 60 x1 + x2 ≤ 40 x1， x2 ≥ 0 max z = 15x1 + 25x2 + 0x3 + 0x4 . x1 + 3x2 + x3 = 60 x1 + x2 + x4=40 x1， x2 , x3, x4≥ 0 167。 4 單純形法的基本原理 z =15 x1+25 x2 x3 = 60 x1 3x2 x4 = 40 x1 x2 因為 x2 的系數(shù)大，所以 x2 換入基變量。 x3 = 60 3x2 ≥ 0 x4 = 40 x2 ≥ 0 誰換出？ 如果 x4 換出，則 x2 = 40， x3 = 60， 不可行 。 如果是“ +”會怎樣？ 如果 x3 換出，則 x2 = 20， x4 = 20。 260 40m in , 2031x????????取最小比值法則 所以 x3 換出。 基變量用非基變量表示： 2 1 34 1 3112033212033x x xx x? ? ?? ? ?代入目標函數(shù)： z =500+20/3 x1 25/3 x3 令非基變量 x1= x3=0 z=500 基可行解 x(1)=(0,20,0,20)T 大于零！ 第一章 線性規(guī)劃及單純形法 132 1 34 1 320 2550033112033212033z x xx x xx x x? ? ?? ? ?? ? ?因為 x1 的系數(shù)大，所以 x1 換入基變量。 120 20m in , 301233x????????????因所以 x4 換出。 基變量用非基變量表示： 1 3 42 3 4313022111022x x xx x x? ? ?? ? ?代入目標函數(shù)： z =700 – 5 x3 – 10 x4 令非基變量 x3= x4=0 z=700 基可行解 x(2)=(30,10,0,0)T 因為非基變量的系數(shù)都小于零， 所以 x(2)=(30,10,0,0)T 是最優(yōu)解 zmax=700 167。 4 單純形法的基本原理 目標函數(shù)用非基變量表示時，非基變量的系數(shù) 稱為 檢驗數(shù) (40,0) (0,0) (0,20) A B C (30,10) 123 60xx??40??O L1 L2 Z=250 x2 x1 x(0)=(0,0,60,40)T z=0 x(1)=(0,20,0,20)T z=500 x(2)=(30,10,0,0)T z=700 第一章 線性規(guī)劃及單純形法 單純形法的基本原理 ? ?m a x ( 1 ). . ( 2)0 ( 3 )ij mnz c xs t Ax bxA a A m????=秩 （ ） =1111m a x ( ) ( 1 ). . ( 2 )0 , 0 ( 3 )B N B NBNBNz c B b c c B N x as t x B N x B b ax x a????? ? ?????稱 (1a)(2a)(3a)為 LP問題對應于 基 B 的典則形式（典式） . Ax = b ? BNB x Nx b??基變量用非基變量表示： 11BNx B Nx B b???x B b B Nx??代入目標函數(shù)： ? ?1 1 1 1,( ) ( )BB N B B N NNB N N N B N B Nxz c x c c c x c xxc B b B N x c x c B b c c B N x? ? ? ???? ? ? ? ?????? ? ? ? ? ? 167。 4 單純形法的基本原理 如果記 ( 0 ) 1Bz c B b?? 112( , , , )N m m n N Bc c B N? ? ? ? ???? ? ?39。39。1 1 139。 1 39。 39。139。39。1( , , )mnmnm m m naaN B N p paa????????? ? ?????39。 1 39。 39。1( , , ) Tmb B b b b???則典式 (1a)(2a)(3a) 可寫成 ( 0 )1 1 2 239。 39。 39。 39。1 1 1 1 1 2 2 1 139。 39。 39。 39。2 2 1 1 2 2 2 2 239。 39。 39。 39。1 1 2 2m a x..0 ( 1 , 2 , , )m m m m n nm m m m n nm m m m n nm m m m m m m m n n mjz z x x xs t x a x a x a x bx a x a x a x bx a x a x a x bx j n? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ???139。j j B jj B jc c B pc c p? ????? 第一章 線性規(guī)劃及單純形法 ( 0 )139。39。1m a x ( 1 ). . ( 1 , 2 , , ) ( 2 )0 ( 1 , 2 , , ) ( 3 )njjjmni ij j ijmjz z x bs t x a x b i m bx j n b???????? ? ?????定理 7 在 LP 問題 的典式 (1b) ～ (3b)中， 如果有 0 ( 1 , 2 , , )j j m m n? ? ? ? ?則對應于基 B 的基可行解 ( 0 ) 39。 39。 39。12( , , , , 0 , , 0) Tmx b b b?是 LP 問題的最優(yōu)解，記為 39。 39。 39。12( , , , , 0 , , 0) Tmx b b b? ?相應的目標函數(shù)最優(yōu)值 z*=z(0) 此時，基 B稱 為最優(yōu)基 ? ? ? ?11, 0 ,B N B N Bc c B A c c B N? ? ? ??? ? ? ? ? 167。 4 單純形法的基本原理 定理 8 在 LP 問題 的典式 (1b) ～ (3b)中， ( 0 )139。39。1m a x ( 1 ). . ( 1 , 2 , , ) ( 2 )0 ( 1 , 2 , , ) ( 3 )njjjmni ij j ijmjz z x bs t x a x b i m bx j n b???????? ? ?????? ? ? ?0 39。39。1 , , , 0 , , 0 Tmx b b?是對應于基 B 的一個基可行解，如果滿足下列條件： (1)有某個非基變量 xk 的檢驗數(shù) σk 0 (m+1 ≤ k ≤n)。 (2)aik(i=1,2,…,m) 不全小于或等于零，即至少有一個 aik0 (i=1,2,…,m) 。 (3) 0 (i=1,2,…,m) , 即 x(0) 為非退化的基可行解。 39。ib則從 x(0)出發(fā)，一定能找到一個新的基可行解 ? ?( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 0 )12 , , , .Tnx x x x c x c x? 使 得 第一章 線性規(guī)劃及單純形法 定理 9 在 LP 問題的典式 (1b) ～ (3b)中，如果檢驗 數(shù)滿足最優(yōu)準則 σj ≤ 0 ( j = m+1 ,…,n ) ， 且其中有一 個 σk = 0 ( m+1 ≤ k ≤n )， 則該 LP 問題有無窮多個 最優(yōu)解。 這在應用中很有價值 定理 10 在 LP 問題的典式 (1b) ～ (3b)中，如果有某 個非基變量的檢驗數(shù) σk 0 ( m+1 ≤ k ≤n )， 且有 39。39。0 ( 1 , 2 , , ) 0ik ka i m p? ? ?即則該 LP 問題解無界（無最優(yōu)解）。 167。 5 單純形法的