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

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

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

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

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

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

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

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

Наиболее важным разделением ЗЛП является разделение на безусловные и условные ЗЛП. Формулировка безусловной ЗЛП приведена выше.