單純形法(人工變量法）.ppt

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

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

2、變量在其余方程中不出現(xiàn)。7/25/20213一、單純形法的基本原理（一）基本變量：如果變量xj在某一方程中系數(shù)為1，而在其它一切方程中的系數(shù)為零，則稱xj為該方程中的基本變量。否則為非基本變量。（二）基本解：在典型方程中，設(shè)非基本變量為零，求解基本變量得到的解，稱為基本解。（三）基本可行解：基本變量為非負(fù)的一組基本解稱為基本可行解。7/25/20214規(guī)范形式—典型方程組(p-59)S.t.7/25/20215最優(yōu)性的檢驗(yàn)與解的判別7/25/20216則:7/25/20217檢驗(yàn)數(shù)對線性規(guī)劃問題的實(shí)際意義是：表示當(dāng)

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

4、步：尋求初始可行基，確定基變量第三步：寫出初始基本可行解和相應(yīng)的目標(biāo)函數(shù)值兩個關(guān)鍵的基本表達(dá)式：1、用非基變量表示基變量的表達(dá)式2、用非基變量表示目標(biāo)函數(shù)的表達(dá)式7/25/2021101、分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式通常把非基變量前面的系數(shù)叫做“檢驗(yàn)數(shù)”（非基變量前面的系數(shù)均為正數(shù)時，任何一個非基變量進(jìn)基都能使Z值增加）2、選哪一個非基變量進(jìn)基任何一個正檢驗(yàn)數(shù)對應(yīng)的非基變量？最大正檢驗(yàn)數(shù)對應(yīng)的非基變量？排在最前面的正檢驗(yàn)數(shù)對應(yīng)的非基變量？3、確定出基變量（最小比值原則）4、基變換，寫出新的用非基變量表示基變量的

5、表達(dá)式5、寫出新的用非基變量表示目標(biāo)函數(shù)的表達(dá)式檢驗(yàn)數(shù)仍有正的，返回（1）進(jìn)行討論，當(dāng)用非基變量表示目標(biāo)函數(shù)的表達(dá)式中，檢驗(yàn)數(shù)全部非正時，當(dāng)前基本可行解就是最優(yōu)解。第四步：分析兩個基本表達(dá)式，看看目標(biāo)函數(shù)是否還可以改善7/25/202111例8某制藥廠生產(chǎn)甲、乙兩種藥品，它們均須在A、B、C三種設(shè)備上加工，每種設(shè)備的使用時間，每噸藥品的加工時間以及所獲利潤見下表，甲、乙藥品各生產(chǎn)多少噸，可使該廠所獲利潤最大？表1－5藥品生產(chǎn)有關(guān)數(shù)據(jù)ABC利潤（百元/噸）甲35970乙95330設(shè)備使用時間（小時）540450720二

6、、單純形解法7/25/202112解：設(shè)甲、乙分別生產(chǎn)x1、x2噸，該廠所獲利潤為Z百元。建立數(shù)學(xué)模型如下：第二步：建立初始單純形表并進(jìn)行表的迭代（見表1－6）第一步：化線性規(guī)劃模型為標(biāo)準(zhǔn)規(guī)范型（見上面右邊）7/25/202113表1－6單純形法表格計(jì)算過程C基變量B7030000θX1X2X3X4X5000X3X4X554045072035[9]9531000100011809080Cj-ZjO70300000070X3X4X130050800018[10/3]1/3100010-1/3-5/91/937.5152

7、40Cj-Zj5600020/300-70/903070X3X2X11801575001010100-12/53/10-1/101-1/61/6Cj-Zj5700000-2-20/37/25/202114由表得最優(yōu)解相應(yīng)的最優(yōu)值Z＝5700例8的最優(yōu)解是最優(yōu)值是Z＝57007/25/202115單純形法的基本步驟:1．建立初始單純形表----確定初始基本可行解確定基變量、非基變量以及初始基本可行解和目標(biāo)函數(shù)的值。（１）求出相應(yīng)的檢驗(yàn)數(shù)在用非基變量表達(dá)的目標(biāo)函數(shù)表達(dá)式中，我們稱非基變量xj的系數(shù)為檢驗(yàn)數(shù)．2．最優(yōu)性檢驗(yàn)

8、7/25/202116（２）最優(yōu)解判別如果任何一個非基變量的值增加都不能使目標(biāo)函數(shù)值增加，即所有檢驗(yàn)數(shù)非正，則當(dāng)前的基本可行解就是最優(yōu)解，計(jì)算結(jié)束。（３）無有限最優(yōu)解判別如果有一個檢驗(yàn)數(shù)大于０，且其所在的列的所有aij非正，則表示可行域是不封閉的，且目標(biāo)函數(shù)值隨進(jìn)基變量的增加可以無限增加，此時，不存在有限最優(yōu)解（或稱有無界解或無最優(yōu)解），計(jì)算結(jié)