第二節(jié)單純形法

第二節(jié) 單純形法單純形法是求解線性規(guī)劃的主要算法， 1947年由美國斯坦福大學(xué)教授丹捷格（ G.B.Danzig）提出。盡管在其后的幾十年中，又有一些算法問世，但單純形法以其簡單實(shí)用的特色始終保持著絕對的 “ 市場 ” 占有率。單純形法是一種迭代的算法（設(shè)計(jì)在單純形表上實(shí)現(xiàn)），它的思想是在可行域的角點(diǎn)（稱為基本可行解）中尋優(yōu)。檢驗(yàn)這個角點(diǎn)是否最優(yōu)否是 停止確定一個初始角點(diǎn)尋找一個更好的角點(diǎn) 一、單純形法的步驟1.將模型化為標(biāo)準(zhǔn)型 標(biāo)準(zhǔn)型的特征： Max型、等式約束、非負(fù)約束非 標(biāo)準(zhǔn)形式如何化為標(biāo)準(zhǔn)1) Min型化為 Max型 加負(fù)號因?yàn)?，求一個函數(shù)的極小點(diǎn)，等價于求該函數(shù)的負(fù)函數(shù)的極大點(diǎn)。注意： Min型化為 Max型求解后，最優(yōu)解不變，但最優(yōu)值差負(fù)號。 2) 不等式約束化為等式約束分析： 以 例 1.1中煤的約束為例之所以 “ 不等 ” 是因?yàn)樽笥覂蛇呌幸粋€差額，稱為 “ 松弛量 ” ，若在左邊加上這個松弛量，則化為等式。而這個松弛量也是變量，記為 X3 ， 則有X3稱為松弛變量。問題： 它的實(shí)際意義是什么？ 煤資源的 “ 剩余 ” 。2.建立初始單純形表前提：模型 的系數(shù)陣 A中含 I（ 單位陣）。否則用人工變量法。初始單純形表的結(jié)構(gòu)全體變量名變量的價格系數(shù)約束系數(shù)陣與 A中的 I 相應(yīng)的變量（稱基變量）名基變量 的價格系數(shù)約束右端項(xiàng)3. 檢驗(yàn)該單純形表是否最優(yōu)檢驗(yàn)數(shù)：每個變量的檢驗(yàn)數(shù)等于該變量的價格系數(shù)減去 與該變量的系數(shù)列之積。法則：如果全體檢驗(yàn)數(shù)均非正，則本表為最優(yōu)，相應(yīng)的最優(yōu)解 否則轉(zhuǎn) 4。練習(xí)： 寫出下列線性規(guī)劃的標(biāo)準(zhǔn)型和初始單純形表，并檢驗(yàn)該表是否最優(yōu)。由于檢驗(yàn)數(shù)中有正的，故本表不是最優(yōu)。4. 計(jì)算下一張單純形表（ 1）確定本表的進(jìn)基、出基變量和主元選本表正檢驗(yàn)數(shù)中最大者，其相應(yīng)的變量 xk 進(jìn) 基；計(jì)算 與 xk 的 系數(shù)列之比（記 ，稱檢驗(yàn)比） ,選 中最小者相應(yīng)的變量 xl 出基（注意：當(dāng) xk 的系數(shù)列中有零或負(fù)值時，相應(yīng) 不算）； xk 列與 xl 行的 交叉元即主元。 例如（ 2）基于主元計(jì)算下一張單純形表用 初等行變換方法，先將主元消成 1，再用此 1將其所在列的其余元消成 0，所得結(jié)果寫在新表上；轉(zhuǎn)第 3步（即檢驗(yàn) 新表是否最優(yōu)）。 例如例 1.7：用單純形法求解例 1.1 （請解釋其實(shí)際意義）練習(xí)：用單純形法求解下面的線性規(guī)劃 總結(jié)表的規(guī)律：1. 表中基變量的系數(shù)列有何特征？2. 基變量的檢驗(yàn)數(shù)有何特征？ 均為單位向量列； 均為零。例 1.8：填出表中空白：問題：如果空白的不是基變量列怎么辦呢？3. 表上每一列的含義：4. 每張表上 B-1的位置在哪？ 對應(yīng)于初