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

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

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

Алгоритм и методы решения транспортной задачи используются при решении некоторых экономических задач, не имеющих отношения к транспортировке грузов. В этом случае величины тарифов a_ij имеют различный смысл в зависимости от конкретной задачи.

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

2. Оптимальные назначения или проблема выбора. Имеется k механизмов, которые могут выполнять l различных работ с производительностью a_ij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности.

3. Задача о сокращении производства с учетом общих расходов на изготовление и доставку продукции.

4. Увеличение эффективности автомобильного транспорта путем уменьшения пустых пробегов, что позволит сократить количество транспортных средств для перевозок за счет повышения их производительности.

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

В общем виде задачу можно представить следующим образом: в т. пунктах производства A₁, A₂, ..., A_m имеется однородный груз в количестве соответственно a₁, a₂,…, a_m. Этот груз необходимо доставить в n пунктов назначения B₁, В₂, …., В_n в количестве соответственно b₁, b₂,..., b_n. Стоимость перевозки единицы груза (тариф) из пункта A_i в пункт B_j равна c_ij.

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

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

Если

то задача называется закрытой. Если

то открытой.

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

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

Оптимальным решением задачи является матрица,

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

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

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

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

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

На предприятии имеются четыре группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков соответственно равно 200, 600, 360, 640 ч. Каждая операция должна выполняться соответственно 400, 500, 240, 260 и 400 ч.

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

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

Заполнение таблицы начинается с клетки (1.1) - северо-западного угла. В нее заносится меньшее из чисел а и b, т.e. X₁₁ = min{a₁;b₁}. Если a > b (a1 <b), то x₁₁ =b₁₁ (X₁₁=а₁) и первый столбец «закрыт» (первая строка «закрыта»), т.е. потребности первого потребителя удовлетворены полностью (предложение первого поставщика полностью исчерпано). Двигаемся далее по первой строке (по первому столбцу), записывая в соседнюю клетку (1.2) (или (2.1)) меньшее из чисел а₁ - b₁, и b₂ (или b₁-a₁ и a₂), т.e. x₁₂ = min{a_{1 –} b₁b₂ }(или x₂₁ = min{b₁ – a₁a₂ }).

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

Таблица 1 – Исходные условия транспортной задачи

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

400 + 500 + 240 + 260 + 400 = 200 + 600 + 360 + 640.

В первую клетку записываем x₁₁ = min {200;400} = 200, первая строка закрыта .

Переходим к клетке (2.1): x₂₁ = min{400- 200;600}=200, первый столбец закрыт. Далее переходим к клетке (2.2): x₂₂ = min{600 - 200;500}=400, вторая строка закрыта. Переходим к клетке (3.2): x₃₂ = min{500-400;360}=100, второй столбец закрыт. Переходим к клетке (3.3): x₃₃ = min{360 -100;240}=240, закрыт третий столбец; x₃₄ = min{360 - 100-240;260}=20, третья строка закрыта; x₄₄ = min {400;640 - 240} = 400. Таблица 2 заполнена.

Таблица 2 – Первый план

Проверим, является ли план, построенный в таблице 2, опорным. Если начать движение от занятой клетки (1.1), вернуться не только в нее, но и в любую другую занятую клетку, двигаясь только по занятым клеткам, невозможно. Следовательно, план является опорным. Он также является и невырожденным, так как содержит точно m+n-1=4+5-1=8 занятых клеток.

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

Опорный план не является оптимальным, что можно доказать с помощью, например, метода потенциалов. После улучшения данного опорного плана в несколько этапов получаем оптимальный вариант (таблица 3) использования производственного оборудования Z = 4*200 + 8*40 + 2*160 + 6*400 + 10*360 + 8*500 + 12*40 + 6*100 = 12520.

Таблица 3 – Оптимальный план

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

Список использованной литературы

1. Зенков, А. В. Методы оптимальных решений : учебное пособие для вузов / А. В. Зенков. — Москва : Издательство Юрайт, 2023. — 201 с. — (Высшее образование). — ISBN 978-5-534-05377-7. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/515509 (дата обращения 23.02.2024).

2. Исследование операций в экономике : учебник для академического бакалавриата / под редакцией Н. Ш. Кремера. — 3-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2017. — 438 с. — (Высшее образование). — ISBN 978-5-9916-9922-8. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/398144 (дата обращения: 10.03.2024).

3. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. — Москва: Дело, 2008