Libiros
@Libiros
WebDev ninja!

Как организовать выборку эффективных вариантов из таблицы?

Есть такая таблица:
5e85ae825c86f207445323.png

Задача:
Сделать наиболее эффективный набор из items, удовлетворяющий условию.

Условие:
Parameter 1 = 20
Parameter 3 = 30
$ < 100 , т.е. наиболее дешевый.

Решение:
Очевидно, решением было бы просто взять Item 1, так как оба параметра сходу удовлетворяют. Но его стоимость 100$. Поэтому попробуем поискать дальше.
Следующим решением задачи будет такой вот набор items:

Item3 + 3*Item4 + Item2

Parameter 1:
1*10 + 3*3 + 1*1 = 20
Parameter 3:
1*10 + 3*5 + 1*5 = 30


По деньгам это выйдет 10$. И это меньше, чем в первом решении, так как 10$ < 100$.
Задача решена.

Теперь, собственно, сами вопросы:
Каков будет алгоритм подбора удовлетворяющей формулы по заданным критериям?
Я понимаю, что алгоритм мне здесь вряд ли напишут, поэтому вопрос - как такое гуглить? Наверняка, я не первый, кто задается поиском и подбором эффективных вариантов из огромной таблицы.
Тот пример, что я привел, тестовый. То есть табличка 5х5. На деле это таблица 200х200 с более чем 50 критериями.
Наверняка, существует какая-то формула, которая работает с таблицей как с матрицей и раскладывает ее. Как к такой формуле прийти?

P.S. возможно, я даже тему неправильно задал, поэтому буду рад, если знающие меня исправят, так как правильно заданный вопрос есть половина ответа

UPD:
Решение найдено. Это задача на принятие решения симплекс-методом (можно и графическим).
Симплекс-метод - это итеративный процесс направленного решения системы уравнений по шагам, который начинается с опорного решения и в поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения.

Необходимо составить целевую функцию, которую будем минимизировать. Для примера из вопроса:
100x1+2x2+2x3+2x4+50x5 -> min
Далее необходимо составить систему линейных неравенств:
20х1 + х2 + 10х3 + 3х4 + 16х5 = 20
30х1 + 5х2 + 10х3 + 5х4 + 25х5 = 30

Далее применяем алгоритм нелинейной оптимизации и симплекс-метод. Сам метод расписывать не буду, куча примеров в интернете. Для такой задачи можно решить на листе бумаги.
Этот же метод можно применить в excel через надстройку "поиск решения".
В python есть SimPy.
При желании, можно написать и свой велосипед, но надо ли?

UPD2
Когда я задал вопрос, то указал решение "очевидное решение", которое оказалось неверным. Стоимость моего решения составила 10$, но решая задачу симплекс-методом, стоимость сократилась до 8.5$.
Решение: x1 = 0, x2 = 2.5, x3 = 1.75, x4 = 0, x5 = 0
Таким образом, надо взять 2.5 Item2 и 1.75 Item3, чтобы получить верное решение поставленной задачи.
  • Вопрос задан
  • 160 просмотров
Пригласить эксперта
Ответы на вопрос 3
Похоже на задачу об упаковке, которая решается полным перебором всех вариантов.
Тут два типа условий: строгие – по параметрам 1 и 3; и нестрогий поиск минимума по стоимости.

Нужно обходить дерево вариантов, отбрасывать ветки сразу, как только не соблюдается одно из строгих условий,
или ранее найденный минимум по стоимости превышен нынешней веткой.
Ответ написан
@MagicMight
Задача в нахождении паретооптимального множества решений?
Допустим, есть вектор характеристик (п1, п3, м) и нужно найти решения, где п1 и п3 максимальны, а М минимально.
Каждая пара решений(р1, р2) может находиться в трех состояниях:
1) р1 по всем параметрам лучше р2
2) р2 по всем параметрам лучше р1
3) р1 и р2 векторно несравнимы (когда часть параметров одного решения лучше, а часть хуже). Пример (item1, item5).

Можно за nlogn оставить векторно несравнимые решения двойным циклом. Во внешнем цикле брать строку из таблицы, а во внутреннем сравнивать взятую строку со всеми последующими, удаляя те, которые проигрывают по всем характеристикам. После завершения цикла останется паретооптимальное множество решений.

P.S. в свое время мне помогла книга Подиновский В.В., Ногин В.Д. Парето-оптимальные ре...

UPD. Полное решение.

Алгоритм.
Пусть у нас есть N записей (будем называть их n1, n2, ...), каждой из которых ставится в соответствие вектор характеристик (a,b,c), где a - param1, b - param2, c - money.
Есть ограничение minmax на a, b и max на c.
Шаг 1.
Для каждой отдельно взятой записи определяем количество, больше которого мы не можем взять (назовем его max(n)).
Пример. Если у нас есть запись (5, 10, 10), minmax(a) = (40, 80), minmax(b) = (50, 70), max(c) = 60, то
Определям количество.
max(a): 80 / 5 = максимум 16 записей
max(b): 70 / 10 = максимум 7 записей
max(c): 60 / 10 = максимум 6 записей
То есть из всех верхних ограничений следует, что мы можем взять эту запись не более 6 раз. max(n) = 6
Строки с max(n)=0 удаляем.

Шаг 1.1 (опциональный). Позволяет отловить решение, удовлетворяющее всем условиям быстрее, но не обязательно выдаст самое эффективное.
Для каждой записи сделаем проверку по минимальному условию min(n). В качестве примера возьмем запись из прошлого примера.
min(a): 40 / 5 = минимум 8 записей
min(b): 50 / 10 = минимум 5 записей
По совокупности ограничений понимаем, что мы можем взять минимум 8, а максимум 6 записей для составления решения
только из нескольких этих записей, что невозможно. Если бы мы получили результат, где min(n) <= max(n), то могли бы построить допустимые решения,
состоящие из одной записи.

Шаг 2. Составление комбинаций из записей.
Представим, что у нас есть чудесное выражение вида k1*n1 + k2*n2 + ... + kN*nN = (ak, bk, ck)
Диапазон для перебора каждого k_i = (0, max(n_i))
Помним, что n_i - это вектора. Соответственно, результат выражения - это сумма векторов, каждый из которых домножен на свой коэффициент.
Все те коэффициенты, при которых (ak, bk, ck) удовлетворяют minmax на ak, bk и max на ck мы сохраняем как допустимые.

Все :)
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Условие:
Parameter 1 = 20
Parameter 3 = 30
$ < 100 , т.е. наиболее дешевый.

Строка умноженная на количество: 2x1, 3x1, 4x3
Сумма: 2*5=10$
Элементы: 20, 30

Как искать?
Разложить целевые параметры на слагаемые, имеющиеся из списка.
Приблизить результат по каждому, перейдя к следующему параметру из текущего: "сузить" выборку и сравнить КПД (минимальную стоимость).
Дробные части строк - считаются точно также.

Кому интересно: на 200-та элементах задача решается в среднем за 120 итераций.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы