運籌學(xué)ppt課件Ch1線性規(guī)劃

運籌學(xué)OperationsResearch Chapter1線性規(guī)劃LinearProgramming 1 1LP的數(shù)學(xué)模型MathematicalModelofLP1 2圖解法GraphicalMethod1 3標準型StandardformofLP1 4基本概念BasicConcepts1 5單純形法SimplexMethod 1 1數(shù)學(xué)模型MathematicalModel 2020 2 24 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 線性規(guī)劃 LinearProgramming 縮寫為LP 通常研究資源的最優(yōu)利用 設(shè)備最佳運行等問題 例如 當(dāng)任務(wù)或目標確定后 如何統(tǒng)籌兼顧 合理安排 用最少的資源 如資金 設(shè)備 原標材料 人工 時間等 去完成確定的任務(wù)或目標 企業(yè)在一定的資源條件限制下 如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益 如產(chǎn)品量最多 利潤最大 2020 2 24 例1 1 生產(chǎn)計劃問題 某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲 乙兩種產(chǎn)品 按工藝資料規(guī)定 每件產(chǎn)品甲需要消耗材料A2公斤 消耗材料B1公斤 每件產(chǎn)品乙需要消耗材料A1公斤 消耗材料B1 5公斤 已知在計劃期內(nèi)可供材料分別為40 30公斤 每生產(chǎn)一件甲 乙兩產(chǎn)品 企業(yè)可獲得利潤分別為300 400元 如表1 1所示 假定市場需求無限制 企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃 使企業(yè)在計劃期內(nèi)總的利潤收入最大 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 1 1 1應(yīng)用模型舉例 2020 2 24 解 設(shè)x1 x2分別為甲 乙產(chǎn)品的產(chǎn)量 數(shù)學(xué)模型為 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 表1 1 2020 2 24 線性規(guī)劃的數(shù)學(xué)模型由 決策變量Decisionvariables目標函數(shù)Objectivefunction及約束條件Constraints構(gòu)成 稱為三個要素 其特征是 1 解決問題的目標函數(shù)是多個決策變量的線性函數(shù) 通常是求最大值或最小值 2 解決問題的約束條件是一組多個決策變量的線性不等式或等式 怎樣辨別一個模型是線性規(guī)劃模型 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 2020 2 24 例1 2 某商場決定 營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天 輪流休息 根據(jù)統(tǒng)計 商場每天需要的營業(yè)員如表1 2所示 表1 2營業(yè)員需要量統(tǒng)計表 商場人力資源部應(yīng)如何安排每天的上班人數(shù) 使商場總的營業(yè)員最少 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 2020 2 24 解 設(shè)xj j 1 2 7 為休息2天后星期一到星期日開始上班的營業(yè)員 則這個問題的線性規(guī)劃模型為 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 2020 2 24 例1 3 合理用料問題 某汽車需要用甲 乙 丙三種規(guī)格的軸各一根 這些軸的規(guī)格分別是1 5 1 0 7 m 這些軸需要用同一種圓鋼來做 圓鋼長度為4m 現(xiàn)在要制造1000輛汽車 最少要用多少圓鋼來生產(chǎn)這些軸 解 這是一個條材下料問題 設(shè)切口寬度為零 設(shè)一根圓鋼切割成甲 乙 丙三種軸的根數(shù)分別為y1 y2 y3 則切割方式可用不等式1 5y1 y2 0 7y3 4表示 求這個不等式關(guān)于y1 y2 y3的非負整數(shù)解 象這樣的非負整數(shù)解共有10組 也就是有10種下料方式 如表1 3所示 表1 3下料方案 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 2020 2 24 設(shè)xj j 1 2 10 為第j種下料方案所用圓鋼的根數(shù) 則用料最少數(shù)學(xué)模型為 求下料方案時應(yīng)注意 余料不能超過最短毛坯的長度 最好將毛坯長度按降的次序排列 即先切割長度最長的毛坯 再切割次長的 最后切割最短的 不能遺漏了方案 如果方案較多 用計算機編程排方案 去掉余料較長的方案 進行初選 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 2020 2 24 1 1 2線性規(guī)劃的一般模型一般地 假設(shè)線性規(guī)劃數(shù)學(xué)模型中 有m個約束 有n個決策變量xj j 1 2 n 目標函數(shù)的變量系數(shù)用cj表示 cj稱為價值系數(shù) 約束條件的變量系數(shù)用aij表示 aij稱為工藝系數(shù) 約束條件右端的常數(shù)用bi表示 bi稱為資源限量 則線性規(guī)劃數(shù)學(xué)模型的一般表達式可寫成 為了書寫方便 上式也可寫成 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 2020 2 24 在實際中一般xj 0 但有時xj 0或xj無符號限制 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 2020 2 24 1 什么是線性規(guī)劃 掌握線性規(guī)劃在管理中的幾個應(yīng)用例子2 線性規(guī)劃數(shù)學(xué)模型的組成及其特征3 線性規(guī)劃數(shù)學(xué)模型的一般表達式 作業(yè) 教材習(xí)題1 1 1 6 1 1線性規(guī)劃的數(shù)學(xué)模型MathematicalModelofLP 下一節(jié) 圖解法 1 2圖解法GraphicalMethod 2020 2 24 x1 x2 O 10 20 30 40 10 20 30 40 300 400 15 10 最優(yōu)解X 15 10 最優(yōu)值Z 8500 例1 7 1 2圖解法TheGraphicalMethod 2020 2 24 2 4 6 x1 x2 2 4 6 最優(yōu)解X 3 1 最優(yōu)值Z 5 3 1 minZ x1 2x2 例1 8 1 2 1 2圖解法TheGraphicalMethod 2020 2 24 2 4 6 x1 x2 2 4 6 X 2 3 1 X 1 1 3 5 5 minZ 5x1 5x2 例1 9 有無窮多個最優(yōu)解即具有多重解 通解為 0 1 當(dāng) 0 5時 x1 x2 0 5 1 3 0 5 3 1 2 2 1 2圖解法TheGraphicalMethod 2020 2 24 2 4 6 x1 x2 2 4 6 1 2 無界解 無最優(yōu)解 maxZ x1 2x2 例1 10 1 2圖解法TheGraphicalMethod 2020 2 24 x1 x2 O 10 20 30 40 10 20 30 40 50 50 無可行解即無最優(yōu)解 maxZ 10 x1 4x2 例1 11 1 2圖解法TheGraphicalMethod 2020 2 24 由以上例題可知 線性規(guī)劃的解有4種形式 1 有唯一最優(yōu)解 例1 7例1 8 2 有多重解 例1 9 3 有無界解 例1 10 4 無可行解 例1 11 1 2情形為有最優(yōu)解3 4情形為無最優(yōu)解 1 2圖解法TheGraphicalMethod 2020 2 24 圖解法的步驟 1 求可行解集合 分別求出滿足每個約束包括變量非負要求的區(qū)域 其交集就是可行解集合 或稱為可行域 2 繪制目標函數(shù)圖形 先過原點作一條矢量指向點 c1 c2 矢量的方向就是目標函數(shù)增加的方向 稱為梯度方向 再作一條與矢量垂直的直線 這條直線就是目標函數(shù)圖形 3 求最優(yōu)解 依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線 直線與可行域相交的點對應(yīng)的坐標就是最優(yōu)解 一般地 將目標函數(shù)直線放在可行域中求最大值時直線沿著矢量方向移動求最小值時沿著矢量的反方向移動 1 2圖解法TheGraphicalMethod 2020 2 24 1 通過圖解法了解線性規(guī)劃有幾種解的形式2 作圖的關(guān)鍵有三點 1 可行解區(qū)域要畫正確 2 目標函數(shù)增加的方向不能畫錯 3 目標函數(shù)的直線怎樣平行移動 作業(yè) 教材習(xí)題1 7 1 2圖解法TheGraphicalMethod 下一節(jié) 線性規(guī)劃的標準型 1 3線性規(guī)劃的標準型StandardformofLP 2020 2 24 在用單純法求解線性規(guī)劃問題時 為了討論問題方便 需將線性規(guī)劃模型化為統(tǒng)一的標準形式 1 3線性規(guī)劃的標準型StandardformofLP 線性規(guī)劃問題的標準型為 1 目標函數(shù)求最大值 或求最小值 2 約束條件都為等式方程3 變量xj非負4 常數(shù)bi非負 2020 2 24 max 或min Z c1x1 c2x2 cnxn 1 3線性規(guī)劃的標準型StandardformofLP 注 本教材默認目標函數(shù)是max 2020 2 24 或?qū)懗上铝行问?或用矩陣形式 1 3線性規(guī)劃的標準型StandardformofLP 2020 2 24 通常X記為 稱 為約束方程的系數(shù)矩陣 m是約束方程的個數(shù) n是決策變量的個數(shù) 一般情況m n 且r m 其中 1 3線性規(guī)劃的標準型StandardformofLP 2020 2 24 例1 12 將下列線性規(guī)劃化為標準型 解 因為x3無符號要求 即x3取正值也可取負值 標準型中要求變量非負 所以令 1 3線性規(guī)劃的標準型StandardformofLP 2020 2 24 3 第二個約束條件是 號 在 號左端減去剩余變量 Surplusvariable x5 x5 0 也稱松馳變量 1 3線性規(guī)劃的標準型StandardformofLP 2 第一個約束條件是 號 在 左端加入松馳變量 slackvariable x4 x4 0 化為等式 4 第三個約束條件是 號且常數(shù)項為負數(shù) 因此在 左邊加入松馳變量x6 x6 0 同時兩邊乘以 1 5 目標函數(shù)是最小值 為了化為求最大值 令Z Z 得到maxZ Z 即當(dāng)Z達到最小值時Z 達到最大值 反之亦然 2020 2 24 綜合起來得到下列標準型 1 3線性規(guī)劃的標準型StandardformofLP 2020 2 24 當(dāng)某個變量xj 0時 令x j xj 當(dāng)某個約束是絕對值不等式時 將絕對值不等式化為兩個不等式 再化為等式 例如約束 將其化為兩個不等式 再加入松馳變量化為等式 1 3線性規(guī)劃的標準型StandardformofLP 2020 2 24 例1 13 將下例線性規(guī)劃化為標準型 解 此題關(guān)鍵是將目標函數(shù)中的絕對值去掉 令 則有 1 3線性規(guī)劃的標準型StandardformofLP 2020 2 24 得到線性規(guī)劃的標準形式 1 3線性規(guī)劃的標準型StandardformofLP 對于a x b a b均大于零 的有界變量化為標準形式有兩種方法 一種方法是增加兩個約束x a及x b另一種方法是令x x a 則a x b等價于0 x b a 增加一個約束x b a并且將原問題所有x用x x a替換 2020 2 24 1 如何化標準形式 可以對照四條標準逐一判斷 標準形式是人為定義的 目標函數(shù)可以是求最小值 2 用WinQSB軟件求解時 不必化成標準型 圖解法時不必化為標準型 3 單純形法求解時一定要化為標準型 作業(yè) 教材習(xí)題1 8 1 3線性規(guī)劃的標準型StandardformofLP 下一節(jié) 基本概念 1 4線性規(guī)劃的有關(guān)概念BasicConceptsofLP 2020 2 24 設(shè)線性規(guī)劃的標準型maxZ CX 1 1 AX b 1 2 X 0 1 3 式中A是m n矩陣 m n并且r A m 顯然A中至少有一個m m子矩陣B 使得r B m 1 4基本概念BasicConcepts 基 basis A中m m子矩陣B并且有r B m 則稱B是線性規(guī)劃的一個基 或基矩陣basismatrix 當(dāng)m n時 基矩陣唯一 當(dāng)m n時 基矩陣就可能有多個 但數(shù)目不超過 2020 2 24 例1 14 線性規(guī)劃 求所有基矩陣 解 約束方程的系數(shù)矩陣為2 5矩陣 容易看出r A 2 2階子矩陣有C52 10個 其中第1列與第3列構(gòu)成的2階矩陣不是一個基 基矩陣只有9個 即 1 4基本概念BasicConcepts 2020 2 24 由線性代數(shù)知 基矩陣B必為非奇異矩陣并且 B 0 當(dāng)矩陣B的行列式等式零即 B 0時就不是基 當(dāng)確定某一矩陣為基矩陣時 則基矩陣對應(yīng)的列向量稱為基向量 basisvector 其余列向量稱為非基向量 基向量對應(yīng)的變量稱為基變量 basisvariable 非基向量對應(yīng)的變量稱為非基變量 在上例中B2的基向量是A中的第一列和第四列 其余列向量是非基向量 x1 x4是基變量 x2 x3 x5是非基變量 基變量 非基變量是針對某一確定基而言的 不同的基對應(yīng)的基變量和非基變量也不同 1 4基本概念BasicConcepts 2020 2 24 可行解 feasiblesolution 滿足式 1 2 及 1 3 的解X x1 x2 xn T稱為可行解 基本可行解 basisfeasiblesolution 若基本解是可行解則稱為是基本可行解 也稱基可行解 例如 與X 0 0 0 3 2 都是例1的可行解 基本解 basissolution 對某一確定的基B 令非基變量等于零 利用式 1 解出基變量 則這組解稱為基 的基本解 最優(yōu)解 optimalsolution 滿足式 1 1 的可行解稱為最優(yōu)解 即是使得目標函數(shù)達到最大值的可行解就是最優(yōu)解 例如可行解是例2的最優(yōu)解 非可行解 Infeasiblesolution 無界解 unboundsolution 1 4基本概念BasicConcepts 2020 2 24 顯然 只要基本解中的基變量的解滿足式 1 的非負要求 那么這個基本解就是基本可行解 在例1 13中 對 來說 x1 x2是基變量 x3 x4 x5是非基變量 令x3 x4 x5 0 則式 1 為 對B2來說 x1 x4 為基變量 令非基變量x2 x3 x5為零 由式 1 2 得到 x4 4 因 B1 由克萊姆法則知 x1 x2有唯一解x1 2 5 x2 1則基本解為 1 4基本概念BasicConcepts 2020 2 24 由于是基本解 從而它是基本可行解 在中x1 0 因此不是可行解 也就不是基本可行解 反之 可行解不一定是基本可行解例如滿足式 1 2 1 3 但不是任何基矩陣的基本解 基本解為 1 4基本概念BasicConcepts 2020 2 24 可行基基可行解對應(yīng)的基稱為可行基 最優(yōu)基基本最優(yōu)解對應(yīng)的基稱為最優(yōu)基 如上述B3就是最優(yōu)基 最優(yōu)基也是可行基 當(dāng)最優(yōu)解唯一時 最優(yōu)解亦是基本最優(yōu)解 當(dāng)最優(yōu)解不唯一時 則最優(yōu)解不一定是基本最優(yōu)解 例如右圖中線段的點為最優(yōu)解時 Q1點及Q2點是基本最優(yōu)解 線段的內(nèi)點是最優(yōu)解而不是基本最優(yōu)解 基本最優(yōu)解最優(yōu)解是基本解稱為基本最優(yōu)解 例如 滿足式 1 1 1 3 是最優(yōu)解 又是B3的基本解 因此它是基本最優(yōu)解 1 4基本概念BasicConcepts 2020 2 24 基本最優(yōu)解 最優(yōu)解 基本可行解 基本解 可行解的關(guān)系如下所示 基本最優(yōu)解 基本可行解 可行解 最優(yōu)解 基本解 例如 B點和D點是可行解 不是基本解 C點是基本可行解 A點是基本最優(yōu)解 同時也是最優(yōu)解 基本可行解 基本解和可行解 1 4基本概念BasicConcepts 2020 2 24 凸集 Convexset 設(shè)K是n維空間的一個點集 對任意兩點時 則稱K為凸集 就是以X 1 X 2 為端點的線段方程 點X的位置由 的值確定 當(dāng) 0時 X X 2 當(dāng) 1時X X 1 凸組合 Convexcombination 設(shè)是Rn中的點若存在使得成立 則稱X為的凸組合 1 4基本概念BasicConcepts 2020 2 24 極點 Extremepoint 設(shè)K是凸集 若X不能用K中兩個不同的點的凸組合表示為 則稱X是K的一個極點或頂點 X是凸集K的極點即X不可能是K中某一線段的內(nèi)點 只能是K中某一線段的端點 O 1 4基本概念BasicConcepts 2020 2 24 定理1 1 若線性規(guī)劃可行解K非空 則K是凸集 定理1 2 線性規(guī)劃的可行解集合K的點X是極點的充要條件為X是基本可行解 定理1 3 若線性規(guī)劃有最優(yōu)解 則最優(yōu)值一定可以在可行解集合的某個極點上到達 最優(yōu)解就是極點的坐標向量 定理1 2刻劃了可行解集的極點與基本可行解的對應(yīng)關(guān)系 極點是基本可行解 反之 基本可行解一定是極點 但它們并非一一對應(yīng) 有可能兩個或幾個基本可行解對應(yīng)于同一極點 退化基本可行解時 線性規(guī)劃的基本定理 1 4基本概念BasicConcepts 2020 2 24 定理1 3描述了最優(yōu)解在可行解集中的位置 若最優(yōu)解唯一 則最優(yōu)解只能在某一極點上達到 若具有多重最優(yōu)解 則最優(yōu)解是某些極點的凸組合 從而最優(yōu)解是可行解集的極點或界點 不可能是可行解集的內(nèi)點 若線性規(guī)劃的可行解集非空且有界 則一定有最優(yōu)解 若可行解集無界 則線性規(guī)劃可能有最優(yōu)解 也可能沒有最優(yōu)解 定理1 2及1 3還給了我們一個啟示 尋求最優(yōu)解不是在無限個可行解中去找 而是在有限個基本可行解中去尋求 下一節(jié)將介紹一種有效地尋找最優(yōu)解的方法 1 4基本概念BasicConcepts 2020 2 24 1 線性規(guī)劃常用的概念 可行解 基本解 基本可行解 最優(yōu)解 基本最優(yōu)解 基 可行基 最優(yōu)基 凸集 極點 凸點 凸組合 2 線性規(guī)劃的三個基本定理 作業(yè) 教材習(xí)題1 9 1 4基本概念BasicConcepts 下一節(jié) 單純形法 1 5單純形法SimplexMethod 2020 2 24 單純形計算方法 SimplexMethod 是先求出一個初始基可行解并判斷它是否最優(yōu) 若不是最優(yōu) 再換一個基可行解并判斷 直到得出最優(yōu)解或無最優(yōu)解 它是一種逐步逼近最優(yōu)解的迭代方法 當(dāng)系數(shù)矩陣A中可以觀察得到一個可行基時 通常是一個單位矩陣或m個線性無關(guān)的單位向量組成的矩陣 可以通過解線性方程組求得基本可行解 例1 15 用單純形法求例1 1線性規(guī)劃的最優(yōu)解 1 5單純形法SimplexMethod 1 5 1普通單純形法 2020 2 24 解 化為標準型 加入松馳變量x3 x4則標準型為 系數(shù)矩陣A及可行基B1 r B1 2 B1是一個初始基 x3 x4為基變量 x1 x2為非基變量 令x1 0 x2 0由約束方程知x3 40 x4 30得到初始基本可行解 X 1 0 0 40 30 T 1 5單純形法SimplexMethod 2020 2 24 以上得到的一組基可行解是不是最優(yōu)解 可以從目標函數(shù)中的系數(shù)看出 目標函數(shù)Z 300 x1 400 x2中x1的系數(shù)大于零 如果x1為一正數(shù) 則Z的值就會增大 同樣若x2不為零為一正數(shù) 也能使Z的值增大 因此只要目標函數(shù)中非基變量的系數(shù)大于零 那么目標函數(shù)就沒有達到最大值 即沒有找到最優(yōu)解 判別線性規(guī)劃問題是否達到最優(yōu)解的數(shù)稱為檢驗數(shù) 記作 j j 1 2 n 本例中 1 300 2 400 3 0 4 0 參看表1 6 a 最優(yōu)解判斷標準當(dāng)所有檢驗數(shù) j 0 j 1 n 時 基本可行解為最優(yōu)解 當(dāng)目標函數(shù)中有基變量xi時 利用約束條件將目標函數(shù)中的xi消去即可求出檢驗數(shù) 1 5單純形法SimplexMethod 檢驗數(shù)目標函數(shù)用非基變量表達時的變量系數(shù) 2020 2 24 進基列 出基行 bi ai2 ai2 0 i 表1 6 基變量 1 20 0 0 2 3 0 2 3 20 4 3 1 2 3 40 100 3 0 800 3 30 1 0 3 4 1 2 15 0 1 1 2 1 10 0 0 25 250 將3 2化為1 1 5單純形法SimplexMethod 20 15 2020 2 24 最優(yōu)解X 15 10 0 0 T 最優(yōu)值Z 8500 X 1 0 0 x1 1 5單純形法SimplexMethod x1 x2 O 10 20 30 40 10 20 30 40 X 2 0 20 X 3 15 10 2020 2 24 單純形法全過程的計算 可以用列表的方法計算更為簡潔 這種表格稱為單純形表 表1 6 計算步驟 1 求初始基可行解 列出初始單純形表 求出檢驗數(shù) 其中基變量的檢驗數(shù)必為零 2 判斷 a 若 j j n 得到最優(yōu)解 b 某個 k 0且aik i 1 2 m 則線性規(guī)劃具有無界解 見例1 18 c 若存在 k 0且aik i 1 m 不全非正 則進行換基 1 5單純形法SimplexMethod 2020 2 24 第 個比值最小 選最小比值對應(yīng)行的基變量為出基變量 若有相同最小比值 則任選一個 aLk為主元素 c 求新的基可行解 用初等行變換方法將aLk化為 k列其它元素化為零 包括檢驗數(shù)行 得到新的可行基及基本可行解 再判斷是否得到最優(yōu)解 b 選出基變量 求最小比值 1 5單純形法SimplexMethod 3 換基 a 選進基變量設(shè) k max j j 0 xk為進基變量 2020 2 24 例1 16 用單純形法求解 解 將數(shù)學(xué)模型化為標準形式 不難看出x4 x5可作為初始基變量 單純法計算結(jié)果如表1 7所示 1 5單純形法SimplexMethod 2020 2 24 表1 7 1 3 1 5 0 1 20 3 0 17 1 3 75 1 3 0 9 0 2 M 20 25 60 1 0 17 3 1 3 1 25 0 1 28 9 1 9 2 3 35 3 0 0 98 9 1 9 7 3 最優(yōu)解X 25 35 3 0 0 0 T 最優(yōu)值Z 145 3 1 5單純形法SimplexMethod 2020 2 24 例1 17 用單純形法求解 解 這是一個極小化的線性規(guī)劃問題 可以將其化為極大化問題求解 也可以直接求解 這時判斷標準是 j 0 j 1 n 時得到最優(yōu)解 容易觀察到 系數(shù)矩陣中有一個3階單位矩陣 x3 x4 x5為基變量 目標函數(shù)中含有基變量x4 由第二個約束得到x4 6 x1 x2 并代入目標函數(shù)消去x4得 1 5單純形法SimplexMethod 2020 2 24 表中 j 0 j 1 2 5所以最優(yōu)解為X 0 5 0 1 11 最優(yōu)值Z 2x1 2x2 x4 2 5 1 11極小值問題 注意判斷標準 選進基變量時 應(yīng)選 j 0的變量xj進基 1 5單純形法SimplexMethod 表1 8 2020 2 24 例1 18 求解線性規(guī)劃 解 化為標準型 1 5單純形法SimplexMethod 2020 2 24 初始單純形表為 2 1 0 x2進基 而a12 0 a22 0 沒有比值 從而線性規(guī)劃的最優(yōu)解無界 由模型可以看出 當(dāng)固定x1使x2 且滿足約束條件 還可以用圖解法看出具有無界解 1 5單純形法SimplexMethod 2020 2 24 例1 19 求解線性規(guī)劃 解 化為標準型后用單純形法計算如下表所示 1 5單純形法SimplexMethod 2020 2 24 表 3 中 j全部非正 則最優(yōu)解為 表 3 表明 非基變量x3的檢驗數(shù) 3 0 x3若增加 目標函數(shù)值不變 即當(dāng)x3進基時Z仍等于20 使x3進基x5出基繼續(xù)迭代 得到表 4 的另一基本最優(yōu)解 X 1 X 2 是線性規(guī)劃的兩個最優(yōu)解 它的凸組合 仍是最優(yōu)解 從而原線性規(guī)劃有多重最優(yōu)解 1 5單純形法SimplexMethod 2020 2 24 唯一最優(yōu)解的判斷 最優(yōu)表中所有非基變量的檢驗數(shù)非零 則線性規(guī)劃具有唯一最優(yōu)解 多重最優(yōu)解的判斷 最優(yōu)表中存在非基變量的檢驗數(shù)為零 則線則性規(guī)劃具有多重最優(yōu)解 無界解的判斷 某個 k 0且aik i 1 2 m 則線性規(guī)劃具有無界解退化基本可行解的判斷 存在某個基變量為零的基本可行解 1 5單純形法SimplexMethod 2020 2 24 在實際問題中有些模型并不含有單位矩陣 為了得到一組基向量和初基可行解 在約束條件的等式左端加一組虛擬變量 得到一組基變量 這種人為加的變量稱為人工變量 構(gòu)成的可行基稱為人工基 用大M法或兩階段法求解 這種用人工變量作橋梁的求解方法稱為人工變量法 例1 20 用大M法解下列線性規(guī)劃 1 大M單純形法 1 5 2大M和兩階段單純形法 1 5單純形法SimplexMethod 2020 2 24 解 首先將數(shù)學(xué)模型化為標準形式 式中x4 x5為松弛變量 x5可作為一個基變量 第一 三約束中分別加入人工變量x6 x7 目標函數(shù)中加入 Mx6 Mx7一項 得到人工變量單純形法數(shù)學(xué)模型 用前面介紹的單純形法求解 見下表 1 5單純形法SimplexMethod 2020 2 24 2 初始表中的檢驗數(shù)有兩種算法 第一種算法是利用第一 三約束將x6 x7的表達式代入目標涵數(shù)消去x6和x7 得到用非基變量表達的目標函數(shù) 其系數(shù)就是檢驗數(shù) 第二種算法是利用公式計算 如 最優(yōu)解X 31 3 13 19 3 0 0 T 最優(yōu)值Z 152 3 注意 1 5單純形法SimplexMethod 1 M是一個很大的抽象的數(shù) 不需要給出具體的數(shù)值 可以理解為它能大于給定的任何一個確定數(shù)值 2020 2 24 例1 21 求解線性規(guī)劃 解 加入松馳變量x3 x4化為標準型 在第二個方程中加入人工變量x5 目標函數(shù)中加上Mx5一項 得到 1 5單純形法SimplexMethod 2020 2 24 用單純形法計算如下表所示 1 5單純形法SimplexMethod 2020 2 24 表中 j 0 j 1 2 5 從而得到最優(yōu)解X 2 0 0 0 2 Z 10 2M 但最優(yōu)解中含有人工變量x5 0說明這個解是偽最優(yōu)解 是不可行的 因此原問題無可行解 兩階段單純形法與大M單純形法的目的類似 將人工變量從基變量中換出 以求出原問題的初始基本可行解 將問題分成兩個階段求解 第一階段的目標函數(shù)是 約束條件是加入人工變量后的約束方程 當(dāng)?shù)谝浑A段的最優(yōu)解中沒有人工變量作基變量時 得到原線性規(guī)劃的一個基本可行解 第二階段就以此為基礎(chǔ)對原目標函數(shù)求最優(yōu)解 當(dāng)?shù)谝浑A段的最優(yōu)解w 0時 說明還有不為零的人工變量是基變量 則原問題無可行解 1 5單純形法SimplexMethod 2 兩階段單純形法 2020 2 24 例1 22 用兩階段單純形法求解例19的線性規(guī)劃 解 標準型為 在第一 三約束方程中加入人工變量x6 x7后 第一階段問題為 用單純形法求解 得到第一階段問題的計算表如下 1 5單純形法SimplexMethod 2020 2 24 1 5單純形法SimplexMethod 2020 2 24 最優(yōu)解為最優(yōu)值w 0 第一階段最后一張最優(yōu)表說明找到了原問題的一組基可行解 將它作為初始基可行解 求原問題的最優(yōu)解 即第二階段問題為 1 5單純形法SimplexMethod 2020 2 24 用單純形法計算得到下表 最優(yōu)解X 31 3 13 19 3 0 0 T 最優(yōu)值Z 152 3 1 5單純形法SimplexMethod 2020 2 24 例1 23 用兩階段法求解例1 21的線性規(guī)劃 解 例1 21的第一階段問題為 用單純形法計算如下表 1 5單純形法SimplexMethod 2020 2 24 j 0 得到第一階段的最優(yōu)解X 2 0 0 0 2 T 最優(yōu)目標值w 2 0 x5仍在基變量中 從而原問題無可行解 1 5單純形法SimplexMethod 2020 2 24 解的判斷 唯一最優(yōu)解的判斷 最優(yōu)表中所有非基變量的檢驗數(shù)非零 則線規(guī)劃具有唯一最優(yōu)解 多重最優(yōu)解的判斷 最優(yōu)表中存在非基變量的檢驗數(shù)為零 則線則性規(guī)劃具有多重最優(yōu)解 無界解的判斷 某個 k 0且aik i 1 2 m 則線性規(guī)劃具有無界解 退化基本可行解的判斷 存在某個基變量為零的基本可行解 無可行解的判斷 1 當(dāng)用大M單純形法計算得到最優(yōu)解并且存在Ri 0時 則表明原線性規(guī)劃無可行解 2 當(dāng)?shù)谝浑A段的最優(yōu)值w 0時 則原問題無可行解 1 5單純形法SimplexMethod 2020 2 24 設(shè)有線性規(guī)劃 其中Am n且r A m X 0應(yīng)理解為X大于等于零向量 即xj 0 j 1 2 n 1 5 3計算公式 1 5單純形法SimplexMethod 2020 2 24 不妨假設(shè)A P1 P2 Pn 中前m個列向量構(gòu)成一個可行基 記為B P1 P2 Pm 矩陣A中后n m列構(gòu)成的矩陣記為N Pm 1 Pn 則A可以寫成分塊矩陣A B N 對于基B 基變量為XB x1 x2 xm T 非基變量為XN xm 1 xm 2 xn T 則X可表示成同理將C寫成分塊矩陣C CB CN CB C1 C2 Cm CN Cm 1Cm 2 cn 則AX b可寫成 1 5單純形法SimplexMethod 2020 2 24 因為r B m 或 B 0 所以B 1存在 因此可有 令非基變量XN 0 XB B 1b 由B是可行基的假設(shè) 則得到基本可行解 X B 1b 0 T 將目標函數(shù)寫成 1 5單純形法SimplexMethod 2020 2 24 得到下列五個計算公式 令XN 0 1 5單純形法SimplexMethod 2020 2 24 上述公式可用下面較簡單的矩陣表格運算得到 設(shè)初始矩陣單純形表1 16 將B化為I I為m階單位矩陣 CB化為零 即求基本可行解和檢驗數(shù) 用B 1左乘表中第二行 得到表1 17 表1 16 表1 17 1