Метод минимального элемента
При построении первоначального плана методом северо-западного угла совершенно не учитываются тарифы, потому план получается далеким от оптимального. Для решения задачи приходится делать много приближений (шагов). Способ минимального элемента учитывает тарифы и потому позволяет найти план, более близкий к оптимальному.
Алгоритм метода.
1. Располагаем все клетки таблицы в очередь по мере возрастания тарифов, начиная с минимального. В нашем примере (табл. 19) на первом месте будет клетка с тарифом 1, потом с тарифами 2, 3, 4 (три клетки), 6, 7 (две клетки) и т. д.
Таблица 19
Метод минимального элемента
Пункты назначения Пункты отправления | B1 | B2 | B3 | B4 | Запасы груза |
A1 | – | – | |||
А2 | – | – | – | ||
A3 | – | ||||
Потребности в грузе |
2. В клетку с минимальным тарифом записываем наибольшую возможную перевозку (исходя из запасов и потребностей), затем заполняем очередную по порядку клетку и т. д., пока не получим план. При этом должен строго соблюдаться баланс по строкам и столбцам. Пустые клетки прочеркиваем, а не заполняем нулями (чтобы было видно, что они не входят в план табл. 19).
|
|
Полученный план будет ациклическим и будет состоять не более чем из (m + n — 1) компонент. Этот план и принимаем за исходный. Он будет лучше плана, построенного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений.
Распределительный метод решения транспортной задачи отличается от метода потенциалов изменением вычислительного процесса и иным по форме критерием оптимальности.
Алгоритм метода.
1. Отыскиваем первоначальный ациклический план, содержащий (m + n — 1) компонент.
2. Включаем в набор свободную клетку, строим для нее цикл, означиваем его, приписывая свободной клетке знак плюс, и вычисляем по этим знакам алгебраическую сумму тарифов, стоящих во всех вершинах цикла. Полученное число с его знаком записываем внутри свободной клетки.
3. Проделываем указанную в п. 2 операцию для каждой свободной клетки, строя всякий раз свой цикл пересчета. В результате в каждой свободной клетке появится число (положительное, отрицательное или ноль).
4. Если все полученные числа неотрицательны, то найдено оптимальное решение, минимизирующее функционал. При наличии чисел разных знаков переходим к пункту 5.
5. Включаем в план свободную клетку, в которой стоит наибольшее по модулю отрицательное число, в отрицательной полуцепи того цикла, который соответствует выбранной клетке, отыскиваем наименьшую перевозку и делаем сдвиг по циклу на это число. В результате находим новый допустимый план.
|
|
6. Испытываем этот план на оптимальность, т. е. для каждой свободной клетки строим цикл пересчета и вычисляем алгебраическую сумму тарифов. При неоптимальности плана снова включаем свободную клетку в план и делаем сдвиг по соответствующему циклу. Так продолжаем до тех пор, пока план не будет оптимальным.