Оптимизация сбыта готовой продукции с помощью сетевого графа

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

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

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

Рассмотрим применение сетевого графа на примере нахождении пути с минимальными затратами времени в процессе реализации готовой продукции.

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

Таблица 1.

На основе таблицы составляем сетевой граф, представленный на рисунке 1.

Рис. 1

Вводим обозначения:

C(t) - длина кратчайшего пути из вершины 0 в вершину t (следует отметить, что любой путь состоит их конечного числа дуг и каждая из дуг входит в путь не более одного раза, поэтому претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается).

Рассматриваемая задача состоит в вычислении С(6) и указании пути, на котором этот минимум достигается.

Произведем расчеты:

С(1) = 5

C(2) = 2+C(1) = 7

C(3) = 1+C(1) = 6

C(4) = min{6+C(1); 10+C(2); 7+C(3)} = min{11; 17; 13} = 11

C(5) = 15+C(4) = 26

C(6) = min{35+C(4); 10+C(5)} = min{46; 36} = 36

Получаем оптимальное решение:

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