网站建设添加视频,凡科建站后台登录,网站营销是什么意思,烟台优化网站排名本文章为上篇建模学习打卡第二天的续
文章目录
一、本次问题 二、本题理解
三、问题求解
1.lingo实现
#xff08;1#xff09;先抛除整数约束条件对问题求解 #xff08;2#xff09;加入整数约束条件求解
2.python实现求解
#xff08;1#xff09;先抛除整数约…本文章为上篇建模学习打卡第二天的续
文章目录
一、本次问题 二、本题理解
三、问题求解
1.lingo实现
1先抛除整数约束条件对问题求解 2加入整数约束条件求解
2.python实现求解
1先抛除整数约束条件对问题求解 2加入整数约束条件求解实现 通过 pulp 库求解 3加入整数约束条件求解实现 分枝界定法求解 一、本次问题 二、本题理解
目标函数
max 40x190x2
一级约束条件
9x17x256
7x120x270
x1,x2 0
二级约束条件
x1x2全为整数
三、问题求解
1.lingo实现
lingo编写代码时每行代码结束后必须以 ‘ ; ’ 结束否则无法运行。
1先抛除整数约束条件对问题求解
基础线性规划实现matlablingo_菜菜笨小孩的博客-CSDN博客 lingo代码实现l无其他条件下ingo中默认变量大于等于0
max 40*x190*x2;
9*x17*x256;
7*x120*x270; 结果最优解 x14.80916 , x2 1.816794 ; 最优值为355.8779显然不符合题意 2加入整数约束条件求解
首先需要引出lingo的变量界定函数 gin(x) --- 将x限制为整数条件 ingo代码实现:通过变量界定函数将x1x2限制为整数约束
max 40*x190*x2;
9*x17*x256;
7*x120*x270;
gin(x1);
gin(x2); 结果最优解 x14 , x2 2 ; 最优值为340符合题意 lingo实现求解到此结束。
2.python实现求解 1先抛除整数约束条件对问题求解
基础线性规划实现---python_菜菜笨小孩的博客-CSDN博客 python代码实现如下详解请看上方python基础线性规划的文章
#导入包
from scipy import optimize as opt
import numpy as np#确定c,A,b,Aeq,beq
c np.array([40,90]) #目标函数变量系数
A np.array([[9,7],[7,20]]) #不等式变量系数
b np.array([56,70]) #不等式变量值
Aeq np.array([[0,0]]) #等式变量系数
beq np.array([0]) #等式变量值
#限制
lim1(0,None)
lim2(0,None)
#求解
res opt.linprog(-c,A,b,Aeq,beq,bounds(lim1,lim2))
#输出结果
print(res) 结果最优解 x14.80916 , x2 1.816794 ; 最优值为355.8779显然不符合题意 2加入整数约束条件求解实现 通过 pulp 库求解
安装库我用python3.8安装成功了
pip install pulp
python代码实现
1.导入库
import pulp as pulp
2.定义解决问题的函数
def solve_ilp(objective , constraints) :print(objective)print(constraints)prob pulp.LpProblem(LP1 , pulp.LpMaximize)prob objectivefor cons in constraints :prob consprint(prob)status prob.solve()if status ! 1 :return Noneelse :return [v.varValue.real for v in prob.variables()]
3.设置目标函数和约束条件等
V_NUM 2 #本题变量个数
# 变量直接设置下限
variables [pulp.LpVariable(X%d % i, lowBound0, catpulp.LpInteger) for i in range(0, V_NUM)]
# 目标函数
c [40, 90]
objective sum([c[i] * variables[i] for i in range(0, V_NUM)])
# 约束条件
constraints []
a1 [9, 7]
constraints.append(sum([a1[i] * variables[i] for i in range(0, V_NUM)]) 56)
a2 [7, 20]
constraints.append(sum([a2[i] * variables[i] for i in range(0, V_NUM)]) 70)4.求解
res solve_ilp(objective, constraints)
print(res) #输出结果
完整代码如下
# -*- coding: utf-8 -*-
import pulp as pulpdef solve_ilp(objective, constraints):print(objective)print(constraints)prob pulp.LpProblem(LP1, pulp.LpMaximize)prob objectivefor cons in constraints:prob consprint(prob)status prob.solve()if status ! 1:# print status# print statusreturn Noneelse:# return [v.varValue.real for v in prob.variables()]return [v.varValue.real for v in prob.variables()]V_NUM 2
# 变量直接设置下限
variables [pulp.LpVariable(X%d % i, lowBound0, catpulp.LpInteger) for i in range(0, V_NUM)]
# 目标函数
c [40, 90]
objective sum([c[i] * variables[i] for i in range(0, V_NUM)])
# 约束条件
constraints []
a1 [9, 7]
constraints.append(sum([a1[i] * variables[i] for i in range(0, V_NUM)]) 56)
a2 [7, 20]
constraints.append(sum([a2[i] * variables[i] for i in range(0, V_NUM)]) 70)
# print (constraints)res solve_ilp(objective, constraints)
print(res) #输出解结果最优解 x14 , x2 2 ; 最优值为340符合题意 3加入整数约束条件求解实现 分枝界定法求解
何为分枝界定法请看详解https://blog.csdn.net/qq_25990967/article/details/121211474
python代码实现
1.导入库
from scipy.optimize import linprog
import numpy as np
import math
import sys
from queue import Queue
2.定义整数线性规划类
class ILP()
3.定义分枝界定法函数
def __init__(self, c, A_ub, b_ub, A_eq, b_eq, bounds):# 全局参数self.LOWER_BOUND -sys.maxsizeself.UPPER_BOUND sys.maxsizeself.opt_val Noneself.opt_x Noneself.Q Queue()# 这些参数在每轮计算中都不会改变self.c -cself.A_eq A_eqself.b_eq b_eqself.bounds bounds# 首先计算一下初始问题r linprog(-c, A_ub, b_ub, A_eq, b_eq, bounds)# 若最初问题线性不可解if not r.success:raise ValueError(Not a feasible problem!)# 将解和约束参数放入队列self.Q.put((r, A_ub, b_ub))def solve(self):while not self.Q.empty():# 取出当前问题res, A_ub, b_ub self.Q.get(blockFalse)# 当前最优值小于总下界则排除此区域if -res.fun self.LOWER_BOUND:continue# 若结果 x 中全为整数则尝试更新全局下界、全局最优值和最优解if all(list(map(lambda f: f.is_integer(), res.x))):if self.LOWER_BOUND -res.fun:self.LOWER_BOUND -res.funif self.opt_val is None or self.opt_val -res.fun:self.opt_val -res.funself.opt_x res.xcontinue# 进行分枝else:# 寻找 x 中第一个不是整数的取其下标 idxidx 0for i, x in enumerate(res.x):if not x.is_integer():breakidx 1# 构建新的约束条件分割new_con1 np.zeros(A_ub.shape[1])new_con1[idx] -1new_con2 np.zeros(A_ub.shape[1])new_con2[idx] 1new_A_ub1 np.insert(A_ub, A_ub.shape[0], new_con1, axis0)new_A_ub2 np.insert(A_ub, A_ub.shape[0], new_con2, axis0)new_b_ub1 np.insert(b_ub, b_ub.shape[0], -math.ceil(res.x[idx]), axis0)new_b_ub2 np.insert(b_ub, b_ub.shape[0], math.floor(res.x[idx]), axis0)# 将新约束条件加入队列先加最优值大的那一支r1 linprog(self.c, new_A_ub1, new_b_ub1, self.A_eq,self.b_eq, self.bounds)r2 linprog(self.c, new_A_ub2, new_b_ub2, self.A_eq,self.b_eq, self.bounds)if not r1.success and r2.success:self.Q.put((r2, new_A_ub2, new_b_ub2))elif not r2.success and r1.success:self.Q.put((r1, new_A_ub1, new_b_ub1))elif r1.success and r2.success:if -r1.fun -r2.fun:self.Q.put((r1, new_A_ub1, new_b_ub1))self.Q.put((r2, new_A_ub2, new_b_ub2))else:self.Q.put((r2, new_A_ub2, new_b_ub2))self.Q.put((r1, new_A_ub1, new_b_ub1))
4.定义求解问题中的变量级约束条件
def test(): 此测试的真实最优解为 [4, 2] c np.array([40, 90])A np.array([[9, 7], [7, 20]])b np.array([56, 70])Aeq Nonebeq Nonebounds [(0, None), (0, None)]solver ILP(c, A, b, Aeq, beq, bounds)solver.solve()print(Test s result:, solver.opt_val, solver.opt_x)print(Test s true optimal x: [4, 2]\n)
5.求解并输出
if __name__ __main__:test()
完整代码如下
from scipy.optimize import linprog
import numpy as np
import math
import sys
from queue import Queueclass ILP():def __init__(self, c, A_ub, b_ub, A_eq, b_eq, bounds):# 全局参数self.LOWER_BOUND -sys.maxsizeself.UPPER_BOUND sys.maxsizeself.opt_val Noneself.opt_x Noneself.Q Queue()# 这些参数在每轮计算中都不会改变self.c -cself.A_eq A_eqself.b_eq b_eqself.bounds bounds# 首先计算一下初始问题r linprog(-c, A_ub, b_ub, A_eq, b_eq, bounds)# 若最初问题线性不可解if not r.success:raise ValueError(Not a feasible problem!)# 将解和约束参数放入队列self.Q.put((r, A_ub, b_ub))def solve(self):while not self.Q.empty():# 取出当前问题res, A_ub, b_ub self.Q.get(blockFalse)# 当前最优值小于总下界则排除此区域if -res.fun self.LOWER_BOUND:continue# 若结果 x 中全为整数则尝试更新全局下界、全局最优值和最优解if all(list(map(lambda f: f.is_integer(), res.x))):if self.LOWER_BOUND -res.fun:self.LOWER_BOUND -res.funif self.opt_val is None or self.opt_val -res.fun:self.opt_val -res.funself.opt_x res.xcontinue# 进行分枝else:# 寻找 x 中第一个不是整数的取其下标 idxidx 0for i, x in enumerate(res.x):if not x.is_integer():breakidx 1# 构建新的约束条件分割new_con1 np.zeros(A_ub.shape[1])new_con1[idx] -1new_con2 np.zeros(A_ub.shape[1])new_con2[idx] 1new_A_ub1 np.insert(A_ub, A_ub.shape[0], new_con1, axis0)new_A_ub2 np.insert(A_ub, A_ub.shape[0], new_con2, axis0)new_b_ub1 np.insert(b_ub, b_ub.shape[0], -math.ceil(res.x[idx]), axis0)new_b_ub2 np.insert(b_ub, b_ub.shape[0], math.floor(res.x[idx]), axis0)# 将新约束条件加入队列先加最优值大的那一支r1 linprog(self.c, new_A_ub1, new_b_ub1, self.A_eq,self.b_eq, self.bounds)r2 linprog(self.c, new_A_ub2, new_b_ub2, self.A_eq,self.b_eq, self.bounds)if not r1.success and r2.success:self.Q.put((r2, new_A_ub2, new_b_ub2))elif not r2.success and r1.success:self.Q.put((r1, new_A_ub1, new_b_ub1))elif r1.success and r2.success:if -r1.fun -r2.fun:self.Q.put((r1, new_A_ub1, new_b_ub1))self.Q.put((r2, new_A_ub2, new_b_ub2))else:self.Q.put((r2, new_A_ub2, new_b_ub2))self.Q.put((r1, new_A_ub1, new_b_ub1))def test(): 此测试的真实最优解为 [4, 2] c np.array([40, 90])A np.array([[9, 7], [7, 20]])b np.array([56, 70])Aeq Nonebeq Nonebounds [(0, None), (0, None)]solver ILP(c, A, b, Aeq, beq, bounds)solver.solve()print(Test s result:, solver.opt_val, solver.opt_x)print(Test s true optimal x: [4, 2]\n)if __name__ __main__:test()结果最优解 x14 , x2 2 ; 最优值为340符合题意
