作业帮什么是混合整数非线性规划问题
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/28 07:03:54
什么是混合整数非线性规划问题
什么是混合整数非线性规划问题
什么是混合整数非线性规划问题
整数规划
integer programming
一类要求问题中的全部或一部分变量为整数的数学规划.
一般认为非线性的整数规划可分成线性部分和整数部分,因此常常把整数规划作为线性规划的特殊部分.在线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常要求解答必须是整数.例如,所求解是机器的台数,工作的人数或装货的车数等.为了满足整数的要求,初看起来似乎只要把已得的非整数解舍入化整就可以了.实际上化整后的数不见得是可行解和最优解,所以应该有特殊的方法来求解整数规划.在整数规划中,如果所有变量都限制为整数,则称为纯整数规划；如果仅一部分变量限制为整数,则称为混合整数规划.整数规划的一种特殊情形是01规划,它的变数仅限于0或1.
整数规划与组合最优化从广泛的意义上说,两者的领域是一致的,都是在有限个可供选择的方案中,寻找满足一定标准的最好方案.有许多典型的问题反映整数规划的广泛背景.例如,背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、送货问题等.因此整数规划的应用范围也是极其广泛的.它不仅在工业和工程设计和科学研究方面有许多应用,而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用.
整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 ,30多年来发展出很多方法解决各种问题.解整数规划最典型的做法是逐步生成一个相关的问题,称它是原问题的衍生问题.对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）.通过松弛问题的解来确定它的源问题的归宿,即源问题应被舍弃,还是再生成一个或多个它本身的衍生问题来替代它.随即 ,再选择一个尚未被舍弃的或替代的原问题的衍生问题,重复以上步骤直至不再剩有未解决的衍生问题为止.目前比较成功又流行的方法是分枝定界法和割平面法,它们都是在上述框架下形成的.
0—1规划在整数规划中占有重要地位,一方面因为许多实际问题,例如指派问题、选地问题、送货问题都可归结为此类规划,另一方面任何有界变量的整数规划都与0—1规划等价,用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题,所以不少人致力于这个方向的研究.求解0—1规划的常用方法是分枝定界法,对各种特殊问题还有一些特殊方法,例如求解指派问题用匈牙利方法就比较方便.