План перевозок продукции со склада

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Задача

перевозка торговый математический матрица

Менеджеру транспортного отдела поручено составить план перевозок продукции со склада фирмы в четыре торговые точки области, обеспечивающий минимальные издержки на перевозки (известно, что издержки на перевозки пропорциональны длине пути). Расстояния от базы до каждого магазина и между магазинами приводятся в таблице 1:

Табл. 1

Пустые клетки означают, что дороги или ремонтируются или плохого качества.

Построение математической модели

Сеть дорог, связывающих базу с магазинами области можно представить в виде неориентированного графа, вершинам которого поставлены в соответствие название базы и магазинов, ребрам - связывающие их дороги, и каждому ребру поставлен в соответствие вес - длина дороги. Для удобства обозначим название базы через х_ьа торговые точки через х₂, х₃, х₃, х₅. Расстояния от вершины Х до всех остальных и между вершинами представим в виде матрицы весов неориентированного графа (табл. 2). Для наглядности в матрице весов знаки ? (показывающие отсутствие дороги) опустим. Тогда задача сводится к нахождению кратчайших путей от вершины X до всех остальных. Для ее решения используем метод Дейкстры.

Табл. 2

Решение задачи

1. Построение графа

Построим граф (рис. 1), соответствующий матрице смежности (табл. 2).

Рис. 1

2. Определение кратчайших расстояний от вершины до всех остальных.

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

Предварительно всем вершинам графа, кроме вершины х_ь присвоим временные метки, равные бесконечности: L(x₂) = L(х₃) = L(х₄) = L(х₅) =L(x6) = ?, а вершине Х₁присвоим постоянную метку L*(x₁)= 0. Занесем метки в нулевой столбец табл. 3.

Выполним последовательность следующих шагов:

Шаг 1

а) Определим множество вершин графа, смежных с вершиной x1 (рис. 1, табл. 2): S(1)= {х₂,x₃,х₄,х_5,x₆}.

б) Для каждой вершины, принадлежащей множеству S(x₁),вычислим новые временные метки L(xj),равные min{ L^CT(xj),L*(X]) + R]j},где L^CT(xj)- старая временная метка вершины xj, L*(xj)= 0 - постоянная метка вершины xj, Rj-вес ребра (xj, х,). Вычисления выполним в табл. 3-а.

L *(x_t) = 0

Табл. 3-а

Вершинам x₂, х_3, х_4, х_5, х₆ присвоим новые временные метки, вычисленные в табл. 3а

L(x2)=15, L(x3) =26, L(x4)=31, L(x5)=16, L(x6)=6. Занесем новые метки в первый столбец табл. 4. Обновленные метки выделим.

в) Из всех имеющихся временных меток в столбце 1 (табл. 4) выберем наименьшую и сделаем ее постоянной для своей вершины: min{15, 26, 31, 16, 6}=6. Эта метка соответствует вершине х6. Отметим ее звездочкой в столбце 1 L*(x6)= 6.

Табл. 4

а) Определим множество вершин графа, смежных с вершиной X₆, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(x₆)={Х₂}.

в) Для вершины Х₆, принадлежащей множеству S(x2),вычислим новые временные метку L(x₂),равные min{L^CT(x2), L*(x6) + R62}, где L^CT(x2) - старая временная метка вершины X2, L*(x6) ⁼ 6 - постоянная метка вершины Х6, R₆₂- вес ребра (Х6, Х2_;) (см. табл. 4-а).

Табл. 4-а

Занесем их во второй столбец (табл. 5). Из всех имеющихся временных меток в столбце 2 табл. 5 выберем наименьшую и сделаем ее постоянной для своей вершины: min{15, 26, 31, 16} = 15. Эта метка соответствует вершине L(х₂) = 15. Отметим ее звездочкой.

Табл. 5

Шаг 3

а) Определим множество вершин графа, смежных с вершиной х₂, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(X₂) = {Х₅}.

б) Для вершины, принадлежащей множеству S(х₂), вычислим новую временную метку L(x5), равную min{L^ст(x5), L*(x₂) + R₂₅} где L^СТ(^Х5) - старая временная метка вершины х₅, L*(х₂) = 15 - постоянная метка вершины х₂, R₂₅ - вес ребра (Х2, Х5_;) (см. табл. 5-а).

Табл. 5-а

в) Из всех имеющихся временных меток в третьем столбце табл. 5 выберем наименьшую и сделаем ее постоянной для своей вершины: min{26, 29, 16} = 16. Эта метка соответствует вершине х5: Ј*(х₅) = 16. Отметим ее звездочкой.

Табл. 6

Шаг 4

а) Определим множество вершин графа, смежных с вершиной Х5, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(X₅) = {X₃}.

б) Для вершины Х3, принадлежащей множеству S(х5), вычислим новую временную метки L(x3), равную min{X^CT(x3), L*(x5) + R53}, где L^CT(x3) - старая временная метка вершины Х3, L*(х5) = 16 - постоянная метка вершины Х5, R₅₃ - вес ребра (х5, х3)

Табл. 6-а

Вершине Х3 присвоим новую временную метку, т.е. L(x3) = 26. Занесем ее в четвертый столбец (табл. 7).

в) В четвертом столбце табл. 7 одна временная метка. Сделаем ее постоянной. Эта метка соответствует вершине х₃: L*(x₃) = 26. Отметим ее звездочкой.

Табл. 7

Шаг 5

а) Определим множество вершин графа, смежных с вершиной Х3, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(X₃) = {Х₄}.

в)Для вершины Х4, принадлежащей множеству S(х3), вычислим новую временную метку L(x3), равную min{X^CT(x4), L*(x3) + R34}, где L^CT(x4) - старая временная метка вершины Х4, L*(х3) = 26 - постоянная метка вершины Х3, R₃₄ - вес ребра (Х3, Х4) табл. 7-а.

Табл. 7-а

Вершине Х4 присвоим новую временную метку, т.е. L(x4) = 31. Занесем ее в пятый столбец (табл. 8).

Процесс расстановки меток закончен. Значения их дают кратчайшие расстояния от исходной вершины Х до всех остальных: L(x₂) =15, L(x₃) =26, L(х₄) =29, L(x₅) =16, L(x₆)=6.

На рисунке 2 в квадратных скобках укажем найденные кратчайшие расстояния от вершины X1 до всех остальных, т.е. взвесим вершины исходного графа.

Рис. 2

3. Определение кратчайших путей

Чтобы найти кратчайшие пути от вершины х до всех остальных вершин, используем соотношение:

L*(xj) = L*(xi) + R_ij

где вершина X_i предшествует вершине X_j.

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

Вершина Х4 имеет пять смежных вершин: х_1,х₂,х_3,х_5,х₆: S(х_1,х₂,х_3,х_5,х₆). Определим, какая из этих вершин удовлетворяет соотношению (4).

L*(x₄) = L*(Xi) + R_i4.

L*(x₄) = 29

Как видно, только вершина Х2 удовлетворяет соотношению (4). Следовательно, в кратчайшем пути вершине Х4 предшествует X2. Выделим на графе ребро Х₂,Х₄

б). Определим, какая вершина предшествует вершине Х2 в кратчайшем пути. Вершина X2 имеет смежные вершины: Х1, Х3,X5,X6 (вершина Х4 уже вошла в искомый путь и поэтому не рассматривается).Определим, какая из этих вершин удовлетворяет соотношению (4).

L*(x₂) =15,

Как видно, соотношению (4) удовлетворяет вершина Х1. Следовательно, в кратчайшем пути вершине Х2 предшествует вершина Х1 (рис. 3). Выделим на графе ребро Х1, Х2.

Рис. 3

Таким образом, минимальный путь от вершины Х₁ до вершины Х₄ проходит по вершинам x_1, x_2,x₄ и длина этого пути равна 29.

Очевидно, что каждый из путей из вершины X1 до любой вершины, входящей в построенный кратчайший путь (от вершины X1 в вершину Х4), тоже будет оптимальным.

Найдем кратчайший путь от вершины x₁ до вершины х₃.

а). Вершина х₃ имеет смежные вершины: S(x_1,x_2,x_4,x_5,x₆). Определим, какая из этих вершин удовлетворяет соотношению (4).

L*(x₃) = 26,

Как видно, соотношению (4) удовлетворяет только вершина х₁. Следовательно, в кратчайшем пути вершине х₃ предшествует вершина x₁.

Таким образом, минимальный путь от вершины х₁ до вершины х₃ проходит по ребру (х₁х₃) и длина его равна 26 (весу ребра).

Рис. 4

Найдем кратчайший путь от вершины x₁ до вершины х₃.

б). Вершина х₅ имеет смежные вершины: S(x_1,x_2,x_4,x₆). Определим, какая из этих вершин удовлетворяет соотношению (4).

L*(x₅) = 16,

Как видно, соотношению (4) удовлетворяет только вершина х₁. Следовательно, в кратчайшем пути вершине х₅ предшествует вершина x₁.

Таким образом, минимальный путь от вершины х₁ до вершины х₅ проходит по ребру (х₁х₅) и длина его равна 16 (весу ребра).

Рис. 5

Найдем кратчайший путь от вершины x₁ до вершины х₃.

в). Вершина х₆ имеет смежные вершины: S(x_1,x_2,x₄). Определим, какая из этих вершин удовлетворяет соотношению (4).

L*(x₆) = 6,

Как видно, соотношению (4) удовлетворяет только вершина х₁. Следовательно, в кратчайшем пути вершине х₆ предшествует вершина x₁.

Таким образом, минимальный путь от вершины х₁ до вершины х₆ проходит по ребру (х₁х₆) и длина его равна 6 (весу ребра).

Рис. 6

Размещено на Allbest.ru