整数规划问题--毕业论文.doc

整数规划问题--毕业论文
目 录
摘要 I
Abstract II
引言 1
1 整数规划问题 1
概念 1
分类 2
整数规划的一般形式 2
2 整数规划问题的计不符合整数条件，则增加新约束——缩小可行域；将原整数规划问题分支——分为两个子规划，再解子规划的伴随规划，以此类推，最后得到原整数规划的伴随规划。这就是所谓的“分支”。
所谓“定界”，是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个“界限”，可以作为衡量处理其它分支的一个依据。
“分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索的效率。


分支定界法的计算步骤
第一步：计算原问题目标函数值的初始上界
第二步：计算原问题目标函数值的初始下界
第三步：增加约束条件将原问题分支
第四步：分别求解一对分支
第五步：修改上、下界
第六步：比较上、下界大小，如有上界＝下界，停止计算，找到最优解，否则转3
割平面法
割平面法由高莫瑞(Gomory)于1958年提出。其基本思想是放宽变量的整数约束，首先求对应的松弛问题最优解，当某个变量不满足整数约束时，寻找一个约束方程并添加到松弛问题中，其作用是割掉非整数部分，缩小原松弛问题的可行域，最后逼近整数问题的最优解。
增加的新约束称为割平面方程或切割方程
(1)设是相应线性规划最优解中为分数值的一个基变量，则由单纯形表的最终表得到
()
(2)将拆分成整数部分N和非负真分数之和，即：
()


表示不超过的最大整数。
将()式代入(1)式
（）
其中，
就是割平面方程的最基本形式。
割平面法解整数规划问题的基本步骤
第一步：用单纯形法解松弛问题，得到最优单纯形表。
第二步：求一个割平面方程，加到最优单纯形表中，用对偶单纯形法继续求解。
第三步：若没有得到整数最优解，则继续作割平面方程，转第二步。
3 整数规划问题的应用

投资问题
设有个投资项目及年内逐年投入资金矩阵，其中为第年的投资金额，以及投资矩阵，其中为第年项目所需投入资金。利润矩阵，为项目的利润。
投资问题即在提供的资金的容许条件下，求利润最高的投资决策。
设


则该问题的数学模型为：
例1. 某公司在今后五年内考虑给以下的项目投资。已知：
项目A：从第一年到第四年每年年初可以投资，并于次年末回收本利115%， 但第一年如果投资则最低金额为4万元，第二、三、四年不限；
项目B：第三年初可以投资，到第五年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元；
项目 C：第二年初可以投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。
项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。
该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?
解： 设分别表示第 年年初给项目A，B，C，D的投资额；
设是0—1变量
设 是非负整数变量，并规定：第2年投资C项目8万元时，取值为4；第 2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第


2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0；
目标函数及模型：
生产安排问题
（1） 静态生产安排问题
设有个生产行业，都需要某种资源。对于第个生产行业，如果用第种资源生产，，现有资金。问应购买第中资源多少单位，分配到个生产行业，使总利润最大？
此题的数学模型为：


例2. 有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见表3-1。要求制订一个生产计划，使总收益最大。
表3-1 资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费