数学模型：Python实现整数规划

上篇文章：线性规划
文章摘要：整数规划的Python实现。
参考书籍：数学建模算法与应用(第3版)司守奎 孙玺菁。
PS：只涉及了具体实现并不涉及底层理论。学习底层理论以及底层理论实现：可以参考1.最优化模型与算法——基于Python实现 渐令 粱锡军2.算法导论(原书第3版)Thomas H.Cormen Charles E.Leiserson、Ronald L.Rivest Clifford Stein
文章声明：如有发现错误，还望批评指正。

整数规划简述

目标函数：
$\max or\min y=\sum _{i=1}^n{a}_i{x}_i$

约束条件：
$\sum _{j=1}^n{a}_{ij}{x}_j\le or=or\ge b_i,i=1,2,\dots ,m$
$x_j\ge 0，j=1,2,\dots ,n$
$x_j,j=1,2,\dots ,n$中部分或者全部取整

整数规划典例

标准指派问题

参考书籍例2.6
目标函数：
$\min z=\sum _{i=1}^4\sum _{j=1}^5{c}_{ij}{x}_{ij}$
约束条件：
$\sum _{i=1}^4{x}_{ij}=1,j=1,2,\dots ,5$
$\sum _{j=1}^5{x}_{ij}\le 2,i=1,2,\dots ,4$
$x_{ij}=0$或者$1$

import numpy as np
c=np.array([[15,13.8,12.5,11,14.3],[14.5,14,13.2,10.5,15],[13.8,13,12.8,11.3,14.6],[14.7,13.6,13,11.6,14]])
import cvxpy as cp
x=cp.Variable((4,5),integer=True)
obj=cp.Minimize(cp.sum(cp.multiply(c,x)))
con=[0<=x,1>=x,cp.sum(x,axis=0)==1,cp.sum(x,axis=1)<=2]
pro=cp.Problem(obj,con)
pro.solve(solver=cp.GLPK_MI)
print(x.value)
1
2
3
4
5
6
7
8
9

结果如下：

注释：ECOS用于解决凸优化问题，GLPK_MI是用于解决各种问题的优化器(离散或者连续变量，线性或者非线性的目标函数)。具体如何实现我自然不知拉。还得等学了最优化。

比赛项目排序问题

参考书籍1例2.10。数据，超链。提取码8848.
目标函数：
$\min y=\sum _{i=1}^{15}\sum _{j=1}^{15}{w}_{ij}{x}_{ij}$
约束条件：
$\sum _{j=1}^{15}{x}_{ij}=1,i=1,2,\dots ,15$
$\sum _{i=1}^{15}{x}_{ij}=1,j=1,2,\dots ,15$
$u_i-u_j+15x_{ij}<=14,i=1,2,\dots ,15,j=2,3,\dots ,15$
$u_1=0,1\le u_i\le 14,i=2,3,\dots ,15$
$x_{ij}=0$或者$1,i,j=1,2,\dots ,15$

import pandas as pd
data=pd.read_excel("data.xlsx",header=None).fillna(0).values
import numpy as np
n=data.shape[1];w=np.zeros((n+1,n+1))
for i in range(n):
    for j in range(n):
        w[i,j]=sum(data[:,i]*data[:,j])
import cvxpy as cp
x=cp.Variable((n+1,n+1),integer=True)
obj=cp.Minimize(cp.sum(cp.multiply(w,x)))
u=cp.Variable(n+1,integer=True)
con=[cp.sum(x,axis=0)==1,cp.sum(x,axis=1)==1,x>=0,x<=1,u[0]==0,u[1:]>=1,u[1:]<=n+1]
for i in range(n+1):
    for j in range(1,n+1):
        con.append(u[i]-u[j]+(n+1)*x[i,j]<=n)
pro=cp.Problem(obj,con)
pro.solve(solver=cp.GLPK_MI)
print(x.value)
print(pro.value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

下篇文章：非线性规划