Целочисленное линейное (дискретное) программирование. Метод ветвей и границ
Решение задачи целочисленного линейного программирования симплекс-методом ветвей и границ. Составление оптимального плана выпуска продукции предприятия. Определение необходимого количества изделий с целью получения максимальной прибыли от их реализации.
| Рубрика | Математика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 28.03.2020 |
| Размер файла | 248,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Тема:
Целочисленное линейное (дискретное) программирование. Метод ветвей и границ
Задание
Найти решение задачи целочисленного линейного программирования методом ветвей и границ. По плану производства продукции предприятию необходимо изготовить изделия. Составить оптимальный план выпуска продукции, при котором прибыль предприятия от реализации всех изделий была бы максимальной.
|
Вид сырья |
Номы расхода сырья на одно изделие, кг |
Общее количество сырья, кг |
||
|
Х1 |
Х2 |
|||
|
I II |
5 4 |
7 9 |
35 36 |
|
|
Прибыль от реализации одного изделия, руб. |
2 |
3 |
Математическая постановка задачи:
при ограничениях:
Идея метода ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.
Решаем данную задачу как обычную задачу линейного программирования, полагая, что граничное значение функции, где - целевая функция. Запишем систему ограничений и целевую функцию:
Строим график функции для первого и второго уравнений, для этого выражаем x2 из 1-го и 2-го уравнений:
- получаем точки (0; 5); (7; 0);
- получаем точки (0; 4); (9; 0)
Рис. 1
Областью допустимых решений является многоугольник ОАВС, где точки имеют соответствующие координаты: О (0; 0); А (0; 4); В (3,7; 2,35); С (7; 0). Координаты точки В получены в результате пересечений прямых, их находим решая систему уравнений: . Получаем x1 = 3,7; x2 = 3,7.
Определяем, какая из граничных точек многоугольника ОАВС - возможных решений является оптимальной. Для этого можно использовать графический или аналитический симплекс - метод. Симплекс - метод - метод целенаправленного комбинаторного перебора вершин многогранника ограничений, результатом которого является выбор оптимальной точки целевой функции. Перебор вершин многогранника ограничений прекращается, если на некотором шаге получена вершина, в которой значение целевой функции хуже, чем в предыдущей.
Точкой, от которой начинается движение вдоль вершин многогранника ограничений является точка О (0; 0), а f(0; 0) = 0. Движение будет осуществляться по часовой стрелке.
Найдем значение целевой функции в точке А с координатами (0; 4):
f(0; 4) = 2*0+3*4 = 12
Так как fA>fO - движение продолжается.
Найдем значение целевой функции в точке В с координатами (3,7; 2,35):
f (3,7; 2,35) = 2*3,7+3*2,35 = 14,45
Так как fВ>fА - движение продолжается в том же направлении.
Найдем значение целевой функции в точке С с координатами (7; 0):
f (7; 0) = 2*7+3*0 = 14. Так как fВ>fС - движение вдоль вершин многогранника прекращается.
Таким образом, получаем что точка В (3,7; 2,35) является оптимальной.
Так как координаты точки В являются нецелочисленными необходимо использовать метод ветвей и границ. Ветвление можно начинать по любой координате (обе они не являются целочисленными). В примере рассмотрено начальное ветвление по второй координате.
симплекс ветвь выпуск продукция прибыль
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Задача 1 разбивается на две подзадачи таким образом, что ограничения каждой из полученных задач включают систему ограничений исходной задачи и к ним добавляется для одной подзадачи - для другой. Целевая функция каждой из полученных подзадач совпадает с целевой функцией исходной задачи.
Рассмотрим продолжение дерева ветвлений к задаче №3. Окончательные ветви дерева ветвлений для задачи 5 представлены на следующей странице.
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Расположение точек смотреть на рис. 2.
Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет f = 14 в точках В(4; 2) и С(7; 0).
Рис. 2. Область допустимых решений
Ответ: оптимальное значение f = 14 в точках В(4; 2) и С(7; 0).
Размещено на allbest.Ru
...Подобные документы
Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.
курсовая работа [153,2 K], добавлен 25.11.2011Составление плана выпуска продукции с целью получения максимальной прибыли при ее реализации. Вид и запас сырья, прибыль от единицы продукции и общее количество. Приведение системы ограничений к каноническому виду. Составление симплексной таблицы.
практическая работа [12,8 K], добавлен 24.05.2009Методы определения объемов выпуска изделий каждой модели, при которых прибыль будет максимальна Составление математической модели задачи целочисленного программирования. Решение задачи симплекс-методом. Поиск целочисленного решения методом отсечения.
контрольная работа [156,9 K], добавлен 30.01.2011Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.
задача [26,1 K], добавлен 27.11.2015Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера.
контрольная работа [253,0 K], добавлен 07.06.2011Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление.
задача [53,0 K], добавлен 24.07.2009Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
курсовая работа [219,4 K], добавлен 17.04.2013Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
курсовая работа [37,2 K], добавлен 01.05.2011Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлен 09.04.2013Определение допустимого решения задачи линейного программирования методом введения искусственного базиса. Целочисленное линейное программирование с булевскими переменными. Поиск минимума функции методом градиентного спуска. Одномерная минимизация.
курсовая работа [281,7 K], добавлен 27.05.2013Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Решение систем уравнений по правилу Крамера, матричным способом, с использованием метода Гаусса. Графическое решение задачи линейного программирования. Составление математической модели закрытой транспортной задачи, решение задачи средствами Excel.
контрольная работа [551,9 K], добавлен 27.08.2009Общая формулировка задания на курсовой проект. Линейное программирование. Задача целочисленного линейного программирования, с булевскими переменными. Нелинейное программирование. Задача поиска глобального экстремума функции.
курсовая работа [506,1 K], добавлен 17.05.2006Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
курсовая работа [67,5 K], добавлен 25.11.2011Общее понятие вектора и векторного пространства, их свойства и дополнительные структуры. Графический метод в решении задачи линейного программирования, его особенности и область применения. Примеры решения экономических задач графическим способом.
курсовая работа [1,2 M], добавлен 14.11.2010Теория динамического программирования. Понятие об оптимальной подструктуре. Независимое и полностью зависимое множество вершин. Задача о поиске максимального независимого множества в дереве. Алгоритм Брона-Кербоша как метод ветвей, границ для поиска клик.
реферат [224,1 K], добавлен 09.10.2012
