Can you summarize the following document?
        
  假設有n個變數和m個約束。線性規劃的標準形式如下:  所有其他形式的線性規劃方程組都可以按照下列方式轉化成標準形式:

  可以將標準形式的線性規劃轉化為鬆弛形式,以方便運算。 在原來n個變數,m個約束的線性規劃中,加入m個新的變數,將原來的不等式化為等式:  formula_8  當然,此時formula_9依然成立。  我們將formula_10這些變數稱為非基變數,它們構成的集合記為N。將 formula_10這些變數稱為基變數,它們構成的集合記為B。簡單地理解,非基變數能夠由基變數唯一確定。  在這樣的定義下,線性規劃的鬆弛形式可以寫為如下形式:  formula_12  因此,線性規劃的鬆弛形式可以由c, A, b, N, B唯一確定,c是長度為n+m的向量,b是長度為m的向量,A是m*(n+m)的矩陣。N, B是整數集合,分別表示非基變數集合以及基變數集合。

  轉軸操作是單純形法中的核心操作,其作用是將一個基變數與一個非基變數進行互換。可以將轉軸操作理解為從單純形上的一個頂點走向另一個頂點。  設變數formula_4屬於B(基變數),變數formula_4屬於N(非基變數),執行轉軸操作pivot(d,e)之後,formula_4將變為非基變數,相應地formula_4將變為基變數。  具體地說,一開始我們有  formula_17  移項,得  formula_18  如果formula_19,我們有  formula_20  將此式代入其他的約束等式以及目標函式,我們就實現了formula_4與formula_4在基變數和非基變數上的互換。

  單純形法的一般解題步驟可歸納如下:

  如果b向量所有元素非負,則顯然我們只需要令所有的變數等於0,就可以得到一個可行解。在這種情況下,通過下述最優化過程,我們可以得到該線性規劃的最優解,或者指出該線性規劃的最優解為無窮大(不存在)。  根據formula_27的最小性不難證明pivot(d, e)不會破壞b的非負性。因此將所有變數取0值仍然是可行解。同時,根據formula_29,我們發現v一定是不降的。這就達到了更新解的目的。  不難發現,演算法終止有兩種情況: 可以證明,對於第一種情況,我們已經得到了該線性規劃的最優解。當前的v即為答案。嚴格證明比較複雜,但是直觀上是很容易理解的。因為所有的非基變數都是非負的,而所有的c都是非正的,因此只要某個非基變數不為0,就會使得目標函式更小。  對於第二種情況來說,很容易證明此時線性規劃的最優解是無窮大。只要讓其他所有變數均為0,變數formula_4為正無窮。由於所有的formula_4都非正,因此非基變數的非負性得到保證。同時由於formula_24,目標函式值為正無窮。

  例:解最優化問題:  formula_34  formula_35  formula_36  formula_37  列單純形表(即矩陣): 然後從c所在行的正數中最大的一個所對應的變數作為基變數,因為這裡兩者一樣,不妨選為formula_38。  由於拿formula_38所在列的正係數去除b所在列的數的結果為formula_40,故取formula_41離開基變數。  然後對該矩陣進行行變換,使formula_38所在列變成單位向量:  接下來令c所在行的其餘的正數中最大的一個所在列的變數formula_43進入基變數,並且根據formula_44,令formula_45離開基變數。  繼續進行行變換,得到  由於c所在行的所有數都非正,問題結束。最優解為formula_46,最優值為formula_47。

  如果b向量並不全為非負,則我們需要通過初始化過程來找到一個可行解,然後才可以使用最優化過程進行優化。當然,此時原線性規劃不一定存在可行解。  具體的方法是,加入一個新的非基變數formula_4,並在原線性規劃的基礎上構造一個新的輔助的線性規劃。  formula_49  注意這裡N集合並不包含formula_4。  然後,選擇一個基變數formula_4使得formula_4最小,執行轉軸操作pivot(d, 0)。不難證明該操作過後所有的b值全部非負。然後,使用前文中所述的最優化過程求解該輔助線性規劃。  由於formula_4非負,因此該線性規劃的答案非正。如果答案為負數,則說明原線性規劃不可能讓所有的基變數都非負,因此原線性規劃無可行解。否則,只要令所有變數為0,並去掉formula_4變數,就可以得到可行解。  在從輔助線性規劃轉化到原來的線性規劃的過程中,如果formula_4已經是非基變數,則可以將其從約束條件和目標函式中直接去掉。否則,需要任取一個非基變數formula_4執行pivot(0, e),將formula_4變為非基變數。由於此時formula_4是基變數且formula_59,故formula_59一定成立,因此這個轉軸操作不會破壞b向量的非負性。

  在採用Bland's法則選擇用於轉軸操作的d和e(相同值的情況下取字典序最小)之後,可以證明單純形法一定能夠在有限步之後終止,但是最壞情況演算法的時間複雜度為指數級別的,而且可以構造出讓單純形法的時間複雜度達到指數級別的具體例項。不過實踐證明在絕大多數情況下單純形法的效率非常令人滿意。  單純形法的最壞時間複雜度為指數級別,並不意味著線性規劃不存在多項式級別的演算法。橢球演算法和內點演算法均為解決線性規劃的多項式時間演算法。
單純形法(simplex algorithm)在數學優化領域中常用於線性規劃問題的數值求解,由喬治·伯納德·丹齊格發明。