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