Как используют графы в менеджменте

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

Приведем несколько определений, что позволит придать нашему обсуждению более компактную форму при решении задач.

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

Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о знаменитых Кенигсбергских мостах через реку Прегель. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: «Мне была предложена задача о двух островах, расположенных в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может». Кенигсбергские мосты схематически можно изобразить так. Сформулируем эту задачу на языке графов.

Правило Эйлера

1. В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер с началом в любой вершине графа.

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

3. В графе, имеющем более двух вершин с нечетной степенью, такого обхода не существует.

Воспользуемся этим правилом и решим несколько задач. Сначала – саму задачу о Кенигсберских мостах.

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

Помимо задачи о мостах известен ряд других старинных задач, решение которых сводится к выяснению вопроса: «Является ли граф Эйлеровым?»

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

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

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

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

Один из них, активно развивающимся у нас в стране является ЛОГИСТИКА. Как известно, термин «логистика» происходит от греческого слова λογιστιχη , которое обозначало в Древней Греции искусство рассуждений и вычислений, или счетное искусство.

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