線性規劃方法

線性規劃是運籌學的一個最重要的分支，理論上最完善，實際應用得最廣泛。主要用於研究有限資源的最佳分配問題，即如何對有限的資源作出最佳方式地調配和最有利地使用，以便最充分地發揮資源的效能去獲取最佳的經濟效益。由於有成熟的計算機應用軟件的支持，採用線性規劃模型安排生產計劃，並不是一件困難的事情。在總體計劃中，用線性規劃模型解決問題的思路是，在有限的生產資源和市場需求條件約束下，求利潤最大的總產量計劃。該方法的最大優點是可以處理多品種問題。

目標函數：

式中，

xi--i產品的計劃產量；

aik--每生產一個i產品所需k種資源的數量；

bk--第k種資源的擁有量；

Ui--i產品的最高需求量；

Li--i產品的最低需求量；

pi--i產品的單價；

ci--i產品的單位成本。

1、線性規劃模型考慮的因素可能不全面，實際中有些情況沒有被考慮到，這就使得線性規劃模型過於理想化；

2、實際運用線性規劃模型時，雖然一些因素或約束條件被考慮到了，但是由於這些因素或約束條件不易量化或求得（如進行總生產計劃常需考慮到的能源單耗就不易求得）時，線性規劃模型的運用和有效性因而受到了一定的限制；

3、對一些基礎管理不善的企業而言，模型中的單位產品資源消耗係數a很難得到；

4、目標函數中的產為成本系數c實際上是個變量，他隨計劃的數量結構和品種結構而變。這些問題給機械行業應用線性規劃模型帶來許多困難，如處理不好，求得的結果的可靠性會很低的。

線性規劃模型用在原材料單一、生產過程穩定不變、分解型生產類型的企業是十分有效的，如石油化工廠等。對於產品結構簡單、工藝路線短、或者零件加工企業，有較大的應用價值。需要注意的是，對於機電類企業用線性規劃模型只適用於作年度的總生產計劃，而不宜用來做月度計劃。這主要與工件在設備上的排序有關，計劃期太短，很難安排過來。

對於一般線性規劃問題：

Min z=CX

S.T.

AX =b

X>=0

其中A為一個m*n矩陣。

若A行滿秩

則可以找到基矩陣B，並尋找初始基解。

用N表示對應於B的非基矩陣。則規劃問題1可化為：

規劃問題2：

Min z=CB XB+CNXN

S.T.

B XB+N XN = b (1)

XB >= 0, XN >= 0 (2)

(1)兩邊同乘於B-1，得

XB + B-1 N XN = B-1 b

同時，由上式得XB = B-1 b - B-1 N XN，也代入目標函數，問題可以繼續化為：

規劃問題3：

Min z=CB B-1 b + ( CN - CB B-1 N ) XN

S.T.

XB+B-1N XN = B-1 b (1)

XB >= 0, XN >= 0 (2)

令N:=B-1N，b:= B-1 b，ζ= CB B-1b，σ= CN - CB B-1 N，則上述問題化為規劃問題形式4：

Min z= ζ + σ XN

S.T.

XB+ N XN = b (1)

XB >= 0, XN >= 0 (2)

在上述變換中，若能找到規劃問題形式4，使得b>=0，稱該形式為初始基解形式。

上述的變換相當於對整個擴展矩陣（包含C及A） 乘以增廣矩陣。所以重在選擇B，從而找出對應的CB。

若存在初始基解

若σ>= 0

則z >=ζ。同時，令XN = 0，XB = b，這是一個可行解，且此時z=ζ，即達到最優值。所以，此時可以得到最優解。

若σ >= 0不成立

可以採用單純形表變換。

σ中存在分量<0。這些負分量對應的決策變量編號中，最小的為j。N中與j對應的列向量為Pj。

若Pj <=0不成立

則Pj至少存在一個分量ai，j為正。在規劃問題4的約束條件（1）的兩邊乘以矩陣T。

T=

則變換後，決策變量xj成為基變量，替換掉原來的那個基變量。為使得T b >= 0，且T Pj=ei（其中，ei表示第i個單位向量），需要：

l ai，j>0。

l βq+βi*(-aq,j/ai,j)>=0，其中q!=i。即βq>=βi/ ai,j * aq,j。

n 若aq,j<=0，上式一定成立。

n 若aq,j>0，則需要βq / aq,j >=βi/ ai,j。因此，要選擇i使得βi/ ai,j最小。

如果這種方法確定了多個下標，選擇下標最小的一個。

轉換後得到規劃問題4的形式，繼續對σ進行判斷。由於基解是有限個，因此，一定可以在有限步跳出該循環。

若對於每一個i，ai,j<=0

最優值無界。

若不能尋找到初始基解

無解。

若A不是行滿秩

化簡直到A行滿秩，轉到若A行滿秩。