運(yùn)籌學(xué)13課件

1、第二章 線性規(guī)劃問題及單純形法,線性規(guī)劃問題及其數(shù)學(xué)模型 圖解法 單純形法原理 單純形法計(jì)算步驟 單純形法的進(jìn)一步討論,第三節(jié) 單純形法原理,本節(jié)重點(diǎn)： 基本概念 線性規(guī)劃基本定理 檢驗(yàn)數(shù)的概念和計(jì)算 最優(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中的一個(gè)mm階的滿秩子系數(shù)矩陣，稱B是線性

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

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

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

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

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