Как проверить, без функции объекта, возможны ли ограничения?
Мой профессор дал мне бинарную задачу линейного программирования, но эта проблема немного отличается от задач оптимизации, которые я раньше решал (т.е. это, вероятно, не максимизация или минимизация функции объекта).
Проблема заключается в следующем,
Для матрицы m для записей m_ij! = 0 имеются соответствующие переменные x_ijk.
Записи m_ij = 0 можно игнорировать.
x_ijk равен 0 или 1, и я хочу попробовать 5 переменных x_ijk для каждого m_ij (то есть x_ij1, x_ij2, x_ij3, x_ij4 и x_ij5. Одна из них равна 1, а остальные равны 0), чтобы удовлетворить некоторые условия (множество неравенств).
Проще говоря, это проверить, является ли набор ограничений, включающий 5 переменных x_ijk для каждого m_ij, действительными (или выполнимыми) ограничениями.
Я решил некоторые проблемы оптимизации, но я никогда не решал проблему без целевой функции.
Что я должен установить в качестве моей целевой функции здесь?
0? ничего такого?
Я мог бы использовать lp_solve или CPLEX.
Заранее благодарю за совет!
Решение
Это правильно, вы можете установить произвольное постоянное значение в качестве целевой функции.
Большинство решателей, которые я пробовал, допускают пустую целевую функцию. Просто оставьте это вне вашей модели.
В зависимости от решателя и API, который вы используете, может случиться так, что вам придется установить коэффициенты всех переменных в задаче на ноль.
Не волнуйся, это должно сработать.
В ответ на ваш комментарий: Да, инструменты программирования ограничений могут обеспечить лучшую производительность при решении технико-экономических задач, чем решатели LP (такие как CPLEX). Я играл с IBM ILOG CPLEX CP Optimizer Несколько месяцев назад, это бесплатно для академических пользователей. И решатель LP, и решатель CP потерпели неудачу в моих проблемах. Не ожидайте чуда от программирования ограничений.
Имейте в виду, что время, необходимое для решения программы ограничения, растет в геометрической прогрессии с увеличением размера проблемы в худшем случае. Рано или поздно ваши проблемы, скорее всего, станут неразрешимыми с любым из этих инструментов.
Просто для вашей информации: в конце решатель программирования ограничений вызовет решатель LP (например, CPLEX).
Мой совет: попробуйте инструмент, который у вас уже есть / используйте формулировку проблемы, которая является более естественной для вас. Проверьте, может ли инструмент решить вашу проблему. Переключайте инструмент только в случае сбоя инструмента, и вы не можете улучшить свою модель.
Другие решения
Других решений пока нет …