用單純形法解決線(xiàn)性規(guī)劃問(wèn)題

運(yùn)籌學(xué)期末論文鹽城師范學(xué)院運(yùn)籌學(xué)期末論文題 目: 用單純形法解決線(xiàn)性規(guī)劃問(wèn)題 姓 名: 陳 偉 二級(jí)學(xué)院: 數(shù)學(xué)科學(xué)學(xué)院 專(zhuān) 業(yè): 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 班 級(jí): 111 班 學(xué) 號(hào): 11211149 成績(jī)?cè)u(píng)定: 前 言線(xiàn)性規(guī)劃問(wèn)題是數(shù)學(xué)以及日常生活中最基本的問(wèn)題之一，如何快速有效的解決線(xiàn)性規(guī)劃問(wèn)題是數(shù)學(xué)家也在努力研究的科目之一。以前中學(xué)時(shí)我們解決線(xiàn)性規(guī)劃問(wèn)題一般采用的是圖解法，即畫(huà)出所給條件的可行域，找出目標(biāo)函數(shù)的最優(yōu)解。這種方法的優(yōu)點(diǎn)是直觀性強(qiáng)，計(jì)算方便，但缺點(diǎn)是只適用于問(wèn)題中有兩個(gè)變量的情況。下面我們介紹另外一種方法單純形法，來(lái)解決圖解法不能解決的問(wèn)題。1 單純形法1.1 單純形法的基本思路利用求線(xiàn)性規(guī)劃問(wèn)題基本可行解的方法求解較大規(guī)模的問(wèn)題是不可行的。有選擇地取基本可行解，即從可行域的一個(gè)極點(diǎn)出發(fā)，沿著可行域的邊界移動(dòng)到另一個(gè)相鄰的極點(diǎn)，要求新極點(diǎn)的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差。在線(xiàn)性規(guī)劃的可行域中先找出一個(gè)可行解，檢驗(yàn)它是否為最優(yōu)解，如果是最優(yōu)解，計(jì)算停止；如果不是最優(yōu)解，那么可以判斷線(xiàn)性規(guī)劃無(wú)有限最優(yōu)解，或者根據(jù)一定步驟得出使目標(biāo)函數(shù)值接近最優(yōu)值的另一個(gè)基本可行解。由于基本可行解的個(gè)數(shù)有限，所以總可以通過(guò)有限次迭代，得到線(xiàn)性規(guī)劃的最優(yōu)基本可行解或判定線(xiàn)性規(guī)劃無(wú)有限最優(yōu)解。1.2 單純形法的基本步驟第1步求初始基可行解，列出初始單純形表。對(duì)非標(biāo)準(zhǔn)型的線(xiàn)性規(guī)劃問(wèn)題首先要化成標(biāo)準(zhǔn)形式。由于總可以設(shè)法使約束方程的系數(shù)矩陣中包含一個(gè)單位矩陣（P1,P2，Pm），以此作為基求出問(wèn)題的一個(gè)初始基可行解。為檢驗(yàn)一個(gè)基可行解是否最優(yōu)，需要將其目標(biāo)函數(shù)值與相鄰基可行解的目標(biāo)函數(shù)值進(jìn)行比較。為了書(shū)寫(xiě)規(guī)范和便于計(jì)算，對(duì)單純形法的計(jì)算設(shè)計(jì)了一種專(zhuān)門(mén)表格，稱(chēng)為單純形表（見(jiàn)表11）。迭代計(jì)算中每找出一個(gè)新的基可行解時(shí)，就重畫(huà)一張單純形表。含初始基可行解的單純形表稱(chēng)初始單純形表，含最優(yōu)解的單純形表稱(chēng)最終單純形表。第2步：最優(yōu)性檢驗(yàn) 表11單純形表 Cj c1 , cm , cj , cn Cj 基 b x1 xm xj xn c1 x1 b1 c2 x2 b2 , , , cm xm bm 1 0 a1j a1n 0 0 a2j a2n , 0 , , 0 1 amj amncj-zj 0 0 cj-i=1mciaij ci-i=1ncnaij 如表中所有檢驗(yàn)數(shù)cj-zj0，且基變量中不含有人工變量時(shí)，表中的基可行解即為最優(yōu)解，計(jì)算結(jié)束。當(dāng)表中存在cj-zj0時(shí)，如有Pj0，則問(wèn)題為無(wú)界解，計(jì)算結(jié)束；否則轉(zhuǎn)下一步。第3步：從一個(gè)基可行解轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)值更大的基可行解，列出新的單純形表。（1）確定換入基的變量。只要有檢驗(yàn)數(shù)大于零，對(duì)應(yīng)的變量xj就可作為進(jìn)基的變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于零時(shí)，一般從中找出最大一個(gè)，其對(duì)應(yīng)的變量xk作為進(jìn)基變量。(2)確定出基的變量。=minbiaik丨aik0=brark， 確定xr是出基變量，ark為主元。(3)用進(jìn)基變量xk替換出基變量xr，得到一個(gè)新的基，對(duì)應(yīng)這個(gè)基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫(huà)出一個(gè)新的單純形表(a)把第r行乘以1/ark，之后的結(jié)果填入新表的第r行。對(duì)于ir行，把第r行乘以（-aikalk）之后與原表中第i行。在xB列中的r行位置填入xk，其余行不變；在cB列中用ck代替r行原來(lái)的值，其余的行與原表中相同。(b)然后用xj的價(jià)值系數(shù)cJ減去cB列的各元素與xj列各元素的乘積，把計(jì)算結(jié)果填入xj列的最后一行，得到檢驗(yàn)數(shù)，計(jì)算并填入所得的值。第4步：重復(fù)上述過(guò)程，就可以得到最優(yōu)解或判斷出無(wú)有限最優(yōu)解2 單純形法求解線(xiàn)性規(guī)劃問(wèn)題的范例 max z=-3x1+x3 s.t. x1+x2+x34-2x1+x2-x313x2+x3=9xj0,(i=1.2.3)解：將此問(wèn)題化為標(biāo)準(zhǔn)形式，在約束條件中添加松弛變量和人工變量后得， max z=-3x1+x3+0x4+0x5-Mx6-Mx7 s.t. x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xj0,(j=1.2.37) 列出單純形表： cj-30100-M-MCb基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj-zj-2M-34M10-M000x4330211-100x21-21-10-110-Mx7660403-31cj-zj6M-304M+103M-4M00x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/20x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-9/2000-4/3-M+3/4-M-1/4則當(dāng)x2=5/2，x3=3/2，x4=0時(shí)目標(biāo)函數(shù)有最優(yōu)解max z =3/2.3 單純形法小結(jié) 我覺(jué)得用單純形法解決線(xiàn)性規(guī)劃問(wèn)題需要注意以下幾點(diǎn)，首先將問(wèn)題化為標(biāo)準(zhǔn)形式時(shí)需要觀察約束系數(shù)矩陣中是否有單位矩陣，從而決定是否添加人工變量。第二個(gè)需要注意的點(diǎn)是在確定換入基和換出基時(shí)要細(xì)心計(jì)算，一旦換入