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

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

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

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

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

Предположим, что у нас есть линейная функция

где — вектор коэффициентов, — вектор переменных.

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

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

Формальная математическая запись ЗЛП будет выглядеть следующим образом:

Любая задача на нахождение максимума линейной целевой функции может быть сведена к задаче на минимум. Для этого достаточно умножить целевую функцию на минус единицу:

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

при условии