4. Краткие сведения из теоретического курса

Математические методы оптимизации применяются при решении задач распределения ресурсов, планирования производства, распределения запасов и перевозок. Суть их заключается в том, что из множества вариантов нужно выбрать оптимальный.

Для решения задач оптимизации разработано несколько методов. Во многих случаях решение задачи сводится к отысканию максимума или минимума некоторой функции. Такая функция называется целевой или функцией цели.

Дадим общую формулировку задачи линейного программирования.

Пусть переменные х₁, х₂, х₃…х_n– определяют рассматриваемый процесс. Эти переменные должны удовлетворять некоторым условиям, выраженным в виде системы линейных уравнений или неравенств. Для записи этих уравнений или неравенств в общем виде воспользуемся буквенной символикой (а_ij – коэффициенты). Тогда систему ограничений можно записать:

Кроме этих общих ограничительных условий, в задачах линейного программирования фигурируют еще условия неотрицательности: х₁0, х₂0,… х_n0.

Любая совокупность значений х₁, х₂, х₃…х_n, удовлетворяющих системе и условиям определяет один из допустимых вариантов процесса. В общем случае их будет бесчисленное множество. Каждый из этих вариантом характеризуется величиной:

,

где х_i – переменные, удовлетворяющие системе неравенств, с_i – постоянные числа.

Конечной целью исследования является определение такого допустимого варианта решения, для которого функция h (целевая функция) принимает оптимальное (наибольшее или наименьшее) значение.

Итак, формулировка задачи линейного программирования: найти совокупность значений n переменных х₁, х₂, х₃…х_n, удовлетворяющих системе ограничительных условий, условиям неотрицательности и для которых целевая функция принимает наибольшее (или наименьшее) значение.

Совокупность значение х₁, х₂, х₃…х_n , удовлетворяющих системе ограничений, называется допустимым решением, а допустимое решение, для которого функция принимает наибольшее или наименьшее значение – оптимальным решением задачи линейного программирования.