運(yùn)籌學(xué)ppt課件Ch1線(xiàn)性規(guī)劃

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