Линейное программирование

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

Частными случаями линейного программирования является ЦелочисленноеПрограммирование и дробно-линейное программирование.

В данной статье все вектора по умолчанию являются векторами-строками. Внимательно следите за размерностями матриц и векторов по ходу объяснения.

Содержание

Общая постановка задачи линейного программирования

Предположим, что у нас есть линейная функция f( bold x ) = bold cx sup roman T = sum from i=1 to n c sub i x sub i = c sub 1 x sub 1 + ldots + c sub n x sub n ~ ,

где bold c = (c sub 1 , ldots , c sub n ) — вектор коэффициентов, bold x = (x sub 1 , ldots , x sub n ) — вектор переменных.

Эту линейную функцию будем называть целевой функцией или функцией цели.

Задача линейного программирования (ЗЛП) заключается в нахождении такого вектора bold x, при котором целевая функция f( bold x ) примет своё наименьшее значение.

Формальная математическая запись ЗЛП будет выглядеть следующим образом: min from bold x f( bold x ).

Любая задача на нахождение максимума линейной целевой функции может быть сведена к задаче на минимум. Для этого достаточно умножить целевую функцию на минус единицу: max from bold x f( bold x ) ~ \\(ti ~ min from bold x (-f( bold x )).

Наиболее важным разделением ЗЛП является разделение на безусловные и условные ЗЛП. Формулировка безусловной ЗЛП приведена выше. Такие задачи встречаются относительно нечасто. Более частыми и востребованными в реальной практике (в задачах управления/самоуправления в технических, экономических и проч. системах) являются условные ЗЛП. Условная ЗЛП формулируется как безусловная ЗЛП и ограничения на модели, которые задаются линейными уравнениями и/или неравенствами. Приведём пример: min from bold x f( bold x ) ~ ,

при условии A bold x sup roman T >= bold b sup roman T ~ ,

где A — матрица коэффициентов линейных ограничений (содержит m неравенств), а вектор bold b — вектор свободных членов линейных ограничений.

Условная ЗЛП, приведённая выше, называется основной задачей линейного программирования (ОЗЛП). Задача, в которой все ограничения являются равенствами называется канонической задачей линейного программировани (КЗЛП). ОЗЛП можно свести к КЗЛП путём переноса в левую часть правой части и вычитания из левой части вектора bold d sup roman T, который называют вектором инструментальных переменных (вроде бы).

Методы решения задач линейного программирования

Одним из наиболее эффективных методов решения ЗЛП является СимплексМетод.


КатегорияПрикладнаяМатематика | КатегорияЛинейноеПрограммирование | КатегорияЛинейнаяАлгебра