單純形法綜述

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 單純形法綜述zy-曹文亮單純形法是1947年由George Bernard Dantzing(1914-2005)創(chuàng)建的，單純形法的創(chuàng)建標(biāo)志著線性規(guī)劃問題的誕生。線性規(guī)劃問題是研究在線性約束條件下，求線性函數(shù)的極值問題。然而，對這類極值問題，經(jīng)典的極值理論是無能為力的，只有單純形法才能有效解決這類極值問題的求解。線性規(guī)劃是數(shù)學(xué)規(guī)劃的一個重要分支，也是最早形成的一個分支，線性規(guī)劃的理論與算法均非常成熟，在實際問題和生產(chǎn)生活中的應(yīng)用非常廣泛；線性規(guī)劃問題的誕生標(biāo)志著一個新的應(yīng)用數(shù)學(xué)分支數(shù)學(xué)規(guī)劃時代的到來。過去的60年中，數(shù)學(xué)規(guī)劃已經(jīng)成為一門成熟的學(xué)科

2、。其理論與方法被應(yīng)用到經(jīng)濟、金融、軍事等各個領(lǐng)域。數(shù)學(xué)規(guī)劃領(lǐng)域內(nèi)，其他重要分支的很多問題是在線性規(guī)劃理論與算法的基礎(chǔ)上建立起來的，同時也是利用線性規(guī)劃的理論來解決和處理的。由此可見，線性規(guī)劃問題在整個數(shù)學(xué)規(guī)劃和應(yīng)用數(shù)學(xué)領(lǐng)域中占有重要地位。因此，研究單純形法的產(chǎn)生與發(fā)展對于認(rèn)識整個數(shù)學(xué)規(guī)劃的發(fā)展有重大意義。單純形法是從某一基可行解出發(fā)，連續(xù)地尋找相鄰的基可行解，直到達到最優(yōu)的迭代過程，其實質(zhì)是解線性方程組。概述：根據(jù)單純形法的原理，在線性規(guī)劃問題中，（控制變量）x1，x2，x n的值稱為一個解,滿足所有的的解稱為可行解。使目標(biāo)函數(shù)達到最大值（或最小值）的可行解稱為最優(yōu)解。這樣，一個最優(yōu)解能在整個

3、由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達到最大值（或最小值）。求解線性規(guī)劃問題的目的就是要找出最優(yōu)解。最優(yōu)解可能出現(xiàn)下列情況之一：存在著一個最優(yōu)解；存在著無窮多個最優(yōu)解；不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒有可行解或各項約束條件不阻止的值無限增大（或向負的方向無限增大）。無最優(yōu)解與無可行解是兩個不同的概念。  無可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指     線性規(guī)劃問題的可行域為空集；  無最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目標(biāo)函數(shù)達不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于

4、無窮大（或者無窮?。?。無最優(yōu)解也稱為無限最優(yōu)解，或無界解。無最優(yōu)解判別定理：在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗行存在某個大于零的檢驗數(shù)，但是該檢驗數(shù)所對應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負數(shù)或零，則該線性規(guī)劃問題無最優(yōu)解。無窮多最優(yōu)解判別原理：若線性規(guī)劃問題某個基本可行解所有的非基變量檢驗數(shù)都小于等于零，但其中存在一個檢驗數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。退化與循環(huán)：如果在一個基本可行解的基變量中至少有一個分量為零，則稱此基本可行解是退化的基本可行解。 產(chǎn)生的原因：在單純形法計算中用最小比值原則確定換出變量時，有時存在兩個或兩個以上相同的最小比值，那么

5、在下次迭代中就會出現(xiàn)一個甚至多個基變量等于零。退化可能出現(xiàn)以下情況：  進行進基、出基變換后，雖然改變了基，但沒有改變基本可行解（極點），目標(biāo)函數(shù)當(dāng)然也不會改進。進行若干次基變換后，才脫離退化基本可行解（極點），進入其他基本可行解（極點）。這種情況會增加迭代次數(shù)，使單純形法收斂的速度減慢。  在特殊情況下，退化會出現(xiàn)基的循環(huán)，一旦出現(xiàn)這樣的情況，單純形迭代將永遠停留在同一極點上，因而無法求得最優(yōu)解。事實上，已經(jīng)有人給出了循環(huán)的例子。單純形法的一般解題步驟可歸納如下：把線性規(guī)劃問題的約束方程組表達成典范型方程組，找出基本可行解作為初始基本可行解。若基本可行

6、解不存在，即約束條件有矛盾，則問題無解。若基本可行解存在，從初始基本可行解作為起點，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。按步驟3進行迭代,直到對應(yīng)檢驗數(shù)滿足最優(yōu)性條件（這時目標(biāo)函數(shù)值不能再改善），即得到問題的最優(yōu)解。若迭代過程中發(fā)現(xiàn)問題的目標(biāo)無界，則終止。用單純形法求解線性規(guī)劃問題所需的迭代次數(shù)主要取決于約束條件的個數(shù)?，F(xiàn)在一般的線性規(guī)劃問題都是應(yīng)用單純形法標(biāo)準(zhǔn)在計算機上求解，對于具有106個決策變量和104個約束條件的線性規(guī)劃問題已能在計算機上解得。求解步驟：（1） 確定初始基可行解1 從線性規(guī)劃標(biāo)準(zhǔn)形的系數(shù)矩陣中能直接找出m個線性獨立

7、的單位向量；2 對約束條件全為“<=”連接的LP，化為標(biāo)準(zhǔn)形，左端添加松弛變量后即形成一個單位子矩陣； 3 約束條件中含有“<=”或“=”連接的方程，在插入剩余變量后找不到單位矩陣，則必須采用“人造基”法，也稱“人工變量”法。（2） 最優(yōu)性檢驗及解的判別準(zhǔn)則1 最優(yōu)性判定準(zhǔn)則2 多重最優(yōu)解判定準(zhǔn)則3 無界最優(yōu)解判定準(zhǔn)則（3） 換基迭代1 確定換入變量2 確定換出變量3 樞運算（旋轉(zhuǎn)運算）單純形法 - 正文：根據(jù)單純形法的原理，在線性規(guī)劃問題中，決策變量（控制）x1，x2，x n的值稱為一個解,滿足所有的約束條件的解稱為可行解。使目標(biāo)函數(shù)達到最大值（或最小值）的可行解稱為最優(yōu)解。這樣

8、，一個最優(yōu)解能在整個由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達到最大值（或最小值）。求解線性規(guī)劃問題的目的就是要找出最優(yōu)解。可能出現(xiàn)下列情況之一：存在著一個最優(yōu)解；存在著無窮多個最優(yōu)解；不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒有可行解或各項約束條件不阻止目標(biāo)函數(shù)的值無限增大（或向負的方向無限增大）。要縮小對最優(yōu)解的搜索范圍，就必須認(rèn)識最優(yōu)解的一般性質(zhì)，最優(yōu)解如果存在的話，則它必然處于可行區(qū)域的邊界上。任何一項約束條件的邊界是用“”號來替換該約束條件中的“”或“”號而得到的。每一個邊界方程確定一個超平面。因此，可行區(qū)域的邊界是由那些滿足一個或同時滿足幾個（即處在作為邊界的一個或幾個超平面上）的可行

9、解所組成，而且最優(yōu)解必在其中。最優(yōu)解不僅是在可行區(qū)域的邊界上，而且也在這個區(qū)域的一個隅角上。一個可行解，如果不處在由另兩個可行解連接起來的任何線段上，它就是一個角點可行解。如果連接兩個角點可行解的線段處在可行區(qū)域的邊界上，這兩個角點可行解就稱為相鄰的角點可行解。角點可行解具有下列三個重要性質(zhì)：如果存在著一個最優(yōu)解，那么它必定是角點可行解。如果存在有多個最優(yōu)解，那么至少有兩個最優(yōu)解必定是相鄰的角點可行解。只存在有限個數(shù)的角點可行解。如果一個角點可行解按目標(biāo)來衡量時比其所有的相鄰角點可行解更好一些，那它就比所有其他角點可行解都更好，也就是最優(yōu)解。上述這些性質(zhì)構(gòu)成單純形法的原理基礎(chǔ)。最后一個性質(zhì)的重

10、要性在于它為一個角點可行解是否是最優(yōu)解提供了一種簡便的檢驗標(biāo)準(zhǔn)，因而毋需列舉所有的可行解。單純形法正是利用了這個性質(zhì)，只要檢查少數(shù)的角點可行解，并且一旦這個最優(yōu)性檢驗獲得通過就可立即停止運算。單純形法的運算步驟可歸結(jié)為：起始步驟在一個角點可行解上開始。迭代步驟移動至一個更好一些的相鄰角點可行解（根據(jù)需要反復(fù)進行這一步驟）。停止法則在當(dāng)前角點可行解比所有相鄰角點可行解都更好些時停止。當(dāng)前角點可行解就是一個最優(yōu)解。單純形法的優(yōu)點及其成功之處在于它只需要較少的有限次數(shù)的，即可找到最優(yōu)解。改進單純形法：原單純形法不是很經(jīng)濟的。1953年美國數(shù)學(xué)家G.B.丹齊克為了改進單純形法每次迭代中積累起來的進位誤

11、差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區(qū)別是在逐次迭代中不再以高斯消去法為基礎(chǔ)，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數(shù)。這樣做可以減少迭代中的累積誤差，提高計算精度，同時也減少了在計算機上的存儲量。對偶單純形法： （Dual Simplex Method）1954年美國數(shù)學(xué)家C.萊姆基提出對偶單純形法。單純形法是從原始問題的一個可行解通過迭代轉(zhuǎn)到另一個可行解，直到檢驗數(shù)滿足最優(yōu)性條件為止。對偶單純形法則是從滿足對偶可行性條件出發(fā)通過迭代逐步搜索原始問題的最優(yōu)解。在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。設(shè)原始問題為mincx|Ax=b，x0，則其對偶問題（Dual Problem）為 maxyb|yAc。當(dāng)原始問題的一個基解滿足最優(yōu)性條件時,其檢驗數(shù)cBB-1A-c0。即知y=cB