Метод наименьшей стоимости

1.2.2 Метод наименьшей стоимости

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую. И в клетку, которая ей соответствует, помещают меньшее из чисел a_i или b_j . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Алгоритм:

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

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

·  Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п.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.  На каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;

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

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

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

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

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

Дано:

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

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

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

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

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

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

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

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

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

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

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

Магазины:

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

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

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

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

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

Товары:

Склад №1= A₁

Склад №2 = A₂

Склад №3= A₃

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

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

Похожие работы

Транспортная задача линейного программирования

Скачать

47721

13

4

... , является линейной функцией переменных : (2.4)    Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4). Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без ...

Разработка динамических моделей для транспортно-производственной системы

Скачать

38282

9

2

... 16 11 9 45 Радуга 15 15 12 20 Михайлово 2 6 20 Лебедево 7 3 55 Озерное 4 9 25 20 55 25 40 60 3. Разработка динамических моделей для транспортно-производственной системы.   3.1 Однопродуктовая многоэтапная транспортно-производственная модель. Возьмем из задачи, описанной выше, ...

Организация транспортного обеспечения коммерческой деятельности торгового предприятия

Скачать

52995

4

2

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

Задачи маркетинга, решаемые автоматизированными системами

Скачать

74770

0

0

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