OR-01-線性規(guī)劃及單純型法_167408766

1、運籌學(xué)基礎(chǔ)Introduction to Operations Research清華大學(xué)自動化系 王煥鋼 Introduction to Operations Research線性規(guī)劃2Tsinghua University2022-3-22 Introduction to Operations Research1. 一般模型和標(biāo)準(zhǔn)模型2. 低維問題的圖解法3. 基本定理與基本算法4. 單純形法5. 對偶性與對偶算法6. 靈敏度分析7. 補(bǔ)充內(nèi)容32022-3-22Tsinghua University Introduction to Operations Research一般模型和標(biāo)準(zhǔn)模型4

2、2022-3-22Tsinghua University Introduction to Operations Research例：生產(chǎn)I、II兩種產(chǎn)品，要占用A、B設(shè)備及調(diào)試時間，每件產(chǎn)品機(jī)時利潤如表所示 15245產(chǎn)品I產(chǎn)品II每天可用時間1占用A機(jī)時占用B機(jī)時調(diào)試時間利潤0612521如何生產(chǎn)使每天利潤最大？52022-3-22Tsinghua University Introduction to Operations Research確定變量：12x x，生產(chǎn)兩種產(chǎn)品的數(shù)量約束條件：1552xA機(jī)時約束242621 xxB機(jī)時約束0, 021xx非負(fù)約束521 xx調(diào)試時間約束每天利潤

3、：212xx 62022-3-22Tsinghua University Introduction to Operations Research122121212max 2s.t. 515622450,0 xxxxxxxxx數(shù)學(xué)規(guī)劃模型 72022-3-22Tsinghua University Introduction to Operations Research例：某種物品有 個產(chǎn)地，記為 ，各產(chǎn)地產(chǎn)量分別是 ；有 個銷地mAAA,21m maaa,21n ，各銷地銷量分別是 ；12,nB BBnbbb,21假定從產(chǎn)地 向銷地 運輸單位物品運價jBiA是 ；問怎樣調(diào)運這些物品能使總費用最小

4、？ijc82022-3-22Tsinghua University Introduction to Operations Research產(chǎn)地銷地產(chǎn)量銷量1AmA2AnB1B2B2ama1anb2b1b21c21x22c22x11c11x1mc1mx12c12x2mc2mxnc1nx1nc2nx2mncmnx92022-3-22Tsinghua University Introduction to Operations Research數(shù)學(xué)規(guī)劃模型 1111mins.t. ,1,10,1,1mnijijijnijijmijjiijc xxaimxbjnximjn 102022-3-22Tsin

5、ghua University Introduction to Operations Research數(shù)學(xué)規(guī)劃模型的一般形式 tjxxxgmixxxhxxxfnjnin, 2 , 1, 0, 2 , 1, 0, s.t.,max2121210, 052426155 s.t.2max212121221xxxxxxxxx121211222121231212412151222,0,5,2, 515,6224,5,nmtf x xxxgx xxgx xxxgx xxxgx xxgx xx 112022-3-22Tsinghua University Introduction to Operations

6、 Research111mins.t. ,1,10,1,1njjjnijjijnijjijjjc xa xbipa xbpimxjqxqjn 線性規(guī)劃模型的一般形式（min）122022-3-22Tsinghua University Introduction to Operations Research0, 052426155 s.t.2max212121221xxxxxxxxx231221152451ma5622450,1,2,x 2s.t., 5ixxxxxxxxxxix2155xxx2142624xxxA機(jī)時剩余量B機(jī)時剩余量調(diào)試時間剩余量235-15xx 13線性規(guī)劃不等式約束轉(zhuǎn)化為

7、等式約束2022-3-22Tsinghua University Introduction to Operations Research000s.t.max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxc線性規(guī)劃標(biāo)準(zhǔn)型目標(biāo)函數(shù)等式約束非負(fù)約束142022-3-22Tsinghua University Introduction to Operations Research線性規(guī)劃的標(biāo)準(zhǔn)模型 11min ( or max)s.t. ,10,1njjjnijjijjc xa xbimxjn min ( or

8、max)s.t. 0TC XAXbX1ncCc1mbbb1111nmmnaaAaa1nxXx152022-3-22Tsinghua University Introduction to Operations Research5 , 2 , 1, 052426155 s.t.2max5214213221ixxxxxxxxxxxi0s.t.maxXbAXXCT52415,100110102600150,00012bAC162022-3-22Tsinghua University Introduction to Operations Research對線性規(guī)劃標(biāo)準(zhǔn)型的基本假定1. 系數(shù)矩陣A的行向量

9、 線性無關(guān)TmTTaaa,21如果該假定不滿足，某個行向量，比如 ，可以表示為 的線性組合，即TmaTmTTaaa121,1 12211TTTTmmmaaaa則對任何滿足前 個約束的 都成立1mX11111111mmTmmTTmbbXaXaXa當(dāng) 時，第 個約束不起作用，故可以刪除，若上述等式不滿足原問題無可行解。1 111mmmbbbm172022-3-22Tsinghua University Introduction to Operations Research在基本假定的基礎(chǔ)上可進(jìn)一步假定2. 系數(shù)矩陣A的列數(shù)大于其行數(shù)，即nm如果 ，由于 是 個 維的向量，不可能線性無關(guān)，如果 ，

10、是行向量線性無關(guān)的方陣，因此有逆，滿足 的只有一個向量 ，不需要優(yōu)化Amn maa,1mnmn bAXbAX1182022-3-22Tsinghua University Introduction to Operations Research0s.t.maxXbAXXCT其中 ，并假定我們所考慮的線性規(guī)劃標(biāo)準(zhǔn)型為：mnmnnRbRARXRC,mn 1. 2. 的行向量線性無關(guān)A192022-3-22Tsinghua University Introduction to Operations Research線性規(guī)劃一般模型與標(biāo)準(zhǔn)模型的轉(zhuǎn)換 1 1iinnia xa xb1 1110iinnni

11、na xa xxbx1 11iinnia xa xbx 111110,0iinniaxxa xbxx1maxnjjjc x1minnjjjc x202022-3-22Tsinghua University Introduction to Operations Research低維問題的圖解法212022-3-22Tsinghua University Introduction to Operations Research生產(chǎn)一種家電產(chǎn)品，要占用A、B設(shè)備及調(diào)試時間，每件產(chǎn)品機(jī)時利潤如表所示 15245產(chǎn)品每天可用時間1占用A機(jī)時占用B機(jī)時調(diào)試時間利潤521如何生產(chǎn)使每天利潤最大？222022-

12、3-22Tsinghua University Introduction to Operations Research數(shù)學(xué)規(guī)劃模型： maxs.t. 51522450 xxxxx0 x x515x 224x 5x 黃實線是可行集，紅點是最優(yōu)解232022-3-22Tsinghua University Introduction to Operations Researchmaxs.t. 51522450 xxxxx0 x x515x 224x 5x 24s.t. 5min152245xxxxmaxs.t. 5155224xxxx 求解線性規(guī)劃問題時，解的情況有：惟一最優(yōu)解；無界解；無可行解；無

13、窮多最優(yōu)解。 2022-3-22Tsinghua University Introduction to Operations Research生產(chǎn)I、II兩種產(chǎn)品，要占用A、B設(shè)備及調(diào)試時間，每件產(chǎn)品機(jī)時利潤如表所示 15245產(chǎn)品I產(chǎn)品II每天可用時間1占用A機(jī)時占用B機(jī)時調(diào)試時間利潤0612521如何生產(chǎn)使每天利潤最大？252022-3-22Tsinghua University Introduction to Operations Research數(shù)學(xué)規(guī)劃模型 122121212max2s.t. 515622450,0zxxxxxxxxx262022-3-22Tsinghua Unive

14、rsity Introduction to Operations Research0, 43, 25 . 1, 5 . 33, 00, 010 x 20 x 2515x 125xx126224xx3z 8z 8.5z 0z 1x2x7z 122zxx12zxx梯度方向最優(yōu)解最優(yōu)目標(biāo)值目標(biāo)函數(shù)等值線27最優(yōu)解?2022-3-22Tsinghua University Introduction to Operations Research15245III每天可用時間1占A機(jī)時占B機(jī)時調(diào)試時間利潤4011521II產(chǎn)品I0612生產(chǎn)I、II、III三種產(chǎn)品，要占用A、B設(shè)備及調(diào)試時間，每件產(chǎn)品機(jī)時利

15、潤如表所示如何生產(chǎn)使每天利潤最大？282022-3-22Tsinghua University Introduction to Operations Research數(shù)學(xué)規(guī)劃模型 1232312123max2s.t. 5415622450,1,2,3izxxxxxxxxxxxi292022-3-22Tsinghua University Introduction to Operations Research1x2x3x0, 3, 075. 3, 0, 075. 3, 0,25. 10, 0, 03, 0, 21, 0, 40, 0, 40, 5 . 1, 5 . 33z 7z 8.5z 126

16、224xx235415xx123x5xx8z 9z 1232zxxx3.75z 6.25z 0z 302022-3-22Tsinghua University Introduction to Operations Research一維、二維、三維共有規(guī)律1. 可行集中任意兩點的連線都在可行集內(nèi)：凸集2. 最優(yōu)解都不在兩個不同點的連線上：頂點3. 所有頂點的個數(shù)有限：有限集312022-3-22Tsinghua University Introduction to Operations Research基本定理與基本算法322022-3-22Tsinghua University Introdu

17、ction to Operations Research向高維推廣要解決的基本問題1. 證明可行集總是凸集，總有頂點是最優(yōu)解 所有頂點組成的集合總是有限集2. 如何計算頂點3. 如何在頂點集中找到最優(yōu)解332022-3-22Tsinghua University Introduction to Operations Research凸集凸集非凸集如果某個集合中任意兩點連起來的直線都屬于該集合，則稱其為凸集，否則為非凸集，如下圖所示數(shù)學(xué)定義： 是凸集當(dāng)且僅當(dāng)對任意實數(shù) 和任意的 均成立1X2X1X2X211XX1021,XX342022-3-22Tsinghua University Intro

18、duction to Operations Research線性規(guī)劃的可行集是否是凸集？標(biāo)準(zhǔn)線性規(guī)劃問題（線性規(guī)劃問題的標(biāo)準(zhǔn)型式）的可行集是否是凸集？首先考察更一般的情況。352022-3-22Tsinghua University Introduction to Operations Research線性規(guī)劃的規(guī)范形式11mins.t. ,10,1njjjnijjijjc xa xbimxjn mins.t. 0TC XAXbX1ncCc1mbbb1111nmmnaaAaa1nxXx362022-3-22Tsinghua University Introduction to Operatio

19、ns Research對任意的 可以推得線性規(guī)劃的可行集是凸集,0nX XRAXb X 規(guī)范形式可行集121212,0,0XXAXb AXb XX1212111AXXAXAXbbb101210XX121AXX滿足凸集定義372022-3-22Tsinghua University線性規(guī)劃問題標(biāo)準(zhǔn)型的可行集是凸集（證法相同） Introduction to Operations Research凸集的頂點如果凸集內(nèi)的一點不在凸集內(nèi)任何不同的兩點連起來的直線上，則稱該點為該凸集的頂點，如下所示（頂點）數(shù)學(xué)定義： 是凸集 的頂點當(dāng)且僅當(dāng)不存在實數(shù) 和 滿足（不是頂點）211XXXX2121,XXXX

20、10382022-3-22Tsinghua University Introduction to Operations Research一二三維規(guī)范形式頂點的共有規(guī)律515x 0 x 0 x *5153xx392022-3-22Tsinghua University Introduction to Operations Research一二三維規(guī)范形式頂點的共有規(guī)律10 x 20 x 2515x 125xx126224xx*12125,62243.5,1.5TxxxxX120,00,0TxxX120,5150,3TxxX402022-3-22Tsinghua University Introd

21、uction to Operations Research一二三維規(guī)范形式頂點的共有規(guī)律235415xx126224xx123x5xx10 x 20 x 30 x 頂點是該點所有起作用約束(不等式成為等式的約束)構(gòu)成的線性方程組的唯一解*1231225,6224,04,0,1TxxxxxxX412022-3-22Tsinghua University Introduction to Operations Research0, 0524261552121212xxxxxxx頂點是該點所有起作用約束(不等式成為等式的約束)構(gòu)成的線性方程組的唯一解1203xx21212125156224500 xx

22、xxxxx215150 xx起作用約束該線性方程組的解唯一該點是頂點422022-3-22Tsinghua University Introduction to Operations Research0, 43, 25 . 1, 5 . 33, 00, 010 x 20 x 2515x 125xx126224xx1x2x432022-3-22Tsinghua University Introduction to Operations Research0, 0524261552121212xxxxxxx頂點是該點所有起作用約束(不等式成為等式的約束)構(gòu)成的線性方程組的唯一解1202xx21212

23、125156224500 xxxxxxx10 x 起作用約束該線性方程組的解不唯一該點不是頂點442022-3-22Tsinghua University Introduction to Operations Research0, 43, 25 . 1, 5 . 33, 00, 010 x 20 x 2515x 125xx126224xx1x2x0, 2452022-3-22Tsinghua University Introduction to Operations Research那么當(dāng)且僅當(dāng)?shù)仁椒匠探M的解唯一時 是 的頂點規(guī)范形式頂點的數(shù)學(xué)描述規(guī)范形式可行集1,10,1nijjijja x

24、bimxjn :X11,(1), ( ),0,(1),( ) ,0,(1), (1), ( ) ninijjijjjijjja xb ikk mxjk ma xbikk mkk nxjmk n對任意的 ，將所有的線性不等式進(jìn)行如下劃分X 462022-3-22Tsinghua University Introduction to Operations Research1203xXx 21212125156224500 xxxxxxx4722211215150622450 xxxxxxx2022-3-22Tsinghua University0, 0524261552121212xxxxxxx

25、Introduction to Operations Research1,10,1nijjijja xbimxjn :由于由等式方程約束條件產(chǎn)生的只能是等式，所以對任意的 可進(jìn)行如下劃分（注意 ）標(biāo)準(zhǔn)形式頂點的數(shù)學(xué)描述X 10,(1), ( ), 1,0,(1), ( )njijjijjxjkk ma xbimxjk mk n 當(dāng)且僅當(dāng)上面的等式方程組解唯一時 是 的頂點X482022-3-22Tsinghua Universitymn Introduction to Operations Research一維規(guī)范形式轉(zhuǎn)換為標(biāo)準(zhǔn)形式的頂點規(guī)律3x 0 x 49xy3330,0 xyxy頂點13

26、0030 xyxxyy頂點233000 xyxyyx2022-3-22Tsinghua University Introduction to Operations Research0, 0524261552121212xxxxxxx51, 05242615552142132ixxxxxxxxxi線性方程組解唯一，該點是頂點23121251562245xxxxxx0, 0, 5 . 7, 5 . 1, 5 . 354321xxxxx502022-3-22Tsinghua University Introduction to Operations Research0, 43, 25 . 1, 5

27、. 33, 00, 010 x 20 x 2515x 125xx126224xx1x2x512022-3-22Tsinghua University Introduction to Operations Research212412551562245xxxxxxx線性方程組解不唯一該點不是頂點123451,3,0,12,1xxxxx520, 43, 25 . 1, 5 . 33, 00, 010 x 20 x 2515x 125xx126224xx1x2x2022-3-22Tsinghua University Introduction to Operations Research0, 052

28、4261552121212xxxxxxx可行集原始表示可行集等價表示51, 05242615552142132ixxxxxxxxxi任意指定兩個變量，如 ，解線性方程組 ktxx ,判斷所得到的解是否可行，即是否都不小于05242615552142132xxxxxxxx00ktxx532022-3-22Tsinghua University Introduction to Operations Research52426155212132xxxxxx0054xx5242615552142132xxxxxxxx0, 0, 5 . 7, 5 . 1, 5 . 354321xxxxx例如得到一個頂點

29、求得542022-3-22Tsinghua University Introduction to Operations Research求得又例如有變量為負(fù)數(shù)，不是頂點524215524232xxxxx0051xx5242615552142132xxxxxxxx0,14,10, 5, 054321xxxxx552022-3-22Tsinghua University Introduction to Operations Research標(biāo)準(zhǔn)形式頂點的等價描述之一1njjjP xb1, 1TjjmjPaajn 1111, 1jnnijjijjjmjmaba xbimxab ( )( )( )10

30、,1,mk jk jk jjxjmPxb 10,(1), ( ), 1,0,(1), ( )jnijjijjxjkk ma xbim xjk mk n 當(dāng)且僅當(dāng) 的正分量對應(yīng)的系數(shù)向量線性無關(guān)X 562022-3-22Tsinghua University Introduction to Operations Research5241510001000112516054321xxxxx5242615552142132xxxxxxxx5 , 2 , 1, 0ixi5 , 2 , 1, 0ixi123451,3,0,12,1xxxxx572022-3-22Tsinghua University I

31、ntroduction to Operations Research標(biāo)準(zhǔn)形式頂點的等價描述之二如果 是行滿秩矩陣，那么 是可行集11,0, 1nTnjjjjXxxP xb xjn 的頂點充要條件是：存在可逆方陣 ，1,nPP(1)(),kk mPP可以把 的分量劃分為 ，使?jié)M足XX(1)1(1)()( )(),0,0,1kkk mk jk mxPPbxmjnx ( ),1,k jxjn 主要理由：( )( )1mk jk jjPxb正分量對應(yīng)的系數(shù)向量線性無關(guān)582022-3-22Tsinghua University Introduction to Operations Research稱可

32、行的基本解為基本可行解線性規(guī)劃標(biāo)準(zhǔn)形式的基陣、基本解和基本可行解(1)(),kk mPP稱可逆矩陣 為基陣(1)1(1)()( )(),0,1kkk mk jk mxPPbxmjnx 稱其分量由下式?jīng)Q定的 為基本解X標(biāo)準(zhǔn)線性規(guī)劃的基本可行解就是可行集的頂點標(biāo)準(zhǔn)線性規(guī)劃的可行集的頂點個數(shù)總是有限的稱基陣對應(yīng)變量為基變量，其余變量為非基變量592022-3-22Tsinghua University Introduction to Operations Research線性規(guī)劃標(biāo)準(zhǔn)形式的基本定理【定理1】一個標(biāo)準(zhǔn)形式線性規(guī)劃問題若有可行解，則至少存在一個基本可行解【定理2】一個標(biāo)準(zhǔn)形式線性規(guī)劃問題

33、若有有限的最優(yōu)目標(biāo)值，則一定存在一個基本可行解是最優(yōu)解【定理3】如果標(biāo)準(zhǔn)線性規(guī)劃問題的某個基可行解的相鄰的基可行解都不比它好，那么這個基可行解就是最優(yōu)解602022-3-22Tsinghua University Introduction to Operations Research定理1的圖形表示只要可行解不是頂點，就可以沿某個方向移動直至某個不起作用約束變成起作用約束，如此繼續(xù)一定找到頂點10 x 20 x 23515xx1255xxx1x2x1246224xxx20 x 10 x 30 x 40 x 50 x 0X1X51, 05242615552142132ixxxxxxxxxi612

34、022-3-22Tsinghua University Introduction to Operations Research定理2的圖形表示只要最優(yōu)解不是頂點，就可沿等值線移動直至某個不起作用約束變成起作用約束，如此繼續(xù)一定找到最優(yōu)頂點假設(shè)：125zxxx10 x 20 x 23515xx1255xxx1x2x1246224xxx20 x 10 x 30 x 40 x 50 x 0X1X2X622022-3-22Tsinghua University Introduction to Operations Research例：2143,2242,1232,2241,1231,2221該問題至多

35、有下面 個可能的基陣624C12341234max12347s.t.221230, 14jzxxxxxxxxxj 利用基本定理求解線性規(guī)劃問題632022-3-22Tsinghua University Introduction to Operations Research對每個基矩陣 ，計算 ，可得11372143,25 . 037224225 . 0371232,611313722412 . 24 . 0371231,5 . 54372221111111BbB1該線性規(guī)劃只有3個基本可行解642022-3-22Tsinghua University Introduction to Oper

36、ations Research由 可確定對應(yīng)的基本可行解24132221A1111221331370.40.4, 0, 2.2, 0,2.62132.22370.50, 0.5, 2, 0,2.5213234710, 0,1,1,21231TTTXzXzXz 如果該問題存在有限的最優(yōu)解， 就是最優(yōu)解1X1234zxxxx由 可算出對應(yīng)的目標(biāo)函數(shù)值652022-3-22Tsinghua University Introduction to Operations Research單純形法662022-3-22Tsinghua University Introduction to Operation

37、s Research頂點搜索路徑假設(shè)從頂點 出發(fā)到達(dá)頂點10 x 20 x 23515xx30 x 0X1X3X0X1X672022-3-22Tsinghua University Introduction to Operations ResearchT00 0 15 24 5X ， ， ，T10 3 0 18 2X ， ，23124125125156224500 xxxxxxxxxx23124125135156224500 xxxxxxxxxx起作用約束起作用約束1. 相鄰頂點間只有一個起作用約束不同（非基變量）2. 若頂點不是最優(yōu)解，其相鄰頂點集中有更好的頂點682022-3-22Tsin

38、ghua University Introduction to Operations Research頂點搜索路徑10 x 20 x 23515xx1255xxx1246224xxx30 x 40 x 50 x 0X2X1X3X692022-3-22Tsinghua University Introduction to Operations Research如何計算選定進(jìn)基變量后的基本可行解如何判斷已經(jīng)找到最優(yōu)的基本可行解如何選擇進(jìn)基變量使目標(biāo)函數(shù)改進(jìn)假定已知一個基本可行解702022-3-22Tsinghua University Introduction to Operations Res

39、earchT00 0 15 24 5X ， ， ，T10 3 0 18 2X ， ，23124125125156224500 xxxxxxxxxx23124125135156224500 xxxxxxxxxx起作用約束起作用約束712022-3-22Tsinghua University Introduction to Operations Research例15 , 2 , 1, 052415100010001125160s.t. 0002max5432154321jxxxxxxxxxxxj5241512516021543xxxxx由此可看出 是一個基本可行解TX5 ,24,15, 0 ,

40、0我們將基變量只出現(xiàn)在一個等式的等式約束稱為對應(yīng)的基本可行解的表示式（教材中稱為典式），由表示式可看出基本可行解。其等式約束可寫成722022-3-22Tsinghua University Introduction to Operations Research在 的各行除以 的系數(shù)假設(shè)我們想要讓 變成基變量，即選擇 為進(jìn)基變量，根據(jù)基本可行解的表示式，必須讓 只出現(xiàn)在一個等式約束中2x2x51231111305 . 02 . 021543xxxxx2x5241512516021543xxxxx可得2x732022-3-22Tsinghua University Introduction to

41、 Operations Research51231111305 . 02 . 021543xxxxx在 中選定一行，用其它行減去該行，即可達(dá)到只有一行有 的目的，例如：2x5721001215 . 02 . 02155453xxxxxxx整理后可得5721111215 . 02 . 051243xxxxx問題：第一個方程的右邊出現(xiàn)負(fù)數(shù)742022-3-22Tsinghua University Introduction to Operations Research51231111305 . 02 . 021543xxxxx為了避免前面的問題，在方程中，只能用其它行減去第一行，即右邊常數(shù)最小的一

42、行，由此可得2930011302 . 02 . 05 . 02 . 02135343xxxxxxx752022-3-22Tsinghua University Introduction to Operations Research整理后得到2932 . 02 . 02 . 01305 . 031542xxxxx再將第二行除以 得到基本可行解的表示式5 . 021832 . 04 . 02 . 016031542xxxxx該基本可行解是 , 變成非基變量，它是原來的基本可行解在保留 的行的基變量TX2 ,18, 0 , 3 , 03x2x762022-3-22Tsinghua Universit

43、y5241512516021543xxxxx Introduction to Operations Research51231111305 . 02 . 021543xxxxx5241512516021543xxxxx由于 的 等于152245155123其中 和 分別是 52415125中進(jìn)基變量 的系數(shù)向量和右邊常數(shù)向量，所以前面選擇保留 的行的方法可以總結(jié)為選擇達(dá)到2x15,224,515min2x的行，一旦選定這樣的行，在該行的基變量將變成非基變量，從而確定了出基變量772022-3-22Tsinghua University Introduction to Operations Re

44、search如果我們又想讓 進(jìn)基，由于21832 . 04 . 02 . 016031542xxxxx現(xiàn)在已知基本可行解 的表示式為TX2 ,18, 0 , 3 , 03x采用前面總結(jié)的規(guī)則應(yīng)該保留第二行的 ，但是若將第二行的 前的系數(shù)變成1 ，必須在第二行除以 ，此時右邊系數(shù)將變成負(fù)數(shù)，所以，只能選擇進(jìn)基變量系數(shù)非負(fù)的行保留進(jìn)基變量4 . 0182 . 02,4 . 018,2 . 03min3x4 . 03x782022-3-22Tsinghua University Introduction to Operations Research21832 . 04 . 02 . 01603154

45、2xxxxx由于 ，讓 進(jìn)基只能用第一行的 消去其它行的 ，對于 的系數(shù)不是正數(shù)的行，我們需要將第一行乘以一個合適的正數(shù)加到相應(yīng)的行，這種操作不會使右邊項的數(shù)變成為負(fù)數(shù)，因此在選擇保留進(jìn)基變量所在行的過程中不用考慮進(jìn)基變量的系數(shù)不是正數(shù)的行3x3x3x3x792022-3-22Tsinghua University Introduction to Operations Research可以利用數(shù)據(jù)表完成換基運算的表示式由下面的數(shù)據(jù)表完全確定5241512516021543xxxxxTX5 ,24,15, 0 , 051001124010261500150RHSBV54354321xxxxxxx

46、x（基變量）（右邊項）802022-3-22Tsinghua University Introduction to Operations Research讓 進(jìn)基是對數(shù)據(jù)表進(jìn)行如下運算：2102 . 00118014 . 0063002 . 010RHSBV54254321xxxxxxxx2x51001124010261500150RHSBV54354321xxxxxxxx 5 (-2) + (-1) + 15,224,515min812022-3-22Tsinghua University Introduction to Operations Research總結(jié)前面的討論，可得到下面的一般

47、規(guī)則：假設(shè)某基本可行解的表示式是BnjnjmjmjBXxPxPX)()() 1() 1(其中(1)1 ( )(1)11( )( )()( )(),jj tjBj tj tBj mm j tj mxpxXPB PtXB bxpx如果要選 （ ）進(jìn)基，則應(yīng)該僅保留第 行的 ，即 出基，其中 滿足)(tjxl)(tjx)(ljxl)()(0)()(min)(tjiijptjlljpxpxtjintm1822022-3-22Tsinghua University Introduction to Operations Research為獲得 進(jìn)基、 出基后的基本可行解表示式，需要對原來的表示式Bnjnj

48、mjmjBXxPxPX)()() 1() 1(具體做法：先在第 行除以 ，再將第 行分別乘以 加到第 行l(wèi)), 2 , 1(limii)(tjlpl)(tjx)(ljx進(jìn)行行等價變換，使 前面的系數(shù)向量)(tjx變成)()()(1)(tjmtjltjtjpppP010)(tjip832022-3-22Tsinghua University Introduction to Operations Research1234512345max 2000 s.t.051001562010241100150,1,2,5jxxxxxxxxxxxj 13452010015560102421001510,1,2

49、,5jxxxxxxj 842022-3-22Tsinghua University Introduction to Operations Research(1)(1)( )( )( )( )( )( )( )Bj mj mj nj nBj tj tBXPxPxXPPX( )( )( )( ),( )( )0,1,BBj tj tj iXXPxxmin it 任取正數(shù) ，定義 維向量 的分量如下：n( )X由 可知 ，滿足不等式約束，此外( )0X0)(tjP滿足等式約束，因此 是可行解，并且其分量 在可行集里可以趨于無窮大( )X 時對應(yīng)的變量在可行集可趨于無窮大0)(tjP特殊情況：)()(

50、0)()(min)(tjiijptjlljpxpxtji無法計算( )( )j tx0)(tjP852022-3-22Tsinghua University Introduction to Operations Research小結(jié)假定已知基本可行解 的表示式為BnjnjmjmjBXxPxPX)()() 1() 1(X2. 只要 有一個分量大于 0 ，就可以通過行變換讓 進(jìn)基，形成一個新的基本可行解任取 ，則有以下結(jié)論：1. 如果 ，變量 在可行集可趨于無窮大ntm10)(tjP)(tjx)(tjP)(tjx862022-3-22Tsinghua University Introduction

51、 to Operations Research如何計算選定進(jìn)基變量后的基本可行解如何判斷已經(jīng)找到最優(yōu)的基本可行解如何選擇進(jìn)基變量使目標(biāo)函數(shù)改進(jìn)假定已知一個基本可行解872022-3-22Tsinghua University Introduction to Operations Research對于例我們已經(jīng)得到兩個基本可行解，即5 , 2 , 1, 052415100010001125160s.t. 0002max5432154321jxxxxxxxxxxxjTX2 ,18, 0 , 3 , 0TX5 ,24,15, 0 , 0記12345()2000f Xxxxxx則()0,()3f Xf

52、 X如何找到其目標(biāo)函數(shù)值大于 的基本可行解？()f X882022-3-22Tsinghua University Introduction to Operations Research21832 . 04 . 02 . 016031542xxxxxTX2 ,18, 0 , 3 , 0已知 的表示式為將上式確定的基變量對非基變量的函數(shù)關(guān)系代入目標(biāo)函數(shù) ，可以得到由于每個變量都不能小于0，由上式可知，當(dāng)且僅當(dāng) 取正數(shù)（等價于讓其進(jìn)基）時，才能獲得比 更大的目標(biāo)函數(shù)值1313()320.2()20.2 f XfxXxxx1x()f X12534()2000 xxxfxxX892022-3-22Ts

53、inghua University Introduction to Operations Research2102 . 0016618 . 0003002 . 010RHSBV14254321xxxxxxxx如前所述，讓 進(jìn)基是對數(shù)據(jù)表進(jìn)行如下運算： (-6) + 12,618,03min2102 . 00118014 . 0063002 . 010RHSBV54254321xxxxxxxx1x902022-3-22Tsinghua University Introduction to Operations Research2102 . 0016618 . 0003002 . 010RHSBV

54、14254321xxxxxxxx根據(jù)數(shù)據(jù)表馬上可知新的基本可行解為()()47f Xf XTX0 , 6 , 0 , 3 , 2其中 是 對應(yīng)的目標(biāo)函數(shù)值將上表確定的基變量對非基變量的函數(shù)關(guān)系代入目標(biāo)函數(shù) 又可得新目標(biāo)函數(shù)式13()()20.2xff XxX3535()()40.22()0.22 f Xf Xf XxxxxX912022-3-22Tsinghua University Introduction to Operations Research用 表示線性規(guī)劃標(biāo)準(zhǔn)型的目標(biāo)函數(shù)，它和 之XzzxcxcxcbxPxPxPnnnn22112211可將其寫成下面的擴(kuò)充的等式約束形式zbxcP

55、xcPxcPnnn222111例如，對于例題，其擴(kuò)充的等式約束為zxxxxx524150100001000011125216054321間的函數(shù)關(guān)系完全由以下線性方程組所確定922022-3-22Tsinghua University Introduction to Operations Research21832 . 04 . 02 . 016031542xxxxxTX2 ,18, 0 , 3 , 0相當(dāng)于對擴(kuò)充的等式約束的前三行進(jìn)行變換獲得對原來的等式約束進(jìn)行行變換得到 的表示式zxxxxx21830100001002 . 04 . 02 . 01001216054321932022-3-

56、22Tsinghua University Introduction to Operations Research基變量的函數(shù)關(guān)系代入 以獲得僅含非基變量的 ，相當(dāng)于利用下面前三行等式將第四行的基變量的系數(shù)變成 021832 . 04 . 02 . 016031542xxxxx543210002xxxxxz將 所確定的基變量對非zxxxxx21830100001002 . 04 . 02 . 01001216054321312 . 023xxz942022-3-22Tsinghua University Introduction to Operations Researchzxxxxx2183

57、0100001002 . 04 . 02 . 01001216054321將第一行乘以-1加到第四行就可以得到32183010000102 . 02 . 04 . 02 . 00001216054321zxxxxxX對于擴(kuò)充約束我們將其稱為基本可行解 的擴(kuò)充表示式952022-3-22Tsinghua University Introduction to Operations Research1. 是基本可行解32183010000102 . 02 . 04 . 02 . 00001216054321zxxxxx從擴(kuò)充表示式TX2 ,18, 0 , 3 , 0可以獲得下述信息：2. 的目標(biāo)函數(shù)

58、值滿足 ，即X30 z3z3. 目標(biāo)函數(shù)可以寫成 ，因此讓 進(jìn)基能夠增加目標(biāo)函數(shù)值1x312 . 023xxz962022-3-22Tsinghua University Introduction to Operations Research前面由 的表示式獲得其擴(kuò)充表示式的過程可利用下面擴(kuò)充的數(shù)據(jù)表（單純形表）完成TX2 ,18, 0 , 3 , 0zxxxxxxxx000122102 . 00118014 . 0063002 . 010RHSBV54254321其中前面三行數(shù)據(jù)由 的表示式確定，最后一行是目標(biāo)函數(shù)和變量間的（任意一種）約束式X972022-3-22Tsinghua Univ

59、ersity Introduction to Operations Research該表能夠完全確定基本可行解 的擴(kuò)充表示式，我們將其稱為 的單純形表對前面的單純形表通過行變換將最后一行的基變量前面的系數(shù)變成 0 就得到下面的單純形表3002 . 0022102 . 00118014 . 0063002 . 010RHSBV54254321zxxxxxxxxXX982022-3-22Tsinghua University Introduction to Operations Research3002 . 0022102 . 00118014 . 0063002 . 010RHSBV542543

60、21zxxxxxxxx利用 的單純形表，很容易獲得讓 進(jìn)基后的基本可行解的單純形表，即先由右邊項和 前面的系數(shù)的比值確定出基變量為1x5x12,618,03min然后通過行變換將 所在列除了第三行以外的系數(shù)變成 0 即可得到新的基本可行解對應(yīng)的單純形表1xX1x992022-3-22Tsinghua University Introduction to Operations Research新的基本可行解對應(yīng)的單純形表為據(jù)此可知：2. 的目標(biāo)函數(shù)值滿足 ，即X70 z7z3. 讓 進(jìn)基能夠增加目標(biāo)函數(shù)值3x1. 是基本可行解TX0 , 6 , 0 , 3 , 27202 . 0002102 .