基于线性整数规划求解星穹铁道杯中逸事活动中原料搭配问题

问题描述与数学建模

有以下原料

设第$i$个原料属性可用向量$s_i=$<甜度，浓度，浓稠度, 1>表示，其中第四分量的单位1后续可用于约束原材料投放的最大数量限制。

1. 提纯浮羊奶: $s_1=(2,2,0,1)$
2. 椒椒博士: $s_2=(1,-1,0,1)$
3. 冰点苏乐达: $s_3=(1,-2,0,1)$
4. 安神气泡饮: $s_4=(-1,-1,0,1)$
5. 怪味浓汁: $s_5=(-2,1,0,1)$
6. 激梦果酱: $s_6=(0,2,1,1)$
7. 极致糖浆: $s_7=(0,1,2,1)$
8. 苏花清露: $s_8=(0,1,-1,1)$
9. 夕红果沙司: $s_9=(0,-1,1,1)$
10. 魔血能量: $s_{10}=(0,-1,0,1)$

记做矩阵$S$

$S= \begin{bmatrix} 2 & 2 & 0 & 1 \\ 1 & -1 & 0 & 1 \\ 1 & -2 & 0 & 1 \\ -1 & -1 & 0 & 1 \\ -2 & 1 & 0 & 1 \\ 0 & 2 & 1 & 1 \\ 0 & 1 & 2 & 1 \\ 0 & 1 & -1 & 1 \\ 0 & -1 & 1 & 1 \\ 0 & -1 & 0 & 1 \\ \end{bmatrix}$

设最终选用$x_{i}$个第$i$个原料的个数，故$x_i>=0$，并满足约束$\sum_{i=1}^{10} x_i = 4$。记$x=(x_1,x_2,...,x_{10})$。

记$b=x \cdot S = (b_1,b_2,b_3,b_4)$

由题意需要满足$b_1=-1,b_2=1,b_3<=-2,b_4=4$

求所有满足条件的向量$x$。

代码求解

import numpy as np
from pulp import *

# 创建10个决策变量
x = list(map(lambda i: LpVariable(f'x{i+1}', 0, None, LpInteger), range(10)))

# 定义整数规划问题
problem = LpProblem('lp', LpMinimize)

# 定义不等式约束
A_ub = [[0,0,0,0,0,1,2,-1,1,0]]
b_ub = [-2]
for i in range(0, len(A_ub)):
    tmp = A_ub[i][0]*x[0]
    for j in range(1, len(A_ub[i])):
        tmp = tmp + A_ub[i][j]*x[j]
    problem += tmp <= b_ub[i]

# 定义等式约束
A_eq = [
    [2,1,1,-1,-2,0,0,0,0,0],
    [2,-1,-2,-1,1,2,1,1,-1,-1],
    [1,1,1,1,1,1,1,1,1,1],
]
b_eq = [-1,1,4]
for i in range(0, len(A_eq)):
    tmp = A_eq[i][0]*x[0]
    for j in range(1, len(A_eq[i])):
        tmp = tmp + A_eq[i][j]*x[j]
    problem += tmp == b_eq[i]
# 假设价值向量均为1
c = [1,1,1,1,1,1,1,1,1,1]

# 添加目标函数
tmp = c[0]*x[0]
for j in range(1, len(c)):
    tmp = tmp + c[j]*x[j]
problem += tmp

problem.solve()

# 写入求解过程
problem.writeLP('tmp.lp')

# 打印所有的决策变量
for v in problem.variables():
    print(f'{v.name}={v.varValue}')

运行结果如下：

x1=0.0
x10=0.0
x2=0.0
x3=1.0
x4=0.0
x5=1.0
x6=0.0
x7=0.0
x8=2.0
x9=0.0

即满足条件的一种搭配如下：

• 1份冰点苏乐达
• 1份怪味浓汁
• 2份苏花清露

实际操作结果

结果证实该方案确实可行。