3.3. Задания на лабораторную работу и методические указания к её выполнению

1. Задание на лабораторную работу

По данному курсу студентом выполняется одна лабораторная работа по определению кратчайшего маршрута движения между двумя пунктами города по разветвленной транспортной сети.

Транспортная сеть города и расстояния между соседними пунктами известны, рис. 6. Требуется определить кратчайшее расстояние и путь следования от пункта Аi последовательно до пунктов Аj

Рис.6. Транспортная сеть города и расстояния между пунктами (км)

Номер начального пункта iопределяется последней цифрой шифра студента (если последняя цифра шифра 9, принимается i¹=8, если последняя цифра шифра 0, принимается i=1). Номера конечных пунктов j принимаются по табл. 1 по предпоследней цифре шифра студента.

Таблица 1

Номера конечных пунктов j транспортной сети

Показатель	Предпоследняя цифра шифра студента (варианты)
	1	2	3	4	5	6	7	8	9	0
Номер конечного пункта маршрута	1	1	1	1	1	1	1	1	1	1
--,,--	2	3	3	2	2	4	2	2	4	3
--,,--	3	4	4	6	4	5	7	5	5	4
--,,--	8	5	7	7	6	6	8	8	7	6
--,,--	5	8	8	3	8	8	5	4	8	7
--,,--	7	7	5	8	5	7	3	7	2	2

Например, если две последние цифры шифра студента 79, то i=8 j=1,2,7,8,5,3 (табл. 1, вариант 7). Если две последние цифры 58, то i=8, j=1,2,4,6,8,5 (табл.1, вариант 5).

Основные требования по оформлению лабораторной работы следующие:

- пишется на одной стороне стандартных листов формата А4, все листы, начиная с титульного, нумеруются. Листы должны быть сброшинрованы;

- схема и таблицы выполняются на отдельных листах, сноски и пояснения делаются внизу под схемой и таблицей;

-разделы должны иметь сквозную нумерацию, оглавление в лабораторной работе необязательно;

- лабораторная работа выполняется по вариантам. Работа, выполненная не по варианту, к защите не принимается и не засчитывается.

2. Математическая постановка задачи о кратчайшем пути

и метод её решения

Пусть задана транспортная сеть, состоящая из пунктов А₁, А_2…, А_i…, А_m и дорог, соединяющих эти пункты между собой. Длины участков дороги между каждой парой соседних пунктов А_i Аj известны и равны l_jj. Если два соседних пункта А_i и Аj непосредственно не соединены между собой участком дороги, то принимаем l_jj= ∞. Из начального пункта А₁ в конечный пункт А_m можно попасть по большому числу маршрутов, проходящих через разные промежуточные пункты. Требуется найти среди этих маршрутов путь наименьшей протяженности [13].

Переведём задачу на формальный язык. Обозначим каждый участок сети между двумя соседними пунктами А_i и Аj числом x_ij= 1, если он является звеном выбранного маршрута движения из А_i в А_m и x_ij=0, если он не входит в этот маршрут. Тогда задача отыскания кратчайшего пути из А_i в А_m сводится к выбору чисел x_ij (i, j = 1, 2, …, m), при которых достигает минимума линейная форма

m n

∑ ∑ _ijx_ij (1)

i=1 j=1

при условии

m

∑ (x_ij - xj_i) = 0, i =2, 3, …, m -1; (2)

j=1

m

∑ (x_ij - xj_i) = 1; (3)

j=1

m

∑ (x_mj – xj_m) = -1; (4)

j=1

0≤ Xij ≤ 1, i, j = 1,2……………m (5)

Линейная форма (1) определяет длину маршрута между начальным и конечным пунктами. Условия (2) означают, что для любого пункта маршрута А_i, исключая начальный и конечный, число дорог, входящих в этот пункт, равно числу дорог, выходящих из него. Поскольку l_ji>0 для всех I и j, условия (2) вместе с требованием минимизации линейной формы (1) означают, что из каждого пункта Аi (i=2, 3, …, m -1) выходит не более одной дороги. Условия (3)_ фиксируют тот факт, что количество дорог, выходящих из начального пункта маршрута Аi превышает на единицу число дорог, входящих в этот пункт. Аналогично условия (4) указывают на то, что в последний пункт А_m входит на одну дорогу больше, чем выходит. Условия (3) и (4) вместе с условиями (2) и требованием минимизации линейной формы (1) означают, что в каждый пункт маршрута входит ровно одна дорога и из каждого пункта маршрута исходит ровно одна дорога. Наконец, условия (5) требуют, чтобы все x_ij были равны нулю или единице. В целом соотношения (1)-(5) представляют собой определение кратчайшего пути на сети дорог между двумя заданными пунктами.

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

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

Общая вычислительная схема применительно к данной задаче следующая. В специальную таблицу (табл. 2) типа «шахматной»

Таблица 2

Пункт	Вспомо- гатель- ные	Пункт
		А1	А2	…	Аj	…	Аm
	с трока столбец	υ1	υ2	…	υj	…	υm
А1	u1	l11	l12	…	l1j	…	l1m
А2	u2	l21	l22	…	l2j	…	l2m
…	…	…	…	…	…	…
Аi	ui	li1	li2	…	lij	…	lim
…	…	…	…	…	…	…	…
Аm	um	lm1	lm2	…	lmj	…	lmm

заносят расстояния l_ji от каждого пункта Аi ((i=1, 2, …, m ) до всех соседних с ним пунктов Аi ((i=1, 2, …, m ). После этого для каждого пункта Аi и Аj рассчитывают индексы u_i и υ_j следующим образом. Индекс u_i принимают равным нулю (u_i =0). Затем по порядку, начиная с первой строки таблицы рассматривают клетки с заполненными l_ji . Если для некоторой заполненной клетки (I, j) индекс u_i уже известен, а υ_j - ещё нет, то определяют υ_j по формуле

υ_j= u_i+ l_ji . (6)

Если при определении очередного υ_j в i-м столбце имеется более одной клетки с записанными l_ji и известными u_i , то принимают

υ_j = min (u_i+ l_j) . (7)

Найденные значения υ_j записывают в соответствующие клетки вспомогательной строки, а также в клетки вспомогательного столбца, исходя из правила: u₁= υ₁, u₂= υ₂, … u_m= υ_m. После определения всех индексов υ_j и u_i проверяют оптимальность данного решения, сравнивая все l_ji с их разностями (υ_j- u_i). Если для всех заполненных клеток соблюдается условие

l_ij ≥υ_j- υ_j (8)

то решение оптимально и каждое найденное число υ_j дает кратчайшее расстояние от пункта А₁ до соответствующего пункта А_i, до соответствующего пункта Аj (i=1,2,…m). При наличии хотя бы одной клетки с величиной l_ij <υ_j- u_i, решение неоптимально и вычисления необходимо продолжить.

Предположим, что в клетке Аi _n Аj _n нарушено условие оптимальности (8), т.е.

li _njn< υ i _n- ui _n.

В этих условиях необходимо изменить решение следующим образом. Индекс υ _{j n} заменяют индексом υ` i _n величину которого определяют по формуле

υ i _n= υ i _n+ li _njn.

На каждой итерации корректируют индексы υ_j у всех клеток с l_ij< υ_j- u_i после чего решение снова проверяют на оптимальность. Вычисления повторяют до тех пор, пока в таблице не будет выполнено условие оптимальности (8).

При определении кратчайших расстояний от пункта А₂ до всех остальных принимают u₂=0, после чего находят все индексы и выполняют все описанные выше вычисления. При определении кратчайших расстояний от пункта А₃ до всех остальных принимают u₃=0 и т.д.