X Международная студенческая научная конференция Студенческий научный форум - 2018

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

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

Выполним постановку задачи. Пусть имеется n пунктов. Расстояния между любой их парой i и j известны и составляют c_ij. Автотранспортное средство выезжает из какого-либо пункта и должно посетить все пункты, побывав в каждом только один раз и вернуться в исходный пункт. В качестве исходного пункта выступает, обычно, либо гараж АТП, либо склад загрузки перевозимого груза. Ставится задача определить такую последовательность объезда городов, или маршрут, при которой суммарная длина маршрута была бы минимальной.

Сформулируем математическую модель поставленной задачи. Определим булевы переменные задачи: x_ij = 1, если АТС перемещается из пункта i в пункт j, и x_ij = 0, если автотранспортное средство не переезжает из пункта i в пункта j.

Тогда задача заключается в определении минимума целевой функции

,

при ограничениях

– только один въезд в пункт j,

– только один выезд из пункта i .

В задаче необходимо еще одно условие, а именно:

, i ≠ j, i, j = 2,…, n.

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

Сформулированная задача решается средствами ЭТ MS Excel также как и обычные транспортные задачи, за одним исключением: так как переменные по смыслу задачи могут принимать только двоичные значения 0 или 1, то в ограничениях, задаваемых в диалоговом окне Поиск решения, необходимо указать, что переменные имеют булевы значения.

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

Рис. 1. – Диалоговое окно Добавление ограничения для задания двоичной (булевой) переменной

Приведем решение задачи в среде ЭТ MS Excel.

Пусть имеется 5 пунктов, расстояния с_ij между которыми приведены в таблице.

Номер пункта	1	2	3	4	5
1	∞	9	8	4	10
2	6	∞	4	5	7
3	5	3	∞	6	2
4	1	7	2	∞	8
5	2	4	5	2	∞

В диагональных клетках таблицы стоят значки ∞ (любое большое число, значительно превосходящее остальные числа в таблице), так как прямого маршрута между одноименными пунктами не существует.

Автотранспортное средство, выезжая из пункта 1, должно посетить все пункты, побывав в каждом из них только по одному разу и вернуться в исходный пункт. Необходимо определить такой маршрут объезда, при которой длина маршрута будет минимальной.

Математическая модель задачи в этом случае принимает вид.

Переменные x_ij могут принимать значения равные либо 0, либо 1

– целевая функция,

ограничения:

– условие въезда в пункт j только один раз,

– условие выезда из пункта i только один раз,

, где n = 5,

то есть

, i ≠ j, i, j = 2,…, n .

Исходные данные в рабочей книге Excel приведены на рис. 2. Здесь же приведены формулы для вычисления ограничений и целевой функции.

Рис. 2. – Исходные данные и целевая функция

На панели Поиск решения установить следующие параметры решения задачи:

Целевую ячейку – $B$10 ‒ Равной минимальному значению.

Изменяя ячейки: $B$4:$F$8;$C$11:$F$11 – здесь заносятся не только ячейки, которые будут изменяться, и в которых будут занесены решение задачи (ячейки с адресами $B$4:$F$8), но и ячейки $C$11:$F$11, содержащие переменные u_i , которые также являются изменяемыми.

Ограничения:

$B$21:$E$24 ≤ 3

$B$4:$F$8 = двоичное

$B$9:$F$9=1

$G$4:$G$8=1

$B$4=0

$C$5=0

$D$6=0

$E$7=0

$F$8=0

Параметры: линейная модель, неотрицательные значения, автоматическое масштабирование.

После нажатия кнопки Выполнить на диалоговой панели Поискрешения. На рабочем листе Excel появляются результаты решения задачи (рис. 3).

ЗАДАЧА
	Матрица переменных					Ограничения
	1	2	3	4	5
1	0	0	0	1	0	1
2	1	0	0	0	0	1
3	0	0	0	0	1	1
4	0	0	1	0	0	1
5	0	1	0	0	0	1
Ограничения	1	1	1	1	1
Целевая функция в B10	18
Переменные u в C11:F11		3	1	0	2
	Матрица расстояний
	1	2	3	4	5
1	10000	9	8	4	10
2	6	10000	4	5	7
3	5	3	10000	6	2
4	1	7	2	10000	8
5	2	4	5	2	10000
Формулы для Ограничений по дополнительным переменным u
	u2	u3	u4	u5
u2	0	2	3	1
u3	-2	0	1	3
u4	-3	3	0	-2
u5	3	1	2	0

Рис. 3. – Результаты решения задачи коммивояжера

Итак, оптимальное решение таково: целевая функция F = 18, получившийся маршрут: 1 → 4 → 3 → 5 → 2 → 1.

Рабочий лист MS Excel с результатами решения задачи коммивояжера представлен на рис. 4.

Рис. 4. – Рабочий лист MS Excel с результатами решения

Код для цитирования: Скопировать