Метод ветвей и границ
Метод ветвей и границ целочисленного программирования относится к группе комбинаторных методов. Комбинаторные методы исходят из конечности числа допустимых планов задачи и заменяют полный перебор всех планов их частичным направленным перебором. Комбинаторные методы в значительно меньшей степени подвержены в процессе вычислений влиянию ошибок округления, поэтому являются более предпочтительными по сравнению с методами отсечения. Метод ветвей и границ – один из наиболее эффективных методов решения задач комбинаторного типа.
Перейдем к изложению сущности метода ветвей и границ. Для этого рассмотрим общую задачу дискретного программирования.
где
– конечное множество допустимых планов.
1. Находим верхнюю границу (оценку) функции
,
,
то есть такое число
,
что для любых
Если при этом удается найти такой план
задачи (*), для
которого выполняется равенство
,
то
- оптимальный план задачи (*).
2. Если оптимальный план не найден, то некоторым способом разбиваем
множество
на конечное число непересекающихся множеств
:
и находим для каждого из этих подмножеств верхнюю границу
.
Если при этом удается найти такой план
,
что выполняется соотношение
то
– оптимальный план задачи
(*). Если же такой план не найден, то выбираем подмножество
с наибольшей верхней границей (перспективное
подмножество) и разбиваем его на несколько непересекающихся подмножеств
.
Для каждого нового подмножества находим верхнюю границу
.
Если будет найден такой план
,
что
то
– оптимальный план задачи. Если оптимальный
план не найден, то дальнейшему ветвлению подвергаем подмножество с наибольшей
верхней границей, и т.д.
Процесс продолжается до получения оптимального плана. Способы ветвления и нахождения верхних границ выбираются для каждой конкретной задачи дискретного программирования. Процесс сопровождается построением дерева ветвления.
Задача 1
На приобретение оборудования для нового производственного участка выделено 80 ден. ед. Оборудование должно быть размещено на площади 5200 м2. Предприятие может заказать машины А, стоимостью 8 ден. ед. , занимающие площадь 208 м2 и выпускающие 10 ед. продукции за смену, и машины Б стоимостью 5 ден. ед. , занимающие площадь 505 м2 и обеспечивающие выпуск 13 ед. продукции за смену. При этом следует учесть, что машин типа А можно заказать не более 7 штук.
Требуется:
- составить экономико-математическую модель, пользуясь которой, можно найти план приобретения машин, учитывающий возможности предприятия и обеспечивающий наивысшую производительность нового участка;
- пользуясь одним из методов целочисленного линейного программирования, найти оптимальный план приобретения оборудования.
Решение
Через
и
обозначим количество приобретаемого
оборудования вида
и
соответственно.
Целевая функция, выражающая количество выпускаемых изделий:
Ограничения по деньгам и площади:
Кроме того:
Количество приобретаемых тракторов не может быть
отрицательным числом:
.
Экономико-математическая модель задачи будет иметь вид:
На сайте можно заказать решение задач, контрольных, самостоятельных, домашних работ (возможно срочное решение), а также онлайн-помощь на экзамене или зачете. Для этого вам нужно только связаться со мной:
Телеграм @helptask
ВКонтакте (vk.com/task100)
WhatsApp +7 (968) 849-45-98
Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту.
Подробное решение получите точно в срок или раньше.
Решим полученную задачу симплексным или графическим методом с отброшенным условием целочисленности. Получаем:
Ответ получился нецелым, поэтому решим задачу линейного программирования методом ветвей и границ.
Обе
переменные имеют нецелые значения. Выбор переменной
порождает две подзадачи:
Найдем оптимальный план 1-й
подзадачи c дополнительным ограничением
Решение графическим или симплексным методом дает следующие результаты:
Получили целочисленный ответ – исходная задача целочисленного программирования решена.
Следует закупать 5 штук оборудования типа
и 8 штук оборудования типа
.
При этом производительность нового участка равна 154 изделия за смену.
Задача 2
Для выполнения работ
сельскохозяйственное предприятие может
приобрести тракторы марок
и
стоимостью соответственно
и
ден. ед.
каждый. С использованием новой техники необходимо выполнить не менее
условных единиц работы
,
не менее
условных единиц работы
и не менее
условных единиц работы
.
За рассматриваемый промежуток времени с использованием трактора марки
можно выполнить
условных единиц работы
,
условных единиц работы
или
условных единиц работы
;
с использованием трактора марки Б –
условных единиц работы
,
условных единиц работы
или
условных единиц работы
.
Требуется:
- Составить экономико-математическую модель, позволяющую найти такой вариант приобретения тракторов той или другой марки, при котором будут выполнены все необходимые работы, а затраты на новую технику будут минимальны;
- Пользуясь одним из методов целочисленного программирования, найти оптимальный вариант приобретения тракторов.
Решение
Через х1 и х2 обозначим количество приобретаемых тракторов вида А и Б соответственно.
Целевая функция, выражающая стоимость тракторов будут иметь вид:
Ограничения, показывающее на то, что все работы должны быть выполнены:
Кроме того,
количество приобретаемых тракторов не может быть отрицательным числом:
.
Экономико-математическая модель задачи будет иметь вид:
Решим полученную задачу симплексным или графическим методом с отброшенным условием целочисленности. Получаем:
Ответ получился нецелым, поэтому решим задачу линейного программирования методом ветвей и границ.
Обе
переменные имеют нецелые значения. Выбор переменной
порождает две подзадачи:
Найдем оптимальный план 2-й
подзадачи c дополнительным ограничением
Решение графическим или симплексным методом дает следующие результаты:
Таким образом, следует приобретать 7 тракторов марки А и 4 трактора марки Б. При этом все работы будут выполнены в полном объеме, а затраты на приобретение тракторов будут минимальны и равны 41 ден. ед.
Данную задачу целочисленного программирования можно также решить методом Гомори.