Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

ЗАДАЧА 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), соответствующий матрице смежности (табл. 2).

Рис. 1

Определение кратчайших расстояний от вершины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{L^CT(xj), ( L*(x1) +R1j}
L(x₂) = ∞	L*(x₁) + R12 =	0 + 15 = 15	min{∞, 15} = 15
L(x₃) = ∞	L*(x₁) + R13 =	0 + 26 = 26	min{∞, 26} = 26
L(x₄)= ∞	L*(x₁) + R14 =	0 + 31 = 31	min{∞, 31} = 31
L(x₅)= ∞	L*(x₁) + R15 =	0 + 16 = 16	min{∞, 16} = 16
L(x₆)= ∞	L*(x₁) + 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{L^CT(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-а

L^CT(Xi)	L*(xi)+R2j		min{L^CT(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-а

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

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

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

Табл. 7

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

Шаг 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-а

L^CT(Xi)	L*(x3)+R3j		min{L^CT(xj), ( L*(x1) +R1j}
L(x4) = 29	L*(x₃) + R34 =	26 + 17 =	min{29, 43} = 29

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

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

Процесс расстановки меток закончен. Значения их дают кратчайшие расстояния от исходной вершины Х] до всех остальных:

L(x₂) =15 , L(x₃) =26 , L(х₄) =29 , L(x₅) =16 , L(x₆)=6.

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

Рис. 2

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

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

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

L*(x1)=0	R14=31	L(x4)=L(x1)+R14=0+31=31
L*(x2)=15	R24=14	L(x4)≠L(x2)+R24=15+14=29
L*(x3)=26	R34=17	L(x4)≠L(x3)+R34=26+17=43
L*(x5)=16	R54=26	L(x4)≠L(x5)+R54=16+26=42
L*(x6)=6	R64=28	L(x4)≠L(x6)+R64=6+28=34

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

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

L*(x₂) =15,

L*(x1)=0	R12=15	L(x2)=L(x1)+R12=0+15=15
L*(x3)=26	R32=16	L(x2)≠L(x3)+R32=26+16=42
L*(x5)=16	R52=24	L(x2)≠L(x5)+R52=16+24=40
L*(x6)=6	R62=33	L(x2)≠L(x6)+R62=6+33=39

Как видно, соотношению (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,

L*(x1)=0	R13=26	L(x3)=L(x1)+R13=0+26=26
L*(x2)=15	R23=16	L(x3)≠L(x2)+R23=15+16=31
L*(x4)=29	R43=17	L(x3)≠L(x4)+R43=29+17=46
L*(x5)=16	R53=19	L(x3)≠L(x5)+R53=16+19=35
L*(x6)=6	R63=25	L(x3)≠L(x6)+R63=6+25=31

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

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

Рис. 4

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

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

L*(x₅) = 16,


L*(x1)=0	R15=16	L(x5)=L(x1)+R15=0+16=16
L*(x2)=15	R25=24	L(x5)≠L(x2)+R25=15+24=39
L*(x4)=29	R45=26	L(x5)≠L(x4)+R45=29+26=55
L*(x6)=6	R65=14	L(x5)≠L(x6)+R65=6+14=20

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

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

Рис. 5

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

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

L*(x₆) = 6,


L*(x1)=0	R16=6	L(x6)=L(x1)+R16=0+6=6
L*(x2)=15	R26=33	L(x6)≠L(x2)+R26=15+33=48
L*(x4)=29	R46=28	L(x6)≠L(x4)+R46=29+28=57

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

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

Рис. 6

	х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	∞

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

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

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

	х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	∞

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

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

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

	х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	∞

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

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

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