1、運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外線線 性性 規(guī)劃規(guī)劃Linear ProgrammingLinear Programming運(yùn)運(yùn) 籌籌 學(xué)學(xué) 課課 件件第第 1 章章 線線 性性 規(guī)規(guī) 劃劃|線性規(guī)劃問(wèn)題線性規(guī)劃問(wèn)題提出提出|可行區(qū)域與基本可行解可行區(qū)域與基本可行解|單純形算法單純形算法|單純形法進(jìn)一步討論單純形法進(jìn)一步討論1.1 線線 性性 規(guī)規(guī) 劃劃 問(wèn)問(wèn) 題提出題提出|線性規(guī)劃例題線性規(guī)劃例題 生產(chǎn)計(jì)劃問(wèn)題生產(chǎn)計(jì)劃問(wèn)題 |線性規(guī)劃模型線性規(guī)劃模型 一般形式一般形式 規(guī)范形式規(guī)范形式 標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式 形式轉(zhuǎn)換形式轉(zhuǎn)換 概念概念 圖解法圖解法 1.1.1

2、 線性規(guī)劃例題線性規(guī)劃例題某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如表某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如表所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃單位產(chǎn)品所需原單位產(chǎn)品所需原料數(shù)量（公斤）料數(shù)量（公斤）產(chǎn)品產(chǎn)品Q1產(chǎn)品產(chǎn)品Q2產(chǎn)品產(chǎn)品Q3原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000單位產(chǎn)品的利潤(rùn)單位產(chǎn)品的利潤(rùn)（千元）（千元）354 生生 產(chǎn)產(chǎn) 計(jì)計(jì) 劃劃 問(wèn)問(wèn) 題題問(wèn)問(wèn) 題題 分分 析析可控因素：可控因素：每天生產(chǎn)三種產(chǎn)品的數(shù)量，分別設(shè)為每天生產(chǎn)三種產(chǎn)品的數(shù)量，分別設(shè)為321,xxx 目標(biāo)

3、：目標(biāo)：每天的生產(chǎn)利潤(rùn)最大每天的生產(chǎn)利潤(rùn)最大 利潤(rùn)函數(shù)利潤(rùn)函數(shù)321453xxx 受制條件：受制條件： 每天原料的需求量不超過(guò)可用量：每天原料的需求量不超過(guò)可用量： 原料原料1P：15003221 xx 原料原料2P：8004232 xx 原料原料3P：2000523321 xxx 蘊(yùn)含約束：蘊(yùn)含約束：產(chǎn)量為非負(fù)數(shù)產(chǎn)量為非負(fù)數(shù) 0,321 xxx 模模 型型321453maxxxx 15003221 xx s.t. 8004232 xx 2000523321 xxx 0,321 xxx 1.1.2 )(0)(,),(.),(.),(.2122112222212111212111無(wú)限制 nmnm

4、nmmnnnnxxxbxaxaxabxaxaxabxaxaxatsnnxcxcxczMax 2211min)(或或 一一 般般 形形 式式注注 釋釋njxj,.,2 , 1; 為待定的為待定的決策變量決策變量， ),(21ncccc 為為價(jià)值向量?jī)r(jià)值向量， njcj,.,2 , 1; 為為價(jià)值系數(shù)價(jià)值系數(shù)， ),.,(21mbbbb 為為右端向量右端向量， 矩陣矩陣 為為系數(shù)矩陣系數(shù)矩陣。 mnmmnnaaaaaaaaaA212222111211 向向 量量 形形 式式 0),(),(max(min)1xbxPcxznjjj mnmmnnnmnaaaaaaaaaPPPbbbbbcccc2122

5、221112112121210,),(系系數(shù)數(shù)矩矩陣陣：資資源源向向量量：價(jià)價(jià)值值向向量量： 矩矩 陣陣 形形 式式 0),(),(max(min)xbAxcxz nmnmmnnmnPPPaaaaaaaaaAbbbbbcccc2121222211121121210,),( 系系數(shù)數(shù)矩矩陣陣：資資源源向向量量：價(jià)價(jià)值值向向量量：0,.min)(21211122221121112121112211 nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxczMax或 標(biāo)標(biāo) 準(zhǔn)準(zhǔn) 形形 式式 變一般形式為標(biāo)準(zhǔn)形式變一般形式為標(biāo)準(zhǔn)形式v約束轉(zhuǎn)換約束轉(zhuǎn)換v實(shí)例實(shí)例令令自自

6、由由變變量量 jjjxxx，其其中中 jjxx ,為為非非負(fù)負(fù)變變量量 求最大可以等價(jià)成求負(fù)的最小求最大可以等價(jià)成求負(fù)的最小 xcxc minmax v目標(biāo)轉(zhuǎn)換目標(biāo)轉(zhuǎn)換v變量轉(zhuǎn)換變量轉(zhuǎn)換不不 等等 式式 變變 等等 式式ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 或或 ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 松弛變量松弛變量剩余變量剩余變量幾幾 個(gè)個(gè) 概概 念念可行解（或可行點(diǎn)） ：可行解（或可行點(diǎn)） ：滿足所有約束條件的向量滿足所有約束條件的向量 ),(21nxxxx 可行集（或可行域）可行集（或可行

7、域） ：所有的可行解的全體：所有的可行解的全體 0, xbAxxD 最優(yōu)解：最優(yōu)解：在可行域中目標(biāo)函數(shù)值最大（或最小）的可行解，最優(yōu)解的全體在可行域中目標(biāo)函數(shù)值最大（或最小）的可行解，最優(yōu)解的全體稱為最優(yōu)解集合稱為最優(yōu)解集合 DyycxcDxO , 最優(yōu)值：最優(yōu)值：最優(yōu)解的目標(biāo)函數(shù)值最優(yōu)解的目標(biāo)函數(shù)值 Oxxcv , 圖圖 解解 法法例例 解線性規(guī)劃解線性規(guī)劃 注注 釋釋解可能出現(xiàn)的情況解可能出現(xiàn)的情況：| 可行域是空集可行域是空集| 可行域無(wú)界無(wú)最優(yōu)解可行域無(wú)界無(wú)最優(yōu)解| 最優(yōu)解存在且唯一，則一定在頂點(diǎn)上達(dá)到最優(yōu)解存在且唯一，則一定在頂點(diǎn)上達(dá)到| 最優(yōu)解存在且不唯一，一定存在頂點(diǎn)是最優(yōu)解最優(yōu)

8、解存在且不唯一，一定存在頂點(diǎn)是最優(yōu)解1.2 可行區(qū)域與基本可行解可行區(qū)域與基本可行解 |可行域的幾何結(jié)構(gòu)可行域的幾何結(jié)構(gòu)| 基本可行解與基本定理基本可行解與基本定理可行域的幾何結(jié)構(gòu)可行域的幾何結(jié)構(gòu)|基本假設(shè)基本假設(shè)|凸集凸集|可行域的凸性可行域的凸性基基 本本 假假 設(shè)設(shè)凸凸 集集 與與 頂頂 點(diǎn)點(diǎn)基基 本本 可可 行行 解解 與與 基基 本本 定定 理理|定義定義|基本定理基本定理|問(wèn)題問(wèn)題第第29頁(yè)頁(yè)例例:基本解不一定是可行解基本解不一定是可行解基基 本本 定定 理理證明：由基可行解的定義知，必要性顯然成立。證明：由基可行解的定義知，必要性顯然成立。充分性：若向量充分性：若向量kppp,2

9、1線性獨(dú)立，則必有線性獨(dú)立，則必有mk 當(dāng)當(dāng)mk 時(shí)，它們恰好構(gòu)成一個(gè)基，從而為相應(yīng)的時(shí)，它們恰好構(gòu)成一個(gè)基，從而為相應(yīng)的基可行解；當(dāng)基可行解；當(dāng)mk 時(shí)，則一定能從剩余的列向量時(shí)，則一定能從剩余的列向量中取出中取出m-k個(gè)與個(gè)與kppp,21構(gòu)成最大的線性獨(dú)立向量構(gòu)成最大的線性獨(dú)立向量組組其對(duì)應(yīng)的解恰為其對(duì)應(yīng)的解恰為x，所以，所以，x是基可行解。是基可行解。證明證明 (1) x不是基可行解，則不是基可行解，則x不是可行域的頂點(diǎn)。不是可行域的頂點(diǎn)。不失一般性，假設(shè)不失一般性，假設(shè)x的前的前m個(gè)分量為正，則有個(gè)分量為正，則有 miiibxP1由定理由定理2知，知，mPPP,21線性相關(guān)，即存在一

10、組線性相關(guān)，即存在一組不全為不全為0的數(shù)的數(shù)), 2 , 1(mii 使得有使得有02211 mmPPP 上式乘上一個(gè)不為上式乘上一個(gè)不為0的數(shù)的數(shù) 02211 mmPPP與與 miiibxP1相加、相減得相加、相減得bPxPxPxmmm )()()(222111bPxPxPxmmm )()()(222111令令TmmxxxX0 , 0),( ,),(),(2211)1( TmmxxxX0 , 0),( ,),(),(2211)2( 的選取保證，對(duì)所有的的選取保證，對(duì)所有的mi, 2 , 1 有有0 iix所以，所以，CXCX )2()1(,且且)2()1(2121XXX 所以，所以， x不是

11、可行域的頂點(diǎn)不是可行域的頂點(diǎn)(2) x不是可行域的頂點(diǎn)，則不是可行域的頂點(diǎn)，則x不是基可行解。不是基可行解。不失一般性，設(shè)不失一般性，設(shè)TrxxxX0 , 0 ,21 不是可行域的頂點(diǎn)，所以可以找到可行域內(nèi)另外不是可行域的頂點(diǎn)，所以可以找到可行域內(nèi)另外兩個(gè)不同點(diǎn)兩個(gè)不同點(diǎn)Y,Z，有，有X=AY+(1-a)Z（0a0,1-a0，故當(dāng)，故當(dāng)0 0時(shí)，必有時(shí)，必有jjjzyx 因?yàn)橐驗(yàn)?njrjjjjjbxPxP11 njrjjjjjbyPyP11所以所以 njrjjjjjbzPzP11上面兩式相減得上面兩式相減得 rjjjjPzy10)(因?yàn)橐驗(yàn)?(jjzy 不全為不全為0，故，故rPPP,21線

12、性相關(guān)，即線性相關(guān)，即x不是基本可行解。不是基本可行解。1.3 單單 純純 形形 算算 法法|算法的三個(gè)階段算法的三個(gè)階段|算法步驟算法步驟|單純形表單純形表|算例算例階階 段段 1：確定初始基可行解：確定初始基可行解0 .max: xbAxtscxzLP假設(shè)問(wèn)題假設(shè)問(wèn)題引入松弛變量引入松弛變量Tmnnnsxxxx),(21 0, .0max sssxxbIxAxtsxcxz得得則，可設(shè)則，可設(shè)IB 則，約束變?yōu)閯t，約束變?yōu)?則，初始基可行解為則，初始基可行解為 bBxAxBN bxB 則則 0bxxxNB階階 段段 2：由一個(gè)基可行解到另一個(gè)：由一個(gè)基可行解到另一個(gè)設(shè)初始基可行解設(shè)初始基可行

13、解Tnxxxx),(0001)0(2 又設(shè)前又設(shè)前m個(gè)坐標(biāo)非個(gè)坐標(biāo)非0，即，即Tmxxxx)0 , 0 , 0 ,(0001)0(2 因?yàn)槭腔尚薪猓砸驗(yàn)槭腔尚薪猓?miiibxP10若我們總假定有方法使基矩陣是單位矩陣，則上式展若我們總假定有方法使基矩陣是單位矩陣，則上式展開為開為 mnmjmmmnjmnjmnjmmbbbaaaaaaaaabpppppp21,1,2,21,2, 1, 11, 1121100010001mppp,21因?yàn)橐驗(yàn)?miiijjpap1是基，所以，其余向量可由它是基，所以，其余向量可由它線性表示線性表示01 miiijjpap對(duì)上式乘以正數(shù)對(duì)上式乘以正數(shù)

14、0)(1 miiijjpap miiibxP10上式與上式與相加得相加得bppaxmijiiji 10)( 從中可找到另一個(gè)滿足約束的點(diǎn)從中可找到另一個(gè)滿足約束的點(diǎn))0 , 0 ,(0101)1( mjmjaxaxX 要使它成為基可行解，需要滿足要使它成為基可行解，需要滿足ljlijijiiaxaax000min 0, 00101 mjmjaxax ，且至少有一個(gè)取等號(hào)。，且至少有一個(gè)取等號(hào)。又因?yàn)椋粲忠驗(yàn)椋鬭ij0，則條件自然滿足，所以，只需取，則條件自然滿足，所以，只需取即可。即可。階階 段段 3：最優(yōu)性檢驗(yàn)和解的判別：最優(yōu)性檢驗(yàn)和解的判別把基可行解把基可行解)1()0(, XX分別代

15、入目標(biāo)分別代入目標(biāo))()(1)0(10)1(10)0( miijijjmiijiimiiiacczcaxczxcz )(1 miijijjacc 令令（1）當(dāng)所有的）當(dāng)所有的0 j 說(shuō)明：現(xiàn)有頂點(diǎn)的目標(biāo)函數(shù)值說(shuō)明：現(xiàn)有頂點(diǎn)的目標(biāo)函數(shù)值比相鄰各頂點(diǎn)的目標(biāo)函數(shù)值都大，現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基比相鄰各頂點(diǎn)的目標(biāo)函數(shù)值都大，現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解即為唯一最優(yōu)解。可行解即為唯一最優(yōu)解。（2）當(dāng)所有的）當(dāng)所有的0 j 又對(duì)某個(gè)非基變量又對(duì)某個(gè)非基變量jx有有0 jjzc則，則，無(wú)窮多最優(yōu)解。無(wú)窮多最優(yōu)解。（3）若存在某個(gè)）若存在某個(gè)0 j 又又jp無(wú)界解。無(wú)界解。的所有分量的所有分量0 ija算算 法法 步步 驟

16、驟單純形表例子單純形表例子例：例： 0,825943.510max432142132121xxxxxxxxxxtsxxz解：0 x321/5014/51-3/510 x18/512/501/5cjzj010-25x23/2015/14-3/1410 x1110-1/7 2/7cjzj00-5/14-25/14cj10500cBxBbx1x2x3x40 x3934100 x485201cjzj105005858,39min 235258,514521min 2/3, 1, 021 xxj，達(dá)到最優(yōu)解達(dá)到最優(yōu)解 第第52頁(yè)頁(yè)單純形法的矩陣描述單純形法的矩陣描述0 .max: xbAxtscxzLP

17、考慮問(wèn)題考慮問(wèn)題引入松弛變量引入松弛變量Tmnnnsxxxx),(21 0, .0max sssxxbIxAxtsxcxz得得第第53頁(yè)頁(yè)設(shè)設(shè)B是一個(gè)是一個(gè)可行基可行基，若，若),(),(NBIA則對(duì)應(yīng)于則對(duì)應(yīng)于B的變量向量的變量向量TmBBBBxxxx),(21 則則 NBxxx同時(shí)將同時(shí)將C也分成兩塊也分成兩塊 NBCCC 所以所以,有有 bxxNBNB NNBBNBNBxCxCxxCC 第第54頁(yè)頁(yè)所以，所以，LP問(wèn)題寫成問(wèn)題寫成0, )2( . NBNBxxbNxBxts)1( maxNNBBxCxCz 將（將（2）移項(xiàng)后得）移項(xiàng)后得)3( - NBNxbBx 將（將（3）左乘）左乘1

18、 B)4( - 11NBNxBbBx 將（將（4）代入目標(biāo)（）代入目標(biāo)（1）得）得)5( )-( 1N1NBBxNBCCbBCz 第第55頁(yè)頁(yè)單純形法進(jìn)一步討論單純形法進(jìn)一步討論|兩階段法兩階段法|大大M法法|退化退化說(shuō)明說(shuō)明第第56頁(yè)頁(yè)為什么要做進(jìn)一步討論為什么要做進(jìn)一步討論?第第57頁(yè)頁(yè)兩兩 階階 段段 法法第一階段第一階段：不考慮原問(wèn)題是否存在基可行解，給原問(wèn)：不考慮原問(wèn)題是否存在基可行解，給原問(wèn)題加入人工變量，并構(gòu)造只含人工變量的目標(biāo)函數(shù)題加入人工變量，并構(gòu)造只含人工變量的目標(biāo)函數(shù)w，并要求實(shí)現(xiàn)最小化。若求解得并要求實(shí)現(xiàn)最小化。若求解得w=0，說(shuō)明原問(wèn)題存在基，說(shuō)明原問(wèn)題存在基可行解，

19、可進(jìn)入第二階段，否，原問(wèn)題無(wú)可行解，停。可行解，可進(jìn)入第二階段，否，原問(wèn)題無(wú)可行解，停。第二階段第二階段：將第一階段計(jì)算得到的最終表，除去人工：將第一階段計(jì)算得到的最終表，除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系變量，將目標(biāo)函數(shù)行的系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，作為第二階段的初始表。數(shù)，作為第二階段的初始表。例例算算 例例解解:第一階段第一階段 cj0000011cBxBbx1x2x3x4x5x6x70 x4111-2110001x63-4120-1101x71-2010001 Cj-zj6-1-30100 cj00000110 x4103-20100-11x610100-11-

20、20 x31-2010001 Cj-zj0-1001030 x4123001-22-50 x210100-11-20 x31-2010001 Cj-zj0000011所以，所以，w=0第二階段第二階段 cj-31100cBxBbx1x2x3x4x50 x4123001-21x210100-11x31-20100 Cj-zj-10001-3x141001/3-2/31x210100-11x390012/3-4/3 Cj-zj0001/31/3大大 M 法法在一個(gè)在一個(gè)LP問(wèn)題的約束條件中加入人工變量后，要求人問(wèn)題的約束條件中加入人工變量后，要求人工變量對(duì)目標(biāo)函數(shù)取值不受影響，為此假定人工變量工變量對(duì)目標(biāo)函數(shù)取值不受影響，為此假定人工變量在目標(biāo)函數(shù)中的系數(shù)為（在目標(biāo)函數(shù)中的系數(shù)為（M），這樣目標(biāo)要實(shí)現(xiàn)最大），這樣目標(biāo)要實(shí)現(xiàn)最大化時(shí)，必須把人工變量換出基，否則不能最大化。化時(shí)，必須把人工變量換出基，否則不能最大化。采用大采用大 M 法，引入人工變量，構(gòu)造新的線性規(guī)劃問(wèn)題（法，引入人工變量，構(gòu)造新的線性規(guī)劃問(wèn)題（LP）單純形表如下單純形表如下例：例：cj-31100MMcBxB