Can you summarize the following document?
        
  描述線性規劃問題的常用和最直觀形式是標準型。標準型包括以下三個部分:  線性規劃問題通常可以用矩陣形式表達成:  其他型別的問題,例如極小化問題,不同形式的約束問題,和有負變數的問題,都可以改寫成其等價問題的標準型。

  以下是一個線性規劃的例子。假設一個農夫有一塊formula_9平方千米的農地,打算種植小麥或大麥,或是兩者依某一比例混合種植。該農夫只可以使用有限數量的肥料formula_10和農藥formula_11,而單位面積的小麥和大麥都需要不同數量的肥料和農藥,小麥以formula_12表示,大麥以formula_13表示。設小麥和大麥的售出價格分別為formula_14和formula_15,則小麥與大麥的種植面積問題可以表示為以下的線性規劃問題:

  在用單純型法求解線性規劃問題之前,必須先把線性規劃問題轉換成增廣矩陣形式。增廣矩陣形式引入非負鬆弛變數將不等式約束變成等式約束。問題就可以寫成以下形式: 這裡formula_19是新引入的鬆弛變數, formula_16需要極大化的變數。

  以上例子的轉換成增廣矩陣: 這裡formula_21,是(非負)鬆弛變數。  寫成矩陣形式:

  每個線性規劃問題,稱為原問題,都可以變換為一個對偶問題。我們可將“原問題”表達成矩陣形式:  而相應的對偶問題就可以表達成以下矩陣形式:  這裡用formula_28來作為未知向量。

  上述線性規劃例子的對偶問題:  假如有一個種植園主缺少肥料和農藥,他希望同這個農夫談判付給農夫肥料和農藥的價格。可以構造一個數學模型來研究如何既使得農夫覺得有利可圖肯把肥料和農藥的資源賣給他,又使得自己支付的金額最少?  問題可以表述如下  假設formula_29分別表示每單位肥料和農藥的價格,則所支付租金最小的目標函式可以表示為

  幾何上,線性約束條件的集合相當於一個凸包或凸集,叫做可行域。因為目標函式亦是線性的,所以其極值點會自動成為最值點。線性目標函式亦暗示其最優解只會出現在其可行域的邊界點中。  在兩種情況下線性規劃問題沒有最優解。其中一種是在約束條件相互矛盾的情況下(例如formula_30和formula_31),其可行域將會變成空集,問題沒有解,因此亦沒有最優解。在這種情況下,該線性規劃問題會被稱之為「不可行」。  另一種情況是,約束條件的多面體可以在目標函式的方向無界(例如:formula_32),目標函式可以取得任意大的數值,所以沒有最優解。  除了以上兩種病態的情況以外(問題通常都會受到資源的限制,如上面的例子),最優解永遠都能夠在多面體的頂點中取得。但最優解未必是唯一的:有可能出現一組最優解,覆蓋多面體的一條邊、一個面、甚至是整個多面體(最後一種情況會在目標函式只能等於0的情況下出現)。

  單純形演算法利用多面體的頂點構造一個可能的解,然後沿著多面體的邊走到目標函式值更高的另一個頂點,直至到達最優解為止。雖然這個演算法在實際上很有效率,在小心處理可能出現的「迴圈」的情況下,可以保證找到最優解,但它的最壞情況可以很壞:可以構築一個線性規劃問題,單純形演算法需要問題大小的指數倍的執行時間才能將之解出。事實上,有一段時期內人們曾不能確定線性規劃問題是NP完全問題還是可以在多項式時間裡解出的問題。  第一個在最壞情況具有多項式時間複雜度的線性規劃演算法在1979年由前蘇聯數學家Leonid Khachiyan提出。這個演算法建基於非線性規劃中Naum Shor發明的橢球法(ellip-soid method),該法又是Arkadi Nemirovski(2003年馮‧諾伊曼運籌學理論獎得主)和 D. Yudin的凸集最優化橢球法的一般化。  理論上,「橢球法」在最惡劣的情況下所需要的計算量要比「單形法」增長的緩慢,有希望用之解決超大型線性規劃問題。但在實際應用上,Khachiyan的演算法令人失望:一般來說,單純形演算法比它更有效率。它的重要性在於鼓勵了對內點演算法的研究。內點演算法是針對單形法的「邊界趨近」觀念而改採「內部逼近」的路線,相對於只沿著可行域的邊沿進行移動的單純形演算法,內點演算法能夠在可行域內移動。  1984年,貝爾實驗室印度裔數學家卡馬卡(Narendra Karmarkar)提出了投影尺度法(又名Karmarkar's algorithm)。這是第一個在理論上和實際上都表現良好的演算法:它的最壞情況僅為多項式時間,且在實際問題中它比單純形演算法有顯著的效率提升。自此之後,很多內點演算法被提出來並進行分析。一個常見的內點演算法為Mehrotra predictor-corrector method。儘管在理論上對它所知甚少,在實際應用中它卻表現出色。  單形法沿著邊界由一個頂點移動到「相鄰」的頂點,內點演算法每一步的移動考量較周詳,「跨過可行解集合的內部」去逼近最佳解。當今的觀點是:對於線性規劃的日常應用問題而言,如果演算法的實現良好,基於單純形法和內點法的演算法之間的效率沒有太大差別,只有在超大型線性規劃中,頂點幾成天文數字,內點法有機會領先單形法。  線性規劃的求解程式在各種各樣的工業最優化問題裡被廣泛使用,例如運輸網路的流量的最優化問題,其中很多都可以不太困難地被轉換成線性規劃問題。  線性規劃理論中存在幾個尚未解決的問題,這些開放問題的答案將會是數學運算中的根本突破,並且很可能是我們解決大規模線性規劃問題的主要進展。  這些問題已經由斯蒂芬·斯梅爾在二十一世紀十八個尚未解決的最偉大的問題中應用。用斯梅爾的話來說,“第三個問題是線性規劃理論中最主要的尚未解決的問題”。然而,對於線性規劃問題存在弱多項式時間演算法,比如橢球演算法和內點演算法,尚未發現限制在約束條件個數和變數個數的強多項式時間演算法,此演算法的發展將會帶來理論上重大意義,或者是解決大規模線性規劃上的實際收益。

  要求所有的未知量都為整數的線性規劃問題叫做整數規劃(integer programming, IP)或整數線性規劃(integer linear programming, ILP)問題。相對於即使在最壞情況下也能有效率地解出的線性規劃問題,整數規劃問題的最壞情況是不確定的,在某些實際情況中(有約束變數的那些)為NP困難問題。  0-1整數規劃是整數規劃的特殊情況,所有的變數都要是0或1(而非任意整數)。這類問題亦被分類為NP困難問題。  只要求當中某幾個未知數為整數的線性規劃問題叫做混合整數規劃(mixed integer programming, MIP)問題。這類問題通常亦被分類為NP困難問題。  存在著幾類IP和MIP的子問題,它們可以被有效率地解出,最值得注意的一類是具有完全單位模約束矩陣,和約束條件的右邊全為整數的一類。  一個解決大型整數線性規劃問題的先進演算法為delayed column generation。

  求解軟體包
在數學中,線性規劃(Linear Programming,簡稱LP)特指目標函式和約束條件皆為線性的最優化問題。