Экстремальные комбинаторные задачи.

Задача о коммивояжере — классический пример задачи выбора оптимального маршрута.

Пусть Хц = 1, если коммивояжер переезжает из города i непосредственно в город j, и xij = 0 в противном случае. Обозначим через cij расстояние между городами i и j (чтобы избежать бессмысленных значений Xij = 1, предполагается, что си равны достаточно большому числу).

Тогда формальная модель имеет вид

п п

F(x) = ? X Си X;, min ,

v 7 ,=i;=i U \'J \'

п

ЇХу= 1 для і = 1, ..., п,

п

Zxg=l дляу= 1, ..., п.

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

Zi - Zj+ пху<п- 1, / = 2, п; j = 2, ..., п (/ sty),

где на переменные zi и Zj не требуется накладывать никаких ограничений.

Общая задача календарного планирования формулируется следующим образом. Имеется п станков (машин), на которых требуется обработать m деталей. Заданы маршруты (в общем случае различные) обработки каждой детали на каждом из станков или группе станков. Задана также продолжительность операций обработки деталей. Предполагается, что одновременно на станке можно обрабатывать не более одной детали. Требуется определить оптимальную последовательность обработки. Критерием оптимальности могут выступать продолжительность обработки всех деталей, суммарные затраты на обработку, общее время простоя станков и др. Существует огромное число постановок данной задачи, учитывающих конкретные условия производства.

Один из представителей задач данного типа — так называемая задача о ранце.

п

F (х) = ? с, X: шах,

у\'= 1 J J

iwjXjXjG {0, 1} для j= 1, ..., tl.

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

Большинство целочисленных и комбинаторных типов задач, таких, как задача с неделимостями, задача коммивояжера, задача календарного планирования, принадлежит к разряду так называемых трудно

решаемых. Это означает, что вычислительная сложность алгоритма их точного решения — зависимость числа элементарных операций (операций сложения или сравнения), необходимых для получения точного решения, от размерности задачи я — является экспоненциальной (порядка 2n), т.е. сравнимой по трудоемкости с полным перебором вариантов. В качестве п, например, для задачи с неделимостями служит число целочисленных переменных и число ограничений, для задачи коммивояжера — число городов (или узлов графа маршрутов), для задачи календарного планирования — число деталей и число станков. Такие задачи называют еще NP-трудными или NP- полными. Получение их точного решения не может быть гарантировано, хотя для некоторых задач данного типа существуют эффективные методы, позволяющие находить точное решение даже при больших размерностях. Примером таких задач служит задача о ранце с булевыми переменными.

Задачи с вычислительной сложностью, определяемой полиномиальной зависимостью от п, называются эффективно решаемыми. К такого типа задачам принадлежат задачи транспортного типа и линейные задачи о назначениях.

Для решения целочисленных задач используются следующие методы:

симплекс-метод (для транспортных задач, задач о назначениях);

метод отсечения (метод Гомори);

метод ветвей и границ (в общем случае не обеспечивает получения точного решения);

эвристические методы (не обеспечивают получения точного решения).

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