目录
文章目录
前言
一、整数规划
分类:
二、典例讲解
1.背包问题
2.指派问题
总结
前言
如果觉得本篇文章还不错的话,给作者点个赞鼓励一下吧😁😁😁
在规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常要求某些变量(全部或部分)的解必须是整数。例如当我们的变量时人数或者机器的台数。此时我们就需要利用整数规划来求最优解。
一、整数规划
分类:
- 🌏线性整数规划:我们只需要在线性规划的基础上,加入决策变量取整数的条件
此时我们使用matlab中的intlinprog函数,其中intcon中的值指示决策变量 x 中应取整数值的分量,其他都与线性规划的变量含义相同。如假如有x1,x2,x3三个整数变量则令intcon=[1,2,3]/[1:3]
- 🌏非线性整数规划:无特定算法,只能用近似算法 ,如蒙特卡罗模拟,智能算法
- 🌏0—1规划:仍然使用intlinprog函数求解,只需要限定lb和ub即可
如:假如有三个决策变量,其中x2,x3为0-1变量,而x1不限制,则 lb=[-inf(负无穷),0,0],ub=[+inf,1,1],每个决策变量的范围按照顺序一一对应
二、典例讲解
1.背包问题
通过读题我们很容易达到这是一个优化类题目,并且需要用到0-1整数规划,因为货物的运送只有运送(0)和不运送(1)两种情况,那么我们写出相应的目标函数和约束条件
这里我们可以设第i件物品为xi,其重量为wi,取得的利润为pi
则总利润:
约束条件:根据题干中所给条件写出
特别注意:运用intlinprog函数仍然要符合函数的使用形式,要把最大值的求解变成min,大于等于变成<=
然后我们只需要将根据上述所列设相应的变量并且带入函数即可
%背包问题
clear,clc
f = -[540,200,180,350,60,150,280,450,320,120];%特别注意要转换成求最小值
intcon= 1:10;%xi都是整数
A = [6,3,4,5,1,2,3,5,4,2];
b = 30;
lb=zeros(10,1);%约束变量的下届
ub=ones(10,1);%约束变量的上界
[x,favl] = intlinprog(f,intcon,A,b,[],[],lb,ub);%这里没有等式约束则Aeq,beq为[][]
W = -favl;%计算出最大利润
disp('选择运输的结果为:');disp(x);
disp('最大利润为:');disp(W);
2.指派问题
指派问题通常是将i人分配到j地,再对相应问题求解
注意: 当下标有两个变量时,我们需要将这些变量按照顺序排列起来,要从1开始重新给他们排列得到决策变量的相应下标,其他做法均与线性规划问题相同
%指派问题
%注意这里要把双指标转换成单指标,x11->x1,x12->2···x21-x5···,x54->x20
%目标函数的系数矩阵
f=[66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6,57.2,67.4,71,83.8,62.4];intcon=1:20;
%不等式约束的系数矩阵和常数项矩阵
A =[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1];
b=ones(5,1);
%等式约束
Aeq = repmat(eye(4),1,5);
beq = ones(4,1);
lb = zeros(20,1);
ub = ones(20,1);
%最后调用函数即可
[x,favl]=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);
disp('安排方式为');disp(x);
disp('最短的时间为');disp(favl);
x = reshape(x,4,5);%reshape函数会将原始向量中的数据将按照列的顺序填充到新的矩阵
disp(x');
总结
完结撒花🎇🎆🎇🎆
背包问题和指派问题是运用0-1规划的常见两种情况,需要掌握还有其他一些情况大家可自行查找资料学习