algorithm - 求解方程组 :

Question

我有以下问题:

f(x) 定义为 f1(x) 在 0 到 10 之间，f2(x) 在 10 到 20 之间，否则为 0。 f(x)在0到20之间的积分需要大于等于一个值K。

g(x) 定义为 g1(x) 介于 0 和 5 之间，g2(x) 介于 5 和 20 之间，否则为 0。 g(x)在0到20之间的积分需要大于等于一个值Q。

对于任何x，f(x)和g(x)之和不能超过一个值R。

我假设它背后有相当复杂的理论，并且想知道是否有人可以指出正确的方向来设计一种可以生成 f1(x)、f2(x)、g1(x) 和 g2( x)?

编辑:我想补充一点，对于给定的 K 和 Q，兴趣是使 R 尽可能低。

谢谢:)

Answer 1

从陈述问题的方式来看，我假设 f1(x)、f2(x)、g1(x) 和 g2(x) 是(非负)常数函数。那么这是一个linear programming (LP) 问题，例如可以使用 simplex algorithm 来解决.

用 LP 问题表示的问题是:

10*x1 + 10*x2 >= K
5*x3 + 15*x4 >= Q
x1 + x3 <= R
x1 + x4 <= R
x2 + x4 <= R

Variables: x1, x2, x3, x4, R
Minimize R

您可以自己实现 LP 求解器，也可以使用现有的库或工具。例如，使用 GNU 线性规划工具包 (GLPK) 解决 K=23 和 Q=42 的问题:

var x1;
var x2;
var x3;
var x4;
var R;

s.t. rel1: 10*x1 + 10*x2 >= 23;
s.t. rel2: 5*x3 + 15*x4 >= 42;
s.t. rel3: x1 + x3 <= R;
s.t. rel4: x1 + x4 <= R;
s.t. rel5: x2 + x4 <= R;

minimize obj: R;

solve;

printf "Result: %f %f %f %f %f\n", x1, x2, x3, x4, R;

end;

用 glpsol --math q22883102.mod 执行:

...
Result: 1.150000 1.150000 2.100000 2.100000 3.250000

PS:这个特殊问题总是产生 x1 = x2 = K/20 和 x3 = x4 = Q/20，因此对于 LP 来说似乎有点轻量级。但我想问题更多的是关于这类问题，而不是这个特定问题。