【正文】 1 12 121 22 2nnm m m na a aa a aAa a a????? ? ?????其中 系數(shù)矩陣 決策向量 假設(shè) A 的秩為 m , 且只討論 m n 的情 形。 2 線性規(guī)劃問題的圖解法 圖解法優(yōu)點(diǎn)： 直觀、易掌握。 稱為無最優(yōu)解 。 2 線性規(guī)劃問題的圖解法 max z = 15x1 +25x2 . x1 + 3x2 ≤ 60 x1 + x2 ≤ 40 x1， x2 ≥ 0 (40,0) (0,0) B C (30,10) 123 60xx??40??O (0,20) A L1 L2 Z=250 目標(biāo)函數(shù)變形： x2=3/5 x1+z/25 x2 x1 最優(yōu)解 ： x1=30 x2 =10 最優(yōu)值 ： zmax=700 B點(diǎn)是使 z達(dá)到最大的唯一可行點(diǎn) 第一章 線性規(guī)劃及單純形法 LP問題圖解法的基本步驟 ： 在平面上建立直角坐標(biāo)系； 圖示約束條件，確定可行域和頂點(diǎn)坐標(biāo)； 圖示目標(biāo)函數(shù)（等值線）和移動(dòng)方向； 尋找最優(yōu)解。 2 線性規(guī)劃問題的圖解法 定義 1 在 LP 問題中，凡滿足約束條件 (2)、 (3)的 解 x = (x1,x2,…, xn)T 稱為 LP 問題的可行解， 所有可行解的集合稱為可行解集（或可行域）。max 因?yàn)榍? min z 等價(jià)于求 max (z)， 令 z’ = z， 即化為 ： 約束條件為不等式， ??? ??njinjij bxxa11???njijij bxa1??njijij bxa1xn+1 ≥ 0 松弛變量 如何處理？ 167。 決策變量 xj≥0 約束條件 —— 一組決策變量的線性等式或不等式 目標(biāo)函數(shù) —— 決策變量的線性函數(shù) 第一章 線性規(guī)劃及單純形法 max（ min） z = c1x1 + c2x2 + … + xn . a11x1 + a12x2 + … + a1nxn ≤（ 或 =， ≥） b1 a21x1 + a22x2 + … + a2nxn ≤（ 或 =， ≥） b2 … … am1x1 + am2x2 + … + amnxn ≤（ 或 =， ≥） bm xj ≥ 0 （ j = 1,2,…,n） 其中 aij、 bi、 cj（ i = 1,2,…,m； j = 1,2,…,n） 為已知 常數(shù) 線性規(guī)劃問題的一般形式： 167。設(shè) Bj 內(nèi)含有 Ai 種營(yíng)養(yǎng)數(shù)量為 aij (i=1~m,j=1~n)，又知人們每 天對(duì) Ai 營(yíng)養(yǎng)的最少 需要量為 bi。 167。來自 中國最大的資料庫下載 運(yùn) 籌 學(xué) Operations Research 第一章 線性規(guī)劃及單純形法 第一章 線性規(guī)劃及單純形法 線性規(guī)劃 （ Linear Programming，簡(jiǎn)稱 LP） 運(yùn)籌學(xué)的一個(gè)重要分支，是運(yùn)籌學(xué)中研究較早、發(fā)展較 快、理論上較成熟和應(yīng)用上極為廣泛的一個(gè)分支。 1 線性規(guī)劃問題及其數(shù)學(xué)模型 . 1 資源的合理利用問題 問：如何安排生產(chǎn)計(jì)劃， 使得既能充分利用現(xiàn)有資 源又使總利潤(rùn)最大？ 表 1 產(chǎn)品 資源 甲 乙 庫存量 A 1 3 60 B 1 1 40 單件利潤(rùn) 15 25 某工廠在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品， 要消耗 A、 B 兩種資源，已知每件產(chǎn)品對(duì)這兩種資源的 消耗，這兩種資源的現(xiàn)有數(shù)量和每件產(chǎn)品可獲得的利 潤(rùn)如表 1。見表 2： 表 2 食品 最少 營(yíng)養(yǎng) B1 B2 … Bn 需要量 A1 a11 a12 … a1n b1 A2 a21 a22 … a2n b2 … … … … … … Am am1 am2 … amn bm 單 價(jià) c1 c2 … 試在滿足營(yíng)養(yǎng)要 求的前提下，確定食 品的購買量，使食品 的總價(jià)格最低。 1 線性規(guī)劃問題及其數(shù)學(xué)模型 線性規(guī)劃問題的標(biāo)準(zhǔn)形式： max z = c1x1 + c2x2 + … + xn . a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 … … am1x1 + am2x2 + … + amnxn = bm xj ≥ 0 （ j = 1,2,…,n） bi ≥ 0 （ i = 1,2,…,m） 特點(diǎn)： 目標(biāo)函數(shù)為極 大化； 除決策變量的 非負(fù)約束外，所有 的約束條件都是等 式，且右端常數(shù)均 為非負(fù)； 所有決策變量 均非負(fù) 。 1 線性規(guī)劃問題及其數(shù)學(xué)模型 ３、 右端項(xiàng) bi 0時(shí)，只需將等式兩端同乘（ 1） 則右端項(xiàng)必大于零 決策變量無非負(fù)約束 設(shè) xj 沒有非負(fù)約束，若 xj ≤0 ，可令 xj = xj’ ， 則 xj’ ≥0 ； 又若 xj 為自由變量，即 xj 可為任意實(shí)數(shù)， 可令 xj = xj’ xj’’ ，且 xj’ , xj’’ ≥0 第一章 線性規(guī)劃及單純形法 . 3 試將 LP 問題 min z = x1+2x23x3 . x1+x2+x3 ≤7 x1x2+x3 ≥2 3x1+x2+2x3 = 5 x1,x2 ≥0 化為標(biāo)準(zhǔn)形式。 記作 D={ x | Ax = b ,x≥0 }。 167。 可行域?yàn)闊o界區(qū)域一定無最優(yōu)解嗎？ 167。有助于了解解的結(jié)構(gòu)。 什么意思？ 為什么？ 第一章 線性規(guī)劃及單純形法 定義 3 在上述 LP 問題中，約束方程組 （ 2） 的系數(shù) 矩陣 A 的任意一個(gè) m m 階的非奇異的子方陣 B （ 即 |B|≠0）， 稱為 LP 問題的一個(gè)基陣或基 。 3 線性規(guī)劃問題解的基本性質(zhì) A = ( B, N ) xB= (x1,…,xm)T , xN =(xm+1,…,xn)T 則 BNxxx???????, 代入約束方程 （ 2），得 ? ? .BNxB N bx?? ?????? BnB x Nx b???? 自由變量 （獨(dú)立變量） 令 0Nx ? 1Bx B b?? 11BNx B b B Nx?????1( 4)0Bbx ????????稱（ 4）為相應(yīng)于基 B 的基本解 第一章 線性規(guī)劃及單純形法 1( 4)0Bbx ????????是可行解嗎？ max z’ = x12x2+3x4 3x5 . x1+x2+x4x5+x6=7 x1x2+x4x5x7=2 3x1x22x4+2x5=5 x1,x2,x4,x5,x6,x7≥0 ?1 1 1 1 1 01 1 1 1 0 13 1 2 2 0 0A?????? ? ? ?????令 x1=x2=x4=0 T5 19 9得 一 基 本 解 x=(0,0,0, , , ) 2 2 2 如果 B1b ≥ 0，則 稱（ 4）為相應(yīng)于基 B 的基可行 解，此時(shí)的基 B 稱為可行基。 定義 4 在 LP問題的一個(gè) 基可行解中 ， 如果它的所 有的基變量都取正值 ， 則 第一章 線性規(guī)劃及單純形法 LP 問題解的基本性質(zhì) 定理 1 設(shè) x 是 LP 問題的可行解 (1) 若 x = 0， 則它一定是基可行解； (2) 若 x≠0， 則 x 是基可行解的充要條件是它的非零分 量所對(duì)應(yīng)的列向量線性無關(guān) 。 3 線性規(guī)劃問題解的基本性質(zhì) 定理 2 證明 設(shè) x = (x1, x2,…, xn)T 是 LP 問題的一個(gè)可行解 ， 如果 x = 0， 則由定理 1知 ， 它是 LP 問題的一個(gè)基可行解 ， 定理成立 。 167。 證畢 。 如果 x(1)或 x(2) 是基可行解，則定理成立。 Note: 空集和單點(diǎn)集也是凸集。 ,nS R x S x S?? 如 果 不 能 用 中 不 同 的(1 ) ( 2 )xx， ( 1 ) ( 2 )( 1 ) ( 0 1 )x x x? ? ?? ? ? ? ?定理 4 LP 問題的可行解集 ? ?,0D x A x b x? ? ? 是 凸 集 。 定理 6 設(shè) LP 問題在多個(gè)極點(diǎn) x(1),x(2),…x (k) 處取到最優(yōu) 解，則它們的凸組合，即 * ( )110 , 1kkii i iiixx ? ? ???? ? ???也是 LP 問題的最優(yōu)解 . （此時(shí)，該 LP 問題有無窮多最優(yōu)解） 167。 ?180。 4 單純形法的基本原理 單純形法 （ Simplex Method） 是 1947年由 . Dantzig 提出，是解 LP 問題最有效的算法之一， 且已成為整數(shù)規(guī)劃和非線性規(guī)劃某些算法的基礎(chǔ) 。 x3 = 60 3x2 ≥ 0 x4 = 40 x2 ≥ 0 誰換出？ 如果 x4 換出，則 x2 = 40， x3 = 60， 不可行 。 120 20m in , 301233x????????????因所以 x4 換出。39。139。 39。 39。 39。 39。1m a x ( 1 ). . ( 1 , 2 , , ) ( 2 )0 ( 1 , 2 , , ) ( 3 )njjjmni ij j ijmjz z x bs t x a x b i m bx j n b???????? ? ?????定理 7 在 LP 問題 的典式 (1b) ～ (3b)中， 如果有 0 ( 1 , 2 , , )j j m m n? ? ? ? ?則對(duì)應(yīng)于基 B 的基可行解 ( 0 ) 39。 39。39。 (2)aik(i=1,2,…,m) 不全小于或等于零，即至少有一個(gè) aik0 (i=1,2,…,m) 。 這在應(yīng)用中很有價(jià)值 定理 10 在 LP 問題的典式 (1b) ～ (3b)中，如果有某