Скажем, у меня есть структура данных Group, которая содержит список объектов Element, так что каждая группа имеет уникальный набор элементов .:
public class Group
{
public List<Element> Elements;
}
и скажем, у меня есть список популяций, которым требуются определенные элементы, таким образом, чтобы у каждой популяции был уникальный набор необходимых элементов:
public class Population
{
public List<Element> RequiredElements;
}
У меня есть неограниченное количество каждой определенной группы, т.е. они не потребляются населением.
Скажем, я смотрю на конкретный Population. Я хочу найти наилучшее возможное совпадение групп с минимальным количеством лишних элементов и отсутствием несовпадающих элементов.
Например: у меня есть население, которому нужны древесина, сталь, зерно и уголь. Доступны только группы {дерево, травы}, {сталь, уголь, масло}, {зерно, сталь} и {травы, мясо}.
Последняя группа - {травы, мясо} совсем не нужна моему населению, поэтому не используется. Все остальные необходимы, но травы и масло не требуются, поэтому они тратятся впустую. Кроме того, в минимальном наборе сталь существует дважды, поэтому одна партия стали также тратится впустую. У наилучшего соответствия в этом примере потери равны 3.
Итак, для нескольких сотен Population объектов мне нужно найти наилучшее соответствие минимальных потерь и вычислить, сколько элементов теряется.
Как мне вообще начать это решать? Как только я найду совпадение, подсчет потерь станет тривиальным делом. Во-первых, найти совпадение сложно. Я мог бы перечислить все возможности, но с несколькими тысячами популяций и многими сотнями групп это довольно трудная задача. Особенно с учетом того, что все это находится внутри каждой итерации алгоритма имитации отжига.
Мне интересно, могу ли я сформулировать все это как программу со смешанными целыми числами и вызывать решатель, такой как GLPK, на каждой итерации.
Надеюсь, я правильно объяснил проблему. Я могу прояснить все, что неясно.
Вот моя бинарная программа, для тех, кому интересно ...
x - вектор решения, элемент {0,1}, который говорит, что рассматриваемая популяция получает / не получает от группы i. Для каждой группы есть запись.
b - вектор-столбец, элемент {0,1}, который говорит, какие ресурсы данной популяции нужны / не нужны. Для каждого ресурса есть запись.
A - это матрица, элемент {0,1}, которая говорит, какие ресурсы в каких группах.
Программа:
Свернуть: ((Ax - b) '* 1-вектор) + (x' * 1-вектор);
При условии: Ax> = b;
Ограничение просто говорит, что все необходимые ресурсы должны быть удовлетворены. Цель состоит в том, чтобы свести к минимуму все лишнее и общее количество используемых групп. (т.е. 0 превышений при использовании 1 группы лучше, чем избыток 0 при использовании 5 групп).
