Определение. Общей задачей линейного программирования называется задача, которая состоит в определении максимума (минимума) целевой функции
Z(x1,...xn) = c1x1+...+cnxn max (min) (2. 1)
при ограничениях:
(2.2)
(2.3)
x j 0, (j = 1,….n). (2.4)
Определение. Функция (2.1) называется целевой функцией или линейной формой задачи линейного программирования, а условия (2.2) - (2.4) - ограничениями данной задачи.
Определение. Стандартной (симметричной) задачей линейного программирования называется задача, которая состоит в определении экстремального значения целевой функции (2.1) при выполнении условий (2.2) и (2.4).
Определение. Основной (канонической) задачей линейного программирования называется задача, которая состоит в определении экстремального значения целевой функции (2.1) при выполнении условий (2.3) и (2.4).
Определение. Вектор или совокупность чисел `Х = (х1, х2,...., хn), удовлетворяющих ограничениям задачи (2.2) - (2.4), называется допустимым решением или планом задачи линейного программирования.
Определение. План `Х*=(х1*, х2*,...., хn*), при котором целевая функция (2.1) принимает свое оптимальное (минимальное или максимальное) значение, называется оптимальным планом.
|
|
Таким образом, линейное программирование является частью математического программирования, особенностью которого является то, что исследуемая целевая функция является линейной: Z(x1,...,xn)=c1x1+...+cnxn, а ограничения, накладываемые на переменные, представляют собой линейные уравнения или неравенства.
Если же целевая функция или система ограничений нелинейная, то соответствующая задача является задачей нелинейного программирования.
Если требуется провести поиск целочисленных значений x j, то приходим к задаче целочисленного линейного программирования (ЦЛП).
2.2. Геометрическое решение задач линейного программирования
Геометрическое решение задач линейного программирования приемлемо для случаев n 3.
Как известно, линейное уравнение a1x1 + a2x2 = b задает на плоскости (в пространстве R2) прямую; уравнение a1x1 + a2x2 + a3x3 = b - плоскость в R3. Точно так же уравнение ai1x1 +... + ainxn= bi (i - е ограничение в канонической задаче ЛП) определяет в пространстве Rn некоторое множество, называемое гиперплоскостью.
Определение. Фигура на плоскости называется выпуклой, если наряду с любыми ее точками М1 и М2 ей принадлежат и все точки отрезка М1М2.
Например, отрезок, треугольник, квадрат, острый угол.
Определение. Множество X называется выпуклым, если вместе с любыми двумя точками (элементами) (x, y); (x, y) X оно содержит отрезок между этими точками, т.е. точки вида
y+( 1 - )x, (0 1).
Это уравнение является уравнением отрезка.
Теорема. Пересечение любого числа выпуклых множеств является выпуклым множеством.
|
|
Очевидно, прямая в R2, плоскость в R3 являются выпуклыми множествами. Точно так же, выпуклым множеством является гиперплоскость ai1x1 +... + ainxn = bi и полупространство (вместе с границей) в Rn, определяемое i -м ограничением в стандартной задаче:
ai1x1 +... + ainxn bi.
Система ограничений (2.2) задает множество М - пересечение m выпуклых множеств в n -мерном евклидовом пространстве Rn, поэтому само является выпуклым множеством. Множество М называется выпуклым многогранником (областью) допустимых решений.
При наличии только двух переменных М задает многоугольник решений в R2, а в случае переменных x1, x2, x3 - выпуклый многогранник в пространстве R3.
Геометрическое решение задачи линейного программирования состоит в том, что из всех допустимых решений требуется выделить оптимальное решение, определяющее экстремум целевой функции Z.
Теорема. Функция цели (2.1) задачи линейного программирования достигает экстремума в угловой точке выпуклого множества допустимых решений.
Решить задачу графического - значит найти угловую точку выпуклого множества области допустимых решений, координаты которой дают экстремум функции цели.