【正文】 （ c） 若存在 λk0且 aik (i=1,… ,m)不全非正 ， 則進(jìn)行換基； m i n 0 , 0 ,iiL i k i ki k i kbba a M Maa?????????當(dāng) ≤ 時(shí) ＝ 為 任 意 大 的 正 數(shù)第 Ｌ 個(gè)比值最小 ， 選最小比值對應(yīng)行的基變量為出基變量 ， 若有相同最小比值 ， 則任選一個(gè) 。 當(dāng)系數(shù)矩陣 A中可以觀察得到一個(gè)可行基時(shí) （ 通常是一個(gè)單位矩陣或 m個(gè)線性無關(guān)的單位向量組成的矩陣 ） ， 可以通過解線性方程組求得基本可行解 。例如，滿足式（ ） ~()是最優(yōu)解 ,又是 B3的基本解 ,因此它是基本最優(yōu)解。 最優(yōu)解 (optimal solution) 滿足式 （ 1 .1） 的可行解稱為最優(yōu)解 ，即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解 ， 例如可行解 是 例 2的最優(yōu)解 。當(dāng)矩陣B的行列式等于零即 |B|=0時(shí)就不是基 。也稱松馳變量 321 3m in xxxZ ????????????????????????無符號(hào)要求、 32132132132100)3(523)2(3)1(82xxxxxxxxxxxx(3) 第一個(gè)約束條件是 ≤號(hào)，在 ≤左端加入松馳變量 (slack variable) x4，x4≥0,化為等式； (5)第三個(gè)約束條件是 ≤號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在 ≤左邊加入松馳變量 x6， x6≥0，同時(shí)兩邊乘以－ 1。 3） 右端項(xiàng)有負(fù)值的問題： 在標(biāo)準(zhǔn)形式中 ， 要求右端項(xiàng)必須每一個(gè)分量非負(fù) 。 這種情況下 ， 需要重新進(jìn)行求解 。 說明在一定范圍內(nèi)每增加 （ 減少 ） 1個(gè)臺(tái)時(shí)的設(shè)備能力就可增加 （ 減少 ） 50元利潤 ， 稱為該約束條件的對偶價(jià)格 。 線性規(guī)劃的圖解法 對于只有兩個(gè)決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。 線性規(guī)劃的數(shù)學(xué)模型由 決策變量 Decision variables 目標(biāo)函數(shù) Objective function 及約束條件 Constraints 構(gòu)成。第 2章 線性規(guī)劃 問題的提出 線性規(guī)劃的數(shù)學(xué)模型 圖解法 單純形法 【 例 21】 某商場決定：營業(yè)員每周連續(xù)工作 5天后連續(xù)休息 2天 ，輪流休息 。稱為三個(gè)要素。 x1 x2 O 10 20 30 40 10 20 30 40 (300,400) (15,10) 最優(yōu)解 X=(15,10) 最優(yōu)值 Z=8500 402 21 ?? xx 21 ?? xx0,0402212121??????xxxxxx例 22 12m a x 3 0 0 4 0 0Z x x??2 4 6 x1 x2 2 4 6 最優(yōu)解 X=(3,1) 最優(yōu)值 Z=5 (3,1) 121212123643600xxxxxxxx???? ???????? ??? 、min Z=x1+2x2 例 23 (1,2) 2 4 6 x1 x2 2 4 6 X（ 2） ＝（ 3,1） X（ 1） ＝（ 1,3） (5,5) ???????????????006346321212121xxxxxxxx、min Z=5x1+5x2 例 24 有無窮多個(gè)最優(yōu)解 即具有多重解 ,通解為 0≤α≤1 當(dāng) α= Ｘ =(x1,x2)=(1,3)+(3,1)=(2,2) 2 4 6 x1 x2 2 4 6 (1,2) ???????????????006346321212121xxxxxxxx、無界解 (無最優(yōu)解 ) max Z=x1+2x2 例 25 x1 x2 O 10 20 30 40 10 20 30 40 50 50 0,05040221212121????????xxxxxxxx無可行解 即無最優(yōu)解 max Z=10x1+4x2 例 26 由以上例題可知，線性規(guī)劃的解有 4種形式： (例 22例 23) (例 24) (例 25) (例 26) 2情形為有最優(yōu)解 4情形為無最優(yōu)解 靈敏度分析 ： 建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī) 劃的一個(gè)或多個(gè)參數(shù)（系數(shù)） ci , aij , bj 變化時(shí)，對最優(yōu)解產(chǎn) 生的影響。 2 5 02 0 01 0 01 0 0 2 0 0 3 0 0ABCDOB ’C ’ 假設(shè)原料 A 增加 10 千克時(shí) ， 即 b2變化為 410， 這時(shí)可行域擴(kuò)大 ， 但 最優(yōu)解仍為 x2 = 250 和 x1 + x2 = 300 的交點(diǎn) x1 = 50， x2 = 250 。 ? 影子價(jià)格 當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值增加的數(shù)量。 當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí) ， 如 bi0， 則把該等式約束兩端同時(shí)乘以 1， 得到： ai1 x1ai2 x2 … ain xn = bi。 綜合起來得到下列標(biāo)準(zhǔn)型： 3321 33m a x xxxxZ ???????????????????????????????????????????05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、【 例 29】 ：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 Min f = 2 x1 3x2 + 4 x3 . 3 x1 + 4x2 5 x3 ≤6 2 x1 + x3 ≥8 x1 + x2 + x3 = 9 x1 , x2 , x3 ≥ 0 解：首先 ,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 z= f = 2x1+3x24x3 其次考慮約束 ， 有 2個(gè)不等式約束 ， 引進(jìn)松弛變量 x4， x5 ≥ 0。 當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對應(yīng)的列向量稱為 基向量 (basis vector)，其余列向量稱為 非基向量 。 TX )8,0,0,0,53(?非可行解 (Infeasible solution) 無界解 (unbound solution) 顯然，只要基本解中的基變量的解滿足式（ ）的非負(fù)要求，那么這個(gè)基本解就是基本可行解。 1Q2Q基本最優(yōu)解 、 最優(yōu)解 、 基本可行解 、 基本解 、 可行解的關(guān)系如下所示： 基本最優(yōu)解 基本可行解 可行解 最 優(yōu) 解 基本解 例如 ,B點(diǎn)和 D點(diǎn)是可行解 ,不是基本解 。 【 解 】 化為標(biāo)準(zhǔn)型 ， 加入松馳變量 x x4則標(biāo)準(zhǔn)型為 121 2 31 2 41 2 3 4m a x 3