線性規(guī)劃(Ⅱncar Pr0gramming,LP)是運(yùn)籌學(xué)的一個(gè)重要分支,自1947年丹捷格提出一般線性規(guī)劃問(wèn)題求解的單純形法之后,線性規(guī)劃在理論上趨于成熟。21世紀(jì)初期,一些學(xué)者開始使用線性規(guī)劃求解集束型裝備調(diào)度問(wèn)題。FBMH1608HL221-T

   線性規(guī)劃所研究的問(wèn)題是:在一定條件下,合理安排人力、物力等資源,使經(jīng)濟(jì)效果達(dá)到最好。一般地,要解決的是求解線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問(wèn)題。

   線性規(guī)劃方法有兩種:單純形法和對(duì)偶單純形法。

   單純形法

   適合求解的問(wèn)題:約束條件全部為“≤”,右邊常數(shù)全部為非負(fù),對(duì)目標(biāo)函數(shù)的系數(shù)沒有要求。例如:

   求解步驟如下。

   第一步:將線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)化。

   第二步:判斷是否有明顯的初始基礎(chǔ)可行解,如果有∫轉(zhuǎn)第四步,否則轉(zhuǎn)第三步。

   第三步:構(gòu)造輔助問(wèn)題,用兩階段法求解輔助問(wèn)題。如果輔助問(wèn)題最優(yōu)解的目標(biāo)函數(shù)大于0,原問(wèn)題沒有可行解,算法終止,否則轉(zhuǎn)第四步。

   第四步:寫出單純形表,將基變量在約束條件下的系數(shù)消為單位矩陣,將基變量在目標(biāo)函數(shù)中的系數(shù)消為0,轉(zhuǎn)至第五步。

   第五步:如果所有非基變量的檢驗(yàn)數(shù)全為負(fù)數(shù)或0,則已獲得最優(yōu)解,算法終止,否則選擇檢驗(yàn)數(shù)為正數(shù),并且選擇絕對(duì)值最大的非基變量為進(jìn)基變量,轉(zhuǎn)第六步。

   第六步:如果進(jìn)基變量在約束條件中的系數(shù)全為負(fù)數(shù)或0,目標(biāo)函數(shù)無(wú)界,算法終止,否則根據(jù)右邊常數(shù)和正的系數(shù)的最小比值確定離基變量,轉(zhuǎn)第七步。

   第七步:進(jìn)基變量列和離基變量行交叉的元素稱為主元。對(duì)單純表進(jìn)行變換,將主元變?yōu)?,將主元所有列的其他元素變?yōu)?,轉(zhuǎn)第五步。