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

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

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

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