Мастерская программиста Гирича Семёна Николаевича
Решение задач линейного программирования

2. Решение графическим методом

Для начала надо построить систему координат. Размерность системы координат определяется количеством переменных в системе неравенств ограничений. Таким образом графическим методом решения обычно пользуются при двух переменных (двумерная система координат), реже при 3-х (трехмерная система координат). При больших количествах переменных не представляется возможным построить многомерную систему координат.

2.1. Построение графика области допустимых решений

Необходимо построить прямые ограничивающие область допустимых решений. Каждая прямая соответствует одному неравенству системы неравенств ограничений. Для получения координат двух точек по которым строится прямая знаки неравенств заменяют на равенства и находят корень полученного уравнения относительно каждой переменной. Таким образом получаются точки пересечения прямой с осями координат. Построив прямую определяют область допустимых решений ограничивающуюся этой прямой путем исследования точек находящихся по обе стороны прямой на удовлетворение их координат соответствующему этой прямой неравенству. Так получается область допустимых решений ограниченная прямыми.

2.2. Выбор оптимальной вершины

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


Далее: 2.3. Пример решения задачи ЛП графическим методом

Далее: 3. Решение методом симплекс-таблиц

Вернуться в Начало

© 2011 Семён Гирич,
Система Orphus: Выделите текст с ошибкой и нажмите [Ctrl] + [Enter]
Назад    Вверх