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

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

Функция n переменных x ₁, x ₂,... x _n, называется линейной функцией, если она представима в виде линейной комбинации переменных, то есть в виде суммы переменных с постоянными коэффициентами

.

Иногда линейной называют также функцию вида

,

отличающуюся от предыдущей постоянным слагаемым d.

Равенство , а также неравенства

,

называются линейным равенством и линейными неравенствами, если функция

является линейной.

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

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

Функция, экстремальное значение которой требуется отыскать, называется целевой функцией. Система равенств и неравенств называется системой ограничений.

Всякий набор значений переменных, то есть вектор X значений,

называется планом задачи. План называется допустимым планом, если он удовлетворяет системе ограничений. Обычно (но не всегда) множество допустимых планов бесконечно. На разных планах целевая функция принимает различные значения. Задача линейного программирования требует, чтобы среди всех допустимых планов был найден тот план, на котором целевая функция достигает искомого экстремального значения (максимального и минимального, в зависимости от конкретной задачи). Такой план называется оптимальным планом. Значение целевой функции на оптимальном плане называется оптимумом.

Решить задачу линейного программирования - значит найти ее оптимальный план и оптимум.