规划求解 - 单纯形

一. 前言

问题并不复杂, 只是借此机会顺便搞一下excel的规划求解器, 看看能不能让这个组件还能在2019及以上版本的64位excel中使用.

问题来源于广告书.

二. 问题解析

直观的数学模型\\ x, y, z, 分别为甲乙丙三种产品的产量\\ a_{i}, b_{i}, c_{i}分别为A, B, C三种产品的含量\\ \\ 目标函数, max: 2.9 * x + 2.45 * y + 1.95 * z - (2 * (a_1 * x + a_2 *y + a_3 * z) - 1.5 * (b_1 * x + b_2 *y + b_3 * z) - 1 *(c_1 * x + c_2 *y + c_3 * z))\\ \\ x * a_1 + a_2 * y + a_3 * z \leq 2000 \\ x * c_1 + y * c_2 + z * c_3 \leq 1200 \\ x * b_1 + y * b_2 + z * b_3 \leq 2500 \\ a_1 + b_1 + c_1 = 1 \\ a_2 + b_2 + c_3 = 1 \\ a_3 + b_3 + c_3 = 1 \\ a_1 \geq 0.6\\ a_2 \geq 0.15\\ c_1 \leq 0.2\\ c_2 \leq 0.6\\ c_3 \leq 0.5 \\

这是个非线性模型, 需要转换为线性模型.

【教学视频】优化 | 线性化(2): 连续变量 * 0-1变量的线性化

非线性如何线性化? - 知乎

$$ x * a_1 = x_{1, 1} \\ 其余的类似操作\\ 转换后:\\ \sum_{j = 1}^{3} x_{1, j} \leq 2000 \\ \sum_{j = 1}^{3} x_{2, j} \leq 2500 \\ \sum_{j = 1}^{3} x_{3, j} \leq 1200 \\ \\ 0.6 * (\sum_{i = 1}^{3}x_{i, 1}) \leq x_{11} \\ 0.15 * (\sum_{i = 1}^{3} x_{i, 2}) \leq x_{12} \\ 0.2 * (\sum_{i = 1}^{3} x_{i, 1}) \geq x_{31} \\ 0.6 * (\sum_{i = 1}^{3} x_{i, 2}) \geq x_{32} \\ 0.5 * (\sum_{i = 1}^{3} x_{i, 3}) \geq x_{33} \\ \\ 则目标函数: max = 2.9 * \sum_{i = 1}^ 3 x_{i, 1} + 2.45 * \sum_{i = 1}^ 3 x_{i, 2} + 1.95 * \sum_{i = 1}^ 3 x_{i, 3} - 2 * \sum_{j = 1}^ 3 x_{1, j} - 1.5 * \sum_{j = 1}^ 3 x_{2, j} - 1 * \sum_{j = 1}^ 3 x_{3, j} \\ x_{i, j} \geq 0; i, j \in [1,2,3] $$ 至此, 模型构建完成.

三. 问题的求解

3.1 Excel

excel预置的规划求解器最后能在64位上使用的是2016版, 之后的版本只能在32位上使用.

需要注意的是预置版本为封闭的商业软件, 不可修改, 提供商为: Excel Solver Online Help | solver

有个第三方的开源求解器组件:

OpenSolver for Excel – The Open Source Optimization Solver for Excel

但可惜的是也不继续更新了, 应该和预置版本类似, 都是只能在2016版(64bit)下使用.

还有个对求解器进行优化的dll, host.kelley.iu.edu/albrightbooks/solver.htm

求解没什么好说的, 相关内容见: Excel规划求解加载项 | Lian

	1	2
1	1526.666667	473.3333333	2000
2	508.8888889	1991.111111	2500
3	508.8888889	691.1111111	1200
	2544.444444	3155.555556	target:	6160

3.2 ortools

求解并不困难, 对着数学模型敲击即可, 基本上数学模型和代码是互通的.

使用约束求解器来处理.

from ortools.sat.python import cp_model

model = cp_model.CpModel()
solver = cp_model.CpSolver()

variables = {}
for i in range(1, 4):
    for j in range(1, 4):
        variables[(i, j)] = model.NewIntVar(0, 2500, "x%i_%i" % (i, j))

model.add(sum(variables[(1, j)] for j in range(1, 4)) <= 2000)
model.add(sum(variables[(2, j)] for j in range(1, 4)) <= 2500)
model.add(sum(variables[(3, j)] for j in range(1, 4)) <= 1200)

# 在运算中, 减少浮点数带来的精度丢失问题

model.add(60 * sum(variables[(i, 1)] for i in range(1, 4)) <= 100 * variables[(1, 1)]) # 数据缩放, x100
model.add(15 * sum(variables[(i, 2)] for i in range(1, 4)) <= 100 * variables[(1, 2)])

model.add(20 * sum(variables[(i, 1)] for i in range(1, 4)) >= 100 * variables[(3, 1)])
model.add(60 * sum(variables[(i, 2)] for i in range(1, 4)) >= 100 * variables[(3, 2)])
model.add(50 * sum(variables[(i, 3)] for i in range(1, 4)) >= 100 * variables[(3, 3)])

# 数据缩放, x100
model.Maximize(
    290 * sum(variables[(i, 1)] for i in range(1, 4))
    + 245 * sum(variables[(i, 2)] for i in range(1, 4))
    + 195 * sum(variables[(i, 3)] for i in range(1, 4))
    - 200 * sum(variables[(1, j)] for j in range(1, 4))
    - 150 * sum(variables[(2, j)] for j in range(1, 4))
    - 100 * sum(variables[(3, j)] for j in range(1, 4))
)

status = solver.Solve(model)
print(status)

if status == cp_model.OPTIMAL:
    print("objective value:", solver.ObjectiveValue() / 100) # 目标值 / 100, 恢复正常数据
    print("sudoku solution:")
    results = []
    for i in range(1, 4):
        data = []
        for j in range(1, 4):
            data.append(solver.Value(variables[(i, j)]))
        results.append(' | '.join([str(x) for x in data]))
    print('\n'.join(results))

objective value: 6159.35
sudoku solution:
1526 | 474 | 0
509 | 1991 | 0
508 | 692 | 0

需要注意的是, 在涉及浮点数运算时, 为了降低浮点数精度的影响, 可以对数据进行缩放处理.

四. 小结

还是没办法让2019以上的64位版本的excel启用这个规划求解器组件.