初軋和鋼坯軋製

[拼音]：xianxing guihua

[英文]：linear programming

研究線性約束條件下線性目標函式的極值問題的數學理論和方法，英文縮寫LP。它是運籌學的一個重要分支，廣泛應用於軍事作戰、經濟分析、經營管理和工程技術等方面。為合理地利用有限的人力、物力、財力等資源作出的最優決策，提供科學的依據。

發展簡史

法國數學家 J.- B.- J.傅立葉和 C.瓦萊－普森分別於1832和1911年獨立地提出線性規劃的想法，但未引起注意。1939年蘇聯數學家Л.В.康託羅維奇在《生產組織與計劃中的數學方法》一書中提出線性規劃問題，也未引起重視。1947年美國數學家G.B.丹齊克提出線性規劃的一般數學模型和求解線性規劃問題的通用方法──單純形法，為這門學科奠定了基礎。1947年美國數學家J.von諾伊曼提出對偶理論,開創了線性規劃的許多新的研究領域，擴大了它的應用範圍和解題能力。1951年美國經濟學家T.C.庫普曼斯把線性規劃應用到經濟領域，為此與康託羅維奇一起獲1975年諾貝爾經濟學獎。50年代後對線性規劃進行大量的理論研究，並湧現出一大批新的演算法。例如，1954年C.萊姆基提出對偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規劃的靈敏度分析和引數規劃問題，1956年A.塔克提出互補鬆弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解演算法等。線性規劃的研究成果還直接推動了其他數學規劃問題包括整數規劃、隨機規劃和非線性規劃的演算法研究。由於數位電子計算機的發展，出現了許多線性規劃軟體，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變數的線性規劃問題。1979年蘇聯數學家Л.Г.哈奇揚提出解線性規劃問題的橢球演算法，並證明它是多項式時間演算法。1984年美國貝爾電話實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間演算法。用這種方法求解線性規劃問題在變數個數為5000時只要單純形法所用時間的1/50。現已形成線性規劃多項式演算法理論。50年代後線性規劃的應用範圍不斷擴大。

數學模型

要對實際規劃問題作定量分析，必須先加以抽象，建立數學模型。在建立線性規劃模型時，需要有關的專業知識，並要有一定的經驗和技巧。建立線性規劃模型包括：

（1）明確問題的目標和劃定決策實施的範圍（包括時間界限），並將目標表達成決策變數的線性函式，稱為目標函式。

（2）選定決策變數和引數。決策變數就是待決定的問題的未知量，一組決策變數的取值即構成一個規劃方案。決策變數的選定往往需要對問題進行仔細的分析。

（3）建立約束條件。問題的各種限制條件稱為約束條件。每一個約束條件均表達成決策變數的線性函式應滿足的等式或不等式。約束條件往往不止一個，通常表達成一組線性等式或不等式。線性規劃問題就是在決策變數滿足一組約束條件的情況下使目標函式達到極大值或極小值。

一般線性規劃模型的形式為：

max(或min)

s.t.

(≤,＝或≥)bi

(i=1,2,…,m)

xj≥0 (j=1,n)

式中max表示求極大值；min表示求極小值；s.t.表示受約束於或約束條件是;Z為目標函式;xj為決策變數；aij，bi和cj分別為消耗係數、需求係數和收益係數,在具體的線性規劃問題中具有不同的經濟學意義，一般都是已知實數。在線性規劃中滿足約束條件的一組數(x1,x2,xn)稱為問題的一個可行解,全體可行解構成的集合稱為問題的可行域。在可行域上使目標函式取得極大值（或極小值）的可行解稱為問題的最優解，對應的目標函式值稱為最優值。

解題演算法

求解線性規劃問題的基本方法是單純形法，現在已有單純形法的標準軟體，可在電子計算機上求解約束條件和決策變數數達 10000個以上的線性規劃問題。為了提高解題速度，又有改進單純形法、對偶單純形法、原始對偶方法、分解演算法和各種多項式時間演算法。對於只有兩個變數的簡單的線性規劃問題，也可採用圖解法求解。這種方法僅適用於只有兩個變數的線性規劃問題。它的特點是直觀而易於理解，但實用價值不大。通過圖解法求解可以理解線性規劃的一些基本概念。

例如，某工廠生產A，B兩種產品,已知生產A1千克，耗煤9噸，耗電4千瓦，用勞力3個工；生產B1千克，耗煤4噸，耗電5千瓦，用勞力10個工。已知生產1千克A的利潤是500元，生產1千克B的利潤是900元。現根據工廠條件，只能提供煤360噸，電力200千瓦,勞力300個工。問如何安排兩種產品的生產量，才能使總的利潤最大。

設A，B 的產量分別為x1，x2（千克）,則上述問題的線性規劃模型是：

maxZ＝5x1＋9x2

s.t.9x1＋4x2≤360

4x1＋5x2≤200

3x1＋10x2≤300

x1≥0，x2≥0

此問題的可行域為圖中的多邊形區域，即陰影部分。目標函式的等值線為平行於直線 l的平行直線族。將直線l向右上方平行移動，對應的目標函式值逐漸增大,在即將脫離可行域之際，它與可行域的交點便對應於問題的最優解。由此可知,在可行域的頂點B 處,目標函式達到最大值。因此,問題的最優解為:x1＝20千克,x2＝24千克，最大總利潤為3.16萬元。