Метод потенциалов для решении ТЗ.

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

Каждая ячейка (i, j) таблицы хранит информацию о цене (cij) и о количестве перево- зимого товара (xij). В процессе решения задачи часть клеток будем называть базисными (их всегда будет m + n − 1), а остальные — небазисными (или свободными).

Aлгоритм

Шаг 0. Замкнуть задачу, если она не замкнута.

Шаг 1 Нарисовать начальную таблицу.

Шаг 2 Рассчитать начальный план перевозок (например, методом северо-западного угла) и выделить базисные клетки. Вычислить значение целевой функции.

Шаг 3 Рассчитать значения потенциалов. Положить u1 = 0 (или любому другому чис- лу). Остальные потенциалы рассчитать с помощью базисных клеток, исходя из уравнения ui + vj = cij

Шаг 4 Для свободных клеток рассчитать оценки sij = cij − ui − vj . Если все sij > 0, то найдено оптимальное решение. Перейти на шаг 6. Иначе выполнить шаг 5.

Шаг 5 Из небазисных клеток выбрать ту, у которой оценка sij минимальна и для нее выполнить следующую процедуру:

∙ Построить цикл для этой клетки. Цикл — это замкнутая ломаная линия, которая чередует вертикальное и горизонтальное направления и проходит только по базисным клеткам. В исходной клетке поставить « + » и далее по циклу расставить, чередуя, « + » и « − ».

∙ Вычислить λ = min{xij : «-»}. Клетку, на которой достигается этот минимум, убрать из базиса (только одну), а клетку (i, j) (у которой минимальная оценка sij) сделать базисной.

∙ Нарисовать новую таблицу, с пересчитанным планом перевозок: для клеток с « + » прибавить λ к xij а для клеток с « − » — вычесть. Остальные клетки остаются как были. Пересчитать целевую функцию: z ′ = z + min sij · λ.

Перейти на шаг 3.

Шаг 6 Конец алгоритма.

 На шаге 3 у нас m + n − 1 уравнение и n + m неизвестных. Поэтому возникает неоднозначность, разрешить которую можно, определив одну из переменных заранее (например, u1 = 0).

Пример

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

Задача не замкнута, поэтому добавляем фиктивный магазин (свалку) мощностью 5, стоимость перевозки в который равна нулю. После этого потребности магазинов и воз- можности складов равны:

Построим начальную таблицу и рассчитаем оценки методом северо-западного угла. Базисные клетки выделим цветом:

Рассчитаем потенциалы и значение целевой функции:

Оценки для свободных клеток равны: s12 = −10, s13 = −5, s23 = 0, s31 = 0. Среди них есть отрицательные, значит, решение не оптимально. Выберем клетку с минимальной оценкой, это (1, 2), построим через неё цикл и расставим знаки:

Цикл здесь: (1, 2) → (2, 2) → (2, 1) → (1, 1) → (1, 2). Минимальное из тех перевозок, где стоит знак «−», равна 5 (в клетке (2, 2), поэтому она покидает базис). Значение λ = 5. Таким образом, новое значение целевой функции будет равно z ′ = 200 + (−10)· 5 = 150, а новый план перевозок записан в следующей таблице:

Повторяем процедуру сначала, рассчитывая потенциалы и т. д

s13 = 5, s22 = 10, s23 = 10, s31 = −10. Цикл: (3, 1) → (1, 1) → (1, 2) → (3, 2) → (3, 1). λ = 5.

s11 = 10, s13 = 5, s22 = 0, s23 = 0. Решение оптимально. z = 100, x12 = 10, x21 = 5, x31 = 5, x33 = 5. Пять единиц товара ушло на свалку (избыток).

 

⇐ Предыдущая12345678910

Поделиться: