第二讲 整数规划与非线性规划.pdf

《第二讲 整数规划与非线性规划.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、整数规划与非线性规划什么是整数规划？¢定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。2整数规划的分类¢变量全限制为整数时，称纯（完全）整数规划。¢变量部分限制为整数的，称混合整数规划。¢变量只能取0或1时，称之为0-1整数规划。34例2背包问题5整数规划特点(1)原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：¾原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。¾原线性规划最优解不全是整数，

2、则整数规划最优解小于原线性规划最优解或整数规划最优解大于原线性规划最优解。¾整数规划无可行解。(2)整数规划最优解不能按照实数最优解简单取整而获得。6整数规划求解方法分类（i）分枝定界法—可求纯或混合整数线性规划。（ii）割平面法—可求纯或混合整数线性规划。（iii）隐枚举法—求解“0-1”整数规划：①过滤隐枚举法；②分枝隐枚举法。（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）7分枝定界法¢首先，不考虑变量的整数约束，求解相应的线性规划，得到线性规划的最优解。如果线性规划的最优解恰好是整数解，则这个解就是整数规划的最优解。¢如果线性规划的最优解中至少有一个变量不是整数，把线性规划的

3、可行域切割成两部分，分别求解两个线性规划的最优解。¢如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。这个过程，叫做“分枝”。¢分枝过程得到的整数解中，目标函数值最大的一个叫做整数规划目标函数值的“界”。分枝过程中非整数的线性规划的最优解，如果目标函数值小于或等于这个“界”，就停止继续分枝。这个过程，叫做“定界”。8maxz=3x+5x28.91254(x1,x2)=(3.8,3.5)321z=28.9z=2401234567z=19z=159maxz=3x+5x28.91228.528.654321z=28.9z=2401234567z=19z=1510maxz=3x+

4、5x28.91228.528.6528244321z=28.9z=2401234567z=19z=1511maxz=3x+5x28.91228.528.652824427321z=28.9z=2401234567z=19z=1512maxz=3x+5x28.91228.528.65282442732621z=28.9z=2401234567z=19z=1513maxz=3x+5x28.91228.528.652824272842732621z=28.9z=2401234567z=19z=1514最优解：x=4,x=3,maxz=2728.91228.528.65282427284272532

5、621z=28.9z=2401234567z=19z=1515Lingo软件实现¢Lingo可用于求解纯整数规划或混合整数规划。¢原理：分支定界程序16变量界定函数¢变量界定函数实现对变量取值范围的附加限制:@bin(x)限制x为0或1@bnd(L,x,U)限制L≤x≤U@free(x)取消对变量x的默认下界为0的限制@gin(x)限制x为整数在默认情况下，lingo规定变量是非负的，也就是说下界为0，上界为+∞。@free取消了默认的下界为0的限制，使变量也可以取负值。@bnd用于设定一个变量的上下界,它也可以取消默认下界为0的约束17例1集装箱运货18Lingo:max=20*x1+10

6、*x2;5*x1+4*x2<=24;2*x1+5*x2<=13;@gin(x1);@gin(x2);19Globaloptimalsolutionfoundatiteration:0Objectivevalue:100.0000VariableValueReducedCostX14.000000-20.00000X22.000000-10.00000RowSlackorSurplusDualPrice1100.00001.0000002-4.0000000.0000003-5.0000000.000000200-1型整数规划¢0-1型整数规划是整数规划中的特殊情形，它的变量x仅取值0或1。这

7、时x称为0-1变量，或jj称二进制变量。x仅取值0或1这个条件可由下j述约束条件：01≤x≤整数j所代替，是和一般整数规划的约束条件形式一致的。21例3选址问题¢某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）A(i=1,2,…,7)可供选择。规定i1.在东区：由A1,A2,A3三个点中至多选两个；2.在西区：由A4,A5两个点中至少选一个；3.在南区：由A6,A7两个点中至少选一个。¢如选用点A