• 备战数学建模48-数学规划模型终结篇(全)(攻坚战13)

    数学规划是运筹学的一个分支，其用来研究在给定约束条件下，如何按照某一目标函数，寻求最优方案，准确地说就是求解目标函数在某一条件下的极值问题，规划类问题是数学建模中很重要的问题，常见的有线性规划，非线性规划，整数规划，0-1规划，最大最小化模型，多目标规划等。

    目录

    一、概述

    1.1、数学规划的概念和表现形式

    1.2、数学规划的分类

    二、线性规划类问题

    2.1、Matlab线性规划问题的求解

    2.2、线性规划问题的典型案例1生产决策问题

    2.3、线性规划问题典型案例2投料问题

    三、非线性规划类问题

    3.1、非线性规划问题的求解

    3.2、非线性规划典型例题选址问题

    四、整数规划类问题

    4.1、整数规划类问题求解

    4.2、 整数规划典型例题1之背包问题

    4.3、 整数规划典型例题2之指派问题

    4.4、整数规划典型例题3之钢管切割问题

    五、最大最小化模型

    5.1、最大最小化模型的一般形式

    5.2、最大最小化问题经典例题

    六、多目标规划问题

    6.1、多目标规划处理方法

    6.2、多目标规划经典案例

    一、概述

    1.1、数学规划的概念和表现形式

    数学规划就可以理解为求目标函数在约束条件下的极值问题，数学规划的一般形式包含目标函数，决策变量和约束条件三部分。

    1.2、数学规划的分类

    一般将规划类问题分为线性规划，非线性规划，整数规划和0-1规划，具体如下：

    二、线性规划类问题

    2.1、Matlab线性规划问题的求解

    我们看一下下面的三个线性规划问题，基本上大同小异，我们可以使用matlab的linprog函数求解。

    对于matlab求解线性规划问题，有如下问题需要注意，c表示目标函数，A，b表示不等式约束，Aeq，beq表示等式约束，lb,ub分别表示上下界，x0表示初始。

    上面三个题目的matlab求解代码如下：

    1. c = [-5 -4 -6]';  % 加单引号表示转置
    2. A = [1 -1 1;
    3.         3 2 4;
    4.         3 2 0];
    5. b = [20 42 30]';   
    6. lb = [0 0 0]'; 
    7. [x fval] = linprog(c, A, b, [], [], lb)  % ub我们直接不写，则意味着没有上界的约束
    1. c = [0.04 0.15 0.1 0.125]';  
    2. A = [-0.03 -0.3 0 -0.15;
    3.         0.14 0 0 0.07];
    4. b = [-32 42]';
    5. Aeq = [0.05 0 0.2 0.1];
    6. beq = 24;
    7. lb = [0 0 0 0]';
    8. [x fval] = linprog(c, A, b, Aeq, beq, lb)
    1. c = [-2 -3 5]';
    2. A = [-2 5 -1;
    3.           1 3 1];
    4. b = [-10 12];
    5. Aeq = ones(1,3);
    6. beq = 7;
    7. lb = zeros(3,1);
    8. [x fval] = linprog(c, A, b, Aeq, beq, lb)
    9. fval = -fval % 注意这个fval要取负号（原来是求最大值，我们添加负号变成了最小值问题）

    2.2、线性规划问题的典型案例1生产决策问题

    我们看一下下面这个例题，一个生产决策的问题，就是根据决策变量写出目标函数和约束条件，最后求解目标函数的最大值即可。

     

     matlab求解上述线性规划问题的代码如下，就是使用linprog函数求解：

    1. %% 生产决策问题
    2. format long g   %可以将Matlab的计算结果显示为一般的长数字格式（默认会保留四位小数，或使用科学计数法）
    3. % (1) 系数向量
    4. c = zeros(9,1); % 初始化目标函数的系数向量全为0
    5. c(1) = 1.25 -0.25 -300/6000*5;  % x1前面的系数是c1
    6. c(2) = 1.25 -0.25 -321/10000*7;
    7. c(3) = -250 / 4000 * 6;
    8. c(4)  = -783/7000*4;
    9. c(5) = -200/4000 * 7;
    10. c(6) = -300/6000*10;
    11. c(7) = -321 / 10000 * 9;
    12. c(8) = 2-0.35-250/4000*8;
    13. c(9) = 2.8-0.5-321/10000*12-783/7000*11;
    14. c = -c;  % 我们求的是最大值，所以这里需要改变符号
    15. % (2) 不等式约束
    16. A = zeros(5,9);
    17. A(1,1) = 5;  A(1,6) = 10;
    18. A(2,2) = 7;  A(2,7) = 9; A(2,9) = 12;
    19. A(3,3) = 6;  A(3,8) = 8;
    20. A(4,4) = 4;  A(4,9) = 11;
    21. A(5,5) = 7;  
    22. b = [6000 10000 4000 7000 4000]';
    23. % (3) 等式约束
    24. Aeq = [1 1 -1 -1 -1 0 0 0 0;
    25.             0 0 0 0 0 1 1 -1 0];
    26. beq = [0 0]';
    27. %（4）上下界
    28. lb = zeros(9,1);
    29.  
    30. % 进行求解
    31. [x fval] = linprog(c, A, b, Aeq, beq, lb)
    32. fval = -fval

    2.3、线性规划问题典型案例2投料问题

    我们看一下下面的投料问题，我们可以使用matlab和lingo去求解线性规划问题，对于这一题而言，lingo求解更为简单。

    如下是matlab求解上述线性规划问题的代码：

    1. %% 投料问题
    2. clear,clc
    3. format long g   %可以将Matlab的计算结果显示为一般的长数字格式（默认会保留四位小数，或使用科学计数法）
    4. % (1) 系数向量
    5. a=[1.25  8.75  0.5  5.75  3  7.25];  % 工地的横坐标
    6. b=[1.25  0.75  4.75	5  6.5  7.25];   % 工地的纵坐标
    7. x = [5  2];  % 料场的横坐标
    8. y = [1  7];  % 料场的纵坐标
    9. c = [];  % 初始化用来保存工地和料场距离的向量 (这个向量就是我们的系数向量）
    10. for  j =1:2
    11.     for i = 1:6
    12.         c = [c;  sqrt( (a(i)-x(j))^2 + (b(i)-y(j))^2)];  % 每循环一次就在c的末尾插入新的元素
    13.     end
    14. end
    15. % (2) 不等式约束
    16. A =zeros(2,12);
    17. A(1,1:6) = 1;
    18. A(2,7:12) = 1;
    19. b = [20,20]';
    20. % (3) 等式约束
    21. Aeq = zeros(6,12);  
    22. for i = 1:6
    23.     Aeq(i,i) = 1;  Aeq(i,i+6) = 1;
    24. end
    25. % Aeq = [eye(6),eye(6)]  % 两个单位矩阵横着拼起来
    26. beq = [3 5 4 7 6 11]';  % 每个工地的日需求量
    27. %（4）上下界
    28. lb = zeros(12,1);
    29.  
    30. % 进行求解
    31. [x fval] = linprog(c, A, b, Aeq, beq, lb)
    32. x = reshape(x,6,2)

    lingo解决上述线性规划问题的代码如下：

    1. model:
    2. sets:
    3. factory /1..6/ : a,b,d ;
    4. plant /1..2/ : x,y ;
    5. coo (factory,plant) : x1 ;
    6. endsets
    7.  
    8. data:
    9. a = 1.25, 8.75, 0.5, 5.75, 3, 7.25 ;
    10. b = 1.25, 0.75, 4.75, 5, 6.5, 7.25 ;
    11. d = 3,5,4,7,6,11 ;
    12. x = 5, 2 ;
    13. y = 1, 7 ;
    14. enddata
    15.  
    16. min = @sum(coo(i,j) : x1(i,j) * @sqrt((a(i)-x(j)) * (a(i)-x(j)) + (b(i) - y(j)) * (b(i) - y(j)))) ;
    17. @for(factory(i) : @sum(plant(j) : x1(i,j)) = d(i)) ;
    18. @for(plant(j) : @sum(factory(i) : x1(i,j)) <= 20) ;
    19. @for(factory(i) : @for(plant(j) : x1(i,j) >= 0)) ;
    20. end

    三、非线性规划类问题

    3.1、非线性规划问题的求解

    我们看一下非线性规划的标准型，aeq和b为线性不等式约束，Aeq和beq是线性等式约束，c是非线性不等式约束，ceq是非线性等式约束。

     我们先看一下matlab求解上面的函数的思路，可以使用fmincon函数进行求解，非线性规划的需要选取一个很好的初始值，因为非线性规划本来求出来的就是一个局部最优解，我们想求一个相对的全局最优解的话，可以通过尝试大量的解，然后找一个最优的，也可以通过蒙特卡洛模拟出初始解，通过初始解计算最优解。option选项是设置求解非线性规划的算法，不同的算法都可以尝试对比一下。

    另外第一个@fun中的fun是目标函数，需要用一个m函数文件来存储，另外的@nonlfun用来表示非线性约束，就是编写一个函数文件来存储非线性约束条件。

    我们看一下上面的的三个例题的matlab代码实现，具体如下,先使用蒙特卡洛方法模拟出一个解，然后以该解作为初始值代入fmincon函数对非线性规划进行求解，第一个例题具体如下：

    1. %% 使用蒙特卡罗的方法来找初始值(推荐）
    2. clc,clear;
    3. n=10000000; %生成的随机数组数
    4. x1=unifrnd(-100,100,n,1);  % 生成在[-100,100]之间均匀分布的随机数组成的n行1列的向量构成x1
    5. x2=unifrnd(-100,100,n,1);  % 生成在[-100,100]之间均匀分布的随机数组成的n行1列的向量构成x2
    6. fmin=+inf; % 初始化函数f的最小值为正无穷（后续只要找到一个比它小的我们就对其更新）
    7. for i=1:n
    8.     x = [x1(i), x2(i)];  %构造x向量, 这里千万别写成了：x =[x1, x2]
    9.     if ((x(1)-1)^2-x(2)<=0)  & (-2*x(1)+3*x(2)-6 <= 0)     % 判断是否满足条件
    10.         result = -x(1)^2-x(2)^2 +x(1)*x(2)+2*x(1)+5*x(2) ;  % 如果满足条件就计算函数值
    11.         if  result  < fmin  % 如果这个函数值小于我们之前计算出来的最小值
    12.             fmin = result;  % 那么就更新这个函数值为新的最小值
    13.             x0 = x;  % 并且将此时的x1 x2更新为初始值
    14.         end
    15.     end
    16. end
    17. disp('蒙特卡罗选取的初始值为：'); disp(x0)
    18. A = [-2 3]; b = 6;
    19. [x,fval] = fmincon(@fun1,x0,A,b,[],[],[],[],@nonlfun1)
    20. fval = -fval

    使用的目标函数fun1和非线性约束函数nonlfun如下：

    1. function f = fun1(x)
    2.     % 注意：这里的f实际上就是目标函数，函数的返回值也是f
    3.     % 输入值x实际上就是决策变量，由x1和x2组成的向量
    4.     % fun1是函数名称，到时候会被fmincon函数调用, 可以任意取名
    5.     % 保存的m文件和函数名称得一致，也要为fun1.m
    6. %      max  f(x) = x1^2 +x2^2 -x1*x2 -2x1 -5x2
    7.     f = -x(1)^2-x(2)^2 +x(1)*x(2)+2*x(1)+5*x(2) ; 
    8. end
    1. function [c,ceq] = nonlfun1(x)
    2.     % 注意：这里的c实际上就是非线性不等式约束，ceq实际上就是非线性等式约束
    3.     % 输入值x实际上就是决策变量，由x1和x2组成的一个向量
    4.     % 返回值有两个，一个是非线性不等式约束c，一个是非线性等式约束ceq
    5.     % nonlfun1是函数名称，到时候会被fmincon函数调用, 可以任意取名，但不能和目标函数fun1重名
    6.     % 保存的m文件和函数名称得一致，也要为nonlfun1.m
    7. %     -(x1-1)^2 +x2 >= 0 
    8.    c = [(x(1)-1)^2-x(2)];   % 千万別写成了: (x1-1)^2 -x2
    9.    ceq = [];  % 不存在非线性等式约束，所以用[]表示
    10. end

    另外使用fmincon求解非线性规划问题可以设置option选项，就是设置求解算法，常见的求解算法有四种，分别如下：

    1. % 使用interior point算法 （内点法）
    2. option = optimoptions('fmincon','Algorithm','interior-point')
    3. [x,fval] = fmincon(@fun1,x0,A,b,[],[],[],[],@nonlfun1,option)  
    4. fval = -fval
    5.  
    6. % 使用SQP算法 （序列二次规划法）
    7. option = optimoptions('fmincon','Algorithm','sqp')
    8. [x,fval] = fmincon(@fun1,x0,A,b,[],[],[],[],@nonlfun1,option)  
    9. fval = -fval  
    10.  
    11. % 使用active set算法 （有效集法）
    12. option = optimoptions('fmincon','Algorithm','active-set')
    13. [x,fval] = fmincon(@fun1,x0,A,b,[],[],[],[],@nonlfun1,option)
    14. fval = -fval  
    15.  
    16. % 使用trust region reflective (信赖域反射算法)
    17. option = optimoptions('fmincon','Algorithm','trust-region-reflective')
    18. [x,fval] = fmincon(@fun1,x0,A,b,[],[],[],[],@nonlfun1,option)  
    19. fval = -fval

    第二个非线性规划的例题求解过程如下，先使用蒙特卡洛模拟出一个解作为初始值，然后将初始值代入fmincon函数进行求解，得出结果。

    1. %% 使用蒙特卡罗的方法来找初始值(推荐）
    2. clc,clear;
    3. n=1000000; %生成的随机数组数
    4. x1= unifrnd(0,2,n,1);   % 生成在[0,2]之间均匀分布的随机数组成的n行1列的向量构成x1
    5. x2 = sqrt(2-x1);  % 根据非线性等式约束用x1计算出x2
    6. x3 = sqrt((3-x2)/2); % 根据非线性等式约束用x2计算出x3
    7. fmin=+inf; % 初始化函数f的最小值为正无穷（后续只要找到一个比它小的我们就对其更新）
    8. for i=1:n
    9.     x = [x1(i), x2(i), x3(i)];  %构造x向量, 这里千万别写成了：x =[x1, x2, x3]
    10.     if (-x(1)^2+x(2)-x(3)^2<=0) & (x(1)+x(2)^2+x(3)^2-20<=0)   % 判断是否满足条件
    11.         result =sum(x.*x) + 8 ;  % 如果满足条件就计算函数值
    12.         if  result  < fmin  % 如果这个函数值小于我们之前计算出来的最小值
    13.             fmin = result;  % 那么就更新这个函数值为新的最小值
    14.             x0 = x;  % 并且将此时的x1 x2 x3更新为初始值
    15.         end
    16.     end
    17. end
    18. disp('蒙特卡罗选取的初始值为：'); disp(x0)
    19. lb = [0 0 0];  % 决策变量的下界
    20. [x,fval] = fmincon(@fun2,x0,[],[],[],[],lb,[],@nonlfun2)  % 注意 fun2.m文件和nonfun2.m文件都必须在当前文件夹目录下

    下面是上述第2个非线性规划的目标函数和非线性约束函数，如下：

    1. function f = fun2(x)
    2.     %     f = x(1)^2+x(2)^2 +x(3)^2+8 ; 
    3.     f = sum(x.*x) + 8;  % 可别忘了x实际上是一个向量，我们可以使用矩阵的运算符号对其计算
    4. end
    1. function [c,ceq] = nonlfun2(x)
    2.     % 非线性不等式约束
    3.     c = [-x(1)^2+x(2)-x(3)^2;   % 一定要注意写法的规范，再次强调这里的x是一个向量！不能把x(1)写成x1
    4.             x(1)+x(2)^2+x(3)^2-20];
    5.     % 非线性等式约束
    6.     ceq = [-x(1)-x(2)^2+2;
    7.                 x(2)+2*x(3)^2-3]; 
    8. end

    第三个非线性规划的例题求解过程如下，先使用蒙特卡洛模拟出一个解，用该解作为初始值代入fmincon函数中求解该非线性规划的解。代码如下：

    1. clear;clc
    2. n=10000000; %生成的随机数组数
    3. x1=unifrnd(20,30,n,1);  % 生成在[20,30]之间均匀分布的随机数组成的n行1列的向量构成x1
    4. x2=x1 - 10;
    5. x3=unifrnd(-10,16,n,1);  % 生成在[-10,16]之间均匀分布的随机数组成的n行1列的向量构成x3
    6. fmax=-inf; % 初始化函数f的最大值为负无穷（后续只要找到一个比它大的我们就对其更新）
    7. for i=1:n
    8.     x = [x1(i), x2(i), x3(i)];  %构造x向量, 这里千万别写成了：x =[x1, x2, x3]
    9.     if (-x(1)+2*x(2)+2*x(3)>=0)  &  (x(1)+2*x(2)+2*x(3)<=72)     % 判断是否满足条件
    10.         result = x(1)*x(2)*x(3);  % 如果满足条件就计算函数值
    11.         if  result  > fmax  % 如果这个函数值大于我们之前计算出来的最大值
    12.             fmax = result;  % 那么就更新这个函数值为新的最大值
    13.             X = x;  % 并且将此时的x1 x2 x3保存到一个变量中
    14.         end
    15.     end
    16. end
    17. disp(strcat('蒙特卡罗模拟得到的最大值为',num2str(fmax)))
    18. disp('最大值处x1 x2 x3的取值为：')
    19. disp(X)
    20. % 蒙特卡罗模拟得到的最大值为3445.6014
    21. % 最大值处x1 x2 x3的取值为：
    22. %           22.5823101903968          12.5823101903968          12.1265223966757
    23. A = [1 -2 -2;  1 2 2];  b = [0 72];
    24. x0 = [ 22.58   12.58  12.13];
    25. Aeq = [1 -1 0]; beq = 10;
    26. lb = [-inf 10 -inf];  ub = [inf 20 inf];  
    27. [x,fval] = fmincon(@fun3,x0,A,b,Aeq,beq,lb,ub,[])  % 注意没有非线性约束，所以这里可以用[]替代，或者干脆不写
    28. fval = -fval

    使用到的目标函数代码如下，由于没有非线性约束，所以不用写非线性函数。

    1. function f = fun3(x)
    2.     f = -prod(x);  % 可别忘了x实际上是一个向量（prod表示连乘符号，用法和sum类似）
    3. end

    3.2、非线性规划典型例题选址问题

    我们看一下这个题目的第二问，关于选址问题的，就是现在的临时料场不要了，新建两个料场，使得总的吨千米数最少，由于新料场的位置未知，那么这个题目就变成了一个非线性规划的问题了。决策变量由原来的12个变成了16个。

     下面看一下matlab求解上述非线性规划问题的代码如下：

    1. %% 选址问题
    2. clear;clc
    3. format long g   %可以将Matlab的计算结果显示为一般的长数字格式（默认会保留四位小数，或使用科学计数法）
    4. A =zeros(2,16);  % 注意这里要改成16
    5. A(1,1:6) = 1;
    6. A(2,7:12) = 1;
    7. b = [20,20]';
    8. % (3) 等式约束
    9. Aeq = zeros(6,16);  % 注意这里要改成16
    10. for i = 1:6
    11.     Aeq(i,i) = 1;  Aeq(i,i+6) = 1;
    12. end
    13. beq = [3 5 4 7 6 11]';  % 每个工地的日需求量
    14. %（4）上下界
    15. lb = zeros(16,1);
    16. % lb = [zeros(12,1); -inf*ones(4,1)];  两个新料场坐标的下界可以设为-inf
    17.  
    18. % 进行求解
    19. % 注意哦，这里我们只尝试了这一个初始值，大家可以试试其他的初始值，有可能能够找到更好的解。
    20. % 未来我会在遗传算法中再来看这个例题。
    21. x0 = [3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7];  % 用第一问的结果作为初始值
    22. [x,fval] = fmincon(@fun5,x0,A,b,Aeq,beq,lb)  % 注意没有非线性约束，所以这里可以用[]替代，或者干脆不写
    23. reshape(x(1:12),6,2) 
    1. function f = fun5(xx)  % 注意为了避免和下面的x同号，我们把决策变量的向量符号用xx表示（注意xx的长度为16）
    2.     a=[1.25  8.75  0.5  5.75  3  7.25];  % 工地的横坐标
    3.     b=[1.25  0.75  4.75	5  6.5  7.25];   % 工地的纵坐标
    4.     x = [xx(13)  xx(15)];  % 新料场的横坐标
    5.     y = [xx(14)  xx(16)];  % 新料场的纵坐标
    6.     c = [];  % 初始化用来保存工地和料场距离的向量 (这个向量就是我们的系数向量）
    7.     for  j =1:2
    8.         for i = 1:6
    9.             c = [c;  sqrt( (a(i)-x(j))^2 + (b(i)-y(j))^2)];  % 每循环一次就在c的末尾插入新的元素
    10.         end
    11.     end
    12.     % 下面我们要求吨千米数，注意c是列向量，我们计算非线性规划时给定的初始值x0是行向量
    13.     f = xx(1:12) * c;
    14. end

    lingo求解上述非线性规划问题的代码如下：

    1. model:
    2. sets:
    3. factory /1..6/ : a,b,d ;
    4. plant /1..2/ : x,y ;
    5. coo (factory,plant) : x1 ;
    6. endsets
    7.  
    8. data:
    9. a = 1.25, 8.75, 0.5, 5.75, 3, 7.25 ;
    10. b = 1.25, 0.75, 4.75, 5, 6.5, 7.25 ;
    11. d = 3,5,4,7,6,11 ;
    12. enddata
    13.  
    14. min = @sum(coo(i,j) : x1(i,j) * @sqrt((a(i)-x(j))* (a(i)-x(j))  + (b(i) - y(j)) * (b(i) - y(j)))) ;
    15. @for(factory(i) : @sum(plant(j) : x1(i,j)) = d(i)) ;
    16. @for(plant(j) : @sum(factory(i) : x1(i,j)) <= 20) ;
    17. @for(factory(i) : @for(plant(j) : x1(i,j) >= 0)) ;
    18. end

    四、整数规划类问题

    4.1、整数规划类问题求解

    整数规划问题分为线性整数规划和非线性整数规划问题，我们主要还是考虑线性整数规划，非线性的一般不使用matlab自带的函数求解，一般用蒙特卡洛模拟或者启发式算法求解。

    在matlab中求解线性整数规划问题，一般使用intlinprog函数求解，intcon指定决策变量为整数。

    我们可以看一下下面的三个简单的例子，intlinprog的用法和linprog的用法很相似，主要是加上了一个整数约束intcon。

    4.2、 整数规划典型例题1之背包问题

    我们看一下这个背包问题，就是典型的0-1整数规划问题，目标函数总利润最大，约束条件总重量不超过30.

    求解上面整数规划的matlab代码如下：

    1. %% 背包问题（货车运送货物的问题）
    2. c = -[540 200 180 350 60 150 280 450 320 120];  % 目标函数的系数矩阵(最大化问题记得加负号)
    3. intcon=[1:10];  % 整数变量的位置(一共10个决策变量，均为0-1整数变量)
    4. A = [6 3 4 5 1 2 3 5 4 2];  b = 30;   % 线性不等式约束的系数矩阵和常数项向量（物品的重量不能超过30）
    5. Aeq = []; beq =[];  % 不存在线性等式约束
    6. lb = zeros(10,1);  % 约束变量的范围下限
    7. ub = ones(10,1);  % 约束变量的范围上限
    8. %最后调用intlinprog()函数
    9. [x,fval]=intlinprog(c,intcon,A,b,Aeq,beq,lb,ub)
    10. fval = -fval

    求解上面整数规划的lingo代码如下：

    1. model:
    2. sets:
    3. factory /1..10/ : x,p,t ;
    4.  
    5. endsets
    6.  
    7. data:
    8. t = 6,3,4,5,1,2,3,5,4,2;
    9. p = 540, 200, 180, 350, 60, 150, 280, 450, 320, 120;
    10. enddata
    11. max = @sum(factory(i) : (p(i) * x(i)));
    12. @sum(factory(i) : t(i)*x(i)) <= 30 ;
    13. @for(factory(i) : @bin(x(i))) ;
    14.  
    15. end

    4.3、 整数规划典型例题2之指派问题

    我们看一下这个指派问题，就是指派队员i参加j种游泳比赛，使得成绩最好，即用时最短，目标函数是用时最小，约束条件是最多只能参加一个比赛，每种比赛有且只有一人参加。参加表示为1，不参加表示为0.

     上述的整数规划问题求解的lingo代码如下：

    1. model:
    2. sets:
    3. factory /1..5/  ;
    4. plant /1..4/ ;
    5. coo (factory,plant) : t,x ;
    6. endsets
    7. data:
    8. t = 66.8 75.6 87 58.6
    9.     57.2 66 66.4 53
    10.     78 67.8 84.6 59.4
    11.     70 74.2 69.6 57.2
    12.     67.4 71 83.8 62.4 ;
    13. enddata
    14. min = @sum(coo(i,j) : (t(i,j) * x(i,j))) ;
    15. @for(factory(i) : @sum(plant(j) : x(i,j)) <= 1) ; 
    16. @for(plant(j) : @sum(factory(i) : x(i,j)) = 1) ;
    17. @for(factory(i) : @for(plant(j) : @bin(x(i,j))));
    18.  
    19. end

    4.4、整数规划典型例题3之钢管切割问题

    我们看一下下面的钢管切割问题，使得切割使用的原材料最少，具体如下。

     

    求解上述整数规划问题的matlab代码如下：

    1. %% 钢管切割问题
    2. %% (1)枚举法找出同一个原材料上所有的切割方法
    3. for i = 0: 2  % 2.9m长的圆钢的数量
    4.     for j = 0: 3  % 2.1m长的圆钢的数量
    5.         for k = 0:6   % 1m长的圆钢的数量
    6.             if 2.9*i+2.1*j+1*k >= 6 && 2.9*i+2.1*j+1*k <= 6.9
    7.                 disp([i, j, k])
    8.             end
    9.         end
    10.     end
    11. end
    12. % 有同学使用比较老的MATLAB版本，会出现浮点数计算的误差
    13. % 只需要将上面的if这一行进行适当的放缩即可。
    14. % if 2.9*i+2.1*j+1*k >= 6-0.0000001 && 2.9*i+2.1*j+1*k <= 6.9+0.0000001
    15. % 有兴趣的同学可以百度下：浮点数计算误差
    16.  
    17. %% (2) 线性整数规划问题的求解
    18. c = ones(7,1);  % 目标函数的系数矩阵
    19. intcon=[1:7];  %  整数变量的位置(一共7个决策变量，均为整数变量)
    20. A = -[1 2 0 0 0 0 1;  
    21.          0 0 3 2 1 0 1;
    22.          4 1 0 2 4 6 1];  % 线性不等式约束的系数矩阵
    23. b = -[100 100 100]'; %  线性不等式约束的常数项向量
    24. lb = zeros(7,1); % 约束变量的范围下限
    25. [x,fval]=intlinprog(c,intcon,A,b,[],[],lb)

    五、最大最小化模型

    5.1、最大最小化模型的一般形式

    我们看一下最大最小化模型的一般形式，除了目标函数之外，其余的和常规的规划问题没啥区别。

    5.2、最大最小化问题经典例题

    我们看一下这个选址问题，其实就是选择一个位置，距离其余位置的总和最小，或者说，距离其它位置的最大值最小。

     求解上述最大最小化模型的matlab代码如下：

    1. %% 最大最小化模型  :   min{max[f1,f2,···,fm]}
    2. x0 = [6, 6];      % 给定初始值
    3. lb = [3, 4];  % 决策变量的下界
    4. ub = [8, 10];  % 决策变量的上界
    5. [x,feval] = fminimax(@fun,x0,[],[],[],[],lb,ub)
    6. max(feval)
    1. function f = fun(x)
    2.     a=[1 4 3 5 9 12 6 20 17 8];
    3.     b=[2 10 8 18 1 4 5 10 8 9];
    4.     %  函数向量
    5.     f=zeros(10,1);
    6.     for i = 1:10
    7.         f(i) = abs(x(1)-a(i))+abs(x(2)-b(i));  
    8.     end
    9. % f(1) = abs(x(1)-a(1))+abs(x(2)-b(1));  
    10. % f(2) = abs(x(1)-a(2))+abs(x(2)-b(2));
    11. % f(3) = abs(x(1)-a(3))+abs(x(2)-b(3));
    12. % f(4) = abs(x(1)-a(4))+abs(x(2)-b(4));
    13. % f(5) = abs(x(1)-a(5))+abs(x(2)-b(5));
    14. % f(6) = abs(x(1)-a(6))+abs(x(2)-b(6));
    15. % f(7) = abs(x(1)-a(7))+abs(x(2)-b(7));
    16. % f(8) = abs(x(1)-a(8))+abs(x(2)-b(8));
    17. % f(9) = abs(x(1)-a(9))+abs(x(2)-b(9));
    18. % f(10) = abs(x(1)-a(10))+abs(x(2)-b(10));
    19. end

    lingo求解上述最大最小化问题的代码如下：

    1. model:
    2. sets:
    3. factory /1..10/ : a, b;
    4. endsets
    5. data:
    6. a = 1 4 3 5 9 12 6 20 17 8 ;
    7. b = 2 10 8 18 1 4 5 10 8 9 ;
    8. enddata
    9. min = @sum(factory(i):(@abs(x-a(i)) + @abs(y-b(i))));
    10. x>=3;
    11. x<=8;
    12. y>=4;
    13. y<=10;
    14. end

    六、多目标规划问题

    6.1、多目标规划处理方法

    多目标规划就是有多个目标函数，我们对多目标规划的解决方法是加权组合转换成单目标规划问题求解，但是需要注意一些事项：比如统一转换成最大化或最小化问题还有就是如果有量纲问题，需要进行消除量纲后 再加权处理。

    6.2、多目标规划经典案例

    我们可以看一下这个例题，当然这个例题很简单，直接加权转换成一个线性规划问题，然后求解即可，我们可以考虑改变两个目标函数的权重，然后进行灵敏度分析，这个在建模中也是加分项。

    求解上述多目标规划的matlab代码如下：

    1. %%  多目标规划问题
    2. clc;
    3. clear;
    4. w1 = 0.4;  w2 = 0.6;  % 两个目标函数的权重  x1 = 5  x2 = 2
    5. %w1 = 0.5;  w2 = 0.5;  % 两个目标函数的权重  x1 = 5  x2 = 2
    6. %w1 = 0.3;  w2 = 0.7;  % 两个目标函数的权重  x1 = 1  x2 = 6
    7. c = [w1/30*2+w2/2*0.4 ;w1/30*5+w2/2*0.3];  % 线性规划目标函数的系数
    8. A = [-1 -1];  b = -7; % 不等式约束
    9. lb = [0 0]'; ub = [5 6]'; % 上下界
    10. [x,fval] = linprog(c,A,b,[],[],lb,ub)
    11. f1 = 2*x(1)+5*x(2)
    12. f2 = 0.4*x(1) + 0.3*x(2)

    通过改变权重进行敏感度分析的模拟，具体的代码如下：

    1. %% 敏感性分析
    2. clear;clc
    3. W1 = 0.1:0.001:0.5;  W2 = 1- W1;  
    4. n =length(W1);
    5. F1 = zeros(n,1);  F2 = zeros(n,1);   X1 = zeros(n,1);  X2 = zeros(n,1);   FVAL = zeros(n,1);
    6. A = [-1 -1];  b = -7; % 不等式约束
    7. lb = [0 0]; ub = [5 6]; % 上下界
    8. for i = 1:n
    9.     w1 = W1(i);  w2 = W2(i);
    10.     c = [w1/30*2+w2/2*0.4 ;w1/30*5+w2/2*0.3];  % 线性规划目标函数的系数
    11.     [x,fval] = linprog(c,A,b,[],[],lb,ub);
    12.     F1(i) = 2*x(1)+5*x(2);
    13.     F2(i) = 0.4*x(1) + 0.3*x(2);
    14.     X1(i) = x(1);
    15.     X2(i) = x(2);
    16.     FVAL(i) = fval;
    17. end
    18.  
    19. % 「Matlab」“LaTex字符汇总”讲解：https://blog.csdn.net/Robot_Starscream/article/details/89386748
    20. % 在图上可以加上数据游标，按住Alt加鼠标左键可以设置多个数据游标出来。
    21. figure(1) 
    22. plot(W1,F1,W1,F2)
    23. xlabel('f_{1}的权重') 
    24. ylabel('f_{1}和f_{2}的取值')
    25. legend('f_{1}','f_{2}')
    26.  
    27. figure(2)
    28. plot(W1,X1,W1,X2)
    29. xlabel('f_{1}的权重') 
    30. ylabel('x_{1}和x_{2}的取值')
    31. legend('x_{1}','x_{2}')
    32.  
    33. figure(3)
    34. plot(W1,FVAL)  % 看起来是两个直线组合起来的下半部分
    35. xlabel('f_{1}的权重') 
    36. ylabel('综合指标的值')

    我们可以看一下敏感度分析的结果，具体如下，通过改变权重，目标函数f1的权重转折点，f1权重越小，说明生成A越大，对污染就越大，那么厂家更倾向于生成B类的。

  • 相关阅读:
    ACM模式各种输入整理（C++）
    每天几道Java面试题：集合（第四天）
    新变化新营销 这些知识点你得 Get！（文末有 PPT 福利首次放送）
    Sonar Java默认的扫描规则
    10分钟教对象搭建了一个多人聊天室~
    C语言之字符函数&字符串函数篇（2）
    nginx配置IP白名单
    转运RNA（tRNA）甲基化修饰7-甲基胞嘧啶(m7C)|tRNA-m7G
    10.Tomcat,Servlet
    线性表的单链表
  • 原文地址：https://blog.csdn.net/nuist_NJUPT/article/details/126845520