資源描述：
《單純形法(人工變量法）.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第二章線性規(guī)劃——單純形法單純形是在n維空間里由n+1個點組成的最簡單圖形7/25/20211一、單純形法的基本原理單純形法是一種迭代的算法，它的思是在可行域的頂點----基本可行解中尋優(yōu)。由于頂點是有限個,因此，算法經有限步可終止。基本思路：從可行域的一個頂點到另一個頂點迭代求最優(yōu)解。（注：轉移的條件和目的是使MaxZ增加）7/25/20212①目標求極大值②變量非負③右端項非負④全部等式約束單純形法要求線性規(guī)劃模型（P-56）標準形式規(guī)范形式⑤系數矩陣中包含一個單位子矩陣每個約束方程中要有一個變量的系數１，而這個
2、變量在其余方程中不出現。7/25/20213一、單純形法的基本原理（一）基本變量：如果變量xj在某一方程中系數為1，而在其它一切方程中的系數為零，則稱xj為該方程中的基本變量。否則為非基本變量。（二）基本解：在典型方程中，設非基本變量為零，求解基本變量得到的解，稱為基本解。（三）基本可行解：基本變量為非負的一組基本解稱為基本可行解。7/25/20214規(guī)范形式—典型方程組(p-59)S.t.7/25/20215最優(yōu)性的檢驗與解的判別7/25/20216則:7/25/20217檢驗數對線性規(guī)劃問題的實際意義是： 表示當
3、變量xj增加1個單位時，目標函數的增加量；其經濟意義表示相對利潤．當>0時，說明非基本變量增加1個單位，目標函數可以增加，即現在的函數值不是最優(yōu)，還能增加．這時要將某個非基本變量換到基本變量中去（稱為進基變量）．為了使目標函數值增長最快，所以應選擇檢驗數最大的一項所對應的非基本變量進基,7/25/20218得到最優(yōu)解或證明最優(yōu)解不存在標準型從可行域某個頂點開始檢查該點是否最優(yōu)解不是取一個“相鄰”、“更好”的頂點單純形法的基本原理規(guī)范型7/25/20219單純形法原理：第一步：引入非負的松弛變量，將LP化為標準形式第二
4、步：尋求初始可行基，確定基變量第三步：寫出初始基本可行解和相應的目標函數值兩個關鍵的基本表達式：1、用非基變量表示基變量的表達式2、用非基變量表示目標函數的表達式7/25/2021101、分析用非基變量表示目標函數的表達式通常把非基變量前面的系數叫做“檢驗數”（非基變量前面的系數均為正數時，任何一個非基變量進基都能使Z值增加）2、選哪一個非基變量進基任何一個正檢驗數對應的非基變量？最大正檢驗數對應的非基變量？排在最前面的正檢驗數對應的非基變量？3、確定出基變量（最小比值原則）4、基變換，寫出新的用非基變量表示基變量的
5、表達式5、寫出新的用非基變量表示目標函數的表達式檢驗數仍有正的，返回（1）進行討論，當用非基變量表示目標函數的表達式中，檢驗數全部非正時，當前基本可行解就是最優(yōu)解。第四步：分析兩個基本表達式，看看目標函數是否還可以改善7/25/202111例8某制藥廠生產甲、乙兩種藥品，它們均須在A、B、C三種設備上加工，每種設備的使用時間，每噸藥品的加工時間以及所獲利潤見下表，甲、乙藥品各生產多少噸，可使該廠所獲利潤最大？表1－5藥品生產有關數據ABC利潤（百元/噸）甲35970乙95330設備使用時間（小時）540450720二
6、、單純形解法7/25/202112解：設甲、乙分別生產x1、x2噸，該廠所獲利潤為Z百元。建立數學模型如下：第二步：建立初始單純形表并進行表的迭代（見表1－6）第一步：化線性規(guī)劃模型為標準規(guī)范型（見上面右邊）7/25/202113表1－6單純形法表格計算過程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ōu)值Z＝5700例8的最優(yōu)解是最優(yōu)值是Z＝57007/25/202115單純形法的基本步驟:1．建立初始單純形表----確定初始基本可行解確定基變量、非基變量以及初始基本可行解和目標函數的值。（１）求出相應的檢驗數在用非基變量表達的目標函數表達式中，我們稱非基變量xj的系數為檢驗數．2．最優(yōu)性檢驗
8、7/25/202116（２）最優(yōu)解判別如果任何一個非基變量的值增加都不能使目標函數值增加，即所有檢驗數非正，則當前的基本可行解就是最優(yōu)解，計算結束。（３）無有限最優(yōu)解判別如果有一個檢驗數大于０，且其所在的列的所有aij非正，則表示可行域是不封閉的，且目標函數值隨進基變量的增加可以無限增加，此時，不存在有限最優(yōu)解（或稱有無界解或無最優(yōu)解），計算結
