Геометрическая интерпретация - Математические методы и модели в экономике

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

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

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

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

Выбор каждой последующей экстремальной точки при использовании симплекс-метода определяется следующими двумя правилами:

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

Cоответствия геометрических и алгебраических определений представлены в таблице:

Геометрическое определение

Алгебраическое определение (симплекс метод)

Пространство решений

Ограничения модели в стандартной форме

Угловые точки

Базисное решение задачи в стандартной форме

Рис. 1

На рисунке 1 приведен пример Хахулин Г. Ф., Красовская М. А., Булыгин В. С. Теоретические основы автоматизированного управления. Стр.20. некоторого множества допустимых решений ЗЛП с тремя ограничениями типа неравенства и условиями неотрицательности обеих оптимизационных переменных. Любое ограничение типа неравенства разделяет всю плоскость на две полуплоскости. Графически это изображено прямой линией со штриховкой в сторону полуплоскости, где ограничение выполняется. Ограничения типа равенства определяет множество точек, находящихся на соответствующей прямой.

На рис. 1 видно, что множество допустимых решений ЗЛП для случая двух переменных представляет собой выпуклый многогранник, ограниченный прямыми. Несложно представить, что в задаче с тремя переменными допустимое множество в общем случае будет не плоским, а объемным выпуклым многогранным множеством, ограниченным плоскостями. В n-мерном случае множество D также представляет собой выпуклое многогранное множество, ограниченное гиперплоскостями.

Геометрическая интерпретация перестает быть пригодной при числе свободных переменных n - m > 3, а затруднительна уже при n - m = 3. Для нахождения решения задачи линейного программирования в общем случае (при произвольном числе свободных переменных) применяются не геометрические, а вычислительные методы. Из них наиболее универсальным является симплекс-метод.

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




Геометрическая интерпретация - Математические методы и модели в экономике

Предыдущая | Следующая