26. Дискретные оптимизационные задачи. Задача о назначениях. Метод ветвей и границ.

Оптимизация-задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств. В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества. На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда — наилучшего из найденных решений, то подмножество может быть отброшено. Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.дС использованием введенных обозначений простейшая задача размещения записывается следующим образом

y_i  x_ij,  i  I,  j  J,/……/x_ij, y_i , y_i  {0, 1},    iI,  jJ. Двойственная задача линейного программирования имеет вид:

v_j  g_ij + w_ij,  i I, j J,/…../w_ij  0, i I,  j J.

Приближенное решение двойственной задачи используется в качестве нижней оценки.

Для сокращения размерности задачи применяется так называемый блок предварительной отбраковки. Он основан на применении условий дополняющей нежесткости для задач линейного программирования

 

Если для оптимального решения двойственной задачи выражение в скобках положительно для некоторого i I , то “скорее всего” в исходной целочисленной задаче y_i = 0, и размерность можно уменьшить. Понятно, что данный эвристический прием не всегда приводит к правильному решению. Поэтому в качестве порога лучше брать не 0, а некоторую величину d  0, выбор которой зависит от исходных данных. Эту величину называют порогом отбраковки. Очевидно, что при d  max c_i, размерность задачи не сокращается. Другой способ уменьшения трудоемкости алгоритма состоит в искусственном завышении нижней оценки. Предположим, что нас интересует не только оптимальное решение, но и приближенные решения с относительной погрешностью не более e . Тогда завышение нижней оценки в (1 + e ) раз приводит к желаемому результату.Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Метод ветвей и границ был впервые предложен в 1960 году Ленд и Дойг^[1] для решения задач целочисленного программирования. Общая идея метода может быть описана на примере поиска

минимума и максимума функции на множестве допустимых значений . Функция и могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ). Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти. Процедура нахождения оценок заключается в поиске верхних и нижних границ для оптимального значения на подобласти допустимых решений. В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти , то может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную ; любой узел дерева поиска, нижняя граница которого больше значения , может быть исключен из дальнейшего рассмотрения.Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.

27.Дискретные оптимизационные задачи. Задача об оптимальном раскрое материала. Задача оптимального раскроя материалов является одной из самых важных в ресурсосберегающих технологиях для заготовительного производства, поскольку напрямую ведет к экономии материалов и снижению отходов. Существующие методы раскроя материалов условно можно разделить на 3 группы:1)нормативные ;2)технологические ;3)оптимизационные. Обширный класс экономико-математических моделей образуют оптимизационные модели, позволяющие выбирать из всех решений самый лучший оптимальный вариант. В математическом смысле оптимальность понимается как достижение экстремума (максимума или минимума) критерия оптимальности, именуемого также целевой функцией. Оптимизационные задачи решаются посредством выполнения моделей с помощью методов математического программирования, реализуемых обычно с применением электронно-вычислительной техники..Методы решения задач рационального раскроя. Задача рационального раскроя относится к классу NP-полных дискретных оптимизационных задач комбинаторного типа. Следует различать приближенные и точные методы решения задач дискретной оптимизации. К приближенным методам, в свою очередь, относят эвристики и метаэвристики. Разработка точных методов построения оптимальных планов раскроя ведется достаточно давно. Распространенные подходы предполагают использование метода отсечений для решения соответствующих задач целочисленного линейного программирования или реализацию эффективных переборных алгоритмов на основе общей схемы метода ветвей и границ. Эвристические методы не гарантируют получение оптимальных решений, но при этом отличаются сравнительной простотой и позволяют при незначительных затратах получать решения, приемлемые для практического использования. Эвристики, используемые для решения задач рационального раскроя, условно можно разделить на две группы. Методы первой группы основываются на решении вспомогательной задачи линейного программирования. Полученное решение раскройной задачи не является целочисленным и требует соответствующей коррекции. В методах второй группы применяется иной подход, который предполагает пошаговое построение допустимого решения за конечное число итераций