Один из методов составления опорного плана перевозок в транспортной задаче называется «методом минимального элемента». Отличаясь простотой, данный метод все же эффективнее чем, к примеру, метод Северо-западного угла. Кроме того, метод минимального элемента («метод наименьшего элемента», «метод минимальной стоимости») понятен и логичен.
При этом методе в транспортной таблице сначала заполняются ячейки с наименьшими тарифами, а потом уже ячейки с большими тарифами. То есть мы выбираем перевозки с минимальной стоимостью доставки груза. Это очевидный и логичный ход. Но, как ни парадоксально, он не всегда приводит к оптимальному плану.
Формирование опорного плана по методу минимального элемента
Опорный план для транспортной таблицы при методе минимального элемента составляется довольно просто.
Подробный разбор решения транспортной задачи методом потенциалов можно найти здесь.
Ключевая идея заключается в следующем: определяем ячейку транспортной таблицы с наименьшим значением тарифа на перевозку груза (если окажется, что есть несколько ячеек с одинаковыми и минимальными тарифами — выбираем любую из них). В эту ячейку выписываем максимально возможный объем груза (Xij), который можно доставить с соответствующего этой ячейке склада на соответствующий завод.
Объемы запасов и потребностей уменьшаются на величину груза. Если запасы склада исчерпаны, то полностью вычеркиваем эту строку таблицы. Если потребности завода полностью удовлетворены — полностью вычеркиваем этот столбец таблицы.
Продолжаем в том же духе до тех пор, пока все запасы не будут исчерпаны, а все потребности удовлетворены.
В итоге мы получим опорный план перевозок для транспортной задачи.
- Метод минимального элемента для нахождения опорного плана ТЗ // Электронные курсы НГТУ. URL: http://edu.nstu.ru/courses/mo_tpr/files/3.3.3.html (дата обращения: 5.12.2013)
© Копирование любых материалов статьи допустимо только при указании прямой индексируемой ссылки на источник: Галяутдинов Р.Р.
