【文章內(nèi)容簡(jiǎn)介】 1 17/3 28/9 1/3 － 1/9 1 2/3 25 35/3 λ j 0 0 － 98/9 － 1/9 －7/3 【例 】 用單純形法求解 1 2 41 2 31 2 41 2 5m in 2 2566 2 210 , 1, , 5jZ x x xx x xx x xx x xxj? ? ?? ? ???? ? ? ??? ? ? ??? ??? 【 解】 這是一個(gè)極小化的線性規(guī)劃問題 ,可以將其化為極大化問題求解 ,也可以直接求解 ,這時(shí)判斷標(biāo)準(zhǔn)是： λj≥0(j=1， … ， n)時(shí)得到最優(yōu)解。 容易觀察到 ,系數(shù)矩陣中有一個(gè) 3 階單位矩陣 ,x x x5為基變量。目標(biāo)函數(shù)中含有基變量 x4,由第二個(gè)約束得到 x4=6+x1－ x2，并代入目標(biāo)函數(shù)消去 x4 得 212121 6)6(22 xxxxxxZ ????????＝ 單純形法計(jì)算如表 1－ 6 所示。表中 λj≥0,j=1,2,…,5 ，所以最優(yōu)解為 X=(0， 5， 0， 1， 11,)T 最優(yōu)值 Z=2x1－ 2x2－ x4=－ 25－ 1=－ 11。 求極小值問題時(shí) ,注意判斷標(biāo)準(zhǔn) ,選進(jìn)基變量時(shí)應(yīng)選 λj0的變量進(jìn)基。 表 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。 表 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)解無界。由模型可以看出，當(dāng)固定 x1 使 x2→+∞時(shí) Z→+∞且滿足約束條件，還可以用圖解法看出具 有無界解。 【例 】求解線性規(guī)劃 1212121212m ax 2 4242 1020Z x xxxxxxxxx??? ? ??? ???? ???? ?? 、 【解】化為標(biāo)準(zhǔn)型后用單純形法計(jì)算如表 1－ 8 所示。 表 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。使 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)解 。 多重最優(yōu)解的判斷 最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零 ,則線性規(guī)劃具有多重最優(yōu)解； 無界解的判斷 某個(gè) λk0 且 aik≤０ (i=1， 2,…, m)則線性規(guī)劃具有無界解。 例 】求解線性規(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。 表 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)解無界。由模型可以看出，當(dāng)固定 x1 使 x2→+∞時(shí) Z→+∞且滿足約束條件，還可以用圖解法看出具有無界解。 【例 】求解線性規(guī)劃 1212121212m ax 2 4242 1020Z x xxxxxxxxx??? ? ??? ???? ???? ?? 、 【解】化為標(biāo)準(zhǔn)型后用單純形法計(jì)算如表 1－ 8 所示。 表 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。使 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)解 。 多重最優(yōu)解的判斷 最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零 ,則線性規(guī)劃具有多重最優(yōu)解； 無界解的判斷 某個(gè) λk0 且 aik≤０ (i=1， 2,…, m)則線性規(guī)劃具有無界解。 大 M 和兩階段單純形法 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M 法或兩階段法求解，是一種用人工變量作橋梁 的求解方法，也稱為人工變量法。 一 、 大 M 單純形法 大 M 單純形法的基本思想是：約束條件加入人工變量后，求極大值時(shí)，將目標(biāo)函數(shù)變?yōu)? ? ??? nj mi ijj RMxcZ 1 1m a x ＝ ＝ 式中 M 為很大的正數(shù)，因而－ MRi 為很小的負(fù)數(shù)，在迭代過程中， Z 要達(dá)到極大化， Ri 就會(huì)很快出基。求極小值時(shí)，將目標(biāo)函數(shù)變?yōu)? ? ?? ??? nj mi ijj RMxcZ 1 1mi n 同理，在迭代過程中， Z 要達(dá)到極小化， Ri就會(huì)迅速出基。 【例 】 用大 M 單純形法求解下列線性規(guī)劃 ???????????????????????012210243423m ax321321321321321xxxxxxxxxxxxxxxZ、 【 解】 首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 ????????????????????????5,2,1,012210243423m ax32153214321321?jxxxxxxxxxxxxxxxZj 式中 x x5為松弛變量， x5可作為一個(gè)基變量，第一、三約束中分別加入人 工變量 x x7，目標(biāo)函數(shù)中加入 ―M x6―M x7 一項(xiàng)，得到大 M 單純形法數(shù)學(xué)模型 ???????????????????????????7,2,1,012210243423m ax732153216432176321?jxxxxxxxxxxxxxxMxMxxxxZj－ 再用前面介紹的單純形法求解，見表 1－ 9 所示。 表 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)值， 【例 】