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

1、3.6 優(yōu)化問題與規(guī)劃模型與最大、最小、最長(zhǎng)、最短等等有關(guān)的問題都是優(yōu)化問題。解決優(yōu)化問題形成管理科學(xué)的數(shù)學(xué)方法： 運(yùn)籌學(xué)。 運(yùn)籌學(xué)主要分支： （非）線性規(guī)劃、動(dòng)態(tài)規(guī)劃、圖與網(wǎng)絡(luò)分析、存貯學(xué)、排隊(duì)倫、對(duì)策論、決策論。6.1 線性規(guī)劃1939 年1947 年數(shù)學(xué)家康托 數(shù)學(xué)家.生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)問題、馮.提出線性規(guī)劃的一般模型論.1.問題例 1 作物種植安排一個(gè)農(nóng)場(chǎng)有50 畝土地,20 個(gè)勞動(dòng)力,計(jì)劃種蔬菜,棉花和水稻. 種植這三種農(nóng)作物每畝地分別需要?jiǎng)趧?dòng)力 1/21/3 1/4, 預(yù)計(jì)每畝產(chǎn)值分別為 110 元, 75 元, 60 元.如何規(guī)劃經(jīng)營(yí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 個(gè)組成要素: 決策變量、目標(biāo)函數(shù)、約束條件。當(dāng)目標(biāo)函數(shù)和約束條件都是決策變量的線性函數(shù)時(shí)，稱為線

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

4、原點(diǎn)的直線所穿過的凸多邊形的頂點(diǎn)即為取的極值的極點(diǎn)最優(yōu)解。單純形法 : 通過確定約束方程組的基本解, 并計(jì)算相應(yīng)目標(biāo)函數(shù)值,在可行解集的極點(diǎn)中搜尋最優(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 個(gè)分量為零, 其余 m 個(gè)分量對(duì)應(yīng) A 的 m個(gè)線性無關(guān)列, 則稱該解向量為方程組的一個(gè)基本解.在一個(gè)

6、線性規(guī)劃問題中, 如果一個(gè)可行解也是約束方程組的基本解, 則稱之為基本可行解.命題 4一個(gè)向量 x 是線性規(guī)劃問題可行解集的一個(gè)極點(diǎn),當(dāng)且僅當(dāng)它是約束方程的一個(gè)基本可行解。于是尋找取得極值的凸集極點(diǎn)的幾何問題變成了求代數(shù)方程基本解的問題，形成了解優(yōu)化問題的單純形方法，改進(jìn)單純形方法等。按這些計(jì)算方法編制程序，產(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 對(duì)偶問題例 1 作物種植安排一

7、個(gè)農(nóng)場(chǎng)有50 畝土地,20 個(gè)勞動(dòng)力,計(jì)劃種蔬菜,棉花和水稻. 種植這三種農(nóng)作物每畝地分別需要?jiǎng)趧?dòng)力 1/21/3 1/4, 預(yù)計(jì)每畝產(chǎn)值分別為 110 元, 75 元, 60 元.如何規(guī)劃經(jīng)營(yíng)使經(jīng)濟(jì)效益最大.分析：以最經(jīng)濟(jì)的投入達(dá)到的目標(biāo).（或者說以直接出售土地和勞動(dòng)力的方式達(dá)到的目標(biāo).）1 求什么？土地成本價(jià)格勞動(dòng)力成本價(jià)格y1y2優(yōu)化什么？限制條件？蔬菜的市場(chǎng)價(jià)棉花的市場(chǎng)價(jià)水稻的市場(chǎng)價(jià)模型 II .成本價(jià)格最低 Ming=50y1+20y2y1+1/2y2 110 75 60y1+1/3y2 y1+1/4y2設(shè)決策變量:對(duì)土地和對(duì)勞力投入成本價(jià)格分別為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.對(duì)偶問題:min f=yb對(duì)偶定理:互為對(duì)偶的兩個(gè)線性規(guī)劃問題, 若其中一個(gè)有有窮的最優(yōu)解, 則另一個(gè)也有有窮的最優(yōu)解,且最優(yōu)值相等. 若兩者之一有有可行解的最優(yōu)解,則另一個(gè)沒模型 III模型 I對(duì)偶問題.解得最優(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)中資源的最低估價(jià).進(jìn)一步問：如果增加對(duì)土地和勞動(dòng)力的投入，每種資源的產(chǎn)值？投入增加會(huì)帶來多少由最優(yōu)解 y=(10,200) 可見, 多耕一畝地增加 10 元收入，多一個(gè)勞動(dòng)力增加 200元收入。也就是說, 此時(shí)一個(gè)勞動(dòng)力的估價(jià)為 200 元,而一畝土地估價(jià)為 10 元.這種價(jià)格涉及到資源的有效利用,它不是市場(chǎng)價(jià)格,而是根據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)確定的估價(jià),被稱為“價(jià)格”.再進(jìn)一步問，棉花價(jià)格提高到多少才值的生產(chǎn)？由y1+1/3y2=10+

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

11、區(qū) i 設(shè)廠的費(fèi)用為, 供貨能力為,dihi向第 j 個(gè)客戶供應(yīng)數(shù)量的貨物費(fèi)用為cij.如何設(shè)廠與供貨使總費(fèi)用最小.模型：廠，記設(shè)決策變量：為在地區(qū) i 向第 jxij個(gè)客戶供貨數(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 鋼材截短有一批鋼材,每根長(zhǎng) 7.3 米. 現(xiàn)需做 100 套短鋼材.每套包括長(zhǎng) 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（實(shí)際上應(yīng)要求xi為正整數(shù)。這是一個(gè)整數(shù)規(guī)劃問題）。6.2 整數(shù)規(guī)劃如果要求決策變量取整數(shù), 或部分取整數(shù)的線性規(guī)劃問題,例 4 . 飛船裝載問題稱為整數(shù)規(guī)劃.設(shè)有 n 種不同類型的科學(xué)儀器希望裝在登月飛船上,令 cj0 表示每件第每類儀器件數(shù)不限,j 類儀但裝器的科學(xué)價(jià)值;aj0 表示每件第 j 類儀器的重量.載件數(shù)只能是整數(shù).飛船總載荷不得超過數(shù) b. 設(shè)計(jì)案,使得被裝載儀器的科學(xué)價(jià)值之和最大.建模記為第 j 類儀器的裝載數(shù).xjj cj xjja

14、j xj b,求 目標(biāo)函數(shù) f=在約束條件xj 為正整數(shù),下的最大值.用分枝定界法求解整數(shù)規(guī)劃問題基本:反復(fù)劃分可行域并確定最優(yōu)值的界限,將原問題不斷地分枝為若干個(gè)子問題, 且縮小最優(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背包問題一個(gè)旅行者的背包最多只能裝 6 kg 物品. 現(xiàn)有 4 件物品的重量和價(jià)值分別為2 kg , 3 kg,3 kg,4 kg,1 元, 1.2 元, 0.9 元, 1.1 元. 應(yīng)攜帶那些物品使得攜帶物品的價(jià)值最大?建模:記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集合覆蓋問題實(shí)際問題 1 某企業(yè)有 5 種產(chǎn)品要存放,有些不能存放在一起,有些能存放在一起的,由于組合不同所需費(fèi)用不同.求費(fèi)用最低 的儲(chǔ)存方案.實(shí)際問題2 某航空公司在不同城市之間開辟了 5 條航線,一個(gè)航班可以飛不同的航線組合,不同組本不同, 求開通所有航線且總費(fèi)用最小的方案.抽象為集合覆蓋問題：設(shè)集合S=1,2,3,4,5有一個(gè)子集類=1,2,1,3,5,2,4,5,3,1,4,5其中每一個(gè)元素對(duì)應(yīng)一個(gè)數(shù), 稱cj為該元素的費(fèi)用. 選 的一個(gè)子集使其覆蓋S ,且總費(fèi)用最低.即實(shí)際問題 1 中 5 種

17、產(chǎn)品能存放在一起的各種組合為=1,2,1,3,5,2,4,5,3,1,4,5第求這五種產(chǎn)品費(fèi)用最低的儲(chǔ)存方案。i種組合的費(fèi)用為,cj模型: 設(shè)決策變量：設(shè)是 S 的一個(gè)覆蓋（一種方案）. 當(dāng)?shù)牡?i 個(gè)元素屬于, （即第 i 種組合被采用）記xi=1，否則 xi=0i cixi求 目標(biāo)函數(shù)在約束條件合中出現(xiàn))f=x1 +x2x51+1+x1x3(因?yàn)榈?2 種產(chǎn)品只在第 1，3 個(gè)組+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整體評(píng)價(jià)法 min S=(fs.t. Ax b A1x=b1記 f(k) =f(x (k)(k),Tc(k)-x