Метод дифференциальных рент для решения транспортной задачи. Транспортная задача представляет собой задачу линейного программирования, однако ее специфическая структура позволяет так модифицировать симплекс-метод, что вычислительные процедуры становятся б
Назначение . Онлайн-калькулятор предназначен для решения транспортной задачи методом дифференциальных рент (см. пример решения). Для этого выберите размерность матрицы тарифов (количество поставщиков и количество магазинов).Алгоритм метода дифференциальных рент
Если при определении оптимального плана ТЗ методом потенциалов сначала находился какой-нибудь опорный план, а затем он последовательно улучшался, то при нахождении решения ТЗ методом дифференциальных рент сначала распределяют между пунктами назначения часть груза (так называемое оптимальное распределение) и на последующих итерациях постепенно уменьшают общую величину нераспределенных поставок. Первоначальный вариант распределения груза определяют следующим образом.В каждом из столбцов таблицы данных находят минимальный тариф. Найденные числа заключают в кружки, а клетки, в которых стоят указанные числа, заполняют. В них записывают максимально возможные числа. В результате получают некоторое распределение поставок груза в пункты назначения. Это распределение в общем случае не удовлетворяет ограничениям исходной транспортной задачи. Поэтому в результате последующих шагов следует постепенно сокращать нераспределенные поставки груза так, чтобы при этом общая стоимость перевозок оставалась минимальной. Для этого сначала определяют избыточные и недостаточные строки.
Строки, соответствующие поставщикам, запасы которых полностью распределены, а потребности пунктов назначения, связанных с данными потребителями запланированными поставками, не удовлетворены, считаются недостаточными. Эти строки иногда называют также отрицательными. Строки, запасы которых исчерпаны не полностью, считаются избыточными. Иногда их называют также положительными.
После того, как определены избыточные и недостаточные строки, для каждого из столбцов находят разности между числом в кружке и ближайшим к нему тарифом, записанным в избыточной строке. Если число в кружке находится в положительной строке, то разность не определяют. Среди полученных чисел находят наименьшее. Это число называется промежуточной рентой. После определения промежуточной ренты переходят к новой таблице. Эта таблица получается из предыдущей таблицы прибавлением к соответствующим тарифам, стоящим в отрицательных строках, промежуточной ренты. Остальные элементы остаются прежними. При этом все клетки новой таблицы считают свободными. После построения новой таблицы начинают заполнение ее клеток. Теперь уже число заполняемых клеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находится в столбце, в котором была записана промежуточная рента. Все остальные клетки находятся по одной в каждом из столбцов, и в них записаны наименьшие для данного столбца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа, стоящих в столбце, в котором в предыдущей таблице была записана промежуточная рента.
Поскольку в новой таблице число заполняемых клеток больше, чем число столбцов, то при заполнении клеток следует пользоваться специальным правилом, которое состоит в следующем. Выбирают некоторый столбец (строку), в котором имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данный столбец (строку). После этого берут некоторую строку (столбец), в которой имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данную строку (столбец). Продолжая так, после конечного числа шагов заполняют все клетки, в которых помещены кружки с заключенными в них числами. Если к тому же удается распределить весь груз, то получают оптимальный план. Если же оптимальный план ТЗ не получен, то переходят к новой таблице. Для этого находят избыточные и недостаточные строки, промежуточную ренту и строят новую таблицу. При этом могут возникнуть некоторые затруднения при определении знака строки, когда ее нераспределенный остаток равен нулю. В этом случае строку считают положительной при условии, что вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке.
После описанных выше итераций нераспределенный остаток становится равным нулю. В результате получается оптимальный план ТЗ.
Метод дифференциальных рент
В отличие от метода потенциалов, для которого сначала строился опорный план, а затем он последовательно улучшался, при решении задачи методом дифференциальных рент сразу наилучшим образом распределяют часть продукции между потребителями и на последующих итерациях постепенно уменьшают общую величину нераспределенных поставок.
Для определения решения транспортной задачи методом дифференциальных рент используют следующий алгоритм:
1. В каждом столбце определяют минимальный тариф и выделяют сответствую-щую клетку.
2. Выделенные клетки заполняют максимально возможными числами.
3. Т.к. в общем случае это распределение не удовлетворяет всех потребите-лей, чтобы на последующих шагах сокращать величину неудовлетворенных потребностей, необходимо оценить поставщиков.
ОПРЕДЕЛЕНИЕ 6 . Строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности выделенных потребителей не удовлетворены, являются отрицательными.
ОПРЕДЕЛЕНИЕ 7. Строки, соответствующие поставщикам, запасы которых не исчерпаны полностью, являются положительными.
ОПРЕДЕЛЕНИЕ 8. Строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности выделенных потребителей удовлетворены, имеют нулевую оценку. При этом, если вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке, данная строка с нулевой оценкой считается положительной. В противном случае - отрицательной.
4. Для каждого столбца, имеющего выделенный тариф в отрицательной строке, находят разности между выделенным тарифом и ближайшим к нему по величине тарифом, стоящим в положительной строке.
5. Среди полученных разностей определяют минимальную. Это число называют промежуточной рентой.
6. Строят новую таблицу, при этом тарифы, стоящие в положительных строках, переписываются без изменения, а тарифы, стоящие в отрицательных строках, увеличиваются на величину промежуточной ренты.
7. Переходят к п.1.
ЗАМЕЧАНИЕ: а) если в строке или столбце оказывается более одной выделенной клетки, то заполняют, в первую очередь, те выделенные клетки, которые являются единственными в столбце или строке;
б) если удается распределить все запасы, то получают оптимальный план транспортной задачи.
Дополнительные ограничения транспортной задачи
Запрещенные маршруты.
Если по каким-либо причинам невозможно поставлять продукцию из п. А i в п. В j , предполагают тариф этого пути сколь угодно большой величиной М, с ij = М, и решают задачу обычным способом.
Обязательные поставки.
а) Если необходимо из п. А i перевезти в п. В j определенное количество продукции d ij , соответствующую клетку заполняют сразу числом d ij , а в дальнейшем решают задачу, считая заполненную клетку свободной, но с тарифом, с ij = М, равным очень большому числу, а запасы и потребности уменьшают на величину d ij .
б) Если необходимо из п. А i в п. В j перевезти не меньше определенного количества продукции d ij , то считают запасы и потребности меньше на величину d ij , это количество d ij считают перевезенным по маршруту А i В j , и решают задачу далее обычным способом.
в) Если необходимо перевезти из п. А i в п. В j не более определенного количества продукции d ij , вводят дополнительный пункт назначения с потребностью, равной (- d ij), потребность в п. В j делают равной d ij . Тарифы на перевозки в дополнительный пункт назначения равны тарифам п. В j , кроме i-той строки, тариф в которой будет равен сколь угодно большому числу М. Решают задачу обычным образом, а при записи ответа объединяют основного и дополнительного потребителя (складывают содержимое столбцов).
Если при определении оптимального плана транспортной задачи методом потенциалов сначала находился какой-нибудь ее опорный план, а затем он последовательно улучшался, то при нахождении решения транспортной задачи методом дифференциальных рент сначала наилучшим образом распределяют между пунктами назначения часть груза (так называемое условно оптимальное распределение )и на последующих итерациях постепенно уменьшают общую величину нераспределенных поставок. Первоначальный вариант распределения груза определяют следующим образом. В каждом из столбцов таблицы данных транспортной задачи находят минимальный тариф. Найденные числа заключают в кружки, а клетки, в которых стоят указанные числа, заполняют. В них записывают максимально возможные числа. В результате получают некоторое распределение поставок груза в пункты назначения. Это распределение в общем случае не удовлетворяет ограничениям исходной транспортной задачи. Поэтому в результате последующих шагов следует постепенно сокращать нераспределенные поставки груза так, чтобы при этом общая стоимость перевозок оставалась минимальной. Для этого сначала определяют избыточные и недостаточные строки.
Строки, соответствующие поставщикам, запасы которых полностью распределены, а потребности пунктов назначения, связанных с данными потребителями запланированными поставками, не удовлетворены, считаются недостаточными. Эти строки иногда называют также отрицательными. Строки, запасы которых исчерпаны не полностью, считаются избыточными. Иногда их называют также положительными.
После того как определены избыточные и недостаточные строки, для каждого из столбцов находят разности между числом в кружке и ближайшим к нему тарифом, записанным в избыточной строке. Если число в кружке находится в положительной строке, то разность не определяют. Среди полученных чисел находят наименьшее. Это число называется промежуточной рентой. После определения промежуточной ренты переходят к новой таблице. Эта таблица получается из предыдущей таблицы прибавлением к соответствующим тарифам, стоящим в отрицательных строках, промежуточной ренты. Остальные элементы остаются прежними. При этом все клетки новой таблицы считают свободными. После построения новой таблицы начинают заполнение ее клеток. Теперь уже число заполняемых клеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находится в столбце, в котором была записана промежуточная рента. Все остальные клетки находятся по одной в каждом из столбцов и в них записаны наименьшие для данного столбца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа, стоящих в столбце, в котором в предыдущей таблице была записана промежуточная рента.
Поскольку в новой таблице число заполняемых клеток больше, чем число столбцов, то при заполнении клеток следует пользоваться специальным правилом, которое состоит в следующем. Выбирают некоторый столбец (строку), в котором имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данный столбец (строку). После этого берут некоторую строку (столбец), в которой имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данную строку (столбец). Продолжая так, после конечного числа шагов заполняют все клетки, в которых помещены кружки с заключенными в них числами. Если к тому же удается распределить весь груз, имеющийся в пунктах отправления, между пунктами назначения, то получают оптимальный план транспортной задачи. Если же оптимальный план не получен, то переходят к новой таблице. Для этого находят избыточные и недостаточные строки, промежуточную ренту и на основе этого строят новую таблицу. При этом могут возникнуть некоторые затруднения при определении знака строки, когда ее нераспределенный остаток равен нулю. В этом случае строку считают положительной при условии, что вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке.
После конечного числа описанных выше итераций нераспределенный остаток становится равным нулю. В результате получают оптимальный план данной транспортной задачи.
Описанный выше метод решения транспортной задачи имеет более простую логическую схему расчетов, чем рассмотренный выше метод потенциалов. Поэтому в большинстве случаев для нахождения решения конкретных транспортных задач с использованием ЭВМ применяется метод дифференциальных рент.
5.6 Определение оптимального плана транспортных задач, имеющих некоторые усложения в их постановке.
При нахождении решения ряда конкретных транспортных задач часто бывает необходимо учитывать дополнительные ограничения, которые не встречались выше при рассмотрении простых вариантов данных задач. Остановимся подробнее на некоторых возможных усложнениях в постановках транспортных задач.
1. При некоторых реальных условиях перевозки груза из определенного пункта отправления , в пункт назначения , не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что тариф перевозки единицы груза из пункта в пункт , является сколь угодно большой величиной М, и при этом условии известными методами находят решение новой транспортной задачи. При таком предположении исключается возможность при оптимальном плане транспортной задачи перевозить груз из пункта в пункт . Такой подход к нахождению решения транспортной задачи называют запрещением перевозок или блокированием соответствующей клетки таблицы данных задачи.
2. В отдельных транспортных задачах дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из пункта отправления , в пункт назначения требуется обязательно перевести единиц груза. Тогда в клетку таблицы данных транспортной задачи, находящуюся на пересечении строки и столбца записывают указанное число и в дальнейшем эту клетку считают свободной со сколь угодно большим тарифом перевозок М. Для полученной таким образом новой транспортной задачи находят оптимальный план, который определяет оптимальный план исходной задачи.
3. Иногда требуется найти решение транспортной задачи, при котором из пункта отправления в пункт назначения должно быть завезено не менее заданного количества груза . Для определения оптимального плана такой задачи считают, что запасы пункта и потребности пункта меньше фактических на единиц. После этого находят оптимальный план новой транспортной задачи, на основании которого и определяют решение исходной задачи.
4. В некоторых транспортных задачах требуется найти оптимальный план перевозок при условии, что из пункта отправления в пункт назначения перевозится не более чем единиц груза, т. е.
Сформулированную задачу можно решить так. В таблице исходных данных задачи для каждого -го ограничения (1) предусматривают дополнительный столбец, т. е. вводят дополнительный пункт назначения. В данном столбце записывают те же тарифы, что и в столбце , за исключением тарифа, находящегося в -й строке. В дополнительном столбце в этой строке тариф считают равным некоторому сколь угодно большому числу . При этом потребности пункта считают равными „ а потребности вновь введенного пункта назначения полагают равными . Решение полученной транспортной задачи может быть найдено методом потенциалов, и тем самым будет определен оптимальный план или установлена неразрешимость исходной задачи. Заметим, что исходная транспортная задача разрешима лишь в том случае, когда для нее существует хотя бы один опорный план.
Приведенную выше задачу можно решить и таким способом. С учетом ограничения (1) по правилу минимального элемента строят опорный план. При этом если величина записываемого на данном шаге в соответствующую клетку числа определяется только ограничением (1), то в последующем из рассмотрения исключают только заполненную клетку. В других случаяхиз рассмотрения исключают либо строку, либо столбец (что-нибудь одно).
Если в результате составления плана поставок все имеющиеся запасы пунктов отправления распределены и потребности в пунктах назначения удовлетворены, то получен опорный план транспортной задачи.
Если в какой-то строке (а следовательно, и в столбце) остался нераспределенный остаток, равный , то вводят дополнительный пункт назначения и дополнительный пункт отправления с потребностями и запасами, равными . В клетке, находящейся на пересечении столбца дополнительного пункта назначения и строки дополнительного пункта отправления, тариф считают равным нулю. Во всех остальных клетках данной строки и столбца тарифы полагают равными некоторому сколь угодно большому числу М. Полученную в результате этого транспортную задачу решают методом потенциалов. После конечного числа шагов либо устанавливают, что исходная задача не имеет опорного плана, либо находят ее оптимальный план. При этом – оптимальный план исходной задачи, если
Если при определении оптимального плана транспортной задачи методом потенциалов сначала находился какой-нибудь ее опорный план, а затем он последовательно улучшался, то при нахождении решения транспортной задачи методом дифференциальных рент сначала наилучшим образом распределяют между пунктами назначения часть груза (так называемое условно оптимальное распределение) и на последующих итерациях постепенно уменьшают общую величину нераспределенных поставок. Первоначальный вариант распределения груза определяют следующим образом. В каждом из столбцов таблицы данных транспортной задачи находят минимальный тариф. Найденные числа заключают в кружки, а клетки, в которых стоят указанные числа, заполняют. В них записывают максимально возможные числа. В результате получают некоторое распределение поставок груза в пункты назначения. Это распределение в общем случае не удовлетворяет ограничениям исходной транспортной задачи. Поэтому в результате последующих шагов следует постепенно сокращать нераспределенные поставки груза так, чтобы при этом общая стоимость перевозок оставалась минимальной. Для этого сначала определяют избыточные и недостаточные строки.
Строки, соответствующие поставщикам, запасы которых полностью распределены, а потребности пунктов назначения, связанных с данными потребителями запланированными поставками, не удовлетворены, считаются недостаточными. Эти строки иногда называют также отрицательными. Строки, запасы которых исчерпаны не полностью, считаются избыточными. Иногда их называют также положительными.
После того как определены избыточные и недостаточные строки, для каждого из столбцов находят разности между числом в кружке и ближайшим к нему тарифом, записанным в избыточной строке. Если число в кружке находится в положительной строке, то разность не определяют. Среди полученных чисел находят наименьшее. Это число называется промежуточной рентой. После определения промежуточной ренты переходят к новой таблице. Эта таблица получается из предыдущей таблицы прибавлением к соответствующим тарифам, стоящим в отрицательных строках, промежуточной ренты. Остальные элементы остаются прежними. При этом все клетки новой таблицы считают свободными. После построения новой таблицы начинают заполнение ее клеток. Теперь уже число заполняемых клеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находится в столбце, в котором была записана промежуточная рента. Все остальные клетки находятся по одной в каждом из столбцов и в них записаны наименьшие для данного столбца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа, стоящих в столбце, в котором в предыдущей таблице была записана промежуточная рента.
Поскольку в новой таблице число заполняемых клеток больше, чем число столбцов, то при заполнении клеток следует пользоваться специальным правилом, которое состоит в следующем. Выбирают некоторый столбец (строку), в котором имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данный столбец (строку). После этого берут некоторую строку (столбец), в которой имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данную строку (столбец). Продолжая так, после конечного числа шагов заполняют все клетки, в которых помещены кружки с заключенными в них числами. Если к тому же удается распределить весь груз, имеющийся в пунктах отправления, между пунктами назначения, то получают оптимальный план транспортной задачи. Если же оптимальный план не получен, то переходят к новой таблице. Для этого находят избыточные и недостаточные строки, промежуточную ренту и на основе этого строят новую таблицу. При этом могут возникнуть некоторые затруднения при определении знака строки, когда ее нераспределенный остаток равен нулю. В этом случае строку считают положительной при условии, что вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке.
После конечного числа описанных выше итераций нераспределенный остаток становится равным нулю. В результате получают оптимальный план данной транспортной задачи.
Описанный выше метод решения транспортной задачи имеет более простую логическую схему расчетов, чем рассмотренный выше метод потенциалов. Поэтому в большинстве случаев для нахождения решения конкретных транспортных задач с использованием ЭВМ применяется метод дифференциальных рент.
Пример (4):
Для транспортной задачи, исходные данные которой приведены в табл.11, найти оптимальный план методом дифференциальных рент.
Решение. Перейдем от табл.11 к табл.12, добавив один дополнительный столбец для указания избытка и недостатка по строкам и одну строку для записи соответствующих разностей.
Таблица 10.
Пункты отправления |
Пункты назначения | ||||||
Потребности |
Таблица 11.
Пункты отправления |
Пункты назначения |
Недостаток избыток ( |
|||||||||
| |||||||||||
|
|
|
| ||||||||
Потребности | |||||||||||
Разность |
В каждом из столбцов табл.12 находим минимальные тарифы и обводим их кружками. Заполняем клетки, в которых стоят указанные числа. Для этого в каждую из клеток записываем максимально допустимое число. Например, в клетку, находящуюся на пересечении строки и столбца,записываем число 120. В эту клетку нельзя поместить большее число, поскольку в таком случае были бы превышены потребности пункта назначения.
В результате заполнения отмеченных выше клеток получен так называемый условно оптимальный план, согласно которому полностью удовлетворяются потребности пунктов назначения и частично - пункта назначения. При этом полностью распределены запасы пункта отправления, частично - пункта отправленияи остались совсем нераспределенными запасы пункта отправления.
После получения условно оптимального плана определяем избыточные и недостаточные строки. Здесь недостаточной является строка , так как запасы пункта отправления полностью использованы, а потребности пункта назначенияудовлетворены частично. Величина недостатка равна 80 ед.
Строки и являются избыточными, поскольку запасы пунктов отправления и распределены не полностью. При этом величина избытка строки равна 60 ед., а строки равна ед.Общая величина избытка совпадает с общей величиной недостатка, равной.
После определения избыточных и недостаточных строк по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках. В данном случае эти разности соответственно равны 5, 4, 2, 1 (табл.11). Для столбца разность не определена, так как число, записанное в кружке в данном столбце, находится в положительной строке. В столбцечисло, стоящее в кружке, равно, а в избыточных строках в клетках данного столбца наименьшим является число. Следовательно, разность для данного столбца равнаАналогично находим разности для других столбцов: для; для; для. .
Выбираем наименьшую из найденных разностей, которая является промежуточной рентой. В данном случае промежуточная рента равна и находится в столбце. Найдя промежуточную ренту, переходим к табл.11.
В этой таблице в строках и(являющихся избыточными) переписываем соответствующие тарифы из строкитабл.10. Элементы строки(которая была недостаточной) получаются в результате прибавления к соответствующим тарифам, находящимся в строкетабл. 10, промежуточной ренты, т. е..
В табл. 11 число заполняемых клеток возросло на одну. Это обусловлено тем, что число минимальных тарифов, стоящих в каждом из столбцов данной таблицы, возросло на единицу, а именно в столбце теперь имеются два минимальных элемента. Эти числа заключаем в кружки; клетки, в которых они стоят, следует заполнить. Необходимо заполнить и клетки, в которых стоят наименьшие для других столбцов тарифы. Это клетки табл. 11 в которых соответствующие тарифы заключены в кружки.
Таблица 11.
Пункты отправления |
Пункты назначения |
Недостаток избыток ( |
|||||||||
| |||||||||||
|
|
|
| ||||||||
| |||||||||||
Потребности | |||||||||||
Разность |
После того как указанные клетки определены, устанавливаем последовательность их заполнения. Для этого находим столбцы (строки), в которых имеется лишь одна клетка для заполнения. Определив и заполнив некоторую клетку, исключаем из рассмотрения соответствующий столбец (строку) и переходим к заполнению следующей клетки. В данном случае заполнение клеток проводим в такой последовательности. Сначала заполняем клетки ,,,, так как они являются единственными клетками для заполнения в столбцах .После заполнения указанных клеток заполняем клетку, поскольку она является единственной для заполнения в строке. Заполнив эту клетку (табл. 2.16), исключаем из рассмотрения строку . Тогда в столбце остается лишь одна клетка для заполнения. Это клетка, которую заполняем. После заполнения клеток устанавливаем избыточные и недостаточные строки (табл.11). Как видно из табл.11, еще имеется нераспределенный остаток. Следовательно, получен условно оптимальный план задачи и нужно перейти к новой таблице. Для этого по каждому из столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках (табл.11). Среди этих разностей наименьшая равна . Это и есть промежуточная рента. Переходим к новой таблице (табл.12).