1 第五章單純形法 1 單純形法的基本思路和原理 基本思路 從可行域的某個頂點開始 判斷此頂點是否是最優解 若不是 再找另一個使得目標函數值更優的頂點 稱之為迭代 再判斷此點是否是最優解 直到找到一個頂點為其最優解 即使其目標函數值最優的解 或能判斷出線性規劃問題無最優解 基本可行解 可行域的頂點 初始基本可行解 第一個找到的可行域的頂點 一 找出一個初始基本可行解 注 一個LP問題若有最優解 一定是基本可行解 2 將其變為標準形式如下 系數矩陣 約束方程組 P5 P4 P6 3 方程組有無數組解 如何找出一個初始基本可行解 1 幾個線性規劃的基本概念 基 在LP問題中 約束方程組的約束矩陣為m n矩陣 其秩為m 若B是A中的任何一個m m階非奇異子矩陣 即B可逆 B 0 則稱B是線性規劃問題中的一個基 它們是由A中3個線性無關的列向量組成的 基向量 基B中的每一列向量pj 基B中共有m個列向量 4 非基向量 不在B中的A的列向量pj 叫做非基向量 基變量 與基向量pj對應的變量xj叫做基變量 基變量有m個 如 x1 x2 s1是對應B1的基變量 而s1 s2 s3是對應B2的基變量 非基變量 與非基向量pj對應的變量xj叫做非基變量 非基變量有n m個 P2 5 解得 此時得到線性規劃的一個基本解 此解不是線性規劃的可行解 約束方程就變為 基 本 解 在約束方程組中 對于選定的基B 令所有的非基變量為零 得到滿足約束方程組的一組解 稱為對應于基B的基 本 解 P2 基本解的特點 所有的非基變量全為零 6 約束方程就變為 得基本解 此解是可行解 基 本 可行解 滿足非負條件的基本解叫做基可行解 其對應的基B叫做可行基 注 可行基是由基本可行解而定義的 問題 是否能在求解之前 找到一個可行基 可行基 基本可行解 2 如何找出一個初始基本可行解 P2 基本可行解的特點 1 非基變量全為零 2 基變量非負 7 此解也是基本可行解 初始基本可行解找到了 此基B叫初始可行基 標準形式 8 初始可行基與初始基本可行解 在第一次找可行基時 所找到的基 或為單位矩陣或為由單位矩陣的各列向量組成 稱之為初始可行基 相應的基本可行解叫初始基本可行解 注 若在系數矩陣中找不到單位矩陣或由單位矩陣的各列向量組成的初始可行基 需要構造初始可行基 9 二 最優性檢驗 最優性檢驗 檢驗已求得的基本可行解是否是最優解 1 最優性檢驗的依據 檢驗數 j 也可把基變量在目標函數中的系數看作是零 選基 則檢驗數為 10 2 最優解判定定理 定理 對于求最大目標函數問題中 對于某個基本可行解 如果所有的檢驗數 j 0 則這個基本可行解是最優解 事實上 假設用非基變量表示的目標函數為 11 對于目標函數最小值的情況只需把定理中的 改為 注 并不是所有LP問題都有最優解 如何判斷LP問題無最優解 第四節介紹 12 三 基變換 求最優解的思想 從一個基本可行解到另一個基本可行解 最終到達最優解 迭代 求最優解的過程 從一個可行基到另一個可行基 最后找到一個可行基 使其對應的基可行解為最優解 如何通過基變換找到一個新的可行基 從可行基中換一個列向量使其和原來的基中的列向量線性無關 這樣可以得到一個新的可行基 其對應的新的基可行解的目標函數值更優 1 入基變量的確定 目標函數 入基變量 13 選哪一個變量出基 2 出基變量的確定 得基本解 此解不是基可行解 選基 14 得基本解 是基本可行解 確定出基變量的原則 1 使新的基本解為可行解 2 使目標函數改進量最大 P13 15 確定出基變量的方法 16 得基本可行解 此時的目標函數值為 而初始基可行解 對應的目標函數值為 17 用此法選出基變量 不僅保證了基本解可行 而且新的