Ниже приведено условие задачи и текстовая часть решения. Все решение полностью, в формате doc в архиве, вы можете скачать. Некоторые символы могут не отображаться на странице, но документе word все отображается. Еще примеры работ по ЭМММ можно посмотреть

ПОСТАНОВКА ЗАДАЧИ

Издательское предприятие должно выполнить в течении недели (число дней m = 5) работу по набору текста с помощью работников n категорий (высокая, средняя, ниже средней, низкая). Требуются определить оптимальную численность работников по категориям, при которой обеспечивается выполнение работы с минимальным расходом фонда зарплаты при заданных ограничениях. Исходные данные приведены в таблице 1 и 2.

Таблица 1

Таблица 2

Задача должна решаться методом целочисленного линейного программирования в Mathcad 2000/2001.

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
РЕШЕНИЯ ЗАДАЧИ

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

Решение задачи целочисленного программирования выполняется в два этапа.

На первом этапе выполняется задача линейного программирования без учета целочисленности.

На втором этапе производится пошаговый процесс замены нецелочисленных переменных ближайшими верхними или нижними целыми значениями.

Сначала решается, задача без учета условия целочисленности.

Целевая функция определяется по формуле:

где Q - общий фонд зарплаты на выполнение работы;

x 1 , x 2 , …, x n - численность работников по категориям;

n - число категорий работников;

c 1 , c 2 ,…, c n - дневная тарифная ставка одного работника по категориям;

m - число рабочих дней в неделю, m = 5.

Целевую функцию можно записать в векторной форме:

При решении задачи должны выполняться следующие ограничения. Ограничение сверху

x ≤ d (1)

задает максимальную численность работников по категориям, где d —вектор, определяющий численность по категориям.

В ограничении

учтено, что общая численность работников не должна превышать k max .

В ограничении снизу

р × х≥Р (3)

отражается, что все работники вместе должны выполнить заданный объем работ Р .

В качестве последнего ограничения записывается условие неотрицательности вектора переменных

x ≥0 (4)

Математическая модель решения задачи без учета условия целочисленности включает следующие выражения:

x ≤ d

р × х≥Р ,

x ≥ 0 .

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

РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В MATHCAD

Исходные данные для примера даны в табл. 1 и 2.

Для решения задачи используется пакет Mathcad с функцией Minimize. Данная функция определяет вектор решения задачи:

х := Minimize (Q , x ),

где Q — выражение целевой функции, определяющей минимальный фонд зарплаты, х - вектор переменных.

Сначала задача решается без учета условия целочисленности. Это решение приведено в Приложении 1. В первой строке введены нулевые начальные значения вектора х и целевая функция Q (x ) . После слова Given и перед функцией Minimize указаны ограничения. В результате получена нецелочисленная оптимальная численность по категориям:

х =

с фондом зарплаты Q = 135 у. е.

Из данного решения находится целочисленное решение методом ветвей и границ.

Сначала в полученном решении анализируется дробная величина х 4 =
= 1,143. Для нее можно задать два целочисленных значения: х 4 = 1 и х 4 = 2. Начинается построение дерева решений (Приложение 2). На дереве решений откладывается начальный нулевой узел. Затем он соединяется первым узлом х 4 , и из этого узла проводятся две ветви, соответствующие ограничениям: х 4 = 1 и х 4 = 2.

Для ветви с ограничением х 4 = 1 решается задача линейного программирования, данная в Приложении 1, с учетом этого ограничения.

В результате получено решение этой задачи. Переменная х 1 стала целочисленная, но переменная х 2 стала дробной х 2 = 0,9.

Для продолжения ветви создается узел х 3 и ветвь х 3 = 1. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1. С этими ограничениями задача имеет решение х Т =
= (1,938 1 1 1).

Для продолжения ветви создается узел х 1 и ветвь х 1 = 2. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1, х 1 = 2. С этими ограничениями задача имеет решение х Т = = (2 1 1 1).

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

В Приложении 2 приводится полное дерево возможных целочисленных решений, из которого следуют, что в задаче имеется 4 результативных решения.

Из результативных выбирается наилучшее и оно принимается как оптимальное целочисленное решение всей задачи с минимальной величиной Q (x ) . В нашем случае мы имеем два оптимальных целочисленных решения

Q (х) = 140,

x T = (2 1 1 1),

x T = (1 1 2 2).

Следовательно, издательская организация должна привлечь для набора текста двух работников высокой категории, одного работника средней категории, одного работника ниже средней категории и одного работника низкой категории. Возможен так же другой равнозначный вариант привлечения работников: один работник высокой категории, один работник средней категории, два работника категории ниже средней и два работника низкой категории. В обоих вариантах затраты будут минимальными и составят 140 ден. ед.

Скачать решение задачи:

Имя файла: 2.rar
Размер файла: 24.99 Kb

Если закачивание файла не начнется через 10 сек, кликните

Впервые метод ветвей и границ был предложен в 1960 г. в работе Лэнд и Дойг применительно к задаче целочисленного линейного программирования. Однако эта работа не оказала заметного непосредственного влияния на развитие дискретного программирования. Фактически «второе рождение» метода ветвей и границ связано с работой Литтла, Мурти, Суини и Кэрел , посвященной задаче коммивояжера; в этой же работе было впервые предложено и общепринятое теперь название метода «метод ветвей и границ». Начиная с этого момента появляется весьма большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех (да еще применительно к «классически трудной» задаче о коммивояжере) объясняется тем, что Литтл, Мурти, Суини и Кэрел первыми обратили внимание на широту возможностей метода ветвей и границ, отметили важность использования специфики задачи и сами весьма удачно этой спецификой воспользовались.

В § 1 настоящей главы излагается общая идея метода ветвей и границ; в § 2 - алгоритм Лэнд и Дойг для задачи целочисленного линейного программирования, в § 3 - метод Литтла и др. авторов для задачи коммивояжера.

§ 1. Идея метода ветвей и границ

1.1. Рассмотрим задачу дискретного программирования в следующей общей форме.

Минимизировать

при условии

Здесь G - некоторое конечное множество.

1.2. В основе метода ветвей и границ лежат следующие построения, позволяющие в ряде случаев существенно уменьшить объем перебора.

I. Вычисление нижней границы (оценки).

Часто удается найти нижнюю границу (оценку) целевой функции на множестве планов (или на некотором его подмножестве т. е. такое число что для имеет место

(соответственно для имеет место Разбиение на подмножества (ветвление). Реализация метода связана с постепенным разбиением множества планов на дерево подмножеств (ветвлением). Ветвление происходит по следующей многошаговой схеме.

0-й шаг. Имеется множество Некоторым способом оно разбивается на конечное число (обычно не пересекающихся) подмножестве шаг Имеются множества , еще не подвергавгпиеся ветвлению. По некоторому правилу (указанному ниже) среди них выбирается множество и разбивается на конечное число подмножеств:

Еще не подвергавшиеся разбиению множества

заново обозначаются через

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

III. Пересчет оценок. Если множество то, очевидно,

Поэтому, разбивая в процессе решения некоторое множество на подмножества

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

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

V. Признак оптимальности. Пусть

и план X принадлежит некоторому подмножеству Если при этом

то X - оптимальный план задачи (1.1) - (1.2).

Доказательство непосредственно следует из определения оценки.

Обычно этот признак применяется на некотором этапе ветвления (т. е., говоря формально, при ; см. п. II).

VI. Оценка точности приближенного решения. Пусть

Если X - некоторый план исходной задачи (т. е. ), то

Доказательство и здесь сразу следует из определения оценки.

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

1.3. Изложим формальную схему метода ветвей и границ.

0-й шаг. Вычисляем оценку . Если при этом удается найти такой план X, что

то X - оптимальный план.

Если оптимальный план не найден, то по некоторому способу разбиваем множество на конечное число подмножеств

и переходим к шагу.

1-й шаг. Вычисляем оценки Если при этом удается найти такой план X, что для некоторого и

то X - оптимальный план.

Если же оптимальный план не найден, то выбираем «наиболее перспективное» для дальнейшего разбиения множество по следующему правилу:

Разбиваем множество на несколько (обычно не пересекающихся) подмножеств.

Начало развитию подхода, получившего название метод ветвей и границ, положила работа Ленд и Дойг (1960). Это, скорее, даже не метод, а концепция или процедурная оболочка, на основе которой стали разрабатывать алгоритмы решения целочисленных задач различной природы. Ценность предложенной идеи стала особенно заметна после появления первого точного алгоритма решения задачи коммивояжера, построенного по схеме ветвей и границ (Литтл с соавторами, 1963). Метод можно применять как к полностью, так и частично целочисленным задачам.

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

Метод заключается в построении дерева задач, корнем которого является исходная задача, возможно без условия целочисленности (НЗ). Нижележащие задачи порождаются вышележащими так, что их допустимые множества (ДМ) являются непересекающимися подмножествами ДМ вышележащей задачи. Рост дерева происходит за счет перспективных ветвей. Перспективность определяется по оценке критерия терминальной задачи ветвиV ирекорду Z. ОценкаV – это значение критерия, заведомо не хуже оптимального, аZ – достигнутое в процессе решения значение критерия исходной задачи (в качестве начального может приниматься значение, заведомо хуже оптимального). Значит, задача будет порождающей только при условии, что ее оценка лучше рекорда. При этом уровень, на котором находится задача, не имеет значения.

Рассмотрим метод применительно к линейной целочисленной задаче. Хотя нет каких-либо ограничений на число задач, непосредственно порождаемых перспективной, в алгоритмах, как правило, используется разбиение на две задачи, то есть строится бинарное дерево (рис. 7.5). При этом для целочисленных множеств выполняются соотношения

Очевидно, что если, например,V 22 окажется хуже рекорда илиD 22 =, правая ветвь обрывается (говорят также, что она прозондирована). Если же оценкаV 22 будет лучше Z , производится ветвление: множествоD 22 разбивается на 2 подмножества. Решение завершится, когда все ветви будут прозондированы.

Вид оценки зависит от направленности критерия: при максимизации используется верхняя оценка, при минимизации – нижняя. Последующее изложение метода будет относиться к задаче на максимум.

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

Каким образом разбивать перспективное множество на подмножества;

Как определять верхнюю оценку критерия на рассматриваемом множестве.

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

Пусть известен диапазон возможных значений j -й переменной

0  х j  d j ,

которая в непрерывном оптимальном решении оказалась нецелочисленной и равной x j * . Тогда целочисленное значение этой переменной может достигаться либо в интервале 0  х j 
,либо в интервале
+1 х j  d j , где
- целая часть (рис. 7.6).

Это соответствует разбиению непрерывного множестваD н на два непересекающихся подмножества D 1 н и D 2 н , объединение которых не равно D н . В то же время такое разбиение целочисленного множества удовлетворяет соотношениям (7.9). При этом целочисленные множества, как исходное, так и порожденные, включены в соответствующие непрерывные множества. Следовательно, поиск целочисленного решения на непрерывном множестве даст тот же результат, что и на целочисленном. Легко увидеть, что приведенное выделение подинтервалов по одной переменной приводит к разбиению исходного множества на два подмножества при любом числе переменных.

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

Выбор начального значения рекорда зависит от ситуации:

если известно какое-либо целочисленное значение, то рекорд принимается равным критерию в этом решении;

при положительности всех коэффициентов критерия можно взять нулевое значение рекорда;

в иных случаях за начальное значение рекорда берется –М , где М- максимально представимое в компьютере число.

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

Таким образом, базовый алгоритм, реализующий метод ветвей и границ, включает следующие шаги.

Приведенный алгоритм является базовым, так как не включает однозначных правил выбора задачи из списка и ветвящей переменной. Для частично целочисленных задач при выборе переменной для ветвления исключаются непрерывные переменные.

Пример 7.3 . Применим алгоритм ветвей и границ к задаче

L= 9x 1 + 5x 2  max;

3x 1 - 6x 2  1;

5x 1 +2x 2  28;

 x j  0 , целые.

Отбрасывая условие цедочисленности, получаем непрерывную задачу, которую помещаем в список задач. Так как коэффициенты критерия положительны, начальное значение рекорда принимаем равным нулю. Берем из списка единственную задачу и решаем ее. Получаем оптимальное решение в вершине А (рис. 7.7):x 1 * =4,72; x 2 * =2,19 . Ветвление производим по переменнойx 1 . Добавляя к решенной задаче ограничение x 1 4, образуем задачу 2, а добавление x 1 5 дает задачу 3. Допустимые множества новых задач покзаны на рис. 7.7. Эти задачи помещаем в список задач. Решение задачи 2 достигается в точке В, а задачи 3 – в С. Весь ход решения исходной задачи представлен в виде дерева решений на рис. 7.10. Порядок решения задач из списка отражает счетчик итераций k . На 3-й итерации (задача 4) получено целочисленное решение со значением критерия 41 (точка D нарис. 7.8). Поэтому изменяется рекорд: Z =41.Задача 6 имеет нецелочисленное решение (вершина Е на рис. 7.9), задача 8 – целочисленное решение в точкеF. В результате после 7-й итерации рекорд становится равным 50.

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

Из приведенного дерева решений видно, что число задач в списке могло быть меньше при другом порядке решения задач. Действительно, если бы сначала были решены задачи правой ветви с рекордом Z= 50, то после решения задачи 2 не произошло бы ветвления, так как верхняя оценка оказалась бы ниже рекорда (V=L * =45,17<50).

Естественно возникает вопрос: а как на числе задач и дереве решений может отразиться выбор другой переменной для ветвления? Так, в нашем примере если после 1-й итерации произвести ветвление по переменнойx 2 , то получим дерево, показанное на рис. 7.11. Оно содержит на 2 задачи больше, чем на рис. 7.10. Конечно, оно может быть также другим при ином порядке решения задач.

Таким образом, число решаемых задач существенно зависит от выбора задачи из списка и переменной для ветвления.

Из алгоритма и приведенного примера следует, что ветвь обрывается по одной из трех причин:

неразрешимость задачи;

задача имеет целочисленное решение;

верхняя оценка не больше рекорда.

Теперь сделаем ряд замечаний относительно метода ветвей и границ. Как уже отмечалось, в базовом алгоритме не оговариваются правила выбора задачи и переменной. В большинстве программных реализаций метода используются правила, основанные на эвристических оценках перспективности задач и переменных. В некоторых пакетах, например, "ЛП в АСУ" предлагается несколько вариантов управления процессом решения: от автоматического до ручного, в котором пользователь может сам делать выбор как задачи, так и переменной. Кроме того, алгоритмы, основанные на методе ветвей и границ, могут существенно отличаться в связи с учетом особенностей класса задач. Например, для задачи коммивояжера, определение оценки значительно упрощено (не требуется решать непрерывную линейную задачу).

Метода ветвей и границ имеет преимущества в сравнении с методом отсечений:

накопление ошибок менее значительное, так как решение идет по разным ветвям;

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

при решении непрерывных задач размеры симплекс-таблиц не увеличиваются.

Недостатки метода ветвей и границ:

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

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

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

Голосование: 25, 14

Что это такое?

Иногда возникшую NP-полную задачу приходится решать. В таком случае, во-первых, иногда возможно сократить полный перебор так, что алгоритм, оставаясь в худшем случае экспоненциальным, будет работать за приемлемое время на реальных данных. Во-вторых, не точное решение, а некоторое приближение к нему может оказаться удовлетворительным. Алгоритмы, дающие такие решения, называются приближенными.

Способы решения "переборных" задач можно разбить на несколько общих методов улучшения полного перебора.

Методы решения труднорешаемых задач

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

Оценки качества приближенных алгоритмов

Пусть мы решаем оптимизационную задачу, то есть ищем объект с наибольшей или наименьшей стоимостью среди множества объектов, на которых задана функция стоимости. Обозначим оптимальное решение как С *. А решение, которое дает нам алгоритм как С.

Мы будем говорить, что алгоритм решает задачу с ошибкой не более чем в ρ (n) раз, если

Max(C ⁄ C *, C * ⁄ C) ≤ ρ (n)

Заметим, что поскольку максимум из двух взаимно обратных величин не меньше 1, то

Иногда удобнее использовать относительную ошибку, которая определяется как | C − C *| ⁄ C *

Мы будем говорить, что алгоритм имеет ошибку не более ε (n), если

| C − C *| ⁄ C * ≤ ε (n)

Легко проверить, что ε (n) может быть ограничена сверху через функцию ρ (n), а именно ε (n) ≤ ρ (n) − 1. В самом деле для задач на минимум это неравенство превращается в равенство. Для задач на максимум ε (n) = (ρ (n) − 1) ⁄ ρ (n) (далее нужно вспомнить, что ρ (n) ≥ 1.

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

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

Схема приближения называется полиномиальной, если для любого фиксированного ε > 0 время её работы не превосходит некоторого полинома от n . Схема приближения называется полностью полиномиальной, если время её работы ограничено некоторым полиномом от n и от 1 ⁄ ε .

Задача коммивояжера — полигон для испытания оптимизационных методов

Формулировка задачи коммивояжера (1934 г.):

Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2, 3, …, n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

В терминах теории графов задачу можно сформулировать так: имеется полный ориентированный граф G = (V , E), каждой дуге (u , v) которого сопоставлен вес c (u , v). Требуется найти в этом графе гамильтонов контур наименьшей стоимости.

Обратим внимание на детали, которые будут очень существенными для алгоритмов решения задачи:

1. В обеих формулировках предполагается c (u , v) ≥ 0; c (u , u) = ∞ для всех u , v ∈ V .
2. В наивной формулировке предполагается c (u , v) = c (v , u) для всех u , v ∈ V , т. е. граф можно считать неориентированным. Такая задача называется симметричной задачей коммивояжера. Однако, в общем случае, это необязательно.
3. В наивной формулировке предполагаем, что для всех u , v , w ∈ V с (u , v) ≤ c (u , w) + c (w , v) (неравенство треугольника), что нередко выполняется в практических задачах. Однако вообще говоря, это неверно.

Теорема

Пусть P ≠ NP , ρ ≥ 1. Тогда не существует полиномиального приближенного алгоритма, решающего общую (более того, симметричную) задачу коммивояжера с ошибкой не более чем в ρ раз.

Доказательство. Для доказательства заметим, что взяв произвольный граф G = (V , E) и сопоставив ему полный граф G ′ с функцией стоимости c (u , v) = 1, если (u , v) ∈ E и ρ | V | + 1 иначе. Убедимся, что наш полиномиальный алгоритм будет определять, есть ли в графе G гамильтонов цикл, что невозможно.

Метод ветвей и границ ("поиск с возвратом", "backtracking")

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

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

Рассмотрим дискретную экстремальную (для определенности — на минимум) задачу в общем виде:

Пусть задано дискретное множество A и определенная на нем функция f . Обозначим минимум функции f на X как F (X).

Требуется найти x 0 ∈ A: f (x 0) = F (A)

Замечание 1

Пусть A = A 0 ∪ A 1 ∪ … ∪ A k , A i ∩ A j = Ø, i ≠ j . Причем F (A) < F (A 0), т. е. на A 0 минимум не достигается.

Тогда справедливо следующее: F (A) = min { F (A i) | i ∈ 1: k }

Замечание 2

Пусть Φ — функция, заданная на совокупности подмножеств множества A так, что Φ (X) ≤ F (X) ∀ X ⊂ A

Пусть x * — произвольный элемент A и пусть f * = f (x *).

Тогда справедливо следующее: F (A) = min { f *, min { F (A i) | i ∈ 1: k , Φ (A i) ≤ f *} }

Эти два соображения позволяют предложить следующую технологию поиска минимума. Разобьем множество A на какие-либо подмножества A i и на каждом из них найдем нижнюю оценку Φ . Для элементов множества A будем вычислять значения функции f и запоминать наименьшее в качестве рекордного значения. Все подмножества, у которых оценка выше рекордного значения функции (f *), объединим в подмножество A 0 , чтобы в дальнейшем не рассматривать.

Теперь выберем какое-либо из множеств A i , i > 0. Разобьем это множество на несколько более мелких подмножеств. При этом мы будем продолжать улучшать рекордное значение f *. Этот процесс продолжается до тех пор, пока не будут просмотрены все множества A i , i > 0.

Более наглядно метод ветвей и границ (поиск с возвратом) можно объяснить с помощью дерева возможностей. Узлы такого дерева можно рассматривать как совокупности конфигураций (подмножества A i множества A), а каждый потомок некоторого узла представляет подмножество этой совокупности. Наконец, каждый лист представляет собой отдельную конфигурацию.

Пример 1. Задача коммивояжера (алгоритм Литтла)

Рассмотрим работу этого алгоритма на конкретном примере.

Пусть имеется граф, заданный матрицей смежности:

—	6	4	8	7	14
6	—	7	11	7	10
4	7	—	4	3	10
8	11	4	—	5	11
7	7	3	5	—	7
14	10	10	11	7	—

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

Приведем исходную матрицу по строкам

Исходная

—	6	4	8	7	14
6	—	7	11	7	10
4	7	—	4	3	10
8	11	4	—	5	11
7	7	3	5	—	7
14	10	10	11	7	—

Приведенная по строкам

—	2	0	4	3	10	|4
0	—	1	5	1	4	|6
1	4	—	1	0	7	|3
4	7	0	—	1	7	|4
4	4	0	2	—	4	|3
7	3	3	4	0	—	|7

Выделенные жирным шрифтом числа в исходной матрице — это идеальный тур, полученный лексикографическим перебором.

(Отметим, что сумма констант приведения есть 4 + 6 + 3 + 4 + 3 + 7 = 27)

А затем по столбцам:

—	0	0	3	3	6
0	—	1	4	1	0
1	2	—	0	0	3
4	5	0	—	1	3
4	2	0	1	—	0
7	1	3	3	0	—
—	—	—	—	—	—
0	2	0	1	0	4

(Отметим, что сумма констант приведения здесь есть 0 + 2 + 0 + 1 + 0 + 4 = 7, а всех констант: 27 + 7 = 34)

Теперь, тур, проходящий только через ребра нулевой стоимости, будет, очевидно, минимальным. Для того, чтобы определить его стоимость, прибавим к нулю только что вычисленную константу 34:

Таким образом, мы получили нижнюю оценку стоимости класса всех возможных туров. Т. е. минимальный тур в данной задаче не может стоить меньше, чем 34.

Назовем оценкой нуля в позиции (i , j) в матрице сумму минимальных элементов в i -й строке и j -м столбце (не считая сам этот ноль). Оценим теперь каждый ноль в приведенной матрице:

	1	2	3	4	5	6
1	—	0 1	0	3	3	6
2	0 1	—	1	4	1	0
3	1	2	—	0 1	0	3
4	4	5	0 1	—	1	3
5	4	2	0	1	—	0
6	7	1	3	3	0 1	—

Оценки, равные нулю, не указаны. Оценка k нуля, в позиции (i , j) означает буквально следующее: если в тур не будет включен путь из i в j (стоимостью 0), то придется доплатить как минимум k. Поэтому, можно разделить класс всех возможных туров на два: туры, содержащие ребро (i , j) и туры, не содержащие его. Для последних минимальная оценка увеличится на k .

Рассмотрим ребро, соответствующее нулю с максимальной оценкой. В данном случае это ребро (1, 2). Таким образом, как только что было замечено, класс всех туров разбивается на два: содержащих ребро (1, 2) и не содержащих его. Нижняя оценка стоимости второго класса туров увеличивается до 35. Чтобы определить оценку для первого класса туров удалим из матрицы строку 1 и столбец 2 (Обозначим ее как C [(1,2)]):

Т. к. матрицу удалось привести на 1 (по 1-му столбцу), то оценка класса туров с ребром (1, 2) увеличивается на 1 и становится равной 35.

Разбиение на классы и сами оценки можно представить в виде дерева:

Таким образом, класс (ВСЕ) был разбит на два и были вычислены соответствующие оценки.

Выберем теперь класс с наименьшей оценкой и повторим этот процесс для него. Затем из двух полученных классов выберем тот, у которого оценка минимальна и разобьем его. Так будем повторять до тех пор, пока не достигнем листа дерева. Т. е. пока не получим матрицу 0×0:

C [(1, 2); [−](a 1 , b 1); [−](a 2 , b 2); … [−](a k , b k)]

Где (каждое) −(x , y) означает, что матрица соответствует классу, не содержащему ребро (x , y) Удалив из обозначения матрицы элементы вида −(x , y), получим следующее:

(c 0 , d 0); (c 1 , d 1); … (c n , d n)

Вершина (5, 4) дерева будет соответствовать классу, содержащему ребра: (1, 2); (3, 1); (6, 5); (2, 6); (4, 3); (5, 4). Этот класс, очевидно, состоит из одного полного тура (1, 2, 6, 5, 4, 3, 1) со стоимостью = 36 (для полного тура его минимальная оценка равна точной стоимости)

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

Матрица, соответствующая классу туров, не содержащих ребро (1, 2), приведенная по второму столбцу, будет выглядеть так:

	1	2	3	4	5	6
1	—	—	0 3	3	3	6
2	0 1	—	1	4	1	0
3	1	1	—	0 1	0	3
4	4	4	0 1	—	1	3
5	4	1	0	1	—	0
6	7	0 1	3	3	0	—

Она была получена из матрицы, соответствующей классу всех туров путем установки прочерка (обозначающего бесконечную стоимость перелета) вместо элемента (1, 2). Т.е. с 1,2 = ∞. Обозначим ее как C [−(1,2)]

Т. к. максимальная оценка нуля 3 (элемент 1,3) получаем, что оценка для ветви −(1,3) равна 38.

Вычеркивая первую строку и первый столбец, получим матрицу, приводимую на 1 по четвертой строке. То есть оценка ветви −(1,2)(1,3) становится равной 36. Дальнейшее ветвление будем продолжать уже с учетом найденного рекордного значения (36):

Таким образом, вершин не осталось, перебор завершен. А найденное в ходе него рекордное значение и соответствующий ему тур — решение задачи.

Удовлетворительных теоретических оценок алгоритма Литтла и ему подобных нет, но практика показывает, что на современных машинах они позволяют решать задачу коммивояжера с количеством вершин ≈ 100. Кроме того, алгоритмы типа ветвей и границ являются эффективными эвристическими процедурами. Если нет возможности доводить их до конца.

Пример 2. Задача о размыкании контуров

Тот же подход можно применить к задаче о размыкании контуров. Постановка задачи:

Пусть задан граф G = (V , E), каждой дуге (u , v) которого сопоставлено положительное число c (u , v) — вес этой дуги.

Требуется найти E 0 ⊂ E так, чтобы граф (V , E 0) не имел контуров и сумма весов дуг (из E 0) была максимальной.

Рассмотрим вспомогательную задачу (обозначим ее (E , E *)) аналогичную только что сформулированной, но с дополнительным параметром — множеством E * ⊂ E из которого дуги удалять нельзя (при этом будем требовать, чтобы в графе (V , E *) не было контуров).

Если имеется задача (E , E *) то возможно все множество ее решений разбить на два класса следующим образом.

Рассмотрим дугу (u , v) ∈ E \ E * такую, что в графе (V , E * ∪ (u , v)) нет контуров.

Тогда множество решений задачи можно разбить на два:

1. множество решений задачи (E \ (u , v), E *)
2. множество решений задачи (E , E* ∪ (u , v))

Исходная задача о размыкании контуров, очевидно, является задачей (E , Ø).

Введем теперь функцию est(E , E 0) следующим образом:

1. если граф (V , E) не содержит циклов, то est(E , E 0) = 0
2. иначе, пусть E cyc — цикл, тогда: est(E , E 0) = est(E \ E cyc , E 0) + c cyc , где c cyc = min{ c (u , v) | (u , v) ∈ E cyc \ E 0 } (т. е. мин. вес, которым можно разомкнуть этот цикл)

Несложно показать, что

V (E , E 0) ≥ est(E , E 0),

где v (E , E 0) — минимум суммы весов дуг, удаление которых из E \ E 0 размыкает все контуры графа.

Метод локальных улучшений ("локальный поиск")

Идея этого метода заключается в том, что для каждого решения экстремальной задачи x ∈ X определяется окрестность близких решений A (x) и на каждой итерации вычислительного процесса при заданном текущем решении x делается попытка найти в его окрестности решение, которое имело бы лучшее значение целевой функции. Если такое решение удается найти, оно само становится текущим решением, если нет — поиск заканчивается.

Более конкретно стратегия локального поиска такова:

• Начните с произвольного решения
• Для улучшения текущего решения примените к нему какое-либо преобразование из заданной совокупности преобразований. Это улучшенное решение становится текущим решением
• Повторяйте указанную процедуру до тех пор, пока ни одно из преобразований в заданной совокупности не позволит улучшить текущее решение

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

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

Рассмотрим точный алгоритм нахождения минимального остовного дерева в графе с помощью метода локального поиска. Локальные преобразования будут таковы: мы берем то или иное ребро, не относящееся к текущему остовному дереву и добавляем его к дереву (получая цикл), а затем убираем из этого цикла одно ребро (с наивысшей стоимостью). Это продолжается, пока все ребра вне дерева не будут иметь наивысшую стоимость среди всех ребер в цикле, который образуется при добавлении его к дереву (одна эта проверка требует времени O (| V || E |)). Этот алгоритм работает медленнее, чем алгоритмы Прима и Крускала, и служит примером нерационального использования локального поиска для не NP-полных задач.

Пример 2. Задача коммивояжера ("двойной выбор")

Простейшее преобразование, которым можно воспользоваться в симметричной задаче коммивояжера, является так называемый "двойной выбор" . Он заключается в том, что мы выбираем любые два ребра (например (a , b) и (c , d)), удаляем их и "перекоммутируем" соединявшиеся ими точки так, чтобы образовался новый маршрут. Если сумма стоимостей двух новых ребер оказалась меньше, чем двух старых, то мы нашли улучшенный маршрут.

Рассмотрим тот же граф, для которого мы строили остовное дерево. Выберем в качестве начального маршрута (a , b , c , d , e) и применим к нему "двойной выбор". Легко убедиться, что на рисунке "в" нельзя удалить ни одну пару ребер, выгодно заменив её другой.

Двойной выбор можно обобщить на k -выбор. В этом случае мы удаляем до k ребер и "перекоммутируем" оставшиеся элементы в любом порядке, пытаясь получить маршрут. Мы, вообще говоря, не требуем, чтобы удаляемые ребра были несмежными.

Легко убедиться в том, что количество различных преобразований, которые нужно рассмотреть при k -выборе равно O (| V | k). Однако время, требуемое для получения какого-либо оптимального маршрута, может оказаться значительно больше.

На практике очень эффективным является "выбор с переменной глубиной". Он с большой вероятностью обеспечивает получение оптимального маршрута для | V | = 40 − 100.

Пример 3. Задача размещения блоков

Формулировка задачи одномерного размещения блоков: требуется упорядочить вершины неориентированного графа G = (V , E) с весами на ребрах c (u , v), пронумеровав их числами 1 … n так, чтобы минимизировать ∑ i , j = 1… n | i − j | c (v i , v j); n = | V |.

Вершины графа обычно называют "блоками", а веса интерпретируют как количество "проводов" между блоками. Тогда суть задачи становится понятна: требуется расположить элементы на прямой так, чтобы длина проводов, требуемая для их соединения была минимальной.

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

Для нахождения локально-оптимальных решений задачи размещения блоков можно использовать такие локальные преобразования:

1. Произвести взаимную перестановку смежных блоков v i и v i +1 , если результирующий порядок имеет меньшую стоимость. Пусть

   L (j) = ∑ k =1… j −1 c (v k , v j);
   R (j) = ∑ k = j +1… n c (v k , v j).

   Улучшение можно выполнить, если

   L (i) − R (i) + R (i +1) − L (i +1) + 2 c (v i , v i +1) < 0

2. Взять блок v i и вставить его между некоторыми блоками v i и v i +1 при некоторых значениях i и j .
3. Выполнить взаимную перестановку двух блоков v i и v j .

Как и в задаче коммивояжера мы не в состоянии точно оценить время, необходимое для нахождения локального оптимума. Можно показать, что, если ограничиться преобразованием (1 ), времени O (| V |) будет достаточно, чтобы проверить, является ли выполняемое преобразование улучшающим, и вычислять L (i) и R (i). Для преобразований (2 ) и (3 ) это время увеличивается до O (| V | 2). Но это не есть оценка времени нахождения локального оптимума, так как каждое улучшение может создавать возможности для новых улучшений.

Приближенные и эвристические методы

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

В эвристических методах для выбора элементов решения используются те или иные, кажущиеся естественными рекомендательные правила выбора, эвристики. Часто такие правила комбинируются с условием жадности выбора: сделанный выбор в дальнейшем не пересматривается. Более мощной разновидностью такого подхода является сокращенный поиск, в котором дерево вариантов, знакомое нам по методу ветвей и границ, искусственно сокращается исходя из некоторых правил, правдоподобных, но формально не обоснованных.

Пример 1. Задача коммивояжера (деревянный алгоритм)

Рассмотрим три эвристических алгоритма, решающих симметричную задачу коммивояжера с неравенством треугольника с ошибкой не более чем в два раза (ρ = 2).

Первый из них, так называемый деревянный алгоритм, состоит в следующем: построим для нашего графа минимальное покрывающее дерево с помощью алгоритма Прима, а затем совершим обход дерева в порядке root-left-right , удаляя повторяющиеся вершины.

Время работы этого алгоритма равно Θ(E) = Θ(V 2).

Пример 1. Задача коммивояжера (жадный алгоритм и алгоритм Карга-Томпсона)

Самый очевидный алгоритм решения задачи коммивояжера — жадный: из текущего города иди в ближайший из тех, куда ещё не ходил. Если выполняется неравенство треугольника, нетрудно доказать, что этот алгоритм ошибается не более, чем в два раза. Трудоемкость этого алгоритма O (V 2).

Алгоритм Карга-Томпсона (эвристика ближайшей точки) чуть менее очевиден: сначала возьмем две ближайшие вершины (вырожденный тур), затем в цикле по всем ребрам уже построенного тура для каждого ребра (u , v) выберем из свободных вершин такую w , чтобы c (u , w) + c (w , v) − c (u , v) было минимальным и включим w в тур между u и v . Для этого способа также ρ = 2, однако его трудоемкость составляет уже O (V 3).

Пример 2. Задача о вершинном покрытии

Напомним, что вершинным покрытием неориентированного графа G =(V , E) мы называем некоторое семейство его вершин V ′ с таким свойством: для всякого ребра (u , v) графа G хотя бы один из его концов u или v содержится в V ′. Размером вершинного покрытия считаем количество входящих в него вершин.

Задача о вершинном покрытии состоит в нахождении вершинного покрытия минимального размера. Эта задача NP-трудна, однако приведенный ниже простой алгоритм решает её с ошибкой не более, чем в два раза.

Пусть С — это уже построенная часть вершинного покрытия, а E ′ содержит непокрытые ребра графа. На каждом шаге мы берем ребро из E ′ и добавляем его концы u и v в C , а из E ′ изымаем все ребра имеющие своим концом u или v . И так пока множество E ′ не станет пустым. Время работы этого алгоритма есть O (E).

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

Дано конечно множество X и семейство его подмножеств F . При этом:

X =∪ S ∈ F S

Мы ищем минимальное число подмножеств из F , которые вместе покрывают множество X , т. е. семейство С наименьшей мощности, для которого:

X =∪ S ∈ C S

Такое семейство С будем называть покрытием множества X . Например, на рисунке черные кружки — элементы множества X , контуры — подмножества из F . Три светлых сплошных контура составляют минимальное покрытие, жадный алгоритм дает покрытие мощностью на единицу больше (включает ещё и пунктирный контур).

Мы будем решать задачу с помощью жадного приближенного алгоритма. Пусть множество U содержит ещё не покрытые элементы, а семейство C — уже включенные в покрытие подмножества. На каждом шаге производится жадный выбор: в качестве S берется множество, покрывающее наибольшее число ещё не покрытых элементов.

Так происходит, пока U не пусто. Трудоемкость алгоритма составляет O (| X |·| F |·min(| X |,| F |)).

Размер покрытия, даваемого этим алгоритмом, превосходит минимально возможный не более чем в H (max{| S |: S ∈ F }) раз (где H (d) — сумма первых d членов гармонического ряда) или, что тоже самое, в (ln| X | + 1) раз.

Псевдополиномиальные алгоритмы

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

Пример 1. Задача о суммах подмножеств ("табличный" алгоритм)

Пусть задана пара (S , t), где S = { x 1 , x 2 , …, x n } представляет собой множество положительных целых чисел, а t — положительное целое число. Требуется отыскать среди подмножеств множества S , сумма которых не превосходит t , такое, у которого сумма ближе всего к t .

Пусть | S | = n . Обозначим (k , w) — задачу, в которой имеется k первых чисел из S и нужно набрать сумму w . Таким образом исходная задача — это задача (n , t).

Для решения задачи построим таблицу T [ n , t + 1], в клетку T [ i , j ] которой будем записывать оптимальное решение задачи (i , j).

Первый столбец заполним нулями. Первую строку заполним сначала нулями, а начиная с клетки (1, x 1) — числами x 1 . Клетку T [ i , j ] (i , j > 1) будем заполнять по правилу:

1. Если j − x i > 0, то y:= T [ i − 1, j − x i ], иначе y:= 0;
2. T [ i , j ] := max(T [ i − 1, j ], y + x i)

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
3	0	0	0	3	3	3	3	3	3	3	3	3	3	3
5	0	0	0	3	3	5	5	5	8	8	8	8	8	8
7	0	0	0	3	3	5	5	7	8	8	10	10	12	12
9	0	0	0	3	3	5	5	7	8	9	10	10	12	12
11	0	0	0	3	3	5	5	7	8	9	10	11	12	12

S = {3, 5, 7, 9, 11} t = 13;

Таблица примет такой вид. Ответ: нет подмножества весом 13, ближе всего снизу 12.

Условие (2) говорит о том, что оптимальная сумма может достигаться либо без использования x i (T [ i − 1, j ]), либо если x i входит в сумму (y + x i). В этом случае его надо прибавить к решению задачи (i − 1, j − x i), что и сохраняется в переменной y в условии (1). Из получившейся таблицы можно узнать и состав оптимальной суммы.

Трудоемкость этого алгоритма составляет O (n t) операций. Таким образом, если t будет велико, можно будет все числа поделить, к примеру, на 10, округлить и получить приближенный алгоритм.

Пример 2. Задача о суммах подмножеств ("списковый" алгоритм)

Пусть L — набор чисел, а x — некоторое число, тогда через L + x обозначим набор чисел, который получится, если ко всем элементам L прибавить x . В этом алгоритме также используется тот факт, что x i может как входить в сумму, так и не входить, то есть:

L i = L i −1 ∪ (L i −1 + x i)

Выкидывая из списка элементы, большие t получим L n — упорядоченный список всех возможных удовлетворяющих нас сумм подмножеств S . Остается взять максимальный (последний) элемент, чтобы получить решение задачи. Список L n может содержать до 2 n элементов (т. е. алгоритм экспоненциален), однако, т.к. все элементы различны, их не может быть более t . Налицо псевдополиномиальность.

Схемы приближения

В связи с приближенными алгоритмами возникает вопрос: нельзя ли постепенно усложняя приближенный алгоритм, получать все более точное решение? Такие алгоритмы есть и, как мы уже говорили, они называются схемами приближения. Нужно заметить, что это большая редкость: обычно для труднорешаемой задачи известен простой алгоритм с плохой точностью, перебор на другом конце и ничего посередине.

Мы рассмотрим две схемы приближения для задачи о сумме подмножеств. Одна из них получается из "спискового" алгоритма, а другая называется алгоритмом Джонсона.

Пример 1. Задача о суммах подмножеств (полностью полиномиальная схема приближения)

Такая схема получается из "спискового" алгоритма, если хранить список L в сокращенной форме. Список L ′ называется δ -сокращением списка L , если L ′ является частью L и

∀ y ∈ L ∃ z ∈ L ′: z ≤ y , (y − z) ⁄ y ≤ δ

Например для δ = 0,1 и L = <10, 11, 12, 15, 20, 21, 22, 23, 24, 29> список L ′ = <10, 12, 15, 20, 23, 29> является δ -сокращением. Сокращение упорядоченного списка из m элементов требует Θ (m) операций. Таким образом, можно доказать, что "списковый" алгоритм, хранящий вместо полного списка сокращенный является полностью полиномиальной схемой приближения.

Пример 2. Задача о суммах подмножеств (алгоритм Джонсона)

Алгоритм, кроме множества S и числа t принимает на вход целочисленный параметр m > 2. Назовем i -е число большим, если x i > t ⁄(m +1). Описание алгоритма:

1. Перебрать все подмножества из больших чисел и найти множество больших чисел с суммой t ′: t ′ < t , Δ = t − t ′ min
2. Если Δ = 0, алгоритм закончен.
3. Перебрать все малые числа в порядке убывания. Если очередное x i ≤ Δ , то t ′:= t ′ + x i , Δ := Δ − x i ;
4. Когда перебор по малым числам закончен, выдать t ′ в качестве ответа.

Пусть k — количество больших чисел. Тогда можно доказать, что количество подходящих нам подмножеств из больших чисел составляет O (k m) ≤ O (n m). Таким образом, перебор имеет полиномиальную, возрастающую с m сложность. Корме того, можно показать, что:

T ′⁄ t ≥ 1 − 1 ⁄ (m + 1) 1 − 1 ⁄ (m + 1) ≤ t ′⁄ t* ≤ 1

то есть относительная погрешность ε = 1⁄ (m +1). Таким образом, эта схема приближения является полиномиальной, но не является полностью полиномиальной.

Метод случайного поиска

Обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать "рекорд", т. е. наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.

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

Пожалуйста. На запрос "метод случайного поиска" поисковик Google анонсирует более 300000 ссылок. Этой информации должно хватить..........

Благодарю за статью, разобрался с алгоритмом Литтла. Хотел запомнить сайт и был удивлен, увидев домен родного университета:)

Про запрет переходов выше замечено верно - хотелось бы видеть здесь пояснения.

Спасибо за понятное разъяснение алгоритма Литтла. Но не учтена важная деталь: при выборе следующего ребра нужно учитывать, чтобы путь из набора ребер последовательно охватывал все точки. Так как ребра добавляем в случайном порядке, то приходится отслеживать наличие микроциклов (например выбрали ребро 1,0 - значит 0, 1 уже нельзя выбирать, или выбрали 0,1 и 1,2 - тогда нельзя выбирать 2,0 и 2,1 и т.д.), что отследить не так уж и просто. Я реализовал алгоритм на C#, циклы отслеживал с помощью специального класса, который содержал набор микроциклов и вычеркивал запрещенные ребра при добавлении в него новых и ребер и восстанавливал ребра при удалении ребер.

Реализация алгоритма оказалась очень сложна на практике, а его отладка просто ад. Код занял 512 строк. 20 точек обрабатывает за 0.1 - 10 секунд - длительность сильно зависит от входного набора. Большее количество уже за адекватное время не решает. Простейший переборщик у меня находит решение для 13 вершин за 1 секунду.

Если нужна реализация алгоритма на C# - пишите на почту [email protected].

Решение задачи коммивояжера методом ветвей и границ (алгоритм Литтла)

http://igorvn.ucoz.ru/load/kursovye/kommivojazher/2-1-0-15

Метод Литла работает только на небольшом количестве точек поэтому во всех примерах их не более 10 Начиная 15 точек он дает приближенный результат 1-2 % больше минимального и это заложено в порядке определения каждого хода (редукции) непонятно на каком основании это делается.Ведь формально мы получаем другую матрицу.

Высылаю вам "Русский метод" для подтверждения моего комментария.

Благодарим. Не сомневаемся в Вашей добросовестности и компетентности. Но файлы *.doc мы не размещаем. Если выложите его содержимое в общедоступное место со статусом постоянного хранения и включите ссылку в текст своего нового комментария, опубликуем для всеобщего обозрения.

Всем, кто хочет узнать про все теоретические ошибки метода Литтла, прошу сначала объяснить себе, что такое редукция и на каком это математическом основании оно проводится. Кроме того, Русский метод, разработанный мной, могу выслать совершенно бесплатно. Мой email: [email protected]

ВВЕДЕНИЕ.................................................................................................. 3

1. ..…………….4

2. МЕТОД ВЕТВЕЙ И ГРАНИЦ ………………………………………..6

2.1 Алгоритм метода ветвей и грани ц…………………………………....10

ЗАКЛЮЧЕНИЕ………………………………………………………….14

СПИСОК ЛИТЕРАТУРЫ………………………………………… ………….15

ВВЕДЕНИЕ

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче комивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.

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

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

1. МЕТОД ВЕТВЕЙ И ГРАНИЦ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ. ОСНОВНЫЕ ПОНЯТИЯ

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

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

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

1. Количество целочисленных переменных уменьшать насколько возможно. Например, целочисленные переменные, значения которых должно быть не менее 20, можно рассматривать как непрерывные.

2. В отличие от общих задач ЛП, добавление новых ограничений особенно включающих целочисленные переменные, обычно уменьшают время решения задач ЦП.

3. Если нет острой необходимости в нахождении точного оптимального целочисленного решения, отличающегося от непрерывного решения, например, 3%. Тогда реализацию метода ветвей и границ для задачи максимизации можно заканчивать, если отношение разницы между верхней и нижней границ к верхней границы меньше 0,03.

Метод ветвей и границ можно применять для решения задач нелинейного программирования.

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

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

2. МЕТОД ВЕТВЕЙ И ГРАНИЦ

Одним из широко распространенных методов решения целочислен­ных задач является метод ветвей и границ, который может быть ис­пользован как для задач линейного программирования, так и для задач, не сводимых к задачам линейного программирования. Рассмотрим идею метода ветвей и границ на примере общей задачи дискретного про­граммирования

f(X) -> max,

Х€D,

где D - конечное множество.

Сначала найдем оценку £(D) (границу) функции f(X), X е D: f(X) ≤ £(D) для V X е D. Если для некоторого плана Х° задачи справедливо равенствоf(X0) = £(D), то Х° = X* является решением задачи. Если указанное условие не выполняется, то возмож­но разбиение (ветвление) множества D на конечное число непересека­ющихся подмножеств D1i: ỤD1i. = D, ∩D1i = Ө, и вычисление оценки £(D1i) (границ), 1≤i≤m (Рисунок 2.1)

Рисунок 2. 1

Если для некоторого плана X1i е Di1, 1 ≤ / ≤ m выполняется условие f(Xkl)= £(D1k)≥ £(D1i), 1≤i≤m то Xk1=X* является оптимальным планом (решением) задачи (7.9)-(7.10).

Если такого плана нет, то выбирается подмножество Dkl с наиболь­шей оценкой £(D1i) и разбивается на конечное число непересекающихся подмножеств D2kj: UD2kj=D1k, ∩D2kj=Ө. Для каждого подмножества находится оценка £(D2kj), 1≤j≤n (Рисунок 2.2)

Рисунок 2.2

Если при этом найдется план X2j е D2kJ, 1 ≤j ≤n, такой, что f(X2r)= £(D2kr)≥ £(D2kj), 1≤j≤n, то X2r= X* является решением задачи. Если такого плана нет, то процедуру ветвления осуществля­ют для множества D2kj с наибольшей оценкой £(D2kj) , 1≤j≤n. Способ ветвления определяется спецификой конкретной задачи.

Рассмотрим задачу, которую можно свести к задаче целочисленного линейного программирования.

Пример.

Контейнер объемом 5 м3 помещен на контейнеровоз грузо­подъемностью 12 т. Контейнер требуется заполнить грузом двух наиме­нований. Масса единицы груза mj (в тоннах), объем единицы груза Vj (в м3), стоимости Cj (в условных денежных единицах) приведены в таблице 2.1.

Таблица 2.1

Вид груза у			С j

Требуется загрузить контейнер таким образом, чтобы стоимость пе­ревозимого груза была максимальной.

Решение. Математическая модель задачи имеет вид

Z(X) = 10x1+12x2→max,

3x1+x2≤12,

x1+2x2≤5

x1≥0

x2≥0

x1, x2- целые числа

где x1, x2 - число единиц соответственно первого и второго груза.

Множество планов этой задачи обозначим через D - это множество целых точек многогранника ОАВС (Рисунок 2.3).

Рисунок 2. 3

Сначала решаем задачу без условия целочисленности, получим оценку множества D - значение функции Z(X) на оптималь­ном плане Х° = (19/5, 3/5).

Точка X не является оптимальным планом задачи. По­этому в соответствии с методом ветвей и границ требуется разбить множество D на непересекающиеся подмножества. Выберем первую нецелочисленную переменную x1=19/5=34/5 и разобьем множество D на два непересекающихся подмножества D11 и D22. Линии x1=3 (L3) и x4= (L3) являются линиями разбиения.

Рисунок 2. 4

L \

Найдем оценки £(D11) и £(D12), для чего решим задачи линейного программирования.

Z(X)=10x1+12x2→max,

3x1+x2≤12

x1+2x2≤5

x1≤3

x1≥0, x2 – целые числа

Z(X)=10x1+12x2→max,

3x1+ x2≤12

x1+2x2≤5

x1≥4

x1≥0, x2 – целые числа

Например, графическим методом:

X11eD11→X01= (3,1); £(D11)=42; X12eD12→X02= (4,0); £(D12)=40.

Результат ветвления приведен на Рисунок 2.5

Рисунок 2. 5

План X01 удовлетворяет условиям задачи, и для него выполняется условие: Z(X11)= £(D11)=42 > £(/)/) = 42 >£(D12) = 40. Следовательно, план X°1= (3, 1) является решением задачи (7.11)-(7.13), т. е. надо взять три единицы первого груза и одну единицу второго груза.

2.1 Алгоритм метода ветвей и границ

· Находим решение задачи линейного программирования без учета целочисленности.

· Составляет дополнительные ограничения на дробную компоненту плана.

· Находим решение двух задач с ограничениями на компоненту.

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

Алгоритм действия метода ветвей и границ

Первоначально находим, к примеру, симплекс-методом оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax = F(X0).

Если же среди компонент плана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Покажем, как это можно сделать, предварительно отметив, что F(X0) ³ F(X) для всякого последующего плана X в связи с увеличением количества ограничений.

Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу font-size:14.0pt">font-size:14.0pt">Найдем решение задач линейного программирования (5) и (6). Очевидно, здесь возможен один из следующих четырех случаев:

1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.

2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (5) и (6).

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

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

3.2. Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (5) и (6).

4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (5) и (6).

Общий алгоритм решения задач с помощью метода границ и ветвей, его суть

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х0, а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (5) и (6). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.

Итак, процесс нахождения решения задачи целочисленного программирования методом ветвей и границ включает следующие основные этапы:

1. Находят решение задачи линейного программирования.

2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане является дробным числом.

3. Находят решение задач (5) и (6), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.

4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (5) и (6), и находят их решение.

Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(4) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

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

Пример использования метода ветвей и границ

В качестве примера к методу ветвей и границ рассмотрим функцию z=4х1+х2+1®max при ограничениях:

font-size:14.0pt">Пусть Х0 = (0; 0), z0 = 1 - «оптимальное» решение. Выполним 1-й этап общего алгоритма и найдем с помощью симплекс-метода, а затем и двойственного симплекс-метода (см. Приложение 1) X1, исходя из ограничений Итак, X1 = (3; 0,5; 0; 1; 0; 2,5), z1= 13,5. Так как z1 дробное, то «оптимальным» так и остается план Х0,

Согласно 2-му пункту нашего плана, составим 2 новых системы ограничений для:

https://pandia.ru/text/79/453/images/image012_25.gif" alt="Описание: http://*****/images/paper/93/79/4327993.png" width="108" height="98"> .

Выполним 3-й пункт алгоритма. Для начала, решим задачу с помощью табличного процессора Microsoft Excel (Приложение 2) и получим X2 = (2; 1) z2= 10. Так как z2 ≥ z0, «оптимальным» становится план Х0.

Решим задачу. Из последнего уравнения очевидно, что x2 = 0. Отсюда следует, что x1 = 3 (максимально возможное). Тогда Х3 = (3; 0), z3 = 13, а следовательно, данный план является оптимальным (теперь уже без кавычек).

Нам не пришлось выполнять 4-й пункт нашего алгоритма в связи с тем, что оптимальное решение найдено, переменные целочисленные. Пример, в котором всё складывается не так просто, приведен в Приложении 3.

ЗАКЛЮЧЕНИЕ

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

Задачи такого типа весьма актуальны, так как к их решению сводится анализ разнообразных ситуаций, возникающих в экономике, технике, военном деле и других областях. Эти задачи интересны и с математической точки зрения. С появлением ЭВМ, ростом их производительности повысился интерес к задачам такого типа и к математике в целом.

СПИСОК ЛИТЕРАТУРЫ

1. А. Схрейвер. Теория линейного и целочисленного программирования: в 2-х томах.; перевод с английского. 1991г. 360с.

2. Т. Ху. Целочисленное программирование и потоки в сетях.; перевод с английского. 1974г.

3. , . Высшая математика: Математическое программирование. Ученик - 2-е издание. 2001г. 351с.

4. . Математическое программирование: Учебное пособие – 5-е издание, стереотип-М:ФИЗМАТ, 2001г.-264с.

5. , .: Экономико-математические методы и прикладные модели: Учеб. пособие для вузов/ЮНИТИ, 1999г.-391с.

6. , ; под ред. Проф. . : Исследование операций в экономике; учеб. Пособие для вузов.

Приложение 2

Решение задачи z = 4х1 + х2 +1 ® max при ограничениях:

с помощью табличного процессора Microsoft Excel.