第二節(jié)單純形法

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