700字范文 > Python数学建模系列（二）：规划问题之整数规划

Python数学建模系列（二）：规划问题之整数规划

时间：2019-02-17 00:26:37

文章目录

前言整数规划例题方法一：分支定界法（使用scipy库）方法二：使用pulp库进行求解结语

前言

Hello！小伙伴！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
自我介绍ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，有幸拿过一些国奖、省奖…已保研。目前正在学习C++/Linux/Python
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
初学Python 小白阶段
文章仅作为自己的学习笔记用于知识体系建立以及复习
题不在多学一题懂一题
知其然知其所以然！
本文仅从Pyhton如何解决建模问题出发
未对建模思路等进行深一步探索

整数规划

整数规划的模型与线性规划基本相同，只是额外增加了部分变量为整数的约束

整数规划求解的基本框架是分支定界法，首先去除整数约束得到"松弛模型"。使用线性规划的方法求解。

若有某个变量不是整数，在松弛模型.上分别添加约束:x≤floor(A)和x≥ceil(A)，然后再分别求解，这个过程叫做分支。当节点求解结果中所有变量都是整数时。停止分支。这样不断迭代，形成了一颗树。

所谓定界，指的是叶子节点产生后，相当于给问题定了一个下界。之后在求解过程中一旦某个节点的目标函数值小于这个下界，那就直接pass,不再进行分支了;每次新产生叶子节点，则更新下界。

例题

求minz=3x1+4x2+x3min \quad z = 3x_1 + 4x_2 + x_3minz=3x1+4x2+x3 的最小值

minz=3x1+4x2+x3s.t.={x1+6x2+2x3>=52x1>=3x1,x2,x3>=0(且都为整数)min \quad z = 3x_1 + 4x_2 + x_3\\ s.t. = \begin{cases} x_1 + 6x_2 + 2x_3 >= 5 \\ 2x_1 >= 3\\ x_1,x_2,x_3 >=0(且都为整数) \end{cases} minz=3x1+4x2+x3s.t.=⎩⎪⎨⎪⎧x1+6x2+2x3>=52x1>=3x1,x2,x3>=0(且都为整数)

方法一：分支定界法（使用scipy库）

Demo代码

# 运行环境：Vs Codeimport mathfrom scipy.optimize import linprogimport sysdef integerPro(c, A, b, Aeq, beq,t=1.0E-8):res = linprog(c, A_ub=A, b_ub=b, A_eq=Aeq, b_eq=beq)bestVal = sys.maxsizebestX = res.xif not(type(res.x) is float or res.status != 0): bestVal = sum([x*y for x,y in zip(c, bestX)])if all(((x-math.floor(x))<=t or (math.ceil(x)-x)<=t) for x in bestX):return (bestVal,bestX)else:ind = [i for i, x in enumerate(bestX) if (x-math.floor(x))>t and (math.ceil(x)-x)>t][0]newCon1 = [0]*len(A[0])newCon2 = [0]*len(A[0])newCon1[ind] = -1newCon2[ind] = 1newA1 = A.copy()newA2 = A.copy()newA1.append(newCon1)newA2.append(newCon2)newB1 = b.copy()newB2 = b.copy()newB1.append(-math.ceil(bestX[ind]))newB2.append(math.floor(bestX[ind]))r1 = integerPro(c, newA1, newB1, Aeq, beq)r2 = integerPro(c, newA2, newB2, Aeq, beq)if r1[0] < r2[0]:return r1else:return r2c = [3,4,1]A = [[-1,-6,-2],[-2,0,0]]b = [-5,-3]Aeq = [[0,0,0]]beq = [0]print(integerPro(c, A, b, Aeq, beq))

运行结果

(8.000000000001586, array([2., 0., 2.]))# 或者(8.000000000001586, array([2.00000000e+00, 1.83247535e-13, 2.00000000e+00]))

方法二：使用pulp库进行求解

只需要在设置变量的时候

设置参数cat='Integer'即可

Continuous：连续Binary：0 或 1Integer：整数

Demo代码

import pulp as pp# 参数设置c = [3,4,1] #目标函数未知数前的系数A_gq = [[1,6,2],[2,0,0]] # 大于等于式子未知数前的系数集合二维数组 b_gq = [5,3] # 大于等于式子右边的数值一维数组# 确定最大最小化问题，当前确定的是最小化问题m = pp.LpProblem(sense=pp.LpMinimize)# 定义三个变量放到列表中生成x1 x2 x3x = [pp.LpVariable(f'x{i}',lowBound=0,cat='Integer') for i in [1,2,3]]# 定义目标函数，并将目标函数加入求解的问题中 m += pp.lpDot(c,x) # lpDot 用于计算点积 # 设置比较条件for i in range(len(A_gq)):# 大于等于m += (pp.lpDot(A_gq[i],x) >= b_gq[i])# 求解m.solve()# 输出结果print(f'优化结果：{pp.value(m.objective)}')print(f'参数取值：{[pp.value(var) for var in x]}')

运行结果

优化结果：8.0参数取值：[2.0, 0.0, 2.0]