混合整數(shù)規(guī)劃

在項(xiàng)目群投資決策中的應(yīng)用研究

劉義成

一、引言

當(dāng)前，我國經(jīng)濟(jì)和社會(huì)發(fā)展已進(jìn)入高質(zhì)量發(fā)展階段，在創(chuàng)新驅(qū)動(dòng)發(fā)展、構(gòu)建現(xiàn)代化產(chǎn)業(yè)體系、因地制宜發(fā)展新質(zhì)生產(chǎn)力等重大戰(zhàn)略的引導(dǎo)下，政府、企業(yè)集團(tuán)等市場主體的項(xiàng)目投資呈現(xiàn)多元化、集群化、系統(tǒng)化的發(fā)展趨勢，其中，項(xiàng)目群投資決策優(yōu)化成為需要關(guān)注的熱點(diǎn)問題，也是固定資產(chǎn)投資決策管理的難點(diǎn)問題[1]。項(xiàng)目群是由若干具有內(nèi)在聯(lián)系、資源共享或協(xié)同效應(yīng)的投資項(xiàng)目組合，在當(dāng)前高質(zhì)量發(fā)展背景下，無論是政府開展的基礎(chǔ)設(shè)施投資、產(chǎn)業(yè)園區(qū)建設(shè)，還是大型企業(yè)集團(tuán)開展戰(zhàn)略性投資，通常都會(huì)面臨多項(xiàng)目備選、多目標(biāo)權(quán)衡、資源優(yōu)化配置的復(fù)雜決策環(huán)境，如在資金、土地等資源限制下，風(fēng)險(xiǎn)與收益平衡的問題。

傳統(tǒng)的多項(xiàng)目投資決策問題，主要依賴專家咨詢法、層次分析法、凈現(xiàn)值法、多準(zhǔn)則決策方法等，例如，M Kandakoglu等[2]研究不同多準(zhǔn)則方法及其與數(shù)學(xué)規(guī)劃技術(shù)聯(lián)合在項(xiàng)目組合選擇中的應(yīng)用；Hui Sun等[3]以BOT高速公路項(xiàng)目為對(duì)象，從財(cái)務(wù)角度計(jì)算了具有真實(shí)約束的最優(yōu)投資組合，這些方法在處理當(dāng)前創(chuàng)新驅(qū)動(dòng)發(fā)展下的基礎(chǔ)設(shè)施規(guī)劃、產(chǎn)業(yè)集群建設(shè)等眾多項(xiàng)目備選的復(fù)雜場景時(shí)會(huì)顯得較為困難。

二、模型建立

目前，在多目標(biāo)混合整數(shù)規(guī)劃建模研究方面，主要集中在供應(yīng)鏈優(yōu)化、能源管理等領(lǐng)域，如Teh等人[5]通過構(gòu)建多目標(biāo)混合整數(shù)線性規(guī)劃模型，研究棕櫚油生物質(zhì)廢棄物轉(zhuǎn)化為高收率生物油涉及的年化總利潤和全球變暖潛力權(quán)衡問題。Jabarzadeh等[6]通過構(gòu)建可持續(xù)水果閉環(huán)供應(yīng)鏈網(wǎng)絡(luò)的多目標(biāo)混合整數(shù)線性模型，同時(shí)考慮經(jīng)濟(jì)、環(huán)境和社會(huì)指標(biāo)，即最小化網(wǎng)絡(luò)總成本和不同網(wǎng)絡(luò)活動(dòng)的二氧化碳排放量，同時(shí)最大化對(duì)需求的響應(yīng)度同時(shí)納入模型，并采用加權(quán)Tchebycheff方法求解Pareto最優(yōu)解。資源約束下的項(xiàng)目群多目標(biāo)選擇優(yōu)化問題，核心是在多重約束條件下，選擇哪些備選項(xiàng)目，在最大化投資收益的同時(shí)，確保整體風(fēng)險(xiǎn)在可容忍的限制范圍內(nèi)。

（一）假設(shè)與參數(shù)定義

1.基本假設(shè)

（1）項(xiàng)目均為獨(dú)立單元，可被投資或不被投資；

（2）已知年均收益、投資額、占地面積、失敗風(fēng)險(xiǎn)等指標(biāo)參數(shù)；

（3）項(xiàng)目失敗風(fēng)險(xiǎn)獨(dú)立，可簡單加和為整體風(fēng)險(xiǎn)水平；

（4）項(xiàng)目間不考慮互斥或互補(bǔ)效應(yīng)；

（5）投資為單一決策，不考慮動(dòng)態(tài)分期；

（6）組合優(yōu)化為一次求解，不考慮實(shí)時(shí)反饋機(jī)制。

2.參數(shù)定義

設(shè)項(xiàng)目集合

，每個(gè)項(xiàng)目具有如下屬性變量：

表1 項(xiàng)目屬性變量表

（二）混合整數(shù)規(guī)劃模型構(gòu)建

模型目標(biāo)包括年均收益最大化的主目標(biāo)和風(fēng)險(xiǎn)失敗風(fēng)險(xiǎn)最小化的次目標(biāo)，數(shù)學(xué)表達(dá)式如下：

三、算法求解

混合整數(shù)規(guī)劃屬于NP-Hard類問題，主要有近似（啟發(fā)式）算法和精確算法兩類求解策略。近似（啟發(fā)式）算法是在問題規(guī)模較大或計(jì)算資源有限時(shí)，能夠快速找到接近最優(yōu)的可行解，例如遺傳算法、模擬退火等，例如，張毅等[7]針對(duì)行調(diào)沖突的大型高鐵站到發(fā)線運(yùn)用優(yōu)化問題，構(gòu)建到發(fā)線運(yùn)用多目標(biāo)優(yōu)化模型，設(shè)計(jì)改進(jìn)遺傳算法進(jìn)行求解。精確算法即能夠找到全局最優(yōu)解，例如分支定界法、分支切割法。本研究選擇使用精確算法，即分支定界法，求得真正意義上的最優(yōu)投資組合。

1.ε約束法

ε約束法由Haimes等人在1971年提出，是一種經(jīng)典的多目標(biāo)優(yōu)化策略，適用于目標(biāo)函數(shù)可解耦的情況，核心思想是保留一個(gè)目標(biāo)函數(shù)作為主目標(biāo)，其余目標(biāo)函數(shù)轉(zhuǎn)化為約束形式，并設(shè)置“ε”作為可接受上限或下限。例如，文獻(xiàn)[8-10]分別研究了基于模型的ε-約束法在車輛服務(wù)設(shè)施選址、考慮跑道復(fù)雜依賴關(guān)系的多目標(biāo)飛機(jī)排序、震后初期多品種應(yīng)急物資動(dòng)態(tài)分配等領(lǐng)域的Pareto最優(yōu)解集。通過引入ε約束法，本文構(gòu)建的模型可以轉(zhuǎn)化為：

2.分支定界法

分支定界法（Branch and Bound）是一種系統(tǒng)性搜索算法，適用于解決混合整數(shù)規(guī)劃問題，例如，Luo Jianchao等[11]針對(duì)由放置定時(shí)Petri網(wǎng)建模的易死鎖柔性制造系統(tǒng)的調(diào)度問題，基于網(wǎng)模型的分支樹和高度允許的死鎖控制器，提出了一種隨時(shí)分支和約束(AB&B)算法，以最大限度地減少系統(tǒng)工期。利用分支定界法，求解的主要步驟包括：對(duì)原問題進(jìn)行松弛求解獲得參考解，即忽略整數(shù)約束；若參考解為整數(shù)，則為可行解；若參考解非整數(shù)，則選擇一個(gè)非整數(shù)變量進(jìn)行“0-1”分支；對(duì)兩個(gè)子問題分別繼續(xù)遞歸求解，并通過求上下界進(jìn)行定界，以判斷是否繼續(xù)分支或剪枝。該方法保證在有限時(shí)間內(nèi)搜索完所有可能組合，并返回全局最優(yōu)解。

在本文構(gòu)建的模型中，每個(gè)項(xiàng)目是否選擇由決策變量表示，當(dāng)失敗風(fēng)險(xiǎn)ε值固定后，模型求解就可以表示為典型的0-1選擇問題。

四、算例分析

為檢驗(yàn)上述模型建立和算法求解的有效性，運(yùn)用PuLP調(diào)用內(nèi)置分支定界法的CBC求解器，進(jìn)行模擬計(jì)算。

1.算例構(gòu)造

算例中的單個(gè)項(xiàng)目參數(shù)設(shè)置：投資強(qiáng)度，即項(xiàng)目投資額/占地面積，為300—800萬元之間的任意值；項(xiàng)目占地面積為30-200畝之間的任意值；年均收益/投資額為0.1-0.3之間的任意值；失敗風(fēng)險(xiǎn)為0.1-0.5之間的任意值。算例約束條件為：總投資額不超過30億元，占地面積不超過500畝。依照項(xiàng)目參數(shù)設(shè)置，隨機(jī)生成10個(gè)項(xiàng)目的算例參數(shù)值如下表：

表2 算例參數(shù)值

2.算例求解

基于模型建立和算法求解的思路，使用Python編程語言構(gòu)建求解流程。核心代碼結(jié)構(gòu)包括：載入項(xiàng)目數(shù)據(jù)，構(gòu)造參數(shù)字典；對(duì)每個(gè)ε值設(shè)定0.2-0.5之間不同的失敗風(fēng)險(xiǎn)值；對(duì)每個(gè)ε值構(gòu)建并求解一個(gè)混合整數(shù)規(guī)劃問題；輸出所選項(xiàng)目組合、投資總額、總收益失敗風(fēng)險(xiǎn)與占地面積。結(jié)果如下表：

表3 算例解集

五、結(jié)論

混合整數(shù)規(guī)劃方法在項(xiàng)目群投資決策問題中具有顯著優(yōu)勢，其能夠有效處理多目標(biāo)沖突和多資源約束條件下的項(xiàng)目組合優(yōu)化問題。通過引入ε-約束法，可以平衡項(xiàng)目收益和風(fēng)險(xiǎn)相沖突問題，而采用分支定界法則能顯著提升大規(guī)模項(xiàng)目組合優(yōu)化問題的求解效率。該方法在當(dāng)前政府預(yù)算內(nèi)投資決策、企業(yè)戰(zhàn)略性投資規(guī)劃等復(fù)雜場景中具有良好的適用性。