Графический метод. Методы решения задач линейного программирования

Методы решения задач линейного программирования

Линейное программирование является наиболее изученным разделом математического программирования. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ.

Задача линейного программирования в общем виде при наличии только двух переменных допускает геометрическую интерпретацию и может быть решена графически.

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

Как известно из курса аналитической геометрии, линейное неравенство вида a₁x₁ + a₂x₂ ≤ b определяет на плоскости (x₁, x₂) одну из двух полуплоскостей, на которые прямая a₁x₁ + a₂x₂ = b разбивает эту плоскость. Таким образом, допустимое множество ЗЛП является пересечением m+2 полуплоскостей, соответствующих ограничениям-неравенствам 2-5, и представляет собой либо выпуклый многоугольник (рис.1а), либо неограниченное многоугольное множество (рис.1б), либо пустое множество (рис.1в).

а б в

Рис.1. Допустимое множество ЗЛП в двумерном случае

Целевая функция определяет на плоскости семейство параллельных прямых каждой из которых соответствует определенное значение Z. Вектор C = (c₁; c₂) перпендикулярный к этим прямым указывает направление наискорейшего возрастания функции Z и называется градиентом функции, а противоположный вектор -C = (-c₁; -c₂) называется антиградиентом функции и указывает убывание функции.

Порядок решения ЗЛП графическим методом:

1. построить прямые, уравнения которых получаются в результате замены в ограничениях 2,3,5 знаков неравенств на знаки равенств;

2. найти полуплоскость, определяемую каждым из ограничений задачи;

3. определить многоугольник решений;

4. построить вектор C = (c₁; c₂);

5. построить прямую Z = c₁x₁ + c₂x₂ = 0 проходящую через начало координат и перпендикулярную вектору C;

6. передвигать прямую Z = c₁x₁ + c₂x₂ = 0 в направлении вектора C, в результате чего находят точку (или точки) в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве плана;

7. определить координаты точки максимума функции и вычислить значение целевой функции в этой точке.

Дата добавления: 2014-01-15