运筹学-整数规划建模

《运筹学-整数规划建模》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章整数规划北京理工大学珠海学院廖爱红aihongliao@126.com本章内容要点整数规划相关概念整数规划问题的一般特点整数规划建模举例引例经济管理当中经常存在人员分派问题，企业中有4个人可以胜任4项不同工作的任意一项，但是完成工作的效率有所不同。如表所示：为了使得企业获得最好的经济效益，应该如何分派这四个人完成四项不同工作？6.1整数规划问题的提出6.1.1问题特征变量取值范围是离散的，经典连续数学中的理论和方法一般无法直接用来求解整数规划问题。不考虑整数条件，由余下的目标函数和约束条

2、件构成的规划问题称为整数规划问题的松弛问题。若松弛问题是一个线性规划问题，则称该整数规划问题为整数线性规划问题。整数线性规划问题的分类：纯整数线性规划问题：要求全部变量均取整数混合整数线性规划问题：要求部分变量取值为整数0-1整数线性规划问题：决策变量取值为0或16.1.2整数规划建模中常用的处理方法（1）资本预算问题设有n个投资方案，cj为第j个投资方案的收益。投资过程共分为m个阶段，bi为第i个阶段的投资总量，aij为第i阶段第j项投资方案所需要的资金。目标是在各阶段资金限制下使整个投资的总

3、收益最大。设决策变量xj为对第j个方案的取（xj=1）或舍（xj=0），可得到下列整数规划问题，是0—1规划。yjyjyjxxij为整数该问题的约束反映了第i个时期资金增长量的平衡。这里aij代表第i时期内第j项投资的净资金流量：①aij>0，表示需附加资金；②aij<0，表示该项投资在第i时期内产生资金。右端项bi表示第i时期外源资金流量的增长量：①bi>0，表示有附加资金的数量；②bi<0，表示要抽回资金的数量。9例．某公司考虑今后五年内给以下项目投资。项目A：每年年初可以投资，于次年末回收

4、本利115%，投资金额必须为1万元的整数倍；项目B：每年初可购买公债，于当年末归还，并加利息6%，投资金额必须为1万元的整数倍；项目C：第2年初可以投资，到第5年未能回收本利140%，投资金额必须为1万元的整数倍；项目D：第3年初可以投资，到第5年未能回收本利128%，如果投资金额必须大于2万元；该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第5年末拥有的资金本利总额为最大?10解：1)设xiA、xiB、xiC、xiD(i＝1，2，3，4，5)分别表示第i年年初给项目A，B，

5、C，D的投资额；变量：第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx1Bx2Bx3Bx4Bx5BCx2CDx3D6.1.2建模中常用的处理方法（续）（2）指示变量：指示不同情况的出现P139例.有m个仓库，要决定动用哪些仓库，满足n个顾客对货物的需要，并决定从各仓库分别向不同顾客运送多少货物？6.1.2建模中常用的处理方法（续）费用:fi:动用i仓库的固定运营费（租金等）cij:从仓库i到j顾客运送单位货物的运费约束条件：i)每个顾客的需要量dj必须得到满足；ii)只能从动用的仓库

6、运出货物。6.1.2建模中常用的处理方法（续）取足够大的数，迫使当yi=0时，xij必须为06.1.2建模中常用的处理方法（续）（3）线性规划模型的附加条件在许多实际问题中，线性规划模型中的约束条件允许一定范围的放宽或对个别因素有进一步限制时，常可通过引入0—1变量来处理。下面介绍几种情况，作为一种建模思路的启示。①不同时成立的约束条件。设某个模型问题中的约束条件不必同时成立，有m个线性不等式约束对每个约束引入一个指示变量yi，并得到每个约束左端的一个上界Mi(i=1,2,…,n)，建立下列不等

7、式：显然，当yi=1时，两式等价；当yi=0时，第二个式子是恒成立，相当于除去了这个限制。在实际问题中，如果至少有k个约束成立时，只需附加下列约束：②最优解中非零分量个数的限制。在许多实际问题中，对最优解中的非零分量个数有所限制。类似上述分析可对每个决策变量xi找到其上界Mi，并引入指示变量yi。附加下式（6-4）（6-5）式（6-5）说明，非零分量至多有k个。③离散的资源变化。实际问题中常出现下列情况：不等式约束表示右端的值可以有k个等级的违背，而，这里b0为最低的限制，在这个限制下，不需付出

8、代价；其余的限制bi（i=1,2,…,k）各需相应付出代价ci（i=1,2,…,k），自然有：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总利润？案例假设上表甲乙两种产品利润中仅未去除用电成本。已知：用电500度以内总成本为0；用电1千度以内总成本为100元；1-2千度总成本为300元；2-3千度总成本为600元；3千度以上成本为1500元。用电量8070