【整数规划】+【0—1规划】解决优化类问题（Matlab代码）

目录

文章目录

前言

一、整数规划

分类：

二、典例讲解

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规划的常见两种情况，需要掌握还有其他一些情况大家可自行查找资料学习