線性規(guī)劃解的概念

1、1.2 線性規(guī)劃解的概念1圖解法對(duì)二維問(wèn)題，可作出約束的圖，簡(jiǎn)單直觀地理解線性規(guī)劃的解。例 考察線性規(guī)劃問(wèn)題等值線 x+3y=C可行域 最優(yōu)解繼續(xù)2解的概念可行解(feasible solution) ：滿足線性規(guī)劃問(wèn)題(LP)的所有約束條件的解，稱為線性規(guī)劃問(wèn)題的一個(gè)可行解?？尚杏颍?LP)的所有可行解組成的集合K稱為(LP)的可行域。若可行域?yàn)榭?，則稱不可行。對(duì)標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題，其可行域?yàn)樽顑?yōu)解(optimal solution) ：可行域中每個(gè)可行解都對(duì)應(yīng)一個(gè)目標(biāo)值，其中對(duì)應(yīng)的目標(biāo)函數(shù)值最小的可行解x*，稱為(LP)的最優(yōu)解，也稱為(LP)的解。即最優(yōu)值：最優(yōu)解對(duì)應(yīng)的目標(biāo)值稱為最優(yōu)值。

2、3基 設(shè) 為滿秩矩陣(秩為m)， 是A中的非奇異子矩陣 ，則稱B為（LP)的一個(gè)基。基變量與非基變量 B是由A的m個(gè)線性無(wú)關(guān)的列組成，對(duì)應(yīng)的變量稱為基變量，剩下的變量稱為非基變量。基解 令非基變量變量等于0，可得線性方程組的一個(gè)解，稱為基解(basic solution).基可行解 若基解還是可行的，即滿足非負(fù)性條件，則稱為基可行解(basic feasible solution 簡(jiǎn)記為bfs)。4基解的個(gè)數(shù)非退化的基可行解：若基變量全部為正。否則稱為退化的基可行解，即有基變量為0可行解基解基可行解非可行解5例 求出線性規(guī)劃問(wèn)題的全部基解，指出哪些是可行的。圖解法6線性規(guī)劃解的幾種可能情況無(wú)可

3、行解 可行域?yàn)榭占?，約束中存在矛盾方程。有唯一的最優(yōu)解（通常的情況），必是可行域的頂點(diǎn)。有無(wú)窮多個(gè)最優(yōu)解。有可行解但無(wú)最優(yōu)解 可行域必?zé)o界。71.3線性規(guī)劃問(wèn)題的幾何意義8基本概念凸集 設(shè)K為n維線性空間的一點(diǎn)集，若對(duì)K中任意兩點(diǎn)x,y，及任意的 ，有則稱K為凸集。規(guī)定空集和單點(diǎn)集為凸集。9例 超平面和半空間都是凸集。凸組合 設(shè) 為 中的點(diǎn)，為滿足下列條件的一組實(shí)數(shù)則稱 為 的凸組合。極點(diǎn) 設(shè)K為凸集， ，若x不能表示成K中不同的兩點(diǎn)的凸組合，則稱x為K的一個(gè)極點(diǎn)(頂點(diǎn))。10基本定理定理1 任意一組凸集的交集仍為凸集。定理2 線性規(guī)劃問(wèn)題的可行域是凸集。引理1 線性規(guī)劃問(wèn)題的可行解為基可行解

4、的充要條件是其正分量所對(duì)應(yīng)的系數(shù)列向量是線性無(wú)關(guān)的。證明： 必要性 若x是基解，由定義，正分量對(duì)應(yīng)的列線性無(wú)關(guān)。充分性 若正分量對(duì)應(yīng)的列線性無(wú)關(guān)，則個(gè)數(shù)不超過(guò)m，若=m,則是基，若m,可擴(kuò)充成基。11定理3 線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)于可行域的頂點(diǎn)。證明：若x是基可行解，設(shè)前m個(gè)分量為基變量，但不是極點(diǎn)，則存在x1,x2,01, x=x1 +(1-) x2.x1,x2的后n-m個(gè)分量為0。若x是極點(diǎn)，但不是基可行解，正分量對(duì)應(yīng)的列線性相關(guān)。對(duì)任意的實(shí)數(shù)取充分小的得兩可行解x1,x2 ，使x= x1/2+x2/2。12推論 線性規(guī)劃可行域的頂點(diǎn)個(gè)數(shù)有限。引理2 若K為有界閉凸集，則其中任何一點(diǎn)可

5、表示為其頂點(diǎn)的凸組合。不證明，舉例說(shuō)明。定理4 若可行域有界，線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)達(dá)到最優(yōu)。證明：另外，若可行域無(wú)界，但有最優(yōu)解，則一定也可在頂點(diǎn)處達(dá)到最優(yōu)。定理4換成代數(shù)說(shuō)法就是：線性規(guī)劃問(wèn)題若存在最優(yōu)解，則一定存在最優(yōu)的基可行解。13第二章 單純形法14窮舉法的困難已知線性規(guī)劃問(wèn)題的一基可行解，問(wèn)題此基可行解是否最優(yōu)；該問(wèn)題是否無(wú)最優(yōu)解；如何改進(jìn)（求一更好的基可行解）；算法是否會(huì)有限步結(jié)束；如何找一基可行解。152.1 單純形表為計(jì)算方便，將系數(shù)提出來(lái)，形成表格：16設(shè)有一可行基，不妨設(shè)是前m個(gè)向量，則線性方程組可化為如下形式其中目標(biāo)函數(shù)可表成非基變量的函數(shù)將系數(shù)

6、提出列成表，稱為對(duì)應(yīng)于基B的單純形表17單純形表18最優(yōu)性檢驗(yàn)與解的判別定理1（最優(yōu)解的判別定理）設(shè) 為(LP)的一基可行解，若對(duì)任意的非基變量，都有 ，則 為最優(yōu)解，稱 為檢驗(yàn)數(shù)。定理2 若對(duì)某非基變量，有那么，該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。19基可行解的改進(jìn)進(jìn)基變量的選擇出基變量的選擇最小比值原則證明新的解是基可行解，在非退化假設(shè)下，新解目標(biāo)值下降。 20單純形法的計(jì)算步驟算法(單純形法)1)找出初始可行基,確定初始可行解,建立初始單純形表；2)檢驗(yàn)各非基變量的檢驗(yàn)系數(shù),若全部非正，結(jié)束,得到最優(yōu)解;3)若某非基變量檢驗(yàn)數(shù)為正，且其對(duì)應(yīng)的系數(shù)列向量全部非正，結(jié)束，問(wèn)題無(wú)最優(yōu)解;4)選某個(gè)檢驗(yàn)數(shù)為正的非基變量進(jìn)基，計(jì)算最小比值，確定出基變量，5)以所選元素為主元進(jìn)行消元,得新單純形表，轉(zhuǎn)2)。21例1 用單純形法求線性規(guī)劃問(wèn)題的解化為標(biāo)準(zhǔn)型,列初始單純形表6/18/222作旋轉(zhuǎn)變換得新的單純形表5/2-4/33/2（2/3）主元23例2 用單純形法求線性規(guī)劃問(wèn)題的解基x1x4x6-310/3主元241/40-1/