Курсовая работа: Нахождение минимальных затрат при распределении товаров среди магазинов методами решения транспо

· Из таблицы тарифов выбирают наименьшую стоимость. И в клетку, которая ей соответствует, вписывают меньшее из чисел.

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

· Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п.1, в противном случае задача решена.

1.2.3 Метод потенциалов

Наиболее простым методом ТЗ является метод потенциалов. Потенциалами называются условные числа U_i ,V_j , приписанные определённым образом каждому поставщику и потребителю.

Теорема(условия оптимального плана): Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых клеток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток

Опорный план должен быть не вырожденным (r=m+n-1 – невырожденный план)

Алгоритм решения:

1. Строим начальные планы методом северо-западного угла и методом наименьшей стоимости из них выбираем лучший

_2. Находим потенциалы поставщика и потребителя, пользуясь первым условием оптимальности плана U_i + V_j < C_ij

3. Проверяем второе условие оптимальности плана для свободных клеток

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

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

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

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

нарушением.

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

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

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

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

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

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

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

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