【学习笔记】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=110pixis.t.{i=110wixi30xi{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=14i=15tijxijs.I. j=14xij1,i=1,2,3,4,5i=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函数求解,只需要限定 lbub 即可
  • 例如: 三个决策变量: 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)问题,这些库提供了类似的功能:

  1. PuLP
  2. ORTools
  3. Gurobi
  4. 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进行代码编写。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/396010.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

案例精选 | 某省级妇幼保健院自动化安全运营中心建设成功实践

某省级妇幼保健院&#xff0c;是一所集医疗、保健、教学、科研、预防、康复于一体的省级三级甲等妇幼保健机构&#xff0c;专注于为全省妇女儿童提供全方位、高质量的医疗保健服务。医院拥有4个院区&#xff0c;总建筑面积10万平米&#xff0c;开放床位700张&#xff0c;年门诊…

【vue3|第21期】Vue3中Vue Router的push和replace方法详解

日期&#xff1a;2024年8月9日 作者&#xff1a;Commas 签名&#xff1a;(ง •_•)ง 积跬步以致千里,积小流以成江海…… 注释&#xff1a;如果您觉得有所帮助&#xff0c;帮忙点个赞&#xff0c;也可以关注我&#xff0c;我们一起成长&#xff1b;如果有不对的地方&#xff…

需求分析-系统架构师(四十六)

软件需求 软件需求&#xff1a;对系统在功能、行为、性能、设计约束等方面的期望。 分为 需求开发 和 需求管理 两大类。 需求分为 业务需求&#xff0c;用户需求&#xff0c;系统需求。 业务需求&#xff1a;企业或者客户对系统高层次的目标要求。 用户需求&#xff1a;用…

C#图片批量下载Demo

目录 效果 项目 代码 下载 效果 C#图片批量下载 项目 代码 using Aspose.Cells; using NLog; using System; using System.Collections.Generic; using System.Data; using System.Diagnostics; using System.Drawing; using System.IO; using System.Linq; using System.…

git强制推送代码教程

git强制推送代码教程 首先说明情况&#xff0c;我的代码remote了两个git库&#xff0c;现在想要推送到其中一个&#xff0c;但是版本不对&#xff0c;被拒绝&#xff0c;因此下面将进行强制推送 首先检查远程库都有哪些 git remote -v2. 检查当前的分支 git branch当前分支前…

八股总结----计算机网络

1.UDP头部格式 UDP的头部比较简单&#xff0c;只有8个字节&#xff0c;这也是为什么UDP不能像TCP那样实现可靠传输的原因。源端口和目标端口表示数据传输的来源和去向&#xff0c;包长度表示数据报文的总长度&#xff08;包含了头部和数据部分&#xff09;&#xff0c;方便接收…

stm32程序调试方式(OLED显示屏调试以及Keil调试模式)

文章目录 前言一、调试的方式二、OLED显示屏调试2.1 OLED简介2.2 OLED硬件电路2.3 OLED驱动函数介绍2.4 OLED显示屏应用案例代码 三、Keil调试模式总结 前言 提示&#xff1a;本文主要用作在学习江协科大STM32入门教程后做的归纳总结笔记&#xff0c;旨在学习记录&#xff0c;…

基于GeoTools使用JavaFx进行矢量数据可视化实战

目录 前言 一、JavaFx展示原理说明 二、GeoTools的Maven依赖问题 三、引入Geotools相关的资源包 四、创建JavaFx的Canvas实例 五、JavaFx的Scene和Node的绑定 六、总结 前言 众所周知&#xff0c;JavaFx是Java继Swing之后的又一款用于桌面应用的开发利器。当然&#xff0…

9.C基础_指针与数组

数组指针&#xff08;一维数组&#xff09; 数组指针就是" 数组的指针 "&#xff0c;它是一个指向数组首地址的指针变量。 1、数组名的含义 对于一维数组&#xff0c;数组名就是一个指针&#xff0c;指向数组的首地址。 基于如下代码进行分析&#xff1a; int a…

语言模型-神经网络模型(二)

神经网络模型语言模型 神经网络模型神经网络的分类神经网络模型和Ngram对比应用一-话者分离对比优劣 应用二-数字归一化应用三-文本打标 神经网络模型 释义&#xff1a; 与ngram模型相似使用&#xff0c;前n个词预测下一个词&#xff0c;输出在字表上的概率分布&#xff1b;过…

如何设置 Visual Studio Code 的滚轮缩放功能

Visual Studio Code (VSCode) 是一个强大的代码编辑器&#xff0c;提供了许多便捷的功能来提高开发效率。其中之一就是通过滚轮缩放字体大小。以下是详细的设置步骤&#xff1a; 步骤 1&#xff1a;打开设置页面 首先&#xff0c;启动 Visual Studio Code。在左上角点击 “文…

【机器学习基础】线性回归

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈Python机器学习 ⌋ ⌋ ⌋ 机器学习是一门人工智能的分支学科&#xff0c;通过算法和模型让计算机从数据中学习&#xff0c;进行模型训练和优化&#xff0c;做出预测、分类和决策支持。Python成为机器学习的首选语言&#xff0c;…

集成视触觉传感器的机器人操作学习

强化学习是一种仿人学习的方法&#xff0c;其在不断与环境交互试错的过程中进行学习&#xff0c;提高自身的认知。其具有如下的优点&#xff0c;首先是数据依赖性低&#xff0c;强化学习通过与环境的交互来学习&#xff0c;减少了对标记数据的依赖性&#xff0c;可以大量的减少…

Linux 系统框架分析(一)

一、linux内核结构框图 对内核结构框图有个总体的把握&#xff0c;有助于理解为什么驱动要这样写&#xff0c;为什么写的应用程序所用的C库接口能够产生这么多的事情。 框图可以看出来&#xff0c;linux系统&#xff0c;包括五个系统 一、Linux内核结构介绍 Linux 内核是操作…

Spring及相关框架的重要的问题

Java框架 问题一&#xff1a;Spring框架中的单例bean是线程安全的吗&#xff1f; 看下图&#xff0c;不能被修改的成员变量就是无状态的类&#xff0c;无状态的类没有线程安全问题&#xff0c;所以在开发中尽量避免可修改的成员变量。 回答&#xff1a;不是线程安全的&#xf…

Oracle一对多(一主多备)的DG环境如何进行switchover切换?

本文主要分享Oracle一对多(一主多备)的DG环境的switchover切换&#xff0c;如何进行主从切换&#xff0c;切换后怎么恢复正常同步&#xff1f; 1、环境说明 本文的环境为一主两备&#xff0c;数据库版本为11.2.0.4&#xff0c;主要信息如下&#xff1a; 数据库IPdb_unique_n…

Github 2024-08-09 开源项目日报 Top10

根据Github Trendings的统计,今日(2024-08-09统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目6TypeScript项目4Jupyter Notebook项目1Cuda项目1Sentry:开发者优先的错误跟踪和性能监控平台 创建周期:5093 天开发语言:Python,…

android系统中data下的xml乱码无法查看问题剖析及解决方法

背景&#xff1a; Android12高版本以后系统生成的很多data路径下的xml都变成了二进制类型&#xff0c;根本没办法看xml的内容具体如下&#xff1a; 比如想要看当前系统的widget的相关数据 ./system/users/0/appwidgets.xml 以前老版本都是可以直接看的&#xff0c;这些syste…

旅游出行必备商城小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;新闻类型管理&#xff0c;新闻资讯管理&#xff0c;商品类型管理&#xff0c;旅游商品管理&#xff0c;旅游景点&#xff0c;景点分类&#xff0c;系统管理 微信端账号功能包括&am…

GitHub的常用操作

目录 GitHub GitHub加速 克隆GitHub上的项目到本地 克隆GitHub上指定分支的项目 把本地项目上传到GitHub上管理 删除分支里的内容 单个仓库管理多个项目 上传项目到新建的分支 目前正在逐步熟悉GitHub&#xff0c;打算把整理好的代码上传到GitHub上&#xff0c;建立属…