Методы решения транспортных ЗЛП

Транспортную задачу можно решать симплексным методом. Но даже для небольших значений n и m получается громоздкая система линейных уравнений с большим числом неизвестных, что усложняет вычисления. В связи с этим для решения транспортной задачи разработаны специальные методы.

Наиболее распространенным методом решения транспортных задач является метод потенциалов.

Решение задачи методом потенциалов включает следующие этапы:

1. разработку начального плана (опорного решения);

2. расчет потенциалов;

3. проверку плана на оптимальность;

4. поиск максимального звена неоптимальности (если условие п.3 не было достигнуто);

5. составление контура перераспределения ресурсов;

6. определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;

7. получение нового плана.

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

Для транспортной задачи существует несколько методов отыскания опорного плана:

· метод северо-западного угла;

· метод наименьших элементов (в строке, в столбце);

· метод двойного предпочтения и т. д.

Метод северо-западного угла.

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

· количество компонент не должно превосходить числа n+m-1;

· должны соблюдаться ограничения (6) и (7).

Метод наименьших элементов.

Заполнение таблицы начинается с клеток с минимальным значением стоимости перевозок.

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

Метод двойных предпочтений.

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

После нахождения опорного плана используют систему потенциалов. каждой клетке, т.е. каждому поставщику присваивают потенциал u_i, а каждому столбцу-потребителю присваивают потенциал v_j.

Выполняется следующее равенство: цена в пункте потребителя равна цена поставщика плюс транспортные расходы.

V_j = U_i + C_ij (11).

Далее следует проверка решения на оптимальность путем составления матрицы оценок:

d_ij = (C_ij + U_i) - V_j (12).

Каждое значение матрицы d для пустой клетки называется оценкой свободной клетки.

Если матрица d содержит отрицательные элементы, то осуществляют перенос по прямоугольнику. В матрице d выбирается такой прямоугольник, чтобы в одной из его вершин лежала клетка с отрицательной оценкой, а в трех других вершинах находились заполненные клетки. Свободную вершину отмечают знаком плюс, вторую вершину (движение по часовой стрелке) знаком минус, третью – знаком плюс и четвертую – знаком минус. Далее проверяется, принесет ли планируемый перенос улучшение плана. Если ∑ с⁺ < ∑ с^-, то план улучшится, если ∑ с⁺ > ∑ с^- , то ухудшится. Если эти две суммы равны, то план останется прежним. После выполнения переноса необходимо составить матрицу d и проверить наличие отрицательных элементов. Решение считают оптимальным, если матрица d неотрицательна d_ij ≥ 0. при наличии отрицательных элементов следует еще раз осуществить перенос.

Дата добавления: 2014-01-15