Основная теорема теории транспортных задач. Сведение распределительных задач к закрытым транспортным задачам.

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

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

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

Методы нахождения опорных планов транспортной задачи.

Опорный план является допустимым решением транспортной задачи.

Существует 4 метода нахождения опорных планов:

1.Метод северо-западного угла

2.Метод минимального элемента

3.Метод двойного предпочтения

4.Метод Фогеля

Сущность этих методов состоит в том, что опорный план находят последовательно за m+n-1 шагов, на каждом из которых в таблице планирования заполняют одну клетку, которую называют занятой.

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

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

Метод северо-западного угла.

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

Метод минимального элемента

Цель построить опорное решение достаточно близкое к оптимальному, используя матрицу стоимости. На каждом шаге заполняется только одна клетка таблицы соответствующая минимальной стоимости и исключается только одна строка (поставщик) или столбец (потребитель)

Метод двойного предпочтения

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

Метод Фогеля

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

Дата добавления: 2015-08-20