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

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