第四部分線性規(guī)劃模型

1、第四部分線性規(guī)劃模型14.1 線性規(guī)劃問題 在20世紀(jì)30年代未，蘇聯(lián)數(shù)學(xué)家康托洛維奇首先提出了線性規(guī)劃模型，并于1947年由美國人丹捷格提出了線性規(guī)劃的單純形算法，較好地解決了線性規(guī)劃的求解問題，從而奠定了線性規(guī)劃作為一個(gè)學(xué)科的基石。 隨著計(jì)算技術(shù)的不斷發(fā)展，使成千上萬個(gè)約束條件和決策變量的線性規(guī)劃問題能夠迅速地求解，為線性規(guī)劃在經(jīng)濟(jì)等各領(lǐng)域的廣泛應(yīng)用創(chuàng)造了有利的條件。 1 線性規(guī)劃的研究對象(1) 在現(xiàn)有的資源條件下，研究如何合理地計(jì) 劃、安排，可使某一目標(biāo) 達(dá)到最大化；(2) 在任務(wù)確定后，研究如何合理地計(jì)劃、排， 用最低限度的人、財(cái)?shù)荣Y源, 去實(shí)現(xiàn)任務(wù)。說明：線性規(guī)劃中研究的問題要求目

2、標(biāo)函數(shù)與約束 條件函數(shù)均是線性的，或者說或以轉(zhuǎn)化為線性的。2 線性規(guī)劃建模型的過程(1) 理解需要解決的問題, 明確模型條件 以及要達(dá)到的目標(biāo)；(2) 針對問題定義一組決策變量, 用 x =(x1, x2, , xn)T 表示某一方案。 這組決策變量的值就代表一個(gè)具體方案, 通常這些變量的取值是非負(fù)的;(3) 用決策變量的線性函數(shù)形式表示出所要尋找求的目標(biāo),稱為目標(biāo)函數(shù)。按問題的不同,要求目標(biāo)函數(shù)在滿足約束條件下實(shí)現(xiàn)最大化或最小化；(4) 用一組含有決策變量的等式或不等式來表示在解決問題的過程中所必須遵循的約束條件。滿足以上條件(2)、(3)、(4) 的數(shù)學(xué)模 型稱為線性規(guī)劃的數(shù)學(xué)模型, 一般

3、形式為：max(min) z = c1x1+c2x2+cnxn約束條件：a11x1+ a12 x2+ +a1n xn (=, ) b1 ;a21x1+ a22 x2+ +a2n xn (=, ) b2 ; am1x1+ am2 x2+ +amn xn(=, ) bm. z = c1x1+c2x2+cnxn 稱為目標(biāo)函數(shù), 其中cj ( j =1, 2, n ) 稱為價(jià)值系數(shù), c = (c1, c2 , cn)T, 稱為價(jià)值向量, xj ( j =1, 2, , n)為求解的變量。由系數(shù)組成的矩陣：稱為約束矩陣； 列向量 b = (b1,b2, ,bn )T : 為右端向量；條件 xj 0 (

4、j=1,2, ,n ) : 非負(fù)約束；一個(gè)向量x = (x1,x2, ,xn )T滿足約束條件, 稱為可行解或可行點(diǎn)，全部可行點(diǎn)的集合稱為可行區(qū)域, 記為D。 使得目標(biāo)函數(shù)值最大化或最小化的可行解稱為該 線性規(guī)劃的最優(yōu)解，此目標(biāo)函數(shù)值稱為最優(yōu)目標(biāo)函數(shù)值，簡稱最優(yōu)值。4.2.1 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題： 在一組線性的等式或不等式的約束之下，求一個(gè)線性函數(shù)的最大值或最小值的問題，其標(biāo)準(zhǔn)形式為：簡寫為用矩陣形式表示為4.2.2 線性規(guī)劃問題解的概念 設(shè) A是約束方程組 m n 維的系數(shù)矩陣, 其秩為 m, B 是矩陣 A 中mm 階非奇異子陣(即| B |0 ), 則稱 B 是線性規(guī)劃問

5、題的一個(gè)基。一般地，設(shè) 稱 aj 是基向量，它是一個(gè)線性無關(guān)的向量組，與基向量 aj 對應(yīng)的變量 xj 稱為基變量，其余變量稱為非基變量?；蛄炕兞糠腔蛄糠腔兞咳艏s束方程組 (2) 中的系數(shù)矩陣的秩為 m, 由 m=18MON) XMON+XTHU+XFRI+XSAT+XSUN=16TUE) XMON+XTUE+XFRI+XSAT+XSUN=15WED) XMON+XTUE+XWED+XSAT+XSUN=16THU) XMON+XTUE+XWED+XTHU+XSUN=19FRI) XMON+XTUE+XWED+XTHU+XFRI=14SAT) XTUE+XWED+XTHU+XSUN+XS

6、AT=12END例5 某個(gè)中型百貨商場對售貨人員的需求量經(jīng)過統(tǒng)計(jì)分析后，得到如表1.2所示數(shù)據(jù)。為了保證銷售人員的充分休息，售貨人員每周工作五天，并連續(xù)休息兩天。問應(yīng)該如何安排售貨人員的作息時(shí)間，既能滿足需要，又使配備的售貨人員的數(shù)量最少？時(shí) 間所需售貨人員數(shù)量時(shí) 間所需售貨人員數(shù)量星期日星期一星期二星期三28152425星期四星期五星期六193128表1.2解：由于每個(gè)售貨員都要工作五天，休z = x1+x2+ +x7 (10)息兩天，因此只要計(jì)算出連續(xù)休息兩天的售貨員的人數(shù)，也就確定了售貨員的總?cè)藬?shù)。 設(shè)周一開始休息的人數(shù)為 x1, 周二開始休息人數(shù)為 x2, , 周日開始休息的人數(shù)為 x

7、7, 則由于除了在周六和周日休息的人員 x1+x2+x3 + x4+x5 28之外其余的售貨員均應(yīng)該工作，因此，同理，有x2 + x3+ x4 +x5+x6 15x3+ x4+x5+ x6+x7 24x4 + x5+x6 + x7+x1 25x5+x6+x7 + x1+x2 19x6+x7 + x1+x2+x3 31x7 +x1+x2+x3+x4 28 xi 0，i=1,2, ,7.用 Lindo 軟件計(jì)算可得： x1=12, x2=0, x3= 11, x4=5, x5= 0, x6 = 8, x7=0每周的至少需要配備 36 個(gè)售貨員，并如下安排休息人數(shù)：星期一、二： 12 人；星期三、四

8、： 11 人；星期五： 5 人;星期六、日： 8 人。MIN 100 XMON+100 XTUE+100 XWED+ 100 XTHU+100 XFRI+100 XSAT+100 XSUNSUBJECT TOSUN) XWED+XTHU+XFRI+XSAT+XSUN=24MON) XMON+XTHU+XFRI+XSAT+XSUN=25TUE) XMON+XTUE+XFRI+XSAT+XSUN=19WED) XMON+XTUE+XWED+XSAT+XSUN=31THU) XMON+XTUE+XWED+XTHU+XSUN=28FRI) XMON+XTUE+XWED+XTHU+XFRI=28SAT)

9、 XTUE+XWED+XTHU+XSUN+XSAT=15END例6 制造某種產(chǎn)品需要A、B、C三種配件，其規(guī)格與數(shù)量如表1.3示。各類配件都用5.5米長的同一種圓鋼生產(chǎn)。若計(jì)劃生產(chǎn)100套產(chǎn)品，最少需要多少根圓鋼？配件類型規(guī)格長度(米)每件產(chǎn)品所需配件數(shù)量ABC3.12.11.2124表1.3解：確定每根圓鋼截成A、B、C三種配截法一根圓鋼所截各類配件數(shù)量產(chǎn)品需要數(shù)量類型12345A(3.1)B(2.1)C(1.2)1100 010210 02124100200400 余料j(米)0.3 0 0.1 1 0.7件的具 體下料方式，即確定余料長度 j1.2米的各種下料方式：問題轉(zhuǎn)化為： 采用上述

10、五種截法，需要多少根圓鋼才能生產(chǎn)100件產(chǎn)品，且使總下料根數(shù)最少？min z= x1+x2 + x3+ x4 +x5s.t.解: 設(shè)按第 j 種截法下料 xj ( j =1,2,3,4,5)根, 則有x1+x2 100 x1 +2x3+x4 200 2x2+ x3+2x4+4x5 400 x1, x2, x3, x4, x5 0用 Lindo 軟件計(jì)算可得： x*（0, 100, 100, 0, 25)T, z*=225.具體下料方式為：截法2、3： 100根；截法5： 25根； 需要用某種原料下 m 種零件 A1, A2, Am 的毛坯材料。根據(jù)既省材料又易于現(xiàn)場操作的原則，在一根原材料上已

11、經(jīng)設(shè)計(jì)出 m 種不同的小料方式，其中第 j 種方式可下得 Ai 零件 aij 個(gè)。若 Ai 零件的需要量為 bi, 則應(yīng)該如何下料，才能使既滿足需要又使所用的原材料最少？一般(一維)下料問題：解：設(shè)按第 j 種截法下料 xj( j =1,2,n)根,所用原材料總數(shù)為 z 件, 則配料問題要用n種原料 A1, A2, , Am 配制成具有 m種成份 B1, B2, , Bm 的某種產(chǎn)品，規(guī)定每一單位的產(chǎn)品所含Bi成分的數(shù)量不低于bi( i=1,2,m)。 原料 Aj 的單價(jià)為cj, 現(xiàn)有數(shù)量為 dj, 而每一單位Aj原料所含Bi成分的數(shù)量為aij (i =1,2,m, j =1,2,n). 若要

12、求釀成的產(chǎn)品的產(chǎn)品數(shù)量不低于t, 則應(yīng)該如何配料, 才能使既滿足需要又使總成本 最少？設(shè)所取原料Aj 的數(shù)量為xj , 原料總成本為 z, 則配成品的總量為所含Bi成分的數(shù)量則有則問題的線性規(guī)劃(LP)模型為：例7 某化工廠要用三種原料I, II,III 混合配制三種不同規(guī)格的產(chǎn)品A,B,C。各產(chǎn)品的規(guī)格、單價(jià)如表1.4所示，各原料的單價(jià)及每天最大供應(yīng)量如表1.5所示，則該廠應(yīng)該如何安排生產(chǎn)才能使利潤本最大？產(chǎn)品規(guī)格 單價(jià)(元/千克)A原料I不少于 50% 50 原料II不超過 25%B原料I不少于 25% 35 原料II不超過 50% C 不限 25 產(chǎn)品最大供應(yīng)量(千克/天) 單價(jià)(元/千

13、克)I 100 50II 100 25III 60 35解:1.確定決策變量設(shè)用 xij 表示第 i 種產(chǎn)品的日產(chǎn)量(千克)中所含第 j 種原料的數(shù)量, 具體關(guān)系如下: jiI II IIIABCx11 x12 x13x21 x22 x23x31 x23 x332.確定約束條件: (1) 規(guī)格約束：整理，得： (2) 資源約束：3.目標(biāo)函數(shù)(1) 產(chǎn)品的總產(chǎn)值：產(chǎn)品 A 的產(chǎn)值：產(chǎn)品 B 的產(chǎn)值：產(chǎn)品 C 的產(chǎn)值：(2) 產(chǎn)品的總成本：產(chǎn)品 A 的成本：產(chǎn)品 B 的成本：產(chǎn)品 C 的成本：因此，目標(biāo)函數(shù)為：因此，問題的LP模型為：用 Lindo 軟件計(jì)算可得：x11=100, x12=50, x13=50, x21= x22=x23 =x31= x32x33 0 每天只生產(chǎn) A 產(chǎn)品 200 千克，分別用 I 原料 100千克和 II、III 原