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

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

Пусть необходимо найти минимум целевой функции:

(1.1)

При ограничениях:

(1.2)

Переменные x₁ иx₂ должны быть неотрицательными.

Поэтому множество точек, являющихся возможными (допустимыми) решениями, может находиться в первом квадранте (см. рис. 1.1.) . Неравенства–ограничения изображены в виде полуплоскостей, границами которых являются прямые (графики функций), полученные из неравенств путём отбрасывания знаков >,<. Полуплоскости образуют выпуклый многоугольник (многоугольник решений – симплекс).

Линейная форма (линия уровня) для некоторого набора фиксированных значений переменнойzпредставляет собой семейство параллельных прямых. Одна из них, которая пройдёт через вершину многоугольника «М», ближайшую к началу координат и даст минимумz(для координат вершины).

Определив координаты точки М (8/7;4/7) получим:

z= 28/7 + 34/7 = 4

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

Области допустимых решений, изображённые на рис.1.2,а) и 1.2,б) – выпуклые многоугольники. На рис.1.2,а) максимум достигается в одной точке, задача имеет единственное решение (максимизирует z). На рис.1.2,б) задача имеет альтернативный оптимум, максимумz достигается в любой точке отрезка АВ, так как соотношения коэффициентов при неизвестныхx₁ иx₂в одном из ограничений и в целевой функции совпадают.

Примечание.

При построении z=6.

Рис. 1.1.

На рис.1.2,в) и 1.2,г) представлен случай, когда область допустимых решений – неограниченная фигура. В зависимости от вида zцелевая функция достигает минимума в точке «В» (рис.1.2,в) и не имеет максимума (z_max  ) или (рис.1.2,г) оказывается неограниченной сверху и снизу (z_max  ; z_min  - ).

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

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

Графический способ решения (перемещение графика целевой функции по симплексу) приемлем только для двухмерных задач (задач на плоскости). Но геометрическое толкование задачи линейного программирования справедливо и для общего случая (m ограничений и n переменных). Каждое из соответствующих неравенству уравнений системы определяет некоторую гиперплоскость в n – мерном пространстве. Множество неотрицательных решений образует выпуклый многогранник в n – мерном пространстве. Линейная форма z-гиперплоскость, перемещая которую параллельно самой себе, будем получать множество точек пересечения её с выпуклым многогранником. Максимальное или минимальное значение линейной формыzдостигается в точках, являющихся вершинами выпуклого многогранника.

Рис. 1.2