【正文】 1 找出初始可行基 ， 列初始單純形表 ,確定初 始基可行解； j?j39。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? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ??? c c1 c2 cm cm+1 cm+2 cB xB x1 x2 xm xm+1 xm+2 xn b c1 c2 cm x1 x2 xm 1 0 0 a’1m+1 a’1m+2 a’1n 0 1 0 a’2m+1 a’2m+2 a’2n 0 0 1 a’mm+1 a’mm+2 a’mn b’1 b’2 b’m 檢驗(yàn)數(shù) 0 0 0 z(0) n?2??1?? 第一章 線性規(guī)劃及單純形法 如何得到單純形表？ 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????? ? ????? c A b 檢驗(yàn)數(shù) 0 B1b cB B1b z0 I B1N B1b 0 σN 檢驗(yàn)數(shù) B N cB cN I B1N 0 cNcB B1N 167。 39。2 2 1 1 2 2 2 2 239。 39。1 1 1 1 1 2 2 1 139。 39。 5 單純形法的計(jì)算步驟 單純形表 ( 0 )1 1 2 239。0 ( 1 , 2 , , ) 0ik ka i m p? ? ?即則該 LP 問(wèn)題解無(wú)界（無(wú)最優(yōu)解）。 這在應(yīng)用中很有價(jià)值 定理 10 在 LP 問(wèn)題的典式 (1b) ～ (3b)中，如果有某 個(gè)非基變量的檢驗(yàn)數(shù) σk 0 ( m+1 ≤ k ≤n )， 且有 39。 39。 (2)aik(i=1,2,…,m) 不全小于或等于零，即至少有一個(gè) aik0 (i=1,2,…,m) 。39。39。12( , , , , 0 , , 0) Tmx b b b? ?相應(yīng)的目標(biāo)函數(shù)最優(yōu)值 z*=z(0) 此時(shí)，基 B稱 為最優(yōu)基 ? ? ? ?11, 0 ,B N B N Bc c B A c c B N? ? ? ??? ? ? ? ? 167。 39。 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 問(wèn)題 的典式 (1b) ～ (3b)中， 如果有 0 ( 1 , 2 , , )j j m m n? ? ? ? ?則對(duì)應(yīng)于基 B 的基可行解 ( 0 ) 39。j j B jj B jc c B pc c p? ????? 第一章 線性規(guī)劃及單純形法 ( 0 )139。 39。 39。 39。 39。 39。 39。 39。1( , , )mnmnm m m naaN B N p paa????????? ? ?????39。139。 1 39。39。 4 單純形法的基本原理 目標(biāo)函數(shù)用非基變量表示時(shí)，非基變量的系數(shù) 稱為 檢驗(yàn)數(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問(wèn)題對(duì)應(yīng)于 基 B 的典則形式（典式） . Ax = b ? BNB x Nx b??基變量用非基變量表示： 11BNx B Nx B b???x B b B Nx??代入目標(biāo)函數(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。 120 20m in , 301233x????????????因所以 x4 換出。 260 40m in , 2031x????????取最小比值法則 所以 x3 換出。 x3 = 60 3x2 ≥ 0 x4 = 40 x2 ≥ 0 誰(shuí)換出？ 如果 x4 換出，則 x2 = 40， x3 = 60， 不可行 。 第一章 線性規(guī)劃及單純形法 單純形法引例 首先，化原問(wèn) 題為標(biāo)準(zhǔn)形式： ? ?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 代入目標(biāo)函數(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 單純形法的基本原理 單純形法 （ Simplex Method） 是 1947年由 . Dantzig 提出，是解 LP 問(wèn)題最有效的算法之一， 且已成為整數(shù)規(guī)劃和非線性規(guī)劃某些算法的基礎(chǔ) 。180。 ?180。 設(shè)有一個(gè) 50個(gè)變量、 20個(gè)約束等式的 LP 問(wèn)題，則 最多可能有 個(gè)基。 定理 6 設(shè) LP 問(wèn)題在多個(gè)極點(diǎn) x(1),x(2),…x (k) 處取到最優(yōu) 解，則它們的凸組合，即 * ( )110 , 1kkii i iiixx ? ? ???? ? ???也是 LP 問(wèn)題的最優(yōu)解 . （此時(shí)，該 LP 問(wèn)題有無(wú)窮多最優(yōu)解） 167。 xD?prove 推論 1 如果 LP 問(wèn)題的可行解集非空，則極點(diǎn)集合也 一定非空，且極點(diǎn)的個(gè)數(shù)是有限的 。 ,nS R x S x S?? 如 果 不 能 用 中 不 同 的(1 ) ( 2 )xx， ( 1 ) ( 2 )( 1 ) ( 0 1 )x x x? ? ?? ? ? ? ?定理 4 LP 問(wèn)題的可行解集 ? ?,0D x A x b x? ? ? 是 凸 集 。 3 線性規(guī)劃問(wèn)題解的基本性質(zhì) 定義 6 設(shè) 則稱 ()1, 0 , 1 , 2 , , , 1kiniiix R i k???? ? ? ??且 ，( 1 ) ( 2 ) ( )12 kkx x x x? ? ?? ? ? ?為點(diǎn) 的一個(gè)凸組合。 Note: 空集和單點(diǎn)集也是凸集。 返回 第一章 線性規(guī)劃及單純形法 LP 問(wèn)題解的幾何意義 定義 5 設(shè)集合 是 n 維歐氏空間中的一個(gè)點(diǎn) 集，如果 及實(shí)數(shù) ( 1 ) ( 2 )( 1 )x x S??? ? ?nSR? ( 1 ) ( 2 )x x S??、? ?0 , 1? ? 都 有則稱 S 是一個(gè)凸集。 如果 x(1)或 x(2) 是基可行解，則定理成立。 3 線性規(guī)劃問(wèn)題解的基本性質(zhì) 定理 3 證明 設(shè) * * * *12( , , , )nx x x x?是 LP 的一個(gè)最優(yōu)解。 證畢 。 否則 ， 可以從 出發(fā) ， 重復(fù)上述步驟 ， 再構(gòu)造 一個(gè)新的可行解 ， 使它的非零分量的個(gè)數(shù)繼續(xù)減 少 。 167。 則有 x1p1 + x2p2 +…+xkpk = b， 及 x10, x20,…, xk 0， 分兩種情況討論： (1) 如果 p1, p2,…, pk 線性無(wú)關(guān) ， 即 x 的 非零分量對(duì)應(yīng)的列向量線 性無(wú)關(guān) ， 則由定理 1知 ， 它是 LP 的一個(gè)基本可行解 ， 定理成立 。 3 線性規(guī)劃問(wèn)題解的基本性質(zhì) 定理 2 證明 設(shè) x = (x1, x2,…, xn)T 是 LP 問(wèn)題的一個(gè)可行解 ， 如果 x = 0， 則由定理 1知 ， 它是 LP 問(wèn)題的一個(gè)基可行解 ， 定理成立 。 定理 3 如果一個(gè) LP 問(wèn)題有最優(yōu)解，則必存在一個(gè)基可 行解是它的最優(yōu)解。 定義 4 在 LP問(wèn)題的一個(gè) 基可行解中 ， 如果它的所 有的基變量都取正值 ， 則 第一章 線性規(guī)劃及單純形法 LP 問(wèn)題解的基本性質(zhì) 定理 1 設(shè) x 是 LP 問(wèn)題的可行解 (1) 若 x = 0， 則它一定是基可行解； (2) 若 x≠0， 則 x 是基可行解的充要條件是它的非零分 量所對(duì)應(yīng)的列向量線性無(wú)關(guān) 。 3 線性規(guī)劃問(wèn)題解的基本性質(zhì) 基本解唯一嗎？ 最多有多少？ mnn!最 多 有 C = 種m!(nm)!