純形法(人工變量法

《純形法(人工變量法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第二章線性規(guī)劃——單純形法單純形是在n維空間里由n+1個點組成的最簡單圖形7/15/20211一、單純形法的基本原理單純形法是一種迭代的算法，它的思是在可行域的頂點----基本可行解中尋優(yōu)。由于頂點是有限個,因此，算法經(jīng)有限步可終止?；舅悸罚簭目尚杏虻囊粋€頂點到另一個頂點迭代求最優(yōu)解。（注：轉(zhuǎn)移的條件和目的是使MaxZ增加）7/15/20212①目標(biāo)求極大值②變量非負(fù)③右端項非負(fù)④全部等式約束單純形法要求線性規(guī)劃模型（P-56）標(biāo)準(zhǔn)形式規(guī)范形式⑤系數(shù)矩陣中包含一個單位子矩陣每個約束方程中要有一個變量的系數(shù)１，而這個變量在其余方程中不出現(xiàn)。7/15/20

2、213一、單純形法的基本原理（一）基本變量：如果變量xj在某一方程中系數(shù)為1，而在其它一切方程中的系數(shù)為零，則稱xj為該方程中的基本變量。否則為非基本變量。（二）基本解：在典型方程中，設(shè)非基本變量為零，求解基本變量得到的解，稱為基本解。（三）基本可行解：基本變量為非負(fù)的一組基本解稱為基本可行解。7/15/20214規(guī)范形式—典型方程組(p-59)S.t.7/15/20215最優(yōu)性的檢驗與解的判別(p-59)7/15/20216則:7/15/20217檢驗數(shù)對線性規(guī)劃問題的實際意義是：表示當(dāng)變量xj增加1個單位時，目標(biāo)函數(shù)的增加量；其經(jīng)濟(jì)意義表示相對利潤

3、．當(dāng)>0時，說明非基本變量增加1個單位，目標(biāo)函數(shù)可以增加，即現(xiàn)在的函數(shù)值不是最優(yōu)，還能增加．這時要將某個非基本變量換到基本變量中去（稱為進(jìn)基變量）．為了使目標(biāo)函數(shù)值增長最快，所以應(yīng)選擇檢驗數(shù)最大的一項所對應(yīng)的非基本變量進(jìn)基,7/15/20218得到最優(yōu)解或證明最優(yōu)解不存在標(biāo)準(zhǔn)型從可行域某個頂點開始檢查該點是否最優(yōu)解不是取一個“相鄰”、“更好”的頂點單純形法的基本原理規(guī)范型7/15/20219單純形法原理：第一步：引入非負(fù)的松弛變量，將LP化為標(biāo)準(zhǔn)形式第二步：尋求初始可行基，確定基變量第三步：寫出初始基本可行解和相應(yīng)的目標(biāo)函數(shù)值兩個關(guān)鍵的基本表達(dá)式：1、用

4、非基變量表示基變量的表達(dá)式2、用非基變量表示目標(biāo)函數(shù)的表達(dá)式7/15/2021101、分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式通常把非基變量前面的系數(shù)叫做“檢驗數(shù)”（非基變量前面的系數(shù)均為正數(shù)時，任何一個非基變量進(jìn)基都能使Z值增加）2、選哪一個非基變量進(jìn)基任何一個正檢驗數(shù)對應(yīng)的非基變量？最大正檢驗數(shù)對應(yīng)的非基變量？排在最前面的正檢驗數(shù)對應(yīng)的非基變量？3、確定出基變量（最小比值原則）4、基變換，寫出新的用非基變量表示基變量的表達(dá)式5、寫出新的用非基變量表示目標(biāo)函數(shù)的表達(dá)式檢驗數(shù)仍有正的，返回（1）進(jìn)行討論，當(dāng)用非基變量表示目標(biāo)函數(shù)的表達(dá)式中，檢驗數(shù)全部非正時，當(dāng)

5、前基本可行解就是最優(yōu)解。第四步：分析兩個基本表達(dá)式，看看目標(biāo)函數(shù)是否還可以改善7/15/202111例8某制藥廠生產(chǎn)甲、乙兩種藥品，它們均須在A、B、C三種設(shè)備上加工，每種設(shè)備的使用時間，每噸藥品的加工時間以及所獲利潤見下表，甲、乙藥品各生產(chǎn)多少噸，可使該廠所獲利潤最大？表1－5藥品生產(chǎn)有關(guān)數(shù)據(jù)ABC利潤（百元/噸）甲35970乙95330設(shè)備使用時間（小時）540450720二、單純形解法7/15/202112解：設(shè)甲、乙分別生產(chǎn)x1、x2噸，該廠所獲利潤為Z百元。建立數(shù)學(xué)模型如下：第二步：建立初始單純形表并進(jìn)行表的迭代（見表1－6）第一步：化線性規(guī)劃

6、模型為標(biāo)準(zhǔn)規(guī)范型（見上面右邊）7/15/202113表1－6單純形法表格計算過程CB基變量B7030000θX1X2X3X4X5000X3X4X554045072035[9]9531000100011809080Cj=Cj-ZjO70300000070X3X4X130050800018[10/3]1/3100010-1/3-5/91/937.515240Cj-Zj5600020/300-70/903070X3X2X11801575001010100-12/53/10-1/101-1/61/6Cj-Zj5700000-2-20/37/15/202114由表

7、得最優(yōu)解相應(yīng)的最優(yōu)值Z＝5700例8的最優(yōu)解是最優(yōu)值是Z＝57007/15/202115單純形法的基本步驟:1．建立初始單純形表----確定初始基本可行解確定基變量、非基變量以及初始基本可行解和目標(biāo)函數(shù)的值。（１）求出相應(yīng)的檢驗數(shù)在用非基變量表達(dá)的目標(biāo)函數(shù)表達(dá)式中，我們稱非基變量xj的系數(shù)為檢驗數(shù)．2．最優(yōu)性檢驗7/15/202116單純形法的基本步驟:1．建立初始單純形表----確定初始基本可行解確定基變量、非基變量以及初始基本可行解和目標(biāo)函數(shù)的值。觀察法：系數(shù)矩陣中是否有現(xiàn)成的單位矩陣LP限制條件中全是“≤”類型：將松弛變量作為初始基變量，其系數(shù)列向

8、量構(gòu)成單位矩陣思考：LP限制條件中全是“≥”或“=”類型，怎么辦？7/15/20