python+gurobi求解线性规划、整数规划、0-1规划

文章目录

        • 简单回顾
        • 线性规划LP
        • 整数规划IP
        • 0-1规划

简单回顾

线性规划是数学规划中的一类最简单规划问题，常见的线性规划是一个有约束的，变量范围为有理数的线性规划。如：

在这里插入图片描述
使用matlab的linprog函数即可求解简单的线性规划问题，可以参考这篇博客：
MATLAB求解线性规划（含整数规划和0-1规划）问题

matlab求解线性规划LP问题需要化为最小化问题，所有约束条件必须为≤类型，限制较多。本文介绍使用python+gurobi进行求解。
在这里插入图片描述
python+gurobi介绍参考这篇博客：
gurobi最新下载安装教程 2023.11

线性规划LP

在这里插入图片描述

import gurobipy
from gurobipy import GRB

# 创建模型
c = [7, 12]
a = [[9, 4],
	[4, 5],
	[3, 10]]
b = [300, 200, 300]
MODEL = gurobipy.Model("Example")

# 创建变量
x = MODEL.addVars(2, lb=0, ub=gurobipy.GRB.INFINITY, name='x')

# 更新变量环境
MODEL.update()

# 创建目标函数
MODEL.setObjective(x.prod(c), gurobipy.GRB.MAXIMIZE)

# 创建约束条件
MODEL.addConstrs(x.prod(a[i]) <= b[i] for i in range(3))

# 执行线性规划模型
MODEL.optimize()
print("Obj:", MODEL.objVal)
for v in MODEL.getVars():
	print(f"{v.VarName}：{round(v.X,3)}")


Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)

CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3 rows, 2 columns and 6 nonzeros
Model fingerprint: 0x6b25b35d
Coefficient statistics:
  Matrix range     [3e+00, 1e+01]
  Objective range  [7e+00, 1e+01]
  Bounds range     [0e+00, 0e+00]
  RHS range        [2e+02, 3e+02]
Presolve time: 0.01s
Presolved: 3 rows, 2 columns, 6 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    3.2500000e+30   2.812500e+30   3.250000e+00      0s
       2    4.2800000e+02   0.000000e+00   0.000000e+00      0s

Solved in 2 iterations and 0.01 seconds (0.00 work units)
Optimal objective  4.280000000e+02
Obj: 428.0
x[0]：20.0
x[1]：24.0

最终可得最优解为x = 20, y = 24, 最优值为428。
gurobi对最大化问题、最小化问题，大于等于和小于等于约束都支持。

整数规划IP

在这里插入图片描述

import gurobipy
from gurobipy import GRB
import numpy as np

# 创建模型
c = [3, 2]
a = [[2, 3],
	[4, 2]]
b = [14, 18]
MODEL = gurobipy.Model("Example")

# 创建变量
#x = MODEL.addVars(2, lb=0, ub=gurobipy.GRB.INFINITY, name='x')

x1 = MODEL.addVar(vtype=GRB.INTEGER,lb=0,ub=GRB.INFINITY, name='x1')
x2 = MODEL.addVar(vtype=GRB.INTEGER,lb=0,ub=GRB.INFINITY, name='x2')
# 更新变量环境

MODEL.update()

# 创建目标函数
MODEL.setObjective(c[0]*x1+c[1]*x2, gurobipy.GRB.MAXIMIZE)

# 创建约束条件
for i in range(2):
    MODEL.addConstr(a[i][0]*x1 + a[i][1]*x2 <= b[i])

# 执行线性规划模型
MODEL.optimize()
print("Obj:", MODEL.objVal)
for v in MODEL.getVars():
	print(f"{v.VarName}：{round(v.X,3)}")

Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)

CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x15a6e8bd
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:
  Matrix range     [2e+00, 4e+00]
  Objective range  [2e+00, 3e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e+01, 2e+01]
Found heuristic solution: objective 14.0000000
Presolve time: 0.00s
Presolved: 2 rows, 2 columns, 4 nonzeros
Variable types: 0 continuous, 2 integer (0 binary)

Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 1: 14 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.400000000000e+01, best bound 1.400000000000e+01, gap 0.0000%
Obj: 14.0
x1：4.0
x2：1.0

可得该整数规划问题的最优解为x1 = 4, x2 = 1,最优值为14。

如果解其对应的松弛问题：

import gurobipy
from gurobipy import GRB
import numpy as np

# 创建模型
c = [3, 2]
a = [[2, 3],
	[4, 2]]
b = [14, 18]
MODEL = gurobipy.Model("Example")

# 创建变量
x = MODEL.addVars(2, lb=0, ub=gurobipy.GRB.INFINITY, name='x')

# 更新变量环境

MODEL.update()

# 创建目标函数
MODEL.setObjective(x.prod(c), gurobipy.GRB.MAXIMIZE)

# 创建约束条件
MODEL.addConstrs(x.prod(a[i]) <= b[i] for i in range(2))

# 执行线性规划模型
MODEL.optimize()
print("Obj:", MODEL.objVal)
for v in MODEL.getVars():
	print(f"{v.VarName}：{round(v.X,3)}")

Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)

CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x15a42e7d
Coefficient statistics:
  Matrix range     [2e+00, 4e+00]
  Objective range  [2e+00, 3e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e+01, 2e+01]
Presolve time: 0.01s
Presolved: 2 rows, 2 columns, 4 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    5.0000000e+30   2.750000e+30   5.000000e+00      0s
       2    1.4750000e+01   0.000000e+00   0.000000e+00      0s

Solved in 2 iterations and 0.01 seconds (0.00 work units)
Optimal objective  1.475000000e+01
Obj: 14.75
x[0]：3.25
x[1]：2.5

可以发现对应的解是x1 = 3.25, x2 = 2.5, 最优值为14.75。松弛问题的最优解总是优于整数规划问题的。

0-1规划

无论是matlab的linprog函数还是gurobi，0-1规划实际上只需要在整数规划的基础上，让决策变量的定义域在0-1之间即可。

仍然是上面的同一个问题：

##  0-1规划

import gurobipy
from gurobipy import GRB

# 创建模型
c = [3, 2]
a = [[2, 3],
	[4, 2]]
b = [14, 18]
MODEL = gurobipy.Model("Example")

# 创建变量
#x = MODEL.addVars(2, lb=0, ub=gurobipy.GRB.INFINITY, name='x')

x1 = MODEL.addVar(vtype=GRB.INTEGER,lb=0,ub=1, name='x1')
x2 = MODEL.addVar(vtype=GRB.INTEGER,lb=0,ub=1, name='x2')
# 更新变量环境

MODEL.update()

# 创建目标函数
MODEL.setObjective(c[0]*x1+c[1]*x2, gurobipy.GRB.MAXIMIZE)

# 创建约束条件
for i in range(2):
    MODEL.addConstr(a[i][0]*x1 + a[i][1]*x2 <= b[i])

# 执行线性规划模型
MODEL.optimize()
print("Obj:", MODEL.objVal)
for v in MODEL.getVars():
	print(f"{v.VarName}：{round(v.X,3)}")

Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)

CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3 rows, 2 columns and 6 nonzeros
Model fingerprint: 0x6b25b35d
Coefficient statistics:
  Matrix range     [3e+00, 1e+01]
  Objective range  [7e+00, 1e+01]
  Bounds range     [0e+00, 0e+00]
  RHS range        [2e+02, 3e+02]
Presolve time: 0.01s
Presolved: 3 rows, 2 columns, 6 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    3.2500000e+30   2.812500e+30   3.250000e+00      0s
       2    4.2800000e+02   0.000000e+00   0.000000e+00      0s

Solved in 2 iterations and 0.01 seconds (0.00 work units)
Optimal objective  4.280000000e+02
Obj: 428.0
x[0]：20.0
x[1]：24.0
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)

CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3 rows, 6 columns and 18 nonzeros
Model fingerprint: 0x157f6a4a
Coefficient statistics:
  Matrix range     [9e+00, 6e+01]
  Objective range  [6e+00, 1e+01]
  Bounds range     [0e+00, 0e+00]
  RHS range        [6e+01, 2e+02]
Presolve time: 0.01s
Presolved: 3 rows, 6 columns, 18 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    0.0000000e+00   4.187500e+01   0.000000e+00      0s
       3    2.9842520e+01   0.000000e+00   0.000000e+00      0s

Solved in 3 iterations and 0.01 seconds (0.00 work units)
Optimal objective  2.984251969e+01
Obj: 29.84251968503937
x[0]：0.0
x[1]：0.433
x[2]：0.0
x[3]：4.252
x[4]：0.0
x[5]：0.0
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)

CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x15a6e8bd
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:
  Matrix range     [2e+00, 4e+00]
  Objective range  [2e+00, 3e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e+01, 2e+01]
Found heuristic solution: objective 14.0000000
Presolve time: 0.00s
Presolved: 2 rows, 2 columns, 4 nonzeros
Variable types: 0 continuous, 2 integer (0 binary)

Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 1: 14 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.400000000000e+01, best bound 1.400000000000e+01, gap 0.0000%
Obj: 14.0
x1：4.0
x2：1.0
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)

CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x15a42e7d
Coefficient statistics:
  Matrix range     [2e+00, 4e+00]
  Objective range  [2e+00, 3e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e+01, 2e+01]
Presolve time: 0.01s
Presolved: 2 rows, 2 columns, 4 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    5.0000000e+30   2.750000e+30   5.000000e+00      0s
       2    1.4750000e+01   0.000000e+00   0.000000e+00      0s

Solved in 2 iterations and 0.01 seconds (0.00 work units)
Optimal objective  1.475000000e+01
Obj: 14.75
x[0]：3.25
x[1]：2.5
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)

CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0xdff3d373
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:
  Matrix range     [2e+00, 4e+00]
  Objective range  [2e+00, 3e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 2e+01]
Found heuristic solution: objective 5.0000000

Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 8 available processors)

Solution count 1: 5 

Optimal solution found (tolerance 1.00e-04)
Best objective 5.000000000000e+00, best bound 5.000000000000e+00, gap 0.0000%
Obj: 5.0
x1：1.0
x2：1.0

可得0-1规划的最优解是x1 = x2 = 1, 最优值 = 5。
当然0-1规划的典型应用场景是指派问题、运输问题、排班问题等。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

人力资源管理后台 === 角色管理

人力资源管理后台 === 角色管理

目录 1.组织架构-编辑部门-弹出层获取数据 2.组织架构-编辑部门-编辑表单校验 3.组织架构-编辑部门-确认取消 4.组织架构-删除部门 5.角色管理-搭建页面结构 6.角色管理-获取数据 7.角色管理-表格自定义结构 8.角色管理-分页功能 9.角色管理-新增功能弹层 10.角色管理…
阅读更多...
springboot实现验证码功能

springboot实现验证码功能

转载自 : www.javaman.cn 1、编写工具类生成4位随机数 该工具类主要生成从0-9&#xff0c;a-z&#xff0c;A-Z范围内产生的4位随机数 /*** 产生4位随机字符串*/public static String getCheckCode() {String base "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmn…
阅读更多...
【TinyALSA全解析（三）】tinyplay、tincap、pcm_open源码解析

【TinyALSA全解析（三）】tinyplay、tincap、pcm_open源码解析

tinyplay、tincap、pcm_open源码解析 一、本文的目的二、tinyplay.c源码分析三、tinycap.c源码分析四、pcm.c如何调度到Linux Kernel4.1 pcm_open解析4.1.1 pcm_open的主要流程4.1.2 流程说明4.1.3 调用方法 4.2 pcm_write解析 /*********************************************…
阅读更多...
文章改写工具-改写神器

文章改写工具-改写神器

当代社会&#xff0c;信息爆炸&#xff0c;写作已成为人们生活与工作中不可或缺的一环。无论是学术论文、商业报告还是日常沟通&#xff0c;文字的准确表达和精彩呈现是至关重要的。然而&#xff0c;许多人在面对写作时&#xff0c;常常为语言表达、词汇选择而苦恼。为了解决这…
阅读更多...
基于OpenCV+YOLOv5实现车辆跟踪与计数(附源码)

基于OpenCV+YOLOv5实现车辆跟踪与计数(附源码)

导 读 本文主要介绍基于OpenCVYOLOv5实现车辆跟踪与计数的应用&#xff0c;并给出源码。 资源下载 基础代码和视频下载地址&#xff1a; https://github.com/freedomwebtech/win11vehiclecount main.py代码:​​​​​​​ import cv2import torchimport numpy as npfrom tr…
阅读更多...
Dockerfile讲解

Dockerfile讲解

Dockerfile 1. 构建过程解析2. Dockerfile常用保留字指令3. 案例3.1. 自定义镜像mycentosjava83.2. 虚悬镜像 4. Docker微服务实战 dockerfile是用来构建docker镜像的文本文件&#xff0c;是由一条条构建镜像所需的指令和参数构成的脚本。 dockerfile定义了进程需要的一切东西&…
阅读更多...
hdlbits系列verilog解答（Exams/m2014 q4e）-46

hdlbits系列verilog解答（Exams/m2014 q4e）-46

文章目录 一、问题描述二、verilog源码三、仿真结果 一、问题描述 实现以下电路&#xff1a; 二、verilog源码 module top_module (input in1,input in2,output out);assign out ~(in1 | in2);endmodule三、仿真结果 转载请注明出处&#xff01;
阅读更多...
JOSEF 综合继电器 HJZZ-32/2 AC220V 合闸延时整定0.02-9.99S

JOSEF 综合继电器 HJZZ-32/2 AC220V 合闸延时整定0.02-9.99S

系列型号&#xff1a; HJZZ-91分闸、合闸、电源监视综合装置&#xff1b; HJZZ-92/1分闸、合闸、电源监视综合装置&#xff1b; HJZZ-92/2分闸、合闸、电源监视综合装置&#xff1b; HJZZ-92/2A分闸、合闸、电源监视综合装置&#xff1b; HJZZ-92/3分闸、合闸、电源监视综…
阅读更多...
Gitee上传代码教程

Gitee上传代码教程

1. 本地安装git 官网下载太慢&#xff0c;我们也可以使用淘宝镜像下载&#xff1a;CNPM Binaries Mirror 安装成功以后电脑会有Git Bush标识&#xff0c;空白处右键也可查看。 2. 注册gitee账号&#xff08;略&#xff09; 3. 创建远程仓库 4. 上传代码 4.1 在项目文件目录…
阅读更多...
【教学类-06-10】20231126 X-Y数字分合-分-下空左

【教学类-06-10】20231126 X-Y数字分合-分-下空左

结果展示&#xff1a; 背景需求&#xff1a; 数字分合&#xff0c;这一次空在左侧 代码展示&#xff1a; X-Y 之间的分合题-分-空在右侧 时间&#xff1a;2023年11月26日 21:46 作者&#xff1a;阿夏 import random from win32com.client import constants,gencache from win3…
阅读更多...
python之静态服务器程序开发

python之静态服务器程序开发

文章目录 Python静态Web服务器开发Web静态服务器初识搭建Python自带的静态Web服务器静态Web服务器返回固定页面数据静态Web服务器返回指定页面数据静态Web服务器多任务版静态Web服务器面向对象开发静态Web服务器命令行启动动态绑定端口号 Python静态Web服务器开发 Web静态服务…
阅读更多...
Web3.0时代：区块链DAPP将如何颠覆传统模式

Web3.0时代：区块链DAPP将如何颠覆传统模式

小编介绍&#xff1a;10年专注商业模式设计及软件开发&#xff0c;擅长企业生态商业模式&#xff0c;商业零售会员增长裂变模式策划、商业闭环模式设计及方案落地&#xff1b;扶持10余个电商平台做到营收过千万&#xff0c;数百个平台达到百万会员&#xff0c;欢迎咨询。 随着…
阅读更多...
基于DSP/SOC音乐灯效系统设计方法

基于DSP/SOC音乐灯效系统设计方法

音乐灯效系统设计方法 是否需要申请加入数字音频系统研究开发交流答疑群(课题组)？可加我微信hezkz17, 本群提供音频技术答疑服务，+群赠送语音信号处理降噪算法，蓝牙耳机音频，DSP音频项目核心开发资料, 三种方法： （1）MIC 采集音乐信号变化，（2）直接获取SPK 模拟音频…
阅读更多...
使用char.js 柱形方式显示 一年12个月的最高气温与最低气温

使用char.js 柱形方式显示 一年12个月的最高气温与最低气温

<!DOCTYPE html> <html> <head><title>气温图表</title><script src"https://cdn.jsdelivr.net/npm/chart.js"></script><style>#myChart{width:800px;height: 400px;}</style> </head> <body>&l…
阅读更多...
【Linux】：信号在内核里的处理

【Linux】：信号在内核里的处理

信号的发送和保存 一.内核中的信号处理二.信号集操作函数1.一些信号函数2.sigprocmask3.sigpending4.写代码 三.信号在什么时候处理的四.再谈地址空间 一.内核中的信号处理 1.实际执行信号的处理动作称为信号递达(Delivery )2.信号从产生到递达之间的状态,称为信号未决(Pending…
阅读更多...
通义灵码，你的智能编码助手，免费公测啦！

通义灵码，你的智能编码助手，免费公测啦！

目录 ​编辑 1、介绍 2、安装 3、功能介绍 行/函数级实时续写 自然语言生成代码 单元测试生成 代码注释生成 代码解释 研发智能问答 多编程语言、多编辑器全方位支持 4、视频 &#x1f343;作者介绍&#xff1a;双非本科大三网络工程专业在读&#xff0c;阿里云专家…
阅读更多...
QT Day01 qt概述，创建项目，窗口属性，按钮，信号与槽

QT Day01 qt概述，创建项目，窗口属性，按钮，信号与槽

1.qt概述 1.什么是qt Qt 是一个跨平台的 C 图形用户界面应用程序框架。它为应用程序开发者提供建立艺 术级图形界面所需的所有功能。它是完全面向对象的&#xff0c;很容易扩展&#xff0c;并且允许真正的组 件编程。 2.支持的平台 Windows – XP 、 Vista 、 Win7 、 Win8…
阅读更多...
博捷芯打破半导体切割划片设备技术垄断，国产产业链实现高端突破

博捷芯打破半导体切割划片设备技术垄断，国产产业链实现高端突破

近日&#xff0c;国内半导体产业传来喜讯&#xff0c;博捷芯成功实现批量供货半导体切割划片设备&#xff0c;打破国外企业在该领域的长期技术垄断&#xff0c;为国产半导体产业链在高端切割划片设备领域实现重大突破。 自上世纪90年代以来&#xff0c;由于国外企业的技术封锁和…
阅读更多...
通俗易懂的spring Cloud；业务场景介绍 二、Spring Cloud核心组件：Eureka 、Feign、Ribbon、Hystrix、zuul

通俗易懂的spring Cloud；业务场景介绍 二、Spring Cloud核心组件：Eureka 、Feign、Ribbon、Hystrix、zuul

文章目录 通俗易懂的spring Cloud一、业务场景介绍二、Spring Cloud核心组件&#xff1a;Eureka三、Spring Cloud核心组件&#xff1a;Feign四、Spring Cloud核心组件&#xff1a;Ribbon五、Spring Cloud核心组件&#xff1a;Hystrix六、Spring Cloud核心组件&#xff1a;Zuul七…
阅读更多...
vivado产生报告阅读分析25-复杂性报告

vivado产生报告阅读分析25-复杂性报告

对于顶层设计和 / 或包含 1000 个以上叶节点单元的层级单元 &#xff0c; 复杂性报告会显示每个叶节点单元类型的“ Rent Exponent” &#xff08; Rent 指数 &#xff09; 、“ Average Fanout ” &#xff08; 平均扇出 &#xff09; 和分布。 Rent 指数是指在使用最小割 …
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站