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

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

отправления

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

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

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

Пункты

отправления

Пункты назначения Запасы Недостаток (-)

Избыток (+)

B1 B2 B3 B4 В5
А1 7 12
(4)

120

8 5 180 +60
А2
(1)

110


(8)

90


6

(5)

80

(3)

70

350 -80
А3 6 13 8 7 4 20 +20
Потребности 110 90 120 80 150 550
Разность 5 4 - 2 1

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

отправления

Пункты назначения Запасы
Недостаток (-)
Избыток (+)
B1 B2 B3 B4 В5
А1
7

12

(4)

120


8

5


180

+60

А2
(2)

110


(9)

90


7

(6)

80

(4)

70

350

-60
А3 6 13 8 7
(4)

20


20

-0
Потребности 110 90 120 80 150
550
Разность 5 3 - 2 1

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

отправле-ния

Пункты назначения Запасы Недостаток (-)

Избыток (+)

B1 B2 B3 B4 В5
А1
7

12

(4)

120


8

(5)

60
180 0
А2
(3)

110


(10)

90

8

(7)

80

(5)

70
350 0
А3
7

14

9

8

(5)

20

20 0
Потребности 110 90 120 80 150 550

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


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.

загрузка...