XXI Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Транспортная задача

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Нижегородова Д.С. 1Азарков А.К. 1

---

1 ГУО «Средняя школа №9 г.Могилева»

Жарикова Т.В. 1

---

1ГУО «Средняя школа №9 г.Могилева»

Работа в формате PDF

311.1 KB

Автор работы награжден дипломом победителя I степени

Диплом школьникаСвидетельство руководителя

ВВЕДЕНИЕ

Одиннадцатый класс средней школы – это последний этап школьного образования, когда впору задуматься о выборе профессии.

Начав изучать современный рынок труда, мы обнаружили много новых, ранее неизвестных нам профессий, и среди них специальность «Логистика».

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

Как оказалось, помогает находить оптимальные решения в сфере транспортных затрат «транспортная задача» (ТЗ). Для решения ТЗ сначала строится общая математическая модель, потом производятся необходимые вычисления.

Цель исследовательской работы: рассчитать затраты на доставку товара папка на кнопке, приобретаемого через интернет ресурс.

Для достижения поставленной цели требуется выполнить следующие задачи:

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

2) изучить метод потенциалов как метод нахождения оптимального решения;

3) рассчитать минимальные затраты на перевозку грузов исследуемого объекта.

Объект исследования: маркетплейс, папка на кнопке.

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

Метод исследования: метод потенциалов.

ГЛАВА 1. ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЮ СТОИМОСТИ

1.1 Постановка и математическая модель транспортной задачи

Транспортная задача (ТЗ) по критерию стоимости формулируется следующим образом. В m пунктах отправления А₁, А₂, ..., A_m сосредоточен однородный груз в количествах соответственно а₁, а₂, ..., а_m единиц. Имеющийся груз необходимо доставить потребителям В₁, В₂, ..., В_n, спрос которых выражается величинами b₁, b₂, ..., b_n единиц. Известна стоимость с_ij перевозки единицы груза из i-го пункта отправления ( ) в j-й пункт назначения ( )

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

Для наглядности условие ТЗ удобно представить таблицей 1, такую таблицу принято называть распределительной. Распределительную таблицу иногда называют также табличной или матричной моделью ТЗ. [1 стр 112]

Таблица 1 – Представление транспортной задачи в матричной форме

В таблице 1 x_ij - это количество товара, доставляемого от поставщика к потребителю (т.е. из i-го ( ) пункта отправления в j-й ( ) пункт назначения), а величина с_ij - стоимость доставки единицы груза от i-го поставщика конкретному j-му покупателю.

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

В качестве объекта исследования выбран популярный в настоящее время маркетплейс и товар – папка на кнопке, реализуемая через эту электронную платформу.

Обоснуем, почему через маркетплейс рассматривается доставка именно однородного товара, а не товара от конкретного поставщика конкретному покупателю. Однородным считает товар одинаковый по форме, размеру, цвету, цене и т.д. О том, что Маркетплейс сортирует и доставляет товар как однородный свидетельствует следующее. На сайте у продавца мы заказали одновременно два комплекта папок формата А5, но они отличались ценой и цветом, заказ представлен на рисунке 1.

Рисунок 1. Выбор товара папка на кнопке

На рисунке 1, так же, представлена информация по заказу, а именно доставка ожидается 9-11 октября и склад отгрузки – склад продавца.

Заметим, что вместе с этими папками заказали и папку-уголок, но уже у другого поставщика.

Итак, в корзине 3 товара, два из них от одного поставщика, третий от другого поставщика. Оплата проводилась одной суммой, одномоментно. Сумма платежа 811 российских рубля и товар доставляется в пункт выдачи г.Могилева.

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

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

Рисунок 2. Информация по доставке в ПВЗ

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

1 Выбрали однородный товар папка на кнопке.

2 Поставщиками данного товара являются: ИП поставщик В. А.; – ИП поставщик З. Д.; ИП поставщик Х. Р. (фамилии поставщиков в работе сокращены)

3 Пункты выдачи заказанного товара, указанные покупателями: проспект Мира, 15, заказано папок в количестве 5 штук; проспект Шмидта, 46, заказано папок 1 в количестве 10 штук; улица Ленинская, 83, заказано папок в количестве 6 штук; бульвар Непокоренных, 72, заказано папок в количестве 4 штуки.

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

5 Стоимость доставки груза в пункты выдачи указана условно, потому что это является коммерческой тайной.

Построим распределительную таблицу, введя следующие обозначения:

А1 – ИП поставщик В. А., запас груза составляет 12 штук;

А2 – ИП поставщик З. Д., запас груза составляет 4 штуки;

А3 – ИП поставщик Х. Р., запас груза составляет 9 штук.

Пункты выдачи заказанного товара, указанные покупателями:

В1 – проспект Мира, 15;

В2 – проспект Шмидта, 46, корпус1;

В3 – улица Ленинская, 83;

В4 – бульвар Непокоренных, 72.

Распределительная таблица (матрица) представлена в таблице 2

Таблица 2 – Распределительная матрица объекта исследования

Построим математическую модель ТЗ для объекта исследования.

Экономико-математическая модель ТЗ должна отражать все условия и цель задачи в математической форме.

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

Цель решения ТЗ — минимизировать общие затраты на реализацию плана перевозок, затраты можно представить целевой функцией:

Вывод: математическая модель ТЗ ставится следующая: даны система ограничений и линейная функция. Требуется среди множества решений системы найти такое неотрицательное решение, при котором линейная функция принимает минимальное значение (минимизируется). Будем называть план перевозок X=[x_ij]_m×n допустимым, если он удовлетворяет ограничениям. Допустимый план перевозок, доставляющий минимум целевой функции, называется оптимальным.

1.2 Определение вида транспортной задачи

Установим вид нашей транспортной задачи согласно приложения В.

Сравниваем запасы поставщиков и заказы покупателей, представленных в таблице 2: и . Заключаем, что данная ТЗ обладает закрытой моделью.

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

ГЛАВА 2. МЕТОДЫ ПОСТРОЕНИЯ ИСХОДНОГО ОПОРНОГО ПЛАНА

Решение любой ТЗ содержит три последовательных этапа:

1 Формирование исходного опорного плана;

2 Проверка построенного опорного плана на оптимальность;

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

Этап 1 Построение исходного опорного плана можно проводить по одному из трех методов: метод северо-западного угла, метод минимального элемента, метода Фогеля.

2.1 Метод «северо-западного угла»

Необходимо составить план перевозок товара папка на кнопке от поставщиков A1, A2, А3, у которых запасы составляют соответственно 12, 4, 9 единиц продукции, в пункты выдачи товара B1, В2, В3 и В4 для конечных потребителей (покупателей), потребности которых 5, 10, 6, 4 единиц соответственно, условие задачи представлено в распределительной таблице 2.

Решение. Так как транспортная задача закрытого типа, построение начального опорного плана начнем с верхней левой клетки таблицы («северо-западной» клетки, движение по клеткам осуществляется поступательно слева направо и сверху вниз. При заполнении таблицы приоритетным считается потребности покупателя, которого следует удовлетворить максимально возможным количеством товара.

Из оставшихся пустыми клеток распределительной таблицы опять рассматриваем верхнюю левую клетку (1;2) («северо-западную» клетку), эта клетка соответствует пункту выдачи В2, мы можем поместить туда оставшиеся у поставщика А1 x₁₂=min(7,10)=7 шт товара папка на кнопке. Теперь весь запас товара у поставщика А1 отгружен, и поставщик А1 исключается из рассмотрения.

В результате полной отгрузки заказанного через интернет ресурс товара папка на кнопке получили опорный план перевозок Х₁.

Исходный опорный план, построенный методом северо-западного угла, представлен в таблице 3.

Таблица 3 – Опорный план методом северо-западного угла.

Вывод: суммарные расходы (целевая функция) на перевозку товара при построении начального плана методом северо-западного угла составят 5·7+7·4+3·2+1·7+5·12+4·8=168 ед. Но является ли этот план оптимальным, нельзя ли еще больше снизить транспортные расходы?

2.2 Метод минимального элемента

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

Опорный план является вырожденным, так как число занятых клеток 5, а это меньше, чем m+n-1=6. Сделаем его невырожденным, поместив базисный нуль в клетку с координатами (i.j) – в клетку (2,4) для построения замкнутого цикла.

Таблица 4 – Опорный план методом минимального элемента

Вывод: затраты на доставку груза (целевая функция) при построении плана перевозок (опорного плана) методом минимального элемента составит 6·4+6·15+4·2+5·4+4·8+0·3=174 ед. Эти затраты выше чем при методе «северо-западного» угла.

2.3 Метод Фогеля

Проиллюстрируем метод Фогеля для объекта исследования. Для большей наглядности в таблице 5 поставки x_ij снабжены комментариями с номером этапа, указывающими последовательность загрузки клеток таблицы.

На первом этапе определим разности между двумя наименьшими тарифами в каждой строке и каждом столбце. Максимальные разности находятся в столбцах В3 и В4. Пометим буквой D любую из максимальных разностей, например, столбец В3.

Заполним в столбце В3 клетку с минимальным тарифом (такой является клетка (2;3)), поместив туда x₂₃=min(4,6)=4. В дальнейшем строка А2 в расчет не принимается, так как товар от этого поставщика полностью доставлен в пункт выдачи В3, ставим напротив нее прочерки.

На втором этапе опять определим разности между двумя наименьшими тарифами в каждой строке и каждом столбце. Максимальные разности находятся в строке 1 и в столбцах 1 и 3. Заполним клетку с минимальным тарифом, например, клетку (3,1), поместив туда x₃₁=min(5,9)=5. Так как в пункт выдачи В1 отгружен весь товар, то в дальнейшем клетки столбца 1 в расчет не принимаем. Аналогично заполняем клетки (1,2), (1,4), (3,4) и последнюю клетку (3,3).

В результате получен исходный опорный план X₃, представленный в таблице 5.

Таблица 5 – Опорный план методом Фогеля

Вывод: суммарные расходы на перевозку товара (целевая функция) при построении начального опорного плана методом Фогеля составят 10·4+2·9+4·7+5·4+2·12+2·8=146 ед.

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

ГЛАВА 3. НАХОЖДЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ МЕТОДОМ ПОТЕНЦИАЛОВ

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

Рассчитаем потенциалы. Просматриваем все занятые клетки. Полагаем потенциал U₁=0 и определяем остальные потенциалы из соотношения U_i+V_j=C_ij (i=1..m, j=1..n). Получаем потенциалы U_i: U₁=0; V₂=C_1.2-U₁=4; V₄=C_1.4-U₁=9;
U₃=C_3.4-V₄=-1; V₁=C_3.1-U₃=5; V₃=C_3.3-U₃=13; U₂=C_2.3-V₃=-6. Потенциалы заносим в таблицу 6.

Таблица 6 – Потенциалы

По формуле S_i.j=C_i.j-(U_i+V_j) для всех свободных клеток определим значения оценок: S_1.1=2; S_1.3=2; S_2.1=12; S_2.2=4; S_2.4=0; S_3.2=2.

Так как все оценки S_i.j>=0, то полученный план является оптимальным. Транспортная задача решена.

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

Оптимальный план перевозок получился таким:

– от А1 10 единиц в В2 и 2 единицы в В4;

– от А2 4 единицы в В3;

– от А3 5 единиц в В1, 2 единицы в В3 и 2 единицы в В4.

3.1 Автоматизация решения ТЗ с помощью табличного редактора EXCEL

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

Возникает вопрос, как облегчить расчеты, если выбраны другие пункты выдачи или стоимость доставки поменялась, или изменилось количество товара, заказанного через интернет ресурс?

Оказывается, есть эффективное средство решения оптимизационных задач, им является программная надстройка Поиск решения, которая входит в табличный редактор EXCEL. [4. стр 251]

Надстройка «Поиск решения» доступна на вкладке Данные.

На рисунке 3 представлено размещение распределительной таблицы и ограничений в табличном редакторе.

Мы разместили распределительную таблицу нашего исследуемого объекта в ячейках В2:Е4.

Ячейки В8:Е10 оставили для вывода решения задачи, т.е. в них будет отражаться оптимальный план перевозок выбранного товара в пункты выдачи (решение).

Целевую функцию разместили в ячейке В13, она отражает суммарные затраты на доставку товара.

Ограничения разместили в ячейках С15:Е21.

В ячейках В8:Е10 мы поставили единицы, т.е. от каждого поставщика каждому потребителю поставляется по единице товара. Здесь мы специально не ставили числа из исходного опорного плана, полученного одним их методов: северо-западного угла, минимального элемента или методом Фогеля, чтобы посмотреть на результат решения в EXCEL (рисунок 3).

Рисунок 3. Окно табличного редактора EXCEL

На рисунке 4 представлено заполненное окно параметров поиска решения. Для получения решения надо нажать кнопку «Найти решение» (рисунок 4).

Рисунок 4. Окно параметров поиска решения

После этого на экране отражается сообщение «Решение найдено. Все ограничения и условия оптимальности выполнены». Надо заметить, что результат мы получили за доли секунды.

Результат решения транспортной задачи для объекта исследования (рисунок 5).

Рисунок 5.

Вывод: Поиск решения действительно универсален. Результат получен за минимальное время, подготовка таблицы заняла максимум 10 минут. Конечно, целевую функцию и систему ограничений мы определили заранее. И результат применения функции Поиск решения такой же, как и при применении метода потенциалов для начального опорного плана.

Оптимальный план по перевозке товара, проверенный методом потенциалов, совпал с решением ТЗ в табличном редакторе Excel, при этом затраты на доставку груза составили 146 ед.

ЗАКЛЮЧЕНИЕ

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

Первоначально минимальные затраты (целевая функция) на перевозку товара по методу «северо-западного угла» составили 168 единиц, на перевозку товара по методу минимального элемента составили 174 единицы, а по методу Фогеля 146 единиц.

В ходе применение метода потенциалов мы получили оптимальный план решения данной задачи для объекта исследования.

Специфические особенности ТЗ позволяют успешно решать задачи с большим числом переменных. Метод потенциалов позволяет решать ТЗ, последовательно переходя от одного (опорного) решения к другому, а проблему построения исходного плана перевозок решают методы: «северо-западного» угла, минимального элемента и Фогеля. А если мы используем табличный редактор EXCEL и его надстройку Поиск решения, то можно первоначально поставить любые числа, в том числе и ноль.

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Костевич, Л.С. Математическое программирование: Информ. технологии оптимальных решений: учебное пособие / Л.С. Костевич. – Минск: Новое знание, 2003. – 424 с.: ил.

2. Кузнецов, А.В. Сборник задач и упражнений по высшей математике: Мат. программирование: учебное пособие / А.В. Кузнецов, В.А. Сакович, Н.И. Холод; под редакцией А.В. Кузнецова. –– 2-е издание, перераб. и доп. – Минск: Выш. шк., 2002. – 447 с.: ил.

3. Конюховский П.В. Экономическая информатика / П.В.Конюховский, Д.Н. Колесова – СПб: Питер, 2001. – 560 с.: ил.