單純形法計算步驟

關(guān)于單純形法計算步驟第1頁，共17頁，2023年，2月20日，星期三既然最優(yōu)解如果存在，必定可以在基本可行解處取到，因為只要在基本可行解集合（頂點集合）中尋找即可?；究尚薪馐墙K止是否最優(yōu)？否迭代尋找更好的基本可行解判斷問題無最優(yōu)解單純形方法基本思想第2頁，共17頁，2023年，2月20日，星期三單純形法計算步驟第3頁，共17頁，2023年，2月20日，星期三單純形表cjc1

c2…cm

cm+1…ck…cnCBXBbx1

x2…xmxm+1…xk…xnc1c2cmx1x2xmb1b2bm10…0a1m+1…a1k…a1n01…0a2m+1…a2k…a2n

00…1amm+1…amk…amnσj00…0第4頁，共17頁，2023年，2月20日，星期三單純形法的基本法則

法則1

最優(yōu)性判定法則若對基可行解X1，所有檢驗數(shù)σj≤0，則X1為最優(yōu)解。法則2

入基變量確定法則設(shè)，則xk為入基變量。法則2

出基變量確定法則設(shè)，則xl為入基變量。第5頁，共17頁，2023年，2月20日，星期三算例求解下列LP問題第6頁，共17頁，2023年，2月20日，星期三0-2-3/401/20σj-280103-10σj

03-4010x6

002x5-200x601[4]-2012x400-1317x10x4x3x2x1bXBCB03-10Cj0-12/5-4/500-1/5σjx1021/40[5/2]1100x3001/41-1/2033x6

18-3/40-5/2010x204/51/10012/54-1x302/53/10101/553x6

110-1/2001110算例310/34第7頁，共17頁，2023年，2月20日，星期三關(guān)于單純形法的補充說明

無窮多最優(yōu)解與唯一最優(yōu)解的判別法則若對某基可行解X1，（1）所有檢驗數(shù)σj≤0，且有一個非基變量xk的檢驗數(shù)等于0，則問題有無窮多最優(yōu)解；（2）所有非基變量的檢驗數(shù)σj<0，則問題有唯一最優(yōu)解。第8頁，共17頁，2023年，2月20日，星期三cj112-1CBXBbx1x2x3x421x3x210[1]-10110-12σj000-111x1x211100111-11σj000-1第9頁，共17頁，2023年，2月20日，星期三關(guān)于單純形法的補充說明

無最優(yōu)解（無界解）的判定若對基可行解X1，存在非基變量xk的檢驗數(shù)σk>0，但aik≤0，i=1，2，…，m即xk的系數(shù)列向量無正分量，則問題無最優(yōu)解。第10頁，共17頁，2023年，2月20日，星期三關(guān)于單純形法的補充說明

求minz

的情況直接計算最優(yōu)性檢驗條件改為：所有σj≥0；入基變量確定法則改為：如果則xk為入基變量。第11頁，共17頁，2023年，2月20日，星期三關(guān)于單純形法的補充說明cj22300CBXBbx1x2x3x4x523x2x31/42/5[1/2]1/21001-1/4000-1/20σj-1/2001/203/2023x1x31/23/20102-101-1/201/400-1/20σj0101/403/20X*=(0.5,0,0.15,0,0)T，z=2×1/2+3×3/20=1.45第12頁，共17頁，2023年，2月20日，星期三練習(xí)第13頁，共17頁，2023年，2月20日，星期三練習(xí)第14頁，共1