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

Линейное программирование – раздел прикладной математики, занимающийся методами исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции многих переменных, на независимые переменные которых наложены линейные ограничения.

Такая линейная функция называется целевой, а набор количественных соотношений между переменными, выражающих определенные требования экономической задачи в виде уравнений или неравенств, называется системой ограничений. Совокупность соотношений, содержащих целевую функцию и ограничения на ее аргументы, называется математической моделью экономической задачи оптимизации. Слово «программирование» введено в связи с тем, что неизвестные переменные, которые находятся в процессе решения задачи, обычно определяют программу (план) работы некоторого экономического субъекта.

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

Задача линейного программирования (ЗЛП) ставится следующим образом: найти экстремум (максимум или минимум) линейной целевой функции

, (1.1)

при линейных ограничениях:

(1.2)

(1.3)

где , , (, ) – известные величины, () – управляющие переменные. Формулы (1.1) – (1.3) представляют собой запись задачи линейного программирования в развернутом (координатном) виде.

Матричная запись ЗЛП имеет вид:

где – вектор-столбец коэффициентов целевой функции, – вектор управляющих переменных, – вектор-столбец свободных членов, – матрица коэффициентов при управляющих переменных (матрица условий).

Определение 1.1. Систему (1.2) называют системой функциональных, или ресурсных ограничений задачи линейного программирования.

Определение 1.2. Неравенства (1.3) называют прямыми ограничениями задачи линейного программирования.

Определение 1.3. Вектор , удовлетворяющий системе неравенств (1.2) – (1.3), называют допустимым решением или допустимым (опорным) планом задачи линейного программирования.

Определение 1.4. Допустимое решение , доставляющее целевой функции максимум или минимум, называют оптимальным решением, или оптимальным планом задачи линейного программирования.