ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ МЕТОДОМ ПОТЕНЦИАЛОВ

ВТОРОЕ ОПОРНОЕ РЕШЕНИЕ

Построив исходное опорное решение, необходимо определить некоторую последовательность опорных решений, при этом каждое следующее решение должно быть лучше предыдущего. Для этого используем метод потенциалов, основанный на следующей теореме. Для того чтобы опорное решение транспортной задачи было оптимальным, необходимо и достаточно, чтобы существовала система чисел U₁, U₂,…,U_m и V₁, V₂,…, V_n, удовлетворяющих условиям (условиям оптимальности):

, если ; (2)

, если . (3)

Набор величин U₁, U₂,…,U_m приписывается строкам транспортной таблицы: U₁ – первой строке, U₂ – второй строке и т.д. Аналогично, набор величин V₁, V₂,…, V_n приписывается столбцам транспортной таблицы: V₁ – первому столбцу, V₂ – второму столбцу и т.д. Эти величины называются потенциалами соответствующих столбцов или строк.

Алгоритм получения оптимального решения методом потенциалов включает в себя последовательное выполнение следующих шагов:

1) по соотношению (2) рассчитываем систему потенциалов;

2) используя соотношение (3), выявляем нарушения и проверяем решение на оптимальность (если условие выполняется для всех ячеек без перевозок, то решение является оптимальным и процесс оптимизации закончен; в противном случае переходим к следующему пункту алгоритма);

3) улучшаем план перевозок, получаем новое опорное решение и переходим к пункту 1 алгоритма. Выполнение пункта 1 заключается в определении m+n неизвестных (общее число величин потенциалов U₂,…,U_m и V₁, V₂,…, V_n) в системе m+n–1 уравнений (количество ячеек с перевозками в опорном решении). Для решения системы потенциалов задаемся потенциалом одного из поставщиков или потребителей (произвольно выбранным числом), а далее вычисляем потенциалы для всех остальных строк и столбцов.

Соотношение (3), используемое в пункте 2, можно переписать в виде:

, где , если . (4)

Величины v_ij называют невязками, их вычисляют для всех ячеек без перевозок. Если хотя бы в одной ячейке невязка больше нуля, то план перевозок может быть улучшен. Если все невязки неположительные, то опорное решение является оптимальным.

Пункт 3 приведенного выше алгоритма направлен на улучшение плана перевозок и состоит в организации замкнутого контура (цикла) по следующим правилам:

· контур начинается с ячейки, имеющей максимальную невязку v_max (вершине контура в этой ячейке присваивается № 1);

· все остальные вершины контура обязательно содержат перевозки;

· все линии контура являются ортогональными (т.е. горизонтальными или вертикальными);

· допускаются самопересечения контура.

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

Величинаперераспределения q равна наименьшему значению из перевозок, стоящих в четных вершинах цикла. Объемы перевозок в вершинах контура перераспределяют следующим образом: к объемам перевозок в нечетных вершинах добавляют величину q, а из объемов в четных вершинах вычитают эту же величину. В результате получают улучшенный план, в котором общие затраты на перевозку меньше, чем в предыдущем на величину q×v_max.

Новый план также является опорным. В каждой строке и столбце в одной ячейке объем увеличился, а в другой – уменьшился на одну и ту же величину. Количество вершин с перевозками в новом плане по-прежнему должно быть не больше, чем m+n–1.

В случаях, когда количество ячеек с перевозками уменьшилось, то такой план называется вырожденным. Здесь невозможно решить систему потенциалов. Для выхода из этой ситуации, в одну из ячеек без перевозок проставляют фиктивную перевозку малого объема – e. И далее решают задачу как невырожденную, а в оптимальном плане величину e заменяют нулем.

Произведем нахождение оптимального плана на примере нашей задачи.

Рис. 1

Рис. 2

Рис. 3

Дата добавления: 2015-06-30; просмотров: 142; Нарушение авторских прав

Мы поможем в написании ваших работ!