约束下的优化

Question

我有一个关于优化的问题。

我有一个包含 3 列和特定行数（最多 200）的矩阵 x。每行代表一个候选人。第一列包含一个分数（0 到 1 之间），第二列包含候选人的种类（从 1 到 10 总共有 10 种标记），第三列包含每个候选人的数量。需要考虑一件事：金额可以为负

我想要做的是 select 在这些候选者中最多 35 个元素，这将在最多 10 个约束条件下最大化对各自分数（第 1 列）求和的函数每种类型的百分比按以下方式计算：类型 1 的百分比：类型 1 的总和除以所有总和。

最后，我想要一组最多 35 名满足约束条件并优化他们分数总和的候选人。

这是我到目前为止提出的代码，但我在 10% 的限制上苦苦挣扎，因为它似乎没有被考虑在内：

rng('default');

clc;
clear;
n = 100;
maxSize =  35;

%%%TOP BASKET
nbCandidates = 100;
score = rand(100,1)/10+0.9;
quantity = rand(100,1)*100000;
type = ceil(rand(100,1)*10)
typeMask = zeros(n,10);

for i=1:10
    typeMask(:,i) = type(:,1) == i;
end

fTop = -score;
intconTop = [1:1:n];

%Write the linear INEQUALITY constraints: 
A = [ones(1,n);bsxfun(@times,typeMask,quantity)'/sum(type.*quantity)];
b = [maxSize;0.1*ones(10,1)];


%Write the linear EQUALITY constraints:
Aeq = [];
beq = [];

%Write the BOUND constraints: 
lb = zeros(n,1);
ub = ones(n,1); % Enforces i1,i2,...in binary

x = intlinprog(fTop,intconTop,A,b,Aeq,beq,lb,ub);

如果我做错了，请给我一些建议，我将不胜感激！

Answer 1

您的模型的线性程序可能如下所示：

n为考生人数
S[x] 是候选人 x 的分数。
A[i][x] 是种类 i 的候选 x 的数量（A[i][x] 可以是正数或负数，就像你说的那样）。
T[i] 是种类 i.

x

I[x] 为 1，如果要排除元素 x，则为 0。

您要优化的函数f是S[x]和I[x]的函数。您可以将 S 和 I 视为 n 维向量，因此您要优化的函数是它们的点积。

f() = DotProduct(I, S)

这相当于线性函数I1 * S1 + I2 * S2 + ... + In * Sn。

我们可以用这种方式制定所有约束以获得一组线性函数，其系数是 n 维向量中的分量，我们可以用 I 点缀，参数优化。

对于最多只能取35个元素的约束，让C1()是一个计算元素总数的函数。然后第一个约束可以形式化为 C1() <= 35 并且 C1() 是一个线性函数，可以这样计算：

设 j 为每个分量都等于 1 的 n 维向量：j = <1,1,...,1>.

C1() = DotProduct(I, j)

所以C1() <= 35是一个等价于的线性不等式：

I1 * 1 + I2 * 1 + ... + In * 1 <= 35 I1 + I2 + ... + In <= 35

我们需要在这里添加一个松弛变量x1，将其转化为等价关系：

I1 + I2 + ... + In + x1 = 35

对于每一种只能取10%的约束条件，我们将对每一种i（你说一共10个）有一个函数C2[i]()。 C2[i]() 给定我们选择的学生 i 计算被录取的学生数量：

C21() <= .1 * T1
C22() <= .1 * T2
...
C210() <= .1 * T10

我们这样计算 C2[i]()：设 k 是等于 <A[i]1, A[i]2, ..., A[i]n> 的 n 维向量，每个分量是每个候选种类 i 的数量。然后 DotProduct(I, k) = I1 * A[i]1 + I2 * A[i]2 + ... + In * A[i]n，是给定 I 的种类 i 的总量，捕获我们包含哪些元素的向量。

所以C2[i]() = DotProduct(I, k)

现在我们知道如何计算 C2[i]()，我们需要添加一个松弛变量将其转化为等式关系：

C2[i]() + x[i + 1] = .1 * T[i]

这里x的下标是[i + 1]，因为x1已经被用作前面约束的松弛变量

总而言之，线性规划看起来像这样（为每个不等式约束添加 11 个松弛变量 x1, x2, ..., x11）：

Let:
V = <I1, I2, ..., In, x1, x2, ..., x11> (variables)

    |S1|
    |S2|
    |. |
    |. |
    |. |
P = |Sn| (parameters of objective function)
    |0 |
    |0 |
    |. |
    |. |
    |. |
    |0 |

    |35    |            
    |.1*T1 |            
C = |.1*T2 | (right-hand sides of constraining equality relations)      
    |...   |            
    |.1*T10|


     |1    |1    |...|1    |1|0|...|0| 
     |A1,1 |A1,2 |...|A1,n |0|1|...|0|
CP = |A2,1 |A2,2 |...|A2,n |0|0|...|0| (parameters of constraint functions)
     |...  |...  |...|...  |0|0|...|0|
     |A10,1|A10,2|...|A10,n|0|0|...|1|

Maximize:
V x P

Subject to:
CP x Transpose(V) = C

希望这是清楚的，对于糟糕的格式感到抱歉。

Answer 2

我相信 MIP 模型看起来像：

这里i是数据点，j表示类型。为简单起见，我在这里假设每种类型都具有相同数量的数据点（即 Amount(i,j)、Score(i,j) 是矩阵）。通过限制求和可以很容易地处理更不规则的情况。

10% 规则仅适用于金额总和。我希望这是正确的解释。如果我们有负和，不确定这是否正确。

约束下的优化

Optimization under constraints

matlab

optimization

constraints

dynamic-programming

linear-programming