Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. пособие

Подождите немного. Документ загружается.

ГЛАВА 1. ВСТУПЛЕНИЕ

Предлагаемая

модель

Найти

решение

Предлагаемое

решение

Рис. 3

истинную природу изучаемой проблемы. В этом случае она долж-

на быть либо как-то усовершенствована, либо заменена на другую,

более подходящую модель.

5-й шаг — организовать контроль (рис. 5).

Если найденное решение оказалось приемлемым, естественно возни-

кает необходимость создания механизма контроля за правильным

использованием модели. Основная задача такого контроля состоит

в обеспечении соблюдения ограничений, предполагаемых моделью,

качества входных данных и получаемого решения. Полезно также

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

ГЛАВА 1. ВСТУПЛЕНИЕ

часто используется) не только для разрешения сиюминутной ситу-

ации, но и при рассмотрении сходных обстоятельств в будущем. За-

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

использовать ее в течение более продолжительного промежутка вре-

мени.

6-й шаг — создать режим благоприятствования (рис. 6).

Этот шаг часто оказывается самым трудным — внедрение новаций

нередко наталкивается на незаинтересованность и даже на сопротив-

ление. Поэтому обучение персонала, реклама, качество подготавли-

ваемой документации и учет разнообразия поведенческих мотивов

людей играют здесь решающую роль.

Техника

решений

Создать режим

благоприятствования

Используемые

методики

Рис. 6

На схеме (рис. 7) пунктирной линией отмечена та часть процесса

принятия решения, где заметную роль играют различные соображе-

ния математического характера.

Рис. 7

ГЛАВА 1. ВСТУПЛЕНИЕ

Отметим, что сам термин "управление" можно понимать по-раз-

ному. Это и организация, в том числе и технологическая, той или

иной осмысленной деятельности для достижения каких-либо целей

(в качестве математического обеспечения здесь используются пре-

имущественно детерминированные и стохастические модели), и изу-

чение моделей поведения взаимодействующих сторон (здесь приме-

няются игровые модели).

В настоящее время к решению сложных управленческих задач,

представляющих практический интерес, привлекаются большие

коллективы людей (и, добавим, значительные вычислительные сред-

ства) с разной профессиональной подготовкой и ориентацией, с раз-

ной степенью осведомленности о задаче в целом и, конечно, с разной

степенью ответственности — от руководителя (ЛПР) до специалис-

та-разработчика (исследователя) и рядового исполнителя.

Для того чтобы такое сложное образование могло достаточно пло-

дотворно функционировать, важно подготовить тех, кто был бы спо-

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

влял бы нетривиальные коммуникационные функции, был посред-

ником как между ЛПР и специалистом-разработчиком, так и между

разработчиком и исполнителем. Этому посреднику вовсе не обяза-

тельно знать в деталях всю техническую сторону вопроса (это зада-

ча для найденных при его посредстве специалистов), а достаточно

ориентироваться в основных идеях. Иными словами, если касать-

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

ные представления о возможностях математических методов, об их

идейных основаниях и о банке готовых математических моделей и

ключевых методов.

Одной из целей книги, которые ставили перед собой авторы, явля-

ется преодоление математической, методологической и языковой ра-

зобщенности исследователей сложной практической управленческой

задачи. Только это дает возможность, с одной стороны, как можно

точнее отразить в создаваемой (или выбираемой) модели реальные

процессы, а с другой — создать (или выбрать) модель, простую на-

столько, чтобы можно было надеяться решить задачу до конца и

получить обозримые и уже этим полезные результаты.

Большинство используемых здесь идей допускает простое и впол-

не доступное объяснение, разумеется требующее некоторой матема-

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

тий, формул, подходов и фактов, равно как и методику их изложе-

ния.

ГЛАВА 1. ВСТУПЛЕНИЕ

Не следует также забывать о том, что важно не только озна-

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

быть готовым к разработке новых. Аппарат, используемый при вы-

работке и принятии нестандартных решений, должен быть настоль-

ко прост и нагляден, насколько это возможно. И насколько это воз-

можно, он должен быть согласован с точностью и объемом доступной

информации и с вопросами, ответы на которые хочется получить.

Области, где математические методы работают достаточно эф-

фективно, не совпадают с ареалом управленческих задач. Последние

слабо формализуемы и часто традиционно консервативны. Отсюда

подозрительное отношение к рекомендациям, основанным на точных

расчетах, требующих обширных и глубоких математических знаний.

Нужно признать, что определенные основания для этого есть. Ме-

тоды математики способны решать только те задачи, которые изло-

жены на ее языке. А это предполагает непременные упрощения в ре-

альной сложной ситуации. За разделением определяющих факторов

задачи на существенные и второстепенные часто стоят управленчес-

кий опыт и интуиция.

Впрочем, даже весьма грубая на вид идеализация может позво-

лить глубже вникнуть в суть проблемы.

Авторы стремятся обходиться минимальным количеством фор-

мул и фактов, а привычные в математических курсах теоремы и их

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

тельно высокой математической культуры, просто опускаются.

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

ражнений (как правило, с ответами), призванный помочь читателю

в его самооценке степени усвоения соответствующей темы.

Все отзывы и замечания по поводу данной книги авторы с благо-

дарностью примут по адресу: alexch@spa.msu.ru.

Часть I

ДЕТЕРМИНИРОВАННЫЕ

МЕТОДЫ

Глава 2

ГРАФЫ И СЕТИ

2.1. Графы

"Мне была предложена задача об острове, расположенном в горо-

де Кенигсберге и окруженном рекой, через которую перекинуто 7

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

проходя только однажды через каждый мост. И тут же мне было

сообщено, что никто еще до сих пор не смог это проделать, но никто

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

показался мне достойным внимания тем, что для его решения не-

достаточны ни геометрия, ни алгебра, ни комбинаторное искусство.

После долгих размышлений я нашел легкое правило, основанное на

вполне убедительном доказательстве, при помощи которого можно

во всех задачах такого рода тотчас же определить, может ли быть

совершен такой обход через какое угодно число и как угодно распо-

ложенных мостов или не может".

Из письма Л. Эйлера от 13 марта 1736 г.

Город Кенигсберг (ныне Калининград) располагался на обоих бере-

гах реки Прегель и на двух островах, которые соединялись семью

мостами. План расположения мостов приведен на рис. 1. Задача, о

которой говорится в письме, состоит в том, чтобы во время прогулки

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

Так как нас интересуют только переходы по мостам, то план горо-

да можно заменить схемой, представленной на рис. 2. На этой схеме

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

точки Л, В, С, D (вершины), а мосты вытянуты в линии а, Ь, с, d, e,

ГЛАВА 2. ГРАФЫ И СЕТИ

Рис. 1

Рис. 2

/, д (ребра). Нетрудно проверить (например, перебрав все возмож-

ные варианты), что изображенную фигуру нельзя обвести острием

пера, не отрывая его от бумаги и проходя по каждой дуге ровно один

раз.

Исследуя ситуацию с кенигсбергскими мостами, Эйлер решил

значительно более общую задачу. Для того чтобы лучше понять по-

лученный им результат, введем некоторые определения.

Рис. 3

Рис. 4

Фигура, состоящая из точек (вершин) и соединяющих их линий

(ребер), называется графом (рис. 3). Маршрутом, или путем, со-

единяющим вершины Аи В графа, называется такая последователь-

ность его ребер, в которой каждые два ребра имеют общую концевую

точку, причем первое ребро выходит из вершины А, а последнее вхо-

2.1. ГРАФЫ

Рис. 5

Рис. 6

дит в вершину В (рис. 4). В этом случае вершины А а В называются

связанными. Граф называется связным, если любая пара его вершин

связана (рис. 5). Граф, изображенный на рис. 6, несвязен.

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

ся в нем не более одного раза (вершины в цепи могут повторяться и

несколько раз) (рис. 7). Цепь, начальная и конечная вершины кото-

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

Рис. 7

Рис. 8

Вершина называется четной, если в ней сходится четное число

ребер, и нечетной, если число всех сходящихся в ней ребер нечетно.

Вершина А на рис. 9 четна — в ней сходятся 6 ребер, а вершина

В нечетна — в ней сходятся 5 ребер. Число ребер, сходящихся в

вершине графа, называется степенью (порядком) этой вершины.

ГЛАВА 2. ГРАФЫ И СЕТИ

Рис. 9

Наконец, граф называется конечным, если множество его ребер

конечно. Примером бесконечного графа может служить прямоуголь-

ная сетка, заданная на всей плоскости.

ТЕОРЕМА (Эйлер). В любом конечном связном графе, все вер-

шины которого четны, существует цикл, в котором каждое ребро

графа участвует ровно один раз.

Такой цикл называют эйлеровым циклом, а граф, вес вершины

которого четны (и, значит, существует эйлеров цикл), — эйлеровым

графом.

Обратившись к графу в задаче о кенигсбергских мостах, замеча-

ем, что все четыре его вершины являются нечетными — в каждой

из вершин А, С, D сходятся по три ребра, а в вершине В - - пять

ребер. Значит, этот граф не эйлеров.

Найти эйлеров цикл (разумеется, после того, как вы убедились,

что заданный граф эйлеров (все вершины четны)) совсем не труд-

но: существует универсальный и достаточно простой алгоритм, при

помощи которого задача построения эйлерова цикла всегда разре-

шима.

Покажем эффективность этого алгоритма на конкретном примере

(см. рис. 10).

Пример 1. Выйдя из вершины А и не пытаясь еще раз пройти

по уже пройденному ребру, мы неизбежно вернемся в вершину А.

Это объясняется тем, что, входя в любую вершину графа (кроме,

быть может, вершины А), мы всегда имеем возможность выйти из

нее (напомним, что в каждой вершине графа сходится четное чи-

сло ребер). Следовательно, неутомимо продолжая перемещение, мы