Методы и модели теории графов и сетевого моделирования

В коммерческой деятельности большинство возникающих задач удобно представлять для целостного восприятия и анализа в виде сетей, которые позволяют ответить на два главных вопроса: до какого места необходимо дойти (цель) и какой путь следует избрать (как)? Коммерческую деятельность можно рассматривать как совокупность задач для передвижения, складирования и распределения товаров, денег, документов, воды, нефти, газа, электроэнергии, телеи радиосистем, информации о товарах, поставках и покупателях. Наглядность и логическая обоснованность методов сетевого анализа позволяют выбрать довольно естественный подход к решению задач коммерческой деятельности. Сетевые модели для людей, не занимающихся научной работой, являются более понятными, чем другие модели, поскольку для них все же лучше один раз увидеть, чем сто раз услышать. В значительной степени методы сетевого анализа основаны на теории графов — области математики, началом развития которой явилась задача о кенигсбергских мостах, сформулированная швейцарским ученым Л. Эйлером в 1736 г. Через р. Прегель, на которой стоял город Кенигсберг, семь мостов (рис. 4.1) связывали два острова друг с другом. Задача заключалась.

Рис. 4.1

в том, чтобы пройти по всем мостам только один раз и вернуться обратно к началу маршрута. Л. Эйлер доказал неразрешимость этой задачи.

Позже Д. К. Максвелл и Г. Р. Кирхгоф в 1847 г. на основе исследования движения тока в электрических цепях сформулировали некоторые принципы сетевого анализа. Были разработаны методы расчета наибольшей пропускной способности телефонных линий. В 1940;х гг. в результате развития теории исследования операций был разработан ряд математических методов, необходимых для анализа больших систем. В 1950—1960;х гг. проводились работы по построению новых сетевых моделей и разработке алгоритмов их решения на основе элементов теории графов. В целом графы обладают эстетической привлекательностью.

В результате изучения материала студенты будут:

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