【正文】 形法 LP問題圖解法的基本步驟 ： 在平面上建立直角坐標系； 圖示約束條件，確定可行域和頂點坐標； 圖示目標函數(shù)（等值線）和移動方向； 尋找最優(yōu)解。 167。 2 線性規(guī)劃問題的圖解法 max z =3x1 + . x1 + ≥ x1 ≤ x1 + ≤ x1 ≥ x1 ， x2 ≥ 0 x1 x2 o x1 x2 = x1 + x2= x1 + x2 = （ ,2） D 0=3 x1 + x2 max Z min Z （ ,4） = 3 x1 + x2 可行域 x1 x2 = (0,2) (,0) 綠色線段上的所有點 都是最優(yōu)解 ,即有無窮多最優(yōu)解。 Zman= 第一章 線性規(guī)劃及單純形法 max z = 2x1 + 2x2 . 2x1 – x2 ≥ 2 x1 + 4x2≤ 4 x1， x2 ≥ 0 1222xx??44? ? ?O A (１ ,0) x1 x2 Note: 可行域為無界區(qū)域， 目標函數(shù)值可無限 增大，即解無界。 稱為無最優(yōu)解 。 可行域為無界區(qū)域一定無最優(yōu)解嗎？ 167。 2 線性規(guī)劃問題的圖解法 由以上兩例分析可得如下重要結論： LP 問題從解的角度可分為： ⑴ 有可行解 ⑵ 無可行解 a. 有唯一最優(yōu)解 b. b. 有無窮多最優(yōu)解 c. C. 無最優(yōu)解 LP 問題若有最優(yōu)解，必在可行域的某個頂點上取 到；若有兩個頂點上同時取到，則這兩點的連線上 任一點都是最優(yōu)解。 167。 2 線性規(guī)劃問題的圖解法 圖解法優(yōu)點： 直觀、易掌握。有助于了解解的結構。 圖解法缺點： 只能解決低維問題，對高維無能為力。 167。 3 線性規(guī)劃問題解的基本性質 討論如下 LP 問題： ? ?m a x ( 1 ). . 20 ( 3 )z c xs t Ax bx???? ?12, , , nc c c c? ? ? 價 值 向 量? ?12, , , Tnx x x x? ? ?? ?12, , , , 0Tmib b b b b? ? ? ? 右 端 向 量11 12 121 22 2nnm m m na a aa a aAa a a????? ? ?????其中 系數(shù)矩陣 決策向量 假設 A 的秩為 m , 且只討論 m n 的情 形。 什么意思？ 為什么？ 第一章 線性規(guī)劃及單純形法 定義 3 在上述 LP 問題中，約束方程組 （ 2） 的系數(shù) 矩陣 A 的任意一個 m m 階的非奇異的子方陣 B （ 即 |B|≠0）， 稱為 LP 問題的一個基陣或基 。 ? ?11 1121, , ,mmm m maaB p p paa??????????稱 pi (i=1,2,…,m) 為基向量 。 xi (i=1,2,…,m) 為基 變量； xj (j= m+1,…,n) 為 非 基 變量 pj (j= m+1,…,n) 為 非 基向量 。 記： ? ?1 1 1112, , ,mnm m m nm m naaNaap p p??????????????則 A = ( B, N ) 167。 3 線性規(guī)劃問題解的基本性質 A = ( B, N ) xB= (x1,…,xm)T , xN =(xm+1,…,xn)T 則 BNxxx???????, 代入約束方程 （ 2），得 ? ? .BNxB N bx?? ?????? BnB x Nx b???? 自由變量 （獨立變量） 令 0Nx ? 1Bx B b?? 11BNx B b B Nx?????1( 4)0Bbx ????????稱（ 4）為相應于基 B 的基本解 第一章 線性規(guī)劃及單純形法 1( 4)0Bbx ????????是可行解嗎？ max z’ = x12x2+3x4 3x5 . x1+x2+x4x5+x6=7 x1x2+x4x5x7=2 3x1x22x4+2x5=5 x1,x2,x4,x5,x6,x7≥0 ?1 1 1 1 1 01 1 1 1 0 13 1 2 2 0 0A?????? ? ? ?????令 x1=x2=x4=0 T5 19 9得 一 基 本 解 x=(0,0,0, , , ) 2 2 2 如果 B1b ≥ 0，則 稱（ 4）為相應于基 B 的基可行 解，此時的基 B 稱為可行基。 167。 3 線性規(guī)劃問題解的基本性質 基本解唯一嗎？ 最多有多少？ mnn!最 多 有 C = 種m!(nm)!Rn 非可行解 基 可行解 可 基解 行 解 稱它是非退化的解；反之 ， 如果有一個基變量也取 零值 ， 則稱它是退化的解 。 一個 LP問題 ， 如果它的 所有基可行解都是非退化的就稱該是非退化的 ， 否 則就稱它是退化的 。 定義 4 在 LP問題的一個 基可行解中 ， 如果它的所 有的基變量都取正值 ， 則 第一章 線性規(guī)劃及單純形法 LP 問題解的基本性質 定理 1 設 x 是 LP 問題的可行解 (1) 若 x = 0， 則它一定是基可行解； (2) 若 x≠0， 則 x 是基可行解的充要條件是它的非零分 量所對應的列向量線性無關 。 Ax=0 定理 2 如果一個 LP 問題有可行解，則它必有基可行解。 定理 3 如果一個 LP 問題有最優(yōu)解，則必存在一個基可 行解是它的最優(yōu)解。 定理 定理 3 稱為 LP 問題的基本定理 定理 2 證明 向前 定理 3 證明 LP 問題是一個組合優(yōu)化問題 167。 3 線性規(guī)劃問題解的基本性質 定理 2 證明 設 x = (x1, x2,…, xn)T 是 LP 問題的一個可行解 ， 如果 x = 0， 則由定理 1知 ， 它是 LP 問題的一個基可行解 ， 定理成立 。 如果 x≠0， 不妨設 x 的前 k 個分量為非零分量 。 則有 x1p1 + x2p2 +…+xkpk = b， 及 x10, x20,…, xk 0， 分兩種情況討論： (1) 如果 p1, p2,…, pk 線性無關 ， 即 x 的 非零分量對應的列向量線 性無關 ， 則由定理 1知 ， 它是 LP 的一個基本可行解 ， 定理成立 。 (2) 如果 p1,p2,…,pk線性相關 ， 則必存在一組不全為零的數(shù) δ1,δ2, …,δk 使得 10 ( 5 )kjjjp???? 第一章 線性規(guī)劃及單純形法 假定有 δi≠0， =m in 0 ( 6)i iix??????????????( 2 )xx ????(1 ) ????12( , , , , 0 , , 0) Tk? ? ? ?? 0 ( 1 , 2 , ..., ) ( 7 )jjx j n??? ? ?( 1 ) ( 2 )0 , 0 ,??1 1 1()n n nj j j j j j jj j jx p x p p b?? ? ?? ? ?? ? ? ?? ? ?( 1 ) ( 2 ),A x b A x b??(1) (2),xx取 作 其中 由（ 6）式知，必有 即 又因為由（ 5）式知 故有， ，即 也是 LP的兩個可行解。 167。 3 線性規(guī)劃問題解的基本性質 再由 的取法知 ， 在式 (7) 的諸式中 ， 至少有一個等于零 ， 于是所作的可行解 中 ， 它的 非零分量的個數(shù)至少比 x 的減少 1， 如果這些非零分量所對應 的列向量線性無關 ， 則 為基可行解 ， 定理成立 。 否則 ， 可以從 出發(fā) ， 重復上述步驟 ， 再構造 一個新的可行解 ， 使它的非零分量的個數(shù)繼續(xù)減 少 。 這樣經(jīng)過有限次重復之后 ， 必可找到一個可行解 使它的非零分量對應的列向量線性無關 ， 故可行解 必為基可行解 。 證畢 。 (1 ) ( 2 )xx或(1 ) ( 2 )或(1 ) ( 2 )或( 3 ) ( 4 )或( ) ( 1 )ss?或( ) ( 1 )?或返回 0 ( 1 , 2 , ..., ) ( 7 )jjx j n??? ? ?? 167。 3 線性規(guī)劃問題解的基本性質 定理 3 證明 設 * * * *12( , , , )nx x x x?是 LP 的一個最優(yōu)解。 如果 x* 是基本解，則定理成立； 如果 x* 不是基本解，則由定理 2的證明過程可構造兩個可行解 ( 1 ) * ( 2 ) *x x x x? ? ? ?? ? ? ?它的非零分量的個數(shù)比 x* 的減少，且有 ， ( 1 ) * ( 2 ) *, ( 8 )c x c x c c x c x c? ? ? ?? ? ? ?又因為 x* 是最優(yōu)解，故有 * ( 1 ) * ( 2 ), ( 9)c x c x c x c x??由式（ 8）和（ 9）知，必有 ( 1 ) ( 2 ) *0,c c x c x c x?? ? ? ?故 即 x(1),x(2) 仍為最優(yōu)解。 如果 x(1)或 x(2) 是基可行解，則定理成立。 否則，按定理 2證明過程，可得基可行解 x(s)或 x(s+1),使得 ( ) * ( 1 ) *ssc x c x c x c x??? 或即 得基可行解 x(s)或 x(s+1)為最優(yōu)解。 返回 第一章 線性規(guī)劃及單純形法 LP 問題解的幾何意義 定義 5 設集合 是 n 維歐氏空間中的一個點 集，如果 及實數(shù) ( 1 ) ( 2 )( 1 )x x S??? ? ?nSR? ( 1 ) ( 2 )x x S??、? ?0 , 1? ? 都 有則稱 S 是一個凸集。 幾何意義：如果集合中任意兩點連線上的一切點都在 該集合中，則稱該集合為凸集。 Note: 空集和單點集也是凸集。 167。 3 線性規(guī)劃問題解的基本性質 定義 6 設 則稱 ()1, 0 , 1 , 2 , , , 1kiniiix R i k???? ? ? ??且 ，( 1 ) ( 2 ) ( )12 kkx x x x? ? ?? ? ? ?為點 的一個凸組合。 ( 1 ) ( 2 ) ( )kx x x， ， ，定義 7 設凸集