Условия применения метода линейного программирования

ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ С ПОМОЩЬЮ МЕТОДА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задачи линейного программирования обычно сводятся к необходимости максимизировать или минимизировать некоторую количественную величину с учетом ряда ограничений. Целевая функция и ограничения записываются линейными уравнениями. Задача линейного программирования имеет вид:

W = ф(а, х) → max(min),

где а - заданные условия;

х - элементы решений, x=(x₁,x₂,... х_n); п - число решений (n-мерный вектор).

Линейное программирование используется для оптимизации процессов, связанных с распределением ресурсов, организацией работ, решением транспортных задач и др.

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

• показатель эффективности W линейно зависит от элементов решения x₁, х₂,... х„;

• ограничения, налагаемые на элементы решения, представлены линейными равенствами или неравенствами относительно х₁, х₂,... х_n

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

Линейная функция этих переменных должна обеспечивать экстремальные значения:

L = С₁x₁, + С₂х₂ +......С_nx_n→ тax

Трудности решения задач линейного программирования часто возникают в случае некорректной их постановки и задания нереальных ограничений.

Задачи линейного программирования далеко не всегда имеют решения. Назовем наиболее типичные случаи:

• условия равенства общей задачи линейного программирования могут противоречить друг другу в области неотрицательных решений;

• допустимые решения существуют, но целевая функция не имеет оптимума (не ограничена).

Задачи линейного программирования наглядно иллюстрируются графически. Если число уравнений т, число переменных п=т+2, то интерпретация поставленной задачи может быть представлена на плоскости. Имея в виду n-m=k+2, линейные независимые уравнения-равенства можно разрешить относительно каких-либо т базисных переменных.

В линейном программировании часто приходится сталкиваться с взаимно двойственными задачами, когда:

• одна из задач является задачей максимизации, а другая - минимизации, в системе ограничений неравенства;

• записываются со знаком > или <;

• каждому ограничению одной задачи соответствует переменная другой за дачи; номер переменной совпадает с номером ограничения, при этом ограничению, записанному в виде неравенств, соответствует переменная, связанная условиями неотрицательности;

• коэффициенты целевой функции одной задачи соответственно равны свободным членам другой задачи;

• матрица условия одной задачи получается из матрицы условий другой задачи с помощью транспонирования.

Дата добавления: 2014-12-25