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

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

2、經(jīng)濟(jì)效益最大. 分析：以取得最高的產(chǎn)值的方式達(dá)到收益最大的目標(biāo).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 畝，求目標(biāo)函數(shù) f=110x1+75x2+60x3在約束條件x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 下的最大值規(guī)劃問(wèn)題：求目標(biāo)函數(shù)在約束條件下的最值,規(guī)劃問(wèn)題包含3個(gè)組成要素:

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

4、構(gòu)成一族平行直線,目標(biāo)值的大小描述了直線離原點(diǎn)的遠(yuǎn)近。于是穿過(guò)可行域的目標(biāo)直線組中最遠(yuǎn)離(或接近)原點(diǎn)的直線所穿過(guò)的凸多邊形的頂點(diǎn)即為取的極值的極點(diǎn)最優(yōu)解。單純形法 : 通過(guò)確定約束方程組的基本解, 并計(jì)算相應(yīng)目標(biāo)函數(shù)值, 在可行解集的極點(diǎn)中搜尋最優(yōu)解. 正則模型: 決策變量: x1,x2,xn. 目標(biāo)函數(shù): z=c1x1+c2x2+cnxn. 約束條件: a11x1+a1nxnb1, am1x1+amnxnbm,模型的標(biāo)準(zhǔn)化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. 將目標(biāo)函數(shù)的優(yōu)化變?yōu)槟繕?biāo)函數(shù)的極大化. 若求 min z, 令 z=z, 則問(wèn)題變?yōu)?max z .30. 引入人工變量,使得所有變量均為非負(fù). 若 xi 沒(méi)有非負(fù)的條件,則引入 xi 0 和 xi0, 令 xi= xi xi, 則可使得問(wèn)題的全部變量均非負(fù). 標(biāo)準(zhǔn)化模型 求變量 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個(gè)分量為零, 其余m個(gè)分量對(duì)應(yīng)a的m個(gè)線性無(wú)關(guān)列, 則稱該解向量為方程組的一個(gè)基本解.在一個(gè)線性規(guī)劃問(wèn)題中, 如果一個(gè)可行解也是約束方程組的基本解, 則稱之為基本可行解. 命題 4 一個(gè)向量 x 是線性規(guī)劃問(wèn)題可行解集的一個(gè)極點(diǎn), 當(dāng)且僅當(dāng)它是約束方程的一個(gè)基本可行解。于是尋找取得極值的凸集極點(diǎn)的幾何問(wèn)題變成了求代數(shù)方程基本解的問(wèn)題，形成了解優(yōu)化問(wèn)題的單純形方法，改進(jìn)單純形方法等。按這些計(jì)算方法編制程序，產(chǎn)生了專門解優(yōu)化問(wèn)題的軟件 lindo、lingo 。 用matlab求解：標(biāo)準(zhǔn)的線性規(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)化問(wèn)題。3 對(duì)偶問(wèn)題例1 作物種植安排 一個(gè)農(nóng)場(chǎng)有50畝土地, 20個(gè)勞動(dòng)力, 計(jì)劃種蔬菜,棉花和水稻. 種植這三種農(nóng)作物每畝地分別需要?jiǎng)趧?dòng)力 1/2 1/3 1/4, 預(yù)計(jì)每畝產(chǎn)值分別為 110元, 75元, 60元. 如何規(guī)劃經(jīng)營(yíng)使經(jīng)濟(jì)效益最大. 分析：以最經(jīng)濟(jì)的投入達(dá)到收益最大的目標(biāo).（或者說(shuō)以直接出售土地和勞動(dòng)力的方式達(dá)到收益最大的目標(biāo).）1 求什么？土地成本價(jià)格 y1 勞動(dòng)力成本價(jià)格 y22. 優(yōu)化什么？ 成本價(jià)格最低 mi

8、n g=50y1+20y2 3. 限制條件？蔬菜的市場(chǎng)價(jià) y1+1/2y2 110棉花的市場(chǎng)價(jià) y1+1/3y2 75水稻的市場(chǎng)價(jià) y1+1/4y2 60模型 ii . 設(shè)決策變量: 對(duì)單位土地和對(duì)單位勞力投入成本價(jià)格分別為 y1 y2求目標(biāo)函數(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 向量問(wèn)題: max f=ctx s.t. ax b xi0, i=1,2,n.對(duì)偶問(wèn)題: min f=yb s.t. ya c yi0,

9、 i=1,2,m.對(duì)偶定理: 互為對(duì)偶的兩個(gè)線性規(guī)劃問(wèn)題, 若其中一個(gè)有有窮的最優(yōu)解, 則另一個(gè)也有有窮的最優(yōu)解, 且最優(yōu)值相等. 若兩者之一有無(wú)界的最優(yōu)解, 則另一個(gè)沒(méi)有可行解模型 i ii構(gòu)成對(duì)偶問(wèn)題.模型 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)中資源的最低估價(jià). 進(jìn)一步問(wèn)：如果增加對(duì)土地和勞動(dòng)力的投入，每種資源的單位投入增加會(huì)帶來(lái)多少產(chǎn)值？由最優(yōu)解 y=(10,20

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

11、關(guān)系的問(wèn)題, 被稱為參數(shù)線性規(guī)劃. 例如, 當(dāng)農(nóng)作物的價(jià)格發(fā)生變化時(shí), 生產(chǎn)計(jì)劃是否應(yīng)馬上隨之改變? 參見(jiàn)線性規(guī)劃書籍將實(shí)際問(wèn)題歸結(jié)為線性規(guī)劃模型是一個(gè)探索創(chuàng)造的過(guò)程。線性規(guī)劃模型的求解仍是計(jì)算數(shù)學(xué)的一個(gè)難題。例 2 供貨問(wèn)題一家公司生產(chǎn)某種商品. 現(xiàn)有n 個(gè)客戶, 第 j 個(gè)客戶需要貨物量至少為 bj, 可在m 各不同地點(diǎn)設(shè)廠供貨. 在地區(qū) i 設(shè)廠的費(fèi)用為 di , 供貨能力為 hi , 向第 j 個(gè)客戶供應(yīng)單位數(shù)量的貨物費(fèi)用為 cij. 如何設(shè)廠與供貨使總費(fèi)用最小.模型： 設(shè)決策變量： xij 為在地區(qū) i 向第 j 個(gè)客戶供貨數(shù)量, 在地區(qū) i 設(shè)廠，記 yi =1 , 否則 記 yi

12、 =0 求 目標(biāo)函數(shù) f= i (j cij xij + yi 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種 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 根鋼材。求目標(biāo)函數(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 （實(shí)際上應(yīng)要求xi 為正整數(shù)。這是一

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

15、將原問(wèn)題不斷地分枝為若干個(gè)子問(wèn)題, 且縮小最優(yōu)質(zhì)的取值范圍,直到求得最優(yōu)解. 例:求目標(biāo)函數(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ī)劃問(wèn)題, 稱為0-1規(guī)劃. 0-1 約束不一定是由變量的性質(zhì)決定的, 更多地是由于邏輯關(guān)系引進(jìn)問(wèn)題的例5 背包問(wèn)題 一個(gè)旅行者的背包最多只能裝 6 kg 物品

16、. 現(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.求目標(biāo)函數(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 集合覆蓋問(wèn)題實(shí)際問(wèn)題 1 某企業(yè)有5種產(chǎn)品要存放, 有些不能存放在一起, 有些能存放在一起的, 由于組合不同所需費(fèi)用不同. 求費(fèi)用最低 的儲(chǔ)存方案. 實(shí)際問(wèn)題 2 某航空公司在不同城市之間開(kāi)辟了5 條航線, 一個(gè)航班可以飛不同的航線組合, 不同組合成本不同, 求開(kāi)通所有航線且總費(fèi)用最小的方案.抽象為集合覆蓋問(wèn)題：設(shè)集合 s=1,2,3,4,5 有一個(gè)子集類f=1,2,1,3,5,2,4,5,3,1,4,5其中每一個(gè)元素對(duì)應(yīng)一個(gè)數(shù) cj , 稱為該元素的費(fèi)用. 選 f 的一個(gè)子集使其覆蓋s , 且總費(fèi)用最低.即實(shí)際問(wèn)題 1中5種產(chǎn)品能存放在一起的各種組合為 f=1,2,1,3,5

18、,2,4,5,3,1,4,5第 i 種組合的存儲(chǔ)費(fèi)用為 cj , 求這五種產(chǎn)品費(fèi)用最低的儲(chǔ)存方案。模型: 設(shè)決策變量：設(shè)df是 s 的一個(gè)覆蓋（一種存儲(chǔ)方案）. 當(dāng)f的第 i 個(gè)元素屬于d, （即第 i 種組合被采用）記 xi=1，否則xi=0求 目標(biāo)函數(shù) f= si cixi在約束條件 x1 +x2 + x51 x1 + x3 1 (因?yàn)榈?種產(chǎn)品只在第1，3個(gè)組合中出現(xiàn)) x2 + x4 1 x3 + x6 1 x2 +x3 + x6 1 xi0，1， i=1,2, ,6, 下的最小值.6.4 多目標(biāo)線性規(guī)劃目標(biāo)函數(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)整體評(píng)價(jià)法min s=s(f