【正文】 4是基變量， x x x5是非基變量。 （ 3） 可行解 滿足式（ ）及（ ）的解 X=(x1,x2,…, xn)T、稱為可行解。 （ 4） 最優(yōu)解 滿足式（ ）的可行解稱為最優(yōu)解，即使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解，例如可行解 X=（ 3/5， 0， 0， 0， 8）、是例 的最優(yōu)解。 （ 6） 基本可行解 若基本解是可行解則稱為是基本可行解（也稱基 可行解或基解）。 、 x2 是基變量， x x x5是非基變量，令 x3=x4=x5=0，則 ??? ???? 2610 352121 xx xx－ 因 |B1|≠０，由克菜姆法則知， x x2 有唯一解 x1＝ 2/ x2=1，則基本解為 TX )0,0,0,1,52()1( ? 對(duì) B2 來說， x x4為基變量，令非變量 x2,、 x x5為零，得到 x1=－ 1/5， x4=4，基本解為 TX )0,4,0,0,51()2( ?? 由于 是基本解，從而它是基本可行解，在 ）（ 2X 中 x10,因此 ）（ 2X 不是可行解，也就不是基本可行解。 （ 7） 基本最優(yōu)解 最優(yōu)解是基本解稱為基本最優(yōu)解。 （ 8） 可行基與最優(yōu)基 基可行解對(duì)應(yīng)的基稱為可行基；基本最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基，如上述 B3 就是最優(yōu)基，最優(yōu)基也是可行 基。 （ 10） 凸組合 設(shè) )()2()1( , KXXXX ?是 Rn中的點(diǎn)，若存在 021 ?iK ???? ，且， ? 及11 ???Ki i? ，使得 iKi i XX ??1?＝ 成立，則稱 X 為 )()2()1( , KXXX ? 的凸組合。 X 是凸集 K 的極點(diǎn)即 X 不可能是 K 中某一線段的內(nèi)點(diǎn)，只能是 K 中某一線段的端點(diǎn)。 【定理 】 線性規(guī)劃的可行解集合 K 的點(diǎn) X 是極點(diǎn) 的充要條件為 X是基本可行解。 定理 。 定理 ，若最優(yōu)解唯一，則最優(yōu)解只能在某一極點(diǎn)上達(dá)到，若具有多重最優(yōu)解，則最優(yōu)解是某些極點(diǎn)的凸組合，從而最 優(yōu)解是可行解集的極點(diǎn)或界點(diǎn)，不可能是可行解集的內(nèi)點(diǎn)。若線性規(guī)劃具有無界解，則可行域一定無界。用枚舉法求出所有基可行解，再代入目標(biāo)函試算得到最優(yōu)解。 單純形法 普通單純形法 單純形計(jì)算方法 (Simplex method)是先求出一個(gè)初始基可行解并判斷它是否最優(yōu)，若不是最優(yōu)，再換一個(gè)基可行解并判斷，直到得出最優(yōu)解或無最優(yōu)解。普通單純形法是最基本最簡(jiǎn)單的一種方法，它假定標(biāo)準(zhǔn)型系數(shù)矩陣中 A中可以觀察得到一個(gè)可行基（通常是一個(gè)單位矩陣或 m 個(gè)線性無關(guān)的單位向量組成的矩陣），可以通過解線性方程組求得基本可行解。 【例 】 用單純形法求下列線性規(guī)劃的最優(yōu)解 【解】 化為標(biāo)準(zhǔn)型，加入松馳變量 x x4 則標(biāo)準(zhǔn)型為 系數(shù)矩陣 2 1 1 01 3 0 1A ??? ???? 顯然 A中第 3 列和第 4 列組成 2 階單位矩陣，記為 1 1001B ??????? r(B1)=2， B1 是一個(gè)初始基 ,x x4為基變量， x x2 為非基變量，令 x1=0、 x2=0由約束方程知 x3=x4=30 得到初始基本可行解 X(1)=(0， 0， 40， 30)T 求解過程見表 14 所有檢驗(yàn)數(shù)非負(fù)，最優(yōu)解為 X＝ (18， 4， 0， 0)T，最優(yōu)值 Z=70 單純形法的計(jì)算步驟設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為 ??????0maxXbAXCXZ 列出初始單純形表，求出檢驗(yàn)數(shù)。 aLK為主元素； （ c）求新的基可行解：用初等行變換方法將 aLK化為１， k 列其它 元素化為零（包括檢驗(yàn)數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。 【 例 】用單純形法求解 ???????????????020531152322m a x321321321321xxxxxxxxxxxxZ、 【解】 將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： ????????????????????5,2,1,020531152322m a x53214321321?jxxxxxxxxxxxxZj 不難看出 x x5 可作為初始基變量，單純法計(jì)算結(jié)果如表 1－ 5 所示。目的是用來求檢驗(yàn)數(shù)（參看例 ）。 容易觀察到 ,系數(shù)矩陣中有一個(gè) 3 階單位矩陣 ,x x x5為基變量。表中 λj≥0,j=1,2,…,5 ，所以最優(yōu)解為 X=(0， 5， 0， 1， 11,)T 最優(yōu)值 Z=2x1－ 2x2－ x4=－ 25－ 1=－ 11。 表 1－ 6 XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 － 1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λ j 1 － 1↑ 0 0 0 x2 x4 x5 1 － 2 4 1 0 0 1 － 1 － 2 0 1 0 0 0 1 5 1 11 λ j 2 0 1 0 0 一章 第五節(jié) 【例 】求解線性規(guī)劃 21max xxZ ??? ????????????042123212121xxxxxx、 【解】化為標(biāo)準(zhǔn)型 121 2 31 2 4m ax3 2 1240, 1, , 4jZ x xx x xx x xxj? ? ?? ? ? ?? ? ? ??? ??? 初始單純形表為見表 1－ 7。由模型可以看出，當(dāng)固定 x1 使 x2→+∞時(shí) Z→+∞且滿足約束條件，還可以用圖解法看出具 有無界解。 表 1－ 8 XB x1 x2 x3 x4 x5 b θ (1) x3 x4 － 1 1 [2] 2 1 0 0 1 0 0 4→ 10 2 5 x5 1 － 1 0 0 1 2 — λ j 2 4↑ 0 0 0 (2) x2 x4 x5 － 1/2 [2] 1/2 1 0 0 1/2 － 1 1/2 0 1 0 0 0 1 2 6→ 4 — 3 8 λ j 4↑ 0 － 2 0 0 (3) x2 x1 x5 0 1 0 1 0 0 1/4 － 1/2 [3/4] 1/4 1/2 － 1/4 0 0 1 7/2 3 5/2→ 14 — 10/3 λ j 0 0 0↑ － 2 0 (4) x2 x1 x3 0 1 0 1 0 0 0 0 1 1/3 1/3 － 1/3 － 1/3 2/3 4/3 8/3 14/3 10/3 λ j 0 0 0 － 2 0 表 1－ 8(3)中 λj全部非正 ,則最優(yōu)解為 20,)25,0,0,27,3()1( ?? ZX T 表 1－ 8(3)表明 ,非基變量 x3 的檢驗(yàn)數(shù) λ3=0， x3若增加 ,目標(biāo)數(shù)值不變 ,即當(dāng) x3 進(jìn)基時(shí) Z 仍等于 20。 多重最優(yōu)解的判斷 最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零 ,則線性規(guī)劃具有多重最優(yōu)解； 無界解的判斷 某個(gè) λk0 且 aik≤０ (i=1， 2,…, m)則線性規(guī)劃具有無界解。 表 1－ 7 XB x1 x2 x3 x4 b x3 x4 3 2 － 2 － 1 1 0 0 1 1 4 λ j － 1 1 0 0 λ2=10,x2進(jìn)基，而 a120， a220，沒有比值，從而線性規(guī)劃的最優(yōu)解無界。 【例 】求解線性規(guī)劃 1212121212m ax 2 4242 1020Z x xxxxxxxxx??? ? ??? ???? ???? ?? 、 【解】化為標(biāo)準(zhǔn)型后用單純形法計(jì)算如表 1－ 8 所示。使 x3 進(jìn)基 x5出基繼續(xù)迭代 ,得到表 1－ 8(4)的另一基本最優(yōu)解 20,),0,0,310,38,314)1( ?? ZX T（ X(1)、 X(2)是線性規(guī)劃的兩個(gè)最優(yōu)解，它的凸組合 )10()1( )2()1( ????? ??? XXX 唯一最優(yōu)解的判斷 最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零 ,則線規(guī)劃具有唯一最優(yōu)解 。 大 M 和兩階段單純形法 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M 法或兩階段法求解，是一種用人工變量作橋梁 的求解方法，也稱為人工變量法。求極小值時(shí)，將目標(biāo)函數(shù)變?yōu)? ? ?? ??? nj mi ijj RMxcZ 1 1mi n 同理，在迭代過程中， Z 要達(dá)到極小化， Ri就會(huì)迅速出基。 表 1－ 9 Cj 3 2 － 1 0 0 － M －M b CB XB x1 x2 x3 x4 x5 x6 x7 －M 0 －M x6 x5 x7 － 4 1 2 3 － 1 － 2 1 2 [1] － 1 0 0 0 1 0 1 0 0 0 0 1 4 10 1→ λ j 3－2M 2+M － 1+2M↑ － M 0 0 0 －M 0 － 1 x6 x5 x3 － 6 － 3 2 [5] 3 － 2 0 0 1 － 1 0 0 0 1 0 1 0 0 3→ 8 1 λ j 5－6M 5M↑ 0 － M 0 0 2 0 － 1 x2 x5 x3 － 6/5 [3/5] － 2/5 1 0 0 0 0 1 － 1/5 3/5 － 2/5 0 1 0 3/5 31/5→ 11/5 λ j 5↑ 0 0 0 0 2 3 － 1 x2 x1 x3 0 1 0 1 0 0 0 0 1 1 1 0 2 5/3 2/3 13 31/3 19/3 λ j 0 0 0 － 5 － 25/3 因?yàn)?λj≤0， j=1,2,…,5, 并且 x6， x7為非基變量，所以最優(yōu)解 3152),0,0,31913,331( ?? ZX T ，最優(yōu)值， 【例 】 求解線性規(guī)劃 ????????????0,426385m in21212121xxxxxxxxZ 【解】 加入松馳變量 x x4化為標(biāo)準(zhǔn)型 ???????????????4,2,1,0426385m in42132121?jxxxxxxxxxZj 在第二個(gè)方程中加入人工變量 x5，目標(biāo)函數(shù)中加上 Mx5一項(xiàng)，得到 ?????????????????5,2,1,0426385m in5421321521?jxxxxxxxxMxxxZj 用單純形法計(jì)算如表 1－ 10 所示。但最優(yōu)解中含有人工變量 x5≠0 說明這個(gè)解是偽最優(yōu)解，是不可行的，因此原問題無可行解。將問題分成兩個(gè)階段求解，第一階段的目標(biāo)函數(shù)是 ??? mi iRw 1min 約束條件是加入 人工變量后的約束方程，當(dāng)?shù)谝浑A段的最優(yōu)解中沒有人工變量作基變量時(shí)，得到原線性規(guī)劃的一個(gè)基本可行解，第二階段就以此為基礎(chǔ)對(duì)原目標(biāo)函數(shù)求最優(yōu)解。 【例 】 用兩階段單純形法求解例 的線性規(guī)劃。 表 1－ 11 Cj 0 0 0 0 0 1 1 b CB XB x1 x2 x3 x4 x5 x6 x7 1 0 1 x6 x5 x7 － 4 1 2 3 － 1 － 2 1 2 [1] － 1 0 0 0 1 0 1 0 0 0 0 1 4 10 1→ λ j 2 － 1 － 2↑ 1 0 0 1 0 0 x6 x5 x3 － 6 － 3 2 [5] 3 － 2 0 0 1 － 1 0 0 0 1 0 1 0 0 3→