第三章整数线性规划

第三章 整数线性规划本章, 我们介绍三种解决整数线性规划问题的软件:第一种: MATLAB 中的 optimization toolbox 中的若干程序;第二种: LINDO 软件;第二种: LINGO 软件.1. MATLAB 程序说明程序名: intprogram, L01p_e, L01p_ie, transdetobi, biprogramintprogram 是利用分支定界法解决整数规划问题, 是全部的整数规划问题;L01p_e 是利用枚举法解决 0-1 规划问题, 变量要求全部为 0 或者 1;L01p_ie 是利用隐枚举法解决 0-1 规划问题, 变量要求全部为 0 或者 1;Transdetobi 是枚举法和隐枚举法中利用到的将十进制数转化为二进制数的函数;Biprogram 是 MATLAB6.5 以上版本中有的求解 0-1 规划的函数的程序 .intprogram 执行实例 1： 1221max0s.t543, fxx 且 为 整 数在命令窗口的程序执行过程和结果如下: c=-20,-10; %将最大转化为最小; a=5,4;2,5; b=24;13; x,f=intprogram(c,a,b,0;0,inf;inf,0,0.0001) % c,a,b 之后0;0 is the value of low bound;inf;inf is the value of up bound; is the initialization;0 is the number of the equation constraints; 0.0001 is the concise rate.x =4.00001.0000f =-90intprogram 执行实例 2: 书中例题 3.3.1在命令窗口的程序执行过程和结果如下: c=-1,-1; a=-4,2;4,2;0,-2; b=-1;11;-1; x,f=intprogram(c,a,b,0;0,inf;inf,0,0.0001)x =2 21 1f =-3L01p_e 和 L01p_ie 执行实例 : 123312312max5s.t 4 6,01fxx 或在命令窗口的程序执行过程和结果如下: c=3,-2,5; %将最大转化为最小 ; a=1,2,-1;1,4,1;1,1,0;0,4,1; b=2;4;3;6; x1=L01p_e(c,a,b);x2=L01p_ie(c,a,b); %x1 表示利用枚举法解决 0-1 规划问题，x2 表示用隐% 枚举法解决问题 , 结果是一样的 x1x1 =010 x2x2 =010biprogram 执行实例: 1234123434124min()956s.t69 0 fxxxx -在命令窗口的程序执行过程和结果如下：the program is with the binary linear programmingPlease input the constraints number of the programming m=4m =4Please input the variant number of the programming n=4n =4Please input cost array of the objective function c(n)_T=-9,-5,-6,-4c =-9-5-6-4Please input the coefficient matrix of the constraints A(m,n)=6,3,5,2;0,0,1,1;-1,0,1,0;0,-1,0,1A =6 3 5 20 0 1 1-1 0 1 00 -1 0 1Please input the resource array of the program b(m)_T=9,1,0,0b =9100Optimization terminated successfully.x =1100程序的相关知识:Solve binary integer programming problems of the formwhere f, b, and beq are vectors, A and Aeq are matrices, and the solution x is required to be a binary integer vector - that is, its entries can only take on the values 0 or 1.语法如下:x = bintprog(f)x = bintprog(f, A, b)x = bintprog(f, A, b, Aeq, beq)x = bintprog(f, A, b, Aeq, beq, x0)x = bintprog(f, A, b, Aeq, beq, x0, options)x, fval = bintprog(.)x,fval, exitflag = bintprog(.)x, fval, exitflag, output = bintprog(.)解释:x = bintprog(f) solves the binary integer programming problemx = bintprog(f, A, b) solves the binary integer programming problemx = bintprog(f, A, b, Aeq, beq) solves the preceding problem with the additional equality constraint.x = bintprog(f, A, b, Aeq, beq, x0) sets the starting point for the algorithm to x0. If x0 is not in the feasible region, bintprog uses the default initial point.x = bintprog(f, A, b, Aeq, Beq, x0, options) minimizes with the default optimization options replaced by values in the structure options, which you can create using the function optimset.x, fval = bintprog(.) returns fval, the value of the objective function at x.x,fval, exitflag = bintprog(.) returns exitflag that describes the exit condition of bintprog. See Output Arguments.x, fval, exitflag, output = bintprog(.) returns a structure output that contains information about the optimization. See Output Arguments.2LINDO 程序说明LINDO 也提供了解决全整数规划、混合整数规划以及 0-1 规划的方法.2.1 解决全整数规划问题程序名: intlpallintlpall 执行实例: min10s.t2 3, xyxy 且 为 整 数在命令窗口键入以下内容:max 11x+10yst2x+y1endgin x ! the general integer statement GIN 将变量约束为整数gin y ! the general integer statement GIN 将变量约束为整数按 solve 键在 reports window 出现:LP OPTIMUM FOUND AT STEP 7OBJECTIVE VALUE = 72.4285736NEW INTEGER SOLUTION OF 66.0000000 AT BRANCH 0 PIVOT 12BOUND ON OPTIMUM: 66.00000ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 12LAST INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE1) 66.00000VARIABLE VALUE REDUCED COSTX 6.000000 -11.000000Y 0.000000 -10.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 0.0000003) 5.000000 0.000000NO. ITERATIONS= 12BRANCHES= 0 DETERM.= 1.000E 02.2 解决混合整数规划问题：程序名：intlpsec intlpsec 执行实例： min10s.t2 3, xyxyx 且 为 整 数在命令窗口键入以下内容:max 11x+10yst2x+y1endgin x ！only the general integer statement GIN 只将变量 x 约束为整数按 solve 键在 reports windows 中出现以下内容:LP OPTIMUM FOUND AT STEP 2OBJECTIVE VALUE = 72.4285736SET X TO = 6 AT 1, BND= 66.00 TWIN= 68.33 16NEW INTEGER SOLUTION OF 66.0000000 AT BRANCH 1 PIVOT 16BOUND ON OPTIMUM: 68.33334FLIP X TO = 1 AT 1, BND= 112.0 TWIN= 84.00 9NEW INTEGER SOLUTION OF 112.000000 AT BRANCH 1 PIVOT 9BOUND ON OPTIMUM: 112.0000DELETE X AT LEVEL 1ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 9LAST INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE1) 112.0000VARIABLE VALUE REDUCED COSTX 1.000000 20.000000Y 10.000000 0.000000Z 1.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 8.0000003) 0.000000 12.0000004) 6.000000 0.000000NO. ITERATIONS= 10BRANCHES= 1 DETERM.= 1.000E 03. LINGO 程序说明除了特别说明, LINGO 默认变量是非负的以及连续的, 但是可用以下命令使得变量满足要求:GIN restricts a variable to being an integer value,BIN makes a variable binary (i.e., 0 or 1),FREE allows a variable to assume any real value, positive or negativeBND limits a variable to fall within a finite range 等.程序名: intlp (该程序主要是解决整数线性规划问题的, 用上述命令赋予变量属性.)intlp 执行实例:max105s.t26 ,0 yxy 且 为 整 数在模型命令窗口键入以下内容:max=100*x+150*y;x=100;y=120;x+2*y=160;gin(x);gin(y);！若要只限制 x,只要限制 x 即可.按运行按钮在 solution report 窗口得到以下结果:Global optimal solution found at iteration: 2Objective value: 14500.00Variable Value Reduced CostX 100.0000 -100.0000Y 30.00000 -150.0000Row Slack or Surplus Dual Price1 14500.00 1.0000002 0.000000 0.0000003 90.00000 0.0000004 0.000000 0.000000程序名: bilpbilp 的执行实例: 123123231max5.46,01fxxstxor 在模型命令窗口键入以下内容:max=-3*x1+2*x2+5*x3;x1+2*x2-x3=2;x1+4*x2+x3=4;x1+x2=3;4*x2+x3=6;bin(x1);bin(x2);bin(x3);按运行按钮在 solution report 窗