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

ЗАДАЧА 2 / №1

УСЛОВИЕ ЗАДАЧИ

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

Расстояния от базы до каждого  магазина и между магазинами приводятся в таблице 1:

 

Табл. 1

	база	Т2	Т3	Т4	Т5	Т6
база	∞	15	26	31	16	6
Т2	15	∞	16	14	24	33
Т3	26	16	∞	17	19	25
Т4	31	14	17	∞	26	28
Т5	16	24	19	26	∞	14
Т6	6	33	25	28	14	∞

 

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

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

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

 

Табл. 2

	х1	х2	х3	х4	х5	х6
Х1	∞	15	26	31	16	6
Х2	15	∞	16	14	24	33
Х3	26	16	∞	17	19	25
Х4	31	14	17	∞	26	28
Х5	16	24	19	26	∞	14
Х6	6	33	25	28	14	∞

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

РЕШЕНИЕ ЗАДАЧИ

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

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

 

Рис. 1

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

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

 

					табл. 3
	0	1	2	3		4		5
х1	0*
х2	∞
х3	∞
х4	∞
х5	∞
х6	∞

 

Предварительно всем вершинам графа, кроме вершины х_ь присвоим временные метки, равные бесконечности: 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-а

L(Xj)	L*(xi)+R1j		min{LCT(xj), ( L*(x1) +R1j}
L(x2) = ∞	L*(x1) + R12 =	0 + 15 = 15	min{∞, 15} = 15
L(x3) = ∞	L*(x1) + R13 =	0 + 26 = 26	min{∞, 26} = 26
L(x4)= ∞	L*(x1) + R14 =	0 + 31 = 31	min{∞, 31} = 31
L(x5)= ∞	L*(x1) + R15 =	0 + 16 = 16	min{∞, 16} = 16
L(x6)= ∞	L*(x1) + R16 =	0 + 6 = 6	min{∞, 6}   = 6

 

Вершинам x₂, х_3, х₄ , х_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

	0	1	2	3	4	5
х1	0*
х2	∞	15
х3	∞	26
х4	∞	31
х5	∞	16
х6	∞	6*

 

а) Определим множество вершин графа, смежных с вершиной 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-а

L(Xj)	L*(xi)+R6j		min{LCT(xj), ( L*(x1) +R1j}
L(x2) = 15	L*(x6) + R62 =	6+ 33 = 39	min{15, 39} = 15
L(x3) = 26	L*(x6) + R63 =	6 + 25 = 31	min{26, 31} = 26
L(x4) = 31	L*(x6) + R64 =	6 + 28= 34	min{31, 34} = 31
L(x5) = 16	L*(x6) + R65 =	6 + 14 = 20	min{16, 20} = 16

 

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

 

 

 

 

 

 

 

Табл. 5

	0	1	2	3	4	5
х1	0*
х2	∞	15	15*
х3	∞	26	26
х4	∞	31	31
х5	∞	16	16
х6	∞	6*

 

Шаг 3

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

S(X₂) = {Х₅}.

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

 

Табл. 5-а

LCT(Xi)	L*(xi)+R2j		min{LCT(xj), ( L*(x1) +R1j}
L(x3) = 26	L*(x2) + R23 =	15 + 16 = 31	min{26, 31} = 26
L(x4) =31	L*(x2) + R24 =	15 + 14 = 29	min{31, 29} = 29
L(x5) =16	L*(x2) + R25 =	15 + 24 = 39	min{16, 39} = 16

 

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

 

Табл. 6

	0	1	2	3	4	5
х1	0*
х2	∞	15	15*
х3	∞	26	26	26
х4	∞	31	31	29
х5	∞	16	16	16*
х6	∞	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-а

LCT(Xi)	L*(xi)+R5j		min{LCT(xj), ( L*(x1) +R1j}
L(x3) = 26	L*(x2) + R53 =	16 + 19 = 35	min{26, 35} = 26
L(x4) = 29	L*(x2) + R54 =	16 + 26 = 42	min{29, 42} = 29

 

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

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