Практический блок. Вырожденные случаи. Открытая транспортная задача

Вырожденные случаи. Открытая транспортная задача.

Некоторые замечания по частным случаям, которые могут встретиться при решении.

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

2. Если в отрицательных вершинах цикла, по которому перераспределяется поставка, две или более минимальных поставок, то все они при перераспределении обратятся в нуль. Так как на каждом шаге число занятых клеток сохраняется в количестве m+n–1, то из этих “нулевых” клеток образуется только одна пустая клетка, а остальные считаются заполненными поставкой равной 0.

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

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

1. Обязательные поставки.

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

2. Ограничения пропускной способности.

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

Самый простой способ учитывать пропускную способность состоит в следующем:

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

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

При превышении суммарной мощности над суммарным спросом на величину D вводится дополнительный столбец так называемого фиктивного потребителя со спросом равным D. Показатели с_in+1(i=1,2,…,m) в этом столбце выбираются произвольно, но с одним условием, что все они равны между собой. Удобнее всего принимать их равными 0. Далее задача решается как закрытая.

Аналогично, при превышении суммарного спроса над суммарной мощностью на величину D вводится дополнительная строка так называемого фиктивного поставщика с мощностью равной D и с нулевыми транспортными издержками.

Дата добавления: 2015-04-24