教學(xué)設(shè)計(jì)教案 優(yōu)化問題與規(guī)劃模型

1、3.6 優(yōu)化問題與規(guī)劃模型 與最大、最小、最長(zhǎng)、最短等等有關(guān)的問題都是優(yōu)化問題。 優(yōu)化問題分類：（非）線性規(guī)劃、整數(shù)規(guī)劃、0-1規(guī)劃、（多）目標(biāo)規(guī)劃、（與時(shí)間有關(guān)的）動(dòng)態(tài)規(guī)劃、（系數(shù)是隨機(jī)變量的）隨機(jī)規(guī)劃。6.0 多變量?jī)?yōu)化 一個(gè)城郊的社區(qū)計(jì)劃更新消防站。原來的消防站在舊城中心。規(guī)劃要將新的消防站設(shè)置得更科學(xué)合理。在前一個(gè)季度收集了消防隊(duì)對(duì)火警反應(yīng)時(shí)間的資料：平均要用3.2分鐘派遣消防隊(duì)員；消防隊(duì)員到達(dá)火災(zāi)現(xiàn)場(chǎng)的時(shí)間（行車時(shí)間）依賴于火災(zāi)現(xiàn)場(chǎng)的距離。行車時(shí)間的資料列于表1Distance（miles）：距離（英里）Drive Time（minutes）：行車時(shí)間（分）表1 關(guān)于設(shè)備位置問題的反

2、應(yīng)時(shí)間資料從消防官員處得到的從城區(qū)的不同區(qū)域打來的求救電話頻率的數(shù)據(jù)列于圖1。其中每一格代表一平方英里，格內(nèi)的數(shù)字為每年從此區(qū)域打來的緊急求救電話的數(shù)量。1）求反應(yīng)時(shí)間。消防隊(duì)對(duì)離救火站r英里處打來的一個(gè)求救電話需要的反應(yīng)時(shí)間估計(jì)為d分鐘。2）求平均反應(yīng)時(shí)間。設(shè)城區(qū)位區(qū)域0,60,6內(nèi)，(x,y)是新的消防站的位置。根據(jù)求救電話頻率，確定消防隊(duì)對(duì)求救電話的平均反應(yīng)時(shí)間z=f(x,y) 3）求新的消防站的最佳位置。即確定函數(shù)f(x,y)的極小值點(diǎn)。首先， 用隨機(jī)搜索算法：在可行域0,60,6內(nèi)簡(jiǎn)單地選取n個(gè)隨機(jī)的的點(diǎn)，計(jì)算目標(biāo)函數(shù)在這些點(diǎn)的值，選擇其中最小的點(diǎn)即可。然后，可采用Matlab求最值

3、點(diǎn)程序求出精確的最小值點(diǎn): 求函數(shù)fun在x0點(diǎn)附近的最小值點(diǎn) x，f = fminsearch(fun, x0)6.1 線性規(guī)劃 1939年蘇聯(lián)數(shù)學(xué)家康托洛維奇發(fā)表生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)問題 1947年美國數(shù)學(xué)家喬治.丹契克、馮.諾伊曼提出線性規(guī)劃的一般模型及理論.1. 問題例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)營使經(jīng)濟(jì)效益最大. 分析：以取得最高的產(chǎn)值的方式達(dá)到收益最大的目標(biāo).1. 求什么？分別安排多少畝地種蔬菜、棉花

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

5、否則稱為非線性規(guī)劃問題。2. 線性規(guī)劃問題求解方法 稱滿足約束條件的向量為可行解,稱可行解的集合為可行域,稱使目標(biāo)函數(shù)達(dá)最值的可行解為最優(yōu)解.命題 1 線性規(guī)劃問題的可行解集是凸集.因?yàn)榭尚薪饧删€性不等式組的解構(gòu)成。兩個(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í)，構(gòu)成一族平行直線,目標(biāo)值的大小描述了直線離原點(diǎn)的遠(yuǎn)近。于是穿過可行域的目標(biāo)直線組中最遠(yuǎn)離(或接近)

6、原點(diǎn)的直線所穿過的凸多邊形的頂點(diǎn)即為取的極值的極點(diǎn)最優(yōu)解。單純形法 : 通過確定約束方程組的基本解, 并計(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 若有 aj1x1+ajnxnbj, 則引入 xn+j 0, 使得 aj1x1+ajnxn- xn+j =bj.

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

8、量對(duì)應(yīng)A的m個(gè)線性無關(guān)列, 則稱該解向量為方程組的一個(gè)基本解.在一個(gè)線性規(guī)劃問題中, 如果一個(gè)可行解也是約束方程組的基本解, 則稱之為基本可行解. 命題 4 一個(gè)向量 x 是線性規(guī)劃問題可行解集的一個(gè)極點(diǎn), 當(dāng)且僅當(dāng)它是約束方程的一個(gè)基本可行解。于是尋找取得極值的凸集極點(diǎn)的幾何問題變成了求代數(shù)方程基本解的問題，形成了解優(yōu)化問題的單純形方法，改進(jìn)單純形方法等。按這些計(jì)算方法編制程序，產(chǎn)生了Matlab優(yōu)化工具箱和專門解優(yōu)化問題的軟件 Lindo、Lingo 。 用Matlab求解：標(biāo)準(zhǔn)的線性規(guī)劃的模型： min f=cTxs.t. Ax b A1x=b1 LB x UBMatlab求解程序: x

9、,f=linprog(c,A,b,A1,b1,LB,UB)還有軟件Excel 也可應(yīng)用于解優(yōu)化問題。3 對(duì)偶問題例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)營使經(jīng)濟(jì)效益最大. 分析：以最經(jīng)濟(jì)的投入達(dá)到收益最大的目標(biāo).（或者說以直接出售土地和勞動(dòng)力的方式達(dá)到收益最大的目標(biāo).）1 求什么？土地成本價(jià)格 y1 勞動(dòng)力成本價(jià)格 y22. 優(yōu)化什么？ 成本價(jià)格最低 Min g=50y1+20y2 3. 限制條件？蔬菜的市場(chǎng)價(jià) y1+1/2

10、y2 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 向量問題: max f=cTx s.t. Ax b xi0, i=1,2,n.對(duì)偶問題: min f=yb s.t. yA c yi0, i=1,2,m.對(duì)偶定理: 互為對(duì)偶的兩個(gè)線性規(guī)劃問題, 若其中一個(gè)

11、有有窮的最優(yōu)解, 則另一個(gè)也有有窮的最優(yōu)解, 且最優(yōu)值相等. 若兩者之一有無界的最優(yōu)解, 則另一個(gè)沒有可行解模型 I II構(gòu)成對(duì)偶問題.模型 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)一步問：如果增加對(duì)土地和勞動(dòng)力的投入，每種資源的單位投入增加會(huì)帶來多少產(chǎn)值？由最優(yōu)解 y=(10,200) 可見, 多耕一畝地增加10元收入，多一個(gè)勞動(dòng)力增加200元收入。

12、也就是說, 此時(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+200/3=76.675, （而其它兩個(gè)約束條件是等式）可見，只有當(dāng)棉花價(jià)格提高到 76.6元時(shí)才值得生產(chǎn).Lingo命令Model:Max=110*x1+75*x2+60*x3;x1+x2+x3=50;1/2*x1+1/3*x2+1/4*x30表示每件第 j 類儀器的科學(xué)價(jià)值; aj 0表示每件第 j 類儀器的重量. 每類儀器件數(shù)不限, 但

13、裝載件數(shù)只能是整數(shù). 飛船總載荷不得超過數(shù) b. 設(shè)計(jì)一種方案, 使得被裝載儀器的科學(xué)價(jià)值之和最大.建模 記 xj 為第 j 類儀器的裝載數(shù). 求 目標(biāo)函數(shù) f= j cj xj 在約束條件 jaj xj b, xj 為正整數(shù), 下的最大值.用分枝定界法求解整數(shù)規(guī)劃問題基本思想:反復(fù)劃分可行域并確定最優(yōu)值的界限,將原問題不斷地分枝為若干個(gè)子問題, 且縮小最優(yōu)質(zhì)的取值范圍,直到求得最優(yōu)解. 例:求目標(biāo)函數(shù) f=3x1+2x2 在約束條件: 2x1+3x2 14, 2x1+x 2 9, x1 x 2為自然數(shù)下的最大值.用Lingo軟件求解整數(shù)規(guī)劃model:max =3*x1+2*x2;2*x1+

14、3*x2=14;2*x1+x2=9;gin(x1);gin(x2);end6.3 0-1規(guī)劃 如果要求決策變量只取0 或 1的線性規(guī)劃問題, 稱為0-1規(guī)劃. 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.求目標(biāo)函數(shù) f=x 1 +1.2x 2 +0.9x 3 +1.

15、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 集合覆蓋問題實(shí)際問題 1 某企業(yè)有5種產(chǎn)品要存放, 有些不能存放在一起, 有些能存放在一起的, 由于組合不同所需費(fèi)用不同. 求費(fèi)用最低 的儲(chǔ)存方案. 實(shí)際問題 2 某航空公司在不同城市之間開辟了5 條航線, 一個(gè)航班可以飛不同的航線組合, 不同組合成本不同, 求開通所有航線且總費(fèi)用最小的方案.抽

16、象為集合覆蓋問題：設(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種產(chǎn)品能存放在一起的各種組合為 =1,2,1,3,5,2,4,5,3,1,4,5第 i 種組合的存儲(chǔ)費(fèi)用為 cj , 求這五種產(chǎn)品費(fèi)用最低的儲(chǔ)存方案。模型: 設(shè)決策變量：設(shè)是 S 的一個(gè)覆蓋（一種存儲(chǔ)方案）. 當(dāng)?shù)牡?i 個(gè)元素屬于, （即第 i 種組合被采用）記 xi=1，否則xi=0求 目標(biāo)函數(shù) f= i cixi在約束條件 x1 +x2 + x51 x1 + x3

17、 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, 下的最小值.混合問題例： 供貨問題一家公司生產(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 =0 求 目標(biāo)函數(shù) f= i (j

18、cij xij + yi di )在約束條件 i xij = bj, j xij -hi yi 0, xij0, yi 0，1 下的最小值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=(f (k) - c(k)T x)/ f (k) （使相對(duì)偏差最?。﹕.t. Ax b A1x=b1 LB x UB有最佳妥協(xié)解 x*.習(xí)題:1. 資源分配, 生產(chǎn)甲肥1噸, 需要磷酸鹽0.4噸, 硝酸鹽1.8噸,利潤1萬元;生產(chǎn)乙肥1噸,需要磷酸鹽0.1噸

19、,硝酸鹽1.5噸,利潤0.5萬元. 現(xiàn)有磷酸鹽10噸,硝酸鹽66噸, 問甲、乙肥各生產(chǎn)多少噸獲利最大？2. 營養(yǎng)配餐, 甲種食品每10克含5個(gè)單位的蛋白, 10個(gè)單位的鐵, 單價(jià)3元;乙種食品每10克含7個(gè)單位的蛋白,4個(gè)單位的鐵, 單價(jià)2元. 現(xiàn)需要一份食品, 含有35個(gè)單位的蛋白,40個(gè)單位的鐵, 問如何配餐最省錢?3 資源的最優(yōu)配置策略某工廠有1000臺(tái)機(jī)器, 生產(chǎn)兩種產(chǎn)品 A, B, 若投入 y 臺(tái)機(jī)器生產(chǎn)A 產(chǎn)品, 則純收入為 5y .若投入 y 臺(tái)機(jī)器生產(chǎn)B 產(chǎn)品, 則純收入為 4y . 又知, 生產(chǎn)A 種產(chǎn)品機(jī)器的年折損率為20%, , 生產(chǎn)B 種產(chǎn)品機(jī)器的年折損率為10%, 問

20、在5年內(nèi)如何安排各年度的生產(chǎn)計(jì)劃, 才能使總收入最高. 4. 混合泳接力賽由蛙泳、蝶泳、自由泳、仰泳組成。如何根據(jù) 4位運(yùn)動(dòng)員的4種游泳競(jìng)賽成績(jī)安排混合泳接力隊(duì)，以取得最佳成績(jī)。 蛙泳 蝶泳 自由泳 仰泳甲 99 60 59 73 乙 79 65 93 87丙 67 93 63 81丁 56 79 86 76 5. 一家出版社準(zhǔn)備再某市開設(shè)兩個(gè)銷售點(diǎn)，向七個(gè)區(qū)的大學(xué)生售書。每個(gè)區(qū)的大學(xué)生數(shù)量（千人）如圖。 71 18 18 21 42 34 5629每個(gè)銷售點(diǎn)只能向本區(qū)和一個(gè)相鄰區(qū)的大學(xué)生售書。這兩個(gè)銷售點(diǎn)應(yīng)該設(shè)在何處，才能使所供應(yīng)的學(xué)生數(shù)量最大。6 仍考慮例2中的土方問題。在使用10立方碼載

21、重量的自動(dòng)傾卸卡車運(yùn)輸?shù)那闆r下，公司已經(jīng)確定了最優(yōu)的運(yùn)輸方案。公司又有三輛更大的卡車可用于運(yùn)輸，載重量為20立方碼。使用這些車輛可能會(huì)在運(yùn)輸中節(jié)省一些資金。載重10立方碼載的卡車平均用20分鐘裝車，5分鐘卸車，每小時(shí)平均開20英里，費(fèi)用為每英里單位重量20美元；載重20立方碼載的卡車平均用30分鐘裝車，5分鐘卸車，每小時(shí)平均開20英里，費(fèi)用為每英里單位重量30美元，為最大限度地節(jié)約運(yùn)輸費(fèi)用，應(yīng)如何安排車輛的使用？表3-5 例3.7中卡車問題的運(yùn)輸路線數(shù)據(jù)路線從到英里數(shù)運(yùn)量（立方碼）11B212522A417533C422543D410054D43507. 有4名同學(xué)到一家公司參加三個(gè)階段的面試，公司要求每個(gè)同學(xué)都必須首先找公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不許插隊(duì)（即在任何階段4位同學(xué)的順序是