Главная » Справочник » Основы организации и управления транспортными системами » Графоаналитический метод решения простейших линейных оптимизационных моделей

Графоаналитический метод решения простейших линейных оптимизационных моделей

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

Алгоритм графоаналитического метода состоит из следующих действий (итераций):

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

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

Предыдущая статья График движения поездов Следующая статья Двойственные задачи линейного программирования

Статьи по теме