Платная помощь студентам - решение задач и контрольных работ

Помощь в решении ваших задач, домашних работ и контрольных вы можете найти, отправив сообщение ВКонтакте, WhatsApp, Telegram или электроннной почтой, сообщив необходимые вам сроки решения и скинув условие.
Мгновенная связь в любое время и на любом этапе заказа. Общение с автором студенческих работ без посредников. Опыт работы более 20 лет.
Высшая математика и физика, теория вероятностей, линейное программирование, статистика, эконометрика, финансовая математика, методы и модели, оптимальные решения.
На цену сильно влияет срочность решения. Онлайн-помощь на экзамене/зачете (срок решения 1,5 часа и меньше) осуществляется по предварительной записи.

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1

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

Требуется:

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

Решение

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

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

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

Кроме того:

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

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

Задали объемную домашнюю работу или контрольную? Скоро важный зачет/экзамен? Нет времени на выполнение работы или подготовку к зачету/экзамену, но есть деньги? На сайте 100task.ru можно заказать решение задач, домашних работ, контрольных или онлайн-помощь на зачете/экзамене ⟩⟩

Если вам сейчас не требуется помощь, но может потребоваться в дальнейшем, то, чтобы не потерять контакт, вступайте в группу ВК.

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

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

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

 

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

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

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

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

Задача 2

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

Требуется:

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

Решение

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

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

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

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

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

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

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

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

 

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

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

 

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

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

К оглавлению решебника по методам оптимальных решений