【正文】 ,0)。 X2 =(45/13,0,14/13,0) X3 =(34/5, 0,0,7/5)。 X4 =(0,45/16,7/16,0) X5 =(0,68/29,0,7/29) 。 X6 =(0,0,68/31,45/31) 基可行解 X1﹑X 3﹑X 4, 最優(yōu)解 X3， Z=117/5 24C?????????????????????????????????????????????????????? ????????????7641,7243,62137142,6112,2132654321BBBBBB思考： X=(9/7,27/7,1,0)、 X=(7,1,1,2)是何解 ？ 22 例 1 Max Z =2x1+3x2 . x1+ 2x2≤8 4x1 ≤ 16 4x2≤ 12 x1, x2 ≥0 ???可行解、基解和基可行解舉例 非基變量 基變量 圖中的點(diǎn) x4, x5 x1=4 x2=3 x3= 2 A基解 x3, x5 x1=2 x2=3 x4=8 B基可行解 x3, x4 x1=4 x2=2 x5=4 C基可行解 x2, x4 x1=4 x3=4 x5=12 D基可行解 x2, x3 x1=8 x4= 16 x5=12 E基解 x1, x5 x2=3 x3=2 x4=16 F基可行解 x1, x3 x2=4 x4=16 x5= 4 G基解 x1, x2 x3=8 x4=16 x5=12 H基可行解 4x1=16 4x2=12 x1+2x2=8 x1 x2 0 Z=2x1+3x2 A B C D E F G H ????????????????????????)5,1(01241648200032524132154321?jxxxxxxxxxxxxxM axZj標(biāo)準(zhǔn)型 23 線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系 約束方程的 解空間 基解 可行解 非可行解 基可 行解 24 Max Z=3X1+5X2+0X3+0X4+0X5 系數(shù)矩陣 : X1 +X3=8 ① 1 0 1 0 0 2X2 +X4 =12 ② 0 2 0 1 0 3X1+4X2 +X5 =36 ③ 3 4 0 0 1 X1,X2, X3, X4 , X5≥0 C =（ 3 5 0 0 0） x 1 x 2 x 3 x 4 x 5 基本變量 非基變量1 0 1 0 0 x 3 x 4 x 5 x 1 x 20 2 0 1 03 4 0 0 1x 1 x 2 x 3 x 4 x 5 基本變量 非基變量1 1 0 0 x 1 x 4 x 5 x 2 x 30 2 0 1 03 4 0 0 1令 x1,x2=0，得： X=(0 0 8 12 36) z=0 1 令 x2,x3=0，得： X=(8 0 0 12 12) z=24 2 保留的變量稱基變量，由解方程求得。移到右邊并令為零的變量稱非基變量。相應(yīng)于基變量的系數(shù)列稱基。 25 x 1 x 2 x 3 x 4 x 5 基本變量 非基變量1 0 1 0 0 x 1 x 3 x 4 x 2 x 50 2 0 1 03 4 0 0 1x 1 x 2 x 3 x 4 x 5 基本變量 非基變量1 0 1 0 0 x 1 x 2 x 3 x 4 x 50 2 0 1 03 4 0 0 1令 x4,x5=0，得： X=(4 6 4 0 0) z=42 5 令 x2,x5=0，得： X=(12 0 4 12 0) z=36 6 x 1 x 2 x 3 x 4 x 5 基本變量 非基變量1 0 1 0 0 x 2 x 3 x 5 x 1 x 40 2 0 1 03 4 0 0 1x 1 x 2 x 3 x 4 x 5 基本變量 非基變量1 0 1 0 0 x 1 x 2 x 4 x 3 x 50 2 1 03 4 0 0 1令 x1,x4=0，得： X=(0 6 8 0 12) z=30 3 令 x3,x5=0，得： X=(8 3 0 6 0) z=39 4 26 x 1 x 2 x 3 x 4 x 5 基本變量 非基變量1 0 1 0 0 x 2 x 3 x 4 x 1 x 50 2 0 1 03 4 0 0 1x 1 x 2 3 x 4 x 5 基本變量 非基變量1 0 1 0 0 x 1 x 2 x 5 x 3 x 40 2 1 03 4 0 0 1令 x1,x5=0，得： X=(0 9 8 6 0) z=45 7 令 x3,x4=0，得： X=(8 6 0 0 12) z=54 8 x 1 x 2 x 3 x 4 x 5 基本變量 非基變量1 0 1 0 0 x 2 x 4 x 5 x 1 x 30 2 0 1 03 4 0 0 1x 1 x 2 3 x 4 x 5 基本變量 非基變量1 0 1 0 0 x 1 x 3 x 5 x 2 x 40 2 1 03 4 0 0 1 ∵ 0 0 0 2 1 0 =0 4 0 1 ∴ 無解 9 ∵ 1 1 0 0 0 0 =0 3 0 1 ∴ 無解 10 27 小 結(jié) ? 本例 3階系數(shù)行列式共有 10個(gè)，其中有 8個(gè)行列式 ≠ 0，它們稱為 基 ，其中的每一列 Pj (j=1,2,… ,m)稱基向量，另 2個(gè)行列式 =0，無意義。 ? 與基向量 Pj對應(yīng)的變量 xj稱為基變量，記為XB ，其余變量稱為非基變量，記為 XN ? 根據(jù)基求出的解稱 基解 ，本例有 8個(gè)基解，其中有 5個(gè)解的所有變量都 ≥0(即可行 )，這 5個(gè)解稱 基可行解 ，給出這 5個(gè)可行解的基稱為 可行基 。 ? 在 5個(gè)可行解中，第 5個(gè)解的目標(biāo)函數(shù)值最大，故又稱這個(gè)解的可行基為 最優(yōu)基 。 28 線性規(guī)劃解的概念與定理 ?可行解： 滿足約束方程組和非負(fù)條件的解。 ?基 (B)： 約束方程系數(shù)矩陣 Am*n (m為方程個(gè)數(shù)，n為變量個(gè)數(shù) )中滿足行列式 ≠ 0的 m階方陣。對應(yīng)于基系數(shù)列的變量稱基變量 XB ，非基系數(shù)列對應(yīng)變量稱非基變量 XN 。 ?基解： 根據(jù)某個(gè)基，令非基變量 =0而求出的解。 29 線性規(guī)劃解的概念與定理 ?基可行解： 滿足非負(fù)條件的基解。 ?可行基： 對應(yīng)于可行解的基。 ?最優(yōu)基： 給出最優(yōu)目標(biāo)函數(shù)值的可行基。 ?定理： 若線性規(guī)劃問題存在最優(yōu)解，則必定能在其基可行解中得到。從圖形上看，也就是說最優(yōu)解一定能在其可行域的頂點(diǎn)處得到。 30 第 2節(jié) LP理論基礎(chǔ)： (凸集、凸組合、頂點(diǎn)） 凸集 ：設(shè) K為 En的一點(diǎn)集，若對于任意 X(1)﹑X (2) € K，都有 αX (1)+（ 1α ） X(2) € K ，（ 0≤α≤1 ）；則稱K為凸集。 凸組合 ：設(shè) X(1)﹑X (2) … X(k)為 En的 K個(gè)點(diǎn)，若存在 μ μ 2 … μ k，且 0≤μ i≤1 ， i=1， 2… k。 使 X=μ 1 X(1)+μ 2 X(2) … +μ k X(k) 則稱 X為 X(1)， X(2) … X(k)的凸組合。 ????kii1,1頂點(diǎn) ：設(shè) K為凸集， X € K，若 X不能用不同的兩點(diǎn)X(1)﹑X (2) € K的線性組合表示為 αX (1)+（ 1α ） X(2) （ 0≤α≤1 ）；則稱 X為 K的一個(gè)頂點(diǎn)。 31 第 2節(jié) LP理論基礎(chǔ)： (定理 2*、 3） 證明： 設(shè) X(1)﹑X (2)為 LP可行域 D內(nèi)任意兩點(diǎn)， X(1)≠X (2) ， 則 AX(1)=b， AX(2)=b， X(1)≥0 ， X(2)≥0 令 X為 X(1)﹑X (2) 連線上任意一點(diǎn)， 即 X=αX (1)+（ 1α ） X(2) ，（ 0≤α≤1 ） 代入約束 AX=αAX (1)+（ 1α ） AX(2) =αb+ （ 1α ） b=b， 又 ∵ α≥0 ，（ 1α ） ≥ 0， ∴ X≥0 ，即 X(1)﹑X (2) 連線上任意一點(diǎn)也在 D內(nèi)，由凸集定義， D為凸集。 定理 1：若 LP問題存在可行域，則其可行域 D={ X| } 是凸集。 ????nj jjjxbxp10,32 證明： 設(shè) X(1)﹑...﹑X (k)為可行域頂點(diǎn)，相應(yīng)目標(biāo)值 Z(1)﹑...﹑Z (k) ，其中第 m個(gè)頂點(diǎn) X(m)處目標(biāo)值最大，記為 Z(m) ，若 X(0) 不是頂點(diǎn)但其目標(biāo)值最優(yōu)，則： X(0) = α i X(i) ， α i≥0 ， α i =1 CX(0)= α i CX(i)= α iZ(i)≤ α iZ(m)= Z(m) 據(jù)假使 CX(0) 為最優(yōu)值， ∴ X(m)處也能達(dá)到最優(yōu)。 ??k1i??k1i??k1i??k1i??k1i定理 3：若可行域有界， LP問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。 33 第 3節(jié) 單純形法 (Gee Dantgig于 1947年提出 ) 由線性代數(shù)知，對標(biāo)準(zhǔn)形 LP問題，理論上可以求出所有基解（枚舉法），再通過觀察找出其中的可行解（基可行解），進(jìn)而找出最優(yōu)解。但如果變量和方程較多，比如 m=50， n=100，所有基解有可能達(dá) 1029個(gè)，即使計(jì)算機(jī)每秒能求解 1億個(gè)這樣的方程組，也需要 30萬億年！因此，必須尋求有效的算法 . 34 為加快計(jì)算速度，算法必須具有兩個(gè)功能，一是每得到一個(gè)解，就來檢驗(yàn)是否已經(jīng)最優(yōu)，若是，停止。二是若不是最優(yōu)，要保證下一步得到的解不劣于當(dāng)前解?；诰€性代數(shù)原理，并將上述功能貫穿于算法過程，這就是線性規(guī)劃的單純形法。 第 3節(jié) 單純形法 (Gee Dantgig于 1947年提出 ) 35 Z=2X1+3X2,C1=20, C2=30, ∴ 此解非最優(yōu) , 選 X2進(jìn)基 . 令 X1,X2=0,稱非基變量