在Matlab中获得满足线性方程式的一个答案的最佳方法 [英] best way to obtain one answer that satisfy a linear equation in matlab

问题描述

我有一个线性方程:

vt = v1*x1 + v2*x2 + v3*x3

vt，v1，v2，v3是标量，其值在0到1之间.什么是生成满足上面的等式的x1，x2和x3的集合(任何集合都可以)的最佳方法.并且满足

vt, v1, v2, v3 are scalars with values between 0 and 1. What is the best way to generate one set (any set will be fine) of x1, x2 and x3 that satisfy the equation above. and also satisfy

x1>0
x2>0
x3>0

我有两千套vt，v1，v2和v3，因此我需要能够以编程方式生成x1，x2和x3.

I have couple thousand sets of vt,v1,v2 and v3, therefore I need to be able to generate x1, x2 and x3 programmatically.

推荐答案

有两种方法可以解决此问题:

There are two ways you could approach this:

1. 使用您在帖子中设计的方法.随机生成x1和x2并确保vt < v1*x1 + v2*x2，然后继续求解x3.
2. 将其公式化为线性程序.线性程序基本上是在求解一个受不等式或等式约束的方程组.换句话说:

1. From the method that you have devised in your post. Randomly generate x1 and x2 and ensure that vt < v1*x1 + v2*x2, then go ahead and solve for x3.
2. Formulate this into linear program. A linear program is basically solving a system of equations that are subject to inequality or equality constraints. In other words:

这样，我们可以将您的问题转换为线性规划问题. 最大化"语句是所谓的目标函数，即您要实现的总体目标.在线性编程问题中，我们试图最小化或最大化该目标.为此，我们必须满足在要条件下看到的不平等现象.通常，该程序以规范形式表示，因此每个变量的约束应为正.

As such, we can translate your problem to be of a linear programming problem. The "maximize" statement is what is known as the objective function - the overall goal of what you are trying to accomplish. In linear programming problems, we are trying to minimize or maximize this objective. To do this, we must satisfy the inequalities seen in the subject to condition. Usually, this program is represented in canonical form, and so the constraints on each variable should be positive.

最大化条件可以是任意的，因为您不在乎目标.您只在乎任何解决方案.可以通过 linprog 来实现整个范例.您应该注意的是如何指定linprog.实际上，目标是最小化，而不是最大化.但是，除了确保所有变量均为正值外，其他条件都相同.我们将不得不自己编写代码.

The maximize condition can be arbitrary as you don't care about the objective. You just care about any solution. This whole paradigm can be achieved by linprog in MATLAB. What you should be careful with is how linprog is specified. In fact, the objective is minimized instead of maximized. The conditions, however, are the same with the exception of ensuring that all of the variables are positive. We will have to code that in ourselves.

就任意目标而言，我们可以简单地执行x1 + x2 + x3.因此，c = [1 1 1].我们的相等性约束为:v1*x1 + v2*x2 + v3*x3 = vt.我们还必须确保x为正.为了对此进行编码，我们可以做的是选择一个小的常数，以使x的所有值都大于该值.目前，linprog不支持严格的不等式(即x > 0)，因此我们必须通过执行此技巧来避免这种情况.同样，为了确保值是正数，linprog假定Ax <= b.因此，一个常用的技巧是消除x >= 0的不等式，因此这等效于-x <= 0.为了确保值不为零，我们实际上会这样做:-x <= -eps，其中eps是一个小常数.但是，当我进行实验时，通过这种方式进行操作，其中两个变量最终成为相同的解决方案.因此，我建议我们做的是生成每次都是随机的良好解决方案，让我们根据您所说的b来自统一的随机分布.然后，这将为我们每次要解决此问题的起点.

In terms of the arbitrary objective, we can simply do x1 + x2 + x3. As such, c = [1 1 1]. Our equality constraint is: v1*x1 + v2*x2 + v3*x3 = vt. We also must make sure that x is positive. In order to code this in, what we can do is choose a small constant so that all values of x are greater than this value. Right now, linprog does not support strict inequalities (i.e. x > 0) and so we have to circumvent this by doing this trick. Also, to ensure that the values are positive, linprog assumes that the Ax <= b. Therefore, a common trick that is used is to negate the inequality of x >= 0, and so this is equivalent to -x <= 0. To ensure the values are non-zero, we would actually do: -x <= -eps, where eps is a small constant. However, when I was doing experiments, by doing it this way, two of the variables end up to be the same solution. As such, what I would recommend we do is to generate good solutions that are random each time, let's draw b to be from a uniform random distribution as you said. This will then give us a starting point every time we want to solve this problem.

因此，我们的不平等是:

Therefore, our inequalities are:

 -x1 <= -rand1
 -x2 <= -rand2
 -x3 <= -rand3

rand1, rand2, rand3是在0和1之间的三个随机生成的数字.矩阵形式为:

rand1, rand2, rand3 are three randomly generated numbers that are between 0 and 1. In matrix form, this is:

 [-1 0 0][x1]      [-rand1]
 [0 -1 0][x2]  <=  [-rand2]
 [0 0 -1][x3]      [-rand3]

最后，我们之前的等式约束是:

Finally, our equality constraint from before is:

[v1 v2 v3][x1]     [vt] 
          [x2]  = 
          [x3]

现在，要使用linprog，您可以执行以下操作:

Now, to use linprog, you would do this:

X = linprog(c, A, b, Aeq, beq);

c是为物镜定义的系数数组.在这种情况下，它将定义为[1 1 1]，A和b是为不等式约束定义的矩阵和列向量，而Aeq和beq是为等式约束定义的矩阵和列向量.因此，X将在linprog收敛(即x1, x2, x3)之后为我们提供解决方案.因此，您可以这样做:

c is a coefficient array that is defined for the objective. In this case, it would be defined as [1 1 1], A and b is the matrix and column vector defined for the inequality constraints and Aeq and beq is the matrix and column vector defined for the equality constraints. X would thus give us the solution after linprog converges (i.e. x1, x2, x3). As such, you would do this:

A = -eye(3,3);
b = -rand(3,1);
Aeq = [v1 v2 v3];
beq = vt;
c = [1 1 1];
X = linprog(c, A, b, Aeq, beq);

例如，假设v1 = 0.33, v2 = 0.5, v3 = 0.2和vt = 2.5.因此:

rng(123); %// Set seed for reproducibility
v1 = 0.33; v2 = 0.5; v3 = 0.2;
vt = 2.5;
A = -eye(3,3);
b = -rand(3,1);
Aeq = [v1 v2 v3];
beq = vt;
c = [1 1 1];
X = linprog(c, A, b, Aeq, beq);

我得到:

X =

0.6964
4.4495
0.2268

要验证是否等于vt，我们将执行以下操作:

To verify that this equals vt, we would do:

s = Aeq*X

s = 2.5000

以上只是做v1*x1 + v2*x2 + v3*x3.这是用点积形式计算的，以使事情变得容易，因为X是列向量，而v1, v2, v3已经在Aeq中设置，并且是行向量.

The above simply does v1*x1 + v2*x2 + v3*x3. This is computed in a dot product form to make things easy as X is a column vector and v1, v2, v3 are already set in Aeq and is a row vector.

这样，任何一种方法都是好的，但是至少对于linprog，您不必一直循环，直到满足该条件为止！

As such, either way is good, but at least with linprog, you don't have to keep looping until you get that condition to be satisfied!

我在上述方法中忘记提及的一个小警告是，您需要确保vt >= v1*rand1 + v2*rand2 + v3*rand3以确保收敛.既然您说v1,v2,v3限制在0和1之间，那么最坏的情况是v1,v2,v3都等于1.因此，我们确实需要确保vt > rand1 + rand2 + rand3.如果不是情况，则只需取每个rand1, rand2, rand3值，然后除以(rand1 + rand2 + rand3) / vt.这样，假设所有权重均为1，这将确保总和等于vt，这将使线性程序正确收敛.

One small caveat that I forgot to mention in the above approach is that you need to make sure that vt >= v1*rand1 + v2*rand2 + v3*rand3 to ensure convergence. Since you said that v1,v2,v3 are bounded between 0 and 1, the worst case is when v1,v2,v3 are all equal to 1. As such, we really need to make sure that vt > rand1 + rand2 + rand3. If this is not the case, then simply take each value of rand1, rand2, rand3, and divide by (rand1 + rand2 + rand3) / vt. As such, this will ensure that the total summation will equal vt assuming that all of the weights are 1, and this will allow the linear program to converge properly.

如果不这样做，由于b中的不平等条件，解决方案将不会收敛，并且您将无法获得正确的答案.只是一些值得深思的东西！因此，请在运行linprog

If you don't, then the solution will not converge due to the inequality conditions placed in for b, and you won't get the right answer. Just some food for thought! As such, do this for b before you run linprog

if sum(-b) > vt
   b = b ./ (sum(-b) / vt);
end

祝你好运！

这篇关于在Matlab中获得满足线性方程式的一个答案的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！