线性规划和整数规划

文章概览

线性规划问题

线性规划问题都可以建立如下方程

$$min ~ x = 70 x_1 + 50 x_2 + 60 x_3,\\ s.t.\left \{ \begin{aligned} 2 x_1 + 4 x_2 + 3 x_3 \leq 150,\\ 3 X_1 + X_2 + 5 x_3 \leq 160,\\ 7 x_1 + 3 x_2 + 5 x_3 \leq 200,\\ x_i \geq 0, i=1,2,3. \end{aligned} \right.$$

其中第一行的 x1、x2、x3 称为决策变量。

通过 python 求解，使用 scipy 的 optimize.linprog 函数，代码如下

from scipy import optimize as op
import numpy as np

# 定义决策变量范围
x1=(0,None)                                                
x2=(0,None)
x3=(0,None)

# 定义目标函数系数
c = np.array([70, 50, 60])        

# 定义约束条件系数
a = np.array([[-2, -4, -3], [-3, -1, -5], [-7, -3, -5]])    
b = np.array([-150, -160, -200])

res=op.linprog(c,a,b,bounds=(x1,x2,x3))

print(res.x[0])

注意 optimize 函数判定约束条件统一是大于号。

投资的收益与风险

• 问题：每种股票有收益率 r 和风险 q，合理分配资金，使收益尽可能大而风险尽可能小
• 模型：定义股票购买量 $x_i$

整数规划

背包问题

• 问题：每件物品有重量 a 和价值 c，限定重量 b 内任取物品，使价值总和最大
• 模型：定义某物品是否被选取 $x_i \in {0,1}$

指派问题

• 问题：某人完成某项任务的费用为 c，分配人员完成与人数同等的任务，使费用总和最小
• 模型：定义某人是否分配到某任务 $x_{ij} \in {0,1}$

旅行商问题

• 问题：从某城市到零一城市的费用为 c，安排旅行顺序，使费用总和最小

• 模型

  c 变量表示费用，$x_{ij} \in {0,1}$ 变量表示路径是否被选择

  $$min z = \sum_{i=1}^n\sum_{j=1}^n c_{ij} x_{ij}, \\ s.t. \left\{ \begin{aligned} \sum_{i=1}^n x_{ij} = 1, j=1,2,...,n, \\ \sum_{j=1}^n x_{ij} = 1, i=1,2,...,n, \\ u_i - u_j + n x_{ij} \leq n - 1, i=1,...,n, j=2,...n, \\ u_1 = 0, 1 \leq u_i \leq n-1, i=2,...,n, \\ x_{ij} = 0或1, i,j=1,2,...,n. \end{aligned} \right.$$

  $u_i \in {1,2,…,n}$ 变量保证只有 $i<j$ 的 $x_{ij}$ 才可能为1，防止回路

比赛项目的排序问题

• 问题：每名运动员报名了比赛项目若干，安排比赛顺序，尽可能使运动员不连续参加两场比赛

• 模型：定义 $w_{ij}$ 同时参加两项目的人数和 $x_{ij} \in {0,1}$ 变量表示路径是否被选择（用类似于旅行商的模型）

多想多做，发篇一作