【正文】 Rn 非可行解 基 可行解 可 基解 行 解 稱(chēng)它是非退化的解；反之 ， 如果有一個(gè)基變量也取 零值 ， 則稱(chēng)它是退化的解 。 3 線性規(guī)劃問(wèn)題解的基本性質(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 ????????稱(chēng)（ 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，則 稱(chēng)（ 4）為相應(yīng)于基 B 的基可行 解，此時(shí)的基 B 稱(chēng)為可行基。 xi (i=1,2,…,m) 為基 變量； xj (j= m+1,…,n) 為 非 基 變量 pj (j= m+1,…,n) 為 非 基向量 。 什么意思？ 為什么？ 第一章 線性規(guī)劃及單純形法 定義 3 在上述 LP 問(wèn)題中，約束方程組 （ 2） 的系數(shù) 矩陣 A 的任意一個(gè) m m 階的非奇異的子方陣 B （ 即 |B|≠0）， 稱(chēng)為 LP 問(wèn)題的一個(gè)基陣或基 。 167。有助于了解解的結(jié)構(gòu)。 167。 可行域?yàn)闊o(wú)界區(qū)域一定無(wú)最優(yōu)解嗎？ 167。 Zman= 第一章 線性規(guī)劃及單純形法 max z = 2x1 + 2x2 . 2x1 – x2 ≥ 2 x1 + 4x2≤ 4 x1， x2 ≥ 0 1222xx??44? ? ?O A (１ ,0) x1 x2 Note: 可行域?yàn)闊o(wú)界區(qū)域， 目標(biāo)函數(shù)值可無(wú)限 增大，即解無(wú)界。 167。 m a x ( 1 ). . ( 2)0 ( 3 )z c xs t Ax bx??? 167。 記作 D={ x | Ax = b ,x≥0 }。 1 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 LP的幾種表示形式： ),2,1(0),2,1(..max11njxmibxatsxczjinjjijnjjj???????????? ?12, , , nc c c c? ? ? 價(jià) 值 向 量m a x ( 1 ). . ( 2)0 ( 3 )z c xs t Ax bx???1m a x..0njjjz c xs t p x bx?????? ? 決策向量??? Tnxxxx , 21 ?? ? 右端向量???? 0, 21 iTm bbbbb ?? ? 列向量的第為 jAaaap Tmjjjj , 21 ??系數(shù)矩陣?????????????????mnmmnnaaaaaaaaaA???????212222111211 167。 1 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 ３、 右端項(xiàng) bi 0時(shí)，只需將等式兩端同乘（ 1） 則右端項(xiàng)必大于零 決策變量無(wú)非負(fù)約束 設(shè) xj 沒(méi)有非負(fù)約束，若 xj ≤0 ，可令 xj = xj’ ， 則 xj’ ≥0 ； 又若 xj 為自由變量，即 xj 可為任意實(shí)數(shù)， 可令 xj = xj’ xj’’ ，且 xj’ , xj’’ ≥0 第一章 線性規(guī)劃及單純形法 . 3 試將 LP 問(wèn)題 min z = x1+2x23x3 . x1+x2+x3 ≤7 x1x2+x3 ≥2 3x1+x2+2x3 = 5 x1,x2 ≥0 化為標(biāo)準(zhǔn)形式。 ???njjj xcz1min ????njjj xcz139。 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ù) 。 1 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 三個(gè)基本要素 ： Note： 善于抓住關(guān)鍵因素，忽略對(duì)系統(tǒng)影響不大的因素； 可以把一個(gè)大系統(tǒng)合理地分解成 n 個(gè)子系統(tǒng)處理。見(jiàn)表 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 … 試在滿(mǎn)足營(yíng)養(yǎng)要 求的前提下，確定食 品的購(gòu)買(mǎi)量，使食品 的總價(jià)格最低。 1 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 . 2 營(yíng)養(yǎng)問(wèn)題 假定在市場(chǎng)上可買(mǎi)到 B1,B2,…Bn n 種食品，第 i 種 食品的單價(jià)是 ci , 另外有 m 種營(yíng)養(yǎng) A1,A2,…Am。 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。 60年來(lái)，隨著計(jì)算機(jī)的發(fā)展，線性規(guī)劃已廣泛應(yīng)用 于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸、經(jīng)濟(jì)管理和國(guó)防等各 個(gè)領(lǐng)域，成為現(xiàn)代化管理的有力工具之一。來(lái)自 中國(guó)最大的資料庫(kù)下載 運(yùn) 籌 學(xué) Operations Research 第一章 線性規(guī)劃及單純形法 第一章 線性規(guī)劃及單純形法 線性規(guī)劃 （ Linear Programming，簡(jiǎn)稱(chēng) LP） 運(yùn)籌學(xué)的一個(gè)重要分支，是運(yùn)籌學(xué)中研究較早、發(fā)展較 快、理論上較成熟和應(yīng)用上極為廣泛的一個(gè)分支。 1947年 . Dantying提出了一般線性規(guī)劃問(wèn)題求解 的方法 —— 單純形法之后，線性規(guī)劃的理論與應(yīng)用都得 到了極大的發(fā)展。 167。 第一章 線性規(guī)劃及單純形法 max z = 15x1 +25x2 . x1 + 3x2 ≤ 60 x1 + x2 ≤ 40 x1， x2 ≥ 0 解 ： 設(shè) x1， x2 為下一個(gè)生 產(chǎn)周期產(chǎn)品甲和乙的產(chǎn)量； 約束條件 ： Subject to x1 + 3x2 ≤ 60 x1 + x2 ≤ 40 x1， x2 ≥ 0 目標(biāo)函數(shù) ： z = 15 x1 +25 x2 表 1 產(chǎn)品 資源 甲 乙 庫(kù)存量 A 1 3 60 B 1 1 40 單件利潤(rùn) 15 25 決策變量 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。 第一章 線性規(guī)劃及單純形法 表 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 … 解 ： 設(shè) xj 為購(gòu)買(mǎi)食 品 Bj 的數(shù)量 ( j=1,2, …,n ) （ i = 1,2,… ,m） xj≥0 （ j = 1,2,… ,n） 0≤ xj ≤lj 1m innjjjz c x?? ? 167。 決策變量 xj≥0 約束條件 —— 一組決策變量的線性等式或不等式 目標(biāo)函數(shù) —— 決策變量的線性函數(shù) 第一章 線性規(guī)劃及單純形法 max（ min） z = c1x1 + c2x2 + … + xn . a11x1 + a12x2 + … + a1nxn ≤（ 或 =， ≥） b1 a21x1