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

Краткая теория

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

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

где – конечное множество допустимых планов.

1. Находим верхнюю границу (оценку) функции , , то есть такое число , что для любых

Если при этом удается найти такой план задачи (*), для которого выполняется равенство , то - оптимальный план задачи (*).

2. Если оптимальный план не найден, то некоторым способом разбиваем множество на конечное число непересекающихся множеств :

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

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

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

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

Примеры решения задач

Задача 1

На приобретение оборудования для нового производственного участка выделено 80 ден. ед. Оборудование должно быть размещено на площади 5200 м². Предприятие может заказать машины А, стоимостью 8 ден. ед. , занимающие площадь 208 м² и выпускающие 10 ед. продукции за смену, и машины Б стоимостью 5 ден. ед. , занимающие площадь 505 м² и обеспечивающие выпуск 13 ед. продукции за смену. При этом следует учесть, что машин типа А можно заказать не более 7 штук.

Требуется:

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

Решение

Через и обозначим количество приобретаемого оборудования вида и соответственно.

Целевая функция, выражающая количество выпускаемых изделий:

Ограничения по деньгам и площади:

Кроме того:

Количество приобретаемых тракторов не может быть отрицательным числом: .

Экономико-математическая модель задачи будет иметь вид:

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

Телеграм (+7 968 849-45-98)
ВКонтакте
WhatsApp (+7 968 849-45-98)

Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту. Опыт работы более 25 лет.

Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.

Решим полученную задачу симплексным или графическим методом с отброшенным условием целочисленности. Получаем:

Ответ получился нецелым, поэтому решим задачу линейного программирования методом ветвей и границ.

Обе переменные имеют нецелые значения. Выбор переменной порождает две подзадачи:

Найдем оптимальный план 1-й подзадачи c дополнительным ограничением

Решение графическим или симплексным методом дает следующие результаты:

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

Следует закупать 5 штук оборудования типа и 8 штук оборудования типа . При этом производительность нового участка равна 154 изделия за смену.

Задача 2

Для выполнения работ сельскохозяйственное предприятие может приобрести тракторы марок и стоимостью соответственно и ден. ед. каждый. С использованием новой техники необходимо выполнить не менее условных единиц работы , не менее условных единиц работы и не менее условных единиц работы . За рассматриваемый промежуток времени с использованием трактора марки можно выполнить условных единиц работы , условных единиц работы или условных единиц работы ; с использованием трактора марки Б – условных единиц работы , условных единиц работы или условных единиц работы .

Требуется:

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

Решение

Через х₁ и х₂ обозначим количество приобретаемых тракторов вида А и Б соответственно.

Целевая функция, выражающая стоимость тракторов будут иметь вид:

Ограничения, показывающее на то, что все работы должны быть выполнены:

Кроме того, количество приобретаемых тракторов не может быть отрицательным числом: .

Экономико-математическая модель задачи будет иметь вид:

Ответ получился нецелым, поэтому решим задачу линейного программирования методом ветвей и границ.

Обе переменные имеют нецелые значения. Выбор переменной порождает две подзадачи:

Найдем оптимальный план 2-й подзадачи c дополнительным ограничением

Решение графическим или симплексным методом дает следующие результаты:

Таким образом, следует приобретать 7 тракторов марки А и 4 трактора марки Б. При этом все работы будут выполнены в полном объеме, а затраты на приобретение тракторов будут минимальны и равны 41 ден. ед.

Данную задачу целочисленного программирования можно также решить методом Гомори.