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

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

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

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

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

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

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

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

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

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

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

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

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

при условии

где — матрица коэффициентов линейных ограничений, а вектор — вектор свободных членов линейных ограничений.

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

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

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