练习|整数规划模型——分枝定界法

一、练习题目

 1.抛开限制为整数条件不谈，首先利用matlab求解出答案：

>> f = [-4 5];
>> A = [1 4; 3 -4];
>> b = [10;6];
>> Aeq = [];
>> beq = [];
>> lb = [0 0];
>> ub = [inf inf];
>> [x fval] = linprog(f,A,b,Aeq,beq,lb,ub)Optimal solution found.x =4.00001.5000fval =-8.5000

我们发现x1=4，x2=1.5为最优解，但此时，x2不是整数。所以接下来，我们将x2的分枝为两部分B1和B2，分别在父问题的基础上增加约束x2 ≤ 1和x2 ≥ 2；

1.1分枝x2 ≤ 1：求解出x1 = 3.3 ； x2 = 1； 最大值为18.3，由于x1 = 3.3，并不是整数，所以将x1划分为x1 ≤ 3；和x1 ≥ 4 两部分，继续分解

>> f = [-4 -5];
>> A = [1 4; 3 -4];
>> b = [10;6];
>> Aeq = [];
>> beq = [];
>> lb = [0 0];
>> ub = [inf 1];
>> [x,fval] = linprog(f,A,b,Aeq,beq,lb,ub)Optimal solution found.x =3.33331.0000fval =-18.3333

 1.1.1分枝x2 ≤ 1； x1 ≤ 3；求解出 x1 = 3； x2 = 1，最大值为17，最优解

>> f = [-4 -5];
>> A = [1 4;3 -4];
>> b = [10;6];
>> Aeq = [];
>> beq = [];
>> lb = [0 0];
>> ub = [3 1];
>> [x,fval] = linprog(f,A,b,Aeq,beq,lb,ub)Optimal solution found.x =31fval =-17

1.1.2 分枝x2 ≤ 1； x1 ≥ 4；无解

>> f = [-4 -5];
>> A = [1 4; 3 -4];
>> b = [10;6];
>> Aeq = [];
>> beq = [];
>> lb = [4 0];
>> ub = [inf 1];
>> [x,fval] = linprog(f,A,b,Aeq,beq,lb,ub)No feasible solution found.Linprog stopped because no point satisfies the constraints.x =[]fval =[]

1.2分枝x2 ≥ 2；求解结果x1 = 2；x2 = 2,；最优解:z = 18

>> f = [-4 -5];
>> A = [1 4; 3 -4];
>> b = [10;6];
>> Aeq = [];
>> beq = [];
>> lb = [0 2];
>> ub = [inf inf];
>> [x,fval] = linprog(f,A,b,Aeq,beq,lb,ub)Optimal solution found.x =2.00002.0000fval =-18

综上比较，整数可行解（x1，x2）=（2,2），最优解为18和（x1，x2）=（3,1），最优解为17；由于题目求解最大值，max z ；故（x1，x2）=（2,2）为所求解！