化工系統(tǒng)工程：第3章 化工過(guò)程系統(tǒng)的優(yōu)化-整數(shù)規(guī)劃

1、1第二篇化工過(guò)程系統(tǒng)的優(yōu)化 NO.4 整數(shù)規(guī)劃2寫出其對(duì)偶問(wèn)題畫約束條件；標(biāo)明可行域；目標(biāo)函數(shù)等值線；說(shuō)明如何得到最優(yōu)解，算出相應(yīng)的目標(biāo)函數(shù)最優(yōu)值。 用圖解法求解下面的線性規(guī)劃的對(duì)偶問(wèn)題 課堂習(xí)題-2原問(wèn)題3課堂習(xí)題-2對(duì)偶問(wèn)題紅色區(qū)域?yàn)榭尚杏?，灰色虛線為目標(biāo)函數(shù)等值線。根據(jù)其梯度4，2，向右平移等值線，在點(diǎn)A(3,1)處達(dá)到可行域最遠(yuǎn)點(diǎn)，則該點(diǎn)為最優(yōu)解。Min W=4*3+2*1=14 目標(biāo)函數(shù)最優(yōu)值為14。A梯度4，2方法1：二次型特征矩陣A的正定性4第二篇課程(3)非線性規(guī)劃重點(diǎn)回顧(1) 二次函數(shù)凸凹性判定規(guī)則一般形式:Convex/concaveConvex?方法2： Hessian

2、矩陣H的正定性二次型:Hessian矩陣:0，正定，嚴(yán)格凸函數(shù) 0，半正定：凸函數(shù)=9X1=4X2=4X2=7X1 Z(5) F如對(duì) Z(6) 繼續(xù)分解，其最小值也不會(huì)低于15.5 ，問(wèn)題探明，剪枝。44最優(yōu)解為： x1=2， x2 =3, Z* = Z(5) =17以上的求解過(guò)程可以用一個(gè)樹形圖表示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4無(wú)可行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6)

3、15.5x11x12x23x24x12x1345分支定界法求解原問(wèn)題(IP) （1）先不考慮整數(shù)約束，解( IP )的松弛問(wèn)題( LP )，可能得到以下情況之一： 若( LP )沒(méi)有可行解，則( IP )也沒(méi)有可行解，停止計(jì)算。 若( LP )有最優(yōu)解，并符合( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算。 若( LP )有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)入下一步。 為討論方便，設(shè)( LP )的最優(yōu)解為： 目標(biāo)函數(shù)最優(yōu)值為不全為整數(shù)46分枝定界法解法步驟記( IP )的目標(biāo)函數(shù)最優(yōu)值為 ,以 作為 的下界，記為 。令 ，則有 （2）定界： 在( LP

4、 )的最優(yōu)解 X(0)中，任選一個(gè)不符合整數(shù)條件的變量，例如 xr= br （不為整數(shù)），以br表示不超過(guò)br的最大整數(shù)。構(gòu)造兩個(gè)約束條件 xr br 和 xr br1 將這兩個(gè)約束條件分別加入問(wèn)題( IP ) ，形成兩個(gè)子問(wèn)題( IP1)和( IP2 ) ，再解這兩個(gè)子問(wèn)題的松弛問(wèn)題( LP1)和( LP2) 。 （3）分枝：47如此反復(fù)進(jìn)行，直到得到 為止，即得最優(yōu)解 X* 。 （4）修改上、下界：按照以下兩點(diǎn)規(guī)則進(jìn)行。 在各分枝問(wèn)題中，找出目標(biāo)函數(shù)值最小者作為新的下界； 從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最小者作為 新的上界。 （5）比較與剪枝 ： 各分枝的目標(biāo)函數(shù)值中，若有大于

5、者，則剪掉此枝，表明此子問(wèn)題已經(jīng)探清，不必再分枝了;否則繼續(xù)分枝。 （1）先不考慮整數(shù)約束，解(IP)的松弛問(wèn)題(LP)：（2）定界：（3）分枝：48整數(shù)規(guī)劃的應(yīng)用第三部分生產(chǎn)計(jì)劃優(yōu)化人力資源問(wèn)題城市應(yīng)急系統(tǒng)選址問(wèn)題煉油廠1#原油24$/桶2#原油15$/桶汽油36$/桶燃料油21$/桶煤油24$/桶殘油10$/桶例1：生產(chǎn)計(jì)劃優(yōu)化產(chǎn)品名稱收率 / %最大生產(chǎn)能量或市場(chǎng)需求/(桶/天)1#原油2#原油汽油804424000煤油5102000燃料油10366000殘油510加工費(fèi)用/$0.51.0生產(chǎn)計(jì)劃模型 1#原油用量 2#原油用量 汽油產(chǎn)量 煤油產(chǎn)量 燃料油產(chǎn)量 殘油產(chǎn)量生產(chǎn)計(jì)劃模型實(shí)際生

6、產(chǎn)過(guò)程（0-1規(guī)劃）：在短周期內(nèi)，裝置生產(chǎn)不可能頻繁切換。假定在一天內(nèi)，煉油廠只能加工一種原油。 加工1#原油 加工2#原油生產(chǎn)計(jì)劃模型54例1：人力資源分配問(wèn)題某個(gè)中型百貨商場(chǎng)對(duì)售貨人員（周工資200元）的需求經(jīng)統(tǒng)計(jì)如下表，為了保證銷售人員充分休息，銷售人員每周工作5天，休息2天，每天需要的售貨人員數(shù)如下表。問(wèn)應(yīng)如何安排銷售人員的工作時(shí)間，使得所配售貨人員的總費(fèi)用最??？星期一二三四五六七人數(shù)12151214161819例2：人力資源分配問(wèn)題55人員安排限制每天工作8小時(shí)，不考慮夜班的情況；每個(gè)人的休息時(shí)間為連續(xù)的兩天時(shí)間；每天安排的人員數(shù)不得低于需求量，但可以超過(guò)需求量例2：人力資源分配問(wèn)題

7、56問(wèn)題分析確定每天工作的人數(shù)，由于連續(xù)休息2天，當(dāng)確定每個(gè)人開始休息的時(shí)間就等于知道工作的時(shí)間，因而確定每天開始休息的人數(shù)就知道每天開始工作的人數(shù)，從而求出每天工作的人數(shù)。變量：每天開始休息的人數(shù) 57問(wèn)題分析約束條件 ：1.每人休息時(shí)間2天，自然滿足；2.每天工作人數(shù)不低于需求量；3.某天休息的人數(shù)就是從某天往前數(shù)5天內(nèi)開始工作的人數(shù) 58 3.變量非負(fù)約束：59目標(biāo)函數(shù)：總費(fèi)用最小，總費(fèi)用與使用的總?cè)藬?shù)成正比。由于每個(gè)人必然在且僅在某一天開始休息，所以總?cè)藬?shù)等于60模型61例3：應(yīng)急選址問(wèn)題 某城市要在市區(qū)設(shè)置k個(gè)應(yīng)急服務(wù)中心,經(jīng)過(guò)初步篩選確定了m個(gè)備選地，現(xiàn)已知共有n個(gè)居民小區(qū)，各小區(qū)

8、到各備選地的距離為 為了使得各小區(qū)能及時(shí)得到應(yīng)急服務(wù)，要求各小區(qū)到最近的服務(wù)中心的距離盡可能的短，試給出中心選址方案。62問(wèn)題分析 該問(wèn)題與傳統(tǒng)的選址問(wèn)題的主要區(qū)別在于其目標(biāo)不再是要求費(fèi)用最小，而是要求最長(zhǎng)距離最短。也就是離服務(wù)中心距離最遠(yuǎn)的小區(qū)的路程要最小化。 變量：當(dāng)中心的位置確定下來(lái)后，各小區(qū)對(duì)應(yīng)的最近中心也就確定，所以真正的變量也就是中心的位置。設(shè) 63問(wèn)題分析 為了便于說(shuō)明問(wèn)題引入間接變量，第i小區(qū)是否由第j個(gè)中心服務(wù) 以及最遠(yuǎn)的距離約束條件，小區(qū)服務(wù)約束64問(wèn)題分析最遠(yuǎn)距離約束 中心個(gè)數(shù)約束目標(biāo)函數(shù)：最遠(yuǎn)距離 最小 65模型66混合整數(shù)線性規(guī)劃求解器 MILP SolversCPL

9、EXGUROBIXPRESS其他: CBC, CGL, GLPK67凸/非凸-混合整數(shù)非線性規(guī)劃求解器Convex/non-Convex MINLP SolversMINLP codes:SBB Bussieck, Drud (2003) (B&B)Bonmin (COIN-OR) Bonami et al (2006) (B&B, OA, Hybrid)DICOPT (GAMS) Viswanathan and Grossman (1990) (OA)AOA (AIMMS) (OA)-ECP Westerlund and Peterssson (1996) (ECP)MINOPT Schwe

10、iger and Floudas (1998)(GBD, OA)Global MINLP code:BARON Sahinidis et al. (1998) (Deterministic Global Optimization)MIQP codes:CPLEX-MIQP ILOG (Branch and bound, cuts)68Academic Tree of Ignacio E. Grossmann作業(yè)1(只列數(shù)學(xué)模型，不要求計(jì)算結(jié)果)：現(xiàn)有資金總額為B?？晒┻x擇購(gòu)買的化工產(chǎn)品有n個(gè)，產(chǎn)品j的價(jià)格和預(yù)期利潤(rùn)分別為aj和cj，此外，因供貨商對(duì)產(chǎn)品的采購(gòu)約束，有3個(gè)附加條件：第一，若選擇產(chǎn)品1必須同時(shí)選擇項(xiàng)目2，反之，不一定；第二