【正文】 100022min10987542987643154321101，jxxxxxxxxxxxxxxxxxxxxxZjjj 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 方案 規(guī)格 1 2 3 4 5 6 7 8 9 10 需求量 y1(根 ) 2 2 1 1 1 0 0 0 0 0 1000 y2 1 0 2 1 0 4 3 2 1 0 1000 y3 0 1 0 2 3 0 1 2 4 5 1000 余料（ m） 0 0 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 13 1 X1 500 2 X2 0 3 X3 0 4 X4 0 5 X5 0 6 X6 7 X7 0 8 X8 0 9 X9 250 10 X10 0 Z＝ 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 14 【 例 】 配料問題 。 某投資公司在第一年有 200萬元資金 ， 每年都有如下的投資方案可供考慮采納： “ 假使第一年投入一筆資金 ， 第二年又繼續(xù)投入此資金的 50%， 那么到第三年就可回收第一年投入資金的一倍金額 ” 。 【 解 】 設(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/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 20 目標(biāo)函數(shù)線性化。 分別求出滿足每個(gè)約束包括變量非 負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為 可行域 ； 。 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 40 綜合起來得到下列標(biāo)準(zhǔn)型 332133max xxxxZ ???????????????????????????????????????????05)(23382654321633215332143321xxxxxxxxxxxxxxxxxxxxxx、 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 41 當(dāng)某個(gè)變量 xj≤0時(shí) ,令 x/j=－ xj 。 作業(yè)：教材 P34 T 8 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 下一節(jié)：基本概念 2/4/2023 線性規(guī)劃的有關(guān)概念 Basic Concepts of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 46 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型 max Z=CX （ ） AX=b （ ） X ≥0 （ ） 式中 A 是 m n矩陣 ， m≤n并且 r（ A） =m， 顯然 A中至少有一個(gè) m m子矩陣 B， 使得 r（ B） =m。 例如， 與 X=（ 0， 0， 0， 3， 2，）都是例 1 的可行解。例如右圖中線段 的點(diǎn)為最優(yōu) 解時(shí)， Q1點(diǎn)及 Q2點(diǎn)是基本最優(yōu)解 ,線段 的內(nèi)點(diǎn)是最優(yōu)解而不是基本最優(yōu)解。 )()2()1( , KXXXX ? 及，且， 021 ?iK ???? ?11 ???Kii? iKii XX ??1?＝)()2()1( , KXXX ? 基本概念 Basic Concepts 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 55 極點(diǎn) (Extreme point) 設(shè) K是凸集 ， ， 若 X不能用K中兩個(gè)不同的 點(diǎn) 的凸組合表示為 KX ? )2()1( , XX? ) 1 0 ( ) 1 ( ) 2 ( ) 1 ( ? ? ? ? ? ? ? X X X 則稱 X是 K的一個(gè)極點(diǎn)或頂點(diǎn)。 定理 ， 尋求最優(yōu)解不是在無限個(gè)可行解中去找 ， 而是在有限個(gè)基本可行解中去尋求 。 本例中 λ1=3,λ2=4,λ3=0,λ4=0。 aLk為主元素； (c） 求新的基可行解：用初等行變換方法將 aLk 化為１ ,k列其它元素化為零 （ 包括檢驗(yàn)數(shù)行 ） 得到新的可行基及基本可行解 ， 再判斷是否得到最優(yōu)解 。 由模型可以看出 ， 當(dāng)固定 x1使 x2→+∞且滿足約束條件 ， 還可以用圖解法看出具有無界解 。其中基變量的檢驗(yàn)數(shù)必為零； ： （ a） 若 λj≤０ （ j＝１ ， ２ ， … ， n） 得到最解； （ b） 某個(gè) λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無界解 (見例 )。 【例 】用單純形法求下列線性規(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)型為 ??????????????0,30340243max432142132121xxxxxxxxxxxxZ系數(shù)矩陣 A及可行基 B1 ???????10310112A??????10011Br(B1)=2， B1是一個(gè)初始基 ,x x4為基變量 ， x x2為非基變量 ， 令 x1=0、 x2=0由約束方程知 x3=x4=30得到初始基本可行解 X(1)=(0,0,40,30)T 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 62 以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。 線性規(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) 。 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為凸集 。 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)基也是可行基 。 ????????010152B ?????????10261001115A 基本概念 Basic Concepts 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 49 可行解 (feasible solution) 滿足式（ ）及（ ）的解 X=（ x1,x2… ， xn)T 稱為可行解 。 圖解法時(shí)不必化為標(biāo)準(zhǔn)型。也稱松馳變量 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ī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 23 ，掌握線性規(guī)劃在管理中的幾個(gè)應(yīng)用例子 。為了保持兩種設(shè)備均衡負(fù)荷生產(chǎn) ， 要求一種設(shè)備每天的加工總時(shí)間不超過另一種設(shè)備總時(shí)間 1小時(shí) 。 配料問題也稱配方問題 、營養(yǎng)問題或混合問題 ， 在許多行業(yè)生產(chǎn)中都能遇到 。 則用料最少數(shù)學(xué)模型 為 : 求下料方案時(shí)應(yīng)注意，余料不能超過最短毛坯的長度；最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案 。 根據(jù)統(tǒng)計(jì) ， 商場每天需要的營業(yè)員如表 。 某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲 、乙 、 丙三種產(chǎn)品 。 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 4 【 例 】 最優(yōu)生產(chǎn)計(jì)劃問題 。 怎樣辨別一個(gè)模型是線性規(guī)劃模型？ 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023