Ослабление целочисленной задачи [c.329]
На первом шаге решается задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. Если полученное оптимальное решение оказывается целочисленным, то оно является также решением исходной задачи. В противном случае следует ввести дополнительные ограничения, порождающие (вместе с исходными ограничениями) новую задачу линейного программирования, решение которой оказывается целочисленным и совпадает с оптимальным решением исходной целочисленной задачи. [c.466]
Если в целочисленной задаче линейного программирования отбросить требование о целочисленное неизвестных, то получим задачу линейного программирования, которая называется ослаблением исходной целочисленной задачи. [c.218]
Целочисленное оптимальное решение ослабления является оптимальным решением и исходной целочисленной задачи, [c.218]
В большинстве же случаев ослабление целочисленной задачи линейного программирования имеет только нецелочисленное оптимальное решение, причем если округлить нецелочисленные координаты этого решения, то нельзя получить даже допустимого решения исходной задачи.. С другой стороны, для решения комбинаторной оптимизационной задачи можно попробовать перебрать все допустимые решения этой задачи и выбрать среди них такое, на котором целешая функция принимает наибольшее (наименьшее) значение. Однако встречаются задачи, у которых допустимых решений очень много и перебрать их все практически невозможно. [c.219]
В частности, если ослабление окажется транспортной задачей с целочисленным вектором ограничений, то оптимальное решение транспортной задачи (которое при этих условиях всегда можегг быть выбрано целочисленным) будет оптимальным решением исходной целочисленной задачи линейного программирования. [c.219]
Решения модели перераспределения ресурсов с требованием целочисленности переменных и линейным критерием относятся к задаче целочисленного программирования. К ним можно применить следующие методы оптимизации метод отсекающих плоскостей (метод Гомори), различные методы построения ослабленных задач, метод ветвей и границ и различные его модификации, например метод штрафных функций. [c.183]