Определитель матрицы ▦ Производная функции dydx График 3D Упростить выражение Графический метод решения задач нелинейного программирования ⇲ …
Примеры решений Метод Гомори Симплекс-метод Метод Фогеля Транспортная задача 🚚 Задача о назначениях Распределительный метод Метод потенциалов Задача коммивояжера Открытые и закрытые задачи

Метод дифференциальных рент

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

Количество столбцов (магазины) Количество строк (поставщики)
Здесь будет отображаться решение.

Алгоритм метода дифференциальных рент

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

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

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

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

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

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

Метод дифференциальных рент (также известный как метод разрешающих слагаемых А. Л. Лурье) был разработан для поиска оптимального плана перевозок. Его главная особенность в том, что он сразу строит условно-оптимальный план (минимизируя затраты), а затем итеративно «подгоняет» его под ограничения по запасам и потребностям, пока план не станет допустимым.

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

Задание. Для ТЗ, исходные данные которой приведены в таблице 27, найти оптимальный план методом дифференциальных рент.
Таблица 27 – Исходные данные для определения оптимального
плана ТЗ методом дифференциальных рент
Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4 В5
А1 7 12 4 8 5 180
А2 1 8 6 5 3 350
А3 6 13 8 7 4 20
Потребности 110 90 120 80 150 550

Решение ведем с помощью калькулятора.

Перейдем от таблицы 27 к таблице 28, добавив один дополнительный столбец для указания избытка и недостатка по строкам и одну строку для записи соответствующих разностей.
Таблица 28 – Определение оптимального плана ТЗ методом
дифференциальных рент

Пункты отправления Пункты назначения Запасы Недостаток (-) / Избыток (+)
B1 B2 B3 B4 В5
А1 7 12 (4)120 8 5 180 +60
А2 (1)110
90 		6 (5)
80 		(3)
70 		350 -80
А3 6 13 8 7 4 20 +20
Потребности 110 90 120 80 150 550
Разность 5 4 - 2 1
В каждом из столбцов таблицы 28 находим минимальные тарифы и обводим их кружками. Заполняем клетки, в которых стоят указанные числа. Для этого в каждую из клеток записываем максимально допустимое число. Например, в клетку А1В3 записываем число 120. В эту клетку нельзя поместить большее число, поскольку в таком случае были бы превышены потребности пункта назначения В3.
В результате заполнения отмеченных выше клеток получен так называемый условно оптимальный план, согласно которому полностью удовлетворяются потребности пунктов назначения В1,В2, В3, В4 и частично пункта В5. При этом полностью распределены запасы пункта отправления А2, частично – пункта А1 и остались совсем нераспределенными запасы пункта отправления А3.
После получения условно оптимального плана определяем избыточные и недостаточные строки. Здесь недостаточной является строка А2, так как запасы пункта отправления А2 полностью использованы,
а потребности пункта назначения В5 удовлетворены частично. Величина недостатка 80 единиц.
Строки А1 и А3 являются избыточными, поскольку запасы пунктов отправления А1 и А3 распределены не полностью. При этом величина избытка строки А1 равна 60 единицам, а строки А3 – 20 единицам. Общая величина избытка 60+20=80 совпадает с общей величиной недостатка, равной 80.
После определения избыточных и недостаточных строк по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках. В данном случае эти разности соответственно равны 5,4,2,1 (таблица 28). Для столбца В3 разность не распределена, т.к. число, стоящее в кружке в данном столбце, находится в положительной строке. В столбце В1 число, стоящее в кружке, равно 1, а в избыточных строках в клетках данного столбца наименьшим является число 6. Следовательно, разность для данного столбца равна 6-1=5. Аналогично находим разности для других столбцов: 12-8=4 для В2; 7-5 = 2 для В4; 4-3=1 для В5.
Выбираем наименьшую из найденных разностей, которая является промежуточной рентой. В данном случае промежуточная рента равна 1 и находится в столбце В5. Найдя промежуточную ренту, переходим к таблице 29.
В этой таблице в строках А1 и А3 (являющихся избыточными) переписываем соответствующие тарифы из строк А1 и А3 таблицы 28. Элементы строки А2 (которая была недостаточной) получаются в результате прибавления к соответствующим тарифам, находящимся в строке А2 таблицы 28, промежуточной ренты, т.е. 1.
Таблица 29 – Определение оптимального плана ТЗ методом
дифференциальных рент
Пункты отправления Пункты назначения Запасы
Недостаток (-) / Избыток (+)
B1 B2 B3 B4 В5
А1 7 12 (4)
120 		8 5 180 +60
А2 (2)
110 		(9)
90 		7 (6)
80 		(4)
70 		350 -60
А3 6 13 8 7 (4)
20 		20 -0
Потребности 110 90 120 80 150 550
Разность 5 3 - 2 1
В таблице 29 число заполняемых клеток возросло на одну. Это обусловлено тем, что число минимальных тарифов, стоящих в каждом из столбцов данной таблицы, возросло на единицу, а именно: в столбце В5 теперь имеются два минимальных элемента 4. Эти числа заключаются в кружки; клетки, в которых они стоят, следует заполнить. Необходимо заполнить и клетки, в которых стоят наименьшие для столбцов тарифы: это клетки таблицы 29, в которых соответствующие тарифы заключены в кружки. После того, как указанные клетки определены, устанавливаем последовательность их заполнения. Для этого находим столбцы (строки), в которых имеется лишь одна клетка для заполнения. Определив и заполнив некоторую клетку, исключаем из рассмотрения соответствующий столбец (строку) и переходим к заполнению следующей клетки. В данном случае заполнение клеток проводим в такой последовательности. Сначала заполняем клетки А1В3, А2В1, А2В2, А2В4, так как они являются единственными клетками для заполнения в столбцах В1, В2, В3, В4. После заполнения указанных клеток заполняем клетку А3В5, поскольку она является единственной для заполнения в строке А3. Заполнив эту клетку таблицы 29, исключаем из рассмотрения строку А3. Тогда в столбце В5 остается лишь одна клетка для заполнения. Эта клетка А2В5, которую заполняем. После заполнения клеток устанавливаем избыточные и недостаточные строки таблицы 29. Как видно из таблицы 29, еще имеется нераспределенный остаток. Следовательно, получен условно оптимальный план задачи и нужно перейти к новой таблице. Для этого по каждому из столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках таблицы 29. Среди этих разностей наименьшая равна 1. Это и есть промежуточная рента. Переходим к новой таблице 30.
Таблица 30 – Определение оптимального плана ТЗ методом
дифференциальных рент
Пункты отправления Пункты назначения Запасы Недостаток (-) / Избыток (+)
B1 B2 B3 B4 В5
А1 7 12 (4)
120 		8 (5)
60 		180 0
А2 (3)
110 		(10)
90 		8 (7)
80 		(5)
70 		350 0
А3 7 14 9 8 (5)
20 		20 0
Потребности 110 90 120 80 150 550
В новой таблице элементы строк А2 и А3 получены в результате прибавления к соответствующим числам строк А2 и А3 (являющихся недостаточными) таблицы 29 промежуточной ренты, т.е. 1. В результате в таблице 30 число клеток для заполнения возросло еще на одну и стало равным 6. Определяем указанные клетки и заполняем их. Сначала заполняем клетки А1В3, А2В1, А2В2, А2В4, а затем А3В5, А2В5, А1В5. В результате все имеющиеся запасы поставщиков распределяются в соответствии с фактическими потребностями пунктов назначения. Число заполненных клеток равно 7, и все они имеют наименьший показатель cij. Следовательно, получен оптимальный план исходной транспортной задачи:
0 0 120 0 60
X* = 110 90 0 80 70
0 0 0 0 20
При этом плане перевозок общие затраты таковы:

S = 4.120+5.60+1.110+8.90+5.80+3.70+4.20 = 2300.

Суть алгоритма и его универсальность

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

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

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

Области науки и техники для применения алгоритма

1. Логистика и управление цепями поставок (Supply Chain Management)

2. Экономика и менеджмент (Операционный менеджмент)

3. Вычислительная техника и IT

4. Промышленность и производство

5. Военное дело и гражданская оборона