Описание метода дифференциальных рент. Дополнительные ограничения транспортной задачи. Метод дифференциальных рент

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

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

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

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

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

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

Пример (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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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