2.3.Решение задачи методом дифференциальных рент

Стоимость перевозки единицы продукции задана матрицей (табл. 2.3):

Таблица 2.3

Транспортная задача

Потребители Склады	Москва	Брянск	Орел	Новгород	Воронеж	Ресурсы
1	9	6	3	6	3	300
2	5	4	9	7	8	270
3	7	3	7	2	9	250
4	4	5	6	8	2	180
Заказ	190	170	210	160	230

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 300 + 270 + 250+180 = 1000

∑b = 190 + 170 + 210 + 160+230 = 960

Как можно видеть, суммарная потребность груза в пунктах назначения превышает запасы груза на складах. Поэтому, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный (фиктивный) склад с запасом груза, равным 40 (1000—960).

Тарифы перевозки единицы груза со склада во все магазины полагаем равны нулю.

Далее мы занесем исходные данные в распределительную таблицу (табл.2.4).

Таблица 2.4

Транспортная задача

Потребители Склады	Москва	Брянск	Орел	Новгород	Воронеж	6		Ресурсы
1	9	6	3	6	3	0		300
2	5	4	9	7	8	0		270
3	7	3	7	2	9	0		250
4	4	5	6	8	2	0		180
Заказ	190	170	210	160	230		40

Итерация №1. В каждом из столбцов таблицы 1 находим минимальные тарифы (они выделены) (табл.2.5.).

Таблица 2.5

Минимальные тарифы

9	6	3	6	3	0
5	4	9	7	8	0
7	3	7	2	9	0
4	5	6	8	2	0

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

В этом случае заполнение клеток проводим в последовательности:

Искомый элемент равен 3. Для этого элемента запасы равны 300, потребности 210. Поскольку минимальным является 210, то вычитаем его.

Искомый элемент равен 3. Для этого элемента запасы равны 250, потребности 170. Поскольку минимальным является 170, то вычитаем его.

Искомый элемент равен 2. Для этого элемента запасы равны 80, потребности 160. Поскольку минимальным является 80, то вычитаем его.

Искомый элемент равен 4. Для этого элемента запасы равны 180, потребности 190. Поскольку минимальным является 180, то вычитаем его.

Таблица 2.6

Условно оптимальный план

Потребители Склады	1	2	3	4	5	6			Ресурсы
1	9	6	3[210]	6	3	0			300[90]
2	5	4	9	7	8	0			270[270]
3	7	3[170]	7	2[80]	9	0			250[0]
4	4 [180]	5	6	8	2[0]	0			180[0]
Заказ	190[10]	170[0]	210[0]	160[80]	230[230]		40[40]

После получения условно-оптимального плана определяем избыточные и недостаточные строки.

Здесь недостаточными являются строки 3,4, так как запасы этих пунктов отправления полностью использованы, а потребности пункта назначения удовлетворены частично.

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

Таблица 2.7

Избыточные и недостаточные строки

Потребители Склады	1	2	3	4	5	6	Ресурсы	Избыток(+)/ Недостаток(-)
1	9	6	3[210]	6	3	0	300[90]	+90
2	5	4	9	7	8	0	270[270]	+270
3	7	3[170]	7	2[80]	9	0	250	-80
4	4[180]	5	6	8	2[0]	0	180	-240
Заказ	190[10]	170	210	160[80]	230	40[40]

После определения избыточных и недостаточных строк по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках (табл.2.8).

Таблица 2.8

Определение оптимального плана ТЗ

Потребители Склады	1	2	3	4	5	6	Ресурсы	Избыток(+)/ Недостаток(-)
1	9	6	3[210]	6	3	0	300[90]	+90
2	5	4	9	7	8	0	270[270]	+270
3	7	3[170]	7	2[80]	9	0	250	-80
4	4[180]	5	6	8	2[0]	0	180	-240
Заказ	190[10]	170	210	160[80]	230	40[40]
Разность	1	1	-	4	1	-

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

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

Таблица 2.9

Получены новые данные для нахождения оптимального плана

9	6	3	6	3	0
5	4	9	7	8	0
8	4	8	3	10	1
5	6	7	9	3	1

Итерация №2. Производится аналогичным способом.

Получили новую матрицу для нахождения оптимального плана (табл.2.10).

Таблица 2.10

Определение оптимального плана ТЗ

Потребители Склады	1	2	3	4	5	6	Ресурсы	Избыток(+)/ Недостаток(-)
1	9	6	3[210]	6	3[90]	0	300	-0
2	5[150]	4[120]	9	7	8	0	270	-0
3	8	4[50]	8	3[160]	10	1	250[40]	+40
4	5[40]	6	7	9	3[140]	1	180	-0
Заказ	190	170	210	160	230	40[40]
Разность	3	-	5	-	7	-

Итерация №3. Производится аналогичным образом.

После выполнения всех операций получили новую матрицу для нахождения оптимального плана (табл.2.11).

Таблица 2.11

Определение оптимального плана ТЗ

Потребители Склады	1	2	3	4	5	6	Ресурсы	Избыток(+)/ Недостаток(-)
1	10	7	4[210]	7	4[90]	1[0]	300	-0
2	6[150]	5	10	8	8	1[40]	270[80]	+80
3	8	4[170]	8	3[80]	10	1[0]	250	-80
4	6[40]	7	8	10	4[140]	2	180	-0
Заказ	190	170	210	160[80]	230	40
Разность	-	1	6	5	5	-

Итерация №4. Производится аналогичным образом.

После выполнения всех операций получили условно-оптимальный план (табл.2.12).

Таблица 2.12

Условно-оптимальный план

Потребители Склады	1	2	3	4	5	6	Ресурсы	Избыток(+)/ Недостаток(-)
1	11	8	4[210]	8	5[90]	2	300	-0
2	6[190]	5[80]	10	8	9	1[0]	270	-40
3	9	5[90]	9	4[160]	11	2	250	-0
4	7	8	9	11	4[140]	3	180[40]	-40
Заказ	190	170	210	160	230	40[40]
Разность	1	3	4	7	-	2

Итерация №5. Производится аналогичным образом.

После выполнения всех операций получили условно-оптимальный план (табл.2.13).

Таблица 2.13

Условно-оптимальный план

Потребители Склады	1	2	3	4	5	6	Ресурсы	Избыток(+)/ Недостаток(-)
1	12	9	6[210]	9	6	3	300[90]	+90
2	7[190]	6[80]	11	9	10	2[0]	270	-40
3	10	6[90]	10	5[160]	12	3	250	-0
4	7[0]	8	9	11	5[180]	3	180	-40
Заказ	190	170	210	160	230[50]	40[40]
Разность	5	3	-	4	1	1

Итерация №6. Производится аналогичным образом.

После выполнения всех операций получили условно-оптимальный план (табл.2.14).

Таблица 2.14

Условно-оптимальный план

Потребители Склады	1	2	3	4	5	6	Ресурсы	Избыток(+)/ Недостаток(-)
1	12	9	6[210]	9	6[90]	3[0]	300	0
2	8[150]	7[80]	12	10	11	3[40]	270	0
3	11	7[90]	11	6[160]	13	4	250	0
4	8[40]	9	10	12	6[140]	4	180	0
Заказ	190	170	210	160	230	40

В результате все имеющиеся запасы поставщиков распределяются в соответствии с фактическими потребностями пунктов назначения. Число заполненных клеток равно 10, и все они имеют наименьший показатель. Следовательно, получен оптимальный план исходной транспортной задачи (табл.2.15).

Таблица 2.15

Оптимальный план

-	-	210	-	90	0
150	80	-	-	-	40
-	90	-	160	-	-
40	-	-	-	140	-

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

F(x) = 3*210 + 3*90 + 5*150 + 4*80 + *40 + 3*90 + 2*160 + 4*40 + 2*140 = 3000

Таким образом, для получения минимальных издержек продукцию с первого склада отправляем в Орёл (210 кор.) и Новгород (90 кор.), со второго склада в Москва (150 кор.) и Брянск (80 коробов.), с третьего в Брянск (90 кор.) и Новгород (80 кор.), с четвертого склада в Москва (40 кор.) и Воронеж (140 коробов.).

В ходе выполнения второй главы “Решение задачи об оптимизации плана перевозок и получении минимальных издержек” обоснована целесообразность применения методов исследования операций для разработки схемы оптимального распределения продукции со складов. Построена математическая модель задачи. Проведённый анализ методов решения такого рода математических задач позволил сделать вывод о целесообразности сведения решения транспортной задачи линейного программирования методом дифференциальных рент. Рассмотрен пример решения задачи, в результате чего получен оптимальный план распределения готовой продукции со складов между потребителями в различных городах.