Задача о соединении городов 39

Вид материала

Задача

Содержание Глава 1. вступление Глава 1. вступление Рис. 2 Модели могут быть очень разными: есть физические Глава 1. вступление Глава 1. вступление Глава 1. вступление Глава 1. вступление Глава 1. вступление Етерминированные методы Из письма Л. Эйлера от 13 марта 1736 г. Глава 2. графы и сети В (рис. 4). В этом случае вершины А ж В Глава 2. графы и сети ТЕОРЕМА (Эйлер). А. Это объясняется тем, что, входя в любую вершину графа (кроме, быть может, вершины А) Рис. 10 неизбежно вернемся в вершину А Глава 2. графы и сети

Подобный материал:

• Тема форума, 187.38kb.
• 1 Вопросы методологии исследования, 416.32kb.
• Проект Сводного доклада Форума "Стратегии крупных городов. Инвестиционные строительные, 508.25kb.
• Проблемы развития городов в последние годы уверенно занимает ключевую позицию в приоритетах, 81.82kb.
• Городов Всемирного Наследия, Международной Ассоциации Породненных Городов, Европейской, 145.2kb.
• Программа курса лекций «Математические методы и модели исследования операций», 27.98kb.
• Т. М. Боровська кандидат технічних наук, доцент І. С. Колесник, 118.17kb.
• Малые города России: в будущее – через инновации, 56.32kb.
• При физическом соединении двух или более компьютеров образуется компьютер¬ная сеть, 1009.79kb.
• Деловую программу откроет конференция, на которой будут обсуждаться вопросы формирования, 201.02kb.

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

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

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

17

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

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

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

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

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

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

18

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

1-й шаг — сформулировать проблему (рис. 1).

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

Факты

Сформулировать проблему

Вербальная

модель

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

не определенны и известны. Здесь обычно ставится задача оптими­зации некоторой величины (например, минимизация затрат).

Стохастические модели применяются в тех случаях, когда неко­торые факторы носят неопределенный, случайный характер.

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

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

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

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

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

3-й шаг — найти решение (рис. 3).

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

4-й шаг — тестировать решение (рис. 4).

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

20

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

Предлагаемое решение

Тестировать решение

Приемлемое решение

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

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

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

Техника решений



Создать режим благоприятствования

Используемые методики

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

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

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

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

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

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

23

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

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

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

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

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

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

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

Все отзывы и замечания по поводу данной книги авторы с благо­дарностью примут по адресу: alexch@spa.msu.ru.

^{Часть I}

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


Глава 2 ГРАФЫ И СЕТИ

2.1. Графы

"Мне была предложена задача об острове, расположенном в горо­де Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне достойным внимания тем, что для его решения не­достаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, при помощи которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно распо­ложенных мостов или не может".

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

Город Кенигсберг (ныне Калининград) располагался на обоих бере­гах реки Прегель и на двух островах, которые соединялись семью мостами. План расположения мостов приведен на рис. 1. Задача, о которой говорится в письме, состоит в том, чтобы во время прогулки пройти каждый мост по одному разу и вернуться в исходную точку. Так как нас интересуют только переходы по мостам, то план горо­да можно заменить схемой, представленной на рис. 2. На этой схеме земельные участки, разделенные рукавами реки, как бы сжаты в точки А, В, С, D (вершины), а мосты вытянуты в линии а, 6, с, d, e,

27

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

2.1. ГРАФЫ


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



Рис. 9

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

^ ТЕОРЕМА (Эйлер). В любом конечном связном графе, все вер­шины которого четны, существует цикл, в котором каждое ребро графа участвует ровно один раз.

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

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

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

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

Пример 1. Выйдя из вершины А и не пытаясь еще раз пройти по уже пройденному ребру, мы неизбежно вернемся в вершину ^ А. Это объясняется тем, что, входя в любую вершину графа (кроме, быть может, вершины А), мы всегда имеем возможность выйти из нее (напомним, что в каждой вершине графа сходится четное чи­сло ребер). Следовательно, неутомимо продолжая перемещение, мы

30


2.1. ГРАФЫ



^ Рис. 10

неизбежно вернемся в вершину А, а вернувшись, окажемся перед двумя возможными ситуациями: 1) в построенный нами цикл вхо­дят все ребра графа, 2) остались еще не пройденные ребра.


Рис. 11


31

Первый случай не так интересен: если в построенный цикл входят все ребра, то поставленная задача решена. Что же касается второго случая, то здесь в полученном нами цикле (обозначим его через Л) обязательно есть вершина, из которой выходит еще не пройденное нами ребро. Пусть это вершина В. Об этой вершине можно сказать даже больше: число выходящих из нее ребер, не принадлежащих по­строенному циклу Л, обязательно четно. И мы строим новую цепь из вершины В, привлекая только ранее не пройденные ребра. Ясно, что в результате мы вернемся в вершину В и получится новый цикл — В (рис. 11).



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

Теперь легко получить цикл, начинающийся в вершине А и боль­ший построенного ранее цикла А.

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



Рис. 12

Если мы и на этот раз не прошли по всем ребрам графа, то, вы­брав вершину цикла, построенного по циклам Л и Б, из которой исходят ребра, не входящие в этот цикл, расширяем его описанным выше способом.

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

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

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

Если вход и выход совпадают, то разместить экспонаты следует так, чтобы схема экспозиции была эйлеровым графом. Что же ка­сается указателей, то они должны 1) быть снабжены порядковыми номерами и 2) описывать эйлеров цикл (рис. 13).

32

2.1. ГРАФЫ

<•—<—с