Excel规划求解示例 - 上架商品利润最大化

一. 前言

在Excel规划求解加载项 | Lian (kyouichirou.github.io)一文, 使用规划求解加载项进行了简单的演示, 这里使用一个稍微复杂的示例来看看excel的求解器是否可以实现.

二. 问题

构造一个商店上架商品的模拟数据:

店铺的货架数量是有限的.

这个假想场景: 商店销售商品时需要考虑利润的同时, 还需要考虑到各种生活必需品必须满足消费者的需要(例如饮用水, 纸巾等); 以及品牌方强制上架要求的商品.

为上述的问题建立数学模型:

$\max\; z = \sum_{i = 1}^n x_ip_i\\ s.t = \begin{cases} 商品是否强制选中:\\ y_i = \begin{cases} 0,\\ 1 \end{cases}, j = 0, ..., 5\\ 强制选中和普通商品的最低要求:\\ \sum_{j= 0}^n x_{i} >= y_i\\ \\ 每个品类最少需要的选中的, 即该品类上架数必须 >= 1:\\ \sum_{j=0}^m\sum_{i = 1} ^ n x_{ji} >= 1,\; m = 0, ..., 5\\ \\ 货架的限制:\\ \sum_{i = 1} ^ n x_i s_i <= 1000\\ m: 产品的类目 \end{cases}\\$

三. 求解

实际的求解也并不困难, 主要是增加了一个品类的约束

# 利润, 目标函数
=SUMPRODUCT(C2:C17, F2:F17)

# 货架的使用, 约束
=SUMPRODUCT(D2:D17, F2:F17)

创建辅助列:

对每个品类相同的产品进行求和.

=SUMIF(B2:B17,I2:I7, F2:F17)

进一步延申, 通过调节最低上架数量, 利润等参数, 将可以看到在不同组合模式下, 整体利润和货架的使用变动情况, 而构建出最有的决策.

四. Python求解

使用Google的ortools.

from ortools.linear_solver import pywraplp

N = 16
n = 6
matrix = [
    [0,7,4,1],
    [0,8,6,0],
    [1,3,1,1],
    [1,2,1,0],
    [2,5,2,1],
    [2,5,3,1],
    [3,8,5,0],
    [3,2,1,1],
    [3,8,6,1],
    [3,2,1,1],
    [4,8,5,1],
    [4,4,2,1],
    [4,1,1,1],
    [4,5,3,0],
    [5,1,1,0],
    [5,6,3,0]
]

solver = pywraplp.Solver.CreateSolver('SCIP')

variables = {}
for i in range(N):
    j = matrix[i][0]
    y = 1 if matrix[i][3] > 0 else 0
    variables[j, i] = solver.IntVar(y, 1000, f'x_{j}_{i}')

for j in range(n):
    data = []
    for i in range(N):
        if variables.get((j, i)):
            data.append((j, i))

    if len(data) > 0:
        constrain = sum((variables[key] for key in data)) >= 1
        solver.Add(constrain)
    else: print('err')

constrain = sum((variables[j, i] * matrix[i][2] for (j, i) in variables.keys())) <= 1000
solver.Add(constrain)

solver.Maximize(sum((variables[j, i] * matrix[i][1] for (j, i) in variables.keys())))

status = solver.Solve()
0

solver.Objective().Value()
2950

for key in variables.keys():
    print(variables[key].solution_value())

1.0
0.0
974.0
0.0
1.0
1.0
0.0
1.0
1.0
1.0
1.0
1.0
1.0
0.0
1.0
0.0

五. 小结

对于很多的线性/非线性规划问题, Excel规划求解组件还是很好用的.

但比较令人遗憾, 由于该组件并不是微软所提供, Excel Solver Online Help | solver, 这个求解器的功能非常有限, 需要实现更为复杂功能, 就需要从该站点购买单独求解器组件.

例如: 尝试一个更复杂的求解: 数独求解

由于需要循环创建大量约束, 故此需要在VBA上调用该求解器来实现:

首先, 在引用中勾选solver

Sub sudoku_test()
    Const N As Integer = 9, M As Integer = 3
    Dim r As Integer, c As Integer, i As Integer, j As Integer

    '重置求解器'
    SolverReset

    '设置求解器目标等 '
    SolverOk MaxMinVal:=0, ValueOf:=0, ByChange:="$A$1:$I$9", Engine:=1, EngineDesc _
        :="GRG Nonlinear"
    ' 整体约束 --------
    ' 整数约束
    SolverAdd CellRef:="$A$1:$I$9", Relation:=4, FormulaText:="整数"

    ' 数字约束,  大于等于1
    SolverAdd CellRef:="$A$1:$I$9", Relation:=3, FormulaText:="1"

    ' 数字约束,  小于等于9
    SolverAdd CellRef:="$A$1:$I$9", Relation:=1, FormulaText:="9"

    ' ------   整体约束

    ' 已经填入的数字约束, 这部分的约束和AllDifferent冲突
    For r = 1 To N
        For c = 1 To N
            i = Cells(r, c).Value
            If i > 0 Then
                SolverAdd CellRef:=Range(Cells(r, c), Cells(r, c)), Relation:=2, FormulaText:=CStr(i)
            End If
        Next
    Next

    ' 行约束
    For r = 1 To N
        SolverAdd CellRef:=Range(Cells(r, 1), Cells(r, 9)), Relation:=6, FormulaText:="AllDifferent"
    Next

    ' 列约束
    For c = 1 To N
        SolverAdd CellRef:=Range(Cells(1, c), Cells(9, c)), Relation:=6, FormulaText:="AllDifferent"

    Next

    ' 小宫格约束
    i = 1
    j = 1
    For r = 1 To M
        For c = 1 To M
            SolverAdd CellRef:=Range(Cells(i, j), Cells(i + 2, j + 2)), Relation:=6, FormulaText:="AllDifferent"
            j = j + 3
        Next
        i = i + 3
        j = 1
    Next

    SolverSolve
End Sub

通过AllDifferent类型约束貌似可以轻易解析数独, 但是令人遗憾, AllDifferent设置约束后, 无法对决策变量进行再次约束, 即已经填入数字约束部分无法实现.

Excel Solver - How Integer, Binary and Alldifferent constraints affect solving | solver

使用 Solver VBA 函数 | Microsoft Learn

该约束只能用于一些简单的计算:

实现行列求和相等, 同时行列元素要求行列皆不相同.

数据分析, 规划求解, 不应该忽视这两个高阶组件的存在, 对于大部分的分析/建模需求, excel是可以实现一站式服务的. 再配上power query & dax, excel这把瑞士军刀还是兼具便利和锋利的数据利器.