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

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

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

- совокупность неизвестных величин,

- целевую функцию;

- ограничения.

Совокупность неизвестных величин – это те величины, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.).

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

Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов оборудования, отходы производства и т. д.;

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

Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений (область технических, техно-логических, экономических и других возможностей).

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

Одним из разделов математического программирования является линейное программирование.

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

Формы записи задачи линейного программирования.

Общей задачей линейного программирования называют задачу нахождения максимума или минимума линейной функции:

(8.21)

при ограничениях:

(8.22)

 

где: x_i - искомые величины, оптимум которых необходимо найти, - коэффициенты, заданные действительные числа, определяющие условия использования искомых величин x; i - порядковый номер ограничения; j- номер переменной; n - количество искомых переменных; m - количество ограничений;

- план задачи.

На практике система уравнений 8.21-8.22 представляется в виде матриц A и векторов коэффициентов c и b, которые будут рассмотрены ниже. Чтобы задача имела решение, система её ограничений (8.22) должна быть совместной. Это означает, что число уравнений этой системы m не должно быть больше числа неизвестных n. Случай m > n вообще невозможен. При m= n система имеет единственное решение, которое будет при

оптимальным. В этом случае проблема выбора оптимального решения теряет смысл.

Если m < n, то в этом случае система векторов содержит базис - максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Каждый из них состоит точно из m векторов. Переменные, соответствующие m векторам базиса, называют базисными. Остальные n – m переменных будут свободными. Базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свободными будут переменные .

Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы будет называться опорным решением (планом).

Нахождение оптимального значения линейной функции с ограничениями осуществляется с помощью симплекс-метода. Общая идея симплексного метода

(метода последовательного улучшения плана) для решения задачи линейного программирования состоит в:

- нахождении начального опорного плана;

- определении признака оптимальности опорного плана;

- переходе к не худшему опорному плану.

Решение подобной задачи можно осуществить с помощью специального пакета прикладных программ.

В ППП Матлаб решение задач линейного программирования после представления соответствующих матриц осуществляется вызовом оператора

x = linprog (f, A, b, Aeq, beq, lb, ub) (8.23)

или [ x, fval ] = linprog (f, A, b, Aeq, beq, lb, ub),

где: x - выходной вектор оптимальных иcкомых переменных;

fval- оптимальное значение целевой функции;

f - вектор коэффициентов целевой функции,;

A - матрица коэффициентов левой части уравнений ограничений;

b- вектор коэффициентов правой части уравнений ограничений;

Aeq - матрица коэффициентов левой части уравнений равенств;

beq - вектор коэффициентов правой части уравнений равенств;

lb - вектор нижнего порога ограничений искомых переменных;

ub - вектор верхнего порога ограничений искомых переменных.

Оператор linprog минимизирует функцию

minx f^T x

при ограничениях:

Ax <= b;

A_eq = beq;

lb <= x <= ub

и выдает решение в виде вектора оптимальных значений переменных x и оптимального значения целевой функции f_val = min f.

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

Главное применение метода - оптимальное распределение некоторых ресурсов (материалов, энергии, времени и т.п.) с позиций выбранного критерия и при заданных ограничениях. Типичные примеры использования в сельском хозяйстве: распределение земли по культурам, принятие решений о типах и нормах внесения минеральных удобрений, подбор рациона наименьшей стоимости для сельскохозяйственных животных, планирование трудозатрат и потребностей в технике.

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