線性規(guī)劃問題解的性質(zhì)-5264課件

1、線性規(guī)劃問題解的性質(zhì)2.3線性規(guī)劃問題解的性質(zhì)一、幾個基本概念（名詞）1、可行解、基礎(chǔ)可行解；最優(yōu)解、基礎(chǔ)最優(yōu)解。設(shè)：LP問題： 滿足約束條件的向量 若可行解 x0=o 或 x0 中非零分量 xs xt 所對應(yīng)A中的 滿足 minS=CX0 的可行解 x0 稱為 最優(yōu)解 滿足 minS=CX0 的基礎(chǔ)可行解 x0 稱為 基礎(chǔ)最優(yōu)解稱為可行解列向量 ps pt 是線性無關(guān)時，稱為 基礎(chǔ)可行解2123X201o324X1ABCD由上節(jié)得解 最優(yōu)解在 BC 線段上（無窮最優(yōu)解） 凸多邊形OABCD上任一點都是可行解如 E（1，2）點對應(yīng)解 是可行解 O（0，0）點對應(yīng)解是基礎(chǔ)可行解 p3 p4 p5

2、無關(guān)如 F（3，5/2）點對應(yīng)解 是最優(yōu)解 B（2，3）點對應(yīng)解是基礎(chǔ)最優(yōu)解F（3，5/2）E（1，2）32、凸集（ P31）在二維集合中：矩形、三角形、園是凸集園環(huán)不是凸集在三維集合中：立方體、棱柱、四面體是凸集空心球不是凸集例如：若連接 n 維點集S中任意兩點 x(1), x(2)的線段仍在S內(nèi)則稱 S為凸集。即：4說明：二維點 A,B連線上點 C 可視為定比內(nèi)分點ABC若：則 ：令 ：則 ：寫成向量形式 ：（等號為端點）結(jié)論可推至 n 維5123X201o324X1ABCD最優(yōu)解在 BC 線段上B(2,3) C(4,2)無窮最優(yōu)解:S=063、極點 （P31）極點例如：矩形、三角形、四面

3、體的頂點，園周上的點都是極點若凸集S中的點 x ，不能成為S中任何線段的內(nèi)點，則稱 x 為 S 的極點。即：若對 S 中任意兩點x(1), x(2)不存在使：72例 2 集合：判斷此集合的圖形是否為凸集？找出極點。5AOx1x2可見：此集合是凸集極點有：O（0，0）A（0，5）8二、線性規(guī)劃問題的解的性質(zhì)性質(zhì)1、若(LP)問題有可行解，則可行解集必是凸集 證明：設(shè)解集：有任意兩個解應(yīng)證明當(dāng)：也是屬于S的解1） 2） x S9性質(zhì)2、LP問題的可行解集 S 中點 x 為極點的充分必要條件是 x 為基礎(chǔ)可行解。證明：1） 若 x = 0 ，由定義可知必是基礎(chǔ)可行解。 2） 若 x 0設(shè) x 的非零

4、分量為 xj1 xj2 xjk （kn）在 A中對應(yīng)的列向量為 pj1 pj2 pjk 要證明它們?yōu)榫€性無關(guān)，則 x 就是基礎(chǔ)可行解。用反證法證明。 書上 P32 （略）10性質(zhì)3、LP問題的最優(yōu)值可在極點上達(dá)到證明：設(shè)最優(yōu)解為 x0 ，最優(yōu)值 S（ x0 ）= C x0 1） 若 x0 = 0 ，由定義可知必是極點。2） 若 x0 0用性質(zhì)2的證法，由 x0 構(gòu)造 x（1）， x（2）使其中一個的非零分量比 x0 少一個，且仍是最優(yōu)解 重復(fù)數(shù)次總能找到一個最優(yōu)解，使其非零分量（為最少）它們對應(yīng)的列向量線性無關(guān)，即為極點。（略）11性質(zhì)2：可行解集中點X是極點 性質(zhì)1：LP問題的可行解集一定是凸集性質(zhì)3：LP若有最優(yōu)解必定可以在其可行解集的X是基礎(chǔ)可行解某個極點得到。12A中m 個列向量中的線性無關(guān)組的個數(shù)更少，是有限的基礎(chǔ)可行解與矩陣 A中的一組線性無關(guān)的列向量相對應(yīng)由定理3可知LP問題的最優(yōu)解可從有限的幾個極點中去找。單純形方法：從一個極點迭代到另一個極點，判斷并找出最優(yōu)解?；A(chǔ)可行解即極點個數(shù)有限當(dāng)約束條件為m個，n個變量時所以極點的個數(shù)（基礎(chǔ)可行解個數(shù)）是有限的在A中的任取 m 列共有（不超過上數(shù)）13例如圖解法例題2123X201o324X1ABCDR（A）= 3其中：無關(guān)的：p1p2p3p1p2p4p2p3p5p1p4p5p3p4p5對應(yīng)B點對應(yīng)