Главная / Системный анализ / Геометрическая интерпретация задач линейного программирования

Геометрическая интерпретация задач линейного программирования

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

1) Построим область дополнительных решений.

Каждое из неравенств системы ограничений геометрически определяет полуплоскость с граничными прямыми ai1x1+ai2x2=bi. Поэтому область дополнительных решений задачи – многогранник, если n>2, полученный в результате пересечения этих прямых.

В одной из вершин многоугольника целевая функция имеет экстремум.

2) Построим линии уровней целевой функции C1x1+C2x2=h, (h – const). Меняя значение h, т. е. меняя пропорционально значения x1 и x2 , будем передвигать линии уровней в направлении вектора С до тех пор, пока линия уровня пройдет через последнюю вершину. Координаты этой вершины можно найти пересечением прямых (например 1 и 2). Это и будет оптимальный план.

, ® I квадрант.