Сетевое планирование и управление

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

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

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

Пример решения задачи.

Сетевая задача, которая решается как транспортная.

Компания имеет восемь крупных оптовых складов. Отдел сбыта принял решение значительно снизить цену одного дорогостоящего изделия с целью ликвидации образовавшегося запаса этих изделий. Руководство намерено разместить имеющиеся в наличии запасы на указанных восьми складах в соответствии с прогнозами сбыта в этих районах. Таким образом, надо перераспределить некоторую часть запасов. Числа у складов – это избыток или недостаток товара. Склады 2, 4, 5, 6, 7 – промежуточные. Все другие склады – источники, если избыток товаров и стоки – если требуется дополнительный запас. С_ij – затраты на перевозку одного изделия со склада i на склад j.

Рис. 3.1. Схема перевозок товаров между складами

Задание для самостоятельной работы. Составить экономико-математическую модель транспортной задачи.

Дата добавления: 2015-05-09