Метод 1. Метод минимальной стоимости

Транспортная задача и алгоритм ее решения

Алгоритм решения транспортной задачи состоит из четырех этапов:

Этап 1 Представление данных в форме стандартной таблицы и поиск любого допустимого распределения ресурсов. Допустимым называется такое распределение ресурсов, которое позволяет удовлетворить весь спрос в пунктах назначения и вывезти весь запас продуктов из пунктов производства.

Этап 2 Проверка полученного распределения ресурсов на оптимальность.

Этап 3 Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость перевозки.

Этап 4 Повторная проверка оптимальности полученного распределения ресурсов.

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

Поиск начального распределения ресурсов

Начальное распределение ресурсов может быть получено с помощью любого метода, позволяющего найти допустимое решение задачи. Мы остановимся на двух методах нахождения начального распределения ресурсов:

· метод минимальной стоимости;

· метод Вогеля.

Алгоритм этих методов рассмотрим на примере 2.

Пример №2 Три торговых склада - P, Q, R, - могут поставить некоторое изделие в количестве 9,4, и 8 единиц соответственно. Величины спроса трех магазинов розничной торговли, находящихся в пунктах А, В, и С, на это изделие равны 3, 5 и 6 единицам соответственно. Какова минимальная стоимость транспортировки изделий от поставщиков потребителям? Единичные издержки транспортировки приведены в табл. 2.

Таблица 2

Издержки транспортировки, объемы потребностей и предложений

Решение

В нашем распоряжении имеется информация об издержках, предложении изделий и потребностях в них, но общее предложение превышает общий спрос. Общее количество изделий, которое могут поставить все склады, равно 21, однако, розничным магазинам необходимо только 14 изделий. Следовательно, необходимо ввести фиктивный розничный магазин, потребность которого будет равна 7 изделиям, определяющим избыток предложения. Фактически эти 7 изделий не будут вывезены с торговых складов, поэтому предполагается, что издержки транспортировки для них будут равны нулю. Ниже приводится первая транспортная таблица 3.

Таблица 3

Сбалансированная транспортная таблица

Для нахождения начального допустимого распределения будем использовать метод минимальной стоимости, а затем метод Вогеля. Тем не менее, следует иметь в виду того, что на практике требуется применение только одного из методов.

Метод 1. Метод минимальной стоимости

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

2. Производится корректировка оставшихся объемов предложения и потребности.

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

4. Если наименьшее значение стоимости соответствует более чем одной клетке таблицы, выбор осуществляется случайным образом.

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

Стоимость = (3·1) + (4·10) + (1·20) + (2·5) + (4·7) + (7·0) = 101 руб.

Мы еще не можем сказать, является ли данное распределение перевозок наиболее дешевым, однако, оно позволяет получить некоторую реальную стоимость.

Таблица 4

Начальное распределение ресурсов, полученное методом минимальной стоимости

Торговый склад	Розничный магазин	Общее предложение
А (V1)	В (V2)	С (V3)	Фиктивный
P (U1)	-		-		23		71
Q (U2)	-		45		-		-
R (U3)	32		16		44		4•
Общая потребность

Проверка наоптимальность

m — число поставщиков

n — число потребителей

U₁+V₃=5 Положим: 1)U₁ = 0 V₃ = 5

U₁+V₄=0 2) V₄ = 0

U₂+V₂=10 6)U₂ = -8

U₃+V₁=1 4) V₁ = -1

U₃+V₂=20 5) V₂ = 18

U₃+V₃=7 3)U₃ = 2

S₁₁ = 10-(U₁+V₁) = 10-(0-1) = 11

S₁₂ = 20-(U₁+V₂) = 20-(0+18) =2

S₂₁ = 2-(U₂+V₁) = 2-(-8-1) = 11

S₂₃ = 8-(U₂+V₃) = 8-(-8+5) = 11

S₂₄ = 0-(U₂+V₄) = 0-(-8+0) = 8

S₃₄ =0-(U₃+V₄)=0-(2+0) = -2 (при отрицательном значении стоимости перевозки необходимо перераспределение)

Находим коэффициенты.

U₁+V₃=5 Положим: 1) U₁=0 V₃=5

U₁+V₄=0 2) V₄=0

U₂+V₂=10 5) U₂=-10

U₃+V₁=1 6) V₁=1

U₃+V₂=20 4) V₂=20

U₃+V₄=0 3) U₃=0

S₁₁=10-(U₁+V₁)=10-(0+1)=9

S₁₂=20-(U₁+V₂)=20-(0+20)=0

S₂₁=2-(-10+1)=11

S₂₄=0-(-10+0)=10

S₂₃=8-(-10+5)=11

S₃₃=7-(0+5)=2

С = 6 ^. 5 + 4^. 10 + 3 ^. 1 + 1^. 20 = 30 + 40 + 3 + 20 =93 рубля

Ответ: минимальная стоимость транспортировки составляет 93 рубля.

Поиск по сайту: