項目數(shù)據(jù)師運籌學(xué)之線性規(guī)劃

項目數(shù)據(jù)分析師----

運籌學(xué)之線性規(guī)劃線性規(guī)劃在人們的生產(chǎn)實踐中，經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟效益的問題。此類問題構(gòu)成了運籌學(xué)的一個重要分支—數(shù)學(xué)規(guī)劃，而線性規(guī)劃(LinearProgramming簡記LP)則是數(shù)學(xué)規(guī)劃的一個重要分支。自從1947年G.B.Dantzig提出求解線性規(guī)劃的單純形方法以來，線性規(guī)劃在理論上趨向成熟，在實用中日益廣泛與深入。特別是在計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了，已成為現(xiàn)代管理中經(jīng)常采用的基本方法之一。1.1線性規(guī)劃的實例與定義例1某機床廠生產(chǎn)甲、乙兩種機床，每臺銷售后的利潤分別為4000元與3000元。生產(chǎn)甲機床需用A、B機器加工，加工時間分別為每臺2小時和1小時；生產(chǎn)乙機床需用A、B、C三種機器加工，加工時間為每臺各一小時。若每天可用于加工的機器時數(shù)分別為A機器10小時、B機器8小時和C機器7小時，問該廠應(yīng)生產(chǎn)甲、乙機床各幾臺，才能使總利潤最大？上述問題的數(shù)學(xué)模型：設(shè)該廠生產(chǎn)臺甲機床和乙機床時總利潤最大，則應(yīng)滿足這里變量稱之為決策變量，（1）式被稱為問題的目標(biāo)函數(shù)，（2）中的幾個不等式是問題的約束條件，記為s.t.(即subjectto)。上述即為一規(guī)劃問題數(shù)學(xué)模型的三個要素。由于上面的目標(biāo)函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題?？傊?，線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題。在解決實際問題時，把問題歸結(jié)成一個線性規(guī)劃數(shù)學(xué)模型是很重要的一步，但往往也是困難的一步，模型建立得是否恰當(dāng)，直接影響到求解。而選取適當(dāng)?shù)臎Q策變量，是我們建立有效模型的關(guān)鍵之一。1.2線性規(guī)劃的Matlab標(biāo)準(zhǔn)形式線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號可以是小于號也可以是大于號。為了避免這種形式多樣性帶來的不便，Matlab中規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)形式為1.3線性規(guī)劃問題的解的概念一般線性規(guī)劃問題的標(biāo)準(zhǔn)型為可行解滿足約束條件（4）的解),,,(21nxxxxL=，稱為線性規(guī)劃問題的可行解，而使目標(biāo)函數(shù)（3）達到最小值的可行解叫最優(yōu)解。竭可行域趨所有可行解英構(gòu)成的集合堪稱為問題的鵝可行域，記仍為譜R荷。忙1.4線奴性規(guī)劃的圖頸解法寧圖解法簡單方直觀，有助挎于了解線性競規(guī)劃問題求馬解的基本原詠理。我們先拔應(yīng)用圖解法節(jié)來求解例懶1如上圖伙所示，陰影沿區(qū)域即為英LP問題娘的可行域惡R。對于已每一固定的皮值，使目標(biāo)繩函數(shù)值析z貢等于的點構(gòu)啞成的直線稱寺為目標(biāo)函數(shù)借等位線，當(dāng)著臟z烈變動時，我央們得到一族罷平行直線。罵讓等位線沿割目標(biāo)函數(shù)值失減小的方向撓移動，直到硬等位線與可撞行域有交點鞠的最后位置掌，此時的交自點（一個或正多個）即為腸LP的就最優(yōu)解。欲對于例1型，顯然等要位線越趨于粗右上方，其千上的點具有稅越大的目標(biāo)白函數(shù)值。不攤難看出，本苦攏例的最優(yōu)解歸為，最優(yōu)目輛標(biāo)值危。胖從上面的圖牲解過程可以薄看出并不難疼證明以下斷疲言：當(dāng)（1）嬌可行域版R密可能會出現(xiàn)差多種情況。擴債R雄可能是空集狠也可能是非高空集合，當(dāng)安槽R未非空時，它縣必定是若干伙個半平面的博交集（除非寧遇到空間維畝數(shù)的退化）彼。筆R駁既可能是有壞界區(qū)域，也因可能是無界飄區(qū)域。福（2）鋼在存R逆非空時，線服性規(guī)劃既可繼以存在有限練最優(yōu)解，也讀可以不存在叼有限最優(yōu)解晚（其目標(biāo)函延數(shù)值無界）鞋。診（3）薯R非空粱且L派P有有限崇最優(yōu)解時，盯最優(yōu)解可以鄉(xiāng)唯一或有無解窮多個。禍（4）糊若線性規(guī)劃嫂存在有限最天優(yōu)解，則必緩可找到具有鏈最優(yōu)目標(biāo)函擋數(shù)值的可行獨域坑R家的“頂點”尋。喜上述論斷可倘以推廣到一猛般的線性規(guī)堂劃問題，區(qū)牌別只在于空渾間的n維攜數(shù)。在一般炭的述n挎維空間中，農(nóng)滿足一線性弱等式標(biāo)的點集被稱鳴為一個超平扔面，而滿足逐一線性不等恭式惠的點集被稱害為一個半空猾間（其中紡為一縫n往維行向量，驕b覺為一實數(shù)）浸。有限個半惡空間的交集墓被稱為多胞競形，有界的異多胞形又被漫稱為多面體沈。易見，線蕉性規(guī)劃的可兵行域必為多券胞形（為統(tǒng)瑞一起見，空贏集Φ也澤被視為多胞憑形）。屋在一般趴n亮維空間中，丙要直接得出絲多胞形“頂枝點”概念還莊有一些困難譽。二維空間膨中的頂點可春以看成為邊兼界直線的交且點，但這一江幾何概念的圈推廣在一般鋒炎n圾維空間中的枕幾何意義并等不十分直觀留。為此，我磚們將采用另棗一途徑來定升義它。栗定義1尼說明凸集中晴任意兩點的衫連線必在此暑凸集中；而掛定義2贊說明，若環(huán)x童是凸集彈R獲的一弱個極點，則鮮肥x活不能位于向R犧中任意兩點指的連線上。堤不難證明，服多胞形必為益凸集。同樣版也不難悲證明，二維絕空間中可行含域哥R啦的頂點均為邀猛R映的極點（真R寧也沒有其它川的極點）。侵吊1.5求藝解線性規(guī)劃戴的Mat跨lab解鑼法工單純形法是寄求解線性規(guī)箏劃問題的最向常用、最有倍效的算法之醒一。單純形危法是首先由冒Geor弟geDa域ntzig防于19失47年提拆出的，近鎮(zhèn)60年來嗚，雖有許多幣變形體已被橫開發(fā)，但卻活保持著同樣冷的基本觀念準(zhǔn)。由于有如憑下結(jié)論：若撈線性規(guī)劃問飛題有有限最校優(yōu)解，則一要定有某個最醬優(yōu)解是可行食區(qū)域的一個搬極點?；谑４耍瑔渭冃喂辗ǖ幕舅悸劼肥牵合日疑隹尚杏虻某且粋€極點，刊據(jù)一定規(guī)則躺判斷其是否京最優(yōu)；若否遠，則轉(zhuǎn)換到奧與之相鄰的告另一極點，縫并使目標(biāo)函俱數(shù)值更優(yōu)；禾如此下去，壁直到找到某辟一最優(yōu)解為膽止。這里我愈們不再詳細沿介紹單純形彎法，有興趣茂的讀者可以幻參看其它線丑性規(guī)劃書籍潛。下面我們備介紹線性規(guī)良劃的Ma亡tlab熟解法。旋Matla墊b5.3附中線性規(guī)劃填的標(biāo)準(zhǔn)型為蕉岡基本函數(shù)形窗式為li躲nprog腎(c,A,斷b)，它大的返回值是劣向量舟x零的值。還有售其它的一些頌函數(shù)調(diào)用形壁式（在M銀atlab學(xué)指令窗運像行hel嗽plin始prog餅可以看到所川有的函數(shù)調(diào)昨用形式），崗如：贈[x,fv椒al]=l孟inpro班g(c,A近,b,Ae揭q,beq初,LB,U猶B,X0測,OPT堆IONS)柜榜這里fv常al返回啊目標(biāo)函數(shù)的宗值，Ae俗q和b戒eq對應(yīng)籍等式約束氧beqx煩Aeq識=*，濫LB和奮UB分守別是變量續(xù)x督的下界和上輝界，凍x悔0是鍋x槽的初始值，期OPTI裂ONS是擾控制參數(shù)禾.吳例2求星解下列線性輝規(guī)劃問題息解（i肉）編寫M百文件奸c=[2;沒3;-5]緞;迫a=[-2浸,5,-1逢];b=消-10;瘦aeq=[方1,1,1牧];秤beq=7械;吉x=lin蠢prog(供-c,a,興b,aeq秋,beq,都zeros自(3,1)氏)赤value盞=c'*x潤昨（ii懶）將M鄙文件存盤，脈并命名為炭examp絨le1.m間。菊（iii糠）在M哄atlab井指令窗運企行exa掃mple1姜即可得所耗求結(jié)果。免例1求效解線性規(guī)劃谷問題銷解編寫M島atlab慧程序如下盯：恢c=[2;姻3;1];賠齡a=[1,汽4,2;3靈,2,0]雨;牙b=[8;而6];待[x,y]同=linp吃rog(c瓜,-a,-蔑b,[],丙[],ze辛ros(3遵,1))兆1.6可稈以轉(zhuǎn)化為線壺性規(guī)劃的問貧題忠很多