整数规划-经济百科

整数规划(integERProgramming)

在经济建设中，企业总有各种各样的投资机会，每一种投资机会又有多种的投资方式，每一种投资方式都称为一个投资方案，所以经济建设中企业总有多方案可供选择，同时需要大量的资源，而资源是有限的，因此企业要根据有限的资源确定投资方案的顺序，使有限的资源取得最大的效益。即经济建设中企业要进行多方案的最佳选择。

一、多方案选择的传统方法

多方案的选择，必须明确各方案之间的关系，方案之间关系不同，其选择的方法也不同。方案之间的关系可以概括为互斥型、独立型和混合型。

1.互斥型方案的选择

互斥方案就是相互之间存在互不相容、互相排斥关系的一组方案。互斥方案经济效果评比的实质是判断增量投资的经济合理性，评比的基本方法是增量分析法，根据反映增量经济效果的指标的不同，增量分析法可细分为静态的差额投资收益率法和差额投资回收期法、动态的差额净现值法和差额内部收益率法等。由于资金时间价值是客观存在、不容忽视的，动态评价方法对互斥方案的评价更为客观科学，因此，实际工作中，主要应用差额净现值法和差额内部收益率法评比互斥方案，其中由差额净现值法导出了净现值最大准则和净年值最大准则，净现值最大准则用于寿命期相同的互斥方案评比，净年值最大准则用于寿命期不同的互斥方案评比。用NPV和NAV评比互斥方案可以把绝对经济效果评价与相对经济效果比较结合起来，直接进行方案的选择，而△NPV和△IRR只适用于方案的比较而不适用于方案的选择。

2.独立型方案的选择

独立方案是相互之间互不影响的一组方案。受资源限制的独立方案的选择方法有两种，即独立方案的互斥化法和双向均衡排序法。

(1)独立方案的互斥化法。该方法首先把各独立方案形成互斥的方案组合；其次选出能满足资金限制的方案组合；最后用互斥方案评选方法评选最优方案组。

该方法的优点是保证能选出受资源限制的情况下收益最大的方案组合。其不足是当独立方案数目较多时，形成的互斥方案组的数目众多，计算复杂：每一个独立方案都有拒绝或接受两种可能，如果有N个互相独立的方案，所形成的互斥方案组合就有2。

(2)层混方案的双向均衡排序法。该方法用增量效率指标来反映互斥方案的经济效果，所以也称增量效率指标排序法。具体步骤：

淘汰无资格方案：若,则方案k为无资格方案，即如果一笔基础投资的利用效率低于其增量投资的利用效率，那么就认为该基础投资方案是无资格方案，应予以淘汰；计算有资格方案的约束资源的增量效率指标，并按该指标由大到小排序，受资金限制的层混方案的约束资源增量效率指标为△IRR、△NPVR、△R／△I等；计算资源代价率及资源代价并绘图；标注资源约束条件，如资源限额、基准收益率等；比选最优方案组。

该方法的不足是如果资源约束线分割了方案，那么所选择的方案组可能不是真正的最优方案组；如果被分割的方案恰好包含无资格方案，那么真正的最优方案组可能恰恰包含被当作无资格方案淘汰掉的方案。

二、整数规划在多方案选择中的应用

传统方法一般只能对受一种资源约束的多方案进行选择，而整数规划可以解决受多种资源约束的多方案选择问题，并克服传统方法的不足，保证选出受资源限制情况下的收益最大的方案组合。

1.评选目标

考虑到方案间的经济寿命可能不相等，用净年值最大作为评选目标。

目标函数：

。

(CI?CO)tj方案j在第t年的净现金流量；m：方案的总个数；n：方案i的经济寿命；Xj：决策变量，Xj=0表示放弃i方案，Xj=1表示接受方案。

2.结束条件

由具体情况而定，一般由资源约束和关系约束组成：

(1)资源约束(资金、人工、设备、原材料等):且，式中：Ctj：方案i在第t年耗用的资源量；Bt：第t年的资源可用量；B：资源总量。

(2)关系约束：

互斥方案的约束：,表示m个方案中最多只能选取一个。独立方案的约束：,示m个方案中每一个都可以被选中。混合方案的约束:且，式中：K为互相独立的项目数；m1为第k个项目的互斥方案数目。从属关系约束，表示A方案只有当B方案选用时才有意义，即不选用B方案就不能选用A方案。严格互补关系约束：XC?XD=0，表示C方案和方案D必须同时选用或同时不选用。

三、整数规划对混合案选择的例证

例如某石化公司下属三个工厂各自独立，分别提出互斥型投资方案，如表。各投资方案的有效期均为l0年，基准收益率为10%。如果这个公司仅有80000万元可供投资，应如何选择方案对公司最有利?

工厂ABC方案AlA2A3BlB2B3B4ClC2投资300004000050000l00002000030000400002000030000年净收益97001080013800l63051007170866050008400

解：设目标函数为净年值最大，则目标函数：

math>\maxNAV=\sum_{j=1}^9\sum_{t=0}^10(CI-CO)_{tj}(P/F,10%,t)(A/P,10%,10)\CDOtX_j,X_j=0,1</math>。

约束条件：。

计算结果为：Xl=1,X2=0,X3=0,X4=0,X5=1,X6=0,X7=0,X8=0,X9=1。

即应选择Al、B2、C2三个方案。