Решение транспортной задачи методом потенциалов c

Решение транспортной задачи методом потенциалов c

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

Например, у нас есть сеть розничных магазинов, которым требуется определенное количество товаров. Также имеется ряд складов поставщиков, где требуемые товары хранятся. При этом на каждом складе различный объем запасов этих товаров. Кроме этого нам известны тарифы – затраты на перевозку 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. Вычисление потенциалов для плана перевозки

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

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

Итак, сопоставим каждому поставщику 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 7. Перераспределение поставок

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

Отметим ячейку с отрицательной разностью ΔCij знаком «+», следующую знаком «-», и так далее, поочередно.

Затем находим минимальной значение груза в ячейках цикла имеющих знак «-» (здесь это 5) и вписываем его в свободную ячейку со знаком «+». Затем последовательно обходим все ячейки цикла, поочередно вычитая и прибавляя к ним минимальное значение (в соответствии со знаками, которыми эти ячейки помечены: где минус — вычитаем, где плюс — прибавляем).

Читайте также:  Слот для карты триколор в телевизоре

Получим новый опорный план перевозок:

Так как базисных клеток стало больше, чем m + n – 1, то базисную клетку с нулевым значением делаем свободной:

Снова вычисляем значения потенциалов и разности ΔCij:

На этот раз все разности ΔCij ячеек положительные, следовательно, найдено оптимальное решение.

8. Если оптимальное решение найдено, переходим к п. 9, если нет – к п. 5.

У нас оптимальное решение найдено, поэтому переходим к пункту 9.

9. Вычисление общих затрат на перевозку груза

Вычислим общие затраты на перевозку груза (Z), соответствующие найденному нами оптимальному плану, по формуле:

Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 ден. ед.

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

10. Построение графа перевозок

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

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

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

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

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

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

Пригодилась статья? Поделитесь с друзьями:

Библиографическая запись для цитирования статьи по ГОСТ Р 7.0.5-2008:
Галяутдинов Р.Р. Транспортная задача — решение методом потенциалов // Сайт преподавателя экономики. [2013]. URL: http://galyautdinov.ru/post/transportnaya-zadacha (дата обращения: 26.12.2019).

Нашли опечатку? Помогите сделать статью лучше! Выделите орфографическую ошибку мышью и нажмите Ctrl+Enter.

ФОРМУЛЫ —> ТЕРМИНЫ —> БУХУЧЕТ —> НАЛОГИ —> СТАТИСТИКА —> БИОГРАФИИ —> ЗАДАЧИ —> ENGLISH —>

ГАЛЯУТДИНОВ
Руслан Рамилевич

старший преподаватель экономических дисциплин (маркетинг, логистика, рынок ценных бумаг). подробнее

    Типы рыночных структур: совершенная конкуренция, монополистическая конкуренция, олигополия и монополия

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

если известен потенциал v., и

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

и те из них, которые больше нуля, записывают в левые нижние углы клеток. Если для всех свободных клеток Д1;

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

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

100 200 300 400

2 3 4 5 200 100

  • 3 4 8 7
  • 300

Напомним, что запасы фиктивного поставщика должны вывозиться в последнюю очередь (ноль не является наименьшим тарифом).

Наименьшим элементом в матрице С является си = 1, поэтому на первом шаге заполним клетку с номером (1, 1). min t = 200; b <= 100> = 100. Объем перевозки от первого поставщика первому потребителю х11 = 100. Исключается из рассмотрения первый потребитель. Дальнейший порядок заполнения таблицы и исключения из рассмотрения поставщиков или потребителей показаны на матрице С.

Полученное решение Х1 имеет ш+и — 1=4 + 41=7 базисных переменных. Опорное решение является вырожденным, так как одна из его координат равна нулю. Вычислим значение целевой функции на этом опорном решении

3. Проверяем опорное решение на оптимальность. Для этого необходимо найти потенциалы поставщиков и потребителей и оценки для свободных клеток таблицы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равняется стоимости + zi = ctj при xtj > 0). Записываем систему уравнений для нахождения потенциалов:

Система состоит из семи уравнений и имеет восемь неизвестных. Система неопределенная. Одному из потенциалов задаем значение произвольно, пусть и1 = 0. Остальные потенциалы находятся однозначно:

Значения потенциалов записываем рядом с запасами или запросами соответствующих поставщиков и потребителей в таблицу (табл. 14.15).

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

Вычисляем оценки Д.. для всех незаполненных клеток таблицы (для всех базисных клеток всегда Д„ = 0).

Положительные оценки записываем в левые нижние углы соответствующих клеток таблицы, на место отрицательных просто ставим знак «-».

Начальное опорное решение не является оптимальным, так как имеются положительные оценки.

4. Переход к новому опорному решению. Возможна упрощенная схема перехода к новому опорному решению. По этой схеме находится клетка с наибольшей положительной оценкой. В данном примере тах<Д(;.> = тах <1, 3, 2>= 3 для клетки (3, 1). Для такой клетки находят цикл, означивают его, и производят сдвиг по циклу (перераспределение груза). В клетки, отмеченные знаком = -1 ? 0 = 0.

Для клетки (3, 1) цикл (3, 1)(+), (1, 1)( ), (1,4)(+), (3, 3)(-). Разность сумм тарифов равняется (3 — 1 + 2 — 7) = -3. Максимальный для перераспределения груз

Приращение целевой функции AZ(3 = -3 ? 199 = -399.

Для клетки (3, 2) цикл (3, 2)(+), (2, 2)(-), (2, 3)(+), (4, 3)(-), (4, 4)(+), (4, 3)(-) (см. табл. 15.15). Разность сумм тарифов равняется (4-3 + 4 + 9- 9-7) = -2. Максимальный для перераспределения груз

Приращение целевой функции AZ(3 2) = -2 • 299 = -499.

Находим min <0, -300, -400>= -400. Следовательно, наибольшее уменьшение целевой функции будет достигнуто при перемещении груза 0 = 200 ед. в клетку (3, 2). Осуществляем сдвиг по этому циклу.

Получаем второе опорное решение Х2 (табл. 14.16). Значение целевой функции равняется

Данное значение согласуется с предыдущими расчетами

Для проверки на оптимальность Х2 находим потенциалы поставщиков и потребителей и оценки для свободных клеток таблицы. Они вычислены устно и находятся в табл. 14.16. Опорное решение Х2 не является оптимальным, так как оценки для клеток (2, 4) и (3, 1) Д94 = 1 и Д31 = 3 положительные. Определяем, в какой из двух клеток увеличение объема перевозимого груза приведет к большему уменьшению стоимости перевозимых грузов.

Для клетки (2, 4) цикл (2,4)(+), (3, 4)(-), (3, 2)(+), (2, 2)(-). Разность сумм тарифов равняется (5 — 7 + 4 — 3) = -1. Максимальный для перераспределения груз

Приращение целевой функции AZ(3 ^ = -1-0 = 0.

Для клетки (3,1) цикл (3, 1)(+), (1, 1)(-), (1, 4)(+), (3, 4)(-) (см. табл. 14.16). Разность сумм тарифов равняется (3 — 1 + 2 — 7) = -3. Максимальный для перераспределения груз

Приращение целевой функции AZ(3 9) = -3 ? 100 = -300. Осуществляем сдвиг по этому циклу на величину 0 = 100. Получаем третье опорное решение (табл. 14.17).

Значение целевой функции равняется

Данное значение согласуется с предыдущим расчетом (ДZ(3 2) = = -300)

Для проверки на оптимальность Х3 находим потенциалы поставщиков и потребителей и оценки для свободных клеток таблицы. Они вычислены устно и находятся в табл. 14.17. Опорное решение Х3 не является оптимальным, так как оценка для клетки (4, 3) Д43 = 1 положительная.

Для клетки (4, 3) цикл (4, 3)(+), (2, 3)(-), (2, 2)(+), (3, 2)(-), (3, 1)(+), (1, 1) (-), (1, 4)(+), (4, 4)(-) (см. табл. 14.17). Разность сумм тарифов равняется (0-4 + 3- 4 + 3- 1 + 2 — 0) = -1. Максимальный для перераспределения груз

Приращение целевой функции AZ(4 = —1-0 = 0.

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

Перемещаем базисный нуль из клетки (1, 1) в клетку (4, 3). Получаем новое четвертое опорное решение Х4. Потенциалы поставщиков и потребителей и оценки для свободных клеток приведены в табл. 14.18.

Решение является оптимальным, так как все оценки неположительные. Значение целевой функции Z(XA) = 2700.

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

Для описания алгоритма используем формульно-словесный способ. Рассмотрим пример транспортной задачи (табл. 2.2).

Исходная транспортная матрица

В табл. 2.2 по строкам матрицы представлены пункты (станции) отправления от А1 до А4 и объемы погрузки в тоннах — 100, 150, 90, 30 т, а по столбцам — пункты (станции) назначения от В1 до В5 и объемы выгрузки — 40, 80, 110, 50, 90 т. Данная транспортная задача является сбалансированной (ai = bj = 370 т), поэтому добавлять фиктивного потребителя ФВ или фиктивного поставщика ФА не требуется. На пересечении строк и столбцов в клетках матрицы в маленьких квадратиках записаны показатели критерия оптимальности транспортной задачи, например, затраты на перевозку единицы груза или кратчайшие расстояния между соответствующими пунктами (станциями) погрузки и выгрузки. Расстояние между станцией погрузки А1 и станцией выгрузки В1, как следует из матрицы, равно 10 (или 100, 1000 и т. д.) км, потом — 9, 8, 5 км и т. д. Тогда целью, решения задачи явится отыскание совокупности объемов перевозок между всеми пунктами (станциями) погрузки и выгрузки (корреспонденций), обеспечивающей минимальный объем перевозочной работы (грузооборота) в тонно-километрах. Любую совокупность корреспонденций, обеспечивающую весь объем перевозок, будем называть планом, а совокупность, обеспечивающую минимум грузооборота, — оптимальным планом перевозок.

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

Операция 1. Построение опорного плана.

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

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

Берем «северо-западную» клетку матрицы — это клетка А1В1 и записываем в нее максимально возможную поставку — 40 т (объем выгрузки 40 т, ресурсы станции погрузки 100 т). Поскольку ресурсы станции погрузки А1 не исчерпаны, следуем по первой строке вправо и записываем в клетку А1В2 корреспонденцию равную максимально возможной величине — 60 т. Таким образом получается, что ресурсы станции А1полностью использованы, однако спрос станции выгрузки В2 не удовлетворен. Тогда от клетки А1В2 опускаемся вниз до клетки А2В2 и записываем в нее поставку равную 20 т. Описанным способом следуем далее до последней «юго-западной» клетки матрицы. В результате получаем допустимый план перевозок груза. Грузооборот или функционал транспортной задачи (сумма произведений корреспонденций на расстояние, рассчитанная по табл. 2.3) составит:

Fсев-зап. = 40 • 10 + 60 • 9 + 20 • 7 + 110 • 13 + 20 • 6 + 30 • 7 + 60 • 1 + + 30 • 2 = 2960 ткм [см. формулу (2.4)].

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

где m — количество строк, n — количество столбцов, Nбаз — количество базисных клеток.

Другими словами, количество клеток матрицы, содержащих корреспонденции, должно быть равно сумме строк и столбцов без единицы. В нашем случае это условие соблюдается: 8 = 4 + 5 — 1. План транспортной задачи, отвечающий условию (n + m — 1) называют базисным. Базисными также называются клетки матрицы, содержащие поставки. Клетки, в которых поставки отсутствуют, называются небазисными.

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

Наиболее предпочтительным при ручном решении транспортных задач считается метод минимальной стоимости или, как его еще называют, метод наименьшего элемента в матрице. Суть его в следующем. В транспортной матрице выбирается клетка с минимальной стоимостью (расстоянием). В нашем случае это клетка А3В5. В нее записывается максимально возможная поставка — это 90 т (табл. 2.4).

Метод наименьшего элемента в матрице

Далее отыскиваются клетка, имеющая следующее по величине расстояние. В нашей матрице это две клетки с расстоянием 2 км в пятом столбце. Однако в эти клетки поставки корреспонденцию грузов ставить нельзя, поскольку спрос станции В5 полностью удовлетворен со станции А3. Поэтому столбец 5 из дальнейшего построения плана исключаем. Следующие по величине показателя критерия оптимальности клетки с расстоянием 4 км это клетки А2В1 и А4В2. Выбираем одну из них, например, А2В1 и записываем в нее поставку 40 т. Далее идет клетка А4В2 — поставка 30 т, потом А1В4 — 50 т, А2В2 — 50 т. Все оставшиеся ресурсы по станциям погрузки распределяем между клетками третьего столбца в клетки А1В3 и А2В3. После составления опорного плана во избежание ошибок целесообразно проверить балансы погрузки, выгрузки и суммы корреспонденций по строкам и по столбцам матрицы. Функционал F плана, составленного методом наименьшей стоимости, равен 2150 ткм. Таким образом, построенный план значительно лучше плана, построенного методом северо-западного угла. Однако число базисных клеток в плане — 7. Это не соответствует условию (2.5), т. е. меньше требуемого на единицу. Такой план математики назвали вырожденным (случай вырождения). Случай вырождения «лечат» путем введения в матрицу недостающего количества базисных клеток с нулевыми поставками. Нулевую поставку необходимо вводить в матрицу рядом с базисной клеткой, которая обусловила «пропажу» базисной клетки.

Для того чтобы понять, почему «пропадают» поставки, обратимся к методу северо-западного угла. Из табл. 2.3 следует, что как только была заполнена «северо-западная» клетка, рядом с ней сразу появляется соседняя базисная клетка, потом еще одна и т.д. Цепочка базисных клеток без разрыва следует до «юго-восточного угла» матрицы. Однако если бы в этой цепочке появилась клетка, связывающая поставщика и потребителя с равными объемами погрузки и выгрузки, и в нее была бы записана такая же поставка, то это привело бы к пропаже базисной клетки. Описанная ситуация имела место в табл. 2.4, когда в клетку А3В5была введена корреспонденция объемом 90 т, равная объемам погрузки и выгрузки по соответствующим станциям. Поэтому необходимо ввести в план дополнительную базисную клетку с нулевой поставкой. Эта клетка должна стоять рядом с клеткой А3В5. Из трех соседних клеток следует выбрать клетку с минимальным расстоянием, например, А2В5. Записываем в нее корреспонденцию, равную «0» (табл. 2.5).

Добавление нулевой поставки

Таким образом, причиной вырождения плана транспортной задачи является наличие поставщиков и потребителей с равными объемами погрузки и выгрузки или равными объемами сумм погрузки и выгрузки по нескольким станциям в разнообразных комбинациях. Такие случаи необходимо уметь находить для того, чтобы правильно определять места для нулевых поставок. В процессе решения задачи возможны случаи, когда число базисных клеток превышает величину «n + m — 1». Это означает появление ошибки вследствие того, что при построении опорного плана в какую-то клетку была введена не максимально возможная поставка.

Операция 2. Проверка плана на оптимальность.

Операция 2.1. Расчет потенциалов.

Проверка плана транспортной задачи в описываемом методе на оптимальность осуществляется с помощью потенциалов. Потенциалы — это такие числа, которые по определенным правилам назначаются каждой строке и каждому столбцу. Потенциалы строк обозначим ui, потенциалы столбцовvj. Они могут принимать любые значения. Однако удобнее работать с положительными, целыми и относительно небольшими числами. Такой потенциал первоначально назначается любой строке или столбцу. Рекомендуем поступать следующим образом. Выберем базисную клетку с максимальным расстоянием. В нашей матрице это клетка А2В3. Присвоим строке, в которой находится эта клетка, потенциал, равный 0 (u3 = 0). Далее можно рассчитать потенциалы столбцов по базисным клеткам строки 3 по формуле

Потенциал первого столбца

Рассчитанные потенциалы записываем напротив соответствующих столбцов ниже матрицы. Поскольку по всем базисным клеткам строки 2 потенциалы столбов найдены, переходим к расчету потенциалов строк.

Потенциал строки 1 рассчитываем по найденному потенциалу столбца 3 и базисной клетке А1В3 по формуле

Для строки 3 потенциал будет равен:

транспортный задача потенциал оптимальность

Также рассчитываем потенциалы для всех строк и столбцов (табл. 2.6).

Расстановка потенциалов и перераспределение поставок

Операция 2.2. Проверка небазисных клеток на соответствие их условию оптимальности.

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

Если это условие для всех небазисных клеток выполняется, то план является оптимальным, а если нет, хотя бы для одной клетки, то план не оптимален. Иначе говоря, существует некоторый план с меньшим функционалом. Разность потенциалов может интерпретироваться как некоторая условная цена перевозки единицы продукции по маршруту, связывающему соответствующие станции «i» и «j». Если она ниже cij, значит, использование данного маршрута не улучшит план, а если cij ниже разности потенциалов, т. е. условие (2.8) не выполняется, следовательно, существует план лучше рассчитанного, который необходимо отыскать.

Проверим условие (2.8) для табл. 2.6.

Клетка А1В1: 4 — 5 6), клетки А3В3 (13 — 1 > 9), а также для клеток А3В4, А4В3, из чего следует, что разработанный опорный план не оптимален. Отметим эти клетки.

Операция 3. Улучшение плана.

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

Операция 3.1. Построение цепи (контура, цикла) перераспределения поставок.

Улучшение плана осуществляется по одной из небазисных клеток, для которой условие оптимальности оказалось невыполненным. В нашем плане имеется четыре такие клетки. Выбираем одну из них, для которой условие оптимальности не выполняется в наибольшей степени. В нашем плане это клетка А2В4. Для нее условие оптимальности не выполнено на 4 единицы (10 — 0 — 6 = 4). Для этой клетки строим цепь перераспределения поставок. Цепь перераспределения поставок — это такая замкнутая ломаная линия, которая проходит по клеткам матрицы ходом шахматной ладьи. В вершинах контура обязательно лежит одна небазисная клетка (несоответствующая условию оптимальности, найденная ранее), а остальные соответствуют только базисным клеткам. Линии контура могут пересекаться. Для небазисной клетки А2В4 цепь будет проходить по клеткам А1В4, А1В3, А2В3 (табл. 2.7).

Возможные варианты построения цикла перераспределения

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

Операция 3.2. Перераспределение поставок.

Перераспределение поставок (см. табл. 2.6) производится по цепи. Вначале определим объем перераспределения поставок. Для этого присвоим клеткам — вершинам цепи — знаки. В небазисную клетку А2В4 ставим «+», поскольку в нее будет вводиться поставка. Далее, чередуя «+» с «-», расставляем знаки по остальным вершинам контура. Величина объема перераспределения поставок принимается равной минимальной поставке в отрицательной клетке. Для нашего случая это 50 единиц груза. Перераспределение заключается в том, что к поставкам в положительных клетках найденный объем прибавляется, а для отрицательных клеток отнимается. Результат представлен в табл. 2.6.

Функционал F’ нового плана, представленного в табл. 2.6 (выделенные поставки), составляет 1950 ткм, что на 200 ткм меньше значения функционала F предыдущего плана.

Полученный улучшенный план, представленный в табл. 2.6, в свою очередь, требует проверки на оптимальность, поэтому необходимо вернуться к операции 2.

Совокупность действий, описанных в операциях 2 и 3, в процессе решения задачи повторяется до тех пор, пока не будет получен оптимальный план. Эта совокупность носит итеративный (циклический) характер, поэтому она называется итерацией. Через определенное число итераций план становится оптимальным. После этого осуществляется переход от второй операции к четвертой (табл. 2.8).

Повторение операций 2, 3

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

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

Проверка плана на оптимальность свидетельствует о том, что для двух клеток условия оптимальности не выполняются. После перераспределения поставок по клетке А4В3, получаем новый план (табл. 2.9).

Оптимальный план поставок

Проверка плана перевозок на оптимальность по условию (2.8) показала, что для всех небазисных клеток матрицы условия оптимальности выполняются. Функционал F» оптимального плана равен 1920 ткм. Таким образом, получен план перевозок, обеспечивающий минимальный объем перевозочной работы для транспортировки всего груза между станциями погрузки и выгрузки.

«>

Ссылка на основную публикацию
Adblock detector