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