21. Распределительный метод решения транспортной задачи

Решение задачи включает

- предварительный этап,

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

- составление оптимальных планов.

1. Предварительный этап – составляем предварительный опорный план прикрепления.

   1. Способ «северо-западного угла» (диагональный способ).

Распределение поставок производят с верхнего левого угла и далее по строкам по мере исчерпывания плана.

2. Способ двойного предпочтения

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

2. Проверка предварительного плана на оптимальность распределительным методом.

Суть данного метода состоит в том, для каждой свободной слетки проверяемого планом составляются контура (цепочки) по следующим правилам:

1. Начало контура цепочки в свободной клетке

2. Контур представляет собой многоугольник с четным числом вершин.

Первая вершина – свободная клетка, остальные вершины(повороты) в клетках предварительного плана.

Отдельные отрезки контура принадлежат или одной строке или одному столбцу.

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

4. Отрезки могут пересекаться

5. Отдельные отрезки (стороны контура) могут пересекаться

По составленным многоугольникам (цепочка, контурам) можно создать цепочку из цифр:

Первая цифра – коэффициент стоящий в свободной клетке

Коэффициенты стоящие в углах многоугольника в углах поворота.

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

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

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

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

22. Применение метода потенциалов для решения транспортной задачи.

Решение задачи включает

- предварительный этап,

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

- составление оптимальных планов.

3. Предварительный этап – составляем предварительный опорный план прикрепления.

   1. Способ «северо-западного угла» (диагональный способ).

Распределение поставок производят с верхнего левого угла и далее по строкам по мере исчерпывания плана.

2. Способ двойного предпочтения

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

4. Проверка предварительного плана на оптимальность методом потенциалов

Суть данного метода состоит в том, что к строкам и столбцпм матрицы подбираются вспомогательные числа (потенциалы α – потенциал строки и β – потенциал столбца)

Из условия, что для занятых клеток сумма потенциалов строки и столбца равны коэффициенту стоящему в этой клетке.

–для занятых клеток

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

Далее в качестве проверки рассчитаем характеристики незагруженных клеток по формуле:

–для незагруженных клеток

Наличие отрицательного значения характеризующего пустую клетку свидетельствует о возможности улучшения плана.

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

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