運(yùn)籌學(xué)第五章1.ppt

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