Задача коммивояжера - метод ветвей и границ. Метод ветвей и границ целочисленного программирования. Основные понятия

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

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

Алгоритм решения:

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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

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

Одним из широко распространенных методов решения целочисленных задач является метод ветвей и границ, впервые, он был предложен Ленд и Дойг в 1960 г.

ветвь граница линейное программирование

Метод ветвей и границ

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

1. Процесс начинают с решения задачи симплексным или графическим методом без учета требования на целочисленность переменных. Эту задачу называют ЗЛП-0. Если все переменные оптимального плана целые, то этот план также является оптимальными для задач целочисленного программирования.

2. Если некоторая переменная, не получила целочисленного значения, то производится ветвление на две новые задачи ЗЛП-1, ЗЛП-2. Одна из задач ЗЛП-1 представляет собой задачу ЗЛП-0, дополненную ограничением где - целая часть числа. Вторая образуется путем добавления к задаче ЗЛП-0 ограничения. Следует отметить, что выбор целочисленной переменной может быть произвольным определяться следующим образом:

по возрастанию или убыванию индексов;

переменная представляет важное решение принимаемое в рамках данной задачи;

коэффициент в целевой функции при этой переменной существенно превосходит все остальные.

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

Процесс решения можно представить в виде дерева, в котором вершина ЗЛП-0 отвечает начальному плану решения задачи, а каждая из соединенных с ней ветвью вершин отвечает оптимальному плану следующей задачи.

Рассмотрим следующий пример. Максимизировать целевую функцию

при ограничениях

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

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

Обозначим эту задачу линейного программирования ЗЛП-0.

На рисунке 1.1 штриховкой выделен многоугольник решений данной задачи. Максимальное значение достигается в точке Решение не является целочисленным.

Следующий шаг метода ветвей и границ состоит в ветвлении по одной из целочисленных переменных, имеющих дробное значение, например. Для этого добавим к задаче ЗЛП-0 два новых ограничения и Этими ограничениями удаляется интервал = в котором нет целых значений. Таким образом, в процессе ветвления создаются две новые задачи ЗЛП-1 и ЗЛП-2.

Рисунок 1.1 Решение задачи ЗЛП-0

2. Решим задачу ЗЛП-1 графически.

На рисунке 1.2 изображена допустимая область задачи ЗЛП-1. Максимальное значение достигается в точке. Решение задачи нецелочисленное.

Рисунок 1.2 Решение задачи ЗЛП-1

3. Решим задачу ЗЛП-2 графически.

В данном случае множество допустимых решений пусто (рисунок 1.2). Система ограничений несовместна, и задачу ЗЛП-2 можно исключить из дальнейшего рассмотрения.

Рисунок 1.3 Решение задачи ЗЛП-2

Теперь продолжим исследование задачи ЗЛП-1, поскольку значение нецелое. Произведем еще одно ветвление, путем введения ограничений и. В результате получаем две новые задачи ЗЛП-3 и ЗЛП-4.

Впервые метод ветвей и границ был предложен в 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 - оптимальный план.

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

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

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP ). Также встречается название «задача о бродячем торговце ». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

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

Общий план решения задачи коммивояжера

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

Построение матрицы с исходными данными.
Нахождение минимума по строкам.
Редукция строк.
Нахождение минимума по столбцам.
Редукция столбцов.
Вычисление оценок нулевых клеток.
Редукция матрицы.
Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
Вычисление итоговой длины пути и построение маршрута.

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

Подробная методика решения задачи коммивояжера

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

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

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

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

Находим минимальное значение в каждой строке (di ) и выписываем его в отдельный столбец.

3. Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка .

4. Нахождение минимума по столбцам

5. Редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка .

6. Вычисление оценок нулевых клеток

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

И так по всем нулевым клеткам:

7. Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М ». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку, соответствующую обратному пути , ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

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

Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9 .

9. Вычисление итоговой длины пути и построение маршрута

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

В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4 .

Общая длина пути: L = 30 .

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

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

Решение задачи коммивояжера онлайн

Галяутдинов Р.Р.

ВВЕДЕНИЕ.................................................................................................. 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).

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

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х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.