運籌學第五章1.ppt

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