Решение транспортной задачи методом дифференциальных рент

Задание. Для ТЗ, исходные данные которой приведены в таблице 27, найти оптимальный план методом дифференциальных рент.
Таблица 27 – Исходные данные для определения оптимального
плана ТЗ методом дифференциальных рент

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

Решение ведем с помощью калькулятора.

Перейдем от таблицы 27 к таблице 28, добавив один дополнительный столбец для указания избытка и недостатка по строкам и одну строку для записи соответствующих разностей.
Таблица 28 – Определение оптимального плана ТЗ методом
дифференциальных рент

Пункты отправления	Пункты назначения					Запасы	Недостаток (-) / Избыток (+)
Пункты отправления	B₁	B₂	B₃	B₄	В₅	Запасы	Недостаток (-) / Избыток (+)
А₁	7	12	(4)120	8	5	180	+60
А₂	(1)110 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

В каждом из столбцов таблицы 28 находим минимальные тарифы и обводим их кружками. Заполняем клетки, в которых стоят указанные числа. Для этого в каждую из клеток записываем максимально допустимое число. Например, в клетку А₁В₃ записываем число 120. В эту клетку нельзя поместить большее число, поскольку в таком случае были бы превышены потребности пункта назначения В₃.
В результате заполнения отмеченных выше клеток получен так называемый условно оптимальный план, согласно которому полностью удовлетворяются потребности пунктов назначения В₁,В₂, В₃, В₄ и частично пункта В₅. При этом полностью распределены запасы пункта отправления А₂, частично – пункта А₁ и остались совсем нераспределенными запасы пункта отправления А₃.
После получения условно оптимального плана определяем избыточные и недостаточные строки. Здесь недостаточной является строка А₂, так как запасы пункта отправления А₂ полностью использованы,
а потребности пункта назначения В₅ удовлетворены частично. Величина недостатка 80 единиц.
Строки А₁ и А₃ являются избыточными, поскольку запасы пунктов отправления А₁ и А₃ распределены не полностью. При этом величина избытка строки А₁ равна 60 единицам, а строки А₃ – 20 единицам. Общая величина избытка 60+20=80 совпадает с общей величиной недостатка, равной 80.
После определения избыточных и недостаточных строк по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках. В данном случае эти разности соответственно равны 5,4,2,1 (таблица 28). Для столбца В₃ разность не распределена, т.к. число, стоящее в кружке в данном столбце, находится в положительной строке. В столбце В₁ число, стоящее в кружке, равно 1, а в избыточных строках в клетках данного столбца наименьшим является число 6. Следовательно, разность для данного столбца равна 6-1=5. Аналогично находим разности для других столбцов: 12-8=4 для В₂; 7-5 = 2 для В₄; 4-3=1 для В₅.
Выбираем наименьшую из найденных разностей, которая является промежуточной рентой. В данном случае промежуточная рента равна 1 и находится в столбце В₅. Найдя промежуточную ренту, переходим к таблице 29.
В этой таблице в строках А₁ и А₃ (являющихся избыточными) переписываем соответствующие тарифы из строк А₁ и А₃ таблицы 28. Элементы строки А₂ (которая была недостаточной) получаются в результате прибавления к соответствующим тарифам, находящимся в строке А₂ таблицы 28, промежуточной ренты, т.е. 1.
Таблица 29 – Определение оптимального плана ТЗ методом
дифференциальных рент

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

В таблице 29 число заполняемых клеток возросло на одну. Это обусловлено тем, что число минимальных тарифов, стоящих в каждом из столбцов данной таблицы, возросло на единицу, а именно: в столбце В₅ теперь имеются два минимальных элемента 4. Эти числа заключаются в кружки; клетки, в которых они стоят, следует заполнить. Необходимо заполнить и клетки, в которых стоят наименьшие для столбцов тарифы: это клетки таблицы 29, в которых соответствующие тарифы заключены в кружки. После того, как указанные клетки определены, устанавливаем последовательность их заполнения. Для этого находим столбцы (строки), в которых имеется лишь одна клетка для заполнения. Определив и заполнив некоторую клетку, исключаем из рассмотрения соответствующий столбец (строку) и переходим к заполнению следующей клетки. В данном случае заполнение клеток проводим в такой последовательности. Сначала заполняем клетки А₁В₃, А₂В₁, А₂В₂, А₂В₄, так как они являются единственными клетками для заполнения в столбцах В₁, В₂, В₃, В₄. После заполнения указанных клеток заполняем клетку А₃В₅, поскольку она является единственной для заполнения в строке А₃. Заполнив эту клетку таблицы 29, исключаем из рассмотрения строку А₃. Тогда в столбце В₅ остается лишь одна клетка для заполнения. Эта клетка А₂В₅, которую заполняем. После заполнения клеток устанавливаем избыточные и недостаточные строки таблицы 29. Как видно из таблицы 29, еще имеется нераспределенный остаток. Следовательно, получен условно оптимальный план задачи и нужно перейти к новой таблице. Для этого по каждому из столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках таблицы 29. Среди этих разностей наименьшая равна 1. Это и есть промежуточная рента. Переходим к новой таблице 30.
Таблица 30 – Определение оптимального плана ТЗ методом
дифференциальных рент

Пункты отправления	Пункты назначения					Запасы	Недостаток (-) / Избыток (+)
Пункты отправления	B₁	B₂	B₃	B₄	В₅	Запасы	Недостаток (-) / Избыток (+)
А₁	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

В новой таблице элементы строк А₂ и А₃ получены в результате прибавления к соответствующим числам строк А₂ и А₃ (являющихся недостаточными) таблицы 29 промежуточной ренты, т.е. 1. В результате в таблице 30 число клеток для заполнения возросло еще на одну и стало равным 6. Определяем указанные клетки и заполняем их. Сначала заполняем клетки А₁В₃, А₂В₁, А₂В₂, А₂В₄, а затем А₃В₅, А₂В₅, А₁В₅. В результате все имеющиеся запасы поставщиков распределяются в соответствии с фактическими потребностями пунктов назначения. Число заполненных клеток равно 7, и все они имеют наименьший показатель c_ij. Следовательно, получен оптимальный план исходной транспортной задачи:

	0	0	120	0	60
X* =	110	90	0	80	70
	0	0	0	0	20

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

S = 4^.120+5^.60+1^.110+8^.90+5^.80+3^.70+4^.20 = 2300.

Решение транспортной задачи методом дифференциальных рент

Правила ввода данных

Поиск

Процесс

Сообщение