1、單純形法例題:某工廠生產(chǎn)I 、II 兩種商品,已知生產(chǎn)單位商品所需的設(shè)備臺(tái)時(shí)、A 、B 兩種原材料的消耗、設(shè)備使用臺(tái)時(shí)限額以及原材料的限額如下表所示。該工廠每生產(chǎn)一件商品I 可獲利3元,每生產(chǎn)一件商品II 可獲利4元。寫(xiě)出使該工廠所獲利潤(rùn)最大的線性規(guī)劃模型, 解:設(shè)生產(chǎn)產(chǎn)品I 的數(shù)量為1x ,生產(chǎn)產(chǎn)品II 的數(shù)量為2x ,所獲利潤(rùn)為z ,相應(yīng)的模型為:+=0,30340243max 21212121x x x x x x x x z標(biāo)準(zhǔn)型=+=+=0,30340243max 432142132121x x x x x x x x x x x x z 用單純形法求解。 T x ,43。(3將初始

2、基,431P P B =對(duì)應(yīng)的基變量按順序填入單純形表中的B X 一列。34BX b1x 2x 3x 4x 3x 4021104x 30131這時(shí),我們可以得到初始基,431P P B =對(duì)應(yīng)的基可行解。即令非基變量0,021=x x ,根據(jù)表中的約束條件可得30,4043=x x (這兩個(gè)值正好是表中基變量對(duì)應(yīng)的資源向量b 對(duì)應(yīng)的分量,為什么?第一個(gè)基可行解為T(mén) X 30,40,0,01=。(4找到了第一個(gè)基可行解,接下來(lái)的任務(wù)就是判斷該基可行解是否為最優(yōu)解,檢驗(yàn)其是否為最優(yōu)解的標(biāo)準(zhǔn)是:非基變量j x 對(duì)應(yīng)的檢驗(yàn)數(shù)j B j j P B C c =1是否0。如果所有非基變量的檢驗(yàn)數(shù)j 均0,

3、那么該基可行解為最優(yōu)解,如果有一個(gè)或若干個(gè)非基變量的檢驗(yàn)數(shù)j 0>,那么該基可行解不是最優(yōu)解,需要繼續(xù)找另一個(gè)基可行解。因?yàn)槲覀冞x擇的初始基I B =1,所以其逆矩陣I B =11。相應(yīng)的,檢驗(yàn)數(shù)j B j j P B C c =1,j B j j P C c =。在計(jì)算檢驗(yàn)數(shù)時(shí)需用到B C (基變量在目標(biāo)函數(shù)中的系數(shù)向量,將B C 填入表格最左一列中。34BC BX b1x 2x 3x 4x 03x 40211004x 30131接下來(lái)就是計(jì)算非基變量的檢驗(yàn)數(shù)(基變量的檢驗(yàn)數(shù)均等于0,為什么?34BC BX b1x 2x 3x 4x 03x 40211004x 301301jB j j

4、 PC c =1(0這時(shí),非基變量的檢驗(yàn)數(shù):(3120,03111=P C c B ,(4310,04222=P C c B ;均>0,所以該基可行解還不是最優(yōu)解。接下來(lái),我們的任務(wù)就是找另一個(gè)基可行解。當(dāng)然,我們希望接下來(lái)的這第二個(gè)基可行解2X 對(duì)應(yīng)的目標(biāo)函數(shù)值比第一個(gè)基可行解1X 對(duì)應(yīng)的目標(biāo)函數(shù)值更接近max 值。(5找另一個(gè)基可行解。由非基變量基變量的決策變量,我們稱之為進(jìn)基變量,挑選原則:0max >j j k =,那么k x 進(jìn)基(即由非基變量變?yōu)榛兞俊Ｓ苫兞糠腔兞康臎Q策變量,我們稱之為出基變量,挑選原則:>0min ik ik i a a b lk l a

5、b=,那么原來(lái)的第l 個(gè)基變量出基(即由基變量變?yōu)榉腔兞俊Ｎ覀兎Qlk a 為主元素,簡(jiǎn)稱主元,在單純形表中用表示。題中,進(jìn)基變量:2214,3max =k ,即2x 進(jìn)基成為基變量。出基變量:=>0min ik ik i a a b 222121,min a b a b =10330,40140min 222a b=,即第2個(gè)基變量出基,第2個(gè)基變量是4x ,所以是4x 出基成為非基變量。主元為22a 。總結(jié):2x 進(jìn)基成為基變量,4x 出基成為非基變量。也就是說(shuō)2x 代替4x 成為基變量,即:34B C BX b1x 2x 3x 4x ikia b 03x 40211040140=0

6、4x 30130110330=jB j j PC c =1(3403x 42x 這時(shí)的基變矢T B x x X ,232=。這兩個(gè)基變量對(duì)應(yīng)的系數(shù)列向量組成的矩陣即為2B 。因?yàn)樵谟?jì)算非基變量的檢驗(yàn)數(shù)的計(jì)算過(guò)程中會(huì)用到12B ,計(jì)算逆矩陣是一件麻煩事,我們當(dāng)然不想干,怎么辦呢?為了計(jì)算簡(jiǎn)便,我們期待I P P B =,232,目前我們只是期待而已。下面先把我們的“期待”填入單純形表中。3400B C BX b1x 2x 3x 4x iki a b 03x 40211040140=04x 30130110330=jB j j PC c =1(340003x 0142x 1jB j j PC c

7、=2(先來(lái)看1X 對(duì)應(yīng)的主元22a 所在的行。行的系數(shù)表示的是約束條件:421330x x x +=。對(duì)應(yīng)于2X ,我們期待的是:在這個(gè)約束條件中,2x 的系數(shù)=1,3x 的系數(shù)=0。要做到這一點(diǎn),只需在等式左右同除以3(主元22a 本身,得421313110x x x +=,式與式等價(jià)。接著看另一行。即第一行,該行的系數(shù)表示的是約束條件:321240x x x +=。對(duì)應(yīng)于2X ,我們期待的是:在這個(gè)約束條件中,2x 的系數(shù)=0,3x 的系數(shù)=1。要做到這一點(diǎn),需要將-×1431313530x x x +=,式與式等價(jià)。為實(shí)現(xiàn)我們的期待,將約束條件+=+=421321330240x

8、 x x x x x 就等價(jià)的代換成3400B C BX b1x 2x 3x 4x iki a b 03x 40211040140=04x 30130110330=jB j j PC c =1(340003x 3035013142x 1031131jB j j PC c =2(這時(shí),我們可以得到基,232P P B =對(duì)應(yīng)的基可行解。即令非基變量0,041=x x ,根據(jù)表中的約束條件可得10,3023=x x (這兩個(gè)值正好是表中基變量對(duì)應(yīng)的資源向量b 對(duì)應(yīng)的分量那么,第2個(gè)基可行解為T(mén) X 0,30,10,02=。(6找到了第2個(gè)基可行解,接下來(lái)的任務(wù)就是判斷該基可行解是否為最優(yōu)解,檢驗(yàn)其

9、是否為最優(yōu)解的標(biāo)準(zhǔn)前面已經(jīng)詳細(xì)講述,這里就不啰唆了。即轉(zhuǎn)回到步驟(4。34B C BX b1x 2x 3x 4x ikia b 03x 40211040140=04x 30130110330=jB j j PC c =1(34003x 303501314 x2 10 j ( 2 = c j C B Pj 這時(shí)，非基變量的檢驗(yàn)數(shù) 1 = 1 3 5 3 1 0 0 0 1 3 4 3 5 4 , 4 = ，其中 1 > 0 ，所以該基可行解不是最優(yōu)解。 3 3 （7）接下來(lái)，我們的任務(wù)就是找另一個(gè)基可行解。即轉(zhuǎn)回到步驟（5） 。 5 選擇進(jìn)基變量： max 1 = = k = 1 ，即 x

10、1 進(jìn)基成為基變量。 3 出基變量： min b1 b2 3 b1 ，即第 1 個(gè)基變量出基， 第 , = min 30 × = 18,10 × 3 = 30 = 5 a11 a11 a 21 1 個(gè)基變量是 x3 ，所以是 x3 出基成為非基變量。主元為 a11 。 總結(jié)： x1 進(jìn)基成為基變量， x3 出基成為非基變量。也就是說(shuō) x1 代替 x3 成為基變量，即： 3 4 0 0 CB XB b x1 x2 x3 x4 bi aik 40 = 40 1 0 x3 x4 40 2 1 1 0 0 30 1 3 3 4 0 0 1 0 30 = 10 3 j (1 = c

11、j C B Pj 0 x3 x2 30 5 3 1 3 5 3 0 1 1 3 1 3 4 3 3 30 × = 18 5 10 × 3 = 30 4 10 1 0 0 0 j ( 2 = c j C B Pj 3 4 x1 x2 j (3 = c j C B Pj 這時(shí)的基變矢 X B 3 = x1 , x 2 T 。這兩個(gè)基變量對(duì)應(yīng)的系數(shù)列向量組成的矩陣即為 B3 。 第 6 頁(yè) 共 9 頁(yè) 同樣的，我們期待 B3 = P1 , P 2 = I 。 3 4 0 0 CB XB b x1 x2 x3 x4 bi aik 40 = 40 1 0 x3 x4 40 2 1 1

12、 0 0 30 1 3 3 4 0 0 1 0 30 = 10 3 j (1 = c j C B Pj 0 x3 x2 30 5 3 1 3 5 3 1 0 0 1 1 3 3 30 × = 18 5 4 10 1 0 0 1 0 0 j ( 2 = c j C B Pj 3 4 1 3 4 3 10 × 3 = 30 x1 x2 j (3 = c j C B Pj 先來(lái)看主元 a11 所在的行。行的系數(shù)表示的是約束條件： 30 = 5 1 x1 + x3 x 4 。 3 3 我們期待的是：在約束條件中， x1 的系數(shù)1， x 2 的系數(shù)0。要做到這一點(diǎn)，只需在等式 5 3

13、 1 （主元 a11 本身） ，得 18 = x1 + x3 x 4 ，式與式等價(jià)。 3 5 3 1 1 接著看另一行。即第二行，該行的系數(shù)表示的是約束條件： 10 = x1 + x 2 + x 4 。 3 3 左右同除以 我們期待的是：在約束條件中， x1 的系數(shù)0， x 2 的系數(shù)1。 要做到這一點(diǎn)，需要將 1 1 2 × 4 = x 2 x3 + x 4 ，式與式 3 5 5 第 7 頁(yè) 共 9 頁(yè) 等價(jià)。 5 1 3 1 30 = 3 x1 + x3 3 x 4 18 = x1 + 5 x3 5 x 4 約束條件 就等價(jià)的代換成 1 1 1 2 10 = x1 + x 2 +

14、 x 4 4 = x 2 x3 + x 4 3 3 5 5 將這些系數(shù)填入表格中。 3 4 0 0 CB XB b x1 x2 x3 x4 bi aik 40 = 40 1 0 x3 x4 40 2 1 1 0 0 30 1 3 3 4 0 0 1 0 30 = 10 3 j (1 = c j C B Pj 0 x3 x2 30 5 3 1 3 5 3 1 0 0 1 1 3 3 30 × = 18 5 4 10 1 0 0 1 0 0 j ( 2 = c j C B Pj 3 4 x1 x2 18 4 3 5 1 5 1 3 4 3 1 5 2 5 10 × 3 = 30

15、 j (3 = c j C B Pj 這時(shí)，我們可以得到基 B3 = P1 , P2 對(duì)應(yīng)的基可行解。 即令非基變量 x3 = 0, x 4 = 0 ，根據(jù)表中的約束條件可得 x1 = 18, x 2 = 4 （這兩個(gè)值正好是表 中基變量對(duì)應(yīng)的資源向量 b 對(duì)應(yīng)的分量） 那么，第 3 個(gè)基可行解為 X 3 = 18,4,0,0T 。 （8）找到了第 3 個(gè)基可行解，接下來(lái)的任務(wù)就是判斷該基可行解是否為最優(yōu)解，檢驗(yàn)其是 否為最優(yōu)解的標(biāo)準(zhǔn)前面已經(jīng)詳細(xì)講述，這里就不啰唆了。即轉(zhuǎn)回到步驟（4） 。 第 8 頁(yè) 共 9 頁(yè) 3 4 0 0 CB XB b x1 x2 x3 x4 bi aik 40 = 40 1 0 x3 x4 40 2 1 1 0 0 30 1 3 3 4 0 0 1 0 30 = 10 3 j (1 = c j C B Pj 0 x3 x2 30 5 3 1 3 5 3 1 0 0 0 1 1 3 1 3 4 3 1 5