運(yùn)籌學(xué)2線性-3

1、 2022-6-412022-6-422022-6-43 1. 1. 單純形方法的推導(dǎo)單純形方法的推導(dǎo)2. 2. 單純形計(jì)算表單純形計(jì)算表3. 3. 單純形方法的基本定理單純形方法的基本定理4. 4. 如何尋找初始可行解如何尋找初始可行解2022-6-442022-6-452.4.1. 2.4.1. 單純形方法推導(dǎo)單純形方法推導(dǎo)單純形方法的基本思單純形方法的基本思想想 從可行域的一個(gè)基本可從可行域的一個(gè)基本可行解行解( (極點(diǎn)極點(diǎn)) )出發(fā)，判別它是出發(fā)，判別它是否已是最優(yōu)解，如果不是，否已是最優(yōu)解，如果不是，尋找下一個(gè)基本可行解，并尋找下一個(gè)基本可行解，并使目標(biāo)函數(shù)得到改進(jìn)，如此使目標(biāo)函數(shù)得

2、到改進(jìn)，如此迭代下去，直到找到最優(yōu)解迭代下去，直到找到最優(yōu)解或判定問(wèn)題無(wú)界為止?；蚺卸▎?wèn)題無(wú)界為止。2022-6-46 求解線性規(guī)劃：求解線性規(guī)劃：max z = 50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1, x2 02022-6-47 max z = 50 x1+ 30 x2 s.t. 4x1 + 3x2 + x3 = 120 2x1 + x2 + x4 = 50 x1 , x2 , x3 , x4 0 選選 x3 , x4 為基變量為基變量轉(zhuǎn)換為典則形式轉(zhuǎn)換為典則形式 ： max z = 50 x1 + 30 x2 s.t.x3 = 12

3、0 - 4x1 - 3x2 x4 = 50 - 2x1 - x2 x1 , x2 , x3 , x4 0將原問(wèn)題轉(zhuǎn)化為將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型模型標(biāo)準(zhǔn)型模型：2022-6-48（用非基變量表示（用非基變量表示基變量和目標(biāo)函數(shù)基變量和目標(biāo)函數(shù)的形式稱為關(guān)于基的形式稱為關(guān)于基的典則形式）的典則形式）尋找初始可行解：尋找初始可行解：令非基變量為零，令非基變量為零， 得到：得到： x(1) = (0, 0, 120, 50) ， z(1) = 0最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) :該解是最優(yōu)解嗎？該解是最優(yōu)解嗎？第一次換基迭代第一次換基迭代 選選x1入基（系數(shù)為正有利于入基（系數(shù)為正有利于z增加、最大增加增加、最大增

4、加原則）。得到下列不等式關(guān)系原則）。得到下列不等式關(guān)系:2022-6-49 x3 = 120 - 4x1 - 3x2 0 x4 = 50 - 2x1 - x2 0 簡(jiǎn)化為：簡(jiǎn)化為：120 - 4x1 0 50 - 2x1 0 選選 x1= min(120/4, 50/2) = 25（最小比值原則或（最小比值原則或原則）原則）, 才使上述不等式成立，并迫使才使上述不等式成立，并迫使 x4 為零；為零；因此需令因此需令 x4 出基。出基。2022-6-410新的典則方程變?yōu)樾碌牡鋭t方程變?yōu)?4x1 + x3 = 120 - 3x22x1 = 50 - x2 - x4化簡(jiǎn)后：化簡(jiǎn)后： z(2) =

5、1250 + 5x2 - 25x4 x1 = 25 - 0.5x2 - 0.5x4 x3 = 20 - x2 + 2x4第二個(gè)基本可行解第二個(gè)基本可行解 (25, 0, 20, 0) , z(2)=12502022-6-411第二次換基迭代第二次換基迭代 選選 x2入基。得到下列不等式關(guān)系入基。得到下列不等式關(guān)系:x1 = 25 - 0.5x2 - 0.5x4 0 x3 = 20 - x2 + 2x4 0 簡(jiǎn)化為：簡(jiǎn)化為：25 - 0.5x2 0 20 - x2 0 選選 x2 = min(25/0.5, 20/1) = 20 時(shí)才能使不等時(shí)才能使不等式成立，并使式成立，并使 x3為零，令為零

6、，令 x3 出基。出基。2022-6-412換基后的典則形式變?yōu)椋簱Q基后的典則形式變?yōu)椋簔(3) = 1350 - 5x3 - 15x4x1 = 15 + 0.5x3 - 1.5x4x2 = 20 - x3 + 2x4 第三個(gè)解為第三個(gè)解為(15, 20, 0, 0) ，z(3) = 1350； 此時(shí)，此時(shí)，目標(biāo)函數(shù)表達(dá)式中非基變量的目標(biāo)函數(shù)表達(dá)式中非基變量的系數(shù)系數(shù)都為負(fù)都為負(fù)，目標(biāo)函數(shù)無(wú)法繼續(xù)改進(jìn)，為，目標(biāo)函數(shù)無(wú)法繼續(xù)改進(jìn)，為最優(yōu)解最優(yōu)解。2022-6-413考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題：考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題：Max z = c1x1 + c2x2 + + cnxn s.t. a11

7、x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 . . . am1 x1 + am2 x2 + + amn xn = bm x1 , x2 , , xn 02022-6-4 x1 c1 b1 a11 a12.a1n x2 c2 b2 a21 a22.a2nx = . C= . b= . A= . . . . . . . . . xn cn bm am1 am2.amn 14 這里，矩陣這里，矩陣A表示為：表示為： A = ( p1 ，p2 ，pn ) ， 其中其中 pj = ( a1j ，a2j ，amj )T Rm。若。

8、若找到一個(gè)可行基，不妨設(shè)找到一個(gè)可行基，不妨設(shè) B = ( p1 ，p2 ，pm ) ， 則則m個(gè)基變量為個(gè)基變量為 x1 , x2 , , xm，n-m個(gè)非個(gè)非基變量為基變量為 xm+1 ，xm+2 ，xn 。通過(guò)運(yùn)算，。通過(guò)運(yùn)算，所有的基變量都可以用非基變量來(lái)表示所有的基變量都可以用非基變量來(lái)表示：2022-6-415 x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn） (1 ) . . . xm=bm-（amm+1xm+1+amm+2xm+2+amnxn） 把它們代入目標(biāo)函數(shù)，得把它們代入目標(biāo)函數(shù)，得 z

9、 = z+ m+1xm+1+ m+2xm+2+ nxn (2 ) 其中其中 j=cj-（c1a1j + c2a2j + + cm amj） 我們把由非基變量表示的目標(biāo)函數(shù)形式稱為我們把由非基變量表示的目標(biāo)函數(shù)形式稱為基基B相應(yīng)的目標(biāo)函數(shù)典式相應(yīng)的目標(biāo)函數(shù)典式。2022-6-416單純形法的基本步驟可描述如下：?jiǎn)渭冃畏ǖ幕静襟E可描述如下： （1）尋找一個(gè)初始的可行基和相應(yīng)基本尋找一個(gè)初始的可行基和相應(yīng)基本可行解（極點(diǎn)）。確定基變量、非基變量可行解（極點(diǎn)）。確定基變量、非基變量以及基變量、非基變量（全部等于以及基變量、非基變量（全部等于0 0）和目）和目標(biāo)函數(shù)的值，并標(biāo)函數(shù)的值，并將目標(biāo)函數(shù)和基

10、變量分別將目標(biāo)函數(shù)和基變量分別用非基變量表示用非基變量表示；2022-6-417 max z = 50 x1+ 30 x2 s.t. 4x1 + 3x2 + x3 = 120 2x1 + x2 + x4 = 50 x1 , x2 , x3 , x4 0 選選 x3 , x4 為基變量為基變量轉(zhuǎn)換為典則形式轉(zhuǎn)換為典則形式 ： max z = 50 x1 + 30 x2 s.t.x3 = 120 - 4x1 - 3x2 x4 = 50 - 2x1 - x2 x1 , x2 , x3 , x4 0將原問(wèn)題轉(zhuǎn)化為將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型模型標(biāo)準(zhǔn)型模型：2022-6-418（用非基變量表示（用非基變量表示基

11、變量和目標(biāo)函數(shù)基變量和目標(biāo)函數(shù)的形式稱為關(guān)于基的形式稱為關(guān)于基的典則形式）的典則形式）例例 （2）在用非基變量表示的目標(biāo)函數(shù)表達(dá)式（在用非基變量表示的目標(biāo)函數(shù)表達(dá)式（2）中，我們稱中，我們稱非基變量非基變量xj的系數(shù)為檢驗(yàn)數(shù)記為的系數(shù)為檢驗(yàn)數(shù)記為 j 。若。若 j 0，那么相應(yīng)的非基變量，那么相應(yīng)的非基變量xj，它的值從當(dāng)前值，它的值從當(dāng)前值0開(kāi)始增加時(shí)，目標(biāo)函數(shù)值隨之增加。這個(gè)選定的開(kāi)始增加時(shí)，目標(biāo)函數(shù)值隨之增加。這個(gè)選定的非基變量非基變量xj稱為稱為“進(jìn)基變量進(jìn)基變量”，轉(zhuǎn)（，轉(zhuǎn)（3）。如果任）。如果任何一個(gè)非基變量的值增加都不能使目標(biāo)函數(shù)值增何一個(gè)非基變量的值增加都不能使目標(biāo)函數(shù)值增加，

12、即加，即所有所有 j 非正，則當(dāng)前的基本可行解就是最非正，則當(dāng)前的基本可行解就是最優(yōu)解優(yōu)解，計(jì)算結(jié)束；，計(jì)算結(jié)束；2022-6-419尋找初始可行解：尋找初始可行解：令非基變量為零，令非基變量為零， 得到：得到： x(1) = (0, 0, 120, 50) ， z(1) = 0最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) :該解是最優(yōu)解嗎？該解是最優(yōu)解嗎？第一次換基迭代第一次換基迭代選選 x1入基（系數(shù)大有利于入基（系數(shù)大有利于z增加）。增加）。2022-6-420例例2022-6-421問(wèn)題：?jiǎn)栴}：選擇非基變量進(jìn)基的原則？選擇非基變量進(jìn)基的原則？1.任意一個(gè)任意一個(gè)2.任意一個(gè)正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量任意一個(gè)正檢驗(yàn)

13、數(shù)對(duì)應(yīng)的非基變量3.最大正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量最大正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量4.排在最前面的正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量排在最前面的正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量X （3）在用非基變量表示的基變量的表達(dá)式（在用非基變量表示的基變量的表達(dá)式（1）中，觀察進(jìn)基變量增加時(shí)各基變量變化情況，確中，觀察進(jìn)基變量增加時(shí)各基變量變化情況，確定基變量的值在進(jìn)基變量增加過(guò)程中首先減少到定基變量的值在進(jìn)基變量增加過(guò)程中首先減少到0的變量的變量xr ，滿足，滿足， =min bi /aij aij 0 = br /arj這個(gè)基變量這個(gè)基變量xr稱為稱為“出基變量出基變量”。當(dāng)進(jìn)基變量的值。當(dāng)進(jìn)基變量的值增加到增加到 時(shí)，出基變量時(shí)，

14、出基變量xr的值降為的值降為0時(shí)，可行解就時(shí)，可行解就移動(dòng)到了相鄰的基本可行解（極點(diǎn)），轉(zhuǎn)（移動(dòng)到了相鄰的基本可行解（極點(diǎn)），轉(zhuǎn)（4）。）。2022-6-422 x3 = 120 - 4x1 - 3x2 0 x4 = 50 - 2x1 - x2 0 簡(jiǎn)化為：簡(jiǎn)化為：120 - 4x1 0 50 - 2x1 0 選選 x1= min(120/4, 50/2) = 25（最小比值原則或（最小比值原則或原則）原則）, 才使上述不等式成立，并迫使才使上述不等式成立，并迫使 x4 為零；為零；因此需令因此需令 x4 出基。出基。2022-6-423例例如果進(jìn)基變量的值增加時(shí)，所有基變量的值都不減如果進(jìn)基

15、變量的值增加時(shí)，所有基變量的值都不減少，即少，即所有所有aij 非正非正，則表示可行域是不封閉的，且，則表示可行域是不封閉的，且目標(biāo)函數(shù)值隨進(jìn)基變量的增加可以無(wú)限增加，此時(shí)，目標(biāo)函數(shù)值隨進(jìn)基變量的增加可以無(wú)限增加，此時(shí)，不存在有限最優(yōu)解不存在有限最優(yōu)解，計(jì)算結(jié)束；，計(jì)算結(jié)束； （4）將進(jìn)基變量作為新的基變量，出基變量作將進(jìn)基變量作為新的基變量，出基變量作為新的非基變量，確定新的基、新的基本可行解和為新的非基變量，確定新的基、新的基本可行解和新的目標(biāo)函數(shù)值。在新的基變量、非基變量的基礎(chǔ)新的目標(biāo)函數(shù)值。在新的基變量、非基變量的基礎(chǔ)上上重復(fù)重復(fù)（1）。）。2022-6-424新的典則方程變?yōu)樾碌牡鋭t

16、方程變?yōu)?4x1 + x3 = 120 - 3x22x1 = 50 - x2 - x4化簡(jiǎn)后：化簡(jiǎn)后： z(2) = 1250 + 5x2 - 25x4 x1 = 25 - 0.5x2 - 0.5x4 x3 = 20 - x2 + 2x4第二個(gè)基本可行解第二個(gè)基本可行解 (25, 0, 20, 0) , z(2)=12502022-6-425例例第二次換基迭代第二次換基迭代選選 x2入基。得到下列不等式關(guān)系入基。得到下列不等式關(guān)系:x1 = 25 - 0.5x2 - 0.5x4 0 x3 = 20 - x2 + 2x4 0 簡(jiǎn)化為：簡(jiǎn)化為：25 - 0.5x2 0 20 - x2 0 選選 x

17、2 = min(25/0.5, 20/1) = 20 時(shí)才能使不等式成立，并使時(shí)才能使不等式成立，并使 x3為零，令為零，令 x3 出基。出基。換基后的典則形式變?yōu)椋簱Q基后的典則形式變?yōu)椋簔(3) = 1350 - 5x3 - 15x4x1 = 15 + 0.5x3 - 1.5x4x2 = 20 - x3 + 2x4第三個(gè)解為第三個(gè)解為(15, 20, 0, 0) ，z(3) = 1350；此時(shí)，此時(shí)，目標(biāo)函數(shù)表達(dá)式中非基變量的系數(shù)目標(biāo)函數(shù)表達(dá)式中非基變量的系數(shù)都為負(fù)都為負(fù)，目標(biāo)函，目標(biāo)函數(shù)無(wú)法繼續(xù)改進(jìn)數(shù)無(wú)法繼續(xù)改進(jìn)。2022-6-426例例2022-6-427n 確定初始的基本可行解確定初始

18、的基本可行解 n 判斷現(xiàn)行的基本可行解是否最優(yōu)判斷現(xiàn)行的基本可行解是否最優(yōu) n 基本可行解的改進(jìn)基本可行解的改進(jìn) l 換入變量的確定換入變量的確定最大增加原則最大增加原則 l 換出變量的確定換出變量的確定最小比值原則最小比值原則n 用初等變換求改進(jìn)了的基本可行解用初等變換求改進(jìn)了的基本可行解 n 確定初始的基本可行解確定初始的基本可行解 確定初始的基本可行解等價(jià)于確定初始的可行基，確定初始的基本可行解等價(jià)于確定初始的可行基，一旦初始的可行基確定了，那么對(duì)應(yīng)的初始基本可行一旦初始的可行基確定了，那么對(duì)應(yīng)的初始基本可行解也就唯一確定。解也就唯一確定。 為了討論方便，不妨假設(shè)在標(biāo)準(zhǔn)型線性規(guī)劃中，為了

19、討論方便，不妨假設(shè)在標(biāo)準(zhǔn)型線性規(guī)劃中，系數(shù)矩陣中前系數(shù)矩陣中前m m個(gè)系數(shù)列向量恰好構(gòu)成一個(gè)可行基，個(gè)系數(shù)列向量恰好構(gòu)成一個(gè)可行基，即即 = =（，），其中（，），其中B=B=（1 1，2 2，m m）為基）為基變量變量x x1 1，x x2 2，x xm m的系數(shù)列向量構(gòu)成的可行基，的系數(shù)列向量構(gòu)成的可行基，=(=(m+1m+1，P Pm+2m+2, ,P,Pn n) )為非基變量為非基變量x xm+1 m+1 ,x,xm+2,m+2,x,xn n的系數(shù)列向的系數(shù)列向量構(gòu)成的矩陣。量構(gòu)成的矩陣。 2022-6-428 用可行基的逆陣用可行基的逆陣-1-1左乘等式兩端，再通過(guò)移項(xiàng)可推得：左乘等

20、式兩端，再通過(guò)移項(xiàng)可推得： 若令所有非基變量若令所有非基變量, , 則基變量則基變量 由此可得初始的基本可行解由此可得初始的基本可行解所以約束方程所以約束方程 就可以表示為就可以表示為BBNNXAX=(BN)=BX+NX=bX1B bX=0AX=b-1-1BNX =B b-B NX-1BX =B bNX =02022-6-429l 問(wèn)題：?jiǎn)栴}： 要判斷要判斷m m個(gè)系數(shù)列向量是否恰好構(gòu)成一個(gè)基并不是一件容易的事。個(gè)系數(shù)列向量是否恰好構(gòu)成一個(gè)基并不是一件容易的事?；上禂?shù)矩陣中基由系數(shù)矩陣中m m個(gè)線性無(wú)關(guān)的系數(shù)列向量構(gòu)成。個(gè)線性無(wú)關(guān)的系數(shù)列向量構(gòu)成。但是要判斷但是要判斷m m個(gè)系數(shù)列向量是否線

21、性無(wú)關(guān)并非易事。個(gè)系數(shù)列向量是否線性無(wú)關(guān)并非易事。 即使系數(shù)矩陣中找到了一個(gè)基即使系數(shù)矩陣中找到了一個(gè)基B B，也不能保證該基恰好是可行基。，也不能保證該基恰好是可行基。因?yàn)椴荒鼙ＷC基變量因?yàn)椴荒鼙ＷC基變量B B= =-1-1b0b0。 為了求得基本可行解為了求得基本可行解 ，必須求基的逆陣，必須求基的逆陣-1-1。但是求逆陣但是求逆陣-1-1也是一件麻煩的事。也是一件麻煩的事。l 結(jié)論：在線性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中應(yīng)設(shè)法得到一個(gè)結(jié)論：在線性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中應(yīng)設(shè)法得到一個(gè)m m階單位矩陣階單位矩陣I I作為初作為初始可行基始可行基，1B bX=0-1-1-1BNBNNBAX=bBX +NX =bX

22、=B b-B NXX =0,X =B b2022-6-430 若在化標(biāo)準(zhǔn)形式前，約束方程中有若在化標(biāo)準(zhǔn)形式前，約束方程中有“”不等式，不等式，那么在化標(biāo)準(zhǔn)型時(shí)除了在方程式左端減去剩余變量使不等式變那么在化標(biāo)準(zhǔn)型時(shí)除了在方程式左端減去剩余變量使不等式變成等式以外，還必須在左端再加上一個(gè)非負(fù)新變量，稱為成等式以外，還必須在左端再加上一個(gè)非負(fù)新變量，稱為人工變量人工變量 若在化標(biāo)準(zhǔn)形式前，約束方程中有等式方程，那么可以直接在若在化標(biāo)準(zhǔn)形式前，約束方程中有等式方程，那么可以直接在等式左端添加人工變量。等式左端添加人工變量。為了設(shè)法得到一個(gè)為了設(shè)法得到一個(gè)m m階單位矩陣階單位矩陣I I作為初始可行基作

23、為初始可行基，可在線性規(guī)，可在線性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中作如下處理：劃標(biāo)準(zhǔn)化過(guò)程中作如下處理： 若在化標(biāo)準(zhǔn)型前，若在化標(biāo)準(zhǔn)型前，m m個(gè)約束方程都是個(gè)約束方程都是“”的形式，的形式，那么在化標(biāo)準(zhǔn)型時(shí)只需在一個(gè)約束不等式左端都加上一個(gè)松弛變那么在化標(biāo)準(zhǔn)型時(shí)只需在一個(gè)約束不等式左端都加上一個(gè)松弛變量量x xn+in+i (i=1,2, (i=1,2,m),m)。2022-6-431n 判斷現(xiàn)行的基本可行解是否最優(yōu)判斷現(xiàn)行的基本可行解是否最優(yōu) 假如已求得一個(gè)基本可行解假如已求得一個(gè)基本可行解 將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值數(shù)值 其中其中

24、 分別表示基變分別表示基變量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c )2022-6-432 要判定要判定 是否已經(jīng)達(dá)到最大值，只需將是否已經(jīng)達(dá)到最大值，只需將 代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非基變量基變量表表示，示， 即：即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中其中 稱為稱為非基變量非基變量N N的檢驗(yàn)向量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。若的檢驗(yàn)向

25、量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。若N N的每一個(gè)檢的每一個(gè)檢驗(yàn)數(shù)均小于等于驗(yàn)數(shù)均小于等于0 0，即，即N N00，那么現(xiàn)在的基本可行解就是最優(yōu)解。，那么現(xiàn)在的基本可行解就是最優(yōu)解。-1-1BNX=B b-B NX-1BZ=C B b-1NNBm+1m+1n=C -C B N=(,)BBNN-1-1BBNNBNNN-1-1BNBNXZ=CX=(C C )X=C X +C X =C (B b-B NX )+C X=C B b+(C -C B N)X2022-6-433定理定理1 1 最優(yōu)解判別定理最優(yōu)解判別定理 對(duì)于線性規(guī)劃問(wèn)題對(duì)于線性規(guī)劃問(wèn)題若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，若某個(gè)基本可行解所對(duì)應(yīng)的

26、檢驗(yàn)向量， 則這個(gè)基本可行解就是最優(yōu)解。則這個(gè)基本可行解就是最優(yōu)解。nmaxZ=CX, D= XR /AX=b,X0-1NNB=C -C B N0定理定理2 2 無(wú)窮多最優(yōu)解判別定理無(wú)窮多最優(yōu)解判別定理 若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量，其中存在一個(gè)檢驗(yàn)數(shù)，其中存在一個(gè)檢驗(yàn)數(shù)m+km+k=0=0，則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。1B bX=0-1NNB=C -C B N0m +1m +2-1Bm +1,m +1,nnxxZCBb+()x2022-6-434p24n 基本可行解的改進(jìn)基本可行解的改進(jìn) 如果現(xiàn)行的基本可行解不是最優(yōu)

27、解，即在檢驗(yàn)向量如果現(xiàn)行的基本可行解不是最優(yōu)解，即在檢驗(yàn)向量 中存在正的檢驗(yàn)數(shù)，則需在原基本可行解中存在正的檢驗(yàn)數(shù)，則需在原基本可行解的基礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。的基礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：具體做法是： 先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基變量變成基變量（將它的值從零增至正值），變量變成基變量（將它的值從零增至正值）， 再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非基變量（將它的值從正值減至零）

28、。基變量（將它的值從正值減至零）。 由此可得一個(gè)新的基本可行解，由由此可得一個(gè)新的基本可行解，由 可知，這樣的變換一定能使目標(biāo)函數(shù)值有所增加。可知，這樣的變換一定能使目標(biāo)函數(shù)值有所增加。-1NNB=C -C B Nm+1m+2-1Bm+1,m+1,nnxxZC B b+( )x2022-6-435 假設(shè)檢驗(yàn)向量假設(shè)檢驗(yàn)向量 ， 若其中有兩個(gè)以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加若其中有兩個(gè)以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快些，通常要用得快些，通常要用“最大增加原則最大增加原則”，即選取最大正檢驗(yàn)數(shù)所對(duì)應(yīng)的，即選取最大正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量為換入變量，即若非基變量為換入變量，即

29、若 則選取對(duì)應(yīng)的則選取對(duì)應(yīng)的 為換入變量，為換入變量， 由于由于 且為最大，且為最大， 因此當(dāng)由零增至正值，因此當(dāng)由零增至正值， 可使目標(biāo)函數(shù)值可使目標(biāo)函數(shù)值 最大限度的增加。最大限度的增加。 換入變量和換出變量的確定換入變量和換出變量的確定：l換入變量的確定換入變量的確定最大增加原則最大增加原則 -1NNBm+1m+2n=C -C B N=(,)jjm+kmax / 0,m+1jn = m+kxm+kxm+k0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )x2022-6-436l 換出變量的確定換出變量的確定最小比值原則最小比值原則 如果確定如果確定 為換入變量，方程為換入變量，方程其中其中 為中與對(duì)應(yīng)的系數(shù)列向量。為中與對(duì)應(yīng)的系數(shù)列向量?，F(xiàn)在需在現(xiàn)在需在 中確定一個(gè)基變量為換出變量。中確定一個(gè)基變量為換出變量。 當(dāng)當(dāng) 由零慢慢增加到某個(gè)值時(shí)，由零慢慢增加到某個(gè)值時(shí)， 的非負(fù)性可能被打破。的非負(fù)性可能被打破。 為保持解的可行性，可以按最小比值原則確定換出變量：為保持解的可行性，可以按最小比值原則確定換出變量： B12mX =(x ,x ,x )T-1-1-1im+ki-1-1m+kim+k(B b)(B