Важнейшей причиной, обуславливающей выделение сетевых моделей в особую группу, являются особенности их математических характеристик. Используя эти особенности, можно существенно повысить эффективность процесса отыскания оптимальных решений задач, которые удается описать на "сетевом языке". В реальных примерах сетевые модели часто содержат тысячи переменных и сотни ограничений, в связи с чем становится актуальным применение эффективных алгоритмов.
Сетевая структура обладает той особенностью, что во всех ограничениях коэффициенты при управляющих переменных могут принимать одно из двух ненулевых значений, а именно +1 или -1 в соответствии с установленным правилом выбора знаков. В тех случаях, когда возможны два значения, одно из них равняется +1, а другое -1 . При наличии такой структуры задачу можно свести к оптимизации потоков однородной продукции на некоторой сети. Иногда для выявления сетевой структуры той или иной задачи уравнения соответствующей модели необходимо преобразовать.
Сетевые задачи применяют при проектировании больших и сложных систем, а также при поиске путей их наиболее рационального использования. В первую очередь это связано с тем, что с помощью сетей можно довольно просто построить модель системы. [1]
1.3. Теория вероятностей.
Теория вероятностей предлагает пути уменьшения неопределенности, именно поэтому важно ею овладеть. Начало теории вероятностей было положено в середине XVII века, когда французские математики Блез Паскаль и Пьер Ферма по заказу известных игроков в азартные игры разработали математическую модель, описывающую вероятность исходов в играх, зависящих от случая. При игре в "кости", рулетку, как и при опросах, исследованиях (физических, экономических, социологических и т.д.), результаты меняются от раза к разу даже при сохранении неизменных условий.
Деловые люди принимают решения в таких же условиях. Специалист по маркетингу никогда не сможет точно предсказать объемы реализации нового товара. Так же, как, заключая пари, невозможно предвидеть, выиграешь или проиграешь. И в том, и в другом случае присутствует неопределенность.
Теория вероятностей как раз и оперирует этим понятием. Изучение теории вероятностей, основанной на игре случая, обеспечивает надежный инструмент измерения и контроля различных форм неопределенности, с которыми имеют дело лица, принимающие решения.
Опыт - действие, результат которого заранее неизвестен. Например, результат бросания монеты или игральной кости.
Эксперимент - один или несколько опытов. Например, бросание монеты 7раз.
Исход - возможный результат эксперимента.
Вероятность - числовая характеристика степени возможности появления какого-либо случайного события при тех или иных определенных, могущих повторяться неограниченное число раз условиях.
В качестве иллюстрации рассмотрим бросание монеты. Существует два возможных исхода - "орел" и "решка". С какой вероятностью будет выпадать "решка"? Бросим монету 10 раз, а результаты запишем. А потом увеличим число экспериментов до 100, 1000 и так далее. В каждом эксперименте будем определять отношение интересующих нас событий к общему числу опытов в эксперименте.
Так в каждом эксперименте будет определяться частота появления того или иного события (например, появления "орла"). Возможные результаты могут быть таковы. По мере увеличения числа бросков выявляется стремление частоты появления "орлов" к определенной величине. В данном примере их доля - 0,643 при точности трех знаков после запятой.
Таким образом, вероятность может быть определена как отношение числа интересующих нас исходов эксперимента к общему числу опытов при числе опытов, стремящемся к бесконечности.
На практике вероятность обычно заменяют частотой появления интересующего события при конечном (по возможности достаточно большом) числе опытов.
Из того, что вероятность является соотношением, следуют два важных вывода. Если обозначить вероятность исхода эксперимента р, то можно сказать следующее:
1.Числовое значение вероятности находится в интервале от 0 до 1, включая концы интервала, то есть 0 < р < 1.
2.Сумма вероятностей всех возможных исходов эксперимента (вероятность полной группы событий) равна 1, то есть Zp = 1. Полную группу событий, например, образуют все опыты по бросанию монеты, включающие выпадение как "орла", так и "решки" (строго говоря, также и падение монеты "на ребро", что, впрочем, практически невероятно).
Таким образом, значение вероятности, приближающееся к 1, свидетельствует о большей определенности рассматриваемого события (значение р = 1 соответствует достоверному событию, например, вероятность того, что день сменит ночь). И наоборот - уменьшающееся к нулю значение вероятности сигнализирует об увеличении неопределенности события (значение р = 0 соответствует невозможному событию, например, вероятность, того, что подброшенный на Земле камень упадет на Солнце).
1.4.Модели теории игр.
Модели теории игр предназначены для принятия решений в условиях конфликтных ситуаций или противодействия. Конфликтные ситуации подразумевают наличие, по крайней мере, двух противодействующих сторон, интересы которых противоположны. Эти стороны преследуют разные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнера. Такие ситуации, возникающие, например, при игре в шахматы, шашки и т.д., относятся к конфликтным: результат каждого хода игрока зависит от ответного хода противника, цель игры - выигрыш одного из партнеров.
В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Характерным примером является и довольно распространенная ситуация, когда несколько фирм добиваются права у заказчика на получение выгодного заказа (конкурс проектов) или конфликтуют из-за овладения новыми рынками сбыта.
Во всех этих примерах конфликтная ситуация порождается различием интересов партнеров и стремлением каждого из них принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнера, и учитывать заранее неизвестные решения, которые эти партнеры будут принимать.
Эти задачи и составляют проблематику теории игр, поскольку упрощенная математическая модель конфликтной ситуации представляет собой игру. Основные научные разработки теории игр связывают с именем американского математика Джона фон Неймана (1903 - 1957) и его книгой "Теория игр и экономическое поведение". Игра может быть определена следующим образом:
1.Имеется nконфликтующих сторон (лиц), принимающих решения, интересы которых не совпадают.
2.Заданы правила, определяющие набор допустимых стратегий, известные игрокам.
3.Существует точно определенный набор конечных состояний, которыми заканчивается игра (например, выигрыш, ничья, проигрыш).
4.3аранее определены и известны всем игрокам платежи, соответствующие каждому возможному конечному состоянию.
Игра называется парной, если количество сторон (игроков) равно двум, и множественной, если число игроков больше двух.
Игра называется игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков равен проигрышу другого, в противном случае она называется игрой с ненулевой суммой. Примером игры с ненулевой суммой является карточная игра с участием "банкира", т.е. лица, которое держит банк и забирает часть выигрыша себе. В играх с нулевой суммой для полного задания игры достаточно указать выигрыш одного из игроков. Если обозначить а – выигрыш одного из игроков, b - выигрыш другого, то для игры с нулевой суммой b == - а, поэтому достаточно рассматривать, например, а.
Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход - это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре). Случайный ход - это случайно выбранное действие (например, выбор карты из перетасованной колоды).
Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации.
Обычно в процессе игры при каждом личном ходе игрок делает выбор в зависимости от конкретной ситуации. Однако в принципе возможно, что все решения приняты игроком заранее (в ответ на любую сложившуюся ситуацию). Это означает, что игрок выбрал определенную стратегию, которая может быть задана в виде списка правил или программы для компьютера. Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае.
Для того чтобы решить игру, или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, то есть один из игроков должен получить максимальный выигрыш, когда второй игрок придерживается своей стратегии. В то же время, второй игрок должен иметь минимальный проигрыш, если первый игрок придерживается своей стратегии. Такие стратегии называются оптимальными. Оптимальные стратегии должны также удовлетворять условию устойчивости, то есть любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре.
Если игра повторяется достаточно много раз, то игроков может интересовать не выигрыш или проигрыш в каждой конкретной игре, а средний выигрыш (проигрыш) во всех партиях.
Таким образом, целью теории игр является определение оптимальной стратегии для каждого игрока. При выборе оптимальной стратегии естественно предполагать, что оба игрока ведут себя разумно с точки зрения своих интересов.