Лекции.Орг


Поиск:




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




 

Транспортная задача является специальной задачей линейного программирования.
Суть ее заключается в следующем. Есть m поставщиков грузов А1, А2, …, Аm и n потребителей B1, B2, …, Bn этих грузов. Известны запасы грузов у поставщиков а1, а2, …, аm и потребности в этих грузах b1, b2, …, bn соответственно, а также тарифы перевозок сij.

Требуется:

1. Все запасы изъять.

2. Все потребности удовлетворить.

3. Чтобы стоимость доставки грузов была минимальной.

Математическая модель задачи следующая:

Как видим, математическая модель записана в каноническом виде, так как в ней присутствует условие равновесия (2), но это идеальный случай. Чаще всего можно столкнуться со следующим:

a. запасы превышают потребности и тогда приходится вводить фиктивного потребителя с нулевым тарифом;

b. потребности превышают запасы – вводят фиктивного поставщика с нулевым тарифом.

Почему тарифы равны нулю? Вывод очевиден – надо следовать критерию задачи.
Более подробную информацию по теории транспортной задачи можно посмотреть в учебниках по исследованию операций либо математическому программированию.
Любая задача ЛП, в том числе и транспортная задача, решается в два этапа.
Сначала находят опорный план, затем его подвергают анализу и в конечном итоге находят оптимальный план. Для транспортной задачи существуют и прямые методы – это распределительный метод, дельта-метод и метод дифференциальных рент. Но независимо от применяемого математического метода полученное решение проверяют на оптимальность с помощью метода потенциалов.
Рассмотрим задачу: имеются три поставщика грузов и три потребителя этих грузов. Запасы грузов составляют 150, 100 и 300 ед., потребности в них равны 100, 250 и 200 ед. соответственно. Тарифы перевозок также известны:

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

Вначале найдем опорный план с помощью диагонального способа без учета тарифов.

Для решения задачи составляется таблица перевозок:

Правила заполнения таблицы несложные. Заполнение начинают с левой верхней клетки, в которую записывают грузопоставку исходя из наличия груза и потребности в нем. Наличие груза у поставщика А1 составляет 150 ед. а потребность потребителя В1 в грузе равна 100 ед. Запишем этот груз полностью, а остаток 50 ед. запишем следующему потребителю, третью ячейку вычеркнем, так как весь груз у первого поставщика изъят:

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

Как видим, при распределении грузов тарифы не учитывались. Расходы на доставку грузов составляют:

f = 3×100 + 2×50 + 1×100 + 3×100 + 3×200 = 1400 у.е. Найдем опорный план методом минимального элемента с учетом тарифов перевозок и сравним решения. Составим такую же таблицу перевозок, но вот порядок заполнения будет отличен от предыдущего случая:

Грузопоставки начнем вписывать в клетку, которая имеет наименьший тариф. Если таких клеток несколько, то начинать записывать можно в любую из них. Минимальный тариф в таблице равен единице, а так как таких клеток три, то выберем первой например ячейку А1В3. Размер грузопоставки определяется исходя из наличия груза у поставщика и потребности потребителя. Наличие груза у первого поставщика равно 150 ед., потребность равна 200 ед. Мы забираем весь груз у А1 и записываем:

Заполняем следующую клетку с тарифом, равным единице:

Оставшиеся клетки с одинаковым тарифом последовательно заполняем:

Вычислим транспортные расходы: f = 1×100 + 3×50 + 1×150 + 3×250 = 1150 у.е. Как видим, опорный план, полученный методом минимального элемента, дает лучший результат, чем диагональный способ. После того, как получено допустимое решение, его надо проверить на оптимальность с помощью метода потенциалов. Перед проверкой убеждаемся, что число заполненных клеток равно соотношению m+n-1. В нашей таблице их 3+3-1=5.

Признак оптимальности: решение оптимально, если во всех свободных клетках выполняется неравенство: αi + cij ≥ βj, где αi и βj – потенциалы, cij – тарифы перевозок. Вычислим αi и βj с помощью выше указанного неравенства:

Принято считать, что α1 всегда равно 0. Если не сделать это допущение, то задача не будет иметь решение. Вычисления остальных значений потенциалов производят по базовым (заполненным) клеткам:
α1 = 0

β1 = 3 + 0 = 3

β2 = 2 + 0 = 2

α2 = 2 — 1 = 1

α3 = 2 — 3 = -1

β3 = -1 + 3 = 2

Проверку на оптимальность делают по свободным клеткам с помощью этого же неравенства:

А1В3: 0 + 1 ≥ 2 – нет

А2В1: 1 + 1 ≥ 3 – нет

А2В3: 1 + 4 ≥ 2 – да

А3В1: -1 + 2 ≥ 3 – нет

В результате проверки мы выявили три недостаточные клетки. Находим цикл пересчета:

цикл пересчета – это ход ладьи по базовым клеткам с чередованием знаков «+» и «-», начиная с недостаточной клетки и замыкаясь в ней же.

В клетках с минусовыми отметками выбирает минимальное число. В нашем случае это число равно 100. Пересчет делают следующим образом: где стоит знак «-» это число отнимают, а где «+» то прибавляют. Значения, не входящие в цикл пересчета переписывают без изменений. Получает таблицу, в которой соотношение m+n-1 не выполняется, и поэтому выбираем клетку с минимальным тарифом и, проставляя в ней ноль, считаем ее условно базовой:

Вначале транспортные расходы составляли 1400 у.е. Считаем сейчас: f2 = 2×100 + 2×150 + 1×100 + 3×200 = 1200 у.е. Уменьшение этого показателя говорит о том, что мы на верном пути. Полученное решение снова проверяем на оптимальность:

 

Проверка выявляет одну недостаточную клетку, для которой находим цикл пересчета:

А1В1: 0 + 3 ≥ 0 – да

А1В3: 1 + 0 ≥ 1 – да

А2В1: 1 + 1 ≥ 0 – да

А3В2: -2 + 3 ≥ 2 – нет

В отрицательных клетках из двух значений выбираем число 150, которое отнимаем, где знак «-» и прибавляем где знак «+»:

 

Транспортные расходы:f3 = 2×100 + 3×150 + 1×100 + 1×150 + 3×50 = 1050 у.е.
Проверяем снова на оптимальность и убеждаемся, что найден оптимальный план:

А1В1: 0 + 3 ≥ 0 – да

А1В2: 0 + 2 ≥ 1 – да

А2В1: 0 + 1 ≥ 0 – да

А2В3: 0 + 4 ≥ 1 – да

 

Ответ: f = 1050 у.е.





Поделиться с друзьями:


Дата добавления: 2016-11-23; Мы поможем в написании ваших работ!; просмотров: 1326 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

80% успеха - это появиться в нужном месте в нужное время. © Вуди Аллен
==> читать все изречения...

780 - | 730 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.