Сетевые методы. Методы теории графов

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

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

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

Предположим, что задан граф с множеством узлов (вершин) и множеством дуг . Длина каждой дуги графа есть неотрицательное число . Выберем на графе некоторый путь, условно обозначенный для которого справедливо ≥ ≥ , при 0< i< m и . Тогда длину этого выбранного пути может быть определена из выражения 2.14.

, 2.14

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

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

где . 2.15

М — множество возможных путей из начальной точки (вер­шины) графа в конечную вершину .

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

;

;

;

≥ ≥ , при 0< i< m и ;

;

;

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

§3.6 Методы оптимизации на основе теории игр и статистических решений.

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

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

Задача теории игр – выявление оптимальных стратегий противоборствующих сторон. При этом рассматриваются ситуации, имеющие элемент неопределенности, что отражается на достоверности окончательных решений. Самый простой случай – конечная парная игра. Допустим, что в ней участвуют две противоборствующие стороны со стратегиями А={А₁,А_2,…,А_n} и B={B₁,B₂,…,B_m}. Выигрыш стороны А является проигрышем стороны В. Обозначим исход игры a. Таким образом, сторона А, выбирая стратегию А_i(или совокупность стратегий), стремится максимизировать выигрыш а, а сторона В – минимизировать. Противопоставляя каждой стратегии А_i стратегию В_j с исходом а_ij игру можно представить в виде прямоугольной матрицы

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

Для реализации указанного принципа анализа матрицы конечной игры n×m устанавливаем для каждой строки α_{i =} min α_ij и затем из чисел а_i выбираем максимальное значение α = max α_i = max min α_ij (α – нижняя цена игры). Для стороны В анализ проводим подобным образом. Для каждой стратегии В_j по сторонам находим максимальное значение β_j = max a_ij, а затем из их числа выбираем минимальную величину β = min max a_ij (β – верхняя цена игры). В случае, если α = β, игра решается в чистых оптимальных стратегиях и называется игрой с седловой точкой. В этом случае можно указать для сторон А и В их оптимальные стратегии с исходом α = β = γ.

Если , то гарантированный выигрыш находиться . В этом случае игра называется со смешанной стратегией.

Чаще всего с помощью теории игр решают задачи на нахождение вероятности применения различных решений (стратегий).

В случаях α ≠ β (а эти ситуации наиболее часты) игра называется игрой со смешанными стратегиями. В оптимальном варианте необходимо найти чередование нескольких стратегий А_i и В_j.

Задача анализа в этом случае - найти частоты p_i, q_j (вероятности) применения стратегий А_i, B_j.

Оптимальные стратегии находим из систем уравнений:

(2.16)

где - средний гарантированный выигрыш ( α ≤ ≤ β)

Поделим левую и правую часть каждого из уравнений (2.16) на величину и введем новые неизвестные x_i.

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

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

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

где

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

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

Пусть сторона А располагает стратегиями А₁, А₂ (в общем случае ) в условиях недостаточной информации о природе, состояния которой В₁, В₂,... В_m, ( ). Исход (выигрыш или ущерб) а_ij (r_ij) заранее известен для каждой пары А_i, В_j. Кроме матрицы выигрышей (ущерба) в статистической игре могут быть известны вероятности возможных состояний природы В_j. Задача состоит в выборе оптимальной стратегии поведения стороны А. Матрица выигрышей может быть заменена на матрицу рисков

Применяются несколько критериев выбора оптимальных решений.

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

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

Согласно максиминному критерию Ваальда в качестве оптимальной выбирается стратегия А_i, при которой минимальный выигрыш по В_j максимален по А_i, то есть

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

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

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

,

где - коэффициент, выбираемый субъективно из интервала между 0 и 1. При = 0 критерий Н превращается в критерий крайнего оптимизма, а при =1 - крайнего пессимизма. Задача принимающего решение - выбрать сообразно содержанию задачи. Ситуацию целесообразно анализировать с разных позиций, и если рекомендации со всех позиций совпадают, то это подтверждает правильность принимаемого решения. Если же рекомендации противоречивы, то окончательное решение следует принимать с учетом слабых и сильных сторон оптимистического и пессимистического подходов.

В том случае, когда неопределенность В_j характеризуется вероятностью qi , при принятии решения стремятся выбрать ту стратегию, которая дает максимум для среднего выигрыша

или минимум среднего риска

В случае, когда исход от стратегии А_i при одном и том же состоянии В_j имеет вероятностный характер, число возможных стратегий следует увеличить.

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

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

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

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

Данные, необходимые для принятия решений в условиях неопределённости, обычно задают в форме матрицы, строки которой соответствуют возможным действиям, а столбцы - возможным состояниям системы. Каждому действию Аi и каждому возможному состоянию Вj соответствует результат (исход), определяющий выигрыш а_ij (или потери r_ij) при выборе данного действия и реализации данного состояния.

Рассмотрим несколько вариантов принятия решений в условиях неопределённости. Сторона А, принимающая решение, имеет две стратегии:

А₁ - заниженная оценка безопасности системы (это реализация принципа осторожности, пессимизма). Обычно это лучший образ действия (принцип максимина, критерий Ваальда, Сэвиджа);

А₂ - завышенная оценка безопасности системы (это оптимизм при анализе факторов, влияющих на безопас­ность).

Сторона В характеризуется двумя состояниями :

В₁ - безаварийное и В₂ - аварийное. Затраты на обеспечение в поддержание безаварийного состояния или на преодоление последствий аварии изменяются в пределах от С_min до С_mах Эти величины можно пронормировать:

.

Все элементы матрицы r_ij можно взять в долях единицы. После умножения всех элементов .матрицы на 10 получим r_ij ≤ 10 .

В рассмотренной ситуации матрица игры может быть записана в виде

Таблица 3.1

В таблице 3.1 можно допустить (экспертная оценка) в первом случае r₂₂ > r₂₁, r₂₂ > r₁₁, r₁₁ < r₁₂ < r_21. В оценочных цифрах (можно рассмотреть, как это сделано ниже, различные варианты) матрица игр имеет вид:

Таблица 3.2

Методы решения игр изложены в специальной литературе [19] и поэтому здесь не рассматриваются.

Находим нижнюю цену игры:

и верхнюю цену игры:

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

Во втором варианте принятия решений можно рассмотреть ситуацию, когда : r₂₂ > r₁₁ > r₁₂> r₂₁

Матрица игры в этом варианте имеет вид:

Таблица 3.3

По данным таблицы 3.3 нижняя цена игры:

и верхняя цена игры:

В данной ситуации α < β и , следовательно, решение может быть смешанным:

p₁+p₂=1 q₁+q₂=1

Здесь р_i и q_j- частоты (вероятности) использования стратегий А_i и В_j для нахождения средних потерь (α ≤ ≤ β) и p_i, q_j необходимо решить системы уравнений:

Из первой системы уравнений находим:

6р₁+3(1-р₁)=4р₁+10(1-р₁).

Откуда р₁=0,78 и р₂=0,22; = 5,33 ( α< < β ) .

Из второй системы уравнений получим:

6q₁+4(1-q₁)=Зq₁+10(1-q₁).

Откуда q₁=0,67 , q₂=0,33 , = 5,33.

Таким образом, в рассмотренном случае оптимальный образ действий может быть записан как:

Предпочтение, хотя и не безоговорочно, и в этой ситуации отдаётся принятию решения с заниженной оценкой безопасности (р₁=0,78>р₂=0,22) и ориентация также в большей степени на обеспечение безаварийной эксплуатации шламохранилища (q₁=^:0,67>q₂=0,33).

В связи с полученным анализом методом игр, влияние неопределённости при оценке безопасности шламохра­нилища, на наш взгляд, представляет интерес рассмотрение двух решений по шламохранилищам:

• А₁ - строительство нового шламохранилища;

• А₂ - реконструкция существующего шламохранилища.

Матрица игры для обоснования решения имеет вид (табл.3.1). В рассматриваемом случае а₁ - решение по строительству нового шламохранилища, А₂ - решение по реконструкции старого шламохранилища, В₁ затраты на строительство или реконструкцию шламохранилища, В₂-затраты на преодоление негативных последствий в случае возникновения аварии на шламохранилище.

Рассматриваются различные варианты соотношения затрат С_ij при А_i и В_j. Также , как и в предыдущем случае, проведено нормирование С_ij и все элементы r_ij умножены на 10. Допускается, что r₂₂>r₁₁ , r₁₁>r₁₂ , r₁₁>r₂₁ , r₁₂<r₂₁. Проанализированы различные варианты решений с отношениями

Таблица 3.4

Решение находилось тем же методом из принципа максимина :

и

Во всех пяти вариантах имеем смешанную игру. Результаты расчётов сведены в табл. 3.5.

Таблица 3.5

Вариант	А	В		n
p1	p2	q1	q2	m
	0,86	0,14	0,57	0,43	6,57	0,464
	0,73	0,27	0,66	0,34	6,33	0,636
	0,625	0,375	0,75	0,25	6,25	0,875
	0,58	0,42	0,81	0,19	6,41	1,0
	0,49	0,51	0,94	0,06	6,8	1,33

Рассмотрены самые различные варианты соотношений потерь при различных вариантах сочетания A_i и В_j. Это даёт возможность проанализировать общие тенденции при обосновании решения А_i. Во-первых, во всех случаях, кроме пятого варианта, предпочтение по безопасности (риску возникновения аварии и преодоления ее. последствий) отдаётся решению по строительству нового шламохранилища. С точки зрения безопасности, это легко обосновывается (рассредоточение нагрузки, повышенная надёжность элементов сооружения, уменьшение масштабов негативного влияния экстремальных природных явлений (ураганы, бури, землетрясения). При этом учитывается высокая степень (заниженная экспертная оценка) опасности аварии и различного рода нарушений безопасности (достаточно высокое значение q₂). В пятом варианте предпочтение отдаётся (с очень малым преимуществом р₁=0,49 против р₂=0,51) выбору решения по реконструкции старого шламохранилища. Однако, при этом следует обратить внимание, что доля влияния безопасности решения (q₁=0,06) ничтожно мала по сравнению с весом затрат на реконструкцию (q₁=0,94). Этот вариант имеет, на наш взгляд, не очень высокий уровень достоверности. Поэтому остаётся признать наиболее обоснованным с позиции уменьшения риска возникновения аварий на шламохранилище решение о строительстве нового сооружения.

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

Глава 4. Разработка методов численной реализации математических моделей принятия решений с использованием подходов компьютерной математики.

§4.1 Описание и формулировка проблемы.

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

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

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

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

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

 

---

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

---

Дата добавления: 2014-08-04; просмотров: 786; Нарушение авторских прав

---

Поделиться с ДРУЗЬЯМИ:

Мы поможем в написании ваших работ!