【学习笔记】Matlab和python双语言的学习(整数规划和0-1规划)
文章目录
- 前言
- 一、整数规划和0-1规划
- 二、典型示例
- 1.背包问题
- 2.指派问题
- 三、代码实现----Matlab
- 1.Matlab 的 `intlinprog` 函数
- 2.Matlab 代码
- 背包问题
- 指派问题
- 四、代码实现----python
- 背包问题
- 指派问题
- 总结
前言
通过模型算法,熟练对Matlab和python的应用。
学习视频链接:
https://www.bilibili.com/video/BV1EK41187QF?p=26&vd_source=67471d3a1b4f517b7a7964093e62f7e6
一、整数规划和0-1规划
- 在规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常要求某些变量(全部或部分)的解必须是整数。例如,当变量代表的是机器的台数,工作的人数或装货的车数等。为了满足整数的要求,初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解,所以应该有特殊的方法来求解整数规划。在整数规划中,如果所有变量都限制为整数,则称为纯整数规划;如果仅一部分变量限制为整数,则称为混合整数规划。整数规划的一种特殊情形是0-1规划,它的变数仅限于0或1。
- 本文讨论的整数规划和0-1规划都在线性规划的范畴
二、典型示例
1.背包问题
-
有10件货物要从甲地运送到乙地,每件货物的重量(单位: 吨)和利润(单位: 元)如下表所示
-
由于只有一辆最大载重为30t的货车能用来运送货物,所以只能选择部分货物进行运送。
-
要求确定运送哪些货物,使得运送这些货物的总利润最大。
记 x i = { 1 , 运送了第 i 件货物 0 , 没有运送第 i 件货物 , i = 1 , 2 , … , 10 \left.\text{记}\quad x_{i}=\begin{cases}1,\text{运送了第}i\text{件货物}\\0,\text{没有运送第}i\text{件货物}\end{cases}\right.,i=1,2,\ldots,10 记xi={1,运送了第i件货物0,没有运送第i件货物,i=1,2,…,10
记 w i w_i wi 表示第 i 件物品的重量, p i p_i pi 表示第 i 件物品的利润
模型建立:
m a x ∑ i = 1 10 p i x i s . t . { ∑ i = 1 10 w i x i ≤ 30 x i ∈ { 0 , 1 } \begin{aligned}max\sum_{i=1}^{10}p_ix_i\end{aligned}\\s.t.\begin{cases}\sum_{i=1}^{10}w_ix_i\leq30\\x_i\in\{0,1\}\end{cases} maxi=1∑10pixis.t.{∑i=110wixi≤30xi∈{0,1}
2.指派问题
-
已知5名游泳候选人的百米成绩,怎么选拔队员组成 4×100 米混合泳接力队伍
(表中的数据是各运动员百米游泳的耗时) -
候选人: i = 1 , 2 , 3 , 4 , 5 i = 1,2,3,4,5 i=1,2,3,4,5
-
泳姿: j = 1 , 2 , 3 , 4 j = 1,2,3,4 j=1,2,3,4
-
x i j = { 1 , 队员 i 参加第 j 种泳姿 0 , 队员 i 不参加第 j 种泳姿 x_{ij}=\begin{cases}&1 ,\text{队员} i\text{参加第}j\text{种泳姿}\\&0 ,\text{队员} i\text{不参加第}j\text{种泳姿}\end{cases} xij={1,队员i参加第j种泳姿0,队员i不参加第j种泳姿
-
t i j t_{ij} tij:队员 i 参加第 j 种泳姿的耗时
模型建立:
m i n ∑ j = 1 4 ∑ i = 1 5 t i j x i j s . I . { ∑ j = 1 4 x i j ≤ 1 , i = 1 , 2 , 3 , 4 , 5 (每个人只能入选4种泳姿之一) ∑ i = 1 5 x i j = 1 , 2 , 3 , 4 (每种泳姿有且仅有1人参加) x i j ∈ { 0 , 1 } \begin{aligned}min\quad\sum_{j=1}^{4}\sum_{i=1}^{5}t_{ij}x_{ij}\end{aligned}\\[1em]\\s.I.\begin{cases}\sum_{j=1}^{4}x_{ij}\leq1,i=1,2,3,4,5&\text{(每个人只能入选4种泳姿之一)}\\[0em]\\\sum_{i=1}^{5}x_{ij}=1,2,3,4&\text{(每种泳姿有且仅有1人参加)}\\[0em]\\x_{ij}\in\{0,1\}\end{cases} minj=1∑4i=1∑5tijxijs.I.⎩ ⎨ ⎧∑j=14xij≤1,i=1,2,3,4,5∑i=15xij=1,2,3,4xij∈{0,1}(每个人只能入选4种泳姿之一)(每种泳姿有且仅有1人参加)
三、代码实现----Matlab
1.Matlab 的 intlinprog
函数
intlinprog
是 MATLAB 中用于求解混合整数线性规划(MILP)问题的函数。混合整数线性规划问题是指在线性约束条件下,求解线性目标函数的最优解,其中部分或全部决策变量被限制为整数。
线性整数规划
intlinprog
函数的基本语法如下:
[x, fval] = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub, options)
各参数的含义如下:
f
:目标函数的系数向量。intcon
:一个向量,指定哪些决策变量是整数变量。例如,如果intcon = [1, 3]
,则表示第一个和第三个决策变量是整数变量。A
:不等式约束矩阵。b
:不等式约束向量。Aeq
:等式约束矩阵。beq
:等式约束向量。lb
:决策变量的下界。ub
:决策变量的上界。options
:一个结构体,包含求解器的选项。
返回值的含义如下:
x
:最优解。fval
:目标函数在最优解处的值。
线性0-1规划
- 仍然使用
intlinprog
函数求解,只需要限定lb
和ub
即可 - 例如: 三个决策变量: x1,x2,x3, x1 和 x3 是0-1变量,x2 不限制,则
intcon=[1,3]
,lb=[0;-inf;0]
,ub =[1;+inf;1]
2.Matlab 代码
背包问题
%% 背包问题% 线性整数规划
% [x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0)
% f :目标函数的系数向量(最小值形式下)
% intcon :intcon中的值指示决策变量x中应取整数值的分量
% A,b :不等式约束条件的变量系数矩阵和常数项矩阵(必须是≤形式)
% Aeq,beq :等式约束条件的系数矩阵和常数项矩阵
% lb,ub :决策变量的最小取值和最大取值
% intcon 的用法:决策变量如果有三个:x1,x2,x3;若x1和x3是整数,则intcon = [1,3]% 线性0-1规划
% 仍然使用intlinprog函数求解,只需限定lb和ub即可
% 决策变量如果有三个:x1,x2,x3;若x1和x3是0-1变量,x2不限制,则intcon = [1,3],lb = [0;-inf;0],ub = [1;+inf;1]
clc;clear
f = [-540 -200 -180 -350 -60 -150 -280 -450 -320 -120];
A = [6 3 4 5 1 2 3 5 4 2];
b = 30;
intcon = [1:10];
lb = zeros(10,1);
ub = ones(10,1);
[x,fval] = intlinprog(f,intcon,A,b,[],[],lb,ub)
res = -fval
运行结果:
即:运送1、2、4、6、7、8、9、10货物,运送这些货物的总利润最大为 2410 元
指派问题
%% 指派问题% 线性整数规划
% [x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0)
% f :目标函数的系数向量(最小值形式下)
% intcon :intcon中的值指示决策变量x中应取整数值的分量
% A,b :不等式约束条件的变量系数矩阵和常数项矩阵(必须是≤形式)
% Aeq,beq :等式约束条件的系数矩阵和常数项矩阵
% lb,ub :决策变量的最小取值和最大取值
% intcon 的用法:决策变量如果有三个:x1,x2,x3;若x1和x3是整数,则intcon = [1,3]% 线性0-1规划
% 仍然使用intlinprog函数求解,只需限定lb和ub即可
% 决策变量如果有三个:x1,x2,x3;若x1和x3是0-1变量,x2不限制,则intcon = [1,3],lb = [0;-inf;0],ub = [1;+inf;1]clc;clear
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];
A = zeros(5,20);
for i = 1:5A(i,4*i-3:4*i) = 1;
end
b = ones(5,1);
Aeq = [eye(4), eye(4), eye(4), eye(4), eye(4)];
beq = ones(4,1);
intcon = [1:20];
lb = zeros(20,1);
ub = ones(20,1);
[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
reshape(x,4,5)'
运行结果:
即:甲自由泳;乙蝶泳;丙仰泳;丁蛙泳;戊不参加
四、代码实现----python
在Python中,虽然没有直接对应于MATLAB中intlinprog
函数的内置函数,但可以使用以下第三方库来解决混合整数线性规划(MILP)问题,这些库提供了类似的功能:
- PuLP
- ORTools
- Gurobi
- CVXPY
本文选用 PuLP 库求解
背包问题
# 背包问题
import pulp
import numpy as np# 定义问题规模
# 变量数
n_variables = 10
# 限制条件数
n_constraints = 1# 创建问题实例
prob = pulp.LpProblem("BinaryVectorLP", pulp.LpMaximize)# 创建0-1变量(向量)
x = [pulp.LpVariable(f'x{i}', cat='Binary') for i in range(n_variables)]# 定义目标函数向量
c = np.array([540, 200, 180, 350, 60, 150, 280, 450, 320, 120]) # 目标函数系数# 定义约束矩阵和向量
A = np.array([6, 3, 4, 5, 1, 2, 3, 5, 4, 2]) # 约束矩阵
b = np.array([30]) # 约束向量# 设置目标函数
prob += pulp.lpSum([c[i] * x[i] for i in range(n_variables)]), "Objective"# 添加约束条件
prob += (pulp.lpSum([A[j] * x[j] for j in range(n_variables)]) <= b[0]), f"Constraint_{0+1}"# 求解
prob.solve()# 输出结果
print("Status:", pulp.LpStatus[prob.status])
for i in range(n_variables):print(f"x{i} =", pulp.value(x[i]))
print("Objective =", pulp.value(prob.objective))
运行结果:
指派问题
# 指派问题import pulp
import numpy as np# 定义问题规模
# 变量数
n_variables = 20
# 限制条件数
n_constraints_1 = 5
n_constraints_2 = 4# 创建问题实例
prob = pulp.LpProblem("BinaryVectorLP", pulp.LpMinimize)# 创建0-1变量(向量)
x = [pulp.LpVariable(f'x{i}', cat='Binary') for i in range(n_variables)]# 定义目标函数向量
c = np.array([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])# 定义约束矩阵和向量
A_1 = np.zeros((5,20))
for i in range(1,6):A_1[i-1,4*i-4:4*i] = 1 # 约束矩阵
b_1 = np.ones((5,)) # 约束向量# 定义约束矩阵和向量
A_2 = np.hstack([np.eye(4), np.eye(4), np.eye(4), np.eye(4), np.eye(4)])# 约束矩阵
b_2 = np.ones((4,)) # 约束向量# 设置目标函数
prob += pulp.lpSum([c[i] * x[i] for i in range(n_variables)]), "Objective"# 添加约束条件
for i in range(n_constraints_1):prob += (pulp.lpSum([A_1[i, j] * x[j] for j in range(n_variables)]) <= b_1[i]), f"Constraint_{i+1}"for i in range(n_constraints_2):prob += (pulp.lpSum([A_2[i, j] * x[j] for j in range(n_variables)]) == b_2[i]), f"Constraint_{i+6}"# 求解
prob.solve()# 输出结果
res = np.zeros((20,1))
print("Status:", pulp.LpStatus[prob.status])
for i in range(n_variables):res[i] = pulp.value(x[i])print(f"x{i} =", pulp.value(x[i]))
print("Objective =", pulp.value(prob.objective))
res = res.reshape((5,4))
print(res)
运行结果:
总结
本文介绍了整数规划和0-1规划,并通过背包问题和指派问题两个典型示例建立模型,分别使用Matlab和python进行代码编写。
相关文章:

【学习笔记】Matlab和python双语言的学习(整数规划和0-1规划)
文章目录 前言一、整数规划和0-1规划二、典型示例1.背包问题2.指派问题 三、代码实现----Matlab1.Matlab 的 intlinprog 函数2.Matlab 代码背包问题指派问题 四、代码实现----python背包问题指派问题 总结 前言 通过模型算法,熟练对Matlab和python的应用。 学习视频…...

【连续4届EI检索,SPIE 出版】第五届信号处理与计算机科学国际学术会议(SPCS 2024,8月23-25)
第五届信号处理与计算机科学国际学术会议(SPCS 2024) 将于2024年8月23-25日在中国哈尔滨举行。会议主要围绕信号处理与计算机科学等研究领域展开讨论。 会议旨在为从事信号处理与计算机科学研究的专家学者、工程技术人员、技术研发人员提供一个共享科研成果和前沿技…...
Vue屏蔽Console.Log打印信息
Vue屏蔽打印信息 安装 npm install uglifyjs-webpack-plugin --save-dev 在vue.config.js文件或者webpack.prod.conf.js中配置 vue.config中 const UglifyJsPlugin require(uglifyjs-webpack-plugin) // 屏蔽打印数据 module.exports {optimization: {minimizer: [new Ugl…...

数据结构之《二叉树》(下)
在二叉树(中)了解了堆的相关概念后还实现了堆,并且还实现了堆排序,以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构,会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树,接下来就开始本篇的学习吧&…...
用Python打造精彩动画与视频,9.3 项目案例分享与反思
第九章:综合项目 9.3 项目案例分享与反思 在本节中,我们将分享几个成功的项目案例,并进行反思总结。这些案例将展示如何将前面所学的Python技术运用于实际项目中,同时我们将讨论项目中的挑战和解决方案,以及从中得到…...

分布式主键 详解
文章目录 雪花算法结合分库分表的问题问题出现原因分析解决思路 分布式主键要考虑的问题主键生成策略雪花算法详解时间戳位问题工作进程位问题序列号位问题根据雪花算法扩展基因分片法 雪花算法结合分库分表的问题 问题出现 使用ShardingSphere框架自带的雪花算法生成分布式主…...
synchronzed为什么要升级为重量级锁,轻量级锁不好吗?
轻量级锁和重量级锁各有其适用场景和优缺点。轻量级锁旨在减少在无竞争情况下的同步开销,而重量级锁则在竞争激烈的情况下确保线程的同步。以下是为什么在某些情况下需要将轻量级锁升级为重量级锁的原因,以及轻量级锁的不足之处: 为什么需要…...
.NET 项目中发送电子邮件异步处理和错误机制的解决方案
在 .NET 中处理电子邮件,可以使用多种技术和库来实现高效的电子邮件发送、接收和管理。以下是一些常见的解决方案和最佳实践: 目录 1. 使用 SMTP 发送电子邮件 2. 使用 IMAP/POP3 接收电子邮件 3. 异步处理电子邮件 4. 处理大型邮件队列 5. 错误处…...

如何在银河麒麟操作系统上搭建 Electron (含 Electron 打包指南)
本次教程所用版本 Eletron版本:31.3.1 Electron-packager版本:17.1.2 VScode版本:1.92.0 Node版本:18.19.0 npm版本:10.2.3 前言: 随着跨平台应用开发的需求日益增长,Electron 和 Qt 成为…...

小怡分享之数据结构基础知识准备
前言: 🌈✨之前小怡给大家分享了JavaSE的知识,今天小怡要给大家分享一下数据结构基础知识。 一、初识集合框架 1.什么是集合框架 Java集合框架Java Collection Framework, 又称为容器container,是定义在Java.util 包…...
Linux安全与高级应用(三)深入探索MySQL数据库:安装、管理与安全实践
文章目录 深入探索MySQL数据库:安装、管理与安全实践MySQL数据库简介MySQL的安装与配置编译安装MySQL配置MySQL服务 MySQL数据库的基本操作数据库的创建与删除表的创建与管理数据记录的增删改查 MySQL用户管理与权限设置MySQL数据库的备份与恢复数据库备份数据库恢复…...

基于jsp的宠物领养与服务管理系统(源码+论文+部署讲解等)
博主介绍:✌全网粉丝10W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术栈介绍:我是程序员阿龙ÿ…...

基于STM32F407+NBIOT+华为云IOT平台设计的环境检测系统
基于STM32F407NBIOT华为云IOT平台设计的环境检测系统实现的功能: 【1】能够采集本地环境的温度、湿度、烟雾浓度,火光信息,在OLED显示屏上显示。 如果检测到烟雾、温度、火光超过阀值会触发蜂鸣器报警。 【2】能够通过NBIOT将本地设备采集的信…...
工具方法 - 如何表扬小孩子
赞扬小朋友的表现可以通过多种方法来进行,以鼓励他们的积极行为和努力,增强他们的自信心和动力。以下是一些有效的赞扬方法: 1. 具体表扬:指出具体的行为或成就,而不是泛泛地说“你很棒”。例如,“你今天很…...
【扒模块】DySample
逐行注释 import torch import torch.nn as nn import torch.nn.functional as F import warnings# 忽略警告信息,这通常用于开发过程中,避免警告干扰输出结果 warnings.filterwarnings(ignore)# 定义一个函数,用于对神经网络模块的权重进行…...
数学建模之数据分析【四】:变量及其分析
文章目录 一、单变量数据1.1 单变量数据1.2 单变量分析的要点: 二、双变量数据2.1 双变量数据2.2 双变量分析的要点 三、多元数据3.1 多元数据3.2 多元分析的要点 四、单变量,双变量和多变量数据之间的区别 公众号/小红书: 快乐数模 CSDN: 清上尘 本文&a…...

iOS ------ UIKit相关
UIView和CALayer UIView UIView表示屏幕上的一块矩形区域,它是基本上iOS中所有可视化控件的父类。UIView可以管理矩形区域里的内容,处理矩形区域的事件,包括子视图的管理以及动画的实现。 UIKit相关类的继承关系 UIView继承自UIResponde…...

24/8/9算法笔记 随机森林
"极限森林"(Extremely Randomized Trees,简称ERT)是一种集成学习方法,它属于决策树的变体,通常被归类为随机森林(Random Forest)的一种。极限森林的核心思想是在构建决策树时引入极端…...
如何在前后端分离项目中,使用Spring Security
使用 WebSecurityConfigurationAdapter 在前后端分离的架构中,通常使用 Token 进行认证和授权是一种常见的做法。Token 可以是 JSON Web Token(JWT),用于在客户端和服务器之间传递身份信息和访问控制信息。下面我将详细介绍如何在…...
c#怎么折叠代码快捷
在C#中,你可以使用快捷键来折叠或展开代码,以便更好地管理和浏览代码。以下是一些常用的快捷键: 折叠所有方法:使用Ctrl M O。折叠或展开当前方法:使用Ctrl M M。展开所有方法:使用…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...

基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...

STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...