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

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

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

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

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

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

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

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

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

9、章Python編程方法2.1編程基礎(chǔ)：Python語法2.1.1 類與實(shí)例類在大部分編程語言中都是一個(gè)很重要的概念，類是面向?qū)ο缶幊痰幕A(chǔ)。使用函數(shù)可以實(shí)現(xiàn)簡(jiǎn)單功能的復(fù)用，而使用類則可以實(shí)現(xiàn)復(fù)雜的系統(tǒng)代碼復(fù)用，因此通過類來模擬復(fù)雜的仿真系統(tǒng)。舉一個(gè)例子.如PPT模板可以是一個(gè)類，那么,通過修改PPT模板中的數(shù)據(jù)和文字得到新的PPT，就是實(shí)例，這個(gè)修改的過程就是實(shí)例化。又如，動(dòng)物是一個(gè)類，小貓就是一個(gè)實(shí)例。類由屬性和方法兩部分組成。如小貓是個(gè)類，其屬性包括毛色、體重，方法包括抓老鼠。又如學(xué)生是個(gè)類，某個(gè)具體的同學(xué)就是實(shí)例，學(xué)生這個(gè)類的屬性包括學(xué)號(hào)、身高、體重等;而學(xué)生這個(gè)類的方法就是學(xué)生能干什么

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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