Полная версия

Главная arrow Экономика arrow Исследование операций в экономике

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

8.3. Понятие о методе ветвей и границ

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

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

Пусть задача 1 (задача (8.1)-(8.3) максимизации линейной функции Z (без учета целочисленности переменных) решена симплексным методом и известны нижняя и верхняя границы для каждой нецелочисленной переменной х:. Vi<Xj<Wj (j = 1, 2, ..., п), а также нижняя граница линейной функции Ζ0, т.е. при любом плане X Ζ(Χ)>Ζ0. Предположим для определенности, что только первая компонента xj оптимального плана X* задачи 1 не удовлетворяет условию целочисленности. Тогда из области допустимых решений задачи 1 исключается область: [xj ] < xj < [xj ] +1, где [х, ] – целая часть числа xj. В результате из задачи 1 формируют две задачи: 2 и 3, отличающиеся друг от друга тем, что в задаче 2, кроме ограничений (8.2) задачи 1, добавлено ограничение v, < xj < [xj] + l, а в задаче 3, кроме тех же ограничений (8.2), добавлено ограничение [xj] + l<xj <a"t. Получим список из двух задач: 2 и 3.

Решаем одну из них (в любом порядке). В зависимости от полученного решения список задач расширяется либо уменьшается.

Если в результате решения одной из задач 2 или 3 получен нецелочисленный оптимальный план, для которого Z(X')< Z0, то данная задача исключается из списка. Если Z(X*)>Z0, то из данной задачи формируются новые две задачи.

Если полученное решение X* удовлетворяет условию целочисленности и Z(X')>Z0, то значениеZ0 исправляется и за величину Z0 принимается оптимум линейной функции полученного оптимального целочисленного плана.

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

Проиллюстрируем метод ветвей и границ на примере. 8.3. Решить задачу

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

Решение. За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т.е. Z0 = Z(0; 0) = 0.

I этап. Решая задачу симплексным методом, получим Zmax =13 при Х = (4,5; 0; 0; 1,5; 0,5; 4); так как первая компонента х*, дробная, то из области решения исключается полоса, содержащая дробное оптимальное значение х', т.е. 4 < х, < 5. Поэтому задача 1 разбивается на две задачи – 2 и 3:

Задача 2 Задача 3

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

– целые числа.– целые числа.

Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z0 = 0.

II этап. Решаем (по выбору) одну из задач списка, например задачу 3, симплексным методом.

Получим, что условия задачи 3 противоречивы.

III этап. Решаем задачу 2 симплексным методом. Получимпри. Хотя

i, по-прежнему сохраняется Zfl = 0, план X, нецелочисленный. Так как х – дробное число, из области решений исключаем полосу 0 < х2 < 1 и задачу 2 разбиваем на две задачи – 4 и 5.

Список задач: 4 и 5. Значение Z0 = 0.

IV этап. Решаем задачу 4 симплексным методом. Получим Zmm = 12 при X*, = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z0; Z0 = Z(X) = 12, ибо план Х'А целочисленный.

V этап. Решаем задачу 5 симплексным методом. Получим Zmax = 12,25 при Xj = (3,75; 1; 0; 0,25; 0,25; 0; 3).

Z0 не меняется, т.е. Z0 = 12, ибо план X*- нецелочисленный. Так как х дробное, из области решений исключаем полосу 3 < хх < 4, и задача 5 разбивается на две задачи – 6 и 7.

Список задач: 6 и 7. Значение Z0 = 12.

VI этап. Решаем одну из задач списка, например задачу 7, симплексным методом.

Получим, что условия задачи 7 противоречивы.

VII этап. Решаем задачу 6 симплексным методом. Получим Zmax =10,5 при Χ'ΰ = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так как Z(Xg) = 10,5< Z() = 12, то задача исключается из списка.

Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет X = Х = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Zmax = 12. ►

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

Замечание 2. Название метода ветвей и границ объясняется тем, что в процессе решения задача последовательно "ветвится", заменяясь более простыми задачами. Так, процесс решения задачи 8.3 можно представить в виде дерева (схемы), цифры в узлах (вершинах) которого обозначают номера задач (рис. 8.3).

Рис. 8.3

 
<<   СОДЕРЖАНИЕ   >>