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

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年蘇聯(lián)數(shù)學(xué)家康托洛維奇發(fā)表生產(chǎn)組織與計劃中的數(shù)學(xué)問題 1947年美國數(shù)學(xué)家喬治.丹契克、馮.諾伊曼提出線性規(guī)劃的一般模型及理論.1. 問題例1 作物種植安排 一個農(nóng)場有50畝土地, 20個勞動力, 計劃種蔬菜,棉花和水稻. 種植這三種農(nóng)作物每畝地分別需要勞動力 1/2 1/3 1/4, 預(yù)計每畝產(chǎn)值分別為 110元, 75元, 60元. 如何規(guī)劃經(jīng)營使

2、經(jīng)濟效益最大. 分析：以取得最高的產(chǎn)值的方式達到收益最大的目標.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個組成要素:

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ù)取不同的目標值時，

4、構(gòu)成一族平行直線,目標值的大小描述了直線離原點的遠近。于是穿過可行域的目標直線組中最遠離(或接近)原點的直線所穿過的凸多邊形的頂點即為取的極值的極點最優(yōu)解。單純形法 : 通過確定約束方程組的基本解, 并計算相應(yīng)目標函數(shù)值, 在可行解集的極點中搜尋最優(yōu)解. 正則模型: 決策變量: x1,x2,xn. 目標函數(shù): z=c1x1+c2x2+cnxn. 約束條件: a11x1+a1nxnb1, am1x1+amnxnbm,模型的標準化10. 引入松弛變量將不等式約束變?yōu)榈仁郊s束. 若有 ai1x1+ainxnbi, 則引入 xn+i 0, 使得 ai1x1+ainxn+ xn+i =bi 若有 aj1

5、x1+ajnxnbj, 則引入 xn+j 0, 使得 aj1x1+ajnxn- 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, am1x1+ amnxn= bm

6、, x1 0, xn 0, 定義: 若代數(shù)方程ax=b的解向量有n-m個分量為零, 其余m個分量對應(yīng)a的m個線性無關(guān)列, 則稱該解向量為方程組的一個基本解.在一個線性規(guī)劃問題中, 如果一個可行解也是約束方程組的基本解, 則稱之為基本可行解. 命題 4 一個向量 x 是線性規(guī)劃問題可行解集的一個極點, 當且僅當它是約束方程的一個基本可行解。于是尋找取得極值的凸集極點的幾何問題變成了求代數(shù)方程基本解的問題，形成了解優(yōu)化問題的單純形方法，改進單純形方法等。按這些計算方法編制程序，產(chǎn)生了專門解優(yōu)化問題的軟件 lindo、lingo 。 用matlab求解：標準的線性規(guī)劃的模型： min f=ctxs.

7、t. ax b a1x=b1 lb x ubmatlab求解程序: x,f=linprog(c,a,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)化什么？ 成本價格最低 mi

8、n g=50y1+20y2 3. 限制條件？蔬菜的市場價 y1+1/2y2 110棉花的市場價 y1+1/3y2 75水稻的市場價 y1+1/4y2 60模型 ii . 設(shè)決策變量: 對單位土地和對單位勞力投入成本價格分別為 y1 y2求目標函數(shù) g=50y1+20y2在約束條件 y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60 下的最小值.設(shè) a 是m n 矩陣， c 是 n 1向量，b 是 m 1向量x是 n 1向量, y是1 m 向量問題: max f=ctx s.t. ax b xi0, i=1,2,n.對偶問題: min f=yb s.t. ya c yi0,

9、 i=1,2,m.對偶定理: 互為對偶的兩個線性規(guī)劃問題, 若其中一個有有窮的最優(yōu)解, 則另一個也有有窮的最優(yōu)解, 且最優(yōu)值相等. 若兩者之一有無界的最優(yōu)解, 則另一個沒有可行解模型 i ii構(gòu)成對偶問題.模型 i 解得最優(yōu)解(optimun solution) xopt=(30 0 20), 最大值 f(xopt)=4500模型 ii 解得最優(yōu)解 yopt=(10 200), 最小值 g(yopt)=4500.模型i 給出了生產(chǎn)中的資源最優(yōu)分配方案模型 ii 給出了生產(chǎn)中資源的最低估價. 進一步問：如果增加對土地和勞動力的投入，每種資源的單位投入增加會帶來多少產(chǎn)值？由最優(yōu)解 y=(10,20

10、0) 可見, 多耕一畝地增加10元收入，多一個勞動力增加200元收入。也就是說, 此時一個勞動力的估價為200元,而一畝土地估價為10元.這種價格涉及到資源的有效利用, 它不是市場價格, 而是根據(jù)資源在生產(chǎn)中做出的貢獻確定的估價, 被稱為“影子價格”. 再進一步問，棉花價格提高到多少才值的生產(chǎn)？ 由 y1+1/3y2=10+200/3=76.675, （而其它兩個約束條件是等式）可見，只有當棉花價格提高到 76.6元時才值得生產(chǎn).4 靈敏度分析當線性規(guī)劃問題中的常數(shù)發(fā)生變化(由于測量誤差或具有多個取值可能)時, 最優(yōu)解是否會隨之變化?通常假定變化的常數(shù)是某參數(shù)的線性函數(shù).討論參數(shù)取值與最優(yōu)解的

11、關(guān)系的問題, 被稱為參數(shù)線性規(guī)劃. 例如, 當農(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è)廠供貨. 在地區(qū) i 設(shè)廠的費用為 di , 供貨能力為 hi , 向第 j 個客戶供應(yīng)單位數(shù)量的貨物費用為 cij. 如何設(shè)廠與供貨使總費用最小.模型： 設(shè)決策變量： xij 為在地區(qū) i 向第 j 個客戶供貨數(shù)量, 在地區(qū) i 設(shè)廠，記 yi =1 , 否則 記 yi

12、 =0 求 目標函數(shù) f= i (j cij xij + yi 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種 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)

13、=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模型：設(shè)決策變量：按第i種方法截 xi 根鋼材。求目標函數(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 xi 0 , i=1,8 下的最小值用matlab程序解得 xopt=(40, 20, 0, 0, 30, 0, 0, 0) , f (xopt )= 7 （實際上應(yīng)要求xi 為正整數(shù)。這是一

14、個整數(shù)規(guī)劃問題）。 6.2 整數(shù)規(guī)劃如果要求決策變量取整數(shù), 或部分取整數(shù)的線性規(guī)劃問題, 稱為整數(shù)規(guī)劃.例 4 . 飛船裝載問題 設(shè)有n種不同類型的科學(xué)儀器希望裝在登月飛船上, 令cj0表示每件第 j 類儀器的科學(xué)價值; aj 0表示每件第 j 類儀器的重量. 每類儀器件數(shù)不限, 但裝載件數(shù)只能是整數(shù). 飛船總載荷不得超過數(shù) b. 設(shè)計一種方案, 使得被裝載儀器的科學(xué)價值之和最大.建模 記 xj 為第 j 類儀器的裝載數(shù). 求 目標函數(shù) f= j cj xj 在約束條件 jaj xj b, xj 為正整數(shù), 下的最大值.用分枝定界法求解整數(shù)規(guī)劃問題基本思想:反復(fù)劃分可行域并確定最優(yōu)值的界限,

15、將原問題不斷地分枝為若干個子問題, 且縮小最優(yōu)質(zhì)的取值范圍,直到求得最優(yōu)解. 例:求目標函數(shù) f=3x1+2x2 在約束條件: 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 x2)6.3 0-1規(guī)劃 如果要求決策變量只取0 或 1的線性規(guī)劃問題, 稱為0-1規(guī)劃. 0-1 約束不一定是由變量的性質(zhì)決定的, 更多地是由于邏輯關(guān)系引進問題的例5 背包問題 一個旅行者的背包最多只能裝 6 kg 物品

16、. 現(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.求目標函數(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)

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

18、,2,4,5,3,1,4,5第 i 種組合的存儲費用為 cj , 求這五種產(chǎn)品費用最低的儲存方案。模型: 設(shè)決策變量：設(shè)df是 s 的一個覆蓋（一種存儲方案）. 當f的第 i 個元素屬于d, （即第 i 種組合被采用）記 xi=1，否則xi=0求 目標函數(shù) f= si cixi在約束條件 x1 +x2 + x51 x1 + x3 1 (因為第2種產(chǎn)品只在第1，3個組合中出現(xiàn)) x2 + x4 1 x3 + x6 1 x2 +x3 + x6 1 xi0，1， i=1,2, ,6, 下的最小值.6.4 多目標線性規(guī)劃目標函數(shù) fk=c (k)t x k=1,2, , m,s.t. ax b a1x=b1 lb x ub有最優(yōu)解 x (k), 記 f (k) =f(x (k)整體評價法min s=s(f