【正文】 30 30 260 3 0 15 5 20 60 180 4 20 20 0 40 20 230 5 8 5 15 17 55 190 1 2 3 4 51 2 4 51 3 4 51 3 51 2 3 4 51 2 3 4 512m in 340 260 180 230 190 Z x x x x xx x x xx x x xx x xx x x x xx x x x xxx? ? ? ? ?? ? ? ?? ? ? ?? ? ?? ? ? ? ?? ? ? ? ??3 4 5 10 , 1 , 2 , , 5jx x xxj????????? ? ? ??????2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 16 1 X1 0 2 X2 3 X3 0 4 X4 5 X5 最優(yōu)解： Z= 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 17 【 例 】 投資問題 。 某投資公司在第一年有 200萬(wàn)元資金 ， 每年都有如下的投資方案可供考慮采納： “ 假使第一年投入一筆資金 ， 第二年又繼續(xù)投入此資金的 50%， 那么到第三年就可回收第一年投入資金的一倍金額 ” 。 投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多 。 第五年： (x7/2+x9)=x8+2x5 第一年： x1+x2=200(萬(wàn)元 ) 第二年： (x1/2 +x3)+x4=x2 第三年 (x3/2+x5)+x6=x4+2x1 第四年： (x5/2+x7)+x8=x6+2x3 到第六年實(shí)有資金總額為 x9+2x7，整理后得到下列線性規(guī)劃模型 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 【 解 】 設(shè) x1：第一年的投資； x2：第一年的保留資金 x3：第二年新的投資； x4：第二年的保留資金 x5：第三年新的投資； x6：第三年的保留資金 x7：第四年新的投資 x8：第四年的保留資金 x9：第五年的保留資金 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 18 79121 2 3 41 3 4 5 63 5 6 7 85 7 8 9m a x 22002 2 2 04 2 2 2 04 2 2 2 04 2 2 00 , 1 , 2 , , 9jZ x xxxx x x xx x x x xx x x x xx x x xxj??????? ? ? ??? ? ? ? ? ???? ? ? ? ??? ? ? ? ?????? 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 1 X1 2 X2 3 X3 4 X4 0 5 X5 6 X6 0 7 X7 8 X8 0 9 X9 0 最優(yōu)解： Z＝ x1：第一年的投資； x2：第一年的保留資金 x3：第二年新的投資； x4：第二年的保留資金 x5：第三年新的投資； x6：第三年的保留資金 x7：第四年新的投資 x8：第四年的保留資金 x9：第五年的保留資金 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 19 【 例 】 均衡配套生產(chǎn)問題 。 某產(chǎn)品由 2件甲 、 3件乙零件組裝而成 。兩種零件必須經(jīng)過設(shè)備 A、 B上加工 ， 每件甲零件在 A、 B上的加工時(shí)間分別為 5分鐘和 9分鐘 ， 每件乙零件在 A、 B上的加工時(shí)間分別為 4分鐘和 10分鐘 。 現(xiàn)有 2臺(tái)設(shè)備 A和 3臺(tái)設(shè)備 B， 每天可供加工時(shí)間為 8小時(shí) 。為了保持兩種設(shè)備均衡負(fù)荷生產(chǎn) ， 要求一種設(shè)備每天的加工總時(shí)間不超過另一種設(shè)備總時(shí)間 1小時(shí) 。 怎樣安排設(shè)備的加工時(shí)間使每天產(chǎn)品的產(chǎn)量最大 。 【 解 】 設(shè) x x2為每天加工甲 、 乙兩種零件的件數(shù) ， 則產(chǎn)品的產(chǎn)量是 )31,21min( 21 xxy ?設(shè)備 A、 B每天加工工時(shí)的約束為 60831096082452121????????xxxx要求一種設(shè)備每臺(tái)每天的加工時(shí)間不超過另一種設(shè)備 1小時(shí)的約束為 60)109()45 2121 ???? xxxx（ 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 20 目標(biāo)函數(shù)線性化。產(chǎn)品的產(chǎn)量 y等價(jià)于 21 31,21 xyxy ??整理得到線性規(guī)劃模型 約束線性化。將絕對(duì)值約束寫成兩個(gè)不等式 60)109()45(60)109()45(21212121?????????xxxxxxxx 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 121212121212m a x12135 4 9609 10 14404 6 604 6 600Zyyxyxxxxxxxxxy x x???????????????????? ? ???????－ －、 、2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 21 線性規(guī)劃的一般模型 一般地 ， 假設(shè)線性規(guī)劃數(shù)學(xué)模型中 ， 有 m個(gè)約束 ， 有 n個(gè)決策變量xj, j=1,2… ,n， 目標(biāo)函數(shù)的變量系數(shù)用 cj表示 , cj稱為 價(jià)值系數(shù) 。 約束條件的變量系數(shù)用 aij表示 ， aij稱為 工藝系數(shù) 。 約束條件右端的常數(shù)用 bi表示 ， bi稱為 資源限量 。 則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 2m a x( m in)( , )( , )( , )0 , 1 , 2 , ,nnnnnnm m m n n mjZ c x c x c xa x a x a x ba x a x a x ba x a x a x bx j n? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ??????或或或?yàn)榱藭鴮懛奖?，上式也可寫成? 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 22 11m a x( m in)( , ) 1 , 2 , ,0 , 1 , 2 , ,njjjnij j ijjZ c xa x b i nx j n????? ? ? ???? ????? 或在實(shí)際中一般 xj≥0,但有時(shí) xj≤0或 xj無(wú)符號(hào)限制 。 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 23 ，掌握線性規(guī)劃在管理中的幾個(gè)應(yīng)用例子 。 作業(yè)：教材 P31 T 2， 3， 4， 5， 6 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 下一節(jié)：圖解法 2/29/2023 圖解法 Graphical Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 25 圖解法的步驟： 。 分別求出滿足每個(gè)約束包括變量非 負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為 可行域 ； 。 先過原點(diǎn)作一條矢量指向點(diǎn)（ c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形； 。 依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線，直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是 最優(yōu)解。 一般地，將目標(biāo)函數(shù)直線放在可行域中 求最大值時(shí)直線沿著矢量方向移動(dòng) 求最小值時(shí)沿著矢量的反方向移動(dòng) 圖解法 The Graphical Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 26 x1 x2 O 10 20 30 40 10 20 30 40 (3,4) (15,10) 最優(yōu)解 X=(15,10) 最優(yōu)值 Z=85 402 21 ?? xx 21 ?? xx 0,040222121??????xxxxxx例 2143max xxZ ?? 圖解法 The Graphical Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 27 2 4 6 x1 x2 2 4 6 最優(yōu)解 X=(3,1) 最優(yōu)值 Z=5 (3,1) ???????????????006346321212121xxxxxxxx、min Z=x1+2x2 例 (1,2) 圖解法 The Graphical Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 28 2 4 6 x1 x2 2 4 6 X（ 2） ＝（ 3,1） X（ 1） ＝（ 1,3） (5,5) ???????????????006346321212121xxxxxxxx、min Z=5x1+5x2 例 有無(wú)窮多個(gè)最優(yōu)解 即具有多重解 ,通解為 0≤α≤1 ,)1( )2()1( XXX ?? ??? 當(dāng) α= Ｘ =(x1,x2)=(1,3)+(3,1)=(2,2) 圖解法 The Graphical Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 29 2 4 6 x1 x2 2 4 6 (1,2) ???????????????006346321212121xxxxxxxx、無(wú)界解 (無(wú)最優(yōu)解 ) max Z=x1+2x2 例 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page