優(yōu)化問題與規(guī)劃模型

§3.6優(yōu)化問題與規(guī)劃模型與最大、最小、最長、最短等等有關(guān)的問題都是優(yōu)化問題。解決優(yōu)化問題形成管理科學的數(shù)學方法：運籌學。運籌學主要分支：（非）線性規(guī)劃、動態(tài)規(guī)劃、圖與網(wǎng)絡分析、存貯學、排隊倫、對策論、決策論。6.1線性規(guī)劃1939年蘇聯(lián)數(shù)學家康托洛維奇發(fā)表《生產(chǎn)組織與計劃中的數(shù)學問題》1947年美國數(shù)學家喬治.丹契克、馮.諾伊曼提出線性規(guī)劃的一般模型及理論.1.問題例1作物種植安排一個農(nóng)場有50畝土地,20個勞動力,計劃種蔬菜,棉花和水稻.種植這三種農(nóng)作物每畝地分別需要勞動力1/21/31/4,預計每畝產(chǎn)值分別為110元,75元,60元.如何規(guī)劃經(jīng)營使經(jīng)濟效益最大.分析：以取得最高的產(chǎn)值的方式達到收益最大的目標.1.求什么？分別安排多少畝地種蔬菜、棉花、水稻？x1畝、x2畝、x3畝2.優(yōu)化什么？產(chǎn)值最大maxf=10x1+75x2+60x33.限制條件？田地總量x1+x2+x350勞力總數(shù)1/2x1+1/3x2+1/4x320模型I:設決策變量：種植蔬菜x1畝,棉花x2畝,水稻x3畝，求目標函數(shù)f=110x1+75x2+60x3在約束條件x1+x2+x3501/2x1+1/3x2+1/4x320下的最大值規(guī)劃問題：求目標函數(shù)在約束條件下的最值,規(guī)劃問題包含3個組成要素:決策變量、目標函數(shù)、約束條件。當目標函數(shù)和約束條件都是決策變量的線性函數(shù)時，稱為線性規(guī)劃問題,否則稱為非線性規(guī)劃問題。2.線性規(guī)劃問題求解方法稱滿足約束條件的向量為可行解,稱可行解的集合為可行域,稱使目標函數(shù)達最值的可行解為最優(yōu)解.命題1線性規(guī)劃問題的可行解集是凸集.因為可行解集由線性不等式組的解構(gòu)成。兩個變量的線性規(guī)劃問題的可行解集是平面上的凸多邊形。命題2線性規(guī)劃問題的最優(yōu)解一定在可行解集的某個極點上達到.圖解法：解兩個變量的線性規(guī)劃問題，在平面上畫出可行域，計算目標函數(shù)在各極點處的值，經(jīng)比較后，取最值點為最優(yōu)解。命題3當兩個變量的線性規(guī)劃問題的目標函數(shù)取不同的目標值時，構(gòu)成一族平行直線,目標值的大小描述了直線離原點的遠近。于是穿過可行域的目標直線組中最遠離(或接近)原點的直線所穿過的凸多邊形的頂點即為取的極值的極點—最優(yōu)解。單純形法:通過確定約束方程組的基本解,并計算相應目標函數(shù)值,在可行解集的極點中搜尋最優(yōu)解.正則模型:決策變量:x1,x2,…,xn.目標函數(shù):Z=c1x1+c2x2+…+cnxn.約束條件:a11x1+…+a1nxn≤b1,……am1x1+…+amnxn≤bm,模型的標準化10.引入松弛變量將不等式約束變?yōu)榈仁郊s束.若有ai1x1+…+ainxn≤bi,則引入xn+i≥0,使得ai1x1+…+ainxn+xn+i=bi若有aj1x1+…+ajnxn≥bj,則引入xn+j≥0,使得aj1x1+…+ajnxn-xn+j=bj.且有Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.20.將目標函數(shù)的優(yōu)化變?yōu)槟繕撕瘮?shù)的極大化.若求minZ,令Z’=–Z,則問題變?yōu)閙axZ’.30.引入人工變量,使得所有變量均為非負.若xi沒有非負的條件,則引入xi’≥0和xi’’≥0,令xi=xi’–xi’’,則可使得問題的全部變量均非負.標準化模型求變量x1,x2,…,xn,maxZ=c1x1+…+cnxn,s.t.a11x1+…+a1nxn=b1,……am1x1+…+amnxn=bm,x1≥0,…,xn≥0,定義:若代數(shù)方程AX=B的解向量有n-m個分量為零,其余m個分量對應A的m個線性無關(guān)列,則稱該解向量為方程組的一個基本解.在一個線性規(guī)劃問題中,如果一個可行解也是約束方程組的基本解,則稱之為基本可行解.命題4一個向量x是線性規(guī)劃問題可行解集的一個極點,當且僅當它是約束方程的一個基本可行解。于是尋找取得極值的凸集極點的幾何問題變成了求代數(shù)方程基本解的問題，形成了解優(yōu)化問題的單純形方法，改進單純形方法等。按這些計算方法編制程序，產(chǎn)生了專門解優(yōu)化問題的軟件Lindo、Lingo。用Matlab求解：標準的線性規(guī)劃的模型：minf=cTxs.t.AxbA1x=b1LBxUBMatlab求解程序:[x,f]=linprog(c,A,b,A1,b1,LB,UB)還有軟件Excel也可應用于解優(yōu)化問題。3對偶問題例1作物種植安排一個農(nóng)場有50畝土地,20個勞動力,計劃種蔬菜,棉花和水稻.種植這三種農(nóng)作物每畝地分別需要勞動力1/21/31/4,預計每畝產(chǎn)值分別為110元,75元,60元.如何規(guī)劃經(jīng)營使經(jīng)濟效益最大.分析：以最經(jīng)濟的投入達到收益最大的目標.（或者說以直接出售土地和勞動力的方式達到收益最大的目標.）1求什么？土地成本價格y1勞動力成本價格y22.優(yōu)化什么？成本價格最低Ming=50y1+20y23.限制條件？蔬菜的市場價y1+1/2y2110棉花的市場價y1+1/3y275水稻的市場價y1+1/4y260模型II.設決策變量:對單位土地和對單位勞力投入成本價格分別為y1y2求目標函數(shù)g=50y1+20y2在約束條件y1+1/2y2110y1+1/3y275y1+1/4y260下的最小值.設A是mn矩陣，

c是n1向量，b是m1向量

x是n1向量,y是1m向量問題:maxf=cTxs.t.Axbxi0,i=1,2,,n.對偶問題:minf=ybs.t.yAcyi0,i=1,2,,m.對偶定理:互為對偶的兩個線性規(guī)劃問題,若其中一個有有窮的最優(yōu)解,則另一個也有有窮的最優(yōu)解,且最優(yōu)值相等.若兩者之一有無界的最優(yōu)解,則另一個沒有可行解模型III構(gòu)成對偶問題.模型I解得最優(yōu)解(optimunsolution)Xopt=(30020),最大值f(xopt)=4500模型II解得最優(yōu)解yopt=(10200),最小值g(yopt)=4500.模型I給出了生產(chǎn)中的資源最優(yōu)分配方案模型II給出了生產(chǎn)中資源的最低估價.進一步問：如果增加對土地和勞動力的投入，每種資源的單位投入增加會帶來多少產(chǎn)值？由最優(yōu)解y=(10,200)可見,多耕一畝地增加10元收入，多一個勞動力增加200元收入。也就是說,此時一個勞動力的估價為200元,而一畝土地估價為10元.這種價格涉及到資源的有效利用,它不是市場價格,而是根據(jù)資源在生產(chǎn)中做出的貢獻確定的估價,被稱為“影子價格”.再進一步問，棉花價格提高到多少才值的生產(chǎn)？由y1+1/3y2=10+200/3=76.6>75,（而其它兩個約束條件是等式）可見，只有當棉花價格提高到76.6元時才值得生產(chǎn).4靈敏度分析當線性規(guī)劃問題中的常數(shù)發(fā)生變化(由于測量誤差或具有多個取值可能)時,最優(yōu)解是否會隨之變化?通常假定變化的常數(shù)是某參數(shù)的線性函數(shù).討論參數(shù)取值與最優(yōu)解的關(guān)系的問題,被稱為參數(shù)線性規(guī)劃.例如,當農(nóng)作物的價格發(fā)生變化時,生產(chǎn)計劃是否應馬上隨之改變?參見線性規(guī)劃書籍將實際問題歸結(jié)為線性規(guī)劃模型是一個探索創(chuàng)造的過程。線性規(guī)劃模型的求解仍是計算數(shù)學的一個難題。例2供貨問題一家公司生產(chǎn)某種商品.現(xiàn)有n個客戶,第j個客戶需要貨物量至少為bj,可在m各不同地點設廠供貨.在地區(qū)i設廠的費用為di,供貨能力為hi,向第j個客戶供應單位數(shù)量的貨物費用為cij.如何設廠與供貨使總費用最小.模型：設決策變量：xij為在地區(qū)i向第j個客戶供貨數(shù)量,在地區(qū)i設廠，記yi=1,否則記yi=0求目標函數(shù)f=i(jcijxij+yidi)在約束條件ixij=bj,jxij-hiyi0,xij0,yi{0，1}下的最小值例3鋼材截短有一批鋼材,每根長7.3米.現(xiàn)需做100套短鋼材.每套包括長2.9米,2.1米,1.5米的各一根.至少用掉多少根鋼材才能滿足需要,并使得用料最省.

分析：可能的截法和余料第1種7.3-(2.9×2+1.5)=0第2種7.3-(2.9+2.1×2)=0.2第3種7.3-(2.9+1.5×2)=1.4第4種7.3-(2.9+2.1+1.5)=0.8第5種7.3-(2.1×2+1.5×2)=0.1第6種7.3-(2.1×3)=1第7種7.3-(2.1+1.5×3)=0.7第8種7.3-(1.5×4)=1.3模型：設決策變量：按第i種方法截xi根鋼材。求目標函數(shù)f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8在約束條件2x1+x2+x3+x4=1002x2+x4+2x5+3x6+x7=100x1+2x3+x4+2x5+3x7+4x8=100xi0,i=1,…,8下的最小值用Matlab程序解得xopt=(40,20,0,0,30,0,0,0),f(xopt)=7（實際上應要求xi為正整數(shù)。這是一個整數(shù)規(guī)劃問題）。6.2整數(shù)規(guī)劃如果要求決策變量取整數(shù),或部分取整數(shù)的線性規(guī)劃問題,稱為整數(shù)規(guī)劃.

例4.飛船裝載問題設有n種不同類型的科學儀器希望裝在登月飛船上,令cj>0表示每件第j類儀器的科學價值;aj>0表示每件第j類儀器的重量.每類儀器件數(shù)不限,但裝載件數(shù)只能是整數(shù).飛船總載荷不得超過數(shù)b.設計一種方案,使得被裝載儀器的科學價值之和最大.建模記xj為第j類儀器的裝載數(shù).求目標函數(shù)f=jcjxj在約束條件jajxjb,xj為正整數(shù),下的最大值.用分枝定界法求解整數(shù)規(guī)劃問題基本思想:反復劃分可行域并確定最優(yōu)值的界限,將原問題不斷地分枝為若干個子問題,且縮小最優(yōu)質(zhì)的取值范圍,直到求得最優(yōu)解.例:求目標函數(shù)f=3x1+2x2在約束條件:2x1+3x214,2x1+x29,x1x2為自然數(shù)下的最大值.用Lindo軟件求解整數(shù)規(guī)劃max3x1+2x2s.t.2x1+3x2<=142x1+x2<=9endginx1ginx2(或者用gin2代替ginx1ginx2)6.30-1規(guī)劃如果要求決策變量只取0或1的線性規(guī)劃問題,稱為0-1規(guī)劃.0-1約束不一定是由變量的性質(zhì)決定的,更多地是由于邏輯關(guān)系引進問題的例5背包問題一個旅行者的背包最多只能裝6kg物品.現(xiàn)有4件物品的重量和價值分別為2kg,3kg,3kg,4kg,1元,1.2元,0.9元,1.1元.應攜帶那些物品使得攜帶物品的價值最大?建模:記xj為旅行者攜帶第j件物品的件數(shù),取值只能為0或1.求目標函數(shù)f=x1+1.2x2+0.9x3+1.1x4在約束條件2x1+3x2+3x3+4x46下的最大值.用Lingo軟件求解0-1規(guī)劃Model:Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4<=6;@int(x1);@int(x2);@int(x3);@int(x4);end例6集合覆蓋問題實際問題1某企業(yè)有5種產(chǎn)品要存放,有些不能存放在一起,有些能存放在一起的,由于組合不同所需費用不同.求費用最低的儲存方案.實際問題2某航空公司在不同城市之間開辟了5條航線,一個航班可以飛不同的航線組合,不同組合成本不同,求開通所有航線且總費用最小的方案.抽象為集合覆蓋問題：設集合S={1,2,3,4,5}有一個子集類={{1,2},{1,3,5},{2,4,5},{3},{1},{4,5}}其中每一個元素對應一個數(shù)cj,稱為該元素的費用.選的一個子集使其覆蓋S,且總費用最低.即實際問題1中5種產(chǎn)品能存放在一起的各種組合為={{1,2},{1,3,5},{2,4,5},{3},{1},{4,5}}第i種組合的存儲費用為cj,求這五種產(chǎn)品費用最低的儲存方案。模型:設決策變量：設是S的