運籌學(xué)13課件

1、第二章 線性規(guī)劃問題及單純形法,線性規(guī)劃問題及其數(shù)學(xué)模型 圖解法 單純形法原理 單純形法計算步驟 單純形法的進(jìn)一步討論,第三節(jié) 單純形法原理,本節(jié)重點： 基本概念 線性規(guī)劃基本定理 檢驗數(shù)的概念和計算 最優(yōu)性判別 基變換（換入變量和換出變量的確定）,一、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念,線性規(guī)劃問題 ：,可行解：滿足上述約束條件(2.2)，(2.3)的解 ，稱為線性規(guī)劃問題的可行解。全部可行解的集合稱為可行域。 最優(yōu)解：使目標(biāo)函數(shù)(2.1)達(dá)到最大值的可行解稱為最優(yōu)解。 基：設(shè) A 為約束方程組(2.2)的 mn 階系數(shù)矩陣，(設(shè)nm)，其秩為m，B是矩陣A中的一個mm階的滿秩子系數(shù)矩陣，稱B是線性

2、規(guī)劃問題的一個基。,不失一般性，設(shè) ：,B中的每一個列向量Pj ( j1,m )稱為基向量，與基向量Pj對應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的變量稱為非基變量。 基解: 在約束方程組(2.2)中，令所有非基變量 xm+1xm+2xn0，又因為有 ，根據(jù)克萊姆規(guī)則，由m個約束方程可解出m個基變量的唯一解 。將這個解加上非基變量取0的值有 ，稱X為線性規(guī)劃問題的基解。顯然在基解中變量取非零值的個數(shù)不大于方程數(shù)m，故基解的總數(shù)不超過 個。 基可行解: 滿足變量非負(fù)約束條件(2.3)的基解稱為基可行解。 可行基: 對應(yīng)于基可行解的基稱為可行基。 退化解: 基可行解的非零分量個數(shù) m 時，即

3、有的基可行解也為0，稱為退化解。,例：找出下述線性規(guī)劃問題的全部基解，指出其中的基可行解，并確定最優(yōu)解。,解:該線性規(guī)劃問題的全部基解見表中的 -，打者為基可行解，注*者為最優(yōu)解，z* l9。,線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系,約束方程的 解空間,基解,可行解,非可行解,基 可行解,退化解,二、線性規(guī)劃問題的幾何意義,凸集的概念 頂點 線性規(guī)劃基本定理,1. 凸集,對簡單的幾何形體可以直觀地判斷其凹凸性，但在高維空間，只能給出點集的解析表達(dá)式，因此只能用數(shù)學(xué)解析式判斷。凸集的概念為：如果集合C中任意兩個點X1，X2，其連線上的所有點也都是集合C中的點，稱C為凸集。由于X1，X2的連線可表示為,因此凸

4、集定義用數(shù)學(xué)解析式可表為：對任何 ，有 則稱C為凸集.,圖中紅粗線和紅點是頂點。,2.頂點 凸集C中滿足下述條件的點X稱為頂點。 如果C中不存在任何兩個不同的點X1，X2，使X成為這兩個點連線上的一個點，或者：對任何 ,不存在 ，則稱X是凸集C的頂點。,3. 線性規(guī)劃基本定理,定理1 若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。,證 (方法1) 若滿足線性規(guī)劃約束條件 的所有點組成的幾何圖形C是凸集，根據(jù)凸集定義，C內(nèi)任意兩點Xl，X2連線上的點也必然在C內(nèi)，下面給予證明。,設(shè) 為C內(nèi)任意兩點， 即 ，將X1，X2代入約束條件有,(2.4),X1，X2連線上任意一點可以表示為：,(2.5)

5、,將式（2.4）代入式（2.5）得：,所以 。由于集合中任意兩點連線上的點均在集合內(nèi)，所以C為凸集。,引理 線性規(guī)劃問題的可行解X=(x1，x2，xn）T為基可行解的充分必要條件是X 的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的。,證明： (1)必要性 由基可行解的定義可知，X為基可行解 其正分量的系數(shù)列向量線性無關(guān)。 (2)充分性 若向量 線性獨立，則必有km；當(dāng)km時，它們恰好構(gòu)成一個基，從而 為相應(yīng)的基可行解。當(dāng)是km時，則一定可以從其余列向量中找出(m-k)個與 構(gòu)成一個基，其對應(yīng)的解恰為X，所以據(jù)定義它是基可行解。,定理2 線性規(guī)劃問題的基可行解 對應(yīng)線性規(guī)劃問題可行域（凸集）的頂點。,則

6、問題可以轉(zhuǎn)化為證明： 的正分量對應(yīng)的系數(shù)列向量線性相關(guān) 在可行域內(nèi)存在兩點 、 ， 可以用 、 的凸組合表示。,不是基可行解 不是可行域的頂點。 不是基可行解 的正分量對應(yīng)的系數(shù)列向量線性相關(guān)。 不是可行域的頂點 在可行域內(nèi)存在兩點 、 ， 可以用 、 的凸組合表示。,證明思路： 利用反證法證明。,定理3 若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。,結(jié)論： 線性規(guī)劃問題的可行域是凸集(凸多面體)，有有限多個頂點。頂點對應(yīng)基可行解。當(dāng)可行域有界時，必有頂點達(dá)到目標(biāo)函數(shù)最優(yōu)值。,三、單純型法的基本思路,由定理3可知，如果線性規(guī)劃問題存在最優(yōu)解，一定有一個基可行解是最優(yōu)解。 因此單純形法迭代的基本思路是：先找出一個基可行解，判斷其是否為最優(yōu)解，如果為否，則轉(zhuǎn)換到相鄰的基可行解，并使目標(biāo)函數(shù)值不斷增大，一直找到最優(yōu)解