(第二章 線性規(guī)劃)

1、衛(wèi)生管理運籌學(xué)衛(wèi)生管理運籌學(xué)計算機教學(xué)中心計算機教學(xué)中心王曉娜王曉娜15836185939158361859392表格單純形法的求解步驟：表格單純形法的求解步驟： 1.找出初始基本可行解，建立初始單純形表。找出初始基本可行解，建立初始單純形表。步。結(jié)束。否則，轉(zhuǎn)入下一優(yōu)值算最，則已得到最優(yōu)解，計若對所有檢驗數(shù)檢驗對應(yīng)于非基變量的,bczn),1,2,(j0,C,C. 2im1iijj算，否則轉(zhuǎn)入下一步。計解或無最優(yōu)解），停止最優(yōu)解，（或稱有無界則此問題無有限均有，向量，對的系數(shù)列對應(yīng)中，若有一個在所有, 0am, 21ixC 0C. 3ikkkj3 表格單純形法的求解步驟（續(xù)）：表格單純形法的

2、求解步驟（續(xù)）： 為出基變量。確定依據(jù)“最小比值規(guī)則”為進基變量，再，確定根據(jù)llklikikiikkjxab0aabminminxC0)Cmax(. 4 5.實施以樞元素為中心的初等變換，使約束方程實施以樞元素為中心的初等變換，使約束方程組變?yōu)殛P(guān)于新的基本變量的典型方程組，得到組變?yōu)殛P(guān)于新的基本變量的典型方程組，得到新的單純形表。重復(fù)第二步，新的單純形表。重復(fù)第二步，一直到?jīng)]有，一直到?jīng)]有新的基本變量可以改善目標(biāo)函數(shù)為止。新的基本變量可以改善目標(biāo)函數(shù)為止。4對下列對下列LP模型標(biāo)準(zhǔn)化后用單純形法求解模型標(biāo)準(zhǔn)化后用單純形法求解4321xx3inzxxm4 , 3 , 2 , 1, 063422

3、t . s421321jxxxxxxxj例例24321xxx3xzmax, zz化為標(biāo)準(zhǔn)形式：令4 , 3 , 2 , 1, 063422t . s421321jxxxxxxxj5CBcj-3-1-1-1bx1x2x3x4-1x3-22 104 -1x431016Cj-1x2-111/202-1x440-1/214CjXBXj單純形法運算如下：單純形法運算如下： 在產(chǎn)生最優(yōu)值的單純形表中，非基變量在產(chǎn)生最優(yōu)值的單純形表中，非基變量x1的檢驗數(shù)為的檢驗數(shù)為0，意味，意味著著x1做任何的增大，目標(biāo)函數(shù)最優(yōu)值做任何的增大，目標(biāo)函數(shù)最優(yōu)值z不變。此時的不變。此時的LP問題的最問題的最優(yōu)解不唯一，有多重

4、最優(yōu)解。（換基運算過程見后頁）優(yōu)解不唯一，有多重最優(yōu)解。（換基運算過程見后頁） 26Z=CBb=-10Z=-6-220000-106CBcj-3-1-1-1bx1x2x3x4-1x2-111/202-1x440-1/214Cj00-10Z=-6XBXj換基尋找另一最優(yōu)解運算如下：換基尋找另一最優(yōu)解運算如下： 在產(chǎn)生最優(yōu)值的單純形表中，非基變量在產(chǎn)生最優(yōu)值的單純形表中，非基變量x4的檢驗數(shù)為的檢驗數(shù)為0，意味，意味著著x4做任何的增大，目標(biāo)函數(shù)最優(yōu)值做任何的增大，目標(biāo)函數(shù)最優(yōu)值z不變。此時的不變。此時的LP問題的最問題的最優(yōu)解不唯一，有多重最優(yōu)解。優(yōu)解不唯一，有多重最優(yōu)解。 -1x2013/81

5、/43-3x110-1/81/41Cj00-10Z=-617對下列對下列LP模型標(biāo)準(zhǔn)化后用單純形法求解模型標(biāo)準(zhǔn)化后用單純形法求解2123zaxxxm2 , 1, 03322t . s2121jxxxxxj例例3212x3xmaxz化為標(biāo)準(zhǔn)形式：4 , 3 , 2 , 1, 03322t . s421321jxxxxxxxj畫出最終單畫出最終單純形表，判純形表，判斷找到的解斷找到的解為何種解？為何種解？ 8CBcj3200bx1x2x3x40 x3-211020 x41-3013Cj3200Z=CBb=00 x30-51283x11-3013Cj XBXj 在最終單純形表中，存在檢驗數(shù)在最終單純

6、形表中，存在檢驗數(shù)Cj=110，而其，而其對應(yīng)的列向量對應(yīng)的列向量P2=（-5，-3）02.按按最小比值最小比值 規(guī)則計算，若存在兩個相同以上最小比規(guī)則計算，若存在兩個相同以上最小比值時，選取下標(biāo)最小的基變量為換出變量值時，選取下標(biāo)最小的基變量為換出變量xl，即，即0|min|minikikiraabrL退化解退化解 教材第教材第3737頁（頁（5 5）退化解：）退化解：即計算出的即計算出的存在有存在有兩個以上相同的最小比值，會造成下一次迭代中有兩個以上相同的最小比值，會造成下一次迭代中有一一個或幾個基變量等于個或幾個基變量等于0 0，可能導(dǎo)致計算過程的循環(huán)，可能導(dǎo)致計算過程的循環(huán)，B1 B2

7、B1這樣迭代下去，這樣迭代下去，永遠得不到最優(yōu)永遠得不到最優(yōu)解。解。 值得慶幸的是出現(xiàn)基循環(huán)是罕見的。值得慶幸的是出現(xiàn)基循環(huán)是罕見的。10 對于極小化問題，也可跟據(jù)單純形法求解的基本思想，對于極小化問題，也可跟據(jù)單純形法求解的基本思想，直接用單純形表求解。不同之處在于改變檢驗數(shù)判別方直接用單純形表求解。不同之處在于改變檢驗數(shù)判別方法，以確定進基變量。法，以確定進基變量。 Cj0,則已得到最優(yōu)解。則已得到最優(yōu)解。 Cj0，若有一個，若有一個Cj對應(yīng)對應(yīng)X Xk k的系數(shù)列向量，即對的系數(shù)列向量，即對i=1,2,m, 均有均有aik0,則該則該LP問題有無界解。否則應(yīng)選擇檢驗數(shù)問題有無界解。否則應(yīng)

8、選擇檢驗數(shù)為負值且絕對值最大的變量進基。為負值且絕對值最大的變量進基。最小化問題直接用單純形法運算最小化問題直接用單純形法運算kjC)0C(min 出基變量的判別方法與最大化問題相同。出基變量的判別方法與最大化問題相同。 對上例對上例2最小化問題直接用單純形表求解如下：最小化問題直接用單純形表求解如下：11CBcj3111bx1x2x3x41x3-22 104 1x431016Cj1x2-111/2021x44 0-1/214CjXBXj1x2013/81/433x110-1/81/41Cj 2-200Z=CBb=10260010Z=61Z=6001012 注意：單純形法中，注意：單純形法中，

9、 1.每一步運算只能用矩陣初等行變換；每一步運算只能用矩陣初等行變換； 2.表中表中b列的數(shù)總應(yīng)保持非負（列的數(shù)總應(yīng)保持非負（ 0）；）； 3.當(dāng)所有檢驗數(shù)均非正（當(dāng)所有檢驗數(shù)均非正（ 0）時，得）時，得到最優(yōu)單純形表。到最優(yōu)單純形表。 注：極小化時檢驗數(shù)為非負（注：極小化時檢驗數(shù)為非負（0）線性規(guī)劃的單純形法線性規(guī)劃的單純形法13對下列對下列LP模型建立初始單純形表并求解模型建立初始單純形表并求解例例421410maxxxz2 , 1, 01292123821.212121jxxxxxxxtsj診療問題（教診療問題（教材第材第3838頁）：頁）：在求解過程中在求解過程中觀察單純形表觀察單純形

10、表中基本可行解中基本可行解和目標(biāo)函數(shù)值和目標(biāo)函數(shù)值的變化。的變化。14CBcj104000bx1x2x3x4 x50 x311/210080 x43/21/201090 x51100112Cj 診療問題（教材第診療問題（教材第38頁）：化為標(biāo)準(zhǔn)形后，得頁）：化為標(biāo)準(zhǔn)形后，得 max z=10 x1+4x2 s.t. x1+x2/2+x3=8 3x1/2+x2/2 +x4= 9 x1+x2+x5 =12 xj 0,j=1,2,3,4,5 XBXj 8612104000Z=015CBcj104000bx1x2x3x4 x50 x311/2100880 x43/21/2010960 x5110011

11、212Cj104000Z=00 x301/61 -2/30210 x111/302/3060 x502/30-2/316 CjXBXj 0 x3001-1/2-1/41/210 x11001-1/234x2010-13/29Cj 12189Z=60Z=6602/30-20/30000-6-116課后習(xí)題一第課后習(xí)題一第6題（題（P46頁）。頁）。 6.考慮下面線性規(guī)劃問題考慮下面線性規(guī)劃問題 max z=5x1+9x2 0.5x1+x28 s.t. x1+x2 10 x1+0.5x212 xj 0,j=1,2（1）寫出該線性規(guī)劃問題的標(biāo)準(zhǔn)形；）寫出該線性規(guī)劃問題的標(biāo)準(zhǔn)形；（2）在這個線性規(guī)劃問

12、題中，將至少有多少個變量）在這個線性規(guī)劃問題中，將至少有多少個變量的取值為零？為什么？的取值為零？為什么？（3）在這個線性規(guī)劃問題中，共有多少個基本解？）在這個線性規(guī)劃問題中，共有多少個基本解？（4）圖解法求解次線性規(guī)劃問題的可行域，并求出）圖解法求解次線性規(guī)劃問題的可行域，并求出最優(yōu)解和最優(yōu)值。最優(yōu)解和最優(yōu)值。17 （1） max z=5x1+9x2 0.5x1+x2+x3=8 s.t. x1+x2 +x4=10 x1+0.5x2 -x5=12 xj 0，j=1，2，3，4，5 （2）至少有）至少有2個變量的值取零，因為有個變量的值取零，因為有3個基個基本變量、本變量、2個非基本變量，非基本

13、變量的取值個非基本變量，非基本變量的取值為零。為零。 （3）共有）共有10種基本解。種基本解。 （C52 = C53=10） （4）最優(yōu)解）最優(yōu)解X =（4，6，0，0，1）T， Max Z=74。 18 課后習(xí)題一第課后習(xí)題一第8題（題（P4647頁）。頁）。 第第8題：（題：（1）求）求ag的值的值； （2）是否為最優(yōu)解？）是否為最優(yōu)解？ 若為最優(yōu)解，為何種若為最優(yōu)解，為何種 最優(yōu)解？最優(yōu)解？CBcj2812000bx1x2x3x4 x5x62x301130-14/3a0 x505/206d2528x11000ef0Cj0-1gbc0Z=14XBXj19CBcj2812000bx1x2x3

14、x4 x5x62x301130-14/3a0 x505/206d2528x11000ef0Cj0-1gbc0Z=14XBXj解：解： （1）2 a=14； b=0-2*3=-6；0-（-14/3*2）- 28*f=0 a=7，b=-6，c=0，d=1，e=0，f=1/3，g=0。 （2）C6=0，為多重最優(yōu)解。為多重最優(yōu)解。20 思考題：思考題： 某線性規(guī)劃的目標(biāo)函數(shù)是某線性規(guī)劃的目標(biāo)函數(shù)是maxzmaxz，在用標(biāo)準(zhǔn)的單純形法求解的過程，在用標(biāo)準(zhǔn)的單純形法求解的過程中，得到下表（其中中，得到下表（其中a a是常數(shù)，部分?jǐn)?shù)據(jù)有缺失）。是常數(shù)，部分?jǐn)?shù)據(jù)有缺失）。 1.1.在所有的空格中填上適當(dāng)?shù)臄?shù)或式子（其中可含參數(shù)在所有的空格中填上適當(dāng)?shù)臄?shù)或式子（其中可含參數(shù)a a）。）。 2.2.判斷以下四種情況在什么時候成立，并簡要說明理由。判斷以下四種情況在什么時候成立，并簡要說明理由。 （1 1）此解為最優(yōu)解，試寫出相應(yīng)的解和目標(biāo)函數(shù)值；）此解為最優(yōu)解，試寫出相應(yīng)的解和目標(biāo)函數(shù)值； （2 2）此線性規(guī)劃有無窮多最優(yōu)解；）此線性規(guī)劃有無窮多最優(yōu)解； （3 3）此線性規(guī)劃有無界解；）此線性規(guī)劃有無界解； （4 4）此解不是最優(yōu)解，且能用單純形法得到下一個基本可行解。）此解不是最優(yōu)解，且能用單純形法得到下一個基本可行解。cj258000CBXBbx1x2x3x4x5x6x6