Классификация задач оптимизации

Исходные данные	Переменные	Зависимости	Задача
Детерминированные	Непрерывные	Линейные	Линейного программирования
Целочисленные	Линейные	Целочисленного программирования
Непрерывные, целочисленные	Нелинейные	Нелинейного программирования
Случайные	Непрерывные	Линейные	Стохастическое программирование

А по критерию эффективности:

одноцелевое принятие решений (один критерий эффективности);

многоцелевое принятие решений (несколько критериев эффективности).

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

В общем виде обратная детерминированная задача будет выглядеть следующим образом.

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

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

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

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

Это уже другая, не чисто математическая задача (недаром в ее формулировке сделана оговорка " по возможности" ). Наличие неопределенных факторов переводит эту задачу в новое качество: она превращается в задачу о выборе решений в условиях неопределенности.

Приведем примеры.

Пример 1.4.1

Планируется ассортимент товаров для распродажи на ярмарке. Желательно было бы максимизировать прибыль. Однако заранее неизвестно ни количество покупателей, которые придут на ярмарку, ни потребности каждого из них.

Пример 1.4.2

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

 

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

Пример 1.4.3

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

Пример 1.4.4

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

 

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

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

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

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

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

Пример 1.4.5

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

 

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

Но дело в том, что время ожидания врача отдельными больными не суммируется: слишком долгое ожидание одного из них не компенсируется почти мгновенным обслуживанием другого. Чтобы избежать таких неприятностей, можно дополнить показатель эффективности добавочными требованиями, чтобы фактическое время ожидания врача было не больше какого предельного значения f₀. Поскольку время ожидания величина случайная, нельзя просто потребовать, чтобы выполнялось условие F≤ f₀, но можно потребовать, чтобы это условие выполнялось с большой вероятностью, настолько большой, чтобы событие F≤ f₀ было практически достоверным. Пусть k=0, 995 и потребуем, чтобы вероятность P(F≤ f₀ ) ≥ k.

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

Особенно осторожными надо быть с " оптимизацией в среднем", когда речь идет об единичной операции.

Кроме рассмотренных выше, бывают задачи, когда неизвестные факторы не могут быть изучены и описаны статистическими методами. Это бывает в двух случаях:

• распределение вероятностей для параметров в принципе существует, но к моменту принятия решения не может быть получено;
• распределение вероятностей для параметров вообще не существует.

Пример 1.4.6

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

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

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

 

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

Пример 1.4.7

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

Понятно, что распределение этой вероятностной величины не может быть получено не из каких статистических данных. Что же делать в этом случае?

Можно поступить следующим образом. Задаться каким более или менее правдоподобным значением вероятностного параметра и решить данную задачу, как обычную детерминированную задачу. Но полученное решение может и не быть оптимальным, просто мы получим некоторое компромиссное решение.

 

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

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. I I. Цели, задачи, результаты выполнения индивидуального проекта
2. I. Автоматизации функциональных задач в государственном и региональном управлении.
3. I. КЛАССИФИКАЦИЯ ПО ИСПОЛЬЗОВАНИЮ.
4. I. Классификация установок, по Узнадзе.
5. II КЛАССИФИКАЦИЯ И МАРКИРОВКА ЧУГУНОВ
6. II. Основные задачи управления персоналом.
7. II. Решить следующие ниже финансовые задачи на листе “Задачи”.
8. II. Цели, задачи и предмет деятельности
9. III. Задачи, решаемые организацией с помощью ИСУ и ИТУ.
10. III. Классификация мебельных тканей.
11. III. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ РАЙОННОЙ ОРГАНИЗАЦИИ ПРОФСОЮЗА
12. III. Экономико-управленческие задачи производственной практики