第五章線(xiàn)性規(guī)劃LP.doc

第五章 線(xiàn)性規(guī)劃（LP）第一節(jié) 向量和矩陣的基本知識(shí)1矩陣的概念定義1：由個(gè)數(shù)排成的一個(gè)行列（數(shù)）表叫做一個(gè)行列（或）矩陣。叫做這個(gè)矩陣的元素；常用大寫(xiě)字母A、B等表示矩陣，有時(shí)為明確矩陣記為或。注意：（1）解釋幾個(gè)術(shù)語(yǔ)：行、列、下標(biāo)等。（2）矩陣與行列式形式不同、意義不同，行列式表示一個(gè)數(shù)，矩陣只是一個(gè)數(shù)表；行列式要求行列數(shù)相同，而矩陣不然。例如：（1）三階矩陣 （2）的矩陣 B=向量是一種特殊的矩陣，分為行向量和列向量。（1）行向量是的矩陣，它的具體形式為 ；（2）列向量是的矩陣，它的具體形式為： ，或者。例如： ；2幾種特殊矩陣（1）零矩陣：元素全為零的矩陣；記為。Note：零矩陣只是給出了元素的特征（全為0），由于行、列數(shù)的不同有不同形式的零矩陣。例如 二階零矩陣： ，零矩陣：。（2）負(fù)矩陣：設(shè)，則稱(chēng)為的負(fù)矩陣；記為。Note：負(fù)矩陣是相對(duì)于一個(gè)給定的矩陣而言的。（3）方陣：行列數(shù)相同的矩陣。n行n列矩陣叫n階矩陣。 二階方陣 ；四階方陣.（4）單位矩陣：主對(duì)角線(xiàn)上元素全為1，其余元素全為0的方陣。Note：（1）單位陣是一類(lèi)特殊方陣。（2）定義給出了元素特征，由于階數(shù)不同有不同形式的單位陣。n階單位矩陣記為。例如，三階單位陣,（3）矩陣的相等：設(shè)A、B是數(shù)域F上兩個(gè)矩陣，若1）A、B具有相同的行數(shù)和列數(shù)；2）對(duì)應(yīng)位置上的元素相等。則稱(chēng)A與B相等。記為A=B。3、矩陣的運(yùn)算及性質(zhì)(1）加法：定義：設(shè)，；與的和為矩陣；記為，即=。Note：(1)注意可加的條件以及相加的結(jié)果，實(shí)質(zhì)轉(zhuǎn)化為數(shù)的加法運(yùn)算。 (2）利用負(fù)矩陣可以定義矩陣的減法：設(shè)，定義=。例1：設(shè)，于是，。例2：設(shè)三階方陣滿(mǎn)足，其中，求。(2）數(shù)量乘法定義：設(shè)，與的數(shù)乘為，記為。 例如：設(shè)，則2。(3）乘法(A）定義：設(shè)，；與的乘積為，其中；記為。Note：可乘的條件與結(jié)果。例如：（1）設(shè),于是，。 （2）設(shè)，于是 。(B）性質(zhì)：（注意下列式子有意義的條件） （1）； （2）； （3）； （4） 。Note：1）由定義及矩陣相等的概念證明（略）。 2）乘法一般不滿(mǎn)足交換律（可分析不同的情況）。 3）由于而可能有，所以“消去律”不成立，即“，且不一定有”。(C）方陣的方冪：注：由于乘法滿(mǎn)足結(jié)合律，所以有限個(gè)矩陣相乘有意義，由可乘的條件，只有方陣才可以自乘。定義：設(shè)，定義，稱(chēng)為的次方冪；規(guī)定。性質(zhì)：顯然。Note：1）冪指數(shù)為非負(fù)整數(shù)。 2）一般地，以及無(wú)類(lèi)于其它指數(shù)性質(zhì)和代數(shù)公式，如等。(D）矩陣方程：（線(xiàn)性方程組的矩陣表示）設(shè)線(xiàn)性方程組 （1），其系數(shù)矩陣為，令，則方程組（1）可寫(xiě)為矩陣方程 （2）。 若，則為齊次線(xiàn)性方程組的矩陣表示。求（1）的解，即求滿(mǎn)足（2）的矩陣（列向量）。例3：求解下列方程的解：，首先，把上面的方程組化成矩陣方程的形式，即記 ，于是上面的方程組可以寫(xiě)成如下的形式： 。這種矩陣方程在Matlab中是容易求解的。上面的例子可以這樣寫(xiě)： A=1,-5,6;4,7,8;5,-2,7; b=-8,5,7; x=Abx = 3.8696 0.3913 -1.6522例4：求解下列方程的解：，首先，把上面的方程組化成矩陣方程的形式，即記 ，于是上面的方程組可以寫(xiě)成如下的形式：。這種矩陣方程在Matlab中的求解過(guò)程如下：A=1,2,3;3,2,1; b=2;3; c=Abc = 0.8750 0 0.3750注意：這個(gè)方程組得到的是范數(shù)最小的解。4）轉(zhuǎn)置定義：設(shè)，把的行變?yōu)榱?、列變?yōu)樾兴玫男辛芯仃嚪Q(chēng)為矩陣的轉(zhuǎn)置（矩陣），記為（或者記為）。（可寫(xiě)出具體形式）性質(zhì)：（1）； （2）； （3）； （4）。第二節(jié) 線(xiàn)性規(guī)劃問(wèn)題（LP）例1 設(shè)有兩個(gè)煤廠甲和乙，每月進(jìn)每煤分別為60噸和100噸，聯(lián)合供應(yīng)三個(gè)居民區(qū)A,B,C,三個(gè)居民區(qū)每月對(duì)煤的需求量為50噸，70噸和40噸。煤廠到各個(gè)居民區(qū)的距離如下表所示。 表一：煤廠到居民區(qū)的距離表 居民區(qū)煤廠ABC甲10公里5公里6公里乙4公里8公里12公里 如何分配供煤量使得運(yùn)輸量達(dá)到最??？解：設(shè)甲乙煤廠到各個(gè)居民區(qū)的供煤量如下表所示： 表二：煤廠到居民區(qū)的距離表 居民區(qū)煤廠ABC發(fā)煤量甲60乙100收煤量507040求最小運(yùn)輸量于是運(yùn)輸量為 。由于發(fā)煤量的限制，有下列等式成立： 。又由于收煤量的限制，有下列等式成立：。所以這個(gè)運(yùn)輸問(wèn)題必需滿(mǎn)足下列條件： ； 。當(dāng)然滿(mǎn)足這個(gè)條件的運(yùn)輸方案有很多，我們要求的是最小的運(yùn)輸量。即求： 我們用向量和矩陣的知識(shí)，可以進(jìn)一步簡(jiǎn)化上面的表達(dá)式。 記 ， ，于是 。方法一：對(duì)于這個(gè)問(wèn)題，我們可以用Matlab來(lái)計(jì)算。首先，在命令窗口，輸入： c=10;5;6;4;8;12; beq=60;100;50;70;40; Aeq=1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1; lb=zeros(6,1); x,fval,exitflag,output=linprog(c,Aeq,beq,lb,)運(yùn)行的結(jié)果如下：Optimization terminated successfully.x = 0.0000 20.0000 40.0000 50.0000 50.0000 0.0000fval = 940.0000exitflag = 1output = iterations: 5 cgiterations: 0 algorithm: lipsol注意：對(duì)于線(xiàn)性規(guī)劃問(wèn)題，Matlab有l(wèi)inprog這個(gè)命令可以使用。它可以解決的問(wèn)題的形式如下： ，其中均為列向量，均為矩陣。linprog這個(gè)命令的調(diào)用格式有以下幾種：（1） x=linprog(c,A,b,Aeq,beq);（2） x=linprog(c,A,b,Aeq,beq,lb,ub,x0);（3） x=linprog(c,A,b,Aeq,beq,lb,ub,x0,options);（4） x,fval=linprog(-);（5） x,fval,exitflag,output=linprog(-);例2：自來(lái)水輸送問(wèn)題問(wèn)題：某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來(lái)水由A,B，C三個(gè)水庫(kù)供應(yīng)。四個(gè)居民區(qū)每天必須得到保證的基本生活用水量分別為30，70，10，10千噸。由于水源緊張，三個(gè)水庫(kù)每天最多只能分別供應(yīng)50，60，50千噸自來(lái)水。因?yàn)榈乩砦恢玫牟顒e，自來(lái)水公司從各水庫(kù)向各區(qū)送水所需要付出的引水管理費(fèi)不同（具體見(jiàn)表格，其中水庫(kù)C與丁區(qū)之間沒(méi)有輸水管道），其它管理費(fèi)用為450元每千噸。按公司規(guī)定，各區(qū)用戶(hù)按照統(tǒng)一標(biāo)準(zhǔn)900元每千噸收費(fèi)。此外，四個(gè)區(qū)都向公司申請(qǐng)了額外用水量，分別為50，70，20，40千噸。該公司應(yīng)該如何分配每天的供水量，使得獲利最多？為了增加供水量，自來(lái)水公司正在考慮進(jìn)行水庫(kù)改造，使得三個(gè)水庫(kù)每天的最大供水量提高一倍，問(wèn)那時(shí)的供水方案如何改變？公司利潤(rùn)可以增加多少？ 表格1 各區(qū)的引水管理費(fèi)引水管理費(fèi)甲乙丙丁A160130220170B140130190150C190200230/ 問(wèn)題分析： 分配供水量就是安排從三個(gè)水庫(kù)向四個(gè)區(qū)送水的方案，目標(biāo)是使得獲利最多。從題目中的數(shù)據(jù)來(lái)看，A,B，C三個(gè)水庫(kù)的供水量160千噸，小于四個(gè)區(qū)的基本生活用水量與額外用水量之和300千噸。故水庫(kù)的水總能全部賣(mài)出獲利。于是，公司每天的總收入為元，與供水方案無(wú)關(guān)。同樣，公司每天的其它管理費(fèi)用為元，也與供水方案無(wú)關(guān)。所以，要使利潤(rùn)最大，只要使得引水管理費(fèi)管理費(fèi)最小即可。另外，供水方案自然要受到三個(gè)水庫(kù)的供應(yīng)量和四個(gè)區(qū)的需求量的限制。模型建立決策變量為A,B，C三個(gè)水庫(kù)（）分別向甲、乙、丙、丁四個(gè)居民區(qū)（）的供水量。設(shè)水庫(kù)向居民區(qū)的日供水量為。水庫(kù)C與丁區(qū)之間沒(méi)有輸水管道,所以。 目標(biāo)函數(shù)為 （1）約束條件為兩類(lèi):第一類(lèi)為水庫(kù)的供應(yīng)量限制，第二類(lèi)是各居民區(qū)的需求量限制。首先，由于供水量總能賣(mài)出并獲利，所以水庫(kù)的供應(yīng)量限制可以表示為： ， （2） ， （3） ， （4）考慮到各區(qū)的基本生活用水量和額外用水量，需求量限制可以表示為： ， （5） ， （6） ， （7） ， （8）同時(shí)，。對(duì)于上面的線(xiàn)性規(guī)劃模型，我們可以把它化成矩陣形式：令 ，它們是11維的列向量。設(shè) ， ， ，設(shè) ，在Matlab中調(diào)用linprog的命令。具體的程序如下：c=160;130;220;170;140;130;190;150;190;200;230;b=80;140;30;50;-30;-70;-10;-10;beq=50;60;50;A=1,0,0,0,1,0,0,0,1,0,0; 0,1,0,0,0,1,0,0,0,1,0; 0,0,1,0,0,0,1,0,0,0,1; 0,0,0,1,0,0,0,1,0,0,0; -1,0,0,0,-1,0,0,0,-1,0,0; 0,-1,0,0,0,-1,0,0,0,-1,0; 0,0,-1,0,0,0,-1,0,0,0,-1; 0,0,0,-1,0,0,0,-1,0,0,0;Aeq=1,1,1,1,0,0,0,0,0,0,0; 0,0,0,0,1,1,1,1,0,0,0; 0,0,0,0,0,0,0,0,1,1,1; lb=zeros(11,1); x,fval,exitflag,output=linprog(c,A,b,Aeq,beq,lb) % the results is following: Optimization terminated successfully.x = 0.0000 50.0000 0.0000 0.0000 0.0000 50.0000 0.0000 10.0000 40.0000 0.0000 10.0000fval = 2.4400e+004exitflag = 1output = iterations: 6 cgiterations: 0 algorithm: lipsol所以，供水方案為：A水庫(kù)向乙區(qū)供水50千噸，B 水庫(kù)向乙、丁區(qū)分別供水50、10千噸，C水庫(kù)向甲、丙區(qū)分別供水40、10千噸。引水管理費(fèi)為24400元，所以利潤(rùn)為：144000720002440047600元。習(xí)題五l.生產(chǎn)炊事用具需要兩種資源勞動(dòng)力和原材料，某公司制定生產(chǎn)計(jì)劃，生產(chǎn)三種不同的產(chǎn)品，生產(chǎn)管理部門(mén)提供的數(shù)據(jù)如下：ABC勞動(dòng)力（小時(shí)/件）736原材料（公斤/件）445利潤(rùn)（元/件）423每天供應(yīng)原材料200公斤，每天可供使用的勞動(dòng)力為150小時(shí)。建立線(xiàn)性規(guī)劃模型，使得總收益最大，并求出各種產(chǎn)品的日產(chǎn)量。2一家廣告公司想在電視、廣播上作廣告，其目的是盡可能地吸引顧客。下面是市場(chǎng)調(diào)查的結(jié)