Целочисленное линейное программирование метод ветвей и границ

Целочисленное линейное программирование метод ветвей и границ

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

Пример №1 . В задаче методом Гомори (или методом ветвей и границ) найти оптимальные решения задач целочисленного линейного программирования. Дать геометрическую интерпретацию процесса решений задач.
Z=3x1 + 2x2 → max
при ограничениях:
x1 + x2 ≤ 13
x1 — x2 ≤ 6
-3x1 + x2 ≤ 9
x1≥0, x2 ≥0
x1, x2 – целые числа.

Пример №2 .
5x1 + 2x2 ≤ 14
2x1 + 5x2 ≤ 16
x1 , x2 – целые числа
Z = 3x1 + 5x2 → max
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Область допустимых решений представляет собой треугольник.
Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
5x1+2x2≤14
x1≥2

Решив систему уравнений, получим: x1 = 2, x2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16

Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
2x1+5x2≤16
x1≤1

Решив систему уравнений, получим: x1 = 1, x2 = 2.8
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2.8 = 17

Решим графически задачу 111 как задачу ЛП.
5x1+2x2≤14 (1)
2x1+5x2≤16 (2)
x2≥3 (3)
x1≥1 (4)
x1≥0 (5)
x2≥0 (6) Задача не имеет допустимых решений. ОДР представляет собой пустое множество

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

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

Суть метода ветвей и границ – в направленном частичном переборе допустимых решений. Будем рассматривать задачу линейного программирования. Вначале она решается без ограничений на целочисленность. При этом находится верхняя граница F(x), так как целочисленное решение не может улучшить значение функции цели.

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

Ветвление производится последовательным введением дополнительных ограничений. Пусть xk – целочисленная переменная, значение которой в оптимальном решении получилось дробным. Интервал [βk] ≤ xk ≤ [βk ]+1 не содержит целочисленных компонентов решения. Поэтому допустимое целое значение xk должно удовлетворять одному из неравенств xk≥[βk]+1 или xk≤[βk ]. Это и есть дополнительные ограничения. Введение их в методе ветвей и границ на каждом шаге порождает две не связанные между собой подзадачи. Каждая подзадача решается как задача линейного программирования с исходной целевой функцией. После конечного числа шагов будет найдено целочисленное оптимальное решение.

Читайте также:  Как добавить фон в презентацию powerpoint

Применение метода ветвей и границ рассмотрим на конкретном примере.

Пример 1. Методом ветвей и границ найти максимальное значение функции F(x) = 2x1 + 3x2 при ограничениях

1-й шаг метода ветвей и границ. Решается задача линейного программирования с отброшенными условиями целочисленности с помощью симплекс-метода (табл. 1 – 3).

По данным табл. 3 запишем оптимальное нецелое решение

4 6 базисные переменные Свободные члены Небазисные переменные x1 x2 x3 24 3 4 x4 22 2 5 F -2 -3

Таблица 2 — симплекс-таблица для задачи ЛП

базисные переменные Свободные члены Небазисные переменные
x1 x4
x3 32/5 7/5 -4/5
x2 22/5 2/5 1/5
F 66/5 -4/5 3/5

Таблица 3 — симплекс-таблица для задачи ЛП

базисные переменные Свободные члены Небазисные переменные
x3 x4
x1 32/7 5/7 -4/7
x2 18/7 -2/5 3/7
F 118/7 4/7 1/7

Графическая интерпретация задачи приведена на рис. 1. Здесь ОДЗП представлена четырехугольником ABCD, а координаты вершины С совпадают с x * 1 и x * 2 . Обе переменные в оптимальном решении являются нецелыми, поэтому любая из них может быть выбрана в качестве переменной, инициирующей процесс ветвления.

Пусть это будет x2 . Выбор x2 порождает две подзадачи (2 и 3), одна из них получается путем добавления ограничения x2≥3 к исходной задаче, а другая – путем добавления ограничения x2≤2. При этом ОДЗП разбивается на две заштрихованные области (рис. 1), а полоса значений 2 2-й шаг метода ветвей и границ. Осуществляется выбор одной из обозначенных ранее подзадач. Не существует точных методов определения, какой из подзадач отдать предпочтение. Случайный выбор приводит к разным последовательностям подзадач и, следовательно, к различным количествам итераций, обеспечивающих получение оптимального решения.

Пусть вначале решается подзадача 3 с дополнительным ограничением x2≤2 или x2 + x5 = 2 . Из табл. 3 для переменной x2 справедливо следующее выражение -2/7x3+3/7x4+x2=18/7 или x2=18/7+2/7x3-3/7x4, тогда 2/7x3-3/7x4+x5=-4/7 . Включаем ограничение в табл. 3, при этом получим новую таблицу (табл. 4).

Осуществляя оптимизацию решения, переходим к табл. 5, которой соответствует решение

2
Читайте также:  Wow коллекционная карточная игра

Подзадача 5 предполагает введение дополнительного ограничения x1≥6 в подзадачу 3 . Графическое решение на рис. 1 определяет вершину L с координатами x * 1=6, x * 2=3/2 , в которой достигается оптимальное решение подзадачи 5: Fmax = 16.5 . Дальнейшее ветвление в этом направлении осуществлять нецелесообразно, так как большего, чем 16, целого значения функции цели получить невозможно. Ветвление подзадачи 5 в лучшем случае приведёт к другому целочисленному решению, в котором F = 16.

4-й шаг метода ветвей и границ. Исследуется подзадача 2 с ограничением x2≥3, находится её оптимальное решение, которое соответствует вершине М (рис. 1) с координатами x * 1=3.5, x * 2=3. Значение функции цели при этом Fmax =16, которое не превышает найденного ранее решения. Таким образом, поиск вдоль ветви x2≥3 следует прекратить.

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

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

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

На рис.1 пространство допустимых решений задачи целочисленного линейного программирования представлено точками. Соответствующая начальная задача линейного программирования (обозначим ее ЛП0) получается путем отбрасывания условия целочисленности. Ее оптимальным решением будет =3.75, =1.25, z=23.75.

Рис.1. Пространство допустимых решений

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

Пространство допустимых решений ЛП1 = пространство допустимых решений ЛП0 + (), пространство допустимых решений ЛП2 = пространство допустимых решений ЛП0 + ().

На рис.2 изображены пространства допустимы решений задач ЛП1 И ЛП2 . Оба пространства содержат все допустимые решения исходной задачи ЦЛП. Это обозначает, что задачи ЛП1 и ЛП2 «не потеряют» решения начальной задачи ЛП0.

Читайте также:  Порча дорожного знака статья

Рис.2. Пространства допустимы решений задач ЛП1 И ЛП2

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

Новые ограничения и взаимоисключаемы, так что задачи ЛП1 и ЛП2 необходимо рассматривать как независимые задачи линейного программирования, что и показано на Рис.3. Дихотомизация задач ЛП — основа концепции ветвления в методе ветвей и границ. В этом случае называется переменной ветвления.

Рис.3. Деление основной задачи на подзадачи

Оптимальное решение задачи ЦЛП находятся в пространстве допустимых решений либо в ЛП1, либо в ЛП2. Следовательно, обе подзадачи должны быть решены. Выбираем сначала задачу ЛП1 (выбор произволен), имеющую дополнительное ограничение ?3.

Максимизировать при ограничениях

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

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

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

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

Если бы мы выбрали в качестве ветвлении переменную то ветвления и скорость нахождения оптимального решения были бы другими Рис.4.

Рис.4. Дерево ветвлений решений

Ссылка на основную публикацию
Adblock detector