Меню

Циклы в транспортной таблице Свойства циклов

Транспортная задача — решение методом потенциалов

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

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

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

Теоретический материал по транспортной задаче

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

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

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

где: Z — затраты на перевозку грузов;

X — объем груза;

C — стоимость (тариф) перевозки единицы груза;

A — запас поставщика;

B — запрос потребителя;

m — число поставщиков;

n — число потребителей.

Общий план решения транспортной задачи методом потенциалов

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

Суть его в следующем: находим некий опорный план и проверяем его на оптимальность (Z → min). Если план оптимален — решение найдено. Если нет — улучшает план столько раз, сколько потребуется, пока не будет найден оптимальный план.

Ниже приведен алгоритм решения транспортной задачи в самом общем виде:

  1. Построение транспортной таблицы.
  2. Проверка задачи на закрытость.
  3. Составление опорного плана.
  4. Проверка опорного плана на вырожденность.
  5. Вычисление потенциалов для плана перевозки.
  6. Проверка опорного плана на оптимальность.
  7. Перераспределение поставок.
  8. Если оптимальное решение найдено, переходим к п. 9, если нет — к п. 5.
  9. Вычисление общих затрат на перевозку груза.
  10. Построение графа перевозок.

Подробная инструкция по решению транспортной задачи

1. Построение транспортной таблицы

Заполняем транспортную таблицу с исходными данными, где указываем запасы материалов, имеющиеся на складах поставщиков (Ai), и потребности заводов (Bj) в этих материалах.

В нижний правый угол ячеек таблицы заносим значение тарифов на перевозку груза (Cij).

2. Проверка задачи на закрытость

Обозначим суммарный запас груза у всех поставщиков символом A, а суммарную потребность в грузе у всех потребителей — символом B.

Транспортная задача называется закрытой, если A = B . Если же A ≠ B , то транспортная задача называется открытой. В случае закрытой задачи от поставщиков будут вывезены все запасы груза, и все заявки потребителей будут удовлетворены. В случае открытой задачи для ее решения придется вводить фиктивных поставщиков или потребителей.

Проверим задачу на закрытость:

A = 10 + 20 + 30 = 60.

B = 15 + 20 + 25 = 60.

A = B, следовательно данная транспортная задача — закрытая.

3. Составление опорного плана

Составляет предварительный (опорный) план перевозок. Он не обязательно должен быть оптимальный. Это просто своеобразный «черновик» или «набросок», итерационно улучшая который мы постепенно придем к оптимальному плану.

Есть разные методы нахождения опорного плана. Наиболее распространены следующие:

Суть метода проста — ячейки транспортной таблицы последовательно заполняются максимально возможными объемами перевозок, в направлении сверху вниз и слева направо. То есть сперва заполняется самая верхняя левая ячейка («северо-западная» ячейка), потом следующая справа и т. д. Затем переходят на новую строку и вновь заполняют ее слева направо. И так пока таблица не будет заполнена полностью.

Подробное описание метода и пример можно посмотреть здесь.

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

Подробное описание метода и пример можно посмотреть здесь

Основа метода в нахождении разности (по модулю) между парой минимальных тарифов в каждой строке и столбце. Затем в строке или столбце с наибольшей разностью заполняется клетка с наименьшим тарифом. Затем все эти действия повторяются заново, только при этом уже не учитываются заполненные клетки.

Подробное описание аппроксимации Фогеля и пример можно посмотреть здесь

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

Подробное описание метода и пример можно посмотреть здесь

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

4. Проверка опорного плана на вырожденность

Клетки таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а остальные (пустые) — свободными.

Читайте также:  Таблица размерные признаки женской типовой фигуры

План называется вырожденным, если количество базисных клеток в нем меньше, чем m + n — 1. Если во время решения задачи получился вырожденный план, то его необходимо пополнить, проставив в недостающем числе клеток нулевую перевозку и превратив, тем самым, эти клетки в базисные (общий баланс и суммарная стоимость перевозок плана при этом не изменятся).

Проводить пополнение плана, выбирая клетки произвольно, нельзя. План должен быть ациклическим!

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

Ломаная линия может иметь точки самопересечения, но не в клетках цикла.

В нашем примере количество базисных клеток = 5; m + n — 1 = 3 + 3 — 1 = 5.

Следовательно, первоначальный план перевозок — невырожденный (5 = 5).

5. Вычисление потенциалов для плана перевозки

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

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

Итак, сопоставим каждому поставщику Ai и каждому потребителю Bj соответствующие величины Ui и Vj так, чтобы для всех базисных клеток плана было выполнено следующее соотношение: Ui + Vj = Cij.

Добавим к транспортной таблице дополнительную строку и столбец для Ui и Vj.

Предположим, что U1 = 0.

Тогда мы сможем найти V3 = C13 — U1 = 1 — 0 = 1.

Зная V3, мы теперь можем найти U3:

По аналогии вычисляем все оставшиеся потенциалы:

6. Проверка плана на оптимальность методом потенциалов

Для каждой свободной клетки плана вычислим разности ΔCij = Cij — (Ui + Vj ), и запишем полученные значения в левых нижних углах соответствующих ячеек.

План является оптимальным, если все разности ΔCij ≥ 0.

В данном случае план — неоптимальный (ΔC22 граф . Вершинами графа будут «склады» и «магазины». В вершинах укажем соответствующие объемы запасов и потребностей. Дугам, соединяющим вершины графа, будут соответствовать ненулевые перевозки. Каждую такую дугу подпишем, указав объем перевозимого груза.

В результате получится граф, аналогичный изображенному ниже:

Все, транспортная задача решена. Поздравляю!

Практическое применение транспортной задачи

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

  • оптимизация поставок сырья и материалов на производственные предприятия;
  • оптимизация доставок товаров со складов в розничные магазины;
  • оптимизация пассажирских перевозок.

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

  1. Галяутдинов Р. Р. Конспект лекций по логистике
  2. Решение транспортной задачи в 1С: Предприятие 8.2 // Волшебный форум (@romix). URL: http://kb.mista.ru/article.php?id=859 (дата обращения: 29.10.2013)
  3. Транспортная задача // Википедия. URL: http://ru.wikipedia.org/wiki/Транспортная_задача (дата обращения: 29.10.2013)

© Копирование любых материалов статьи допустимо только при указании прямой индексируемой ссылки на источник: Галяутдинов Р.Р.

Источник

Циклы в транспортной таблице. Свойства циклов.

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

Графическим изображением цикла является замкнутая ломаная линия (контур), звенья которой расположены только в строках и столбцах таблицы. Каждое звено соединяет две и только две соседние клетки цикла. Вершины цикла помечаются знаками «+» и «-» поочередно, начиная со свободной клетки.Таким образом, план ТЗ является опорным тогда и только тогда, когда из занятых им m+n-1 клеток нельзя образовать ни одного цикла.

25. Способы построения начального опорного плана ТЗ (Наименьшего Эл-та, северо-западного угла, Фогеля)

Опорный план можно построить несколькими способами.

Правило «северо-западного угла». Суть состоит в том, что первой загружается левая верхняя клетка (1.1).а затем двигаемся от нее по строке вправо или по столбцу вниз. В клетку (1.1) занесем меньшее из чисел а1, в1. Если закрывается строка, то следующей загружается клетка (2.1); если же закрывается столбец, то следующей загружается клетка (1.2). Итак, каждый раз загружается клетка, соседняя либо по строке, либо по столбцу. Последней будет загружена клетка (m;n). В результате загруженные клетки расположатся вдоль диагонали (1;1) – (m;n), поэтому способ «северо-западного угла» называют еще диагональным способом.

Способ « минимального элемента». Суть: первой в таблице загружается клетка с наименьшим тарифом. В клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответств-ю поставщику, запасы которого полностью израсходованы, или столбец, соответств-й потребителю, спрос которого полностью удовлетворен. Из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать m+n-1 загруженых клеток. В процессе заполнения таблицы могут быть одновременно исключены строка или столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос ( вырожденная задача). В этом случае в свободные клетки надо записать число 0 – «нуль-загрузку», условно считая такую клетку занятой. Однако число 0 записывается в те свободные клетки, к-рые не образуют циклов с ранее занятыми клетками.

Метод « Фогеля». Суть: по строкам и столбцам определяется разность между двумя наименьшими тарифами. Из этих разностей выбирается наибольшая и в соответствующей строке (столбце) загружется клетка с наименьшим тарифом. Закрывающаяся строка (столбец) исключ-ся из дальнейшего рассмотрения. Описанная операция повторяется m+n-1 раз. Если наибольшая разность окаж-ся сразу в нескольких строках (столбцах), то выбир-т ту строку (столбец), в к-рой придется загружать клетку с наименьшим тарифом. Если и эти показатели будут одинаковы, то выбирают клетку, в к-рую придется записать большую поставку.

26, 27, 28. Признак оптим-ти опорного плана. Оценка свободной клетки трансп.таблицы. процедура преобраз-я опорного плана ТЗ в новый опорный план.

В соответствии с теорией двойственности, если xij*=0, то ui+vj

— наз-ся оценкой свободной клетки и ее величина показ-т, как измен-ся общая ст-ть перевозок, если по маршруту (ij) провести единицу груза. Таким образом признаком оптимальности опорного плана ТЗ является неотрицательность оценок свобод.клеток. если среди оценок есть отриц-ые, то чтобы уменьшить общую ст-ть перевозов нужно загрузить первую очередь клетку с наибольшей по модулю отрицательной оценкой. Такую клетку наз-ют перспективной. Если в распределит-ой таблице, содержащей оптим.план, имеются свободные клетки с нулевыми оценками, то задача имеет не единственный оптим.план. Загружая свободную клетку с нулевой оценкой, можно найти еще один оптим.опорный план. И так для каждой свободной клетки с нулевой оценкой.

Чтобы осуществить переход от одного опорного плана к другому необходимо загрузить перспективную клетку. Для этой клетки составляется цикл. Нужно доказать, что для каждой свободной клетки трансп.таблицы, содержащей опорный план, сущ-ет цикл, причем только единственный. Вершины цикла помечаются знаками «+» и «-» поочередно, начиная со свободной клетки. Далее выбир-ся наименьшая из загрузок клеток, отмеченная «-». Она обозначается

Источник



Алгоритм пересчета транспортной таблицы

Шаг 1. Выбрать свободную клетку (r, s), соответствующую наибольшей положительной оценке

.

Шаг 2. Для выбранной свободной клетки (r, s) построить цикл пересчета – это замкнутая ломаная, одна из вершин которой находится в данной свободной клетке, а все остальные – в занятых клетках, соседние звенья взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы. Цикл пересчета всегда состоит из четного числа вершин.

Шаг 3. Клетку (r, s) пометить знаком «плюс», далее соседние вершины цикла пересчета пометить по очереди знаками «минус», «плюс».

Шаг 4. Из поставок, отмеченных знаком «минус», выбрать минимальную – ρ.

Шаг 5. Перейти к новому базисному допустимому решению:

1) к поставкам, отмеченным знаком «плюс», добавляется ρ,

2) из поставок отмеченных знаком «минус», вычитается ρ.

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

Пример №5.1.

Однородный продукт, находящийся в трех пунктах производства (m=3), необходимо доставить в четыре пункта потребления (n=4). При этом матрица транспортных затрат на перевозку единицы продукта из любого пункта отправления в любой пункт назначения, вектор объемов запасов продукта в пунктах производства и вектор объемов продукта, необходимых пунктам потребления, имеют вид:

Решение.

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

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

единиц.

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

Шаг 2. По правилу «северо-западного угла» определяется первое допустимое решение:

Шаг 3.Оценки базисных клеток транспортной таблицы равны нулю.

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

Первая транспортная таблица и потенциалы имеют вид:

Шаг 4. По формуле (5.6) вычисляются оценки всех свободных клеток:

, , ,

, , ,

, .

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

Шаг 6. В соответствии с алгоритмом пересчета транспортной таблицы выбираетсясвободная клетка (r, s), соответствующая наибольшей положительной оценке

Для выбранной свободной клетки (14) строится цикл пересчета: 14-13-23-24.

Клетка (14) помечается знаком «плюс», далее соседние вершины цикла пересчета помечаются по очереди знаками «минус», «плюс». Выбирается минимальная из поставок, отмеченных знаком «минус» , и к поставкам, отмеченным знаком «плюс», добавляется ρmax, а из поставок отмеченных знаком «минус», вычитается .

Производится перераспределение поставок вдоль цикла пресчета:

* ® ®

Получается второе базисное допустимое решение. Далее необходимо вычислить новые потенциалы, полагая :

Вторая транспортная таблица и потенциалы имеют вид:

Оценки всех свободных клеток таблицы равны:

, , ,

, , ,

, .

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

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

Шестая транспортная таблица и потенциалы имеют вид:

Оценки всех свободных клеток таблицы равны:

, , ,

, ,

, ,

.

Все .

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

Ответ.

Оптимальный план перевозки имеет вид:

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

Дата добавления: 2016-04-02 ; просмотров: 893 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Источник

Тема 10. Транспортные задачи. Блокирование перевозок.

Если план транспортной задачи Х= является оптимальным, то ему соответствует система чисел, называемых потенциалами, для которых выполняются следующие условия

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

Цикл в транспортной задаче – это

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

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

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

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

Если число занятых клеток меньше, чем (m+n-1), то одну свободную клетку делают занятой с нулевой перевозкой. Эта клетка

— должна образовывать цикл с вершинами только в занятых клетках

+ не должна образовывать цикл с вершинами только в занятых клетках

— должна образовывать цикл с вершинами только в свободных клетках

— может быть любой свободной клеткой

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

— не зависит от и

Потенциалами транспортной задачи размерности (m×n) называются m+n чисел ui и vj, для которых выполняются условия

— ui+vj=cij для первых двух столбцов распределительной таблицы

— ui+vj=cij для первых двух строк распределительной таблицы

Оценками транспортной задачи размерности (m+n) называются числа γij=cij-ui-vj, которые вычисляются

— для занятых клеток

+для свободных клеток

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

— для первых двух столбцов распределительной таблицы

Целевая функция транспортной задачи имеет вид

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

— расположенные по главной диваглнали распределительной таблицы

— с максимальными тарифами

+ с минимальными тарифами

— расположенные в первых строках и столбцах распределительной таблицы

При решении транспортной задачи значение целевой функции должно от итерации к итерации

— увеличиваться или не меняться

— увеличиваться на γij

+уменьшаться или не меняться

В клетках распределительной таблицы располагаются

— только тарифы перевозок cij

— только планы перевозок xij

+планы перевозок xij и соответствующие тарифы cij

Если план транспортной задачи X=(xij)mxn является оптимальным, то оценки γij=cij-ui-vj удовлетворяют условиям

— γij 0 для всех клеток

— γij 0 для всех клеток

— коэффициенты прямых затрат

— коэффициенты полных затрат

+ стоимость перевозки одной тонны груза от i–ого поставщика к j–ому потребителю

— общая стоимость перевозки от i–ого поставщика к j–ому потребителю

В целевой функции транспортной задачи переменные xij – это

— коэффициенты полных затрат

— коэффициенты прямых затрат

+ объем перевозимого груза от i–ого поставщика к j–ому потребителю

В транспортной задаче сумма потенциалов ui+vj равна тарифу cij, , для

— для любых клеток

— для первого ряда клеток

В транспортной задаче оценки γij вы числяются для

— для всех клеток

+ для незанятых клеток

—для клеток первого столбца

В транспортной задаче

— максимизируется объем перевозок

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

— минимизируется общий объем перевозок

— минимизируется объем холостого пробега транспорта

Экономически отрицательная оценка показывает что, если в клетку перебросить 1т груза, то суммарная стоимость перевозки

—уменьшится на 2

Оценки транспортной задачи, вычисляемые для свободных клеток, находятся по формуле

Блокирование перевозок применяется для клетки , в которой

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

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

Если число загруженных клеток в плане транспортной задачи меньше m+n-1, то план называется

Блокирование перевозок применяется в транспортной задаче с открытой моделью. Если , то накладывается дополнительное условие, что груз i – го поставщика должен

+быть вывезен полностью

—частично остаться на складе

—не вывозиться совсем

—быть отправлен только j –му потребителю

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

—должны удовлетворятся полностью только i – м поставщиком

Если плану транспортной задачи соответствует система m+n чисел (потенциалов), для которых выполняются условия для и для , то план называется

В транспортной задаче для плана, приведенного в таблице

А\В
-2
-4

неоптимальной клеткой будет

Если план транспортной задачи вырожденный, то число загруженных клеток

В транспортной задаче для плана, приведенного в таблице

А\В
-3

неоптимальной клеткой будет

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

—дополнительный потребитель с тарифами, равными 1

+фиктивный потребитель с тарифами, равными 0

—фиктивный поставщик с тарифами, равными 0

— фиктивный поставщик с тарифами, равными 1

План транспортной задачи называется вырожденным, если число занятых клеток

Дан план транспортной задачи и вычислены потенциалы:

А\В
-1
-3

Данный план является

Дана транспортная задача:

с открытой моделью. После приведения к закрытой модели она примет вид

А\В
А\В

Дана транспортная задача:

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

А\В
А\В

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

— фиктивных поставщика и потребителя

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

Источник