Размещено на http://www.allbest.ru/

22

Понятия и принципы моделирования

Содержание

1. Основные понятия и принципы исследования операций.

1.1 Основные определения.

1.2 Понятие «показатель эффективности» и чем он может быть выражен.

1.3 Примеры задач из области «исследования операций» и выбор в них показателя эффективности.

2. Математические модели операций.

2.1 Классификация моделей.

2.2 Этапы построения математических моделей.

3. Разновидности задач исследования операций и подходов к их решению.

3.1 Прямые и обратные задачи исследования операций. Детерминированные задачи.

3.2 Проблема выбора решения в условиях неопределенности.

3.3 Многокритериальные задачи исследования операций. «Системный подход».

1. Основные понятия и принципы исследования операций

математический модель эффективность задача

1.1 Основные определения

В этом параграфе мы познакомимся с терминологией, основными понятиями и принципами науки исследования операций.

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

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

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

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

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

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

Те параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут фигурировать различные числа, векторы, функции, физические признаки и т. д. Например, если составляется план перевозок однородных грузов из пунктов отправления А₁, А₂, …, А_m в пункты назначения B₁, B₂, …, B_n, то элементами решения будут числа x_ij, показывающие, какое количество груза будет отправлено из i-го пункта отправления А_i в j-й пункт назначения В_j. Совокупность чисел x₁₁, x₁₂, …, x_1n, …, x_m1, x_m2, …, x_mn образует решение.

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

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

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

1.2 Понятие «показатель эффективности» и чем он может быть выражен

Чтобы в множестве возможных решений X выделить те решения х (иногда одно, а чаще целую область решений), которые с той или другой точки зрения эффективнее (удачнее, предпочтительнее) других, чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности (его часто называют целевой функцией). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. «Лучшим» будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели. Чтобы выбрать, «назвать по имени» показатель эффективности W, необходимо прежде всего спросить себя: чего мы хотим, к чему стремимся, предпринимая операцию? Выбирая решение, мы, естественно, предпочтем такое решение, которое обращает показатель эффективности W в максимум (или же в минимум). Например, доход от операции хотелось бы обратить в максимум; если же показателем эффективности являются затраты, их желательно обратить в минимум. Если показатель эффективности желательно максимизировать, мы это будем записывать в виде W max, а если минимизировать - W min.

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

В некоторых случаях бывает, что операция, сопровождаемая случайными факторами, преследует какую-то вполне определенную цель А, которая может быть достигнута только полностью или совсем не достигнута (схема «да - нет»), и никакие промежуточные результаты нас не интересуют. Тогда в качестве показателя эффективности выбирается вероятность достижения этой цели Р (А). Например, если ведется стрельба по какому-то объекту с непременным условием уничтожить его, то показателем эффективности будет вероятность уничтожения объекта.

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

1.3 Примеры задач из области «исследования операций» и выбор в них показателя эффективности

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

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

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

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

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

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

В качестве показателя эффективности можно взять среднюю ожидаемую прибыль П от реализации товаров за сезон (П max).

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

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

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

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

6. Выборочный контроль продукции. Завод выпускает определенного вида изделия. Для обеспечения их высокого качества организуется система выборочного контроля. Требуется разумно организовать контроль (т.е. выбрать размер контрольной партии, набор тестов, правила отбраковки и т.д.) так, чтобы обеспечить заданный уровень качества при минимальных расходах на контроль.

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

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

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

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

В формулировке задачи сознательно допущена некоторая нечеткость: неясно, что значит «наилучшее обслуживание абонентов» или «удовлетворение их запросов в максимальной мере». Если о качестве обслуживания судить по времени, которое запросивший книгу абонент ждет ее получения, то в качестве показателя эффективности можно взять среднее время Т ожидания книги читателем, подавшим на нее заявку (T min). Можно подойти к вопросу и с несколько иных позиций, выбрав в качестве показателя эффективности среднее число М книг, выданных за единицу времени (M max).

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

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

2. Математические модели операций

2.1 Классификация моделей

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

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

Одними из простейших и наиболее распространенных видов моделей являются:

Графические - способ представления объекта в наглядной зрительной форме: рисунок, чертеж или схема.

Словесные - представляют собой словесное описание объекта, процесса и явления, выраженное средствами того или иного языка.

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

Информационные - представляют собой формализацию словесных описаний.

Все модели делятся на следующие группы:

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

2. Стохастические - обеспечивают описание вероятностных процессов и событий.

3. Динамические - описывают поведение исследуемого объекта во времени, процессы в котором могут быть дискретными или непрерывными.

4. Статические - отображают поведение объекта в определенный момент времени.

5. Абстрактные - отображают поведение исследуемого объекта, не реализуемое в заданном промежутке времени.

6. Реальные - отображают внешние признаки и условия функционирования исследуемого объекта.

7. Математические - в которых изучаемое явление или процесс представлены в виде математических закономерностей.

8. Наглядные - отображают поведение исследуемого объекта в виде схем, диаграмм, графиков и т. п.

9. Аналитические - отображают процесс в численном виде при конкретных начальных и граничных условиях и в качественном виде - при невозможности решения в явном виде.

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

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

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

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

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

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

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

Дискретные математические модели. Свойство моделей быть дискретными состоит в том, что их элементы существуют независимо друг от друга. Это свойство отражает две возможные ситуации:

а) дискретность структуры изучаемого объекта;

б) дискретность информации, получаемой о нем.

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

2.2 Этапы построения математических моделей

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

а) с той точностью, с которой нам нужно знать решение;

б) с той информацией, которой мы располагаем или можем приобрести.

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

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

1) увязнуть в подробностях («из-за деревьев не увидеть леса»);

2) слишком огрубить явление («выплеснуть вместе с водой и ребенка»).

На рис. 1.1 представлена общая схема процесса компьютерного математического моделирования.



Рис. 1.1

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

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

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

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

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

3. Разновидности задач исследования операций и подходов к их решению

3.1 Прямые и обратные задачи исследования операций. Детерминированные задачи

Задачи исследования операций делятся на две категории:

а) прямые задачи отвечают на вопрос: что будет, если в заданных условиях мы примем какое-то решение х X? В частности, чему будет равен при данном решении x выбранный показатель эффективности W (или же ряд таких показателей)?

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

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

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

Остановимся несколько подробнее на обратных задачах. Если число возможных вариантов решения, образующих множество X, невелико, то можно попросту вычислить величину W для каждого из них, сравнить между собой полученные значения и непосредственно указать один или несколько оптимальных вариантов, для которых W достигает максимума. Такой способ нахождения оптимального решения называется простым перебором. Однако, когда число возможных вариантов решения, образующих множество X, велико, поиск среди них оптимального «вслепую», простым перебором, затруднителен, а зачастую практически невозможен. В этих случаях применяются методы направленного перебора, который состоит в том, что каждая последующая итерация приближает нас к оптимальному решению. С некоторыми из таких методов мы познакомимся в темах 4 и 5.

Сейчас мы ограничимся постановкой задачи оптимизации решения (обратной задачи исследования операций) в самой общей форме: «Пусть имеется некоторая операция Q, на успех которой мы можем в какой-то мере влиять, выбирая тем или другим способом решение х (напомним, что х не число, а целая группа параметров). Пусть эффективность операции характеризуется одним показателем W max».

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

1) заданные, заранее известные факторы (условия выполнения операции), которые обозначаются ;

2) зависящие от нас элементы решения, образующие в своей совокупности решение х.

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

Показатель эффективности W зависит от обеих групп факторов, т.е.

.(1.1)

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

Пусть вид зависимости (1.1) нам известен, т.е. прямая задача решена, тогда обратная задача формулируется следующим образом: « При заданном комплексе условий найти такое решение х = x*, которое обращает показатель эффективности W в максимум».

. (1.2)

Формула (1.2) читается так: W* есть максимальное значение W(, х), взятое по всем решениям, входящим в множество возможных решений X.

Итак, перед нами типичная математическая задача нахождения экстремума. Она принадлежит к классу вариационных задач. Самые простые из таких задач - это «задачи на максимум и минимум». Чтобы найти «экстремум» функции многих аргументов, надо продифференцировать ее по всем аргументам (в данном случае элементам решения), приравнять производные нулю и решить полученную систему уравнений. Казалось бы, что проще? А вот этот классический метод как раз в исследовании операций имеет весьма ограниченное применение. Во-первых, когда аргументов много, задача решения системы уравнении зачастую оказывается не проще, а сложнее, чем непосредственный поиск экстремума. Во-вторых, когда на элементы решения наложены ограничения, экстремум часто достигается не в точке, где производные равны нулю (такой точки может вообще не быть), а где-то на границе области X. Возникают все специфические трудности так называемой многомерной вариационной задачи при ограничениях. Кроме того, в некоторых задачах функция W вообще не имеет производных (например, задана только для целочисленных значений аргументов). Все это делает задачу поиска экстремума далеко не такой простой, какой она кажется с первого взгляда.

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

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

3.2 Проблема выбора решения в условиях неопределенности

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

. (1.3)

Так как величина W зависит от неизвестных факторов , то даже при заданных и х она не может быть вычислена и остается неопределенной.

Формулировка задачи: «При заданных условиях с учетом неизвестных факторов найти такое решение х Х, которое, по возможности, обеспечивает экстремальное значение показателя эффективности W».

Эта задача называется задачей о выборе решения в условиях неопределенности.

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

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

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

Классификация неопределенностей:

1. «Доброкачественный» вид неопределенности. Это случай, когда неизвестные факторы представляют собой обычные объекты изучения теории вероятностей, случайные величины (или случайные функции), статистические характеристики которых нам известны или в принципе могут быть получены. Такие задачи исследования операций называются стохастическими задачами, а присущую им неопределенность - стохастической неопределенностью.

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

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

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

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

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

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

Итак, рассмотрим такую операцию Q, где факторы «существенно случайны» и заметно влияют на показатель эффективности W, который тоже «существенно случаен».

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

. (1.4)

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

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

(1.5)

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

2. Стохастическая неопределенность - это почти определенность, если только известны вероятностные характеристики входящих в задачу случайных факторов. Гораздо хуже обстоит дело, когда неизвестные факторы не могут быть изучены и описаны статистическими методами. Это бывает в двух случаях:

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

б) распределение вероятностей для параметров вообще не существует.

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

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

Теперь обратимся к самому трудному и неприятному случаю б), когда у неопределенных факторов вообще не существует вероятностных характеристик; другими словами, когда их нельзя считать «случайными» в обычном смысле слова.

Поясняю: под термином «случайное явление» в теории вероятностей принято понимать явление, относящееся к классу повторяемых и, главное, обладающее свойством статистической устойчивости. При повторении однородных опытов, исход которых случаен, их средние характеристики проявляют тенденцию к устойчивости, стабилизируются. Частоты событий приближаются к их вероятностям, средние арифметические - к математическим ожиданиям. Если много раз бросать монету, частота появления герба постепенно стабилизируется, перестает быть случайной; если много раз взвешивать на аналитических весах одно и то же тело, средний результат перестает колебаться, выравнивается. Это пример доброкачественной, стохастической неопределенности.

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

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

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

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

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

Существует несколько подходов к решению такого рода задач:

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

ь метод экспертных оценок. Он часто применяется в задачах, связанных с прогнозированием в условиях «дурной неопределенности». Идея метода сводится к следующему: собирается коллектив экспертов, и каждый из них «на глаз» оценивает степень правдоподобия различных вариантов условий , приписывая им какие-то субъективные вероятности. Затем полученные ответы обрабатываются наподобие статистического материала. Результаты обработки, разумеется, сохраняют субъективный характер, но, усредняя оценки целого коллектива, можно получить нечто более объективное (кстати, оценки разных экспертов расходятся не так сильно, как можно было бы ожидать).

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

3.3 Многокритериальные задачи исследования операций. «Системный подход»

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

Рассмотрим пример такой задачи: «Организуется (или реорганизуется) работа промышленного предприятия. Что принять в качестве критерия эффективности? С одной стороны, нам хотелось бы обратить в максимум валовой объем продукции V. Желательно также было бы получить максимальный чистый доход О. Что касается себестоимости S, то ее хотелось бы обратить в минимум, а производительность труда П - в максимум. При обдумывании задачи может возникнуть еще ряд дополнительных критериев».

Итак, типичной для крупномасштабной задачи исследования операций является многокритериальность - наличие ряда количественных показателей W₁, W₂, …, W_n, одни из которых желательно обратить в максимум, другие - в минимум.

Возникает вопрос: «Как же быть в случае, если все же приходится оценивать эффективность операции по нескольким показателям?»

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

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

Вспомним «критерий для оценки человека», полушутя-полусерьезно предложенный когда-то Львом Толстым. Он имеет вид дроби, в числителе которой стоят действительные достоинства человека, а в знаменателе - его мнение о себе. С первого взгляда такой подход может показаться логичным. Но представим себе человека, почти совсем не имеющего достоинств, но совсем не обладающего самомнением. По критерию Л.Н. Толстого, такой человек должен иметь бесконечно большую ценность, с чем уж никак согласиться нельзя.

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

. (1.6)

Для нашего примера обобщенный критерий запишется следующим образом:

,

где W₁ - объем валовой продукции; а₁ - вес первого показателя эффективности; W₂ - чистый доход; а₂ - вес второго показателя эффективности; W₃ - себестоимость продукции; а₃ - вес третьего показателя эффективности; W₄ - производительность труда; а₄ - вес четвертого показателя эффективности.

При произвольном назначении весов а_1, а₂, ... этот способ ничем не лучше предыдущего. Его сторонники ссылаются на то, что и человек, принимая компромиссное решение, тоже мысленно взвешивает все «за» и «против», приписывая больший вес более важным для него факторам. Это, может быть, и так, но, по-видимому, «весовые коэффициенты», с которыми входят в расчет разные показатели, не постоянны, а меняются в зависимости от ситуации.

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

Но гораздо чаще встречаются случаи, когда с первого взгляда ситуация неясна: один из показателей тянет в одну сторону, другой - в другую. При этом всегда полезно провести дополнительные расчеты, пользуясь формулами типа (1.6). Прежде всего это позволяет, решая прямые задачи исследования операций, т.е. для любого решения х находя значения показателей эффективности W₁, W₂, …, W_n, «выбраковать» из множества возможных решений X заведомо неудачные, уступающие другим по всем критериям.

Например, пусть имеется многокритериальная задача исследования операций с критериями W₁, W₂, …, W_n. Для простоты предположим, что все эти величины желательно максимизировать. Пусть в составе множества возможных решений есть два решения х₁ и х₂ такие, что все критерии W₁, W₂, …, W_n для первого решения больше или равны соответствующим критериям для второго решения, причем хотя бы один из них действительно больше. Очевидно, тогда в составе множества X нет смысла сохранять решение х₂, оно вытесняется решением х₁. Выбросим решение х₂ как неконкурентоспособное и перейдем к сравнению других по всем критериям. В результате такой процедуры отбрасывания заведомо непригодных, невыгодных решений множество X обычно сильно уменьшается: в нем сохраняются только так называемые эффективные (иначе паретовские) решения, характерные тем, что ни для одного из них не существует доминирующего решения.