Метод ветвей и границ. Теория графов. Решение задачи коммивояжера. Пример решения задачи коммивояжера методом ветвей и границ
Метод ветвей и границ относится к комбинаторным методам решения целочисленных задач и применим как к полностью, так и к частично целочисленным задачам.
Суть метода ветвей и границ – в направленном частичном переборе допустимых решений. Будем рассматривать . Вначале она решается без ограничений на целочисленность. При этом находится верхняя граница F(x), так как целочисленное решение не может улучшить значение функции цели.
Далее в методе ветвей и границ область допустимых значений переменных (ОДЗП) разбивается на ряд непересекающихся областей (ветвление), в каждой из которых оценивается экстремальное значение функции. Если целое решение не найдено, ветвление продолжается.
Ветвление производится последовательным введением дополнительных ограничений. Пусть x k – целочисленная переменная, значение которой в оптимальном решении получилось дробным. Интервал [β k ] ≤ x k ≤ [β k ]+1 не содержит целочисленных компонентов решения. Поэтому допустимое целое значение x k должно удовлетворять одному из неравенств x k ≥[β k ]+1 или x k ≤[β k ]. Это и есть дополнительные ограничения. Введение их в методе ветвей и границ на каждом шаге порождает две не связанные между собой подзадачи. Каждая подзадача решается как задача линейного программирования с исходной целевой функцией. После конечного числа шагов будет найдено целочисленное оптимальное решение.
Применение метода ветвей и границ рассмотрим на конкретном примере.
Пример 1. Методом ветвей и границ F(x) = 2x 1 + 3x 2 при ограничениях
3x 1 +4x 2 ≤24
2x 1 +5x 2 ≤22
x 1,2 ≥0 - целые
1-й шаг метода ветвей и границ. с отброшенными условиями целочисленности с помощью симплекс-метода (табл. 1 – 3).
По данным табл. 3 запишем оптимальное нецелое решение
| ; x * 2 =2 | 4 | ; F max =16 | 6 |
| 7 | 7 |
Таблица 1 - симплекс-таблица для задачи ЛП
Таблица 2 - симплекс-таблица для задачи ЛП
Таблица 3 - симплекс-таблица для задачи ЛП
Графическая интерпретация задачи приведена на рис. 1. Здесь ОДЗП представлена четырехугольником ABCD, а координаты вершины С совпадают с x * 1 и x * 2 . Обе переменные в оптимальном решении являются нецелыми, поэтому любая из них может быть выбрана в качестве переменной, инициирующей процесс ветвления.
Пусть это будет x 2 . Выбор x 2 порождает две подзадачи (2 и 3), одна из них получается путем добавления ограничения x 2 ≥3 к исходной задаче, а другая – путем добавления ограничения x 2 ≤2. При этом ОДЗП разбивается на две заштрихованные области (рис. 1), а полоса значений 2 < x 2 < 3 исключается из рассмотрения. Однако множество допустимых целочисленных решений сохраняется, порожденные подзадачи содержат все целочисленные решения исходной задачи.
Рисунок 1 - графическая интерпритация решения примера методом ветвей и границ
2-й шаг метода ветвей и границ. Осуществляется выбор одной из обозначенных ранее подзадач. Не существует точных методов определения, какой из подзадач отдать предпочтение. Случайный выбор приводит к разным последовательностям подзадач и, следовательно, к различным количествам итераций, обеспечивающих получение оптимального решения.
Пусть вначале решается подзадача 3 с дополнительным ограничением x 2 ≤2 или x 2 + x 5 = 2 . Из табл. 3 для переменной x 2 справедливо следующее выражение -2/7x 3 +3/7x 4 +x 2 =18/7 или x 2 =18/7+2/7x 3 -3/7x 4 , тогда 2/7x 3 -3/7x 4 +x 5 =-4/7 . Включаем ограничение в табл. 3, при этом получим новую таблицу (табл. 4).
Осуществляя оптимизацию решения, переходим к табл. 5, которой соответствует решение
| ; x * 2 =2 | ; F max =16 | 2 |
| 3 |
Переменная x 1 нецелая, поэтому ветвление необходимо продолжить; при этом возникают подзадачи 4 и 5 с ограничениями x 1 ≤5 и x 1 ≥6 соответственно. Полоса значений 5 < x 1 < 6 исключается из рассмотрения.
Таблица 5 - симплекс-таблица для задачи ЛП
3-й шаг метода ветвей и границ. Решаются подзадачи 4 и 5. Из рис. 1 видно, что оптимальное целочисленное решение подзадачи 4 достигается в вершине К с координатами x * 1 =5, x * 2 =2, однако это не означает, что найден оптимум исходной задачи. Причиной такого вывода являются еще не решенные подзадачи 3 и 5, которые также могут дать целочисленные решения. Найденное целочисленное решение F = 16 определяет нижнюю границу значений целевой функции, т.е. меньше этого значения оно быть не должно.
Подзадача 5 предполагает введение дополнительного ограничения x 1 ≥6 в подзадачу 3 . Графическое решение на рис. 1 определяет вершину L с координатами x * 1 =6, x * 2 =3/2 , в которой достигается оптимальное решение подзадачи 5: F max = 16.5 . Дальнейшее ветвление в этом направлении осуществлять нецелесообразно, так как большего, чем 16, целого значения функции цели получить невозможно. Ветвление подзадачи 5 в лучшем случае приведёт к другому целочисленному решению, в котором F = 16.
4-й шаг метода ветвей и границ. Исследуется подзадача 2 с ограничением x 2 ≥3, находится её оптимальное решение, которое соответствует вершине М (рис. 1) с координатами x * 1 =3.5, x * 2 =3. Значение функции цели при этом F max =16, которое не превышает найденного ранее решения. Таким образом, поиск вдоль ветви x 2 ≥3 следует прекратить.
Отметим, что алгоритм метода ветвей и границ является наиболее надёжным средством решения целочисленных задач, он положен в основу большинства прикладных программ для ПЭВМ, используемых для этих целей.
Для решения задач линейного программирования имеется широкий набор разнообразных машинных программ, которые избавляют от трудоёмкого процесса вычислений вручную. Однако интерпретация информации, выведенной на печать, невозможна без чёткого представления о том, почему и как работает .
Решение будем вести с использованием калькулятора . Возьмем в качестве произвольного маршрута:X 0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X 0) = 90 + 40 + 60 + 50 + 20 = 260
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
d i = min(j) d ij
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 90 | 80 | 40 | 100 | 40 |
| 2 | 60 | M | 40 | 50 | 70 | 40 |
| 3 | 50 | 30 | M | 60 | 20 | 20 |
| 4 | 10 | 70 | 20 | M | 50 | 10 |
| 5 | 20 | 40 | 50 | 20 | M | 20 |
Затем вычитаем d i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
| d j | 0 | 10 | 0 | 0 | 0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d i и d j называются константами приведения .
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 40 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 0 | M | 40 | 0 |
| 4 | 0 | 50 | 10 | M | 40 |
| 5 | 0 | 10 | 30 | 0 | M |
Сумма констант приведения определяет нижнюю границу H:
H = ∑d i + ∑d j
H = 40+40+20+10+20+0+10+0+0+0 = 140
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 40 | 40 | 0(40) | 60 | 40 |
| 2 | 20 | M | 0(20) | 10 | 30 | 10 |
| 3 | 30 | 0(10) | M | 40 | 0(30) | 0 |
| 4 | 0(10) | 50 | 10 | M | 40 | 10 |
| 5 | 0(0) | 10 | 30 | 0(0) | M | 0 |
| d j | 0 | 10 | 10 | 0 | 30 | 0 |
d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (40 + 0) = 40 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
H(1*,4*) = 140 + 40 = 180
Исключение ребра (1,4) проводим путем замены элемента d 14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 40 | 40 | M | 60 | 40 |
| 2 | 20 | M | 0 | 10 | 30 | 0 |
| 3 | 30 | 0 | M | 40 | 0 | 0 |
| 4 | 0 | 50 | 10 | M | 40 | 0 |
| 5 | 0 | 10 | 30 | 0 | M | 0 |
| d j | 0 | 0 | 0 | 0 | 0 | 40 |
Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d 41 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
∑d i + ∑d j = 10
| i j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | 0 | 0 |
| 4 | M | 50 | 10 | 40 | 10 |
| 5 | 0 | 10 | 30 | M | 0 |
| d j | 0 | 0 | 0 | 0 | 10 |
Нижняя граница подмножества (1,4) равна:
H(1,4) = 140 + 10 = 150 ≤ 180
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 150
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| i j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0(20) | 30 | 20 |
| 3 | 30 | 0(10) | M | 0(30) | 0 |
| 4 | M | 40 | 0(30) | 30 | 30 |
| 5 | 0(30) | 10 | 30 | M | 10 |
| d j | 20 | 10 | 0 | 30 | 0 |
d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 150 + 30 = 180
Исключение ребра (3,5) проводим путем замены элемента d 35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.
| i j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | M | 0 |
| 4 | M | 40 | 0 | 30 | 0 |
| 5 | 0 | 10 | 30 | M | 0 |
| d j | 0 | 0 | 0 | 30 | 30 |
Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d 53 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 10
После операции приведения сокращенная матрица будет иметь вид:
| i j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 40 | 0 | 0 |
| 5 | 0 | 10 | M | 0 |
| d j | 0 | 10 | 0 | 10 |
Нижняя граница подмножества (3,5) равна:
H(3,5) = 150 + 10 = 160 ≤ 180
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 160
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| i j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0(20) | 20 |
| 4 | M | 30 | 0(30) | 30 |
| 5 | 0(20) | 0(30) | M | 0 |
| d j | 20 | 30 | 0 | 0 |
d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,2*) = 160 + 30 = 190
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
| i j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 30 | 0 | 0 |
| 5 | 0 | M | M | 0 |
| d j | 0 | 30 | 0 | 30 |
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 20
После операции приведения сокращенная матрица будет иметь вид:
| i j | 1 | 3 | d i |
| 2 | 20 | 0 | 0 |
| 4 | M | 0 | 0 |
| d j | 20 | 0 | 20 |
Нижняя граница подмножества (5,2) равна:
H(5,2) = 160 + 20 = 180 ≤ 190
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 180
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,1) и (4,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,5), (5,2), (2,1),
Длина маршрута равна F(Mk) = 180
Требуется решить следующую задачу:
max 2х 1 + х 2
5х 1 + 2х 2 10
3х 1 + 8х 2 13
Вначале решим эту задачу графически без ограниченийцелочисленности. Решение может быть найдено как симплекс-методом, так и графически. Найдем его графически (рисунок 4). Координаты точки оптимума можно найти, решив систему уравнений: 5х 1 + 2х 2 = 10 х 1 =27/17
3х 1 + 8х 2 = 13 х 2 =35/34
Х G = (27/17;35/34), z G =143/34
Рисунок 4 - Графическое решение задачи без ограничений целочиелейности
Начнем строить дерево, первая вершина которого будет соответствовать всей ОДП нецелочисленной задачи (G), а ее оценка будет равна z G (рис.5).
Рисунок 5 - Схема метода ветвей и границ
Полученный план не является целочисленным, поэтому возьмем его произвольную нецелочисленную компоненту, например, первую (х 1 Z; [х 1 ] = = 1) и разобьем ОДП на две части следующим образом:
G 1 ={XG: х 1 1}
G 2 ={XG: х 1 2}
Это означает, что в область G 1 войдут все точки из G, у которых абсцисса не больше 1, а в G 2 - у которых она не меньше 2. Точки с дробными значениями абсциссы от 1 до 2 исключены из рассмотрения.
Изобразим эти области на графике (рисунок 6).
Из рисунка 6 видно, что G 2 представляет собой одну точку Х G 2 =(2;0), следовательно, на этом множестве оптимум задачи равен 4 ( 2 =4).
План Х G 2 является целочисленным, следовательно, решение целочисленной задачи уже, возможно, найдено. Однако, следует еще найти оценку множества G 1 |. Она может оказаться не менее 4 (но обязательно не более 143/34). Если это так, то нужно проверить, не является ли целочисленным решение задачи на G 1. Если оно целое, то является решением задачи, а если нет, то процесс решения необходимо продолжить, разбивая G 1
Рисунок 6 - Разбиение множества на части
На G 1 точку оптимума можно найти, решив систему уравнений:
х 1 = 1 х 1 =1
3х 1 + 8х 2 = 13 х 2 =5/4
Х G 1 = (1; 5/4), z G =13/4
Оценка меньше 4, следовательно, решением задачи является Х * =Х G 2 =(2;0),z * =4.
3.4 Решение задачи целочисленного линейного программирования методом ветвей и границ с помощью ппп «Система деловых задач»
ЗЦЛП можно решить с помощью пакета прикладных программ “Quantitative Systems for Business” ("Система деловых задач") . Соответствующая программа запускается файлом intlprog.ехе. Она решает как частично, так и полностью целочисленные задачи линейного программирования с числом переменных и ограничений до 20, используя метод ветвей и границ. В том числе решаются и задачи с булевыми переменными (т.е. с переменными, которые могут принимать одно из двух значений - 0 или 1; как, например, в задаче о назначениях ). По умолчанию все переменные неотрицательны. Программа позволяет ввести целочисленные границы для переменных, не включая их в общее число ограничений. По умолчанию нижняя граница 0, а верхняя 32000. Если необходимо установить нецелочисленные границы, их вводят, как обычные ограничения.
Если в задаче имеется несколько оптимальных планов, из них находится только один. Информация о наличии множественного решения не выводится.
Режим 2 (ввод новой задачи) включает три этапа. На первом этапе осуществляют ввод информации о размерности задачи, направлении экстремизации и именах переменных (по умолчанию XI, Х2,..., Хn).
На втором этапе необходимо определить, являются ли все переменные целочисленными, являются ли все переменные булевыми, и будут ли вводиться границы для переменных. При ответе «нет» на первый вопрос или «да» на третий, выводится таблица (рисунок 7):
Введите предел и границы для переменных
(По умолчанию значения нижней границы 0 и верхней границы 32000)
№ перем. Имя Предел (I/C) Нижняя гр. Верхняя гр.
1 X 1
2 X 2
Рисунок 7 - Определение пределов и границ
Установив I (integer) в столбце «Предел», на переменную накладывают ограничение целочисленности. В противном случае (С, continuous) -переменная может принимать и нецелые значения, т.е. является непрерывной.
Значения границ округляются до целых. Если нижняя больше верхней, выдается сообщение об ошибке.
На третьем этапе вводятся коэффициенты при переменных и знаки в ограничениях.
В меню решений имеется возможность исправить целочисленную погрешность (по умолчанию она 0,001).
Решение задачи методом ветвей и границ не сопровождается графической иллюстрацией (изображением дерева) в программе, но для пояснения алгоритма приведем такую иллюстрацию на рисунок 8.
Алгоритм метода ветвей и границ, реализованный в данной программе, несколько отличается от рассмотренного выше в методических указаниях и является менее эффективным в том смысле, что может потребовать большего числа итераций. Тем не менее, его полезно рассмотреть, чтобы наглядно проиллюстрировать разницу в подходах. Кроме того, во многих учебных пособиях применение метода ветвей и границ рассматривается именно на примере данной его модификации.
Основное различие заключается в том, что здесь на каждом этапе не выбирается наиболее «перспективное» подмножество. После того, как очередное подмножество разбито на две части, не подсчитывают сразу оценку обеих частей, а вместо этого каждая ветвь дерева последовательно рассматривается до конца. Исходная ОДП разбивается на подмножества по первой нецелочисленной переменной в оптимальном плане нецелочисленной задачи. Затем рассматривают ту вершину, которой соответствует знак , разбивают соответствующее подмножество так же, как и исходную ОДП, снова рассматривают ту вершину, которой соответствует знак , и т.д. до тех пор, пока не будет получен целочисленный план, или задача окажется неразрешимой. Только после этого возвращаются к рассмотрению вершин, которым соответствовал знак .
При этом на каждой итерации выводится информация о текущих целочисленных границах (определяющих рассматриваемое подмножество), оптимальном плане нецелочисленной задачи, о том, является ли он целочисленным, о значении целевой функции (ЦФ) на нем и о величинах ZL или ZU. Для задачи на максимум выводится значение нижней границы ZL, а на минимум верхней ZU. До тех пор, пока не найдено какое-нибудь целое решение, ZL =-1*10 20 , а ZU = 1*10 20 .
После нахождения целочисленного плана нельзя сразу судить о том, является ли он оптимальным, так как рассматривались не наиболее перспективные вершины. Но можно в уверенностью утверждать, что искомый максимум не меньше (а минимум не больше) значения целевой функции на целочисленном плане. Поэтому значения границ ZL и ZU изменяются (если только ранее не был найден целочисленный план с не меньшим (не большим) значением целевой функции).
Ветви с оценкой, меньшей ZL или большей ZU, не рассматриваются. План, соответствующий границе, запоминается. После того, как рассмотрены или исключены из рассмотрения все подмножества, этот план можно считать оптимальным.
Поясним это на примере (рис.8):
max 3х 1 + 2х 2
7х 1 + 5х 2 35
9х 1 + 4х 2 36
На первой итерации найдено нецелочисленное решение Х=(2,353; 3,706). Вся ОДП (множество G) разбивается на два подмножества - G 1 и G 2 следующим образом:
G 1 ={XG: х 1 3}
G 2 ={XG: х 1 2}.
На второй итерации решают задачу на подмножестве G 1 . Полученное решение также нецелочисленно. Далее, вместо того, чтобы рассмотреть подмножество G 2 , продолжают рассматривать G 1 . В соответствующем плане выбирают первую по счету нецелочисленную компоненту (это х 2) и разбивают G 1 на G 3 и G 4 . На третьей итерации рассматривают G 3 - на этом подмножестве допустимых планов нет. Только после этого на четвертой итерации рассматривается вторая ветвь, выходящая из G 1 - подмножество G 4 . Далее аналогично.
На пятой итерации на подмножестве G 5 найдено целочисленное решение, которому соответствует значение целевой функции 12. На следующей итерации это значение присваивается величине ZL, которая до этого была равна -1*10 20 . Соответствующий план запоминается - он может оказаться оптимальным. Но на шестой итерации снова получен целочисленный план, целевая функция на котором равна 13 (больше 12) - ZL снова изменяется, запоминается новый план.
После этого, на седьмой итерации, переходят к рассмотрению подмножества G 2 , которое разбивают на G 7 и G 8 .
На тринадцатой итерации (подмножество G 14) снова найдено целочисленное решение Х=(0; 7), целевая функция на нем равна 14. Снова изменяется ZL и запоминается соответствующий план.
План, найденный на четырнадцатой итерации, также является целочисленным, но его не запоминают, так как 13<14 (ZL=14). План, найденный на пятнадцатой итерации, тоже, к сожалению, не запоминается, так как 1414, а программа ставит своей целью найти хотя бы одно решение.
Наличие других оптимальных планов здесь игнорируется.
Таким образом, решение Х=(0; 7) получено за 15 итераций.
Отметим, что если бы использовался более эффективный вариант метода ветвей и границ, схема которого описана в методических указаниях, то после второй итерации произошел бы сразу переход к седьмой. В самом деле, если рассматривать значения целевой функции на соответствующих планах в качестве оценки подмножеств, то оценка G 2 выше. Поэтому итерации с 3-ей по 6-ю оказываются лишними, и общее число итераций могло быть равно 11.
5x 1 + 2x 2 ≤ 14
2x 1 + 5x 2 ≤ 16
x 1 , x 2 – целые числа
Z = 3x 1 + 5x 2 → max
Решение находим с помощью калькулятора .:
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Границы области допустимых решений
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 3x 1 +5x 2 → max.
Построим прямую, отвечающую значению функции F = 0: F = 3x 1 +5x 2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) = const
(1)
и (2)
5x 1 +2x 2 ≤14
2x 1 +5x 2 ≤16
Решив систему уравнений, получим: x 1 = 1.8095, x 2 = 2.4762
F(X) = 3*1.8095 + 5*2.4762 = 17.8095
Оптимальное значение переменной x 1 =1.81 оказалось нецелочисленным.
В первой из них к условиям задачи 11 добавляется условие х 1 ≥ 2, а к задаче 12 - условие х 1 ≤ 1.
Эта процедура называется ветвлением
по переменной х 1 .
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≥2 | (3) |
x 1 ≥0 | (4) |
x 2 ≥0 | (5) |
Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (3) , то ее координаты удовлетворяют уравнениям этих прямых:
5x 1 +2x 2 ≤14
x 1 ≥2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16
Решение задачи получилось целочисленным.
Новое значение текущего рекорда будет равно F(X) = 16.
Так как найденная точка является первым целочисленным решением, то ее и соответствующее ей значение ЦФ следует запомнить. Сама точка называется текущим целочисленным рекордом
или просто рекордом, а оптимальное значение целочисленной задачи - текущим значением рекорда
. Это значение является нижней границей оптимального значения исходной задачи Z*.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≤1 | (3) |
x 1 ≥0 | (4) |
x 2 ≥0 | (5) |
Область допустимых решений представляет собой многоугольник
Прямая F(x) = const (2) и (3) , то ее координаты удовлетворяют уравнениям этих прямых:
2x 1 +5x 2 ≤16
x 1 ≤1
Решив систему уравнений, получим: x 1 = 1, x 2 = 2.8
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2.8 = 17
Оптимальное значение переменной x 2 =2.8 оказалось нецелочисленным.
Разбиваем задачу 12 на две подзадачи 121 и 122.
В первой из них к условиям задачи 121 добавляется условие х 2 ≥ 3, а к задаче 122 - условие х 2 ≤ 2.
Решим графически задачу 121 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≤1 | (3) |
x 2 ≥3 | (4) |
x 1 ≥0 | (5) |
x 2 ≥0 | (6) |
Область допустимых решений представляет собой треугольник.
Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (4) , то ее координаты удовлетворяют уравнениям этих прямых:
2x 1 +5x 2 ≤16
x 2 ≥3
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0.5 + 5*3 = 16.5
Решим графически задачу 122 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≤1 | (3) |
x 2 ≤2 | (4) |
x 1 ≥0 | (5) |
x 2 ≥0 | (6) |
Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (3) и (4) , то ее координаты удовлетворяют уравнениям этих прямых:
x 1 ≤1
x 2 ≤2
Решив систему уравнений, получим: x 1 = 1, x 2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2 = 13
Текущий рекорд Z=16≥13, поэтому прекращаем ветвление из этой вершины
Разбиваем задачу 121 на две подзадачи 1211 и 1212.
В первой из них к условиям задачи 1211 добавляется условие х 1 ≥ 1, а к задаче 1212 - условие х 1 = 0.
Решим графически задачу 1211 как задачу ЛП.
Задача не имеет допустимых решений. ОДР представляет собой пустое множество.
Задача 1211 не имеет решения, поэтому для нее процесс ветвления прерываем.
Решим графически задачу 1212 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≤1 | (3) |
x 2 ≥3 | (4) |
x 1 =0 | (5) |
x 1 ≥0 | (6) |
x 2 ≥0 | (7) |
Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (7) , то ее координаты удовлетворяют уравнениям этих прямых:
2x 1 +5x 2 ≤16
x 1 =0
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0 + 5*3.2 = 16
Оптимальное значение переменной x 2 =2.48 оказалось нецелочисленным.
Разбиваем задачу 1 на две подзадачи 11 и 12.
В первой из них к условиям задачи 11 добавляется условие х 2 ≥ 3, а к задаче 12 - условие х 2 ≤ 2.
Эта процедура называется ветвлением
по переменной х 2 .
Решим графически задачу 11 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 2 ≥3 | (3) |
x 1 ≥0 | (4) |
x 2 ≥0 | (5) |
Область допустимых решений представляет собой треугольник.
Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (3) , то ее координаты удовлетворяют уравнениям этих прямых:
2x 1 +5x 2 ≤16
x 2 ≥3
Решив систему уравнений, получим: x 1 = 0.5, x 2 = 3
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0.5 + 5*3 = 16.5
Решим графически задачу 12 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 2 ≤2 | (3) |
x 1 ≥0 | (4) |
x 2 ≥0 | (5) |
Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (3) , то ее координаты удовлетворяют уравнениям этих прямых:
5x 1 +2x 2 ≤14
x 2 ≤2
Решив систему уравнений, получим: x 1 = 2, x 2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16
Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x 1 =0.5 оказалось нецелочисленным.
Разбиваем задачу 11 на две подзадачи 111 и 112.
В первой из них к условиям задачи 111 добавляется условие х 1 ≥ 1, а к задаче 112 - условие х 1 = 0.
Решим графически задачу 111 как задачу ЛП.
Прямая F(x) = const
пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2)
и (6)
, то ее координаты удовлетворяют уравнениям этих прямых:
2x 1 +5x 2 ≤16
x 1 =0
Решив систему уравнений, получим: x 1 = 0, x 2 = 3.2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0 + 5*3.2 = 16
Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
F(X) = 16
x 1 = 2
x 2 = 2
Дерево решения задачи
Метод ветвей и границ -- один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.
Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.
Алгоритм решения:
Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план 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) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.
Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори. Поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод.
целочисленный программирование задача коммивояжер ранец