用單純形法解決線性規(guī)劃問題

運籌學期末論文鹽城師范學院運籌學期末論文題 目: 用單純形法解決線性規(guī)劃問題 姓 名: 陳 偉 二級學院: 數學科學學院 專 業(yè): 數學與應用數學 班 級: 111 班 學 號: 11211149 成績評定: 前 言線性規(guī)劃問題是數學以及日常生活中最基本的問題之一，如何快速有效的解決線性規(guī)劃問題是數學家也在努力研究的科目之一。以前中學時我們解決線性規(guī)劃問題一般采用的是圖解法，即畫出所給條件的可行域，找出目標函數的最優(yōu)解。這種方法的優(yōu)點是直觀性強，計算方便，但缺點是只適用于問題中有兩個變量的情況。下面我們介紹另外一種方法單純形法，來解決圖解法不能解決的問題。1 單純形法1.1 單純形法的基本思路利用求線性規(guī)劃問題基本可行解的方法求解較大規(guī)模的問題是不可行的。有選擇地取基本可行解，即從可行域的一個極點出發(fā)，沿著可行域的邊界移動到另一個相鄰的極點，要求新極點的目標函數值不比原目標函數值差。在線性規(guī)劃的可行域中先找出一個可行解，檢驗它是否為最優(yōu)解，如果是最優(yōu)解，計算停止；如果不是最優(yōu)解，那么可以判斷線性規(guī)劃無有限最優(yōu)解，或者根據一定步驟得出使目標函數值接近最優(yōu)值的另一個基本可行解。由于基本可行解的個數有限，所以總可以通過有限次迭代，得到線性規(guī)劃的最優(yōu)基本可行解或判定線性規(guī)劃無有限最優(yōu)解。1.2 單純形法的基本步驟第1步求初始基可行解，列出初始單純形表。對非標準型的線性規(guī)劃問題首先要化成標準形式。由于總可以設法使約束方程的系數矩陣中包含一個單位矩陣（P1,P2，Pm），以此作為基求出問題的一個初始基可行解。為檢驗一個基可行解是否最優(yōu)，需要將其目標函數值與相鄰基可行解的目標函數值進行比較。為了書寫規(guī)范和便于計算，對單純形法的計算設計了一種專門表格，稱為單純形表（見表11）。迭代計算中每找出一個新的基可行解時，就重畫一張單純形表。含初始基可行解的單純形表稱初始單純形表，含最優(yōu)解的單純形表稱最終單純形表。第2步：最優(yōu)性檢驗 表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 如表中所有檢驗數cj-zj0，且基變量中不含有人工變量時，表中的基可行解即為最優(yōu)解，計算結束。當表中存在cj-zj0時，如有Pj0，則問題為無界解，計算結束；否則轉下一步。第3步：從一個基可行解轉換到相鄰的目標函數值更大的基可行解，列出新的單純形表。（1）確定換入基的變量。只要有檢驗數大于零，對應的變量xj就可作為進基的變量，當有一個以上檢驗數大于零時，一般從中找出最大一個，其對應的變量xk作為進基變量。(2)確定出基的變量。=minbiaik丨aik0=brark， 確定xr是出基變量，ark為主元。(3)用進基變量xk替換出基變量xr，得到一個新的基，對應這個基可以找出一個新的基可行解，并相應地可以畫出一個新的單純形表(a)把第r行乘以1/ark，之后的結果填入新表的第r行。對于ir行，把第r行乘以（-aikalk）之后與原表中第i行。在xB列中的r行位置填入xk，其余行不變；在cB列中用ck代替r行原來的值，其余的行與原表中相同。(b)然后用xj的價值系數cJ減去cB列的各元素與xj列各元素的乘積，把計算結果填入xj列的最后一行，得到檢驗數，計算并填入所得的值。第4步：重復上述過程，就可以得到最優(yōu)解或判斷出無有限最優(yōu)解2 單純形法求解線性規(guī)劃問題的范例 max z=-3x1+x3 s.t. x1+x2+x34-2x1+x2-x313x2+x3=9xj0,(i=1.2.3)解：將此問題化為標準形式，在約束條件中添加松弛變量和人工變量后得， 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則當x2=5/2，x3=3/2，x4=0時目標函數有最優(yōu)解max z =3/2.3 單純形法小結 我覺得用單純形法解決線性規(guī)劃問題需要注意以下幾點，首先將問題化為標準形式時需要觀察約束系數矩陣中是否有單位矩陣，從而決定是否添加人工變量。第二個需要注意的點是在確定換入基和換出基時要細心計算，一旦換入