整数规划问题及分配问题

《整数规划问题及分配问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、整数规划（IP）及分配问题要求一部分或全部决策变量必须取整数值的规划问题称为整数规划（integerprogramming，简记IP）。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松驰问题（slackproblem）。若松驰问题是一个线性规划，则称该整数规划为整数线性规划（integerlinearprogramming）。一、整数规划问题的数学模型§7-1整数规划问题的数学模型及解的特点整数线性规划数学模型的一般形式为:3.0-1型整数线性规划(Zero-oneintegerlinearprogramming)：指决策变量只能了

2、取值0或1的整数线性规划。1.纯整数线性规划(Pureintegerlinearprogramming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。2.混合整数线性规划(Mixedintegerlinearprogramming）：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。整数线性规划问题可以分为下列几种类型：例7-1某厂生产和两种产品，需要经过三道工序。单件工时和利润以及各工序每周工时限额见表7-1。问工厂应如何安排生产，才能使总利润最大？表7-1工序工时/件产品利润（元/件）0.30.20.3250.70

3、.10.540工时限制（h/周）250100150二、整数规划的例子解设工厂每周生产产品件，产品件。则该问题的数学模型为这是一个纯整数线性规划问题。例7-2某服务部门各时段（每2小时为一时段）需要的服务人数见表7-2。按规定，服务员连续工作8小时（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。表7-2时段12345678服务员最少数目10891113853解设在第时段开始时上班的服务员人数为。由于第时段开始时上班的服务员人数将在第时段结束时下班，故决策变量只需要考虑。数学模型为:这也是一个纯整数线性规划问题。三、解的特点松驰问题作为一个

4、线性规划问题，其可行解的集合是一个凸集，任意两个可行解的凸组合仍为可行解。整数规划问题的可行解是它松驰问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。由于整数规划问题的可行解一定也是它的松驰问题的可行解（反之则不一定），所以，前者最优解的目标函数值不会优于后者最优解的目标函数值，即松弛问题的最优解是整数规划问题最优解的上限。在一般情况下，松驰问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，自然就不是整数规划的最优解。此时，若对松驰问题的这个最优解中不符合整数要求的分量简单地取整，所得到的解不一定是

5、整数规划问题的最优解，甚至也不一定是整数规划问题的可行解。§7-2分支定界法7.2.1思路与解题步骤（只解松弛问题）1、在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程若松弛问题最优解中某个xk=bk不是整数，令[bk]为bk的整数部分构造两个新的约束条件xk≤[bk]和xk≥[bk]+1，分别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题—定界过程设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况表7.2.1分枝问题解可能出现的情况情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题

6、1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或5计算过程可利用灵敏度分析（增加约束条件），简化问题的计算量序号问题１问题２说明１无可行解无可行解整数规划无可行解２无可行解整数解问题２的整数解为最优解３无可行解非整数最优解对问题２进行分支４整数解整数解较优解为最优解５整数解，目标函数优于问题２非整数解问题１的整数解为最优解６整数解非整数解，目标函数优于问题１对问题１剪枝，其整数解为界，对问题２继续分支例1：求解下述问题：minz=-40x1-90x2s.t.9x1+7x2≤567x1+20x2≤70xj≥0,整数，j=1，2算例

7、20x1x21（4.81，1.82）234561347K0(K0):X*=(4.81,1.82)TZ*=-356松弛问题的可行域和最优解20x1x21（4.81，1.82）234561347(K1)(K1):X1*=(4.00,2.10)TZ1*=-349(K2)(K2):X2*=(5.00,1.57)TZ2*=-34120x1x21（4.81，1.82）234561347(K3)(K3):X3*=(4.00,2.00)TZ3*=-340(K2)(K4):X4*=(1.42,3.00)TZ4*=-327(K4)20x1x21234561347(K3)(K5):X5

8、*=(5.