1、數(shù)學(xué)實(shí)驗(yàn),第十章,線性規(guī)劃,10. 1 引例,如果每天可供使用的勞動(dòng)力為150h，可供生產(chǎn)的原材料為200kg，試制定生產(chǎn)計(jì)劃使總利潤(rùn)最大，并求各種產(chǎn)品的日產(chǎn)量。,引例1 已知某工廠利用兩種資源勞動(dòng)力和原材料生產(chǎn)A、B、C三種產(chǎn)品的數(shù)據(jù)如下：,1. 問題分析,設(shè)xA，xB，xC分別表示 A，B，C三種產(chǎn)品的日 產(chǎn)量，由已知數(shù)據(jù)可得,7xA+3xB+6xC150 (1),4xA+4xB+5xC200 (2),xA，xB，xC0 (3),z=4xA+2xB+3xC,2. 模型建立,顯然，滿足條件(1),(2)和(3)的變量xA, xB, xC的取值可以有多種方法。而工廠的目標(biāo)是在不超過所有資源限量

2、的條件下，得到最大的利潤(rùn)，即使目標(biāo)函數(shù)z具有最大值。因此問題變成： 求xA, xB, xC ，使得,max z=4xA+2xB+3xC s.t. 7xA+3xB+6xC150 4xA+4xB+5xC200 xA，xB，xC0,引例2 某廣告公司想在電視、廣播和雜志上做廣告，其目的是盡可能多地招攬顧客。已知市場(chǎng)調(diào)查的結(jié)果如下：,廣告公司的期望,1. 廣告的總費(fèi)用不超過800(千元) 2. 要達(dá)到以下效果： (1)至少要有200萬(wàn)婦女收看廣告； (2)電視廣告費(fèi)用不超過500(千元)； (3)電視廣告白天至少播出3次，最佳時(shí)間至少播出2次； (4)通過廣播、雜志做的廣告要重復(fù)5到10次。,總廣告經(jīng)

3、費(fèi)的約束條件,1. 問題分析,受廣告影響的女顧客數(shù)的約束條件,電視廣告的約束條件,廣播和雜志廣告的約束條件,受廣告影響的顧客的總數(shù),40 x1+75x2+30 x3+15x4800(總經(jīng)費(fèi)),設(shè)x1,x2,x3,x4分別表示 白天電視、最佳時(shí)間 電視、廣播、雜志廣 告次數(shù)，則,300 x1+400 x2+200 x3+100 x42000(女顧客數(shù)),40 x1+75x2500，x13，x22(電視),z=400 x1+900 x2+500 x3+200 x4 (總?cè)藬?shù)),5x310，5x410(廣播雜志),2. 模型建立,由問題分析可知引例2的問題變成：求x1,x2,x3,x4 使得,max

4、 z=400 x1+900 x2+500 x3+200 x4,s.t. 40 x1+75x2+30 x3+15x4800 300 x1+400 x2+200 x3+100 x42000 40 x1+75x2500 3 x1 2 x2 5 x310 5 x410,引例3 某公司經(jīng)銷某種產(chǎn)品，三個(gè)產(chǎn)地和四個(gè)銷地的產(chǎn)量、銷量、單位運(yùn)價(jià)如下表所示。問在保證產(chǎn)銷平衡的條件下，如何調(diào)運(yùn)可使總運(yùn)費(fèi)最少？,1. 問題分析,設(shè)xij(i=1,2,3;j=1,2,3,4)為從產(chǎn)地Ai運(yùn)到銷地Bj的運(yùn)量,產(chǎn)量約束,銷量約束,2. 模型建立,設(shè)cij(i=1,2,3;j=1,2,3,4)為從產(chǎn)地Ai運(yùn)到銷地Bj的運(yùn)費(fèi)

5、，則問題變成：求xij 使得,min z= cij xij,s.t. x11+x12+x13+x14=60 x21+x22+x23+x24=40 x31+x32+x33+x34=60 x11+x21+x31 =30 x12+x22+x32 =50 x13+x23+x33 =40 x14+x24+x34 =40 xij0 (i=1,2,3;j=1,2,3,4),10. 2 線性規(guī)劃模型,上述幾例所提出的問題，可歸結(jié)為在變量滿足線性約束條件下，求使線性目標(biāo)函數(shù)值最大或最小的問題。它們具有共同的特征: 每個(gè)問題都可用一組決策變量(x1,x2,xn)表示某一方案，其具體的值就代表一個(gè)具體方案。通常可根

6、據(jù)決策變量所代表的事物特點(diǎn)，可對(duì)變量的取值加以約束，如非負(fù)約束。 存在一組線性等式或不等式的約束條件。 都有一個(gè)用決策變量的線性函數(shù)作為決策目標(biāo)(即目標(biāo)函數(shù))，按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。,線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，它所研究的問題主要有兩類： 任務(wù)確定后，如何統(tǒng)籌安排，盡量做到用最少的人力物力資源去完成這一任務(wù)； 已有一定數(shù)量的人力物力資源，如何安排使用它們，使得完成任務(wù)最多。,求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值問題稱為線性規(guī)劃問題,線性規(guī)劃問題,線性規(guī)劃的主要應(yīng)用領(lǐng)域,生產(chǎn)計(jì)劃制定(合理下料，配料，“生產(chǎn)計(jì)劃、庫(kù)存、勞力綜合”) 市場(chǎng)營(yíng)銷(廣告預(yù)算和媒介選

7、擇，競(jìng)爭(zhēng)性定價(jià)，新產(chǎn)品開發(fā)，制定銷售計(jì)劃) 庫(kù)存管理(合理物資庫(kù)存量, 停車場(chǎng)大小, 設(shè)備容量) 運(yùn)輸問題 財(cái)政、會(huì)計(jì)(預(yù)算, 貸款, 成本分析, 投資, 證券管理) 人事(人員分配, 人才評(píng)價(jià), 工資和獎(jiǎng)金的確定) 設(shè)備管理(維修計(jì)劃, 設(shè)備更新) 城市管理(供水, 污水管理, 服務(wù)系統(tǒng)設(shè)計(jì)、運(yùn)用),線性規(guī)劃的數(shù)學(xué)模型,一般形式,Max(Min) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn(=,)b1 a21x1+a22x2+a2nxn(=,)b2 am1x1+am2x2+amnxn(=,)bm x1 ，x2 ， ，xn 0,(z:目標(biāo)函數(shù)),線性規(guī)劃的數(shù)

8、學(xué)模型,矩陣形式,max(min) z=cTx s.t. Ax(=,)b x0,線性規(guī)劃模型的實(shí)用形式,min z=c1x1+c2x2+cnxn s.t. a11x1+ a12x2+ a1nxn=b1 a21x1+ a22x2+ a2nxn=b2 ak1x1+ ak2x2+ aknxn=bk ak+11x1+ak+12x2+ak+1nxnb k+1 am1x1+ am2x2+ amnxnbm lixiui (i=1,2,n),(目標(biāo)函數(shù)極小化),(決策變量上下界約束),線性規(guī)劃模型的實(shí)用形式的矩陣表示,min z=cTx s.t. A1x=B1 A2xB2 LxU,矩陣分塊的MATLAB實(shí)現(xiàn)

9、A1=A(1:k,:) ; A2=A(k+1:m,:) B1=b(1:k) ; B2=b(k+1:m) L=l1 l2 lnT; U=u1 u2 unT,10. 3 有關(guān)線性規(guī)劃解的概念,1.可行解: 滿足全部約束條件的決策向量x(Rn) 2.可行域: 全部可行解構(gòu)成的集合 3.最優(yōu)解: 使目標(biāo)函數(shù)達(dá)到最優(yōu)值(最大或最小值，且有界)的可行解 4.無(wú)界解: 求極大化時(shí)目標(biāo)函數(shù)在可行域中無(wú)上界，求極小化時(shí)目標(biāo)函數(shù)在可行域中無(wú)下界的可行解 定理 線性規(guī)劃問題如果有最優(yōu)解，則最優(yōu)解必是可行域的某個(gè)頂點(diǎn)(極點(diǎn)),可行域的性質(zhì),線性規(guī)劃的可行域是凸集(“凸多面體”) 線性規(guī)劃的最優(yōu)解在極點(diǎn)上,凸集,凸集,

10、不是凸集,極點(diǎn),線性規(guī)劃算法,單純形法 單純形法(simplex methods)是解決線性規(guī)劃問題最常用、最有效的算法之一。 單純形法的基本思路是：從可行域的一個(gè)頂點(diǎn)到相鄰的另一個(gè)頂點(diǎn)，保證使目標(biāo)函數(shù)值嚴(yán)格下降，直到達(dá)到最優(yōu)點(diǎn)的一種迭代方法。 單純形法是在實(shí)踐中久經(jīng)考驗(yàn)的算法，目前仍是一種比較好的方法。 許多線性規(guī)劃軟件中實(shí)現(xiàn)了單純形算法。,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x10, x20,簡(jiǎn)單線性規(guī)劃的圖解法,可行域,目標(biāo)函數(shù)等值線,最優(yōu)解,6,4,-8,6,0,x1,x2,3,z=0,z=3,z=6,z=12,z=？,(4/3,14/3),max z

11、=46/3,10.4 靈敏度分析,在所有的線性規(guī)劃模型中，目標(biāo)函數(shù)的系數(shù)和約束條件都是作為輸入數(shù)據(jù)或參數(shù)提供給模型的。 由于在實(shí)際問題的建模過程中會(huì)遇到很多不確定因素，所以不容易確切掌握這些系數(shù)。而系數(shù)的變化會(huì)改變?cè)€性規(guī)劃問題，隨之也會(huì)影響原來(lái)求得的最優(yōu)解。 因此必須研究已求得的最優(yōu)解是怎樣隨輸入?yún)?shù)的變化而變化的。這稱為線性規(guī)劃的參數(shù)靈敏度分析。,對(duì)線性規(guī)劃模型 min z= cTx s.t. Axb LxU,其參數(shù)的變化可分為三種情況： 1cc+c; 2AA+A; 3bb+b 參數(shù)變化對(duì)解的影響可以參考有關(guān)的線性規(guī)劃方面的書籍,10.5 線性規(guī)劃問題的MATLAB求解,線性規(guī)劃問題求解的

12、MATLAB命令為linprog,1. 用于求解模型,min z = cTx s.t. Axb,格式1 x= linprog(c,A,b) 格式2 x,z= linprog(c,A,b) 其中輸出x,z分別為決策向量的最優(yōu)解和目標(biāo)函數(shù)的最優(yōu)值 格式3 x=linprog(c,A,b,Aeq,beq) 格式4 x,z=linprog(c,A,b,Aeq,beq) 其中Aeq和beq表示等式約束，即Aeq*x=beq,2. 用于求解模型,min z = cTx s.t. Axb LxU,x0表示初始點(diǎn),格式5 x=linprog(c,A,b,Aeq,beq,L,U) 格式6 x,z=linprog

13、(c,A,b,Aeq,beq,L,U,x0),注意：命令linprog還有一些其他更復(fù)雜的用法可以通過help命令去學(xué)習(xí)了解,引例1的求解,引例1 max z=4xA+2xB+3xC s.t. 7xA+3xB+6xC150 4xA+4xB+5xC200 xA，xB，xC0,min cTx s.t. Axb LxU,求解程序 c=-4;-2;-3; A=7,3,6;4,4,5; b=150;200; L=zeros(3,1); U=inf*ones(3,1); x,z=linprog(c,A,b,L,U),運(yùn)行結(jié)果： x=0 50 0，z=-100,結(jié)論：只生產(chǎn)B產(chǎn)品，日產(chǎn)量50件，利潤(rùn)最大。,

14、max z=400 x1+900 x2+500 x3+200 x4 s.t. 40 x1+75x2+30 x3+15x4800 300 x1+400 x2+200 x3+100 x42000 40 x1+75x2500 3 x1 2 x2 5 x310 5 x410,引例2的求解,引例2的求解,不滿足實(shí)用形式的要求，因此將其改寫為 -(300 x1+400 x2+200 x3+100 x4)-2000,再令 c=-400;-900;-500;-200 b=800;-2000;500 A=40,75,30,15; -300,-400,-200,-100; 40,75,0,0 L=3;2;5;5,

15、 U=inf;inf;10;10,min cTx s.t. Axb LxU,由于第二個(gè)不等式 300 x1+400 x2+200 x3+100 x42000,引例2的求解程序,c=-400;-900;-500;-200; A=40,75,30,15;-300,-400,-200,-100; 40,75,0,0; b=800;-2000;500; L=3;2;5;5; U=inf;inf;10;10; x=linprog(c,A,b,L,U); y=round(x) total=round(-c*x) women=round(-A(2,:)*x),程序運(yùn)行結(jié)果,y =3 3 10 10 tota

16、l =10960 women = 5127,結(jié)論：白天電視、最佳時(shí)間電視、廣播、雜志廣告次數(shù)分別為3，3，10，10，則可以滿足廣告公司的要求。 在此情況下，受廣告影響的總?cè)藬?shù)為10960千人；受廣告影響的女顧客人數(shù)為5127千人。,min z= cij xij s.t. x11+x12+x13+x14=60 x21+x22+x23+x24=40 x31+x32+x33+x34=60 x11+x21+x31 =30 x12+x22+x32 =50 x13+x23+x33 =40 x14+x24+x34 =40 xij0 (i=1,2,3;j=1,2,3,4),引例3的求解,引例3的求解,eye(4),eye(4),eye(4),引例3的求解程序,E=ones(1,4); O=zeros(1,4);I=eye(4); A11=E;O;O;A12=O;E;O;A13=O;O;E; A=A11,A12,A13;I,I,I; c=5;6;10;3;4;1;9;7;4;2;3;8; b=60;