【正文】 個(gè) LP問(wèn)題 ， 如果它的 所有基可行解都是非退化的就稱該是非退化的 ， 否 則就稱它是退化的 。 3 線性規(guī)劃問(wèn)題解的基本性質(zhì) 討論如下 LP 問(wèn)題： ? ?m a x ( 1 ). . 20 ( 3 )z c xs t Ax bx???? ?12, , , nc c c c? ? ? 價(jià) 值 向 量? ?12, , , Tnx x x x? ? ?? ?12, , , , 0Tmib b b b b? ? ? ? 右 端 向 量11 12 121 22 2nnm m m na a aa a aAa a a????? ? ?????其中 系數(shù)矩陣 決策向量 假設(shè) A 的秩為 m , 且只討論 m n 的情 形。 稱為無(wú)最優(yōu)解 。 2 線性規(guī)劃問(wèn)題的圖解法 定義 1 在 LP 問(wèn)題中，凡滿足約束條件 (2)、 (3)的 解 x = (x1,x2,…, xn)T 稱為 LP 問(wèn)題的可行解， 所有可行解的集合稱為可行解集（或可行域）。 決策變量 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ī)劃問(wèn)題的一般形式： 167。 167。 1 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 . 1 資源的合理利用問(wèn)題 問(wèn)：如何安排生產(chǎn)計(jì)劃， 使得既能充分利用現(xiàn)有資 源又使總利潤(rùn)最大？ 表 1 產(chǎn)品 資源 甲 乙 庫(kù)存量 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。 1 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 線性規(guī)劃問(wèn)題的標(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ù) 。 記作 D={ x | Ax = b ,x≥0 }。 可行域?yàn)闊o(wú)界區(qū)域一定無(wú)最優(yōu)解嗎？ 167。 什么意思？ 為什么？ 第一章 線性規(guī)劃及單純形法 定義 3 在上述 LP 問(wèn)題中，約束方程組 （ 2） 的系數(shù) 矩陣 A 的任意一個(gè) m m 階的非奇異的子方陣 B （ 即 |B|≠0）， 稱為 LP 問(wèn)題的一個(gè)基陣或基 。 定義 4 在 LP問(wèn)題的一個(gè) 基可行解中 ， 如果它的所 有的基變量都取正值 ， 則 第一章 線性規(guī)劃及單純形法 LP 問(wèn)題解的基本性質(zhì) 定理 1 設(shè) x 是 LP 問(wèn)題的可行解 (1) 若 x = 0， 則它一定是基可行解； (2) 若 x≠0， 則 x 是基可行解的充要條件是它的非零分 量所對(duì)應(yīng)的列向量線性無(wú)關(guān) 。 167。 如果 x(1)或 x(2) 是基可行解，則定理成立。 ,nS R x S x S?? 如 果 不 能 用 中 不 同 的(1 ) ( 2 )xx， ( 1 ) ( 2 )( 1 ) ( 0 1 )x x x? ? ?? ? ? ? ?定理 4 LP 問(wèn)題的可行解集 ? ?,0D x A x b x? ? ? 是 凸 集 。 ?180。 x3 = 60 3x2 ≥ 0 x4 = 40 x2 ≥ 0 誰(shuí)換出？ 如果 x4 換出，則 x2 = 40， x3 = 60， 不可行 。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 問(wèn)題 的典式 (1b) ～ (3b)中， 如果有 0 ( 1 , 2 , , )j j m m n? ? ? ? ?則對(duì)應(yīng)于基 B 的基可行解 ( 0 ) 39。39。 這在應(yīng)用中很有價(jià)值 定理 10 在 LP 問(wèn)題的典式 (1b) ～ (3b)中，如果有某 個(gè)非基變量的檢驗(yàn)數(shù) σk 0 ( m+1 ≤ k ≤n )， 且有 39。1 1 1 1 1 2 2 1 139。1 1 2 2m a x..0 ( 1 , 2 , , )m m m m n nm m m m n nm m m m n nm m m m m m m m n n mjz z x x xs t x a x a x a x bx a x a x a x bx a x a x a x bx j n? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ??? c c1 c2 cm cm+1 cm+2 cB xB x1 x2 xm xm+1 xm+2 xn b c1 c2 cm x1 x2 xm 1 0 0 a’1m+1 a’1m+2 a’1n 0 1 0 a’2m+1 a’2m+2 a’2n 0 0 1 a’mm+1 a’mm+2 a’mn b’1 b’2 b’m 檢驗(yàn)數(shù) 0 0 0 z(0) n?2??1?? 第一章 線性規(guī)劃及單純形法 如何得到單純形表？ 1111m a x ( ) ( 1 ). . ( 2 )0 , 0 ( 3 )B N B NBNBNz c B b c c B N x as t x B N x B b ax x a????? ? ????? c A b 檢驗(yàn)數(shù) 0 B1b cB B1b z0 I B1N B1b 0 σN 檢驗(yàn)數(shù) B N cB cN I B1N 0 cNcB B1N 167。 轉(zhuǎn)入下一步 。239。 6 單純形法的進(jìn)一步討論 一、初始可行基的求法 max z = c1x1 + c2x2 +… + xn (1c) . a11x1 + a12x2 +… + a1nxn = b1 a21x1 + a22x2 +… + a2nxn = b2 …… …… . (2c) am1x1 + am2x2 +… + amnxn = bm xj≥0 （ j = 1,2,… , n） (3c) a11x1 + a12x2 +… + a1nxn + xn+1 = b1 a21x1 + a22x2 +… + a2nxn + xn+2 = b2 …… …… am1x1 + am2x2 +… + amnxn + xn+m = bm xj≥0 （ j = 1,2,… , n, n+1,… , n+m） 人工變量 試算法 人造基本解 ： x0 = (0,0,…,0,b 1,…,b m)T 人工變 量法 167。 39。 j=1,…,4, j ≥i 第一章 線性規(guī)劃及單純形法 合理下料問(wèn)題 某工廠要制作 100套專用鋼架，每套鋼架需要用長(zhǎng) 為 、 。 7 線性規(guī)劃應(yīng)用舉例 解： 設(shè) xj ( j=1,…,8 )分別按 8種方案下料的原材料根數(shù) 方案 毛坯 /m 方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8 2． 9 2 1 1 1 0 0 0 0 2． 1 0 2 1 0 3 2 1 0 1． 5 1 0 1 3 0 2 3 4 合 計(jì) 7． 3 7． 1 6． 5 7． 4 6． 3 7． 2 6． 6 6． 0 料 頭 0． 1 0． 3 0． 9 0． 0 1． 1 0． 2 0． 8 1． 4 約束條件： : 2x1+x2+x3 +x4 ≥100 : 2x2+x3 +3x5 + 2x6 +x7 ≥100 : x1 +x3+3x4 +2x6 +3x7+4x8 ≥100 xj ≥0 ( j=1,…,8 ) 第一章 線性規(guī)劃及單純形法 目標(biāo)函數(shù)分別為： 材料根數(shù)最少； min z= x1 +x2 +x3+x4 +x5 +x6 +x7+x8 . 2x1+x2+x3 +x4 ≥100 2x2+x3 +3x5 + 2x6 +x7 ≥100 x1 +x3+3x4 +2x6 +3x7+4x8 ≥100 xj ≥0 ( j=1,…,8 ) 用單純形法求解可得： x*=（ 10， 50， 0， 30， 0， 0， 0， 0） T， 最少使用的材料為 90根，各種圓鋼數(shù)均正好 100