常用數(shù)學(xué)模型及建模方法優(yōu)化問題與模型

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

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

3、性規(guī)劃問題,否則稱為非線性規(guī)劃問題。2.線性規(guī)劃問題求解方法稱滿足約束條件的向量為可行解,稱可行解的集合為可行域,稱使目標(biāo)函數(shù)達(dá)最值的可行解為最優(yōu)解.命題 1 線性規(guī)劃問題的可行解集是凸集.因為可行解集由線性不等式組的解面上的凸多邊形。兩個變量的線性規(guī)劃問題的可行解集是平命題 2線性規(guī)劃問題的最優(yōu)解一定在可行解集的某個極點上達(dá)到.圖解法： 解兩個變量的線性規(guī)劃問題，在平面上畫出可行域，計算目標(biāo)函數(shù)在各極點處的值，經(jīng)比較后，取最值點為最優(yōu)解。命題 3 當(dāng)兩個變量的線性規(guī)劃問題的目標(biāo)函數(shù)取不同的目標(biāo)值時，線,目標(biāo)值的大小描述了直線離原點的遠(yuǎn)近。一族平行直于是穿過可行域的目標(biāo)直線組中最遠(yuǎn)離(或接近)

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

5、+0 xn+1+0 xn+m.20. 將目標(biāo)函數(shù)的優(yōu)化變?yōu)槟繕?biāo)函數(shù)的極大化. 若求變?yōu)?max Z .min Z, 令 Z=Z, 則問題30. 引入人工變量,使得所有變量均為非負(fù). 若沒有非負(fù)的條件,則引入xixi0 和xi0,令xi= xi xi,則可使得問題的全部變量均非負(fù).標(biāo)準(zhǔn)化模型求變量x1, x2, xn,max Z =c1x1+ cnxn,s. t.a11x1+ a1nxn=b1,bm,xn am1x1+ amnxn=x1 0,0,定義: 若代數(shù)方程 AX=B 的解向量有 n-m 個分量為零, 其余 m 個分量對應(yīng) A 的 m個線性無關(guān)列, 則稱該解向量為方程組的一個基本解.在一個

6、線性規(guī)劃問題中, 如果一個可行解也是約束方程組的基本解, 則稱之為基本可行解.命題 4一個向量 x 是線性規(guī)劃問題可行解集的一個極點,當(dāng)且僅當(dāng)它是約束方程的一個基本可行解。于是尋找取得極值的凸集極點的幾何問題變成了求代數(shù)方程基本解的問題，形成了解優(yōu)化問題的單純形方法，改進(jìn)單純形方法等。按這些計算方法編制程序，產(chǎn)生了專門解優(yōu)化問題的軟件 Lindo、Lingo。用求解：標(biāo)準(zhǔn)的線性規(guī)劃的模型：min f=cTxs.t. Ax bA1x=b1LB x UB求解程序:x,f=linprog(c,A,b,A1,b1,LB,UB)還有軟件 Excel也可應(yīng)用于解優(yōu)化問題。3 對偶問題例 1 作物種植安排一

7、個農(nóng)場有50 畝土地,20 個勞動力,計劃種蔬菜,棉花和水稻. 種植這三種農(nóng)作物每畝地分別需要勞動力 1/21/3 1/4, 預(yù)計每畝產(chǎn)值分別為 110 元, 75 元, 60 元.如何規(guī)劃經(jīng)營使經(jīng)濟(jì)效益最大.分析：以最經(jīng)濟(jì)的投入達(dá)到的目標(biāo).（或者說以直接出售土地和勞動力的方式達(dá)到的目標(biāo).）1 求什么？土地成本價格勞動力成本價格y1y2優(yōu)化什么？限制條件？蔬菜的市場價棉花的市場價水稻的市場價模型 II .成本價格最低 Ming=50y1+20y2y1+1/2y2 110 75 60y1+1/3y2 y1+1/4y2設(shè)決策變量:對土地和對勞力投入成本價格分別為y1y2求目標(biāo)函數(shù)在約束條件g=50

8、y1+20y2y1+1/2y2 110 75 60 下的最小值.y1+1/3y2y1+1/4y2設(shè) A 是m n 矩陣，c 是 n m 1 向量，b 是1 向量m 向量x 是 n 1 向量,問題:max f=cTxy 是 1 s.t. Ax bxi0,i=1,2,n.s.t. yA cyi0,i=1,2,m.對偶問題:min f=yb對偶定理:互為對偶的兩個線性規(guī)劃問題, 若其中一個有有窮的最優(yōu)解, 則另一個也有有窮的最優(yōu)解,且最優(yōu)值相等. 若兩者之一有有可行解的最優(yōu)解,則另一個沒模型 III模型 I對偶問題.解得最優(yōu)解 (optimun solution)Xopt=(300 20),最大值

9、f(xopt)=4500模型 II解得最優(yōu)解yopt=(10200),最小值g(yopt)=4500.模型I給出了生產(chǎn)中的資源最優(yōu)分配方案模型 II給出了生產(chǎn)中資源的最低估價.進(jìn)一步問：如果增加對土地和勞動力的投入，每種資源的產(chǎn)值？投入增加會帶來多少由最優(yōu)解 y=(10,200) 可見, 多耕一畝地增加 10 元收入，多一個勞動力增加 200元收入。也就是說, 此時一個勞動力的估價為 200 元,而一畝土地估價為 10 元.這種價格涉及到資源的有效利用,它不是市場價格,而是根據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)確定的估價,被稱為“價格”.再進(jìn)一步問，棉花價格提高到多少才值的生產(chǎn)？由y1+1/3y2=10+

10、200/3=76.675,（而其它兩個約束條件是等式）可見，只有當(dāng)棉花價格提高到 76.6 元時才值得生產(chǎn).4 靈敏度分析當(dāng)線性規(guī)劃問題中的常數(shù)發(fā)生變化(由于測量誤差或具有多個取值可能)時, 最優(yōu)解是否會隨之變化?通常假定變化的常數(shù)是某參數(shù)的線性函數(shù).被稱為參數(shù)線性規(guī)劃.參數(shù)取值與最優(yōu)解的關(guān)系的問題,例如, 當(dāng)農(nóng)作物的價格發(fā)生變化時, 生產(chǎn)計劃是否應(yīng)馬上隨之改變?劃書籍參見線性規(guī)將實際問題歸結(jié)為線性規(guī)劃模型是一個探索創(chuàng)造的過程。線性規(guī)劃模型的求解仍是計算數(shù)學(xué)的一個難題。例 2 供貨問題一家公司生產(chǎn)某種商品. 現(xiàn)有n 個客戶,第 j 個客戶需要貨物量至少為bj,可在m 各不同地點設(shè)廠供貨. 在地

11、區(qū) i 設(shè)廠的費用為, 供貨能力為,dihi向第 j 個客戶供應(yīng)數(shù)量的貨物費用為cij.如何設(shè)廠與供貨使總費用最小.模型：廠，記設(shè)決策變量：為在地區(qū) i 向第 jxij個客戶供貨數(shù)量,在地區(qū) i 設(shè)yi=1 , 否則 記=0yi求 目標(biāo)函數(shù)f= i (j cij xijyi di )+i xij = bj,j xij -hi yi 0,xij0,yi 0，1在約束條件值下的最小例 3 鋼材截短有一批鋼材,每根長 7.3 米. 現(xiàn)需做 100 套短鋼材.每套包括長 2.9 米, 2.1米,1.5 米的各一根.至少用掉多少根鋼材才能滿足需要, 并使得用料最省.分析：第 1 種第 2 種第 3 種第

12、 4 種第 5 種第 6 種第 7 種第 8 種可能的截法和余料7.3-(2.9 2+1.5)=07.3-(2.9+2.1 2)=0.27.3-(2.9+1.5 2)=1.47.3-(2.9+2.1+1.5)=0.87.3-(2.1 2+1.5 2)=0.17.3-(2.1 3)=17.3-(2.1+1.5 3)=0.77.3-(1.5 4)=1.3模型：設(shè)決策變量：按第i 種方法截根鋼材。xi求目標(biāo)函數(shù)在約束條件f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x82x1+x2+x3+x4=1002x2+x4+2x5+3x6+x7=100 x1+2x3+x4+2x5

13、+3x7+4x8=1000 ,i=1,8 下的最小值xi用程序解得xopt=(40,20,0,0, 30,0, 0,0) ,f(xopt)= 7（實際上應(yīng)要求xi為正整數(shù)。這是一個整數(shù)規(guī)劃問題）。6.2 整數(shù)規(guī)劃如果要求決策變量取整數(shù), 或部分取整數(shù)的線性規(guī)劃問題,例 4 . 飛船裝載問題稱為整數(shù)規(guī)劃.設(shè)有 n 種不同類型的科學(xué)儀器希望裝在登月飛船上,令 cj0 表示每件第每類儀器件數(shù)不限,j 類儀但裝器的科學(xué)價值;aj0 表示每件第 j 類儀器的重量.載件數(shù)只能是整數(shù).飛船總載荷不得超過數(shù) b. 設(shè)計案,使得被裝載儀器的科學(xué)價值之和最大.建模記為第 j 類儀器的裝載數(shù).xjj cj xjja

14、j xj b,求 目標(biāo)函數(shù) f=在約束條件xj 為正整數(shù),下的最大值.用分枝定界法求解整數(shù)規(guī)劃問題基本:反復(fù)劃分可行域并確定最優(yōu)值的界限,將原問題不斷地分枝為若干個子問題, 且縮小最優(yōu)質(zhì)的取值范圍,直到求得最優(yōu)解.2x1+3x2 14, 2x1+x 2 例:求目標(biāo)函數(shù)數(shù)下的最大值.f=3x1+2x2在約束條件:9,x12 為自然x用 Lindo 軟件求解整數(shù)規(guī)劃max 3x1+2x2 s.t.2x1+3x2=142x1+x2=9endginx1ginx2(或者用 gin 2 代替 ginx1 ginx2)6.3 0-1 規(guī)劃如果要求決策變量只取 0 或 1 的線性規(guī)劃問題, 稱為 0-1 規(guī)劃

15、.0-1 約束不一定是由變量的性質(zhì)決定的,地是由于邏輯關(guān)系引進(jìn)問題的例 5背包問題一個旅行者的背包最多只能裝 6 kg 物品. 現(xiàn)有 4 件物品的重量和價值分別為2 kg , 3 kg,3 kg,4 kg,1 元, 1.2 元, 0.9 元, 1.1 元. 應(yīng)攜帶那些物品使得攜帶物品的價值最大?建模:記xj 為旅行者攜帶第j 件物品的件數(shù),取值只能為 0 或 1.2x +3x +3x+4x 6求目標(biāo)函數(shù) f=x下的最大值.1 +1.2x 2 +0.9x 3 +1.1x 4 在約束條件1234用 Lingo 軟件求解 0-1 規(guī)劃M:Max=x1+1.2*x2+0.9*x3+1.1*x4; 2*

16、x1+3*x2+3*x3+4*x4=6; end(x1);(x2);(x3);(x4);例6集合覆蓋問題實際問題 1 某企業(yè)有 5 種產(chǎn)品要存放,有些不能存放在一起,有些能存放在一起的,由于組合不同所需費用不同.求費用最低 的儲存方案.實際問題2 某航空公司在不同城市之間開辟了 5 條航線,一個航班可以飛不同的航線組合,不同組本不同, 求開通所有航線且總費用最小的方案.抽象為集合覆蓋問題：設(shè)集合S=1,2,3,4,5有一個子集類=1,2,1,3,5,2,4,5,3,1,4,5其中每一個元素對應(yīng)一個數(shù), 稱cj為該元素的費用. 選 的一個子集使其覆蓋S ,且總費用最低.即實際問題 1 中 5 種

17、產(chǎn)品能存放在一起的各種組合為=1,2,1,3,5,2,4,5,3,1,4,5第求這五種產(chǎn)品費用最低的儲存方案。i種組合的費用為,cj模型: 設(shè)決策變量：設(shè)是 S 的一個覆蓋（一種方案）. 當(dāng)?shù)牡?i 個元素屬于, （即第 i 種組合被采用）記xi=1，否則 xi=0i cixi求 目標(biāo)函數(shù)在約束條件合中出現(xiàn))f=x1 +x2x51+1+x1x3(因為第 2 種產(chǎn)品只在第 1，3 個組+1x3x6 1+x3x6 1xi0，1，I=1,2, ,6,x2x4小值.+x2+下的最6.4多目標(biāo)線性規(guī)劃k=1,2, , m,Tfk=c (k)目標(biāo)函數(shù)xs.t. Ax b A1x=b1LB x UB有最優(yōu)解 x整體評價法 min S=(fs.t. Ax b A1x=b1記 f(k) =f(x (k)(k),Tc(k)-x