Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Общая постановка оптимизационных задач.

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

Под ЭФФЕКТИВНОСТЬЮ операции понимается степень ее приспособленности к выполнению стоящей перед ней задачи. Чем лучше организована операция, тем она эффективнее.

В качестве количественной меры достижения поставленной цели или степени соответствия хода операции поставленной цели используют специальный признак - КРИТЕРИЙ ЭФФЕКТИВНОСТИ. Критерий эффективности - (от греческого kriterion - отличительный признак, средство для решения, мерило) представляет собой признак, по которому производится сравнительная оценка альтернатив и выбор наилучшего решения.

КРИТЕРИЕМ ЭФФЕКТИВНОСТИ операции называется формальное соотношение, отражающее математическую связь между допустимыми вариантами решения и мерой достижения поставленной цели - эффективностью операции.

То есть, критерий эффективности представляют в виде некоторой функции или функционала, аргументами которой являются допустимые варианты решения, а значениями - числа, которые характеризуют меру (степень) достижения поставленной цели. Эту функцию (функционал) принято называть еще ЦЕЛЕВОЙ ФУНКЦИЕЙ. Задача принятия решения сводится, тем самым, к нахождению максимального (или минимального) значения целевой функции, а также к нахождению того конкретного решения - аргумента, на котором это значение достигается. Такое решение, максимизирующее (минимизирующее) значение целевой функции, и является оптимальным решением.

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

Все переменные и параметры, входящие в описание исследуемой операции, можно разделить на две группы:

1) экзогенные параметры (или переменные) - параметры, характеризующие условия проведения операции. Они задаются вне модели, то есть, известны заранее, и на которые мы влиять не можем. Обычно они входят в математическую модель в виде коэффициентов уравнения и обозначаются строчными буквами начала латинского алфавита, при необходимости, с индексами: а₁, а₂, …, b₁, b₂, …, c₁, c₂, ….

2) эндогенные параметры - параметры, которые определяются в ходе расчетов по модели и не задаются извне. Эти переменные являются элементами решения задачи. Обозначаются строчными буквами конца латинского алфавита, при необходимости, с индексами: x ₁, x ₂, …, y₁, y₂, …, z₁, z₂, ….

Критерий эффективности, выражаемый некоторой функцией, называемой целевой, зависит от параметров обеих групп, поэтому целевую функцию W можно записать в виде W = f (x₁, x₂,..., a₁, a₂,...) → max (min) (2.1)

Зачастую, на величины эндогенных параметров x_j накладываются ограничения, задаваемые в виде системы уравнений или неравенств, например, Ф_i (x₁, x₂, x₃,..., x_n) ³ b_i, (2.2)

и условия их неотрицательности x_j ³ 0, (2.3)

Оптимизационную задачу можно сформулировать в следующем виде:

Найти значения переменных x₁, x₂,..., х_n, удовлетворяющие системе ограничений (2.2), условию неотрицательности (2.3)) и обращающие в максимум (или минимум) целевую функцию (2.1).

Как известно, упорядоченная совокупность значений n переменных x ₁, x ₂,..., х _n представляется точкой n-мерного пространства. В дальнейшем эту точку будем обозначать Х = (х ₁, x₂,..., x _n), а оптимальное решение Х* = (х ₁*, х ₂*,..., x _n*).

В тех случаях, когда функции f и Ф хотя бы дважды дифференцируемы, можно применять классические методы оптимизации (например, методы дифференциального, вариационного исчисления и др.). Однако применение этих методов в исследовании операций весьма ограничено, так как: 1) задача определения условного экстремума функции n переменных приводит к решению n дифференциальных уравнений, что технически весьма сложно; 2) классические методы дают возможность определить локальный экстремум, а из-за многомерности функции определение ее максимального (или минимального) значения (глобального экстремума) может оказаться весьма трудоемким; 3) тем более, что этот экстремум возможен на границе области решений, а классические методы не позволяют исследование функций на границах области их определения; 4) классические методы вовсе не работают, если множество допустимых значений аргумента дискретно или функция W задана таблично. В этих случаях для решения задачи (2.1)-(2.3) применяются специально разработанные методы математического программирования.

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

Термин "программирование" (от англ. programming - составление плана или программы действий) следует понимать здесь именно в смысле "поиска наилучших планов" (в отличие от того толкования, которое принято специалистами по программному обеспечению ЭВМ, где под программированием понимается процесс составления плана действий - набор алгоритмов и программ по автоматизированной обработке информации на ЭВМ).