问题描述与数学建模

有以下原料

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

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

记做矩阵SS

S=[22011−1011−201−1−101−21010211012101−110−1110−101]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}

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

记b=x⋅S=(b1,b2,b3,b4)b=x \cdot S = (b_1,b_2,b_3,b_4)

由题意需要满足b1=−1,b2=1,b3<=−2,b4=4b_1=-1,b_2=1,b_3<=-2,b_4=4

求所有满足条件的向量xx。

代码求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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}')

运行结果如下：

1
2
3
4
5
6
7
8
9
10
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份苏花清露

实际操作结果

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

另一个问题

若b=(1,−1,−1,4)b=(1,-1,-1,4)，则问题实际上转化为了求解线性方程组的解集问题。

[211−1−2000002−1−2−11211−1−10000012−1101111111111]⋅x=[1−1−14] \begin{bmatrix} 2 & 1 & 1 & -1 & -2 & 0 & 0 & 0 & 0 & 0 \\ 2 & -1 & -2 & -1 & 1 & 2 & 1 & 1 & -1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 2 & -1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix} \cdot x =\begin{bmatrix} 1 \\ -1 \\ -1 \\ 4 \\ \end{bmatrix}

且x>=0x>=0