6-線性規(guī)劃-閱讀頁
2024-08-23 09:20本頁面
【正文】 50x2 0=40x1+50x2 x1+2x2 =30 3x1+2x2 =60 C點(diǎn) : 0 10 20 30 x2 D A B C 3x1+2x2 = 60 x1+2x2 = 30 2x2 = 24 20 30 10 x1 Z=975 Z=0 Zmax =975 34 (0? ? ? 1) maxZ=40x1+ 80x2 x1+2x2 ? 30, 3x1+2x2 ? 60, 2x2 ? 24, x1 , x2 ?0。 C點(diǎn) : x(2)=(15,)39。 即無可行解 . x2 x1 1 1 0 37 . 可行域無解 . x1 x2 =1 nn xcxcxcZ ???? ?2211m ax線性規(guī)劃問題的理論解法 ???????????????nixbxaxaxabxaxaxatsimnmnmmnn,2,1,0.221111212111????xCZ Tm ax ??????0.xbAxtsA稱為約束矩陣 . 或賦權(quán)向量。x 3 +0x 5 x1 + 2x2 ? 30， 3x1 + 2x2 ? 60， 2x2 ? 24， x1， x2 ? 0； max Z= 40x1 +50x2 例 1: . 其中 x3 , x4, x5 為松弛變量 。 . . 26 (2)、變量 例 3: 令 : x1= x139。 (1) (1) 3 x139。 – x1 – 4x2 ? 14, x139。 (2) 27 ????????????0, jjjjjjxxxxxx則可令由變量），無非負(fù)限制，（稱為自如果某個(gè)變量 jj lx ?（ 2）變量轉(zhuǎn)換： 0??? jjj lxyjj lx ? 0??? jjj xly23 令 : x1 39。? 16 x1+x2 ? 5, 6 ? x1 ? 10, x2?0。 +x2 ? 11, x1 39。 , x2 ?0。 ???njjj xcZ1m i n????njjj ccZ139。 = Z x o Z 24 將以下線性規(guī)劃問題 x1+x2 +x3? 7, x1 x2 +x3 ?2, x1 , x2 ?0， x3為自由變量 。 例 5: min Z = x1+2x2 –3x3 . 29 ① 令 x3 =x4 x5 ② 加松弛變量 x6 ③加剩余變量 x7 ④ 令 Z39。= x1 –2x2 +3x4 –3x5 解： min Z = x1+2x2 –3x3 x1+x2 +x3? 7, x1 x2 +x3 ?2, x1 , x2 ?0； . x1 +x2 +x4 x5 +x6 =7, x1 x2 +x4 x5 x7 =2, x1 , x2 , x4 , x5 , x6 , x7 ?0。 任意點(diǎn) x(1), x(2)∈D ,若任一滿足 x=? x(1)+(1?) x(2) (0? ? ? 1) 的點(diǎn) x∈D 。 38 . . x(2) x(1) . x 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型 B＝ [P1 … Pm] N =[Pm+1 … Pn] a11 … a1m a21 … a2m ………… am1 … amm P1 … Pm a1m+1 … a1n a2m+1 … a2n …………… amm+1 … amn Pm+1 … Pn A＝ ， 定義 2： 基 (基陣 ) ——若 A中一個(gè)子矩陣方陣 B可逆，則矩陣 B稱為 LP問題的一個(gè) 基 (基陣 ) 。 非基向量 : Pm+1 … Pn 。 非基變量 : xN = xm+1 xn … 。 B1 b 0 x= 則稱基 B為 基本 可行基。 B1 b 0 x= ——對(duì)應(yīng)于基 B， 若 B1 b?0， 40 ? ?!!!mnnmc mn ??最多 x1+2x2 +x3 =30, 3x1+2x2 +x4 =60, 2x2 +x5=24, x1 … x5 ?0。 1 2 1 0 0 3 2 0 1 0 0 2 0 0 1 P1 P2 P3 P4 P5 A= , N=[P1 P2] 非基陣 . 非基向量 xN= x1 x2 , xB= x3 x4 x5 , 基向量 x= xN xB 解向量 42 xB = B1 b B1N xN Ax=b 令 = 0 0 xN= x1 x2 則基本解 0 0 30 60 24 x= xN xB = 因?yàn)?x ?0， 是 基本 可行解。 求出基變量是 x1 , x3 , x4的基本解，是不是可行解？ 44 例 給定約束條件 解： 0 1 1 0 1 1 1 1 1 B=(P1 P3 P4)= 0 1 1 1/2 1/2 0 1/2 1/2 0 B1= , b= 0 3 2 . 45 xB = x1 x3 x4 = B1 b 0 1 1 1/2 1/2 0 1/2 1/2 0 = 0 3 2 1 3/2 3/2 = 是可行解 . 所以 x = x1 x2 x3 x4 1 0 3/2 3/2 = , 設(shè) x(1) , x (2) , … , x(k) 是 n維歐氏空間中的 k個(gè)點(diǎn)，若有一組數(shù) 181。2 , … , 181。 i ?1 (i=1,… , k) 定義 4 ? 181。1 x(1) + … + 181。 凸組合 : 46 凸集 D, 點(diǎn) x?D， 若找不到兩個(gè)不同的點(diǎn) x(1) , x(2) ?D 使得 x =? x(1) +(1 ? ) x(2) (0? 1) 則稱 x為 D的頂點(diǎn)。 (LP)問題的基本可行解 可行域的頂點(diǎn)。 48 LP問題理論解法的一般步驟 : 將 LP問題模型標(biāo)準(zhǔn)化，找出所有基矩陣； 49 對(duì)找出的每個(gè)基矩陣求得一個(gè)基本解； 在所有的基本解中找出基本可行解； 在所有的基本可行解中找出最優(yōu)解； 算出最優(yōu)解處目標(biāo)函數(shù)的最優(yōu)值 . 圖解法可以解決二元線性規(guī)劃問題，形象直觀地觀察解的性態(tài)。 軟件解法可解決復(fù)雜線性規(guī)劃問題，但解的性態(tài)信息不多 。 根據(jù)題目難度系數(shù)及完成質(zhì)量給分 。 。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1