教案型及解的幾何意義改

1、113 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 為了求解LP問題，必須統(tǒng)一其模型，本課程選用標(biāo)準(zhǔn)型式為（1) 目標(biāo)函數(shù)為求最大 對(duì)于目標(biāo)函數(shù)是求最小怎么辦？min Z=1000 x1+800 x2 令：z= -z, 則minz=maxzmaxZ= -1000 x1-800 x22（2)約束條件均用線性等式方程來表示，且右邊常數(shù)項(xiàng)均非負(fù)。 實(shí)際情形約束條件顯然不可能都是等式關(guān)系。 當(dāng)表達(dá)式中含“”時(shí) 可在約束條件左邊加上一個(gè)非負(fù)的變量松弛變量，使原來的“”變?yōu)椤啊保?max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4 x2 +x5 =12 x1，x2

2、，x3，x4，x5 0 max z = 2x1 + 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 03當(dāng)表達(dá)式中含“”時(shí)， 可以在約束條件左邊減去一個(gè)非負(fù)變量剩余變量，使原來的“”變?yōu)椤啊薄?目標(biāo)：min f =1000 x1+800 x2約束條件： x1 1 0.8 x1+ x2 1.6 x1 2 x2 1.4 x1、x2 0maxzminz1000 x1800 x20 x30 x40 x50 x6 st x1 x3 1 0.8 x1+ x2 x4 1.6 x1 x5 2 x2 x61.4 x1、x2、x3、x4、x5、x60 4（3）所有變量要求非負(fù)

3、現(xiàn)實(shí)中，有些變量可能從物理意義或經(jīng)濟(jì)意義上講沒有非負(fù)要求 min z =x1x24 x3st 3 x24 x3 9x1 + x2 65 x22 x3 16 x1 0，x2 0， x3無符號(hào)限制 解：令x1=x1，x10， x3 = x3x3, x3、x3 0 將第一個(gè)約束條件兩端乘“1”并加入松弛變量x4，第二個(gè)約束減剩余變量x5，第三個(gè)約束加入松弛變量x6，代入整理后得： maxz =x1x24 x34 x3st 3 x24 x34 x3x4 9x1 + x2 x5 = 65 x22 x32 x3 +x6 = 16 x1， x2， x3、 x3，x4，x5，x60 5練習(xí)： min z =2

4、x1x22x3st x1x2x3 4x1 + x2 x3 6 x1 0，x2 3， x3無符號(hào)限制 max z =2x1+x23x3 x4st x1+x2x3 x4 7 2x1-3x2x3 -8 x1-2x22x4 1 x1 , x3 0, x2 0， x4無符號(hào)限制 再思考：如果x有區(qū)間限制怎么辦？6經(jīng)過上述過程，可得到線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式為： max z =c1x1 + c2x2 + cnxn (1.1)s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + amnxn =

5、bm x1，x2，xn 0 (1.3)其中bi 0，（i =1，2，m）一般m 0。7標(biāo)準(zhǔn)型的簡寫形式:max z =c1x1 + c2x2 + cnxn (1.1)s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + amnxn = bm x1，x2，xn 0 (1.3)用求和符號(hào)表示8用矩陣描述為： max z =CX AX = b X 0= (P1，P2，Pn)；a11 a12 a1na21 a22 a2n am1 am2 amnA=稱 A 為約束條件的m n 階系數(shù)矩陣，一般A的

6、秩為m。0 =0009用向量表示：X=x1x2xnPj =a1ja2jamjb=b1b2bm向 量 Pj 對(duì) 應(yīng) 的 決 策 變 量 為 xj 。10b1b2 bm (p1,p2, ,pn)Pjxj=b a11 a12 a1n a21 a22 a2n am1 am2 amn x1x2 xn=xj0 j=1,nx1x2 xnMax z=x1x2 xn (c1 , c2, ,cn )=cjxj=CX=aijxj =bi i=1,mAX = b X 0 b1114 線性規(guī)劃問題的解的概念 max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4

7、 x2 +x5 =12 x1，x2，x3，x4，x5 012 基 A中的m m 階非奇異矩陣B ；（意味著A的秩為m，|B | 0，B 的各列線性無關(guān)） 基向量 B中的列向量； 基變量 B中的列向量對(duì)應(yīng)的變量； 非基變量 非B中的列向量對(duì)應(yīng)的變量；例如，若A的前m列線性無關(guān)，則a11 a12 a1ma21 a22 a2m am1 am2 amm=( P1，P2，Pm )B =是個(gè)基。P1，P2，Pm是基向量；x1，x2，xm 是基變量；xm+1，xn 是非基變量； 若Amn，mn，則至多有 個(gè)基，每個(gè)基有m個(gè)基變量，n- m 個(gè)非基變量。13 基解 對(duì)應(yīng)每一個(gè)基B,令所有非基變量為零，由 (1

8、.5) 約束方程組求得的解X ； 約束方程組(1.5)中，有m 個(gè)方程n 個(gè)變量，mn，有無窮多解，若前m個(gè)系數(shù)向量線性無關(guān)，令xm+1=xn =0，則可求出XB =( x1，x2，xm)T，則X=( x1，x2，xm，0，0)T就是一個(gè)基解。 至多有 個(gè)基解，基解的非零分量至多m個(gè)，非零分量個(gè)數(shù)小于m 的基解為退化解。 基可行解 滿足非負(fù)條件(1.6)的基解； 同樣至多有 個(gè)基可行解，基可行解至多有m個(gè)正分量。 可行基 對(duì)應(yīng)于基可行解的基； 基最優(yōu)解 使目標(biāo)函數(shù)達(dá)到最大值的基可行解。：14 上述解的概念中基解和基可行解最為重要，各種解的關(guān)系粗略地可用下圖表示： 非可行解可行解 基解基可行解最

9、優(yōu)解152線性規(guī)劃問題的幾何意義本節(jié)重點(diǎn)：凸組合的概念凸集的概念線性規(guī)劃基本定理16如例1，max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4 x2 +x5 =12 x1，x2，x3，x4，x5 0 x1x2O4 Q2(4,2)Q1Q3Q43A172線性規(guī)劃問題的幾何意義本節(jié)重點(diǎn)：凸組合的概念凸集的概念線性規(guī)劃基本定理1821基本概念 凸組合 設(shè) ，若存在 ，0 1，且 ，使則稱X 為 的凸組合。 X1X2X21二維空間兩點(diǎn)連線上的任何一點(diǎn)都是這兩點(diǎn)的凸組合19(a)(b)(c)(d)(e)凸集20(a)(b)(c)(d)(e)圖中

10、紅粗線和紅點(diǎn)是頂點(diǎn)。21222324252627結(jié)論： 線性規(guī)劃問題的可行域是凸集（凸多面體），有有限多個(gè)頂點(diǎn)。頂點(diǎn)對(duì)應(yīng)基可行解。當(dāng)可行域有界時(shí)，必有頂點(diǎn)達(dá)到目標(biāo)函數(shù)最優(yōu)值。28 因此，下面求解線性規(guī)劃問題就是求其基最優(yōu)解，當(dāng)存在無窮多最優(yōu)解時(shí)，若能找出它的所有基最優(yōu)解，這些基最優(yōu)解的任一凸組合便表示它的一個(gè)最優(yōu)解。29練習(xí) X1和X2為某一線性規(guī)劃問題的最優(yōu)解，證明該線性規(guī)劃問題有無窮多個(gè)最優(yōu)解。30如例1，max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4 x2 +x5 =12 x1，x2，x3，x4，x5 0 x1x2O4 Q2(4,2)Q1Q3Q43A31選基變量 基 基解 是否為基可行解 z值（x1,x2,x4) 2 0 0 1 0 4 0（2,3,0,8,0）T是 13（x1,x2,x3) 2 1 0 0 0 4 0（4,3,-2,0,0）T否 （x1,x3,x5) 2 0 0 0 0 4 1（4,2,0,0,4）T是 14（x1,x3,x4) 1 0 0 1 0 0 0 |B|=0 無基和基解 （x1,x4,x5) 0 0 1 0 0 0 1（8,0,0,-16,12）T否 32選基變量 基 基解 是否為基可行解 z值（x2,x3,x4) 2 1 0 0 0 1 4 0 0（0,3,2,16,