【正文】 （ c） 若存在 λk0且 aik (i=1,… ,m)不全非正 ， 則進(jìn)行換基； 單純形法 Simplex Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 66 m in 0 , 0 ,iiL ik ikik ikbba a M Maa?????????當(dāng) ≤ 時(shí) ＝ 為 任 意 大 的 正 數(shù)第 Ｌ 個(gè)比值最小 ， 選最小比值對(duì)應(yīng)行的基變量為出基變量 ，若有相同最小比值 ， 則任選一個(gè) 。 若線性規(guī)劃的可行解集非空且有界 ， 則一定有最優(yōu)解；若可行解集無(wú)界 ， 則線性規(guī)劃可能有最優(yōu)解 ，也可能沒有最優(yōu)解 。 當(dāng)最優(yōu)解唯一時(shí)，最優(yōu)解亦是基本最優(yōu)解，當(dāng)最優(yōu)解不唯一時(shí)，則最優(yōu)解不一定是基本最優(yōu)解。 。 作業(yè)：教材 P31 T 2， 3， 4， 5， 6 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 下一節(jié)：圖解法 2/29/2023 圖解法 Graphical Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 25 圖解法的步驟： 。 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 礦石 錫 % 鋅 % 鉛 % 鎳 % 雜質(zhì) 費(fèi)用（元 /t ） 1 25 10 10 25 30 340 2 40 0 0 30 30 260 3 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/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 16 1 X1 0 2 X2 3 X3 0 4 X4 5 X5 最優(yōu)解： Z= 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 17 【 例 】 投資問(wèn)題 。 表 營(yíng)業(yè)員需要量統(tǒng)計(jì)表 商場(chǎng)人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場(chǎng)總的營(yíng)業(yè)員最少。 線性規(guī)劃 （ Linear Programming,縮寫為 LP） 是運(yùn)籌學(xué)的重要分支之一，在實(shí)際中應(yīng)用得較廣泛，其方法也較成熟，借助計(jì)算機(jī)，使得計(jì)算更方便，應(yīng)用領(lǐng)域更廣泛和深入。象這樣的非負(fù)整數(shù)解共有 10組，也就是有 10種下料方式，如表 。兩種零件必須經(jīng)過(guò)設(shè)備 A、 B上加工 ， 每件甲零件在 A、 B上的加工時(shí)間分別為 5分鐘和 9分鐘 ， 每件乙零件在 A、 B上的加工時(shí)間分別為 4分鐘和 10分鐘 。 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為 : 1．目標(biāo)函數(shù)求最大值（或求最小值） 2．約束條件都為等式方程 3．變量 xj非負(fù) 4．常數(shù) bi非負(fù) 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 35 ?????????????????????????mibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2,1,0,2,1,02211222222111212111????????????????max(或 min)Z=c1x1+c2x2+…+xn 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 注：本教材默認(rèn)目標(biāo)函數(shù)是 max 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 36 ???njjj xcZ1m axminjxbxajnjijij,2,1,2,1,01 ???????????????????0maxXbAXCXZ或?qū)懗上铝行问?： 或用矩陣形式 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 37 11 12 1 1 121 22 2 2 21212, , , )nnnm m m n n ma a a x ba a a x bA X b C c c ca a a x b? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?； ； ； ＝ (通常 X記為： 稱Ａ為約束方程的系數(shù)矩陣， m是約束方程的個(gè)數(shù)， n是決策變量的個(gè)數(shù)，一般情況 m≤n，且 r(Ａ )＝ m。當(dāng)矩陣 B的行列式等式零即 |B|=0時(shí)就不是基 當(dāng)確定某一矩陣為基矩陣時(shí)，則基矩陣對(duì)應(yīng)的列向量稱為 基向量 (basis vector)，其余列向量稱為 非基向量 基向量對(duì)應(yīng)的變量稱為 基變量 (basis variable)，非基向量對(duì)應(yīng)的變量稱為 非基變量 在上例中 B2的基向量是 A中的第一列和第四列 ， 其余列向量是非基向量 ， x x4是基變量 ， x x x5是非基變量 。C點(diǎn)是基本可行解 。 它是一種逐步逼近最優(yōu)解的迭代方法 。目標(biāo)函數(shù)中含有基變量 x4,由第二個(gè)約束得到 x4=6+x1－ x2，并代入目標(biāo)函數(shù)消去 x4得 1 2 1 2 1 22 2 ( 6 ) 6Z x x x x x x? ? ? ? ? ? ? ?＝ 單純形法 Simplex Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 70 XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λj 1 1↑ 0 0 0 x2 x4 x5 1 2 4 1 0 0 1 1 2 0 1 0 0 0 1 5 1 11 λj 2 0 1 0 0 表中 λj≥0,j=1,2,? ,5所以最優(yōu)解為 X=(0,5,0,1,11,)最優(yōu)值 Z=2x1－ 2x2－ x4=－ 2 5－ 1=－ 11 極小值問(wèn)題 ,注意判斷標(biāo)準(zhǔn) ,選進(jìn)基變量時(shí) ,應(yīng)選 λj0的變量 xj進(jìn)基。 最優(yōu)解判斷標(biāo)準(zhǔn) 當(dāng)所有檢驗(yàn)數(shù) λj≤0（ j=1， … ， n）時(shí)，基本可行解為最優(yōu)解。 1Q2QO 3Q4Q 基本概念 Basic Concepts 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 56 【 定理 】 若線性規(guī)劃可行解 K非空 ,則 K是凸集。 最優(yōu)解 (optimal solution) 滿足式 （ 1 .1） 的可行解稱為最優(yōu)解 ，即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解 ， 例如可行解 是例 2的最優(yōu)解 。 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 42 【 例 】將下例線性規(guī)劃化為標(biāo)準(zhǔn)型 ???????????無(wú)約束、 211212145||||maxxxxxxxxZ【 解】 此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對(duì)值去掉。將絕對(duì)值約束寫成兩個(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/29/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ù) 。 鋼鐵公司擬從五種不同級(jí)別的礦石中進(jìn)行冶煉 ， 每種礦物的成分含量和價(jià)格如表 。Z=3400 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 7 線性規(guī)劃的數(shù)學(xué)模型由 決策變量 Decision variables 目標(biāo)函數(shù) Objective function 及約束條件 Constraints 構(gòu)成。 企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃 ， 使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大 ？ 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 應(yīng)用模型舉例 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 5 產(chǎn)品 資源 甲 乙 丙 現(xiàn)有資源 設(shè)備 A 3 1 2 200 設(shè)備 B 2 2 4 200 材料 C 4 5 1 360 材料 D 2 3 5 300 利潤(rùn)（元 /件） 40 30 50 表 產(chǎn)品資源消耗 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 6 321 503040max xxxZ ???????????????????????????0003005