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

Обновлено: 29.04.2024

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также: