前言
通过模子算法，熟练对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：一个结构体，包罗求解器的选项。
返回值的寄义如下：
线性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:5
- A(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举行代码编写。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金 |
发表于 2026-2-10 19:38:34