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

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

Пусть имеет некоторое целевая функция z, зависит от параметров x=(x₁ x₂,..., x_n), удовлетворяющих некоторым ограничениям α.

z = z(x,α).

Нужно найти такие значения параметров или функций х=(х₁ х₂,..., х_п), обращающих величину z в максимум или минимум (то есть функція z в них достигает экстремума).

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

Среди задач математического программирования простейшими являются задачи линейного программирования (ЗЛП). При этом целевая оптимизируемая функция z = z(x,α), линейно зависит от x=(x₁, х₂,...x_n) и, кроме того, ограничения, накладываемые на х, имеют вид линейных равенств или неравенств.

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

Основная задача линейного программирования (ОЗЛП) заключается в определении неотрицательных значений n переменных х₁, х₂,... х_п удовлетворяющих m условиям - равенствам::

(1)

и вращающиеся в максимум линейную функцию (целевую функцию) этих переменных^

z = z(x_l,x₂,...x_n) = c_lx₁ +c₂х₂ +... + с_пх_п → mах (2)

х_i ≥ 0, де i=1,2,..,n (3)

Допустимым решением (планом) ОЗЛП является упорядоченное множество значений х₁, х₂,..., х_п, удовлетворяющих ограничениям (1) и (3).

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

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