Оптимизация под ограничениями

Question

У меня есть вопрос относительно оптимизации.

У меня есть матрица x с 3 столбцами и определенное количество строк (макс. 200). Каждая строка представляет кандидата. В первом столбце содержится оценка (от 0 до 1), столбец 2 содержит вид кандидата (всего 10 видов, помеченных от 1 до 10), а столбец 3 содержит количество каждого кандидата. Следует учитывать одно: сумма может быть ОТРИЦАТЕЛЬНОЙ

Что я хотел бы сделать, так это выбрать максимум 35 элементов среди этих кандидатов, которые максимизируют функцию, которая суммируется по их соответствующей оценке (столбец 1) под ограничения могут составлять не более 10% каждого вида, рассчитанные следующим образом: процентное соотношение вида 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] - количество кандидатов x для вида i (A [i] [x] может быть положительным или отрицательным, как вы сказали).
• T[i] - общая сумма всех кандидатов натурой i.
• I[x] - 1, если элемент x должен быть включен, и 0, если элемент x должен быть исключен.

Функция 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 быть n мерный вектор с каждым компонентом равно 1: 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% каждого вида, у нас будет функция C2[i]() для каждого вида i (вы сказали, что всего 10). C2[i]() Вычисляет количество студентов, отобранных для любезного i дал студентам мы выбрали:

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

вычислим C2[i]() так: Пусть k be n размерный вектор, равный <A[i]1, A[i]2, ..., A[i]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 «s индекс является [i + 1] потому что x1 уже используется как переменная slack для предыдущего ограничения.

---

В целом, линейная программа будет выглядеть следующим образом (добавление 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% просто применяется к сумме сумм. Надеюсь, это правильная интерпретация. Не уверен, что это правда, если у нас есть отрицательные суммы.