線性規劃方法

線性規劃方法是在第二次世界大戰中發展起來的一種重要的數量方法,線性規劃方法是企業進行總產量計畫時常用的一種定量方法。

線性規劃,數學模型,問題,適用性,一般解法,

線性規劃

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

數學模型

式中,
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行滿秩。
規劃問題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行滿秩。

相關詞條

熱門詞條

聯絡我們