【正文】 型 Standard form of LP 基本概念 Basic Concepts 單純形法 Simplex Method 2/4/2023 數(shù)學模型 Mathematical Model 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 3 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP 線性規(guī)劃通常研究資源的最優(yōu)利用、設備最佳運行等問題。 某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲 、乙 、 丙三種產(chǎn)品 。Z=3400 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 7 線性規(guī)劃的數(shù)學模型由 決策變量 Decision variables 目標函數(shù) Objective function 及約束條件 Constraints 構(gòu)成。 根據(jù)統(tǒng)計 ， 商場每天需要的營業(yè)員如表 ?，F(xiàn)在要制造 1000輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？ 【解】這是一個條材下料問題 ，設切口寬度為零。 則用料最少數(shù)學模型 為 : 求下料方案時應注意，余料不能超過最短毛坯的長度；最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案 。 鋼鐵公司擬從五種不同級別的礦石中進行冶煉 ， 每種礦物的成分含量和價格如表 。 配料問題也稱配方問題 、營養(yǎng)問題或混合問題 ， 在許多行業(yè)生產(chǎn)中都能遇到 。 第五年： (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) ， 要求一種設備每天的加工總時間不超過另一種設備總時間 1小時 。將絕對值約束寫成兩個不等式 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ù) 。 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 23 ，掌握線性規(guī)劃在管理中的幾個應用例子 。 依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線，直線與可行域相交的點對應的坐標就是 最優(yōu)解。也稱松馳變量 321 3min xxxZ ????????????????????????無符號要求、 32132132132100)3(523)2(3)1(82xxxxxxxxxxxx 線性規(guī)劃的標準型 Standard form of LP (2) 第一個約束條件是 ≤號，在 ≤左端加入松馳變量 (slack variable) x4，x4≥0,化為等式； (4)第三個約束條件是 ≤號且常數(shù)項為負數(shù)，因此在 ≤左邊加入松馳變量 x6， x6≥0，同時兩邊乘以－ 1。 線性規(guī)劃的標準型 Standard form of LP 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 42 【 例 】將下例線性規(guī)劃化為標準型 ???????????無約束、 211212145||||maxxxxxxxxZ【 解】 此題關(guān)鍵是將目標函數(shù)中的絕對值去掉。 圖解法時不必化為標準型。當 m=n時，基矩陣唯一，當 mn時，基矩陣就可能有多個，但數(shù)目不超過 mnC2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 47 【例 】線性規(guī)劃 321 24max xxxZ ???????????????????5,1,0226103553214321?jxxxxxxxxxj 求所有基矩陣。 ????????010152B ?????????10261001115A 基本概念 Basic Concepts 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 49 可行解 (feasible solution) 滿足式（ ）及（ ）的解 X=（ x1,x2… ， xn)T 稱為可行解 。 最優(yōu)解 (optimal solution) 滿足式 （ 1 .1） 的可行解稱為最優(yōu)解 ，即是使得目標函數(shù)達到最大值的可行解就是最優(yōu)解 ， 例如可行解 是例 2的最優(yōu)解 。 TX )1,27,21,0,0(? 321 24max xxxZ ???,010152 ????????B????????????????5,1,0226103553214321?jxxxxxxxxxjTX )0,4,0,0,51()2( ??基本解為 基本概念 Basic Concepts 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 52 可行基 基可行解對應的基稱為可行基； 最優(yōu)基 基本最優(yōu)解對應的基稱為最優(yōu)基； 如上述 B3就是最優(yōu)基 ， 最優(yōu)基也是可行基 。例如，滿足式（ ） ~()是最優(yōu)解 ,又是 B3的基本解 ,因此它是基本最優(yōu)解。 0,0402212121??????xxxxxxx1x2O10 20 30 4010203040( 3 , 4 )A(15 , 1 0 )最優(yōu)解 X = (1 5 , 1 0 )最優(yōu)值 Z = 8 5)20,0(C)35,5(DB(10 ,1 0)例 1 . 6 m ax Z= 3 x1+4 x2 基本概念 Basic Concepts 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 54 凸集 (Convex set)設 K是 n維空間的一個點集 ， 對任意兩點 時 ， 則稱 K為凸集 。 1Q2QO 3Q4Q 基本概念 Basic Concepts 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 56 【 定理 】 若線性規(guī)劃可行解 K非空 ,則 K是凸集。 線性規(guī)劃的基本定理 基本概念 Basic Concepts 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 57 定理 ， 若最優(yōu)解唯一 ， 則最優(yōu)解只能在某一極點上達到 ， 若具有多重最優(yōu)解 ， 則最優(yōu)解是某些極點的凸組合 ， 從而最優(yōu)解是可行解集的極點或界點 ， 不可能是可行解集的內(nèi)點 。 基本概念 Basic Concepts 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 58 1. 線性規(guī)劃常用的概念：可行解、基本解、基本 可行解、最優(yōu)解、基本最優(yōu)解、基、可行基、最優(yōu)基、凸集、極點（凸點）、凸組合 。 【例 】用單純形法求下列線性規(guī)劃的最優(yōu)解 ????????????0,30340243max21212121xxxxxxxxZ 單純形法 Simplex Method 普通單純形法 2/4/2023 制作與教學 線性規(guī)劃 Linear Programming Page 61 【 解 】 化為標準型 ， 加入松馳變量 x x4則標準型為