Математическое моделирование и решение транспортных задач

В разрезе основной задачи транспортной логистики (доставка грузов «точно в срок» и с наименьшими затратами) решаются частные задачи транспорта:

- определение кратчайших расстояний между точками транспортной сети;

- закрепление грузополучателей за грузоотправителями;

- обеспечение ритмичности поставок;

- составление рациональных маршрутов;

- разработка графиков поставки грузов, и другие.

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

Рассмотрим методы решения некоторых транспортных задач.

1.5.1 Определение кратчайших расстояний между точками транспортной сети

Для решения данной задачи модель (логистическую цепь) транспортной сети представляют в виде графа.

Граф – это фигура, состоящая из точек (вершин) и отрезков (ребер), их соединяющих.

Вершины (точки) – соответствуют основным грузообразующим и грузопоглощающим пунктам транспортной сети (потребителям грузов и грузоотправителям).

Ребра – могут иметь различный физический смысл: расстояния ( ), тарифы ( ), объемы перевозок ( ), время оборота автомобиля ( ) и так далее.

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

Пример графа показан на рисунке 9.

Дуги

Значения параметров

(например, в км)

5 5

3 2 4

6 Ребра

3

7 1 2

6

5

1

Вершины 5

Рисунок 9 – Граф транспортной сети

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

Суть решения задачи.

а)Даны:

- транспортная сеть, например, города с точками грузоотправления (грузоотправители) и грузополучения (грузополучатели);

- расстояния между всеми точками транспортной сети;

- ограничения движения транспорта (например, одностороннее движение между отдельными точками).

б) Требуется: из всей дорожной сети выбрать кратчайшие расстояния объезда всех точек из какой-то начальной точки – отправителя грузов.

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

а) По заданной схеме транспортной сети строим граф, включающий всех грузополучателей и грузоотправителей (пример на рисунке 10)

1 – грузоотправитель; 2, 3,…,8 – грузополучатели

Рисунок 10 – Граф заданной транспортной сети

б) В процессе решения задачи все множество вершин разбиваем на группы:

- 1 группа – вершины, до которых кратчайшие расстояния от начальной точки уже найдены;

- 2 группа – вершины, смежные (непосредственно связанные) с вершинами 1 группы;

- 3 группа – все остальные вершины с неопределенными кратчайшими расстояниями.

При начальном состоянии системы единственной вершиной 1-й группы является начальная вершина №1, так как расстояние «от нее до нее» известно и равно нулю. Остальные вершины не имеют определенных смежных вершин, и, стало быть, относятся к 3-й группе.

в) На основании выводов пункта б) строим таблицу 2 первичного состояния системы.

Таблица 2 – Первичное состояние системы

Номер вершины
Кратчайшее расстояние от начальной вершины		М	М	М	М	М	М	М	М
Номер предшествующей вершины
Группа вершин

В ней:

- кратчайшее расстояние для 1-й вершины будет равно нулю. Для остальных вершин кратчайшие расстояния не определены. Поэтому обозначаем их каким-то неопределенным большим число «М»;

- номера предшествующих вершин тоже не определены. Обозначаем их число «0».

На этом подготовительная работа закончена.

Этап 1.

а) Находим вершины, смежные с вершиной 1. Для нашего примера – это вершины 2, 3, и 4.

б) По графу находим кратчайшие расстояния от этих вершин до начальной вершины 1 и обозначим их индексами «d_i», где «i» – номер вершины. Для нашего примера:

- d₂ = 3 км;

- d₃ = 6 км;

- d₄ = 5 км

Так как эти вершины связаны с вершиной 1, отнесенной к 1-й группе, переводим их во 2-ю группу.

в) Зафиксируем это новое состояние системы таблицей 3.

Таблица 3 – Состояние системы на 1-м этапе

Номер вершины
Кратчайшее расстояние от начальной вершины, , км					М	М	М	М
Номер предшествую-щей вершины
Группа вершин

Этап 2.

а) Из вершин 2-й группы выбираем вершину с минимальным кратчайшим расстоянием (d_min) и переводим ее в 1-ю группу. В нашем примере – это вершина 2 с d₂ = d_min =3 км.

б) Находим вершины, смежные с вершиной 2. Это вершины 1, 3, 4 и 5. Вершина 1 уже переведена в 1-ю группу. Поэтому ее исключить из дальнейшего рассмотрения. Остаются вершины 3, 4 и 5.

в) Находим для этих вершин кратчайшие расстояния до начальной вершины по формуле

, км (1)

где - наименьшее кратчайшее расстояние от начальной вершины до предшествующей вершины, км;

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

Из этих вершин выбирается вершина с кратчайшим расстоянием и переводится в 1-ю группу. Остальные вершины, смежные с этой вершиной, переводятся во 2-ю группу.

Например, для приведенного на рисунке 10 графа транспортной сети

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

d₃ = 3 + 2 = 5 км – короче, чем d₃ по таблице 3. Заменяем им значение в последующей таблице 4,

d₄ = 3 + 4 = 7 км – длиннее, чем соответствующее расстояние в таблице 3, не принимаем ее во внимание,

d₅ = 3 + 3 = 6 км – новое значение. Внести его в последующую таблицу 4.

Согласно определению эти вершины относим ко 2-й группе.

г) Зафиксируем это состояние системы таблицей 4.

Таблица 4 – Состояние системы на 2-м этапе

Номер вершины
Кратчайшее расстояние от начальной вершины, , км						М	М	М
Номер предшествую-щей вершины
Группа вершин

Этап 3 и последующие этапы

Повторяем действия этапа 2 в порядке:

- из вершин 2-й группы выбираем вершину с d_min и переводим ее в 1-ю группу;

- находим вершины, смежные с вершиной, имеющей d_min;

- находим расстояние d_j от этих вершин до начальной вершины;

- переводим эти вершины во 2-ю группу;

- фиксируем это состояние новой таблицей.

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

Таблица 5 – Окончательное состояние системы

Номер вершины
Кратчайшее расстояние от начальной вершины, , км
Номер предшествую-щей вершины								3-4
Группа вершин

По окончательной таблице строим оптимальные маршруты, наводя их двойными линиями на графе (рисунок 10).

1.5.2 Задача расчета потребного числа автомобилей

Успешное выполнение перевозок зависит от оптимального количества выпускаемых на линию автомобилей.

Суть задачи.

а) Дано:

- количество грузоотправителей – n. Обозначим их О₁, О₂, О_3,...,О_X,…, О_n;

- количество грузополучателей – m. Обозначим их П₁, П₂, П₃,…, П_i,… Пm;

- количество груза, которое необходимо доставить каждому получателю – G_Пi, т. Например, G_П1, G_П2, G_П3,…,G_Пi,…, G_Пm ;

- время, отпущенное для вывоза груза - Т, мес.;

- продолжительность рабочей смены – t_СМ, час.;

- время оборота автомобилей на маршрутах «грузоотоправитель-грузополучатель-грузоотправитель» - t_Пi, час. Например, t_П1, t_П2, t_П3,…t_Пi,…, t_Пm;

- грузоподъемность выделенных автомобилей – Q, т.;

- количество рабочих дней в месяце – Д_Р.Д.

б) Требуется определить максимально допустимое количество автомобилей, необходимых для выполнения этой работы - C_max.

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

Для примера примем систему из одного поставщика груза и j получателей.

а) Определяем суммарное количество ездок к получателям грузов

; (2)

б) Определяем среднее количество ездок в день для каждого получателя

(3)

На этом подготовительный этап решения закончен

1-й этап

а) Составим j возможных вариантов маршрутов с условием, что суммарное время их выполнения ( ) не превышает времени смены ( ).

В принципе элементами каждого маршрута являются ездки от любого грузообразующего пункта (О_X) до любого из грузополучателей (П_i) и обратно. В общем случае обозначим этот элемент «О_X – П_i», который соответствует времени оборота автомобиля t_Пi . Тогда любой j–тый маршрут обозначится последовательными сочетаниями «О_X – П_i». Например, 1-й маршрут от грузообразующего пункта О₁ как вариант может быть обозначен

О₁ – П₁ – О₁ – П₁ – О₁ – П₃ – О₁ – …– О₁ – П_i

При этих сочетаниях «О_X – П_i» суммарное время каждого маршрута (t_Mj) не должно превышать продолжительности рабочей смены (t_СМ)

, (4)

где - количество одинаковых элементов «O_X – П_i» в маршруте.

Перечень маршрутов оформляется в виде таблицы (таблица 6).

Таблица 6 – Перечень маршрутов (пример)

№ маршрута п/п	Маршрут	Время выполнения, час
1.	О1 – П1 – О1 – П1
2.	О1 – П2 – О1 –… – О1 – П2
………….	………………………………………	………………….
Z	О1 – Пi – О1 –…– О1 – Пm
…….….	……………………………………….	………………….
…………	………………………………………..	………………….
j	О1 – Пi – О1 – …– О1 – Пm

б) Предположим, что на каждом j-том маршруте должно работать X_j автомобилей. Допустим, что каждый из i-тых грузополучателей (например, грузополучатели П₁, П₂,…,П_i и так далее) обслуживаются всеми маршрутами. Тогда общее среднее количество ездок в день к каждому получателю ( ) может быть выражено суммой произведений количества автомобилей на каждом маршруте (X_j) на количество ездок в сутки ( ) к i-тому получателю по j-тому маршруту

= (5)

1-й маршр. 2-й маршр. j-й маршр.

Этих уравнений будет столько, сколько потребителей грузов.

В этих уравнениях количество автомобилей на соответствующих маршрутах (Xj) неизвестно. Количество ездок в сутки к i-тому получателю по j-тому маршруту (a_ij) определяется по таблице 6 как сумма одинаковых сочетаний «О_X – П_i», соответствующих данному потребителю. Например, для потребителя 1: по маршруту 1 соответствующее сочетание будет «О₁ – П₁». Этих сочетаний в маршруте 1 содержится два (таблица 6). Следовательно, . Аналогично по маршруту 2 соответствующие сочетание также будут «О₁ – П₁». Они в маршруте 2 отсутствуют. Следовательно, a₁₂ =0, и так далее.

Уравнение (5) необходимо дополнить уравнением цели, отражающим цель расчета: общее число автомобилей ( ) должно равняться сумме всех автомобилей на всех маршрутах

, (6)

где – коэффициенты загрузки автомобилей, работающих на соответствующих маршрутах.

Однако, уравнения (5) и (6) не отвечает начальному условию. В начальный момент времени при отсутствии автомобилей на линии ( ) правая часть уравнений обращается в нуль. Но левая часть уравнения (5) уже задана уравнением (3) и не равна нулю. Для устранения этого противоречия введем в уравнение (5) дополнительные переменные с коэффициентами «1» перед , соответствующими номеру получателя. Остальные коэффициенты принимаем равными нулю. Так же поступим с уравнением (6), введя в него дополнительные переменные с коэффициентами «0».

Тогда математическая модель задачи может быть выражена системой линейных уравнений

(7)

и уравнением цели

(8)

в) Нахождение точного решения поставленной задачи заключается в решении системы уравнений (7) совместно с уравнением (8). По существу это решение уравнений с неизвестными и является трудоемкой задачей даже с применением ЭВМ.

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

Симплексная таблица показана на рисунке 11.

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

Для этого:

- в столбце свободных членов проставляем значения свободных членов из системы уравнений (7);

- в основных строках дополнительных переменных для каждого X_j проставляем значения коэффициентов a_ij из системы уравнений (7);

- заполняем индексную строку «z_j – c_j»,

где c_j - коэффициент загрузки автомобилей на маршрутах (формула (6))

, (9)

Строка переменных

х

X1

X2

X3

…

Xj

ω1

ω2

ω3

…

…

ωm

ω1

.

ω2

..

0

ω3

..

…

…

…

…

…

.

…

…

…

…

…

…

…

ωm

..

zj-cj

0

-1

-1

-1

-1

Основные столбцы переменных и .Количество столбцов

равно количеству маршрутов плюс количество получателей (j+m)

Основные строки дополнительных

переменных. Количество строк рав-

Индексная строка но количеству получателей – m

Столбец свободных членов

Столбец дополнительных переменных

Рисунок 11 – Симплексная таблица

В соответствии с начальными условиями коэффициенты при дополнительных переменных в уравнении (6) равны нулю. Стало быть, в соответствии с уравнением (9) для всех маршрутов.

Если принять коэффициенты загрузки автомобилей по всем маршрутам c_j = 1, то

z_j – c_j = 0 – 1 = –1 (10)

для всех маршрутов. Проставляем их в индексной строке для основных переменных.

В то же время в соответствии с уравнением (8) коэффициенты при дополнительных переменных равны нулю. Проставляем их в таблице;

- заполняем основные строки дополнительных переменных в столбцах переменных в соответствии с системой уравнений (7).

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

Этап 2

а) Определяется ключевой столбец. Это столбец, у которого в индексной строке стоит отрицательное число с максимальным модулем. В начальный момент во всех столбцах проставлено одинаковое число: –1. Поэтому мы в праве взять любой столбец X_j в качестве ключевого. Но для упорядочения действий выбираем их по порядку и определяем ключевым столбец X₁. Обводим его тонкой линией;

б) Определяем ключевую строку. Для этого свободные члены разделим на соответствующие коэффициенты ключевого столбца. Наименьшее частное от деления и определит ключевую строку.

Например, - ключевая строка – ω₂. Обведем ключевую строку тонкой линией.

в) На пересечении ключевого столбца и ключевой строки находится ключевое число. Для приведенного примера оно равно .

г) Пересчитываем значения ключевой строки, деля их на ключевое число:

; ; ; ; ; ;

д) Выводим из ключевой строки дополнительную переменную ω_i (в приведенном примере – ω₂). Вывод ее из таблицы указываем стрелкой. В дальнейшем заменяем ее основной переменной X_j ключевого столбца. В нашем случае – X_1.

е) Пересчитываем значения индексной строки по формуле

(11)

Значения в индексной строке, имеющие «0» в ключевой строке, не пересчитываются, так как их значения остаются без изменения. Действительно, например, для столбца , где выбранное для пересчета число равно нулю

Стало быть, в нашем случае пересчитываются только значения в столбцах свободных членов, X₁, X₂, X₃, X_j и :

столбец свободных членов ,

cтолбец X₁ ,

столбец X₂ ,

столбец X₃ ,

столбец X_j ,

столбец

ж) Строим новую симплексную таблицу 7 с измененными значениями коэффициентов в основных строках и индексной строке с заменой дополнительной переменной ω₂ на основную переменную X₂.

Таблица 7

X1

X2

X3

…

Xj

ω1

ω2

ω3

…

…

ωm

.

X1

..

ω3

..

…

…

…

…

…

.

…

…

…

…

…

…

…

ωm

..

zj-cj

В новой и последующих симплексных таблицах появились основные переменные X_j. Поэтому, пересчитываем строки основных переменных по формуле 11. Затем повторяем действия этапа 2 до тех пор, пока из индексной строки не исчезнут отрицательные числа. В результате:

- в столбце переменных окажутся наиболее целесообразные маршруты. Например, X₁, X₂,…X_j;

- напротив них в столбце свободных членов окажутся потребные количества автомобилей для обслуживания этих маршрутов;

- в индексной строке столбца свободных членов – суммарное число автомобилей для обслуживания всех маршрутов.

1.5.3Задача закрепления грузополучателей за грузоотправителями

Суть задачи.

а) Дано:

- в пунктах отправления грузов А₁, А₂,…, А_j имеется груз в количестве a₁, a_2, …, a_n тонн;

- этот груз необходимо отправить потребителям Б₁, Б₂,..., Бi в количестве соответственно b₁, b₂,…, b_i тонн;

- расстояния между пунктами заданы и равны соответственно C_ij км.

б) Требуется найти вариант перевозок с наименьшим объемом транспортной работы в тонно-километрах ( ).

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

- i уравнений (по количеству потребителей) с j неизвестными (по количеству поставщиков) в каждом уравнении;

- j уравнений (по количеству поставщиков) с i неизвестными (по количеству потребителей) в каждом уравнении.

То – есть пришлось бы составить и решить (i + j) уравнений с (j х i) + (i х j) = 2ji неизвестными плюс уравнение цели, отражающее необходимость минимума транспортной работы. Например, при четырех отправителях и пяти получателях пришлось бы составить и решить 10 уравнений с 20-ю неизвестными, что затруднительно даже при применении современной электронно-вычислительной техники.

Таблица 8 – Матрица симплексной таблицы

Основные строки, количество – по числу потребителей	Потреби- тели	Вспо-мога- тель- ная	Поставщики	Потреб- ность в грузе, т.
А1	А2	…	Аj
U V			…
Б1 Наши рекомендации Теоретические сведения. Решение таких задач, как планирование расписаний, игровых задач, задач обучения и т Методы обучения и преподавания. · Практические занятия: решение тестовых заданий и ситуационных задач, устный опрос, работа в малых группах: моделирование ситуации; деловые игры Понятия «модель» и «моделирование». Модель и оригинал. Экономико-математическое моделирование и его основные этапы. Классификация экономико-математических моделей и методов Математическое моделирование и решение экономических задач Математическое моделирование Решение задач и моделирование Математическое моделирование Тема I. Решение психолого-педагогических задач, моделирование образовательной и педагогической ситуаций. (2 часа) Решение транспортных задач с ограничениями Лабораторная работа №9: Решение транспортных задач с усложнениями ← Предыдущая страница | Следующая страница →