Распределительный метод

Метод минимального элемента

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

Алгоритм метода.

1. Располагаем все клетки таблицы в очередь по мере воз­растания тарифов, начиная с минимального. В нашем примере (табл. 19) на первом месте будет клетка с тарифом 1, потом с тарифами 2, 3, 4 (три клетки), 6, 7 (две клетки) и т. д.

Таблица 19

Метод минимального элемента

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

Полученный план будет ациклическим и будет состоять не более чем из (m + n — 1) компонент. Этот план и принимаем за исходный. Он будет лучше плана, построен­ного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений.

Распределительный метод решения транспортной задачи от­личается от метода потенциалов изменением вычис­лительного процесса и иным по форме критерием оптималь­ности.

Алгоритм метода.

1. Отыскиваем первоначальный ациклический план, содер­жащий (m + n — 1) компонент.

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

3. Проделываем указанную в п. 2 операцию для каждой свободной клетки, строя всякий раз свой цикл пересчета. В ре­зультате в каждой свободной клетке появится число (положи­тельное, отрицательное или ноль).

4. Если все полученные числа неотрицательны, то найдено оптимальное решение, минимизирующее функционал. При наличии чисел разных знаков переходим к пункту 5.

5. Включаем в план свободную клетку, в которой стоит наибольшее по модулю отрицательное число, в отрицательной полуцепи того цикла, который соответ­ствует выбранной клетке, отыскиваем наименьшую перевозку и делаем сдвиг по циклу на это число. В результате находим новый допу­стимый план.

6. Испытываем этот план на оптимальность, т. е. для каж­дой свободной клетки строим цикл пересчета и вычисляем ал­гебраическую сумму тарифов. При неоптимальности плана снова включаем свободную клетку в план и делаем сдвиг по соответ­ствующему циклу. Так продолжаем до тех пор, пока план не будет оптимальным.