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

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

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

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

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

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

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

Пример (4):

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

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

Таблица 10.

Пункты отправления	Пункты назначения						Запасы
	7	12	4	8	5	180
	1	8	6	5	3	350
	6	13	8	7	4	20
Потребности	110	90	120	80	150	550

Таблица 11.

Пункты отправления	Пункты назначения					Запасы	Недостаток избыток (
	7	12	4 120	8	5	180	+60
	1 110	8 90	6	5 80	3 70	350	-80
	6	13	8	7	4	20	+20
Потребности	110	90	120	80	150	550
Разность	5	4		2	1

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

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

После получения условно оптимального плана определяем из­быточные и недостаточные строки. Здесь недостаточной являет­ся строка , так как запасы пункта отправления полностью использованы, а потребности пункта назначенияудовлетворе­ны частично. Величина недостатка равна 80 ед.

Строки и являются избыточными, поскольку запасы пунктов отправления и распределены не полностью. При этом величина избытка строки равна 60 ед., а строки равна ед.Общая величина избытка совпадает с общей величиной недостатка, равной.

После определения избыточных и недостаточных строк по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоя­щими в заполненных клетках. В данном случае эти разности соответственно равны 5, 4, 2, 1 (табл.11). Для столбца раз­ность не определена, так как число, записанное в кружке в дан­ном столбце, находится в положительной строке. В столбцечисло, стоящее в кружке, равно, а в избыточных строках в клет­ках данного столбца наименьшим является число. Следователь­но, разность для данного столбца равнаАналогично находим разности для других столбцов: для; для; для. .

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

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

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

Таблица 11.

Пункты отправления	Пункты назначения					Запасы	Недостаток избыток (
	7	12	4 120	8	5	180	+60
	2 110	9 90	6	6 80	4 70	350	-60
	6	13	8	7	4 20	20	-0
Потребности	110	90	120	80	150	550
Разность	5	3		2	1

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

Таблица 12.

Пункты отправления	Пункты назначения						Запасы		Недостаток избыток (
	7	12	4 120	8	5 60	180		0
	3 110	10 90	8	7 80	5 70	350		0
	7	14	9	8	5 20	20		0
Потребности	110	90	120	80	150	550

В новой таблице элементы строкполучены в ре­зультате прибавления к соответствующим числам строк(являющихся недостаточными) табл.2.11 промежуточной ренты, т. е.. В результате в табл.12 число клеток для заполнения возросло еще на одну и стало равным. Определяем указанные клетки и заполняем их. Сначала заполняем клетки,,, ,а затем ,,. В результате все имеющие­ся запасы поставщиков распределяются в соответствии с факти­ческими потребностями пунктов назначения. Число заполненных клеток равно , и все они имеют наименьший показатель.Сле­довательно, получен оптимальный план исходной транспортной задачи:

При этом плане перевозок общие затраты таковы: