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

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

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

z = z(x,a).

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

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

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

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

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

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

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

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