Python最優(yōu)化算法實戰(zhàn)學習筆記

1、Python最優(yōu)化算法實戰(zhàn)第一章最優(yōu)化算法概述1.1最優(yōu)化算法簡介最優(yōu)化算法,即最優(yōu)計算方法,也是運籌學。涵蓋線性規(guī)劃、非線性規(guī)劃、整數規(guī)劃、組合規(guī)劃、圖論、網絡流、決策分析、排隊論、可靠性數學理論、倉儲庫存論、物流論、博弈論、搜索論和模擬等分支。當前最優(yōu)化算法的應用領域如下。(1) 市場銷售:多應用在廣告預算和媒體的選擇、競爭性定價、新產品開發(fā)、銷售計劃的編制等方面。如美國杜邦公司在20世紀50年代起就非常重視對廣告、產品定價和新產品引入的算法研究。(2) 生產計劃:從總體確定生產、儲存和勞動力的配合等計劃以適應變動的需求計劃,主要采用線性規(guī)劃和仿真方法等。此外,還可用于日程表的編排,以及合

2、理下料、配料、物料管理等方面。(3) 庫存管理:存貨模型將庫存理論與物料管理信息系統(tǒng)相結合,主要應用于多種物料庫存量的管理,確定某些設備的能力或容量,如工廠庫存量、倉庫容量,新增發(fā)電裝機容量、計算機的主存儲器容量、合理的水庫容量等。(4) 運輸問題:涉及空運、水運、陸路運輸,以及鐵路運輸、管道運輸和廠內運輸等,包括班次調度計劃及人員服務時間安排等問題。(5) 財政和會計:涉及預算、貸款、成本分析、定價、投資、證券管理、現金管理等,采用的方法包括統(tǒng)計分析、數學規(guī)劃、決策分析,以及盈虧點分析和價值分析等。(6) 人事管理:主要涉及以下6個方面。 人員的獲得和需求估計。 人才的開發(fā)，即進行教育和培訓

3、。 人員的分配，主要是各種指派問題。 各類人員的合理利用問題。 人才的評價，主要是測定個人對組織及社會的貢獻。 人員的薪資和津貼的確定。(7) 設備維修、更新可靠度及項目選擇和評價:如電力系統(tǒng)的可靠度分析、核能電廠的可靠度B風險評估等。(8) 工程的最佳化設計:在土木，水利、信息電子、電機、光學、機械、環(huán)境和化工等領域皆有作業(yè)研究的應用。(9) 計算機信息系統(tǒng):可將作業(yè)研究的最優(yōu)化算法應用于計算機的主存儲器配置，如等候理論在不同排隊規(guī)則下對磁盤、磁鼓和光盤工作性能的影響。利用整數規(guī)劃尋找滿足組需求檔案的尋找次序，并通過圖論、數學規(guī)劃等方法研究計算機信息系統(tǒng)的自動設計。(10) 城市管理:包括各

4、種緊急服務救難系統(tǒng)的設計和運用.如消防車、救護車、警車等分布點的設立。美國采用等候理論方法來確定紐約市緊急電話站的值班人數,加拿大采用該方法研究城市警車的配置和負責范圍，以及事故發(fā)生后警車應走的路線等。此外，還涉及城市垃圾的清掃、搬運和處理，以及城市供水和污水處理系統(tǒng)的規(guī)劃等相關問題。1.2最優(yōu)化算法的內容最優(yōu)化算法的內容包括:規(guī)劃論（線性規(guī)劃、非線性規(guī)劃、整數規(guī)劃和動態(tài)規(guī)劃）、庫存論、圖論、排隊論、可靠性理論、對策論、決策論、搜索論等。1.2.1 規(guī)劃論1.2.2 庫存論庫存論中研究的主要問題可以概括為何時訂貨（補充存貯）和每次訂多少貨（補充多少庫存這兩個問題。1.2.3 圖論1.2.4 排

5、隊論排隊論（隨機服務系統(tǒng)理論）主要研究各種系統(tǒng)的排隊長度、排隊的等待時間及所提供的服務等各種參數,以便求得更好的服務,它是研究系統(tǒng)隨機聚散現象的理論。排隊論的研究目的是要回答如何改進服務機構或組織所服務的對象，使某種指標達到最優(yōu)的問題。如一個港口應該有多少個碼頭、一個工廠應該有多少名維修人員等。因為排隊現象是一個隨機現象,因此在研究排隊現象時,主要采用將研究隨機現象的概率論作為主要工具。此外,還涉及微分和微分方程的相關內容。排隊論把它所要研究的對象形象地描述為顧客來到服務臺前要求接待。如果服務臺已被其他顧客占用,那么就要排隊?；蛘叻张_時而空閑、時而忙碌,那就需要通過數學方法求得顧客的等待時間

6、、排隊長度等的概率分布。排隊論在日常生活中的應用非常廣泛,如水庫水量的調節(jié)、生產流水線的安排、鐵路運輸的調度電網的設計等。1.2.5 可靠性理論可靠性理論是研究系統(tǒng)故障，以提高系統(tǒng)可靠性問題的理論?？煽啃岳碚撗芯康南到y(tǒng)一般分為以下兩類。（1）不可修復系統(tǒng):這種系統(tǒng)的參數是壽命、可靠度等，如導彈等。（2）可修復系統(tǒng):這種系統(tǒng)的重要參數是有效度，其值為系統(tǒng)的正常工作時間與正常工作時間加上事故修理時間之比、如一般的機電設備等。1.2.6 對策論對策論(博弈論)是指研究多個個體或團隊之間在特定條件制約下的對局中,利用相關方的策略而實施對應策略的學科,如田忌賽馬,智豬博弈就是典型的博弈論問題。1.2.7

7、 決策論決策論是研究決策問題的,所謂決策就是根據客觀可能性,借助一定的理論、方法和工具,科學地選擇最優(yōu)方案的過程。決策問題由決策者和決策域構成,而決策域則由決策空間、狀態(tài)空間和結果函數構成。研究決策理論與方法的科學就是決策科學。決策所要解決的問題是多種多樣的,不同角度有不同的分類方法。按決策者所面臨的自然狀態(tài)的確定與否可分為確定型決策、不確定型決策和風險型決策,按決策所依據的目標個數可分為單目標決策與多目標決策,按決策問題的性質可分為戰(zhàn)略決策與策略決策，以及按不同準則劃分成的種種決策問題類型。不同類型的決策問題應采用不同的決策方法。決策的基本步驟如下:(1) 確定問題,提出決策的目標;(2)

8、發(fā)現、探索和擬定各種可行方案;(3) 從多種可行方案中，選出最佳方案;(4) 決策的執(zhí)行與反饋,以尋求決策的動態(tài)最優(yōu)。如果對方決策者也是人(一個人或一群人)，雙方都希望取勝，這類具有競爭性的決策稱為對策或博弈型決策。構成對策問題的3個根本要素是：局中人、策略和一局對策的得失。對策問題按局中人數分類可分成兩人對策或多人對策，按局中人贏得函數的代數和是否為零可分成零和對策和非零和對策,按解的表達形式可分成純策略對策和混合策略對策,按問題是否靜態(tài)形式可分成動態(tài)對策和靜態(tài)對策。1.2.8 搜索論搜索論主要研究在資源和探測手段受到限制的情況下，如何設計尋找某種目標的最優(yōu)方案,并加以實施的理論和方法。第二

9、章Python編程方法2.1編程基礎：Python語法2.1.1 類與實例類在大部分編程語言中都是一個很重要的概念，類是面向對象編程的基礎。使用函數可以實現簡單功能的復用，而使用類則可以實現復雜的系統(tǒng)代碼復用，因此通過類來模擬復雜的仿真系統(tǒng)。舉一個例子.如PPT模板可以是一個類，那么,通過修改PPT模板中的數據和文字得到新的PPT，就是實例，這個修改的過程就是實例化。又如，動物是一個類，小貓就是一個實例。類由屬性和方法兩部分組成。如小貓是個類，其屬性包括毛色、體重，方法包括抓老鼠。又如學生是個類，某個具體的同學就是實例，學生這個類的屬性包括學號、身高、體重等;而學生這個類的方法就是學生能干什么

10、，包括學習、考試等。方法就是這個類能做哪些事情，代碼實現就是函數,一個函數經過固定格式的包裝后就是類的方法。注意:類的定義和實例化有固定的格式要求。所有的類都有一個_init_(self)初始化方法，用來定義類有哪些屬性，也可以用來在實例化類時執(zhí)行某些方法。2.2Pandas基礎2.2.1Pandas基礎數據結構Pandas提供了Series和DataFrame兩種基礎數據結構，其中Series表示序列數據,DataFrame表示表格數據，且是由多個Series組成的。2.2.2 分組統(tǒng)計Pandas的分組統(tǒng)計使用groupby函數，參數as_index二False表示統(tǒng)計后返回DataFra

11、me類型的結果，否則返回Series類型的統(tǒng)計結果。2.2.3apply函數對于apply函數，其作用是對目標集合中的每一個元素執(zhí)行相同的操作。第三章Gurobi優(yōu)化器3.1Gurobi的數據結構3.1.1MultidictMultidict，即復合字典，就是多重字典的意思,multidict函數允許在一"語句中初始化一"個或多個字典。3.1.2TuplelistTuplelist，即元組列表，就是tuple和list的組合，也就是list元素的tuple類型，其設計目的是為了高效的在元組列表中構建子列表。3.1.3TupledictTupledict是Python的dic

12、t的一子類，通過tupledict可以更加高效地操作Gurobi中的變量子集，也就是說當定義了很多變量,需要對其中一部分變量進行操作時，可以使用tupledict的內置方法來高效輕松地構建線性表達式，如sum和prod。tupledict的鍵在內部存儲格式是tuplelist，因此可以使用tuplelist的select方法選擇集合的子集。在實際使用中通過將元組與每個Gurobi變量關聯起來，可以有效地創(chuàng)建包含匹配變量子集的表達式。32Gurobi的參數和屬性3.2.1參數類型(1) Termination停止參數，用于控制求解的停止條件。如TimeLimit設定整個求解過程耗時限制；Solu

13、tionLimit設定MIP可行解數量；BarlteLimit設定障礙法(Barrier)迭代次數限制;IterationLimit設定單純形法迭代次數限制，如表3.1所示。Tolerances容差參數，用于控制結果的精度，在大多數情況下，這個限制是通過數值公差來管理的；如果沖突小于相應的公差，求解器將結果視為滿足約束。(3) Simplex單純形參數，用于控制單純形法的應用。如InfUnbdInfo控制是否生成不可行或無界模型的附加信息。(4) Barrier障礙法參數，用于控制障礙法的操作，障礙法也稱罰函數法。如QCPDual控制是否獲取二次模型的對偶值。(5) MIP混合整數規(guī)劃參數，用

14、于控制混合整數規(guī)劃算法。如BranchDir用于設定分支割平面搜索方向，默認值是自動選擇的。值為-1時將總是首先探索向下分支，而值為1時則始終首先探索向上分支;Heristics設定啟發(fā)式算法求解所花費的時間所占的比重。(6) MIPCuts割平面參數，用于控制割平面的形式。如Cuts用于控制全局割平面法的強度。(7) Tuning調參參數，用于控制求解器的調參行為。如TuneCriterion可設定調參的準則，TuneTimeLimit可設定調參的時間。(8) MultipleSolutions多解參數，用于修改MIP的搜索行為，用于嘗試為MIP模型尋找多個解。如PoolSolutions決

15、定儲存可行解的數量。3.2.2 修改參數對于Gorubi參數的修改有3種方法:一種是selPeram(paramname,newvalue)方法，其中paramname還有兩種方法，一種是參數的字符串，比如"TimeLimit",種是完整的類屬性，比如"gkb.CRB.param.TimeLimit"第三種方法是直接修改類的屬性,寫法是modelLParame.xx。3.2.3 屬性類型通過屬性(Attributes)能夠控制模型(變量、約束、目標等對象)的特征,Curobi中的屬性共分成8種類型，分別是模型屬性、變量屬性、線性約束屬性、SOS約束屬性、

16、二次約束屬性、廣義約束屬性、解的質量屬性和多目標屬性。ModelAttributes(模型屬性)，包括ModelSense模型優(yōu)化方向(最大化或最小化).ObjVal當的目標值。3.2.4 查看修改屬性查看和修改Gurobi參數屬性的方法很簡單，用于查看屬性的函數是getAttr(attrname,objs)，用于修改屬性的函數是setAttr(attrname,newvalue)。注意:并不是所有屬性都能進行修改,對于只讀屬性就只能查看而不能修改。(1) 查看屬性。方法:getAttr(attrname,objs)，其中attrname是屬性名稱,objs(可選)是列表或字典對象用來存儲查詢

17、的值。例如,model.getAttr(GRB.Attr.ObjVal)或簡寫為model.ObjVal。(2) 修改屬性。方法:setAttr(attrname,newvalue),其中attrname是屬性名稱,newvalue是屬性的值。例如，var.setAttr(GRB.Attr.VType,C)或簡寫為var.Vtype二C。3.3 Gurobi線性化技巧添加廣義約束有兩種方法;一種是model類的方法add_XXX;另一種是model.addConstr方法。約束條件用Gurobi內置函數表示即用gurobipy.XXX函數來表達廣義約束。注意:當使用第二種方法時.該約束做的是邏

18、輯判斷,而不是賦值操作,這樣就和model.addConstr方法的輸入要求一致了。3.4 Gurobi多目標優(yōu)化在Gurobi中，可以通過MdelsetobjectiveN函數來建立多目標優(yōu)化模型，多目標的setObjectiveN函數和單目標的setObjecive函數用法基本一致，不同的是多了目標優(yōu)先級、目標劣化接受程度多目標的權重等參數。setobjectiveN(expr,index,priority,weight,abstol,reltol,name)各參數說明如下。expr:目標函數表達式，如x+2y+3z。(2) index:目標函數對應的序號(0,1,2,.),即第幾個目標，

19、注意目標函數序號應從0開始。(3) prority優(yōu)先級，為整數，值越大表示目標優(yōu)先級越高。weight:權重(浮點數)，在合成型多目標解法中使用該參數，表示不同目標之間的組合權重。abtol:允許的目標函數值最大的降低量abstol(浮點數)，即當前迭代的值相比最優(yōu)值的可接受劣化程度。reltol:abstol的百分數表示，如rlol=0.05則表示可接受劣化程度是5%。(7)name:目標函數名稱。需要注意的是，在Gurobi的多目標優(yōu)化中，要求所有的目標函數都是線性的，并且目標函數的優(yōu)化方向應一致，即全部最大化或全部最小化，因此可以通過乘以-1實現不同的優(yōu)化方向。當前Gurobi支持3種

20、多目標模式，分別是Blend(合成型)、Hierarchical(分層型)、兩者的混合型。Blend通過對多個目標賦予不同的權重實現將多目標轉化成單目標函數，權重扮演優(yōu)先級的角色Herchial有優(yōu)先級，一般理解是在保證第一個目標值最優(yōu)的情況下優(yōu)化第二個目標或者在優(yōu)化第二個目標時要保證第一一個目標的最優(yōu)值只能允許少量劣化。3.5callback函數callback函數的主要作用是為了獲取程序運行過程中的一些中間信息，或者在程序運行過程中動態(tài)修改程序運行狀態(tài)，如用戶有時在求解過程中需要實現一些功能，包括終止優(yōu)化、添加約束條件(割平面)、嵌入自己的算法等。3.5.1回調函數callback定義回調

21、函數callback的定義的方法如下。deffuneion_name(model,where):print('dosomethingwheregurobirun'，其中calback函數有兩個固定的參數:model是指定義的gurobi.Model類，where是指回調函數的出發(fā)點。在callback函數使用過程中,需要注意的是where和what，即在什么地方(where)獲取哪些信息(what)，如下面的代碼,cbGet查詢獲取優(yōu)化器的指定信息,即grb.CRB.Callback.MULTIOBJ_OBJCNT當前解的數量。ifwhere-=grb.GRB.Callback

22、.MULTIOBJ:#whereprint(model.cbGet(grb.GRB.Callback.MULTIOBJ_OBJCNT)#what注意:where和what一般是配套使用的，如當where二MIP時,what只能獲取MIP的相關信息。3.5.2callback函數的功能在Gurobi中除cbGet函數外還有一些常用函數用于獲取運行過程中信息或修改運行狀態(tài)包cbGetNodeRel.cbGetSolution,cbCut,cbLazy,cbSetSolution,cbStopOneMultiObj等。cbGet(what)這個函數的使用最為頻繁,常用于查詢求解過程中的一些信息，如目

23、標值、節(jié)點數等,使用時應注意what與where的匹配。第四章線性規(guī)劃4.1線性規(guī)劃的標準型在線性規(guī)劃求解方法中,模型的標準形式如下。(1) 目標函數求最大值。(2) 約束條件為等式約束。(3) 約束條件右邊的常數項大于或等于0。(4) 所有變量大于或等于0。對于非標準形式的模型,約束方程可以通過引人松弛變量使約束不能轉化成等式約束。在某些模型中，如果目標函數是求最小值，則兩邊乘以-1將求min轉成求max;如果遇到約束方程右邊常數項為負數，則將約束方程乘以-1使常數項非負;如果變量x沒有約束，則既可以是正數也可以是負數。將模型轉換成標準型后，就可以使用經典的線性規(guī)劃方法求解了,包括單純形法、

24、內點法等。內點法和單純形法的結果相差可能很大，這是因為內點法的搜索路徑是在可行域內部,而不能在可行域的邊界上，這也是內點法的局限性。內點法不僅局限在線性規(guī)劃上，二次規(guī)劃等也是可以求解的,因為其本質是利用函數梯度求最優(yōu)值，這同很多機器學習算法的思路是一致的，真正的難點在于如何保證新的目標函數是否存在一階導數和二階導數，以及如何得到一階導數和二階導數的信息，有了導數信息，很多工具如Python中SciPy庫的optimize包就可以利用函數的一階導數和二階導數快速求解函數的最優(yōu)值。此外，初始迭代點的選擇也是很重要的，在線性規(guī)劃問題中能夠保證最后得到的是最優(yōu)解，而非線性規(guī)劃問題中，函數是非凸的，因此

25、很難保證最后的解是全局最優(yōu)解。4.2列生成法列生成法是一種用于求解大規(guī)模線性優(yōu)化問題非常高效的算法，本質上，列生成算法就是單純形法的一種形式，它是用來求解線性規(guī)劃問題的，所不同的是列生成法改善了大規(guī)模優(yōu)化問題中單純形法基變換計算效率低的問題，列生成法在整數規(guī)劃中已經得到了廣泛應用。4.3對偶問題可以將原問題和對偶問題看成是一個問題的兩個視角，如在一定的資源下如何安排生產才能使利潤最大，這個問題的另一個角度就是怎樣購買這些生產資源使花錢最少。從數學的角度來說，如果原問題不好求解，可以嘗試從對偶問題的角度出發(fā)求原問題，如在求最小問題中，對偶問題就是尋找原問題目標函數的下界。4.4 拉格朗日乘子法第

26、五章整數規(guī)劃通常默認變量的取值是大于或等于0的自然數,然而在許多實際問題中，都要求決策變量的取值為正整數，如機器臺數、商品數量、工人數量、裝載貨物的汽車數量等，,這類要求變量為整數的問題稱為整數規(guī)劃(ntegerProgramming,IP)問題。如果只要求一部分決策變量取整數，則稱為混合整數規(guī)劃(MixIntegerProgramming,MIP)。如果決策變量的取值只能是0或1則稱為0-1整數規(guī)劃(BinaryIntegerProgramming,BIP)。如果模型是線性模型，則稱為整數線性規(guī)劃(IntegerLinearProgramming,ILP)。求解整數規(guī)劃的常用方法有分支定界法

27、和割平面法，這兩種方法的共同特點是，在線性規(guī)劃的基礎上，通過增加附加約束條件，使整數最優(yōu)解稱為線性規(guī)劃的一個極點(可行域的一個頂點)，于是就可以用單純形法等方法找到這個最優(yōu)解，它們的區(qū)別在于約束條件的選取規(guī)劃和方式不同。第六章多目標優(yōu)化多目標優(yōu)化(MultiobjectiveOptimizationProblem,MOP也叫多目標規(guī)劃，即同時優(yōu)化多個目標的規(guī)劃問題。前面講的都是單目標規(guī)劃方法,但是在實際生活中，很多決策往往是多目標決策，如購買商品時，既要保證質量，也要價格合適,如果有贈品就更好了。那么，在企業(yè)的生產管理中，既希望利潤最大化，也希望成本最小化。在講Gurobi求解多目標決策時，已

28、經介紹了Curobi求解多目標規(guī)劃的兩種方法:一種是合成型.將多目標轉化成單目標決策問題;另一種是分層型,在保證第一目標的情況下，盡量優(yōu)化第尺空A/r|IJ-二,第三等目標。因此,多目標規(guī)劃一般有兩種方法:一種是化多為少,即將多目標轉化為比較容易求解的單目標規(guī)劃方法;另一種是分層序列法,即把目標按其重要性排序,每次都在前一個目標最優(yōu)解集內求解下一個目標的最優(yōu)解,直到求出共同的最優(yōu)解。那么,如何理解目標最優(yōu)解集呢?在多目標規(guī)劃中往往有多個最優(yōu)解同時滿足約束條件,不同的解之間不能簡單通過大小來比較,這點是同單目標規(guī)劃的最大區(qū)別,多個解組成的集合稱為帕累托最優(yōu)解集,組成的超平面稱為帕累托前沿。第七章

29、動態(tài)規(guī)劃動態(tài)規(guī)劃（DynamicProgramming,DP是運籌學的一分支，是解決多階段決策過程最優(yōu)化的一種方法。它把多變量復雜決策的問題進行分階段決策,可高效求解多個單變量的決策問題動態(tài)規(guī)劃在現代企業(yè)管理、工農業(yè)生產中有著廣泛的應用，許多問題用動態(tài)規(guī)劃處理，比用線性規(guī)劃或非線性規(guī)劃處理更加有效,如最短路徑、設備維修換新、多階段庫存等問題。7.1多階段決策問題有這樣一類問題，它可以從時間或空間t將決策的過程分解為若干個相互聯系的階段.每個階段都需要做出決策，當前階段的決策往往會影響到下個階段的決策,將各階段的決策構成一個決策序列、稱為策略。每個階段都有若干個決策可供選擇,因此就有許多策略可以

30、選擇。如何在這些策略中選擇一個最優(yōu)策略，這類問題就是多階段決策問題。個較常見的多階段決策問題是網絡最短路徑問題，給定的一個網路，需要從A出發(fā)到達D,如何選擇路徑才能使總路程最短，顯然這是個4階段決策問題。動態(tài)規(guī)劃的另一個常見例子是背包問題，一個背包最多能放15kg的物品，每個物品的重量和價值都已經知道，那要選擇哪些物品才能使背包內的物品總價值最大?背包問題可以看成是一個多階段規(guī)劃問題，如果選擇物品A,占用的空間將使得其他可供選擇的物品減少。雖然簡單背包問題可以用整數規(guī)劃方法求解，但是用動態(tài)規(guī)劃方法求解更為高效。第八章圖與網絡分析8.1圖的基本概念在算法最優(yōu)化領域，圖與網絡分析是一個很重要的組成部分，特別是在交通運輸領域中，問題會被建模成一個圖優(yōu)化問題。不僅僅是交通問題可以用圖的模型表示，像人物關系圖譜任務流程依賴關系、電力線網、信息網絡等都可以用圖來表示。8.2最小生成樹在數學建模中,如果用圖的數據結構求解比較麻煩,而用樹的數據結構求解比較簡單時,就會用到最小生成樹,將圖轉成樹來建模。在實際問題中,一個經典的案例就是村莊架設電話線問題，假設