Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,916

ТРАНСПОРТНАЯ ЗАДАЧА С УЧЕТОМ ВРЕМЕНИ ПОСТАВОК

Гоголин В.А. 1 Николаева Е.А. 1
1 ФГБОУ ВО «Кузбасский государственный технический университет имени Т.Ф. Горбачева»
Классическая транспортная задача – это математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов с минимизацией затрат на их перемещение. В литературе данная задача широко изучена, в данной работе описана транспортная задача, в которой введены дополнительные ограничения, связанные с выполнением всех поставок в заданный срок. Это дополнительные ограничения, связанные со скоростью поставок, и ограничения, задающие момент времени к которому груз должен быть доставлен, то есть дополнительно введены два вида ограничений, одни относительно поставщиков, другие относительно заказчиков. Учет времени поставок оказывает существенное влияние на оптимальное распределение поставок и значение минимума транспортных затрат. В работе показано, что с возрастанием скоростей поставок решение транспортной задачи с учетом времени поставок будет стремиться к решению классической транспортной задачи.
задача линейного программирования
линейная форма
транспортная задача
закрытая транспортная задача
минимизация затрат на перемещение
1. Лубенцова В.С. Математические методы и модели в логистике / В.С. Лубенцова. – Самара: Самар. гос техн. ун-т. 2008. – 157 с.
2. Данциг Д. Линейное программирование, его применения и обобщения / Д. Данциг. – М.: Прогресс, 1966. – 600 с.
3. Палий И.А. Линейное программирование / И.А. Палий. – М.: Эксмо, 2008. – 258 с.
4. Кузнецов А.В. Высшая математика. Математическое программирование / А.В. Кузнецов, В.А. Сакович, Н.И. Холод. – СПб.: Лань, 2013. – 352 с.
5. Мунасыпов Н.А. Линейное программирование / Н.А. Мунасыпов. – М.: Пресса, 2015. – 122 с.
6. Акулич И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич. – СПб.: Лань, 2011. – 352 с.
7. Резниченко С.С. Математические методы и моделирование в горной промышленности / С.С. Резниченко, А.А. Ашихмин. – М.: Изд-во МГГУ, 2001. – 401 с.
8. Горенский Б.М. Моделирование процессов и объектов в металлургии / Б.М. Горенский, Л.А. Лапина, А.Ш. Любанова и др. – Красноярск: ИПК СФУ, 2008. – 145 с.
9. Тырин А.Ю. Модели транспортного обслуживания в цепях поставок пищевой промышленности // Вестник КузГТУ. – 2011. – № 4. – С. 89–92.

Основной задачей математического моделирования транспортных перевозок является построение оптимального плана перевозок [1]. В классической постановке Монж – Канторовича предполагается оптимизация по времени или стоимости перевозок однородного груза без учета временных требований заказчика, то есть требований выполнения сроков поставок. Это серьезное допущение значительно сужает возможности использования классической транспортной задачи при решении прикладных вопросов. В данной работе предлагается обобщение математической модели транспортных перевозок с учетом времени поставок.

Классическая транспортная задача

Математическая постановка классической транспортной задачи сводится к следующему [2–4]: требуется найти минимум линейной формы с n + m переменными:

gog01.wmf (1)

С выполнением баланса по поставкам от m поставщиков

gog02.wmf

С выполнением баланса по заказам от n заказчиков

gog03.wmf

Очевидно, принимается, что Xij ≥ 0.

Коэффициенты cij линейной формы (1) определяют стоимость или время перевозки единицы груза от i-го поставщика к j-му заказчику; Xij – количество груза, отправляемое от i-го поставщика к j-му заказчику.

Одним из видов транспортных задач является так называемая транспортная задача в замкнутой форме – суммарные объемы поставок и заказов равны. Замкнутая транспортная задача в классической ее постановке решается методом потенциалов, который достаточно полно изложен в работах [3, 6].

Транспортная задача с учетом времени поставок

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

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

Каждый из n заказчиков задает сроки поставок, которые формируют вектор сроков поставок:

gog04.wmf.

Каждый из m поставщиков задает скорости поставок от i-го поставщика к j-му заказчику, которые формируют матрицу скоростей поставок:

gog24.wmf.

Элемент матрицы поставок vij задает возможный объем вывозимых грузов от i-го поставщика к j-му заказчику в единицу времени.

Для того, чтобы каждый i-ый поставщик мог бы в срок не более чем за Sj единиц времени поставить свой груз в размере Xij, j-му заказчику требуются следующие дополнительные m + n×ограничений по скоростям поставок:

gog05.wmf. (2)

Это первое дополнительное ограничение.

В то же время скорости поставок должны быть такими, чтобы не позже назначенного заказчиком срока Sj, заказы в объемах Bj должны быть выполнены. Таким образом, получаем второе дополнительное ограничение, связывающее сроки и скорости поставок:

gog06.wmf (3)

кроме этого, необходимо обеспечить вывоз всех объемов поставок, что приводит ко второму условию на сроки заказов и скорости поставок:

gog07.wmf (4)

Условия (3, 4) являются условиями разрешимости транспортной задачи с учетом времени поставок. Напомним, что условием разрешимости классической транспортной задачи является условие замкнутости [2, 4].

Таким образом, сформулированная транспортная задача с учетом времени поставок обобщает классическую транспортную задачу и формулируется следующим образом.

Требуется найти минимум линейной формы (1) с ограничениями (2, 3, 4):

gog08.wmf,

gog09.wmf

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

Результаты исследования и их обсуждение

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

Классическая транспортная задача. Имеется три поставщика с заданными запасами товаров:

gog10.wmf

и четыре заказчика с соответствующими потребностями:

gog11.wmf.

Матрица тарифов имеет вид

gog12.wmf.

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

Математическая модель данной транспортной задачи имеет вид: требуется найти минимум следующей линейной формы:

gog13.wmf

при условии Xij ≥ 0 и следующих ограничениях:

gog14.wmf

Задача решалась методом потенциалов. Решение имеет вид

gog15.wmf

Транспортная задача с учетом времени поставок. В условия предыдущего примера добавим вектор сроков поставок:

gog16.wmf,

и матрицу скоростей поставок:

gog17.wmf.

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

Дополнительные двенадцать ограничений по срокам поставок (2) имеют следующий вид:

gog18.wmf

Переобозначим переменные в целевой функции (1) и в ограничениях (2, 3, 4).

gog19.wmf

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

Найти минимум линейной формы:

gog20.wmf

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

gog22.wmf

Задача решена симплекс-методом. Решение имеет вид

gog23.wmf

Наглядное сравнение решений классической транспортной задачи и транспортной задачи с учетом времени поставок приведено в таблице.

Сравнение решений классической транспортной задачи и транспортной задачи с учетом времени поставок

Без ограничения сроков поставок

С ограничением сроков поставок

 

1

2

3

4

Запасы

 

1

2

3

4

Запасы

1

0

50

60

0

110

1

28

12

50

20

110

2

80

0

110

0

190

2

40

30

84

36

190

3

0

10

0

80

90

3

12

18

36

24

90

Потребности

80

60

170

80

 

Потребности

80

60

170

80

 

Fmin(x) = 1330

Fmin(x) = 1698

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

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

Учет времени поставок при моделировании транспортных перевозок позволит находить более адекватные оптимальные решения в задачах логистики [1], в транспортных задачах горной промышленности [7], металлургии [8], пищевой промышленности [9] и других областях.

Заключение

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


Библиографическая ссылка

Гоголин В.А., Николаева Е.А. ТРАНСПОРТНАЯ ЗАДАЧА С УЧЕТОМ ВРЕМЕНИ ПОСТАВОК // Современные наукоемкие технологии. – 2017. – № 7. – С. 23-26;
URL: http://www.top-technologies.ru/ru/article/view?id=36723 (дата обращения: 31.05.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074