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

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

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

z = z(x,α)

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

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

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

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

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

α₁₁ x₁ + α₁₂ x₂ +...+ α_1n x_n = b₁

α₂₁ x₁ + α₂₂ x₂ +...+ α_2n x_n = b₂

....................................... (2.1)

α_m1 x₁ + α_m2 x₂ +...+ α_mn x_n = b_m

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

z = z(x₁,x_2,,...,x_n) = c_lx_l +с₂х₂ +... + с_пх_п → max (2.2)

х_i >0, где i =1,.., n (2.3)

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

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