【正文】 容易觀察到 ,系數(shù)矩陣中有一個(gè) 3階單位矩陣 ,x x x5為基變量。 當(dāng)目標(biāo)函數(shù)中有基變量 xi時(shí)，利用約束條件將目標(biāo)函數(shù)中的 xi消去即可求出檢驗(yàn)數(shù)。 作業(yè)： P34 T 9 基本概念 Basic Concepts 下一節(jié)：單純形法 2/4/2023 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 60 單純形計(jì)算方法 (Simplex Method)是先求出一個(gè)初始基可行解并判斷它是否最優(yōu) ， 若不是最優(yōu) ， 再換一個(gè)基可行解并判斷 ， 直到得出最優(yōu)解或無最優(yōu)解 。 【 定理 】 線性規(guī)劃的可行解集合 K的點(diǎn) X是極點(diǎn)的充要條件為 X是基本可行解 。 基本概念 Basic Concepts 1Q2Q2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 53 基本最優(yōu)解 、 最優(yōu)解 、 基本可行解 、 基本解 、 可行解的關(guān)系如下所示： 基本最優(yōu)解 基本可行解 可行解 最 優(yōu) 解 基本解 例如 ,B點(diǎn)和 D點(diǎn)是可行解 ,不是基本解 。 TX )8,0,0,0,53(?非可行解 (Infeasible solution) 無界解 (unbound solution) 基本概念 Basic Concepts 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 50 顯然，只要基本解中的基變量的解滿足式（ ）的非負(fù)要求，那么這個(gè)基本解就是基本可行解。 【解】約束方程的系數(shù)矩陣為 2 5矩陣 ?????????10261001115A,610 151 ????????B ,010 152 ????????B ,110 053 ????????B ????? 2614B ???????1009B ,12017 ?????? ,0218 ???????B ,16016 ??????? ,015 ???容易看出 r(A)=2， 2階子矩陣有 C52=10個(gè)，其中第 1列與第 3列構(gòu)成的 2階矩陣不是一個(gè)基，基矩陣只有 9個(gè)，即 基本概念 Basic Concepts 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 48 由線性代數(shù)知，基矩陣 B必為非奇異矩陣并且 |B|≠0。 令 ???????????????????????????????0000000000002222222211111111xxxxxxxxxxxxxxxx，，，－，，222222111111,||,||xxxxxxxxxxx???????????????????? 則有 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 43 得到線性規(guī)劃的標(biāo)準(zhǔn)形式 1 1 2 21 1 2 2 31 1 41 1 2 2 3 4m a x ( ) ( )540Z x x x xx x x x xx x xx x x x x x? ?? ? ??? ? ? ? ?? ?? ? ??? ? ? ? ???? ??? ? ??? ? ?? ? ?? ?? 、 、 、 、 、 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 對于 a≤x≤b(a、 b均大于零 )的有界變量化為標(biāo)準(zhǔn)形式有兩種方法，一種方法是增加兩個(gè)約束 x≥a及 x≤b，另一種方法是令 =x－ a，則 a≤x≤b等價(jià)于 0≤≤b－ a，增加一個(gè)約束 ≤b－ a并且將原問題所有 x用 x=+a替換。 一般地，將目標(biāo)函數(shù)直線放在可行域中 求最大值時(shí)直線沿著矢量方向移動(dòng) 求最小值時(shí)沿著矢量的反方向移動(dòng) 圖解法 The Graphical Method 2/4/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/4/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/4/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 例 有無窮多個(gè)最優(yōu)解 即具有多重解 ,通解為 0≤α≤1 ,)1( )2()1( XXX ?? ??? 當(dāng) α= Ｘ =(x1,x2)=(1,3)+(3,1)=(2,2) 圖解法 The Graphical Method 2/4/2023 制作與教學(xué) 線性規(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 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 30 x1 x2 O 10 20 30 40 10 20 30 40 50 50 0,05040221212121????????xxxxxxxx無可行解 即無最優(yōu)解 max Z=10x1+4x2 例 圖解法 The Graphical Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 31 由以上例題可知，線性規(guī)劃的解有 4種形式 ： (例 ) (例 ) (例 ) (例 ) 2情形為有最優(yōu)解 4情形為無最優(yōu)解 圖解法 The Graphical Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 32 (1)可行解區(qū)域要畫正確 (2)目標(biāo)函數(shù)增加的方向不能畫錯(cuò) (3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng) 作業(yè)：教材 P34 T7 圖解法 The Graphical Method 下一節(jié)：線性規(guī)劃的標(biāo)準(zhǔn)型 2/4/2023 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 34 在用單純法求解線性規(guī)劃問題時(shí)，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。 約束條件的變量系數(shù)用 aij表示 ， aij稱為 工藝系數(shù) 。 某產(chǎn)品由 2件甲 、 3件乙零件組裝而成 。礦石雜質(zhì)在治煉過程中廢棄 ， 現(xiàn)要求每噸合金成本最低的礦物數(shù)量 。 設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為 y1， y2， y3,則切割方式可用不等式+y2+≤4表示，求這個(gè)不等式關(guān)于 y1， y2， y3的非負(fù)整數(shù)解。稱為三個(gè)要素 。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤最大）。 已知在計(jì)劃期內(nèi)設(shè)備的加工能力各為 200臺(tái)時(shí) ， 可供材料分別為 360、 300公斤；每生產(chǎn)一件甲 、乙 、 丙三種產(chǎn)品 ， 企業(yè)可獲得利潤分別為 50元 ， 假定市場需求無限制 。 星期 需要人數(shù) 星期 需要人數(shù) 一 300 五 480 二 300 六 600 三 350 日 550 四 400 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 9 【解】 設(shè) xj(j=1， 2， … ， 7)為休息 2天后星期一到星期日開始上班的營業(yè)員，則這個(gè)問題的線性規(guī)劃模型為 ?????????????????????????????????????????????????????????7,2,1,0550600480400350300300min765436543254321743217632176521765417654321?jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 星期 需要人數(shù) 星期 需要人數(shù) 一 300 五 480 二 300 六 600 三 350 日 550 四 400 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 10 1 X1 0 C1 404 = 300 104 2 X2 67 C2 301 = 300 1 3 X3 146 C3 350 = 350 0 4 X4 170 C4 400 = 400 0 5 X5 97 C5 480 = 480 0 6 X6 120 C6 600 = 600 0 7 X7 17 C7 550 = 550 0 最優(yōu)解： Z＝ 617（人） 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 11 【例 】合理用料問題。 ????????????????????????????? ??102,1,010005423210002342