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

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

2、矩陣H的正定性二次型:Hessian矩陣:0，正定，嚴格凸函數(shù) 0，半正定：凸函數(shù)=9X1=4X2=4X2=7X1 Z(5) F如對 Z(6) 繼續(xù)分解，其最小值也不會低于15.5 ，問題探明，剪枝。44最優(yōu)解為： x1=2， x2 =3, Z* = Z(5) =17以上的求解過程可以用一個樹形圖表示如右：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無可行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6)

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

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

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

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

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

8、到各備選地的距離為 為了使得各小區(qū)能及時得到應急服務，要求各小區(qū)到最近的服務中心的距離盡可能的短，試給出中心選址方案。62問題分析 該問題與傳統(tǒng)的選址問題的主要區(qū)別在于其目標不再是要求費用最小，而是要求最長距離最短。也就是離服務中心距離最遠的小區(qū)的路程要最小化。 變量：當中心的位置確定下來后，各小區(qū)對應的最近中心也就確定，所以真正的變量也就是中心的位置。設 63問題分析 為了便于說明問題引入間接變量，第i小區(qū)是否由第j個中心服務 以及最遠的距離約束條件，小區(qū)服務約束64問題分析最遠距離約束 中心個數(shù)約束目標函數(shù)：最遠距離 最小 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ù)學模型，不要求計算結(jié)果)：現(xiàn)有資金總額為B?？晒┻x擇購買的化工產(chǎn)品有n個，產(chǎn)品j的價格和預期利潤分別為aj和cj，此外，因供貨商對產(chǎn)品的采購約束，有3個附加條件：第一，若選擇產(chǎn)品1必須同時選擇項目2，反之，不一定；第二