運籌學(xué)畢業(yè)論文單純形法

1、01算法分析1.1單純形算法1.1.1單純形法的基本思路利用求線性規(guī)劃問題基本可行解（極點）的方法求解較大規(guī)模的問題是不可行的。有選擇地取基本可行解，即從可行域的一個極點出發(fā)，沿著可行域的邊界移動到另一個相鄰的極點，要求新極點的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差。在線性規(guī)劃的可行域中先找出一個可行解，檢驗它是否為最優(yōu)解，如果是最優(yōu)解，計算停止；如果不是最優(yōu)解，那么可以判斷線性規(guī)劃無有限最優(yōu)解，或者根據(jù)一定步驟得出使目標(biāo)函數(shù)值接近最優(yōu)值的另一個

2、基本可行解。由于基本可行解的個數(shù)有限，所以總可以通過有限次迭代，得到線性規(guī)劃的最優(yōu)基本可行解或判定線性規(guī)劃無有限最優(yōu)解。1.1.2單純形法的基本步驟描述第1步：求初始基可行解，列出初始單純形表。對非標(biāo)準(zhǔn)型的線性規(guī)劃問題首先要化成標(biāo)準(zhǔn)形式。由于總可以設(shè)法使約束方程的系數(shù)矩陣中包含一個單位矩陣，以此作為基求出問題的一個初始基??12mPPP?可行解。為檢驗一個基可行解是否最優(yōu)，需要將其目標(biāo)函數(shù)值與相鄰基可行解的目標(biāo)函數(shù)值進(jìn)行比較。為了書寫規(guī)

3、范和便于計算，對單純形法的計算設(shè)計了一種專門表格，稱為單純形表(見表11)。迭代計算中每找出一個新的基可行解時，就重畫一張單純形表。含初始基可行解的單純形表稱初始單純形表，含最優(yōu)解的單純形表稱最終單純形表。第2步：最優(yōu)性檢驗。2列中用代替r行原來的值，其余的行與原表中相同。Bckc(2)然后用的價值系數(shù)減去列的各元素與列各對應(yīng)元素的乘積，把計jxjcBcjx算結(jié)果填入列的最后一行，得到檢驗數(shù)，計算并填入的值（以零減去jxj?Z??列各元

4、素與b列各元素的乘積）[1]。Bc第4步：重復(fù)上述過程，就可以得到最優(yōu)解或判斷出無有限最優(yōu)解。表12初始單純形表cjc1…cr…cm…cj…ck…CB基bx1…xr…xm…xj…xk…c1…ck…cmx1…xk…xm1rkrrkabbb??…rrkba…mkmrrkabba??1…0…0…1krkaa?…1rka…mkrkaa?…0…0…1…11rjjkrkaaab??…rjrkaa…rjmjmkrkaaaa??…0…1…0cjzj0…

5、??kkrkcza??…0…????rjjjkkrkaczcza???…0…1.1.3單純形算法求解線性規(guī)劃的范例在實踐中，根據(jù)實際問題的要求，常?？梢越⒕€性規(guī)劃問題的數(shù)學(xué)模型。下面這個范例，就是一個用單純形算法求解的線性規(guī)劃的范例。美佳公司計劃制造甲乙兩種家電產(chǎn)品。但因財力、物力等原因，資源有限，已知制造一個家電產(chǎn)品分別占用的設(shè)備A，B的臺時、調(diào)試時間、調(diào)試工序及每天可用于這兩種家電的能力、各售出一件的獲利情況，如表13所示。問該公