Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Линейное программирование. Разновидности задач линейного программирования. Графический метод решения задачи линейного программирования.
Линейное программирование – математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира. Задача линейного программирования (ЛП), состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях. Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно. Описание метода Пусть задача линейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные. Найти минимальное значение функции
при ограничениях вида
и
Допустим, что система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми: . Линейная функция (1) при фиксированных значениях является уравнением прямой линии: .
Пример графического решения задачи линейного программирования с 6 условиями. Построим многоугольник решений системы ограничений (2) и график линейной функции (1) при . Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию: Найти точку многоугольника решений, в которой прямая опорная и функция при этом достигает минимума. Значения уменьшаются в направлении вектора , поэтому прямую передвигаем параллельно самой себе в направлении вектора . Если многоугольник решений ограничен (см. рисунок), то прямая дважды становится опорной по отношению к многоугольнику решений (в точках и ), причём минимальное значение принимает в точке . Координаты точки находим, решая систему уравнений прямых и . Если же многоугольник решений представляет собой неограниченную многоугольную область, то возможны два случая. Случай 1.Прямая , передвигаясь в направлении вектора или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу. Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху. |
Последнее изменение этой страницы: 2019-04-10; Просмотров: 243; Нарушение авторского права страницы