Электронный научный журнал
Международный студенческий научный вестник
ISSN 2409-529X

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

Пушка В.С. 1 Матвеева Т.А. 1 Светличная В.Б. 1 Соколова А.В. 1
1 Волжский политехнический институт
К транспортным задачам относится широкий круг задач с общей математической моделью, они определяются как задачи линейного программирования специального вида и решаются оптимальными методами. В классическом виде транспортной задачи выделяют два типа: по критерию стоимости (минимизируются затраты на перевозку) и по критерию времени (минимизируется время на перевозку грузов). Мы рассматриваем класс задач по минимизации общей стоимости перевозок грузов из пунктов отправления в пункты потребления. По теории сложности вычислений транспортная задача входит в класс сложности P. В работе рассмотрены методы решения транспортных задач. Существует ряд методов построения начального опорного решения, наиболее простым из них является метод северо-западного угла. Далее для анализа полученного плана и его последующего улучшения вводятся дополнительные характеристики пунктов отправления и назначения, называемые потенциалами. Такой метод улучшения плана перевозок называется методом потенциалов. При этом на каждом этапе строится разгрузочный цикл, который позволяет снижать расходы на перевозку. Транспортная задача применяется в случаях: оптимизации поставок сырья и материалов на производственные предприятия; оптимизации доставок товаров со складов в розничные магазины; оптимизации пассажирских перевозок, и т.п.
транспортная задача
метод северо-западного угла
метод потенциалов
план перевозок
1. Агишева Д.К., Зотова С.А., Светличная В.Б., Матвеева Т А. Транспортные и сетевые модели управления. Часть 2: учебное пособие / С.А. Зотова, Д.К. Агишева, В.Б. Светличная, Т.А. Матвеева; ВПИ (филиал) ВолгГТУ. – Волгоград: ИУНЛ ВолгГТУ, 2012. – 160 с.
2. Агишева Д.К., Зотова С.А., Матвеева Т.А., Светличная В.Б. Линейное программирование (учебное пособие) // Успехи современного естествознания. – 2010. – № 9 – С. 61–62 URL: www.rae.ru/use/section=content&op=show_article&article_id=7785125.
3. Казачков А.Д., Агишева Д.К., Светличная В.Б., Зотова С.А. Реализация метода северо-западного угла на Mathcad 15 // Материалы VIII Международной студенческой электронной научной конференции «Студенческий научный форум» www.scienceforum.ru/2016/1762/23702.

Транспортная компания занимается перевозкой зерна специальными зерновозами от трёх элеваторов к четырём мельницам. В табл. 1 показаны возможности отгрузки зерна элеваторами, а также стоимость перевозки зерна одним зерновозом от элеваторов к мельницам. Стоимость перевозок приведена в ден. ед. [1].

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

Начальное решение получим, например, методом северо-западного угла (табл. 2) [3].

Таблица 1

push1.wmf

Таблица 2

push2.wmf

Суммарная стоимость перевозок равна

pu1.wmf (ден. ед.).

Для нахождения оптимального решения используем метод потенциалов [1, 2]. Вычисления обычно выполняются непосредственно в транспортной таблице (табл. 3). Положим pu2.wmf. Поскольку все потенциалы определены, далее вычислим косвенные стоимости pu3.wmf для всех свободных клеток и запишем найденные значения в левом верхнем углу каждой незанятой клетки. В левом нижнем углу записываем разности pu4.wmfдля каждой небазисной переменной pu5.wmf.

Таблица 3

push3.wmf

Определив вводимую в базис переменную pu6.wmf, найдём исключаемую из базиса переменную. Необходимо, чтобы перевозки по маршруту, соответствующему переменной pu7.wmf, уменьшили общую стоимость перевозок. Какой объём груза можно перевезти по этому маршруту? Обозначим через εpu9.wmf количество груза, перевозимого по маршруту (3;1) (т. е. pu11.wmf). Сначала построим замкнутый цикл, который начинается и заканчивается в ячейке, соответствующей вводимой переменной pu12.wmf. Для ячейки (3;1) определим цикл, включающий клетки с базисными поставками: (3;1), (1;1), (1;2), (2;2), (2;4) и (3;4) (табл. 4).

Для перераспределения поставок по найденному циклу необходимо определить минимальный перевозимый груз ε [1]. Чтобы выполнились ограничения по спросу и предложению, надо поочерёдно отнимать и прибавлять величину ε к значениям базисных переменных, расположенных в угловых ячейках найденного цикла (табл. 5).

Искомую величину следует выбирать среди клеток, содержащих знак «минус», т.е.

pu22.wmf.

Переменные pu23.wmf и pu24.wmf обращаются в нуль. Поскольку только одна переменная исключается из базиса, то в качестве исключаемой можно выбрать как pu25.wmf, так и pu26.wmf. Остановим свой выбор на pu27.wmf. Тогда pu28.wmf. Определив значение для вводимой переменной pu29.wmf, и выбрав исключаемую переменную, откорректируем значения базисных переменных, соответствующих угловым ячейкам замкнутого цикла (табл. 6).

Таблица 4

push4.wmf

Таблица 5

push5.wmf

Таблица 6

push6.wmf

Перевозка единицы груза по маршруту (3;1) уменьшает общую стоимость перевозки на pu31.wmf ден. ед. Суммарная стоимость перевозок будет на pu32.wmf ден. ед. меньше, чем в предыдущем решении.

Так как pu33.wmf, то получим

pu34.wmf ден. ед.

Продолжим анализ оптимальности. Вычислим потенциалы нового базисного решения (табл. 7). Новой вводимой в базис переменной будет pu35.wmf. Замкнутый цикл позволяет найти её значение x14=10 и исключаемую переменную pu37.wmf.

Новое решение, представленное в табл. 8, уменьшает значение целевой функции на 40 (ден. ед.). Тогда pu38.wmf ден. ед.

Таблица 7

push7.wmf

Таблица 8

push8.wmf

Теперь для всех небазисных переменных pu39.wmf оценки pu40.wmf. Т.е. выполнился критерий оптимальности на минимум [2]. Таким образом, найденное решение является оптимальным.

pu41.wmf,

pu42.wmf.

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

От элеватора

До мельницы

Количество зерновозов

1

2

5

1

4

10

2

2

10

2

3

15

3

1

5

3

4

5

Суммарная стоимость перевозок pu43.wmf ден. ед.


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

Пушка В.С., Матвеева Т.А., Светличная В.Б., Соколова А.В. УЧИМСЯ МИНИМИЗИРОВАТЬ РАСХОДЫ НА ПЕРЕВОЗКУ // Международный студенческий научный вестник. – 2018. – № 3-1.;
URL: http://eduherald.ru/ru/article/view?id=18226 (дата обращения: 14.06.2021).

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

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