Презентация на тему Транспортная задача, её модификации

перевозок однородного продукта из пунктов наличия в пункты потребления

на транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе.

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача, определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом.

Классическую транспортную задачу можно решить симплекс-методом , но в силу ряду особенностей её можно решить проще(для задач малой размерности)

в объемах а1,а2,а3,… am.
Данный груз необходимо доставить n
потребителям в

объемах b1,b2,…bn.
Нам известны Сij i=1,2,…m; j=1,2,…n —
стоимости перевозки единиц груза от каждого i поставщика j-му
потребителю(переменные транспортной задачи)
Требуется составить такой план перевозок, при котором запасы всех поставщиков
вывозятся полностью, запросы всех потребителей удовлетворяются полностью,
и суммарные затраты на перевозку всех грузов являются минимальными.

Исходные данные записываются в таблицу

i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому

j-му потребителю.
Эти переменные могут быть записаны в виде матрицы перевозок:

Так как произведение Cij*Xij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:

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

Система ограничений задачи состоит из двух групп уравнений.

Учитывая условие неотрицательности объемов перевозок математическая модель выглядит следующим образом:

переменные задачи (матрицу перевозок):
2. Записываем матрицу стоимостей:
3. Целевая функция

задачи равняется сумме произведений всех соответствующих элементов матриц C и X.

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

4. Составим систему ограничений задачи.
Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика:

Это означает, что запасы поставщиков вывозятся полностью.

матрицы X, должны быть равны запросам соответствующих потребителей:
Это означает,

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

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

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

перевозок взаимозаменяемых видов продукции. Такой вопрос следует решать как единую задачу, так как в ней различные продукты могут приравниваться друг к другу через переводные коэффициенты. Решение задачи данной модели не имеет принципиальных отличий от решения закрытой однопродуктовой задачи.
Вариант транспортной задачи, в которой присутствует несколько продуктов (пункты могут производить/потреблять несколько продуктов). Для некоторых дуг задается ограничение на пропускную способность (без этого ограничения задача распадается на отдельные задачи по продуктам).
Данная задача может быть решена симплекс- методом

Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.
Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

из способов решения задачи является метод минимального (наименьшего) элемента. Его

суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями.[3]
Алгоритм:
Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.
Проверяются строки поставщиков на наличие строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Нахождение опорного плана. Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента», двойного предпочтения и аппроксимации Фогеля.
Метод северо-западного угла (диагональный или улучшенный) а каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из Ai или полностью удовлетворяется потребность Bj.

После нахождения опорного плана перевозок, нужно применить один из алгоритмов его улучшения, приближения к оптимальному.
Метод падающего камня (нем.)
Метод потенциалов.

пункты производства находятся в верхней доле, а пункты потребления —

в нижней. Пункты производства и потребления попарно соединяются рёбрами бесконечной пропускной способности и цены за единицу потока .
К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.
Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.
Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда — Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана — Форда. При возврате потока стоимость считается отрицательной.
Алгоритм «mincost maxflow» можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма «mincost maxflow» происходит не более чем за  операций. ( — количество рёбер,  — количество вершин.) При случайно подобраных данных обычно требуется гораздо меньше — порядка  операций.
При решении несбалансированной транспортной задачи применяют приём, позволяющий сделать ее сбалансированной. Для этого вводят фиктивные пункты назначения или отправления. Выполнение баланса транспортной задачи необходимо для того, чтобы иметь возможность применить алгоритм решения, построенный на использовании транспортных таблиц.