Задача линейного программирования

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

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

(1)

при условии, что на переменные наложены ограничения в виде линейных равенств или неравенств:

(2)

Линейная функция Z, оптимальное значение которой отыскивается в ЗЛП, называется целевой функцией, или функцией цели.

Совокупность значений переменных , удовлетворяющих условиям ЗЛП и образующих область определения функции Z, называется областью допустимых значений переменных, или просто допустимой точкой.

Набор значений из допустимой области, при котором целевая функция Z принимает оптимальное значение, называется решением ЗЛП, или оптимальным планом.

Из теории экстремума функции многих переменных известно, что оптимальное значение функция нескольких переменных достигает или на границе области её определения, или внутри области определения, а именно, в одной из точек экстремума. Известно также, что необходимым условием экстремума функции многих переменных является обращение в нуль всех её частных производных во внутренней точке области определения. Но частные производные линейной функции нигде в области её определения одновременно в нуль не обращаются, следовательно, оптимальное значение функция Z может принимать только на границе области.

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