Нахождение минимальных затрат при распределении товаров среди магазинов методами решения транспортной задачи

Если оно выполнено, то план оптимален, если нет то улучшаем план.

4. Улучшение плана:

a. При не выполнении второго условия в клетку заносим нарушение со знаком плюс. Такие клетки называются потенциальными.

b. Среди всех потенциальных клеток выбираем клетку с наибольшим

нарушением.

c. Строим для выбранной клетки

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

За исключением той клетки, для которой строится контур

d. Вершины контура поочерёдно помечаем знаками плюс и минус, начиная с клетки, для которой строится контур.

e. Среди клеток помеченных знаком минус выбираем наименьшею перевозку и на эту величину увеличиваем перевозку в клетках помеченных знаком плюс и уменьшаем в клетках помеченных знаком минус в результатах переназначения освобождается одна клетка.

5. Вновь полученный план проверяем на оптимальность.

1.2.4 Метод аппроксимации Фогеля

Данный метод состоит в следующем:

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

2. Находят max Δcij и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

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

ГЛАВА 2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

2.1 Постановка задачи

Имеются три пункта поставки мониторов: Склад №1, Склад №2, Склад №3. И пять магазинов: Магазин "Терабайт", Магазин "Лидер", Магазин "Эксперт", Магазин "Ока-сервис", "Владимирский рынок", потребления этого товара. Найти оптимальный распределения товаров с минимальными затратами.

Дано:

Склад №1=200 шт.

Склад №2=250шт.

Склад №3=200шт.

Требуется доставить штук:

Магазин "Терабайт"= 190шт.

Магазин "Лидер"= 100 шт.

Магазин "Эксперт" = 120 шт.

Магазин "Ока-сервис" =110 шт.

"Владимирский рынок" =130 шт.

Сетка тарифов:

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

Магазины:

Магазин "Терабайт"= B1

Магазин "Лидер"= B2

Магазин "Эксперт" = B3

Магазин "Ока-сервис" = B4

"Владимирский рынок" = B5

Товары:

Склад №1= A1

Склад №2 = A2

Склад №3= A3

Тогда матрица будет выглядеть так:

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

2.2 Нахождение первоначального плана методом северо-западного угла

Используя построенную матрицу тарифов найдём оптимальный опорный план методом северо-западного угла.

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

Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:

 Скачать реферат