Сформулируйте условие окончания ветвления при решении задач методом ВИГ

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

Критерии окончания ветвления:

В задаче на максимум в начале решения граничное значение целевой функции, или рекорд, полается равным - ∞.

1. Получена задача, не имеющая решения. Это становится все более вероятным с увеличением глубины ветвления, когда все большее число ограничений вида x_i ≤ [{x_i⁰], или x_i ≥ [{x_i⁰] +1 добавляется к уже существующим ограничениям(так, что все более вероятным становится несовместимость системы ограничений получаемых задач).

2. Если находится новое целочисленное решение, то оно сравнивается с рекордом; если прежний рекорд превзойден, то запоминается новый рекорд, в противном случае остается старый.

3. Получаемое оптимальное нецелочисленное решение задачи на какой-то стадии ветвления сравнивается с рекордом; если это значение меньше, чем рекорд, то ветвление задачи прекращается, так как нет возможности побить рекорд.

Непобитый рекорд дает оптимальное решение исходной задачи ЦЛП.

Что такое решение, оптимальное по Парето в многокритериальной задаче.

Множество допустимых решений, для которых невозможно одновременно улучшить все частные показатели эффективности, принято называть областью Парето или областью компромиссов, а принадлежащие ей решения – эффективными или оптимальными по Парето.

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

Множество допустимых решений, для которых невозможно одновременно улучшить все частные показатели эффективности, принято называть областью Парето или областью компромиссов, а принадлежащие ей решения – эффективными или оптимальными по Парето.

Общий вид задачи многокритериальной оптимизации:

f_i(x) → max (i=1,2,…,n),

x € D

x-?

66.Объясните, почему метод ВИГ принадлежит к методам отсечения?

Применяется это тогда, когда нужно найти целочисленное решение.

Метод ВИГ принадлежит к методам отсечения потому, что при решении задачи этим методом, допустимая область делится на части и при решении задачи для каждой отдельной части, мы оставшиеся части временно не учитываем(т.е. отсекаем).

67.Почему нельзя решать задачу целочисленного ЛП, решив ее сначала как обычную задачу ЛП без учета целочисленности, а затем округлив полученное решение?

1) Потому что не известно в какую сторону округлять(в большую или в меньшую)

2) Можно выйти за пределы допустимой области

3) Оптимальное целочисленное решение может быть не в соседней точке, а через одну, две, десять и т.д.

68.Что такое решение, оптимальное по Парето, в многокритериальной оптимизации?

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

Требуется найти точку области допустимых решений, которая максимизирует или минимизирует все эти критерии. Обозначим i-й частный критерий через _I(x), а область допустимых решений через Q. Учитывая, что изменением знака функции всегда можно свести задачу минимизации к задаче максимизации и наоборот, можно сформулировать задачу векторной оптимизации следующим образом: max x

В идеальном случае в этой задаче можно вести поиск такого решения, которое принадлежит пересечению множеств оптимальных решений однокритериальных задач. Однако указанное пересечение обычно оказывается пустым множеством, и потому приходится рассматривать переговорное множество решений Парето. Вектор х* Q называется эффективным решением, если не существует такого х что Z (x) Z (x*), i=1,2,.,m, причем хотя бы для одного i имеет место строгое неравенство. Множество допустимых решений, для которых невозможно одновременно улучшить все частные показатели эффективности, принято называть областью Парето или областью компромиссов, а принадлежащие ей решения – эффективными или оптимальными по Парето.

Основной вопрос, который изучается в многокритериальной оптимизации, - формулировка подходящего обобщенного критерия в зависимости от конкретной ситуации. В некоторых случаях вместо одного обобщенного критерия и решения одной задачи скалярной оптимизации предлагается рассматривать последовательность задач скалярной оптимизации.