Понятие линейного программирования (ЛП). Общий вид задачи. Условия задачи (виды ограничений) и целевая функция.

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

В общем виде постановка задачи ЛП заключается в следующем. Требуется найти экстремум (максимум или минимум) линейной целевой функции

Обычно включаемое в систему тривиальное условие неотрицательности переменных хj? 0 (j = 1, n) вытекает из реального экономического смысла разрешаемости задач.

Систему ограничений называют функциональными ограничениями задачи ЛП, а ограничения хj? 0 – прямыми.

Наиболее часто встречается две разновидности задач ЛП:

1) Каноническая задача ЛП. В этом случае система ограничений, помимо тривиальных ограничений включает в себя только уравнения.

2) Стандартная задача ЛП. Это означает, что система условий состоит только из неравенств, в число которых входят тривиальные ограничения: n

Стандартная задача ЛП может быть сведена к канонической. Добавив в систему ограничений некоторые дополнительные переменные хn+k? 0 со знаком " -" в случае ограничений типа? и со знаком " +" в случае ограничений типа?, можно превратить ее из системы неравенств в систему уравнений.

Переход от задачи на минимум к задаче на максимум (и наоборот) осуществим путем умножения целевой функции на – 1.

В качестве примера можно привести следующую задачу.

Целевая установка оптимизации заключается в том, чтобы, например, свести ожидаемые при решении данной задачи издержки предприятий к минимуму.

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

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

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

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

Геометрическое представление задачи ЛП служит отправной точкой для наиболее часто используемого метода решения – симплекс метода.

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

Целевая функция задачи ЛП тоже является выпуклой. Она описывается уравнением плоскости f(х) = с1х1 + с2х2 + … + сnхn. Представим, что в вершинах выпуклого многоугольника области допустимых планов мы установим «столбы», высота которых определяет значения целевой функции в данной вершине. На эти «столбы» наложим плоскость. Очевидно, что максимального и минимального значения целевая функция задачи ЛП достигает либо в вершине выпуклого многогранника, либо на одной из его граней.

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

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