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 threadsOptimize 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 nonzerosIteration    Objective       Primal Inf.    Dual Inf.      Time0    3.2500000e+30   2.812500e+30   3.250000e+00      0s2    4.2800000e+02   0.000000e+00   0.000000e+00      0sSolved 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 threadsOptimize 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 threadsOptimize 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 nonzerosIteration    Objective       Primal Inf.    Dual Inf.      Time0    5.0000000e+30   2.750000e+30   5.000000e+00      0s2    1.4750000e+01   0.000000e+00   0.000000e+00      0sSolved 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 threadsOptimize 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 nonzerosIteration    Objective       Primal Inf.    Dual Inf.      Time0    3.2500000e+30   2.812500e+30   3.250000e+00      0s2    4.2800000e+02   0.000000e+00   0.000000e+00      0sSolved 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 threadsOptimize 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 nonzerosIteration    Objective       Primal Inf.    Dual Inf.      Time0    0.0000000e+00   4.187500e+01   0.000000e+00      0s3    2.9842520e+01   0.000000e+00   0.000000e+00      0sSolved 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 threadsOptimize 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 threadsOptimize 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 nonzerosIteration    Objective       Primal Inf.    Dual Inf.      Time0    5.0000000e+30   2.750000e+30   5.000000e+00      0s2    1.4750000e+01   0.000000e+00   0.000000e+00      0sSolved 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 threadsOptimize 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.0000000Explored 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.pswp.cn/news/167677.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/167677.shtml
英文地址，請注明出處：http://en.pswp.cn/news/167677.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

【Python 訓練營】N_6 求素數

【Python 訓練營】N_6 求素數

題目 判斷101-200之間有多少個素數&#xff0c;并輸出所有素數。 分析 判斷素數的方法&#xff1a;用一個數分別去除2到sqrt(這個數)&#xff0c;如果能被整除&#xff0c;則表明此數不是素數&#xff0c;反之是素數。 答案 h 0 leap 1 from math import sqrt from sys …
閱讀更多...
2023亞太地區數學建模C題思路模型代碼論文

2023亞太地區數學建模C題思路模型代碼論文

C題的參考思路: 1&#xff0c;問題1的思路: 確定研究問題的主要指標體系(新能源電車的售出數量、安全性指標、充電樁數目、電池續 航里程等)&#xff0c;收集指標的對應數據&#xff0c;檢驗數據是否服從正態性: 若服從正態分布: 0&#xff0c;可考慮優先采用“多元方差分析”模…
閱讀更多...
Python推導式

Python推導式

python推導式是一種獨特的數據處理方式&#xff0c;可以從一個數據序列構建到另一個新的數據序列的結構體。 Python支持各種數據結構的推導式&#xff1a; 1. 列表&#xff08;list&#xff09;推導式 [表達式 for 變量 in 列表] [out_exp_res for out_exp in input_list] or …
閱讀更多...
【?用運算放大器設計恒流電流源電壓4V-74V適應范圍 ?】2021-11-29

【?用運算放大器設計恒流電流源電壓4V-74V適應范圍 ?】2021-11-29

緣由用運算放大器設計恒流電流源-編程語言-CSDN問答直流恒流源設計&#xff0c;要求用到運算放大器-硬件開發-CSDN問答求助恒流驅動電路&#xff0c;運放端口電壓的問題&#xff1f; - 電路設計論壇 - 電子技術論壇 - 廣受歡迎的專業電子論壇!(不能實現恒流壞的電路設計反面例子…
閱讀更多...
OpenCV快速入門：特征點檢測與匹配

OpenCV快速入門：特征點檢測與匹配

文章目錄 前言一、角點檢測1.1 角點特征1.1.1 角點特征概念1.1.2 角點的特點1.1.3 關鍵點繪制代碼實現1.1.4 函數解析 1.2 Harris角點檢測1.2.1 Harris角點檢測原理1.2.2 Harris角點檢測公式1.2.3 代碼實現1.2.4 函數解析 1.3 Shi-Tomasi角點檢測1.3.1 Shi-Tomasi角點檢測原理1…
閱讀更多...
GIT,解決遠程分支沖突

GIT,解決遠程分支沖突

背景&#xff1a;當遠程分支A 與maste 有沖突如何解決–此時無法在這兩個版本之間merge 1、切換到master分支&#xff1a; git checkout master 2、更新master分支代碼&#xff1a; git pull 3、再次切換到自己新建的分支&#xff1a; git checkout add_login_check_func 4、將…
閱讀更多...
SuperMap iDesktopX如何獲取簡單線的起終端點及坐標

SuperMap iDesktopX如何獲取簡單線的起終端點及坐標

作者&#xff1a;超圖研究院技術支持中心-于丁 SuperMap iDesktopX如何獲取簡單線的起終端點及坐標 在GIS行業應用中&#xff0c;線數據的端點坐標有非常多的用處。 定位和可視化&#xff1a;線數據端點坐標可以用于定位和可視化線要素在空間中的位置。這對于地圖制作、規劃和…
閱讀更多...
初識Linux（1），看了這篇文章，媽媽再也不用擔心我Linux找不到門了。

初識Linux（1），看了這篇文章，媽媽再也不用擔心我Linux找不到門了。

文章目錄 前言1. ls 指令例如&#xff1a;只顯示文件名屬性ls顯示文件詳細屬性 ls - l 該操作可以簡寫成ll查看隱藏文件ls -l -a 2.pwd例如&#xff1a;顯示當前目錄所處的路徑類似于windows如下操作: 3.cd 指令例如&#xff1a;改變工作目錄相當于windows如下操作 4.whoami 指…
閱讀更多...
html幸運大轉盤抽獎（附源碼）

html幸運大轉盤抽獎（附源碼）

文章目錄 1.設計來源1.1 幸運大轉盤 風格11.2 幸運大轉盤 風格21.3 幸運大轉盤 風格31.4 幸運大轉盤 獎品效果1.5 幸運大轉盤 活動未開始1.6 幸運大轉盤 活動已結束1.7 幸運大轉盤 圖片源素材 2.效果和源碼2.1 動態效果2.2 源代碼 源碼下載 作者&#xff1a;xcLeigh 文章地址&a…
閱讀更多...
Windows power shell for循環

Windows power shell for循環

有時候需要重復執行某個shell命令 for($i1;$i -lt 10;$i$i1){echo $i}如果是cmd for /l %i in (1,1,5) do echo %i
閱讀更多...
vue 使用vuex中的data數據引用問題

vue 使用vuex中的data數據引用問題

先上代碼&#xff1a; this.userRoleInfo2 this.$store.state.userInfo this.userRoleInfo2.name 111 this.userRoleInfo2.orgName 222 this.userRoleInfo2.orgId 4444問題描述&#xff1a; 博主&#xff0c;定義了一個變量userRoleInfo2來接收了 從vuex中獲取了userInfo…
閱讀更多...
卷積神經網絡（Inception V3）識別手語

卷積神經網絡（Inception V3）識別手語

文章目錄 一、前言二、前期工作1. 設置GPU&#xff08;如果使用的是CPU可以忽略這步&#xff09;2. 導入數據3. 查看數據 二、數據預處理1. 加載數據2. 可視化數據3. 再次檢查數據4. 配置數據集 三、構建Inception V3網絡模型1.自己搭建2.官方模型 五、編譯六、訓練模型七、模型…
閱讀更多...
再生式收音機踩坑記

再生式收音機踩坑記

下載《A Simple Regen Radio for Beginners》這篇文章也有好幾年了&#xff0c;一直沒有動手&#xff0c;上周末抽空做了一個&#xff0c;結果相當令人沮喪&#xff0c;一個臺也收不到&#xff0c;用示波器測量三極管振蕩波形&#xff0c;只有在調節再生電位器R2過程中&#xf…
閱讀更多...
什么是合封芯片工藝，合封芯片工藝工作原理、應用場景、技術要點

什么是合封芯片工藝，合封芯片工藝工作原理、應用場景、技術要點

芯片封裝技術不斷進步&#xff0c;其中合封芯片工藝作為一種先進的芯片封裝技術&#xff0c;“超”廣泛應用于各類電子設備中。 本文將從合封芯片工藝的工作原理、應用場景、技術要點等方面進行深入解讀。 一、合封芯片工藝 合封芯片工藝是一種將多個芯片或不同的功能的電子模…
閱讀更多...
構造命題公式的真值表

構造命題公式的真值表

構造命題公式的真值表 1&#xff1a;實驗類型&#xff1a;驗證性2&#xff1a;實驗目的&#xff1a;3&#xff1a;邏輯聯結詞的定義方法4&#xff1a;命題公式的表示方法5&#xff1a;【實驗內容】 1&#xff1a;實驗類型&#xff1a;驗證性 2&#xff1a;實驗目的&#xff1a…
閱讀更多...
數據黑洞，正在悄悄吞噬你的門店業績

數據黑洞，正在悄悄吞噬你的門店業績

互聯網興起以來&#xff0c;線下門店的數字化程度始終落后于線上。一個重要的原因是&#xff1a;線下信息不像線上那樣簡單、集中、易于統計。很多重要數據隱藏于「黑洞」之中&#xff0c;收集和分析成本極為高昂。這極大束縛了門店業績的提升。 而反過來看&#xff0c;線下場景…
閱讀更多...
C++(20)：通過source_location實現日志函數

C++(20)：通過source_location實現日志函數

C++20中引入了std::source_location，用來描述函數調用的上下文信息。 其主要的成員函數如下： line()：獲取行號。column()：獲取列號。file_name()：獲取文件名。function_name()：獲取函數域名。#include <iostream> #include <string_view> #include <sour…
閱讀更多...
BGP聯邦及路由反射器配置

BGP聯邦及路由反射器配置

需求 1 AS1存在兩個環回&#xff0c;一個地址為192.168.1.0/24&#xff0c;該地址不能再任何協議中宣告 AS3存在兩個環回&#xff0c;一個地址為192.168.2.0/24&#xff0c;該地址不能再任何協議中宣告 AS1還有一個環回地址為10.1.1.0/24&#xff0c;AS3另一個環回地址是11.1.1…
閱讀更多...
DQN算法

DQN算法

DQN算法 教程鏈接 DataWhale強化學習課程JoyRL https://johnjim0816.com/joyrl-book/#/ch7/main DQN算法 DQN(Deep Q-Network) 主要創新點在于將Q-learning算法中的Q表記錄動作價值函數轉為引入深度神經網絡來近似動作價值函數 Q ( s , a ) Q(s,a) Q(s,a),從而能夠處理連續…
閱讀更多...
C現代方法（第23章）筆記——庫對數值和字符數據的支持

C現代方法（第23章）筆記——庫對數值和字符數據的支持

文章目錄 第23章 庫對數值和字符數據的支持23.1 <float.h>: 浮點類型的特性23.2 <limits.h>: 整數類型的大小23.3 <math.h>: 數學計算(C89)23.3.1 錯誤23.3.2 三角函數23.3.3 雙曲函數23.3.4 指數函數和對數函數23.3.5 冪函數23.3.6 就近舍入、絕對值函數和取…
閱讀更多...
最新文章

Copyright @ 2022~2023