Решение транспортных задач методом

ПОТЕНЦИАЛОВ

Метод потенциалов представляет собой упрощенную модификацию распределительного метода, в котором предусматривается замена рассмотренного выше алгоритма распределительного метода в части «Анализ плана на оптимальность» на упрощенную процедуру, исключающую необходимость построения замкнутых контуров. Это обеспечивает методу потенциалов ряд преимуществ по сравнению с обычным распределительным методом: становится возможной реализация алгоритма метода на ЭВМ и, соответственно, решение задач с большим количеством поставщиков и потребителей.

Методика решения транспортной задачи методом потенциалов по этапам решения та же, что и в распределительном методе:

- постановка задачи;

- составление исходной матрицы;

- составление исходного допустимого базисного плана;

- анализ плана на оптимальность;

- улучшение плана;

- контроль решения задачи.

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

1. Вычисляются потенциалы α и β через коэффициенты С _ij занятых клеток плана;

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

3. Вычисляются числовые характеристики для неравенств, не отвечающих условиям оптимальности плана.

К вычислению потенциалов α и β приступают после составления исходного допустимого базисного плана по алгоритму распределительного метода.

Под потенциалами α и β понимаются относительные числа (оценки), выражающие в экономическом смысле, например, стоимость единицы перевозимого груза в i –м пункте отправления (потенциал α _i) и в j -м пункте назначения (потенциал β _j).

Вычисление потенциалов выполняются через коэффициенты С _ij в занятых клетках плана по следующим формулам:

              β _j = α _i + С _ij,                                                              (2.8)

             α _i = β _j - С _ij,                                                               (2.9)

где α _i – потенциал, относящийся к пункту отправления;

β _j – потенциал, относящийся к пункту назначения;

С _ij – коэффициент, выражающий, по условиям задачи, расстояние или стоимость перевозки единицы груза от i –го поставщика до j -го потребителя.

В матрице задачи для записи потенциалов α _i выделяется дополнительный столбец, а для потенциалов β _j дополнительная строка.

Вычисление потенциалов по формулам 2.8 и 2.9 можно начинать с любой строки (столбца). Однако при этом необходимо соблюдать следующую последовательность действий:

- исходному (первоначальному) значению α _i (или β _j) присваивается произвольное круглое число (10, 100 и т.д.) с таким расчетом, чтобы при вычислении потенциалов не было отрицательных чисел;

- выбор формулы расчета зависит от того, значение какого потенциала известно, а значение какого нужно определить. Например, если в качестве исходного задан потенциал α₁ =10, то необходимо использовать формулу 2.8 для расчета недостающего потенциала β _j. Если же известен потенциал β _j, а следует определить значение потенциала α _i, то используют формулу 2.9;

- вычисление потенциалов по формулам выполняется с использованием строки и столбца, на пересечении которых находится клетка, занятая поставкой. Если, например, занятая клетка стоит на пересечении первой строки и третьего столбца матрицы и известен исходный потенциал α₁ =10, то через коэффициент С_1.3 рассчитываем потенциал β₃= α₁+ С_1.3=10+3=13. Если же по третьему столбцу стоит еще одна занятая клетка, но по другой строке, то для нее рассчитывается потенциал α _i через уже найденное значение потенциала β₃ и коэффициент данной клетки. Например, С_3.3 =6, α₁ = β₃ – С_3.3 = 13 – 6=7.

Аналогичным образом вычисляют все потенциалы α _i и β _j. После этого приступают к анализу плана на оптимальность.

Анализ плана на оптимальность выполняется путем построения неравенства для каждой свободной клетки плана и проверки их на соответствие следующим условиям:

      α _i + С _ij ≥ β _j (при решении задачи на минимум), или (2.10)

      α _i + С _ij ≤ β _j (при решении задачи на максимум)         (2.11)

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

Если задача решается на минимум (Z → min), то все неравенства для свободных клеток должны быть типа 2.10. Если хоть одно из неравенств не соответствует данному типу (например, получилось ≤), то план не оптимален и нуждается в улучшении.

Для неравенств, которые не соответствуют требованиям оптимальности (формуле 2.10 или 2.11 в зависимости от функции цели в задаче) вычисляются характеристики, для последующего улучшения плана по формуле:

            ∑ _ij = α _i + С _ij – β _j                                                              (2.12)

Порядок улучшения не оптимального плана тот же, что и в распределительном методе.

Для контроля значение целевой функции можно вычислить по формуле:

                                                                             (2.13)

ПРИМЕР РЕШЕНИЯ ЗАДАЧИ МЕТОДОМ ПОТЕНЦИАЛОВ

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

Для этого в прежнем исходном плане (таблица 2.4) выделим столбец для записи потенциалов α _i и строку – для потенциалов β _j. Исходный план примет, следующий вид (таблица 2.7).

Таблица 2.7

Исходный план

1800