Алгоритм для расчета

Всем привет. Подскажите, или перенаправьте в нужном направлении, а то не уверен, что в той ветке вопрос задаю)))
Есть набор данных. В этом наборе каждый элемент представляет собой тоже набор данных, пусть будет Х. Каждый Х имеет следующую структуру:
Х : К1, К2, К3, К4, К5, Р, где К1-К5 и Р - свойства Х.
Задача - найти Х (маловероятно и решено), или совокупность Х (что вероятнее всего и составляет проблему), где сумма К1 < n, сумма К2 < m, …., сумма К5 < z, а сумма Р - минимальная из всех возможных вариантов.
Вопрос - какой алгоритм можно использовать для решения этой задачи? У меня уже мозг дымится)))

0

Если К1, К2, К3, К4, К5, Р, никак не связаны между собой - то полный перебор.

0

passant, что-то типа такого?

0

Сообщение от Lekks Задача - найти ... совокупность Х (что вероятнее всего и составляет проблему), где сумма К1 < n, сумма К2 < m, …., сумма К5 < z, а сумма Р - минимальная из всех возможных вариантов.

Я бы тут задачу оптимизации с ограничениями попробовал. Добавив каждому иксу вес, который процедура оптимизации должна загнать в 0 или в 1. Веса эти будут домножаться на Ki и P в ограничениях и в минимизируемой сумме.
После расчёта - все иксы с околонулевыми весами выкидываются, для оставшихся проверяется (уже без весов) соответствие исходным условиям=ограничениям на Ki.

В общем, если метод множителей Лагранжа знаком - то я именно в ту сторону намекаю. По сравнению с Вашей исходной постановкой - добавил только веса иксам и ограничения на эти веса.

0

VTsaregorodtsev, ну, с позиций теории немного знаком (правда давненько), кой-чего полистал еще, все равно не въезжаю, как должна выглядеть целевая функция и функция ограничений.

Добавлено через 36 минут
Лол, блин... доп. условие - распределение Xi в совокупности, т.е. n1X1 + n2X2 + ... = 1, n1...ni = ???

0

Lekks,
Пусть у K будет двойной индекс - первым обозначаем номер икса (элемента, строки в таблице), второй - номер колонки (номер К). Тогда
w1*К11 + w2*К21 + ... wn*Кn1 < n,
w1*К12 + w2*К22 + ... wn*Кn2 < m,
и ещё три ограничения на сумму Kij (при суммировании по i)
Далее w1*P1 + w2*P2 + ... wn*Pn -> min.
И ограничения на каждый вес (чтобы загнать его в 0/1) - что-то типа wi(1-wi)=0
В общем, вес wi - он один на строку таблицы (для икса, т.е. одинаковый для всех пяти K и одного P в строке).

Про доп.условие - что-то не понял, ведь икс - это набор исходно из 6 значений. Как такой вектор взвешивать с помощью ni? Именно как вектор из 6 компонент? Тогда ОК (в смысле - можно записать такое ограничение) - но зачем оно? Может, подробно исходную задачу опишете, чтобы подумать именно над задачей (на не над некой Вашей/чужой формулировкой, которая может оказываться уже неправильной).

0

VTsaregorodtsev, смотрите:

X - это некое химическое вещество, которое состоит из некоторого числа элементов К. Из нескольких Х можно собрать другое вещество, на которое накладывается ограничение по нескольким К. Каждое Х имеет цену. Задача - "собрать" новое вещество из нескольких Х с учетом ограничений по К, которое (новое вещество) будет иметь минимальную цену из всех возможных вариантов.

Неопределенности состава каждого Х можно откинуть, так как проверяем по определенному набору К, соответственно, элементы К в Х, не попадающие в набор ограничений, проверке не подлежат.

Сейчас я иду все-таки путем перебора, получаю наборы Х (примерно как в коде выше). После получения наборов Х путем решения уравнения
а(sum(K1)) + в(sum(K2)) + с(sum(K3)) + ... = 1, где sum(Kn) - сумма количества элемента Кn в наборе, получаю разные комбинации (а, в, с ...), после чего беру цены из словаря по ключам набора Х (Х1, Х2, Х3,...), суммирую с учетом коэффициентов (а, в, с,.. ) в наборе и ищу минимальную сумму.

Но что-то это мне совсем не нравится. Куча циклов и условий, в том числе вложенных, не уверен, что это верный путь, кроме того вот наверняка же можно применить нормальный алгоритм.

0

Мой путь оказался неверным... Либо цикл бесконечный, либо точности не хватает

0

Lekks, а какие размеры наборов данных X,K? Если иксов - 4, то можно и полным перебором, т.к. вариантов всего ничего..

0

u235, нет, может быть любое число как Х, так и К. Но число К для всех Х - одинаково. Хотя получение комбинаций показывает, что как правило набор из 2-4 Х уже имеет необходимое решение, независимо от того, сколько всего предложено Х. Надо получить достаточное - то есть сколько какого Х взять. И перебором я не могу реализовать вычисление именно процентного соотношения Х1 - XN в новом веществе.

0

Сообщение от Lekks реализовать вычисление именно процентного соотношения Х1 - XN в новом веществе.

О, я понял тот момент, который раньше не понимал (и последним абзацем в посте #6 ушёл мыслями/вопросами не туда, а Вы затем в посте #7 меня не навели на правильное понимание - что надо искать и доли составляющих веществ). Просто в #5 Вы не сказали, что ni должны быть неотрицательными значениями - вот и не возникло мысли, что Вам нужны доли.

Сообщение от Lekks может быть любое число как Х, так и К.

А конкретные примеры значений этих размерностей - можно?


PS. В 1996ом занимался похожей задачей - но вместо ограничений на <n, <m, ..., <z (тут идёт отсылка к обозначениям из стартового поста темы) требовалось как можно более точное приближение значений свойств целевого объекта, и веса прогнозирующих объектов могли быть отрицательными. Т.е. строилась линейная регрессия не внутри строк таблицы, а внутри столбцов, и поскольку одна такая регрессия для всех объектов таблицы невозможна (слишком уж могут быть разноплановые признаки) - то из всех объектов=строк выбиралось малое число объектов, прогнозирующих данный. Ну и Ваше ограничение на минимальную цену - заменялось на регуляризующий критерий (штрафующий за большие веса, чтобы уменьшить чувствительность прогноза к очепяткам/неточностям значений свойств прогнозирующих объектов). Фактически, был вариант задачи коллаборативной фильтрации - не на основе схожести откликов разных людей, а через поиск возможности прогнозирования откликов некоторого человека по откликам иных людей с помощью лин.регрессии.

0

VTsaregorodtsev,

Сообщение от VTsaregorodtsev А конкретные примеры значений этих размерностей - можно?

chemix = {'N1': [0.108, 0.145, 11.610, 2.772, 6.930, 1.655, 0],
'N2': [0.099, 0.148, 12.150, 2.901, 7.650, 1.827, 0],
'N3': [0.098, 0.150, 11.704, 2.795, 7.656, 1.828, 0],
'N4': [0.405, 0.270, 13.064, 3.120, 8.372, 1.999, 0],
'N5': [0, 0, 0, 0, 0, 0, 2.000]
}
prices = {'N1': 6.22, 'N2': 11.11, 'N3': 10.23, 'N4': 35.49, 'N5': 64.42}
param = [0.15, 0, 0, 0, 9, 0, 0.0075]


Начальное количество N - можно задать, всего вариантов N около 200. Каждое N состоит из компонентов числом от 5 до 70. Param может включать от 1 до 70 (т.е. до максимально возможного в N) компонентов. При этом выбрав компоненты для проверки, мы можем некоторые значения не задавать (нули в param), в этом случае предварительно можно откорректировать длину chemix.values() и param, выкинув нулевые значения из списков.

В практике количество N чаще всего от 1 до 10, редко больше. Количество компонентов для проверки - 3-8, редко меньше или больше.

Добавлено через 22 минуты
И повторюсь - в ходе обработки комбинаций необходимое решение, т.е. chemix[Ni][0] < (или >) param[0] и т.д. до chemix[Ni][-1], param[-1] находится как правило в комбинации из 2-4 N. Достаточное же решение, т.е.
price(newN = aN1+bN2+..+zNi) -> min чет даже мыслей нет как найти.

0

Кажется, для решения подойдет scipy.optimize.minimize, но теперь я не пойму, как должна выглядеть функция, в каком параметре передавать ограничения на элементы и условие на минимум цены.

0

Привет, Lekks!
Я попробую переформулировать задачу эквивалентно.
Мы управляем фермой.
У нас есть несколько плохих комбикормов.
Каждый комбикорм полностью и одинаково хорошо покрывает все потребности животных в еде.
Есть различные типы вредных веществ.
У каждого комбикорма есть набор концентраций типов вредных веществ в нём. (масса вещества на кг корма)
Мы пытаемся смешать комбикорма в некоторой пропорции.
У каждого типа вредной добавки есть своя предельная допустимая концентрация.
Мы обязаны смешать корма так, чтобы не превысить допустимую концентрацию ни одного из типов вредных веществ.
У каждого комбикорма есть цена. (за кг)
Мы пытаемся смешать комбикорма так, чтобы минимизировать цену смеси. (за кг)

Если модель этой задачи существенно отличается от вашей, пожалуйста, уточните, как именно.

Задача про ферму -- задача линейного программирования (потому что набор ограничений и то, что мы оптимизируем -- линейные относительно "двигабельных" параметров функции, елси нужно, могу объяснить подробнее).
Если количество типов вредных примесей и количество типов корма достаточно мало (например, 5 примесей и 100 кормов), то за разумное время найдёт точный ответ алгоритм вроде такого:
"""
Пербрать мелкие наборы линейных ограничений, для каждого набора:
Решить систему линейных уравнений, получить точку Т
Проверить, удовлетворяет ли Т всем остальным условиям, и если да, то записать в список "Кандидаты"
Выбрать наилучшего Канидата.
"""
Если нужно, я могу описать алгоритм более чётко и подробно. На практике вместо всего этого должно сработать просто запустить симплекс-метод.

Для случаев побольше начинать, наверное, стоит тоже с симплекс-метода, но есть и другие техники.

0

Murmuron, спасибо. Да, задача в целом такая. Единственное - ограничения могут быть "от" - "до". В общем-то способ я уже вроде как нашел. Теперь мучаю ограничения)))

тут

0

Решено через scipy.optimize.minimize

0