运筹学PPT 第四章 线性整数规划
- 格式:ppt
- 大小:510.50 KB
- 文档页数:22
第四章整数规划整数规划(Integer Programming)主要是指整数线性规划。
一个线性规划问题,如果要求部分决策变量为整数,则构成一个整数规划问题,在项目投资、人员分配等方面有着广泛的应用。
整数规划是近二、三十年发展起来的数学规划的一个重要分支,根据整数规划中变量为整数条件的不同,整数规划可以分为三大类:所有变量都要求为整数的称为纯整数规划(Pure Integer Programming)或称全整数规划(All integer Programming);仅有一部分变量要求为整数的称为混合整数规划(Mixed Integer Programming);有的变量限制其取值只能为0或1,这类特殊的整数规划称为0-1规划。
本章主要讨论整数规划的分枝定界法、割平面法、0-1规划及指派问题。
第一节整数规划问题及其数学模型一、问题的提出在线性规划模型中,得到的最优解往往是分数或小数,但在有些实际问题中要求有的解必须是整数,如机器设备的台数、人员的数量等,这就在原来线性规划模型的基础上产生了一个新的约束,即要求变量中某些或全部为整数,这样的线性规划称为整数规划(Integer Programming)简称IP,是规划论中的一个分枝。
整数规划是一类特殊的线性规划,为了满足整数解的条件,初看起来,只要对相应线性规划的非整数解四舍五入取整就可以了。
当然在变量取值很大时,用上述方法得到的解与最优解差别不大,当变量取值较小时,得到的解与实际最优解差别较大,当变量较多时,如n=10个,则整数组合有210=1024个,而且整数解不一定在这些组合当中。
先来看下面的例子。
例4.1某工厂生产甲、乙两种设备,已知生产这两种设备需要消耗材料A、材料B,有关数据如下,问这两种设备各生产多少使工厂利润最大?表4-112量都要求为整数,建立模型如下:2123max x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,5.45.01432x x x x x x x x 要求该模型的解,首先不考虑整数约束条件④,用单纯形法对相应线性规划求解,其最优解为:x 1=3.25 x 2=2.5 max z =14.75由于x 1=3.25,x 2=2.5都不是整数,不符合整数约束条件。