视频分享网站怎么做,网站一级页面二级页面怎么做,注册深圳公司代理,广告平面设计作品文章目录 前言一、整数规划和0-1规划二、典型示例1.背包问题2.指派问题 三、代码实现----Matlab1.Matlab 的 intlinprog 函数2.Matlab 代码背包问题指派问题 四、代码实现----python背包问题指派问题 总结 前言
通过模型算法#xff0c;熟练对Matlab和python的应用。 学习视频… 文章目录 前言一、整数规划和0-1规划二、典型示例1.背包问题2.指派问题 三、代码实现----Matlab1.Matlab 的 intlinprog 函数2.Matlab 代码背包问题指派问题 四、代码实现----python背包问题指派问题 总结 前言
通过模型算法熟练对Matlab和python的应用。 学习视频链接 https://www.bilibili.com/video/BV1EK41187QF?p26vd_source67471d3a1b4f517b7a7964093e62f7e6
一、整数规划和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.,i1,2,\ldots,10 记xi{1,运送了第i件货物0,没有运送第i件货物,i1,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_{i1}^{10}p_ix_i\end{aligned}\\s.t.\begin{cases}\sum_{i1}^{10}w_ix_i\leq30\\x_i\in\{0,1\}\end{cases} maxi1∑10pixis.t.{∑i110wixi≤30xi∈{0,1}
2.指派问题 已知5名游泳候选人的百米成绩怎么选拔队员组成 4×100 米混合泳接力队伍 表中的数据是各运动员百米游泳的耗时 候选人 i 1 , 2 , 3 , 4 , 5 i 1,2,3,4,5 i1,2,3,4,5 泳姿 j 1 , 2 , 3 , 4 j 1,2,3,4 j1,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_{j1}^{4}\sum_{i1}^{5}t_{ij}x_{ij}\end{aligned}\\[1em]\\s.I.\begin{cases}\sum_{j1}^{4}x_{ij}\leq1,i1,2,3,4,5\text{(每个人只能入选4种泳姿之一)}\\[0em]\\\sum_{i1}^{5}x_{ij}1,2,3,4\text{(每种泳姿有且仅有1人参加)}\\[0em]\\x_{ij}\in\{0,1\}\end{cases} minj1∑4i1∑5tijxijs.I.⎩ ⎨ ⎧∑j14xij≤1,i1,2,3,4,5∑i15xij1,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问题这些库提供了类似的功能
PuLPORToolsGurobiCVXPY
本文选用 PuLP 库求解
背包问题
# 背包问题
import pulp
import numpy as np# 定义问题规模
# 变量数
n_variables 10
# 限制条件数
n_constraints 1# 创建问题实例
prob pulp.LpProblem(BinaryVectorLP, pulp.LpMaximize)# 创建0-1变量向量
x [pulp.LpVariable(fx{i}, catBinary) 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]), fConstraint_{01}# 求解
prob.solve()# 输出结果
print(Status:, pulp.LpStatus[prob.status])
for i in range(n_variables):print(fx{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(fx{i}, catBinary) 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]), fConstraint_{i1}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]), fConstraint_{i6}# 求解
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(fx{i} , pulp.value(x[i]))
print(Objective , pulp.value(prob.objective))
res res.reshape((5,4))
print(res)运行结果 总结
本文介绍了整数规划和0-1规划并通过背包问题和指派问题两个典型示例建立模型分别使用Matlab和python进行代码编写。
