整数规划属于运筹学的一个分支,同属于运筹学的还有:线性规划,非线性规划,网络规划,组合优化,动态规划,多目标优化,随机规划,决策分析,对策论,排队论,风险管理等。
在线性规划模型中,最后所得到的最优解有可能是整数,也有可能不是整数,但在现实生活中,在求人数、次数、个数、项目数等要求最优解是整数时,非整数的答案显然不符合要求,于是就产生了整数规划这一分支。整数规划是指带整数变量的最优化问题,即最大化或者最小化一个全部或部分变量为整体的多元函数受约束于一组等式和不等式条件的最优化问题。整数规划问题是要求解决决策变量取了整数时的线性规划或非线性规划问题。本文只讨论整数线性规划的问题,它是在线性规划的基础上,对全部决策变量或是部分决策变量的取值加以整数约束条件时而得到的,故而认为整数规划问题要比对应的线性规划问题的约束条件更紧,求解也更加困难。整数规划是离散型优化问题,是数学规划中较弱的一个分支,迄今为止,还没有求解整数规划问题较好的方法,但是在经济管理中很多实际问题又都可以归为整数规划问题,由此,讨论整数规划的解法就显得尤为重要。
1.2整数规划数学模型的一般形式
定义1 在一个数学规划问题中,当它的全部决策变量或者部分决策变量取整数时论文网,就称为整数规划问题。特别地,但这个数学规划问题是线性规划问题时,那么就称之为整数线性规划问题。
由定义1 可得如下整数线性规划问题的教学模型:
maxZ (或 minZ)=∑_(j=1)^n▒c_j x_j
s.t. {█(∑_(j=1)^n▒a_ij x_j=(≤、≥)b_i (i=1,2,…,m)@x_j≥0(j=1,2,…,n)且部分或全部为整数)┤
在上述模型中,去掉对变量取整数的要求而得到的线性规划问题,称为整数规划问题的松弛问题。
1.3整数规划的分类及建模举例
根据决策变量取整数的要求不同,整数规划可分为以下几类:
混合整数规划
定义2 部分决策变量取整数时的线性规划问题称为混合整数规划。
某家工厂计划在n个地点中选择若干个地点建立分工厂,以满足m个销售地的需求。在选择分工厂的地点时,需要考虑以下几个因素:①建立分工厂i的固定成本f_i;②分工厂i的预计生产能力t_i;③第j个销售地的需求量d_i;④第i个分工厂到第j个销售地的单位运价c_ij。问:该公司在哪些地点建立分工厂可以使得公司的产品既能满足消费需求又使得总费用最少?