項(xiàng)目數(shù)據(jù)分析師運(yùn)籌學(xué)之線性規(guī)劃

1、項(xiàng)目數(shù)據(jù)分析師-運(yùn)籌學(xué)之線性規(guī)劃線性規(guī)劃在人們的生產(chǎn)實(shí)踐中，經(jīng)常會(huì)遇到如何利用現(xiàn)有資源來(lái)安排生產(chǎn)，以取得最大經(jīng)濟(jì)效益的問(wèn)題。此類問(wèn)題構(gòu)成了運(yùn)籌學(xué)的一個(gè)重要分支一數(shù)學(xué)規(guī)劃，而線性規(guī)劃（linear programming 簡(jiǎn)記lp）則是數(shù)學(xué)規(guī)劃的一個(gè)重要分支。自從 1947年g. b. dantzig提出求解線性規(guī)劃的單純形方法以來(lái)，線性規(guī)劃在理論上趨向成熟，在實(shí)用中日益廣泛與深入。特別是在計(jì)算機(jī)能處理成千上萬(wàn)個(gè)約束條件和決策變量的線性規(guī)劃問(wèn)題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了，已成為現(xiàn)代管理中經(jīng)常采用的基本方法之一。1.1線性規(guī)劃的實(shí)例與定義例1某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺(tái)銷售后的利潤(rùn)分別

2、為4000元與3000元。生產(chǎn)甲機(jī)床需用a、b機(jī)器加工，加工時(shí)間分別為每臺(tái)2小時(shí)和1小時(shí)；生產(chǎn)乙機(jī)床需用a、 b、c三種機(jī)器加工，加工時(shí)間為每臺(tái)各一小時(shí)。 若每天可用于加工的機(jī)器時(shí)數(shù)分別為a機(jī)器10小時(shí)、b機(jī)器8小時(shí)和c機(jī)器7小時(shí)，問(wèn)該廠應(yīng)生產(chǎn)甲、乙機(jī)床各幾臺(tái)，才能使總利潤(rùn)最大？上述問(wèn)題的數(shù)學(xué)模型：設(shè)該廠生產(chǎn)臺(tái)甲機(jī)床和乙機(jī)床時(shí)總利潤(rùn)最大，則應(yīng)滿足（目標(biāo)函粒）max z = 4x1 + 3x2（!）* x, < 1()工i 十三< 8x2< 7演，2 0這里變量稱之為決策變量，（1 ）式被稱為問(wèn)題的目標(biāo)函數(shù)，（2 ）中的幾個(gè)不等式是問(wèn)題的約束條件，記為s.t.（ 即subjec

3、t to）。上述即為一規(guī)劃問(wèn)題數(shù)學(xué)模型的三個(gè)要素。由于上面 的目標(biāo)函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問(wèn)題?？傊€性規(guī)劃問(wèn)題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問(wèn)題。在解決實(shí)際問(wèn)題時(shí)， 把問(wèn)題歸結(jié)成一個(gè)線性規(guī)劃數(shù)學(xué)模型是很重要的一步，但往往也是困難的一步，模型建立得是否恰當(dāng)，直接影響到求解。而選取適當(dāng)?shù)臎Q策變量， 是我們建立有效模型的關(guān)鍵之一'。1.2 線性規(guī)劃的matlab 標(biāo)準(zhǔn)形式線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號(hào)可以是小于號(hào)也可以是大于號(hào)。為了避免這種形式多樣性帶來(lái)的不便，matlab 中規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)形式為t

4、n in cj x such that < b x其中c和工為為維列向鼠，b為加維列向號(hào)4為mx力矩陣 例如線性規(guī)劃max cj x such that ax >b x的lauab mi什型為inui -c1 x giich that -.lx < -b x1.3 線性規(guī)劃問(wèn)題的解的概念一般線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為可行解 滿足約束條件（4 ）的解），（2 1n x x x x l =，稱為線性規(guī)劃問(wèn)題的可行解，而使目標(biāo)函數(shù)（3 ）達(dá)到最小值的可行解叫最優(yōu)解?？尚杏?所有可行解構(gòu)成的集合稱為問(wèn)題的可行域，記為 r o1.4 線性規(guī)劃的圖解法圖解法簡(jiǎn)單直觀，有助于了解線性規(guī)劃問(wèn)題求

5、解的基本原理。我們先應(yīng)用圖解法來(lái)求解例1如上圖所示，陰影區(qū)域即為lp問(wèn)題的可行域 r。對(duì)于每一固定的值， 使目標(biāo)函數(shù)值 z等于的點(diǎn) 構(gòu)成的直線稱為目標(biāo)函數(shù)等位線，當(dāng)z變動(dòng)時(shí)，我們得到一族平行直線。讓等位線沿目標(biāo)函數(shù)值減小的方向移動(dòng)，直到等位線與可行域有交點(diǎn)的最后位置，此時(shí)的交點(diǎn)(一個(gè)或多個(gè))即為lp的最優(yōu)解。對(duì)于例1 。顯然等位線越趨于右上方，其上的點(diǎn)具有越大的目標(biāo)函數(shù)值。不難看出，本 例的最優(yōu)解為，最優(yōu)目標(biāo)值.5 = (n6)二最優(yōu)i ! mfi二* = 26 從上面的圖解過(guò)程可以看出并不難證明以下斷言：(1 )可行域 r可能會(huì)出現(xiàn)多種情況。r可能是空集也可能是非空集合，當(dāng)r非空時(shí)，它必定是

6、若干個(gè)半平面的交集(除非遇到空間維數(shù)的退化)。r既可能是有界區(qū)域，也可能是無(wú)界區(qū)域。(2 )在r非空時(shí)，線性規(guī)劃既可以存在有限最優(yōu)解，也可以不存在有限最優(yōu)解(其目標(biāo)函數(shù)值無(wú)界)。(3 ) r非空且lp有有限最優(yōu)解時(shí)，最優(yōu)解可以唯一或有無(wú)窮多個(gè)。r的“頂點(diǎn)”(4 )若線性規(guī)劃存在有限最優(yōu)解，則必可找到具有最優(yōu)目標(biāo)函數(shù)值的可行域上述論斷可以推廣到一般的線性規(guī)劃問(wèn)題，區(qū)別只在于空間的n維數(shù)。在一般的 n維空間中，用日工=5滿足一線性等式的點(diǎn)集被稱為一個(gè)超平面，而滿足一線性不等式j(luò)tflz 廣匕 b1或e rx,之力）"e的點(diǎn)集被稱為一個(gè)半空間（其中巴）為一 n維行向量，b為一實(shí)數(shù)）。有限個(gè)

7、半空間的交集被稱為多胞形，有界的多胞形又被稱為多面體。易見(jiàn)，線性規(guī)劃的可行域必為多胞形（為統(tǒng)一起見(jiàn)，空集 也被視為多胞形）。在一般n維空間中，要直接得出多胞形“頂點(diǎn)”概念還有一些困難。二維空間中的頂點(diǎn)可以看成為邊界直線的交點(diǎn)，但這一幾何概念的推廣在一般n維空間中的幾何意義并不十分直觀。為此，我們將采用另一途徑來(lái)定義它。定義1稱井雒空間中的區(qū)域z?為一馬集.打祗w丘a及，仃ax1 + （1 - 2 e r定又2沒(méi)r為"維皆間中的個(gè)凸集，r中的點(diǎn)彳被稱為r的個(gè)極點(diǎn).若不存在x x ersia e（o.l） 使同工=2d + （一2炭.定義1說(shuō)明凸集中任意兩點(diǎn)的連線必在此凸集中；而定義 2

8、說(shuō)明，若x是凸集 r的一個(gè)極點(diǎn)，則 x不能位于 r中任意兩點(diǎn)的連線上。不難證明，多胞形必為凸集。同樣也不難證明，二維空間中可行域r的頂點(diǎn)均為 r的極點(diǎn)（r也沒(méi)有其它的極點(diǎn)）。1.5 求解線性規(guī)劃的 matlab 解法單純形法是求解線性規(guī)劃問(wèn)題的最常用、最有效的算法之一。 單純形法是首先由 george dantzig于1947年提出的，近60年來(lái)，雖有許多變形體已被開(kāi)發(fā)，但卻保持著同樣的基本觀念。由于有如下結(jié)論：若線性規(guī)劃問(wèn)題有有限最優(yōu)解，則一定有某個(gè)最優(yōu)解是可行區(qū)域的一個(gè)極點(diǎn)?；诖耍瑔渭冃畏ǖ幕舅悸肥牵合日页隹尚杏虻囊粋€(gè)極點(diǎn)，據(jù)一定規(guī)則判斷其是否最優(yōu)；若否，則轉(zhuǎn)換到與之相鄰的另一極點(diǎn)，并

9、使目標(biāo)函數(shù)值更優(yōu)；如此下去，直到找到某一最優(yōu)解為止。這里我們不再詳細(xì)介紹單純形法，有興趣的讀者可以參看其它線性規(guī)劃書(shū)籍。下面我們介紹線性規(guī)劃的matlab 解法。x such that at bmatlab5.3 中線性規(guī)劃的標(biāo)準(zhǔn)型為基本函數(shù)形式為linprog（c,a,b） ,它的返回值是向量 x的值。還有其它的一些函數(shù)調(diào)用形式 （在matlab 指令窗運(yùn)行help linprog可以看到所有的函數(shù)調(diào)用形式），如：x,fval=linprog(c,a,b,aeq,beq,lb,ub,x 0 .options)這里fval返回目標(biāo)函數(shù)的值，aeq和beq對(duì)應(yīng)等式約束 beq x aeq = *

10、 , lb和ub分別是變量x的下界和上界，x 0是x的初始值， options是控制參數(shù).例2求解下列線性規(guī)劃問(wèn)題x| + x, + xj = 72斗-5心+三2 10*與小2。解(i )編寫(xiě)m文件c=2；3;-5;a=-2,5,-1; b=-10;aeq=1,1,1；beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1)value=c'*x(ii )將m文件存盤，并命名為examplel.m 。(iii )在matlab 指令窗運(yùn)行 examplel 即可得所求結(jié)果。例1求解線性規(guī)劃問(wèn)題min 三=2鶯 + 3ml + 工i+ 4x2 + 2x2 之 83xj + 2xz > 6> 0解編寫(xiě)matlab 程序如下:c=2；3;1;a=1,4,2;3,2,0;b=8；6;x,y=linprog(c,-a,-b,口口zeros(3,1)1.6 可以轉(zhuǎn)化為線性規(guī)劃的問(wèn)題很多看起來(lái)不是線性規(guī)劃的問(wèn)題也可以通過(guò)變換變成線性規(guī)劃問(wèn)題來(lái)解決。如:例2問(wèn)題為min i* i + i/i+|，| s. t.ax < b其中，u和占為相應(yīng)維數(shù)的也陣和向【3要把上面的問(wèn)題變換成線性規(guī)劃問(wèn)題，只要注意到事實(shí)：對(duì)任意的x i ，