線性規(guī)劃第五講單純形法的進一步講解大M法

1、第五講 單純形法的進一步討論一、大M法二、兩階段法-人工變量法人工變量法問題：線性規(guī)劃問題化為標準形時，若約束條件的系數(shù)矩陣中不存在單位矩陣，如何構(gòu)造初始可行基？ 人工變量法加入人工變量設(shè)線性規(guī)劃問題的標準型為：加入人工變量,構(gòu)造初始可行基. 人工變量法約束條件已改變，目標函數(shù)如何調(diào)整？人工變量法“懲罰” 人工變量?。?）大M法一、大 M 法人工變量在目標函數(shù)中的系數(shù)為 -M, 其中，M 為任意大的正數(shù)。目標函數(shù)中添加“罰因子”-M（M是任意大的正數(shù)）為人工變量系數(shù)，只要人工變量0，則目標函數(shù)不可能實現(xiàn)最優(yōu)。例: 求解線性規(guī)劃問題一、大 M 法一、大 M 法解:加入松弛變量和剩余變量進行標準

2、化, 加入人工變量構(gòu)造初始可行基. 求解結(jié)果出現(xiàn)檢驗數(shù)非正若基變量中含非零的人工變量， 則無可行解； 否則，有最優(yōu)解。一、大 M 法用單純形法求解（見下頁）。目標函數(shù)中添加“罰因子”-M為人工變量系數(shù)，只要人工變量0，則目標函數(shù)不可能實現(xiàn)最優(yōu)。 1 -2 1 -4 1 2 -2 0 1 3-6M M -1 3M-1 3 -1 -1 x1 x2 x3 0 x4 11 -M x6 3 -M x7 1 j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x4 x5 11 3/2 1 0 0 1 0 0 1 0 0 - M - M x6 x7 表1（初始單純形表）一、大 M 法（單

3、純形法求解） 3 -2 0 0 1 0 -2 0 1 1 M-1 0 3 -1 -1x1 x2 x3 0 x4 10 -M x6 1 -1 x3 1 j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x4 x5 1 0 -1 1 -2 0 1 0 1-3M - M - M x6 x7 一、大 M 法（單純形法求解）表2 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1 -1 x1 x2 x3 0 x4 12 -1 x2 1 -1 x3 1 j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x4 x5 4 i 2 -5 1 -2 0 1 1

4、-M -1 -M - M - M x6 x7 表3一、大 M 法（單純形法求解） 1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x1 x2 x3 3 x1 4 -1 x2 1 -1 x3 9 2 C j CB XB b1/3 -2/3 0 -1 2/3 -4/3 -1/3 -1/3 0 0 x4 x5 2/3 -5/3 1 -2 4/3 -7/3 1/3-M 2/3-M - M - M x6 x7 表4一、大 M 法（單純形法求解）最優(yōu)解為目標函數(shù)值 z=2檢驗數(shù)均非正，此為最終單純形表單純形法計算中的幾個問題1、目標函數(shù)極小化時解的最優(yōu)性判斷 只需用檢驗數(shù) 作為最優(yōu)性的標志。2、無可行解的判斷 當求解結(jié)果出現(xiàn)所有 時，如基變量仍 含有非零的人工變量（兩階段法求解時第一階 段目標函數(shù)值不等于0），則問題無可行解。退化 基可行解中存在基變量=0的解退化解 換入變量和換出變量的Bland規(guī)則選擇 中下標最小的非基變量 為換入變量, 這里:當按 規(guī)則計算存在兩個和兩個以上最小比值時,選下標最小的基變量為換出變量。單純形法計算中的幾個問題最優(yōu)解判斷小