線性規(guī)劃解的性質(zhì).ppt

圖解法 線性規(guī)劃問(wèn)題求解的幾種可能結(jié)果 由圖解法得到的啟示 線性規(guī)劃解的概念 凸集的概念 線性規(guī)劃的基本定理,第二節(jié) 線性規(guī)劃問(wèn)題的解,線性規(guī)劃問(wèn)題解的概念,標(biāo)準(zhǔn)型 可行解:滿足AX=b, X=0的解X稱為線性規(guī)劃問(wèn)題的可行解。 最優(yōu)解：使Z=CX達(dá)到最大值的可行解稱為最優(yōu)解。,A為mn陣 m n,基：若B是矩陣A中mm階非奇異子矩陣（B0），則B是線性規(guī)劃問(wèn)題的一個(gè)基。不妨設(shè)：, j=1，2，,m 基向量。 ，j=1，2，,m 基變量。 , j=m+1,n 非基變量。,線性規(guī)劃問(wèn)題解的概念,線性規(guī)劃的基、基變量、非基變量,=,=,目標(biāo)函數(shù),約束條件,行列式0 基矩陣,右邊常數(shù),求解,線性規(guī)劃問(wèn)題解的概念,基解：稱上面求出的X解為基解。 基可行解：非負(fù)的基解X稱為基可行解 可行基：對(duì)應(yīng)基可行解的基稱為可行基,線性規(guī)劃問(wèn)題解的概念,min,max,基變量x1、x2、x3，非基變量x4、x5、x6,基解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0， 0，0） 是基可行解，表示可行域的一個(gè)極點(diǎn)。,基變量x1、x2、x4，非基變量x3、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。,基變量x1、x2、x5，非基變量x3、x4、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基礎(chǔ)解，但不是可行解，不是一個(gè)極點(diǎn)。,基變量x1、x2、x6，非基變量x3、x4、x5,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。,基變量x2、x3、x4，非基變量x1、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基礎(chǔ)解，但不是可行解。,基變量x1、x2、x3，非基變量x4、x5、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。,基變量x1、x2、x3，非基變量x4、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基礎(chǔ)解但不是可行解。,線性規(guī)劃解的關(guān)系圖,非可行解,可行解,基可行解,基解,線性規(guī)劃問(wèn)題解的概念,最優(yōu)解？,例：求基解、基可行解、最優(yōu)解。,線性規(guī)劃問(wèn)題解的概念,最優(yōu)解,線性規(guī)劃問(wèn)題解的概念,解：,注：x1x3x4及x2x4x5所對(duì)應(yīng)的系數(shù)不夠成基,可行解、基礎(chǔ)解和基礎(chǔ)可行解舉例,幾何概念,代數(shù)概念,約束直線,滿足一個(gè)等式約束的解,約束半平面,滿足一個(gè)不等式約束的解,約束半平面的交集： 凸多邊形,滿足一組不等式約束的解,約束直線的交點(diǎn),基解,可行域的極點(diǎn),基可行解,目標(biāo)函數(shù)等值線： 一組平行線,目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解,線性規(guī)劃問(wèn)題的幾何意義,基本概念 凸集：,線性規(guī)劃問(wèn)題的幾何意義,頂點(diǎn):若K是凸集，XK；若X不能用不同的兩點(diǎn) 的線性組合表示為： 則X為頂點(diǎn).,凸集,線性規(guī)劃問(wèn)題的幾何意義,例如：三角形的三個(gè)角點(diǎn)，實(shí)心圓圓周上的任一點(diǎn)，實(shí)心球球面上的任一點(diǎn)。,一個(gè)點(diǎn)是凸集，一段直線是凸集，平面上的凸多邊形、實(shí)心圓，空間中的實(shí)心球、實(shí)心立方體等多面體，都是凸集。,從直觀上講，凸集沒(méi)有凹入部分，其內(nèi)部沒(méi)有空洞。左圖中的(a)(b)是凸集，(c)不是凸集。 右圖中的陰影部分是凸集。 任何兩個(gè)凸集的交集是凸集，見(jiàn)左圖 (d),上圖中（1）（2）是凸集，（3）（4）不是凸集,基本定理,證明:,定理1: 若線性規(guī)劃問(wèn)題存在可行域, 則其可行域: 是凸集.,只要驗(yàn)證X在D中即可,定理4：若可行域有界，線性規(guī)劃 問(wèn)題的目標(biāo)函數(shù)一定可以在 其可行域的頂點(diǎn)上達(dá)到最優(yōu)。,定理2：線性規(guī)劃問(wèn)題的基可性解X 對(duì)應(yīng)于可行域D的頂點(diǎn)。 證明：反證法。分兩步。,幾點(diǎn)結(jié)論：,線性規(guī)劃問(wèn)題的可行域是凸集。 基可行解與可行域的頂點(diǎn)一一對(duì)應(yīng)，可行域有有限多個(gè)頂點(diǎn)。 最優(yōu)解必在頂點(diǎn)上得到。,圖解法,9 8 7 6 5 4 3 2 1 0,x2,可行域?yàn)橥辜?目標(biāo)函數(shù)不同時(shí) 等值線的斜率不同 最優(yōu)解在頂點(diǎn)產(chǎn)生,目標(biāo)函數(shù)等值線的斜率,最優(yōu)解,圖解法,9 8 7 6 5 4 3 2 1 0,x2,可行域?yàn)橥辜?目標(biāo)函數(shù)不同時(shí) 等值線的斜率不同 最優(yōu)解在頂點(diǎn)產(chǎn)生,目標(biāo)函數(shù)等值線的斜率,最優(yōu)解,圖解法,9 8 7 6 5 4 3 2 1 0,x2,可行域?yàn)橥辜?目標(biāo)函數(shù)不同時(shí) 等值線的斜率不同 最優(yōu)解在頂點(diǎn)產(chǎn)生,目標(biāo)函數(shù)等值線的斜率,最優(yōu)解,上述定理的一些有意義的啟示：,線性規(guī)劃的基本可行解和可行域的頂點(diǎn)是一一對(duì)應(yīng)的（類似于坐標(biāo)與點(diǎn)的對(duì)應(yīng)關(guān)系?。?在可行域中尋找LP的最優(yōu)解可以轉(zhuǎn)化為只在可行域的頂點(diǎn)中找，從而把一個(gè)無(wú)限的問(wèn)題轉(zhuǎn)化為一個(gè)有限的問(wèn)題。,線性規(guī)劃理論的小結(jié),1、一般意義上說(shuō)： （1）如果線性規(guī)劃問(wèn)題有可行解，則一定有基本可行解。 （2）線性規(guī)劃問(wèn)題如果有最優(yōu)解，則最優(yōu)解一定可以從基本可行解中找得到。 （3）由于基本可行解的個(gè)數(shù)有限，所以經(jīng)過(guò)有限次迭代，就一定能找到最優(yōu)解。,2、從幾何意義上說(shuō)： （1） 基本解對(duì)應(yīng)所有可行域邊界延長(zhǎng)線、坐標(biāo)軸之間的交點(diǎn)； （2） 線性規(guī)劃問(wèn)題可行域中的每一個(gè)極點(diǎn)都對(duì)應(yīng)著一個(gè)基本可 行解。 （3） 由于最優(yōu)解必定要從基本可行解中尋找，所以所謂求解 線性規(guī)劃問(wèn)題，實(shí)際上就是比較極點(diǎn)處的目標(biāo)函數(shù)值的 大小。 （4） 極點(diǎn)的個(gè)數(shù)是有限的(不大于 個(gè))，那么只要經(jīng)過(guò)有限 次尋找（枚舉法）就一定能夠找到基