第1章線性規(guī)劃及單純型法

1、第1章線性規(guī)劃及單純型法 例: 生產(chǎn)計(jì)劃問題III資資 源源 限限 量量設(shè)設(shè) 備備原原 材材 料料 A原原 材材 料料 B1402048 臺(tái)臺(tái) 時(shí)時(shí)16kg12kg利利 潤潤23產(chǎn)品產(chǎn)品I產(chǎn)品產(chǎn)品2x1x2x1x2zIII資源限量資源限量設(shè)備設(shè)備原材料原材料 A原材料原材料 B1402048 臺(tái)時(shí)臺(tái)時(shí)16kg12kg利潤利潤23 0,.,),(.),(.),(.)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax0,., 0,.,. 2121221122222121112121112211m

2、nmnmnmmnnnnnnbbbxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMax目標(biāo)函數(shù)最大目標(biāo)函數(shù)最大約束條件等式約束條件等式?jīng)Q策變量非負(fù)決策變量非負(fù) njxmibxaxcZjinjjijnijj,.,2 , 1 0,.2 , 1 max11 ),.cc,(cC ,.2, 1 0max212121n211 b.bb ba.aa Px.xxXnjxbxPCXZmmjjjjnjnijj其中： 0.000 ),.,( . 0 max 211111nmnmnPPPaaaaAXbAXCXZ決策變量向量 -X 價(jià)值向量 -C 資源向量0.000 ),.,( . 0 max 32111

3、11bPPPaaaaAXbAXCXZmnmnC C價(jià)值向量價(jià)值向量b b資源向量資源向量X X決策變量向量決策變量向量 0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz 無約束321321321321321,0,7232 7 32minxxxxxxxxxxxxxxxzMax x6 x7543xxxkx0, kkkkkxxxxx令 ：標(biāo)準(zhǔn)形為0,7 )(232 )( 7 )( 00)( 32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz距離AB需求量X10445Y5

4、875Z61540供應(yīng)量60100供需平衡供需平衡線性規(guī)劃模型舉例( (一一) ) 運(yùn)輸問題運(yùn)輸問題( (二二) ) 布局問題布局問題( (三三) ) 分派問題分派問題( (四四) ) 生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題( (五五) ) 合理下料問題合理下料問題線性規(guī)劃模型的條件線性規(guī)劃模型的條件 （1 1）要求解問題的目標(biāo)函數(shù)能用數(shù)）要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)；值指標(biāo)來反映，且為線性函數(shù)； （2 2）存在著多種方案；）存在著多種方案； （3 3）要求達(dá)到的目標(biāo)是在一定約束）要求達(dá)到的目標(biāo)是在一定約束條件下實(shí)現(xiàn)的，這些約束條件可用條件下實(shí)現(xiàn)的，這些約束條件可用線性等式或不等式來

5、描述。線性等式或不等式來描述。( (一一) ) 運(yùn)輸問題運(yùn)輸問題 設(shè)某種物資有設(shè)某種物資有m m個(gè)產(chǎn)地，個(gè)產(chǎn)地，A A1 1，A A2 2，A A m m；聯(lián)合供應(yīng)聯(lián)合供應(yīng)n n個(gè)銷地：個(gè)銷地：B B1 1，B B2 2，B Bn n。各產(chǎn)地產(chǎn)量（單位：噸），各銷地銷量（單位：各產(chǎn)地產(chǎn)量（單位：噸），各銷地銷量（單位：噸），各產(chǎn)地至各銷地單位運(yùn)價(jià)（單位：元噸），各產(chǎn)地至各銷地單位運(yùn)價(jià)（單位：元噸）如下表所示。噸）如下表所示。應(yīng)如何調(diào)運(yùn)，應(yīng)如何調(diào)運(yùn)，才使總運(yùn)費(fèi)最才使總運(yùn)費(fèi)最少？少？單價(jià)（元噸）單價(jià)（元噸）銷銷 地地產(chǎn)產(chǎn) 地地產(chǎn)量（噸）產(chǎn)量（噸） B1 B2 BnA1A2 Am銷量（噸）銷量（噸）

6、 C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn b1 b2 bna1a2 am minjjiba11即即( (一一) ) 運(yùn)輸問題運(yùn)輸問題()()產(chǎn)銷平衡產(chǎn)銷平衡()()產(chǎn)銷平衡產(chǎn)銷平衡()()產(chǎn)銷不平衡產(chǎn)銷不平衡約束條件約束條件產(chǎn)地產(chǎn)地A Ai i發(fā)到各銷地的發(fā)量發(fā)到各銷地的發(fā)量總和應(yīng)等于總和應(yīng)等于A Ai i的產(chǎn)量的產(chǎn)量各產(chǎn)地各產(chǎn)地發(fā)到銷地發(fā)到銷地B Bj j的發(fā)量的發(fā)量總和應(yīng)等于總和應(yīng)等于B Bj j的銷量的銷量調(diào)運(yùn)調(diào)運(yùn)量不能為負(fù)數(shù)量不能為負(fù)數(shù)0約束條件約束條件產(chǎn)地產(chǎn)地A Ai i發(fā)到各銷地的發(fā)量發(fā)到各銷地的發(fā)量總和應(yīng)等于總和應(yīng)等于A Ai i的產(chǎn)量的產(chǎn)量各產(chǎn)地

7、各產(chǎn)地發(fā)到銷地發(fā)到銷地B Bj j的發(fā)量的發(fā)量總和應(yīng)等于總和應(yīng)等于B Bj j的銷量的銷量調(diào)運(yùn)調(diào)運(yùn)量不能為負(fù)數(shù)量不能為負(fù)數(shù)0njmixnjbxmiaxijijiijmijnj, 1;, 2 , 1 0, 2 , 1 , 2 , 1 11 約束條件約束條件njmixnjbxmiaxijijiijmijnj, 1;, 2 , 1 0, 2 , 1 , 2 , 1 11 njmiijijxcs11 min。的值最小目標(biāo)函數(shù)m11injjiba即這一問題的數(shù)學(xué)模型應(yīng)為： 求一組變量 的值,使它滿足njmixij, 2 , 1;, 2 , 1()()產(chǎn)銷不平衡產(chǎn)銷不平衡產(chǎn)大于銷產(chǎn)大于銷( (一一) )

8、運(yùn)輸問題運(yùn)輸問題約束條件約束條件njmixnjbxmiaxijjijiijminj, 2 , 1;, 2 , 1 0, 2 , 1 , 2 , 1 11 產(chǎn)地產(chǎn)地A Ai i發(fā)到各銷地的發(fā)量發(fā)到各銷地的發(fā)量總和不超過總和不超過A Ai i的產(chǎn)量的產(chǎn)量各產(chǎn)地各產(chǎn)地發(fā)到銷地發(fā)到銷地B Bj j的發(fā)量的發(fā)量總和應(yīng)等于總和應(yīng)等于B Bi i的銷量的銷量調(diào)運(yùn)調(diào)運(yùn)量不能為負(fù)數(shù)量不能為負(fù)數(shù)njmiijijxcs11 min 目標(biāo)函數(shù)產(chǎn)小于產(chǎn)小于銷的模銷的模型呢型呢（二）布局問題（二）布局問題 作物布局 在n塊地上種植m種作物，已知各塊土地 畝數(shù)、各種作物計(jì)劃播種面積及各種作 物在各塊的單產(chǎn)（每畝的產(chǎn)量）如表

9、 （與運(yùn)輸問題相似），問：如何合理安排種植計(jì)劃，才使總產(chǎn)量最多。 單價(jià)（元噸）單價(jià)（元噸）銷銷 地地產(chǎn)產(chǎn) 地地產(chǎn)量（噸）產(chǎn)量（噸） B1 B2 BnA1A2 Am銷量（噸）銷量（噸） C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn b1 b2 bna1a2 am（二）布局問題（二）布局問題( (三）分派問題三）分派問題 設(shè)有設(shè)有n n件工作件工作 分派給分派給n n人人 去做，去做，每人只做一件工作且每件工作只分每人只做一件工作且每件工作只分派一人去做。設(shè)派一人去做。設(shè)A Ai i完成完成B Bj j的工時(shí)為的工時(shí)為 。問：應(yīng)如何分派才使完成全部工作問：應(yīng)如何分派才使完

10、成全部工作的總工時(shí)最少。的總工時(shí)最少。nBBB,21nAAA,21njicij,2, 1,解：設(shè)解：設(shè) 為為B Bj j分派給人分派給人A Ai i情況：情況： B Bj j分派給分派給A Ai i時(shí)，時(shí)， ； 不分派給不分派給A Ai i時(shí)，時(shí)， 。 那末這一問題的數(shù)學(xué)模型為：那末這一問題的數(shù)學(xué)模型為：ijx1ijxnjicij, 2 , 1,0njixij, 2 , 1, 求一組變量求一組變量 的值，的值，使目標(biāo)函數(shù)使目標(biāo)函數(shù) 的值最小。的值最小。nimjijijxcs11 (完成全部工作的總工時(shí)最少完成全部工作的總工時(shí)最少）( (三）分派問題三）分派問題約束條件約束條件njixnixnj

11、xijijijnjni,2, 1, 1 0,2, 1 1,2, 1 111或每件工作只分派一人去做每件工作只分派一人去做每人只做一件工作每人只做一件工作每人對每件工作只有每人對每件工作只有做與不做兩種情況做與不做兩種情況分派問題的模型分派問題的模型nimjijijxcs11 min目標(biāo)函數(shù)目標(biāo)函數(shù) 設(shè)用某原材料設(shè)用某原材料( (條材或板材條材或板材) )下零件下零件 的毛坯的毛坯. .根據(jù)過去經(jīng)驗(yàn)根據(jù)過去經(jīng)驗(yàn)在一件原材料上有在一件原材料上有 種不同種不同的下料方式的下料方式, ,每種下料方式可得各種毛每種下料方式可得各種毛坯個(gè)數(shù)及每種零件需要量如下表所示。坯個(gè)數(shù)及每種零件需要量如下表所示。問：

12、應(yīng)怎樣安排下料方式，使得既問：應(yīng)怎樣安排下料方式，使得既 能滿足需要，用的原材料又最少。能滿足需要，用的原材料又最少。mAAA,21nBBB,21( (四四) )合理下料問題合理下料問題各方式下的零件個(gè)數(shù)各方式下的零件個(gè)數(shù)下下 料料 方方 式式零件零件 名稱名稱 B1 B2 BnA1A2 Am C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn零件零件需要量需要量a1a2 am( (五五) )合理下料問題合理下料問題 解：解： 設(shè)用設(shè)用 種方式下料的原材料數(shù)種方式下料的原材料數(shù) 為為 （j=1,2,j=1,2,n),n)， 則這一問題的數(shù)學(xué)模型為：則這一問題的數(shù)學(xué)模型為：

13、jBjxnjjxs1的值最少使目標(biāo)函數(shù)( (五五) )合理下料問題合理下料問題所用原材料數(shù)量最少所用原材料數(shù)量最少), 2 , 1( , 0 ), 2 , 1( 1njxmiaxcjijijnj整數(shù)iA（所下的（所下的 Ai 零件總數(shù)不能少于零件總數(shù)不能少于 ）ia（各種方式下料的原材料數(shù)不能是負(fù)（各種方式下料的原材料數(shù)不能是負(fù)數(shù)、分?jǐn)?shù)）數(shù)、分?jǐn)?shù)）( (五五) )合理下料問題的模型合理下料問題的模型約束條件約束條件njjxs1min目標(biāo)函數(shù)目標(biāo)函數(shù)線性規(guī)劃模型9 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 8(0, 4)(8, 0)4x1 164 x2 1

14、29 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域9 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16BCDEAx1+ 2x2=8 4x1 =16x26 5 4 3 2 1 0 |123456789x

15、16 5 4 3 2 1 0 x2|123456789x1 x2x118 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 1618 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16可行域可行域ABCDE18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)

16、18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)x218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)4x1+ 6x2=48 2x1+ 2x2 =18v線性規(guī)劃解的概念線性規(guī)劃解的概念v線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義 （單純形法原理）（單純形法原理） 標(biāo)準(zhǔn)型 可行解:滿足AX=b, X=0的解X稱為

17、線性規(guī)劃問題的可行解。 最優(yōu)解：使Z=CX達(dá)到最大值的可行解稱為最優(yōu)解。0 max XbAXCXZ 基：若B是矩陣A中mm階非奇異子矩陣（B0），則B是線性規(guī)劃問題的一個(gè)基。不妨設(shè)：),.,(,.,.,.,11111mmmmmPPaaaaBjPjXjX , j=1，2，,m 基向量。 ，j=1，2，,m 基變量。 , j=m+1,n 非基變量。 求解 nmnnmmmmmmmmmmxaaxaabbxaaxaa.111111111110 max XbAXCXZ 基本解：稱上面求出的X解為基本解。 基本可行解：非負(fù)的基本解X稱為基本可行解 可行基：對應(yīng)基本可行解的基稱為可行基TmBxxxX).,(2

18、10.21nmmxxx)0,.,0,0,.,(21mbbbX T基變量令 可求出： 線性規(guī)劃解的關(guān)系圖可行解可行解 基本可行解基本可行解 最優(yōu)解？最優(yōu)解？ 例：求基本解、基本可行解、最優(yōu)解。max, ,.,zxxxxxxxxxxxii235210401251231312425x1x2x5x4x3z1 0 0 5 10 4 5 Y 2 0 4 5 2 0 17 Y 3 5 0 0 5 4 10 Y 4 0 5 5 0 -1 20 N5 10 0 -5 0 4 15 N6 5 2.5 0 0 1.5 17.5 Y 7 5 4 0 -3 0 22 N8 2 4 3 0 0 19 Y 是否基是否基可行

19、解可行解最優(yōu)解最優(yōu)解解：解： ：求基本解、基本可行解、最優(yōu)解。0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz3.的秩是A 1 0 0 4 00 1 0 0 40 0 1 2 1A練習(xí)：3 基本概念凸集：為凸集。K），則10（，KX ）1（X連線上的一切點(diǎn)KX，KX對維歐氏空間的一點(diǎn)集，n是k設(shè)）2（）1（）2（）1（ 頂點(diǎn):若K是凸集，XK；若X不能用不同的兩點(diǎn) 的線性組合表示為： 則X為頂點(diǎn). KXKX)2()1(和) 10( )1 ()2()1 (XXX凸集凸集 凸組合： .,.,., 1,.,2, 1, 10,.,.,)

20、()1()()2(21111)()1的凸組合為則使且若存在個(gè)點(diǎn)維向量空間中的是設(shè)（kkkkiiikkXXXXXXXkiknXXX n=2，k=3定理1: 若線性規(guī)劃問題存在可行域, 則其可行域: D=X|AX=b，X0 是凸集. 基本定理證明:0, , 0,)2()2()1()1()2()1()2()1(XbAXXbAXXXDXDX則有：設(shè)： bbbAXAXXXAAXXX )1 ( )1 ( )1 (0)2()1()2()1(代入約束條件，有：將顯然，1)(0 )1 ()2()1()2()1(XXXXXX：連線上的任意一點(diǎn)，則和為令只要驗(yàn)證只要驗(yàn)證X X在在D D中即可中即可是凸集。因此，DD

21、X, 引理：可行解X為基本可行解 X的正分量對應(yīng)的列向量線性無關(guān) 定理3：若可行域有界，線性規(guī)劃 問題的目標(biāo)函數(shù)一定可以在 其可行域的頂點(diǎn)上達(dá)到最優(yōu)。 定理2：線性規(guī)劃問題的基本可行解X 對應(yīng)于可行域D的頂點(diǎn)。 幾點(diǎn)結(jié)論： 線性規(guī)劃問題的可行域是凸集。 基可行解與可行域的頂點(diǎn)一一對應(yīng)，可行域有有限多個(gè)頂點(diǎn)。 最優(yōu)解必在頂點(diǎn)上得到。9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA可行域?yàn)橥辜尚杏驗(yàn)橥辜繕?biāo)函數(shù)不同時(shí)目標(biāo)函數(shù)不同時(shí)等值線的斜率不同等值線的斜率不同最優(yōu)解在頂點(diǎn)產(chǎn)生最優(yōu)解在頂點(diǎn)產(chǎn)生 目標(biāo)函數(shù)等目標(biāo)

22、函數(shù)等值線的斜率值線的斜率最優(yōu)解最優(yōu)解9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA可行域?yàn)橥辜尚杏驗(yàn)橥辜繕?biāo)函數(shù)不同時(shí)目標(biāo)函數(shù)不同時(shí)等值線的斜率不同等值線的斜率不同最優(yōu)解在頂點(diǎn)產(chǎn)生最優(yōu)解在頂點(diǎn)產(chǎn)生 目標(biāo)函數(shù)等目標(biāo)函數(shù)等值線的斜率值線的斜率最優(yōu)解最優(yōu)解9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA可行域?yàn)橥辜尚杏驗(yàn)橥辜繕?biāo)函數(shù)不同時(shí)目標(biāo)函數(shù)不同時(shí)等值線的斜率不同等值線的斜率不同最優(yōu)解在頂點(diǎn)產(chǎn)生最優(yōu)解在頂點(diǎn)產(chǎn)生 目

23、標(biāo)函數(shù)等目標(biāo)函數(shù)等值線的斜率值線的斜率最優(yōu)解最優(yōu)解求解LP的基本思路1.3 單純形法原理 本節(jié)通過一個(gè)引例，可以了解利用本節(jié)通過一個(gè)引例，可以了解利用單純形法求解線性規(guī)劃問題的思路，并單純形法求解線性規(guī)劃問題的思路，并將每一次的結(jié)果與圖解法作一對比，其將每一次的結(jié)果與圖解法作一對比，其幾何意義更為清楚。幾何意義更為清楚。引例引例（上一章例）（上一章例）0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz求解線性規(guī)劃問題的基本思路1、構(gòu)造初始可行基；2、求出一個(gè)基可行解（頂點(diǎn)）3、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解；4、基變化，轉(zhuǎn)2。要保證目

24、標(biāo)函數(shù)值比 原來更優(yōu)。從線性規(guī)劃解的性質(zhì)可知求解從線性規(guī)劃解的性質(zhì)可知求解線性規(guī)劃問題的基本思路。線性規(guī)劃問題的基本思路。第1步 確定初始基可行解 1 0 00 1 00 0 1),(543PPPB令：1 0 0 4 00 1 0 0 40 0 1 2 1),.,(51PPA根據(jù)根據(jù)顯然顯然 ， 可構(gòu)成初等可行基可構(gòu)成初等可行基B 。543,PPP 為基變量543,xxx 第2步 求出基可行解 )12,16, 8 , 0 , 0(, 0320 )0()0(2121XXxxxxZ得一基可行解令：代入目標(biāo)函數(shù) 4 12 416 2 8 2514213xxxxxxx基變量用非基基變量用非基變量表示，

25、并變量表示，并令非基變量為令非基變量為 0時(shí)對應(yīng)的解時(shí)對應(yīng)的解是否是最優(yōu)解？第3步 最優(yōu)性檢驗(yàn)分析目標(biāo)函數(shù)zxx02312檢驗(yàn)數(shù)檢驗(yàn)數(shù)0 時(shí)，時(shí)， 無解無解換基，繼續(xù)換基，繼續(xù)xxz1200 ,只要取只要取 或或 的的 值可能增大。值可能增大。換入？基變量換入？基變量換出？基變量換出？基變量考慮將考慮將 或或 換入為基變換入為基變量量21 xx第4步 基變換 換入基變量：zxxxx0230121122換入變量 x2（即選最大非負(fù)檢驗(yàn)數(shù)對應(yīng)的變量）一般選取一般選取 對應(yīng)的變量),max(2121,xx, 02, 1均可均可換入。 換出變量使換入的變量越大越好同時(shí)，新的解要可行。選非負(fù) 的最小者對

26、應(yīng)的變量換出i為換出變量52254233)4/12,2/8min( 04 12 0 16 02 8 xxxxxxx2x為換入變量，應(yīng)換出 ？ 變量。為換出變量變量：為換入變量，確定換出522542323) 4 /12, 2 / 8min( 04 12 0 16 02 8 xxxxxxxx3)4/12, 2/8min(0,min2323222121kaababab思考：當(dāng) 時(shí)會(huì)怎樣？02ka因此，基由 變?yōu)锽PPP ()342 轉(zhuǎn)第轉(zhuǎn)第2步：基變量用非基變量表示。步：基變量用非基變量表示。 第第3步：最優(yōu)性判斷步：最優(yōu)性判斷 檢驗(yàn)數(shù)檢驗(yàn)數(shù) 存在正，按第存在正，按第4步換基繼續(xù)迭代步換基繼續(xù)迭代

27、均非正，停止均非正，停止 （這時(shí)的解即是最優(yōu)解）（這時(shí)的解即是最優(yōu)解）2x為換入變量，應(yīng)換出 變量。為換出變量變量：為換入變量，確定換出522542323) 4 /12, 2 / 8min( 04 12 0 16 02 8 xxxxxxxx)(543PPPB )0,16,2,3,0(,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目標(biāo)函數(shù))0,16,2,3,0(,04329 41 3 416 21 2 124 416 82 )1()1(51515214513521412

28、3XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目標(biāo)函數(shù)轉(zhuǎn)轉(zhuǎn) 第第2步步 繼續(xù)迭代, 可得到:43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目標(biāo)函數(shù)為：最優(yōu)值最優(yōu)解 結(jié)合圖形法分析（單純形法的幾何意義）6 5 4 3 2 1 0 x2|123456789x1)0,16,2,3,0(,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目標(biāo)函數(shù)43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,

29、2(xxZXX目標(biāo)函數(shù)為：43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目標(biāo)函數(shù)為：A(0,3)B(2,3)C(4,2)D(4,0)單純形法迭代原理單純形法迭代原理從引例中了解了線性規(guī)劃的求解過程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法單單純形法迭代原理純形法迭代原理。 觀察法:直接觀察得到初始可行基 約束條件: 加入松弛變量即形成可行基。（下頁） 約束條件: 加入非負(fù)人工變量, 以后討論. 1、初始基可行解的確定 0,.,. . . 2111221122111111nmnmnmmmmnnmmnnmmxxxbxaxaxbxaxaxbxaxax1

30、 1、初始基可行解的確定、初始基可行解的確定 不妨設(shè)不妨設(shè) 為松弛變量，為松弛變量，則約束方程組可表示為則約束方程組可表示為mxxx,21 是一初始基可行解。有：令：)0,.,0 , 0 ,.,(),.2 , 1( 0. . . . 21111211222111111miinmnmnmmmmmnnmmnnmmbbbXmibxxxxaxabxxaxabxxaxabx1 1、初始基可行解的確定、初始基可行解的確定2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別nmnmmmmmnnmmnnmmxaxabxxaxabxxaxabx11211222111111. . . . 行解：一般情況下，對于基可

31、 nmjmijijijmiiinnmmjnmjmjmmjnmjjnnxaccbcxcxcxabcxabcxcxcxcZ11111111112221)( . )(.)( .代入目標(biāo)函數(shù)，有：2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別 jnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()( 檢驗(yàn)數(shù)令：令：2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別 (1) 最優(yōu)解判別定理：若： 為基可行解，且全部 則 為最優(yōu)解。 （2）唯一最優(yōu)解判別定理：若所有 則存在唯一最有解。 2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別 （3）無窮多最優(yōu)

32、解判定定理：若： 且存在某一個(gè)非基變量 則存在無窮多最優(yōu)解。（4）無界解判定定理：若有某一個(gè)非基 變量 并且對應(yīng)的非基變量的系數(shù) 則具有無界解。 nmjj,.,1, 00的kkx0的kmkmxmiakmi,.2,1,0,2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別 kmkmmmmkmkmkmkmxabxxabxxabx222111. . . , , 0, 00ZxxZZxakmkmkmkmkim當(dāng)即解都可行，對任意（4）之證明：）之證明：2 2、最優(yōu)性檢驗(yàn)與解的判別、最優(yōu)性檢驗(yàn)與解的判別最優(yōu)解判斷小結(jié) （用非基變量的檢驗(yàn)數(shù)）所有 基變量中有非零人工變量某非基變量檢驗(yàn)數(shù)為零唯一最優(yōu)解無窮多

33、最優(yōu)解無可行解對任一 有 換基繼續(xù)YYYYNNN無界解Njji ka000jji ka000jji ka000以后以后討論討論3、基變換 換入變量確定 對應(yīng)的 為換入變量. (一般)kmjmj)0(maxkmx注意注意：只要只要 對應(yīng)的變量對應(yīng)的變量 均可作為換入變量均可作為換入變量0jjxkmkmxZZ0此時(shí)，目標(biāo)函數(shù)此時(shí)，目標(biāo)函數(shù) 換出變量確定klmlkimkimiikmkmmmmkmkmkmkmabaabxabxxabxxabx22211100. .0 0 min3 3、基變換、基變換kmkmxZZ0kmxZ 大大大大（在可行的范圍內(nèi)）（在可行的范圍內(nèi)）lx4、迭代運(yùn)算 mmnkmmmm

34、klmlmnkmmnlmmlbbbaaaaaaaaabxxxxxx211ln1111111. . 1 . . . . . 1 . . . . . 1 . 寫成增廣矩陣的形式,進(jìn)行迭代.例： TXxxZbxxx xx)12,16,8,0,0(320 121681 0 0 4 00 1 0 0 40 0 1 2 1 )0(21543211x3x2x4x5xb4 4、迭代運(yùn)算、迭代運(yùn)算非基變量非基變量基變量基變量001通過初等行變通過初等行變換化主列為換化主列為主元主元 TXxxZ)0,16,2,3,0( 432931621/4 0 0 1 00 1 0 0 41/2- 0 1 0 1)1(511x

35、3x2x4x5xb4 4、迭代運(yùn)算、迭代運(yùn)算檢驗(yàn)數(shù)檢驗(yàn)數(shù)1.3 1.3 單純形法迭代原理單純形法迭代原理 為書寫規(guī)范和便于計(jì)算，對單純形法的計(jì)算設(shè)計(jì)了單純形表。每一次迭代對應(yīng)一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。本節(jié)介紹用單純形表計(jì)算線性規(guī)劃問題的步驟。 0. . . . 111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcxcxcxcZbxaxaxbxaxaxbxaxax 單純形表0 . 1. 1 0 . . . 1 0. 1 0 . . Z-211211212111121mnmmmnmmnmnmnmmbb

36、bcccccaaaaaabxxxxxE單位陣N非基陣基變量XB非基變量XNN0 單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 檢驗(yàn)數(shù)bbm1xxm1ccm1單純形表結(jié)構(gòu) 單純形表單純形表 24/65/1minA0znmcccc21C已知xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1單純形表結(jié)構(gòu) 單純形表單純形表A0z)0 , 0 ,(1mbbX基可行解：單純形表結(jié)構(gòu) 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1A0zj

37、nmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()( 檢驗(yàn)數(shù)令：令：有時(shí)不有時(shí)不寫此項(xiàng)寫此項(xiàng)單純形表結(jié)構(gòu) 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()( 檢驗(yàn)數(shù)令：令：jcmjjaa1j單純形表結(jié)構(gòu) 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1A0zkmmkmaa, 1

38、km 不妨設(shè)此不妨設(shè)此為主列為主列klmlkimkimiiabaab0minl主行主行單純形表結(jié)構(gòu) 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗(yàn)數(shù)bbm1xxm1ccm1A0zkmmkmaa, 1km lkmla,主元主元用單純形表求解LP問題0,524261552max212121221xxxxxxxxxz例、用單純形表求解例、用單純形表求解LPLP問題問題解：化標(biāo)準(zhǔn)型0,524261550002max515214213254321xxxxxxxxxxxxxxxz 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2

39、0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 jcBCbBX1x3x2x4x5xjjzc 3x4x5x 24/65/1min主元化為1主列單位向量 換出 換入1x4x表表1：列初始單純形表：列初始單純形表 （單位矩陣對應(yīng)的變量為基變量）（單位矩陣對應(yīng)的變量為基變量）正檢驗(yàn)數(shù)中最大者對正檢驗(yàn)數(shù)中最大者對應(yīng)的列為主列應(yīng)的列為主列 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 jcBCbBX1x3x2x4x5xjjzc 3x1x5x 15/524/26/4min 0*5 2*2

40、/6 +0*4/61- 2/3=表表2：換基：換基 （初等行變換，主列化為單位向量，主元為（初等行變換，主列化為單位向量，主元為1）檢驗(yàn)數(shù)檢驗(yàn)數(shù)0確定主列確定主列 最小最小確定主列確定主列主元主元 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 jcBCbBX1x3x2x4x5xjjzc 3x1x2x min檢驗(yàn)數(shù)0，則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu)。例: 求解線性規(guī)劃問題0,1 232 411 2 332131321321321xxxxxxxxxxxxxxMinZ32

41、13xxxMaxz一、大 M 法 0,1 23 2 411 2 00376543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxMinZ7654321003MxMxxxxxxMaxz一、大 M 法解:l加入松弛變量和剩余變量進(jìn)行標(biāo)準(zhǔn)加入松弛變量和剩余變量進(jìn)行標(biāo)準(zhǔn) 化化, , 加入人工變量構(gòu)造初始可行基加入人工變量構(gòu)造初始可行基. . 求解結(jié)果出現(xiàn)檢驗(yàn)數(shù)非正 若基變量中含非零的人工變量， 則無可行解； 否則，有最優(yōu)解。j 0一、大 M 法l用單純形法求解（見下頁）。用單純形法求解（見下頁）。目標(biāo)函數(shù)中添加“罰因子”-M為人工變量系數(shù)，只要人工變量

42、0，則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu)。 1 -2 1 -4 1 2 -2 0 1 3-63-6M M -1 3M-1M M -1 3M-1 3 -1 -1 x x1 x x2 x x3 0 x x4 11 -M x x6 3 -M x x7 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 11 3/2 1 0 0 1 0 0 1 0 0 - M - M x x6 x x7 i表表1（初始單純形表）（初始單純形表）一、大 M 法（單純形法求解） 3 -2 0 0 1 0 -2 0 1 1 1 M M-1-1 0 0 3 -1 -1x x1 x

43、 x2 x x3 0 x x4 10 -M x x6 1 -1 x x3 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 1 0 -1 1 -2 0 1 0 1 1-3 3M M - M - M x x6 x x7 i一、大 M 法（單純形法求解）表表2 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1 -1 x x1 x x2 x x3 0 x x4 12 -1 x x2 1 -1 x x3 1C j - Z j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x x4 x x5 4 i 2 -5

44、1 -2 0 1 1-1-M -1M -1 -M-M - M - M x x6 x x7 i表表3一、大 M 法（單純形法求解） 1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x x1 x x2 x x3 3 x x1 4 -1 x x2 1 -1 x x3 9 2 C j CB XB b1/3 -2/3 0 -1 2/3 -4/3 -1/3 -1/3 0 0 x x4 x x5 2/3 -5/3 1 -2 4/3 -7/3 1/3-1/3-M 2/3-MM 2/3-M - M - M x x6 x x7 i表表4一、大 M 法（單純形法求解）914321xxx檢驗(yàn)數(shù)均非正，

45、此檢驗(yàn)數(shù)均非正，此為最終單純形表為最終單純形表M在計(jì)算機(jī)上處理困難。分階段處理先求初始基，再求解。二、兩階段法二、兩階段法二、兩階段法 第一階段: 構(gòu)造如下的線性規(guī)劃問題0.,., . . . , 121221122222212111121211121mnnnmmnnmnmmnnnnnnmnnnxxxxxbxxaxaxabxxaxaxabxxaxaxaxxxMin 用單純形法求解上述問題用單純形法求解上述問題,若若=0,進(jìn)進(jìn)入第二階段入第二階段,否則否則,原問題無可行解。原問題無可行解。 第二階段：去掉人工變量，還原目標(biāo)函第二階段：去掉人工變量，還原目標(biāo)函數(shù)系數(shù)，做出初始單純形表。數(shù)系數(shù)，做出

46、初始單純形表。 用單純形法求解即可。用單純形法求解即可。二、兩階段法二、兩階段法下面舉例說明，仍用大M法的例。0,1 232 411 232131321321xxxxxxxxxxx3213xxxMaxz例：二、兩階段法二、兩階段法 0,1 23 2 411 2 765432173165321432176xxxxxxxxxxxxxxxxxxxxxMin二、兩階段法二、兩階段法l構(gòu)造第一階段問題并求解構(gòu)造第一階段問題并求解解：解：用單純形法求解用單純形法求解二、兩階段法二、兩階段法（第一階段、求第一階段、求min min ） 1 -2 1 -4 1 2 -2 0 1 -6 1 3 0 0 0 x

47、x1 x x2 x x3 0 x x4 11 -1 x x6 3 -1 x x7 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 - 1 x x4 x x5 x x6 0 11 0 3/2 1 1 0 - 1 x x7 i i表表1jjzc -1 - -2 1 1 - -3 - 1 x x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x x1 x x2 x x3 0 x x4 10 -1 x x6 1 0 x x3 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 x x4 x x5

48、 x x6i二、兩階段法二、兩階段法（第一階段、求第一階段、求min min ）表表2jjzc -5 4 -2 - 1 - -1 - 1 x x7 3 0 0 0 1 0 -2 0 1 0 0 0 0 0 0 x x1 x x2 x x3 0 x x4 12 0 x x2 1 0 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 -1 0 0 -1 x x4 x x5 x x6i二、兩階段法二、兩階段法（第一階段、求第一階段、求min min ）表表3：最終單純形表：最終單純形表jjzc 不含人工不含人工變量且變量且=0=0二、兩階段法二、兩階段法 3 0

49、0 0 1 0 -2 0 1 3 -1 -1 x x1 x x2 x x3 0 x x4 12 -1 x x2 1 -1 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 x x4 x x5 ijjzc 1 0 0 0 -1二、兩階段法二、兩階段法 1 0 0 0 1 0 0 0 1 3 -1 -1 x x1 x x2 x x3 3 x x1 4 -1 x x2 1 -1 x x3 9 C i CB XB b 1/3 -2/3 0 -1 2/3 -4/3 0 0 x x4 x x5 i 0 0 0 -1/3 -1/3jjzc 914321xxx單純形法計(jì)算中

50、的幾個(gè)問題j 0l1、目標(biāo)函數(shù)極小化時(shí)解的最優(yōu)性判斷、目標(biāo)函數(shù)極小化時(shí)解的最優(yōu)性判斷 只需用檢驗(yàn)數(shù) 作為最優(yōu)性的標(biāo)志。j 0l2、無可行解的判斷、無可行解的判斷 當(dāng)求解結(jié)果出現(xiàn)所有 時(shí)，如基變量仍 含有非零的人工變量（兩階段法求解時(shí)第一階 段目標(biāo)函數(shù)值不等于0），則問題無可行解。退化 基可行解中存在基變量=0的解退化解 換入變量和換出變量的換入變量和換出變量的BlandBland規(guī)則規(guī)則選擇 中下標(biāo)最小的非基變量 為換入變量, 這里:當(dāng)按 規(guī)則計(jì)算存在兩個(gè)和兩個(gè)以上最小比值時(shí),選下標(biāo)最小的基變量為換出變量。jkx)0min(jjk單純形法計(jì)算中的幾個(gè)問題單純形法計(jì)算中的幾個(gè)問題 不妨設(shè)基為不妨

51、設(shè)基為mPPPB21基變量基變量非基變量非基變量0.maxXbAXtsCXz設(shè)線性規(guī)劃問題設(shè)線性規(guī)劃問題)()()()(21NBNBnCCCXXXNBPPPA則則NNBNBNBXNbNXbBXbNXBXXXNBbAX)()(1 其中其中NBNbBb11,令令 得當(dāng)前的基解為：得當(dāng)前的基解為：0NXbBbXB1當(dāng)前基解當(dāng)前基解約束方程組約束方程組NBNBNBNBNNBBNBNBXNCCbCXNBCCbBCXCXCXXCCz)()()(11當(dāng)前目標(biāo)值當(dāng)前目標(biāo)值目標(biāo)函數(shù)目標(biāo)函數(shù)bBCbCzBB10令令 得當(dāng)前的目標(biāo)函數(shù)值為：得當(dāng)前的目標(biāo)函數(shù)值為：0NX nBnnmBmmnmmnmBNNPCCPCCP

52、PCCCCNCC)()(111111當(dāng)前檢驗(yàn)數(shù)當(dāng)前檢驗(yàn)數(shù) 檢驗(yàn)數(shù)檢驗(yàn)數(shù)其中其中jjPBP1當(dāng)前當(dāng)前 對應(yīng)的系數(shù)列對應(yīng)的系數(shù)列jx線性規(guī)劃問題線性規(guī)劃問題0.maxXbAXtsCXz化為標(biāo)準(zhǔn)型，引入松弛變量化為標(biāo)準(zhǔn)型，引入松弛變量sX0, 0. .0maxsssXXbIXAXtsXCXz初始單純形表初始單純形表00NBjjssNBCCzcINBbXXXX非基變量非基變量基變量基變量初始基變量初始基變量11110BCNBCCzcBNBIbBXCXXXBBNjjBBsNB基變量基變量非基變量非基變量當(dāng)基變量為當(dāng)基變量為 時(shí)，新的單純形表時(shí)，新的單純形表BX當(dāng)前檢驗(yàn)數(shù)當(dāng)前檢驗(yàn)數(shù)當(dāng)前基解當(dāng)前基解線性規(guī)劃

53、模型單純形法習(xí)題課基本概念 線性規(guī)劃模型 三個(gè)要素三個(gè)要素： 決策變量、目標(biāo)函數(shù)、約束條件 線性性線性性 線性規(guī)劃解的性質(zhì)線性規(guī)劃問題的可行域是凸集。最優(yōu)解必在頂點(diǎn)上得到。 線性規(guī)劃求解方法圖解法單純形法本次習(xí)題課內(nèi)容單純形法小結(jié) 一般線性規(guī)劃問題的標(biāo)準(zhǔn)化及初始單純形法表.變量變量0, 0,: 0 0 jjjjjjjjjjjxxxxxxxxxxx令：無約束令不需要處理 約束條件約束條件 在加人工變量加剩余變量加人工變量加松弛變量約束條件兩端同乘不需要處理, 1- 0 0bb單純形法小結(jié) 目標(biāo)函數(shù)目標(biāo)函數(shù)MZZZ:0: maxZ,Z min max人工變量松弛變量和剩余變量的系數(shù)加入變量求令：不需要處理 單純形法計(jì)算步驟框圖（略）單純形法小結(jié) 一、已知某LP的初始單純形表和單純形法 迭代的表，求未知數(shù)al的值。 6 b c d 1 0 1 -1 3 e 0 1 a -1 2 0 0 f g 2 -1 1/2 0 4 h i 1 1/2