數(shù)學建模中的優(yōu)化問題與規(guī)劃模型

1、與最大、最小、最長、最短等等有關(guān)的問題都是優(yōu)化問題。解決優(yōu)化問題形成管理科學的數(shù)學方法:運籌學。運籌學主要分支:(非線性規(guī)劃、動態(tài)規(guī)劃、圖與網(wǎng)絡(luò)分析、存貯學、排隊倫、對策論、決策論。6.1 線性規(guī)劃1939年蘇聯(lián)數(shù)學家康托洛維奇發(fā)表生產(chǎn)組織與計劃中的數(shù)學問題1947年美國數(shù)學家喬治.丹契克、馮.諾伊曼提出線性規(guī)劃的一般模型及理論.1. 問題例1 作物種植安排一個農(nóng)場有50畝土地, 20個勞動力, 計劃種蔬菜,棉花和水稻. 種植這三種農(nóng)作物每畝地分別需要勞動力1/2 1/3 1/4, 預(yù)計每畝產(chǎn)值分別為110元, 75元, 60元. 如何規(guī)劃經(jīng)營使經(jīng)濟效益最大.分析:以取得最高的產(chǎn)值的方式達到收

2、益最大的目標.1. 求什么?分別安排多少畝地種蔬菜、棉花、水稻? x1畝、 x2畝、 x3畝2. 優(yōu)化什么?產(chǎn)值最大 max f=10x1+75x2+60x33. 限制條件?田地總量 x1+x2+x3 50 勞力總數(shù) 1/2x1+1/3x2+1/4x3 20模型I : 設(shè)決策變量:種植蔬菜x1畝, 棉花x2畝, 水稻x3畝,求目標函數(shù)f=110x1+75x2+60x3在約束條件x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 下的最大值規(guī)劃問題:求目標函數(shù)在約束條件下的最值,規(guī)劃問題包含3個組成要素: 決策變量、目標函數(shù)、約束條件。當目標函數(shù)和約束條件都是決策變量的線性函數(shù)時,

3、稱為線性規(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)成一族平行直線,目標值的大小描述了直線離原點的遠近。于是穿過可行域的目標直線組

4、中最遠離(或接近原點的直線所穿過的凸多邊形的頂點即為取的極值的極點最優(yōu)解。單純形法: 通過確定約束方程組的基本解, 并計算相應(yīng)目標函數(shù)值, 在可行解集的極點中搜尋最優(yōu)解.正則模型:決策變量: x1,x2,xn. 目標函數(shù): Z=c1x1+c2x2+cnxn.約束條件: a11x1+a1n x nb1, a m1x1+a mn x nb m, 模型的標準化10. 引入松弛變量將不等式約束變?yōu)榈仁郊s束.若有 ai1x1+ainxnbi, 則引入 xn+i 0, 使得 ai1x1+ainxn+ xn+i=bi若有 aj1x1+ajnxnbj, 則引入 xn+j 0, 使得 aj1x1+ajnxn-

5、xn+j=bj.且有 Z=c1x1+c2x2+cnxn+0xn+1+0xn+m.20. 將目標函數(shù)的優(yōu)化變?yōu)槟繕撕瘮?shù)的極大化. 若求 min Z, 令 Z=Z, 則問題變?yōu)?max Z .30. 引入人工變量,使得所有變量均為非負. 若 xi 沒有非負的條件,則引入 xi 0 和 xi0,令 xi = xi xi, 則可使得問題的全部變量均非負.標準化模型求變量 x1, x2, xn,max Z = c1x1+ cnxn,s. t. a11x1+ a1nxn= b1,a m1x1+ a mn x n=b m,x1 0, x n 0,定義: 若代數(shù)方程AX=B的解向量有n-m個分量為零, 其余m

6、個分量對應(yīng)A的m個線性無關(guān)列, 則稱該解向量為方程組的一個基本解.在一個線性規(guī)劃問題中, 如果一個可行解也是約束方程組的基本解, 則稱之為基本可行解.命題 4 一個向量 x 是線性規(guī)劃問題可行解集的一個極點, 當且僅當它是約束方程的一個基本可行解。于是尋找取得極值的凸集極點的幾何問題變成了求代數(shù)方程基本解的問題,形成了解優(yōu)化問題的單純形方法,改進單純形方法等。按這些計算方法編制程序,產(chǎn)生了專門解優(yōu)化問題的軟件Lindo、Lingo 。用Matlab求解:標準的線性規(guī)劃的模型:min f=c T xs.t. Ax bA1x=b1LB x UBMatlab求解程序: x,f=linprog(c,A

7、,b,A1,b1,LB,UB還有軟件Excel 也可應(yīng)用于解優(yōu)化問題。3 對偶問題例1 作物種植安排一個農(nóng)場有50畝土地, 20個勞動力, 計劃種蔬菜,棉花和水稻. 種植這三種農(nóng)作物每畝地分別需要勞動力1/2 1/3 1/4, 預(yù)計每畝產(chǎn)值分別為110元, 75元, 60元. 如何規(guī)劃經(jīng)營使經(jīng)濟效益最大.分析:以最經(jīng)濟的投入達到收益最大的目標.(或者說以直接出售土地和勞動力的方式達到收益最大的目標.1 求什么?土地成本價格 y1 勞動力成本價格 y22. 優(yōu)化什么?成本價格最低 Min g=50y1+20y23. 限制條件?蔬菜的市場價 y1+1/2y2110棉花的市場價 y1+1/3y2 7

8、5水稻的市場價 y1+1/4y260模型II .設(shè)決策變量: 對單位土地和對單位勞力投入成本價格分別為y1y2求目標函數(shù)g=50y1+20y2在約束條件y1+1/2y2 110 y1+1/3y2 75 y1+1/4y260 下的最小值.設(shè) A 是m n 矩陣,c 是n 1向量,b 是m 1向量x是n 1向量, y是1 m 向量問題: max f=c T x s.t. Ax b x i0, i=1,2,n.對偶問題: min f=yb s.t. yA c y i0, i=1,2,m.對偶定理: 互為對偶的兩個線性規(guī)劃問題, 若其中一個有有窮的最優(yōu)解, 則另一個也有有窮的最優(yōu)解, 且最優(yōu)值相等.

9、若兩者之一有無界的最優(yōu)解, 則另一個沒有可行解模型I II構(gòu)成對偶問題.模型I 解得最優(yōu)解(optimun solution X opt=(30 0 20, 最大值f(x opt=4500模型II 解得最優(yōu)解y opt=(10 200, 最小值g(y opt=4500.模型I 給出了生產(chǎn)中的資源最優(yōu)分配方案模型II 給出了生產(chǎn)中資源的最低估價.進一步問:如果增加對土地和勞動力的投入,每種資源的單位投入增加會帶來多少產(chǎn)值?由最優(yōu)解 y=(10,200 可見, 多耕一畝地增加10元收入,多一個勞動力增加200元收入。也就是說, 此時一個勞動力的估價為200元,而一畝土地估價為10元.這種價格涉及到

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)計劃是否應(yīng)馬上隨之改變? 參見線性規(guī)劃書籍將實際問題歸結(jié)為線性規(guī)劃模型是一個探

11、索創(chuàng)造的過程。線性規(guī)劃模型的求解仍是計算數(shù)學的一個難題。例 2 供貨問題一家公司生產(chǎn)某種商品. 現(xiàn)有n 個客戶, 第 j 個客戶需要貨物量至少為 bj,可在m 各不同地點設(shè)廠供貨. 在地區(qū) i 設(shè)廠的費用為 di , 供貨能力為 hi,向第 j 個客戶供應(yīng)單位數(shù)量的貨物費用為 c ij. 如何設(shè)廠與供貨使總費用最小.模型:設(shè)決策變量:x ij為在地區(qū)i向第j 個客戶供貨數(shù)量, 在地區(qū)i 設(shè)廠,記y i =1 , 否則記y i =0求目標函數(shù)f= i (j c ij x ij + y i d i 在約束條件i x ij =b j, j x ij -h i y i 0, x ij0, y i 0,

12、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

13、×4=1.3模型:設(shè)決策變量:按第i種方法截x i根鋼材。求目標函數(shù)f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8在約束條件2x1+x2+x3+x4=100 2x2+x4+2x5+3x6+x7=100 x1+2x3+x4+2x5+3x7+4x8=100 x i0 , i=1,8 下的最小值用Matlab程序解得x opt=(40, 20, 0, 0, 30, 0, 0, 0 , f (x opt = 7(實際上應(yīng)要求x i 為正整數(shù)。這是一個整數(shù)規(guī)劃問題。6.2 整數(shù)規(guī)劃如果要求決策變量取整數(shù), 或部分取整數(shù)的線性規(guī)劃問題, 稱為整數(shù)規(guī)劃.例 4 .

14、 飛船裝載問題設(shè)有n種不同類型的科學儀器希望裝在登月飛船上, 令c j>0表示每件第j 類儀器的科學價值;a j >0表示每件第j 類儀器的重量. 每類儀器件數(shù)不限, 但裝載件數(shù)只能是整數(shù). 飛船總載荷不得超過數(shù) b. 設(shè)計一種方案, 使得被裝載儀器的科學價值之和最大.建模記x j為第j 類儀器的裝載數(shù).求目標函數(shù)f= j c j x j在約束條件j a j x j b, x j 為正整數(shù), 下的最大值.用分枝定界法求解整數(shù)規(guī)劃問題基本思想:反復(fù)劃分可行域并確定最優(yōu)值的界限,將原問題不斷地分枝為若干個子問題, 且縮小最優(yōu)質(zhì)的取值范圍,直到求得最優(yōu)解.例:求目標函數(shù)f=3x1+2x2

15、在約束條件: 2x1+3x2 14, 2x1+x 2 9, x1 x 2為自然數(shù)下的最大值. 用Lindo軟件求解整數(shù)規(guī)劃max 3x1+2x2s.t.2x1+3x2<=142x1+x2<=9endgin x1gin x2(或者用gin 2 代替gin x1 gin x26.3 0-1規(guī)劃如果要求決策變量只取0 或1的線性規(guī)劃問題, 稱為0-1規(guī)劃.0-1 約束不一定是由變量的性質(zhì)決定的, 更多地是由于邏輯關(guān)系引進問題的例5 背包問題一個旅行者的背包最多只能裝6 kg 物品. 現(xiàn)有4 件物品的重量和價值分別為2 kg , 3 kg, 3 kg, 4 kg, 1 元, 1.2元, 0

16、.9元, 1.1元. 應(yīng)攜帶那些物品使得攜帶物品的價值最大?建模: 記x j為旅行者攜帶第j 件物品的件數(shù), 取值只能為0 或 1.求目標函數(shù)f=x 1 +1.2x 2 +0.9x 3 +1.1x 4 在約束條件2x 1 +3x 2 +3x 3 +4x 4 6下的最大值.用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)品要存放, 有些不能存放在一起, 有些能存放在一起的, 由于組合不

17、同所需費用不同. 求費用最低的儲存方案.實際問題 2 某航空公司在不同城市之間開辟了5 條航線, 一個航班可以飛不同的航線組合, 不同組合成本不同, 求開通所有航線且總費用最小的方案.抽象為集合覆蓋問題:設(shè)集合S=1,2,3,4,5 有一個子集類=1,2,1,3,5,2,4,5,3,1,4,5其中每一個元素對應(yīng)一個數(shù)c j , 稱為該元素的費用. 選的一個子集使其覆蓋S , 且總費用最低.即實際問題1中5種產(chǎn)品能存放在一起的各種組合為=1,2,1,3,5,2,4,5,3,1,4,5第 i 種組合的存儲費用為 c,j求這五種產(chǎn)品費用最低的儲存方案。模型: 設(shè)決策變量:設(shè)是S 的一個覆蓋(一種存儲方案. 當?shù)牡趇 個元素屬于, (即第i 種組合被采用記x i=1,否則x i=0求目標函數(shù)f= i c i x i在約束條件x1 +x2+ x51 x1 + x31 (因為第2種產(chǎn)品只在第1,3個組合中出現(xiàn)x2+ x41 x3 + x6 1 x2+x3 + x6 1 x i0,1,I=1,2, ,6, 下的最小值.6.4 多目標線性規(guī)劃目標函數(shù)f k=c (kT x k=1,2, , m,s.t. Ax bA1x=b1LB x UB有最優(yōu)解x (k, 記 f (k =