Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel | Статья в журнале «Молодой ученый»

Авторы: ,

Рубрика: Технические науки

Опубликовано в Молодой учёный №12 (116) июнь-2 2016 г.

Дата публикации: 17.06.2016

Статья просмотрена: 963 раза

Библиографическое описание:

Селюкова С. А., Селюкова Г. П. Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel // Молодой ученый. — 2016. — №12. — С. 372-375. — URL https://moluch.ru/archive/116/31884/ (дата обращения: 21.09.2018).



В большинстве экономико-математических моделей, сформулированных как задачи линейного программирования, часть или все компоненты вектора-решения должны выражаться в целых числах, т. е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при закупке оборудования, количество домов при очередности строительства и т. д. [3, c. 180]

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

Для решения рассмотренного класса задач математического программирования, как правило, используется универсальный метод решения под названием «метод ветвей и границ». [2, с. 158]

Продемонстрируем основные идеи этого метода на примере решения задачи целочисленного линейного программирования (ЦЛП).

Эти задачи включают в себя требования целочисленности ко всем искомым переменным. Они относятся к классу задач полностью целочисленного линейного программирования (задача ЦЛП). В свою очередь, эти задачи являются частным случаем задачи частично целочисленного линейного программирования (ЧЦЛП). [2, с. 160]

При решении задач частично-целочисленного линейного программирования методом ветвей и границ на определенных этапах решаются вспомогательные задачи линейного программирования (ЛП), для которых применяется симплекс-метод.

Рассмотрим развернутую экономико-математическую модель задачи.

Система переменных: x1, x2

Система ограничений: 2x1 + x2 ≤ 9

5x1 + 4x2 ≤ 29

Целевая функция: F = 27x1 + 21x2 → max

Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения».

Описание шагов алгоритма «метода ветвей и границ»

  1. Решение вспомогательной задачи линейного программирования.

Вспомогательная задача № 1 получается из данной задачи целочисленного линейного программирования путём игнорирования требования целочисленности. Решим задачу симплексным методом с помощью Excel. В результате получим: х1=2,3, х2=4,3, Fmax=154 (схема 1).

2.Очередное ветвление вспомогательной задачи на две вспомогательные подзадачи нижнего уровня.

Так как вышеполученное решение нецелочисленное, то оно дает верхнюю границу F = 154 для максимума целевой функции искомого оптимального решения исходной задачи.

В этом случае одна из переменных, имеющих дробное значение, в данном случае x1, берется за основу для разбиения (ветвления) данной вспомогательной задачи № 1 на вспомогательные подзадачи под номерами 1.1 и 1.2 по нижеприведенной методике:

Так как 2 < x1=2,3 < 3, то:

задача 1.1. → задача 1.2.

2x1 + x2 ≤ 9 → 2x1 + x2 ≤ 9

5x1 + 4x2 ≤ 29 → 5x1 + 4x2 ≤ 29

х1<=2 → х>=3

х1>=0, х2>=0х1>=0, х2>=0

F = 27x1+21x2 → max → F = 27x1+21x2 → max

При решении подзадачи 1.1. в Excel добавим ограничение х1<=2

В результате получим:

х1=2, х2=4,75 Fмах=153,75.

153,75 — уточненная верхняя граница

При решении подзадачи 1.2. в Excel добавим ограничение х2>=3

В результате получим:

х1=3, х2=3, Fмах=144

Таким образом, получим первый целочисленный рекорд.

  1. Проверка оптимальности текущего целочисленного рекорда после очередного ветвления на основе формулировки критерия оптимальности текущего целочисленного рекорда по методу ветвей и границ:Текущий целочисленный рекорд объявляется оптимальным решением исходной задачи в том и только том случае, если при данном состоянии дерева решений на концах других ветвей не существует верхних границ, превосходящих значение рекорда.

В данном случае критерий не выполняется, так как 153,75 больше 144.

  1. Ветвление следует продолжить по подзадаче № 1.1, которая дает наибольшую на данный момент верхнюю границу из подзадач, находящихся на концах ветвей. В качестве основы для ветвления выбирается дробное значение переменной х2 = 4,75.

Так как 4 < x1=4,75 < 5 то

задача 1.1.1. → задача 1.1.2.

2x1+x2≤9 → 2x1+x2≤9

5x1+4x2≤29 → 5x1+4x2≤29

х2<=4 → х2>=5

х1<=2 → х1<=2

х1>=0, х2>=0х1>=0, х2>=0

F=27x1+21x2 → max → F=27x1+21x2 → max

При решении подзадачи 1.1.1. в Excel добавим ограничение х2<=4

В результате получим:

х1=2, х2=4, Fмах=138

При решении подзадачи 1.1.2. в Excel добавим ограничение х2>=5

В результате получим:

х1=1,8, х2=5, Fмах=153,6

153,6 — уточненная верхняя граница.

  1. Проверка оптимальности текущего целочисленного рекорда после очередного ветвленияпоказывает, что критерий вновь не выполняется, так как 153,6 больше 138.
  2. Продолжаем ветвление по подзадаче 1. Рассмотрим подзадачу 1.3.В качестве основы для ветвления выбирается дробное значение переменной х2 =4,3.

Так как 3 < x2=4,3 < 4 то

задача 1.3. → задача 1.4.

2x1+x2≤9 → 2x1+x2≤9

5x1+4x2≤29 → 5x1+4x2≤29

х2<=4 → х2>=5

х1>=0, х2>=0х1>=0, х2>=0

F=27x1+21x2 → max → F=27x1+21x2→ max

При решении подзадачи 1.3. в Excel добавим ограничение х2<=4

В результате получим:

х1=2,5, х2=4, Fмах=151,5

При решении подзадачи 1.4. в Excel добавим ограничение х2>=5

В результате получим:

х1=1,8, х2=5, Fмах=153,6

  1. Продолжим ветвление по подзадаче 1.4.

В качестве основы для ветвления выбирается дробное значение переменной х1 = 1,8.

Так как 1 < x1=1,8 < 2, то задача 1.4.1. → задача 1.4.2.

2x1+x2≤9 → 2x1+x2≤9

5x1+4x2≤29 → 5x1+4x2≤29

х2>=5 х2>=2

х1<=1 х1<=2

х1>=0, х2>=0 → х1>=0, х2>=0

F=27x1+21x2 →max → F=27x1+21x2 → max

При решении подзадачи 1.4.2. — поиск не может найти подходящего решения.

При решении подзадачи 1.4.1. в Excel добавим ограничение х2<=1.

В результате получим: х1=1, х2=6, Fмах=153

Таким образом, значение 153 является новым текущим целочисленным рекордом, отменяющим прежний рекорд 144.

Оптимальным решением этой задачи будет Fмах=153, при х1=1, х2=6.

Следует отметить, что никаким округлением решения вспомогательной задачи № 1 (х1=2,3, х2=4,3) в принципе невозможно получить оптимальное решение х1=1, х2=6.

Рис. 1. Алгоритм «метода ветвей и границ» Дерево решений

Литература:

  1. Гармаш А. Н., Орлова И. В. Математические методы в управлении: Учебное пособие. — М.: Вузовский учебник: ИНФРА-М, 2014. — 272 — c.
  2. Математическое моделирование экономических процессов в сельском хозяйстве / Гатаулин А. М., Гаврилов Г. В., Сорокина Т. М. и др.; Под ред. А. М. Гатаулина. — СПБ.: ООО «ИТК ГРАНИТ», 2009. — 432 с.
  3. Савиных В. Н. Математическое моделирование производственного и финансового менеджмента [Текст]: учеб. пособие / В. Н. Савиных. — Новосибирск: СГГА, 2007. — 219 с.
  4. Алексеев Г. В. Численное экономико-математическое моделирование и оптимизация [Электронный ресурс]: учебное пособие / Алексеев Г. В., Холявин И. И.— С.: Вузовское образование, 2013. 195— c. — Режим доступа: http://www.iprbookshop.ru/16905. — ЭБС «IPRbooks».
Основные термины (генерируются автоматически): задача, решение подзадачи, целочисленное линейное программирование, линейное программирование, вспомогательная задача, качество основы, дробное значение переменной, метод ветвей, текущий целочисленный рекорд, ветвление.


Похожие статьи

Решение интервальной задачи дробно-линейного...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования. Авторы: Немкова Елена Анатольевна, Левин Виталий Ильич. Рубрика: Математика.

Применение метода линейного программирования для...

Цель настоящей статьи — показать использование метода линейного программирования при решении текстовых задач по математике, предполагающих максимизацию (минимизацию) некоторой величины, например...

Решение многокритериальных задач линейного...

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

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Приложения линейного программирования к решению...

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. К решению краевых задач пространственных стержней при переменных упруго-пластических нагружениях.

Некоторые прикладные задачи целочисленного...

Значительная часть экономических задач, относящихся к линейному программированию, требует целочисленного решения [1…6]. К ним, например, относятся задачи, в которых переменные означают количество единиц продукции.

Математические методы маршрутизации доставки светлых...

целочисленное линейное программирование; – метод «ветвей и границ»; – методы локальной оптимизации

Методы целочисленного программирования впервые применили С. Миллер, А. Таккер и Р. Землин [2]. Метод основывается на том, что в задачах возникает...

Математическая модель управления обучением и её решение...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Применение методов нелинейного программирования к решению экстремальных геометрических задач.

Метод Гомори в решении целочисленной задачи оптимизации...

Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные принимают целочисленные значения [1, c. 136].

Решение интервальной задачи дробно-линейного...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования. Авторы: Немкова Елена Анатольевна, Левин Виталий Ильич. Рубрика: Математика.

Применение метода линейного программирования для...

Цель настоящей статьи — показать использование метода линейного программирования при решении текстовых задач по математике, предполагающих максимизацию (минимизацию) некоторой величины, например...

Решение многокритериальных задач линейного...

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

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Приложения линейного программирования к решению...

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. К решению краевых задач пространственных стержней при переменных упруго-пластических нагружениях.

Некоторые прикладные задачи целочисленного...

Значительная часть экономических задач, относящихся к линейному программированию, требует целочисленного решения [1…6]. К ним, например, относятся задачи, в которых переменные означают количество единиц продукции.

Математические методы маршрутизации доставки светлых...

целочисленное линейное программирование; – метод «ветвей и границ»; – методы локальной оптимизации

Методы целочисленного программирования впервые применили С. Миллер, А. Таккер и Р. Землин [2]. Метод основывается на том, что в задачах возникает...

Математическая модель управления обучением и её решение...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Применение методов нелинейного программирования к решению экстремальных геометрических задач.

Метод Гомори в решении целочисленной задачи оптимизации...

Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные принимают целочисленные значения [1, c. 136].

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Решение интервальной задачи дробно-линейного...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования. Авторы: Немкова Елена Анатольевна, Левин Виталий Ильич. Рубрика: Математика.

Применение метода линейного программирования для...

Цель настоящей статьи — показать использование метода линейного программирования при решении текстовых задач по математике, предполагающих максимизацию (минимизацию) некоторой величины, например...

Решение многокритериальных задач линейного...

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

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Приложения линейного программирования к решению...

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. К решению краевых задач пространственных стержней при переменных упруго-пластических нагружениях.

Некоторые прикладные задачи целочисленного...

Значительная часть экономических задач, относящихся к линейному программированию, требует целочисленного решения [1…6]. К ним, например, относятся задачи, в которых переменные означают количество единиц продукции.

Математические методы маршрутизации доставки светлых...

целочисленное линейное программирование; – метод «ветвей и границ»; – методы локальной оптимизации

Методы целочисленного программирования впервые применили С. Миллер, А. Таккер и Р. Землин [2]. Метод основывается на том, что в задачах возникает...

Математическая модель управления обучением и её решение...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Применение методов нелинейного программирования к решению экстремальных геометрических задач.

Метод Гомори в решении целочисленной задачи оптимизации...

Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные принимают целочисленные значения [1, c. 136].

Решение интервальной задачи дробно-линейного...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования. Авторы: Немкова Елена Анатольевна, Левин Виталий Ильич. Рубрика: Математика.

Применение метода линейного программирования для...

Цель настоящей статьи — показать использование метода линейного программирования при решении текстовых задач по математике, предполагающих максимизацию (минимизацию) некоторой величины, например...

Решение многокритериальных задач линейного...

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

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Приложения линейного программирования к решению...

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. К решению краевых задач пространственных стержней при переменных упруго-пластических нагружениях.

Некоторые прикладные задачи целочисленного...

Значительная часть экономических задач, относящихся к линейному программированию, требует целочисленного решения [1…6]. К ним, например, относятся задачи, в которых переменные означают количество единиц продукции.

Математические методы маршрутизации доставки светлых...

целочисленное линейное программирование; – метод «ветвей и границ»; – методы локальной оптимизации

Методы целочисленного программирования впервые применили С. Миллер, А. Таккер и Р. Землин [2]. Метод основывается на том, что в задачах возникает...

Математическая модель управления обучением и её решение...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Применение методов нелинейного программирования к решению экстремальных геометрических задач.

Метод Гомори в решении целочисленной задачи оптимизации...

Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные принимают целочисленные значения [1, c. 136].

Задать вопрос