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

Заполнение распределительной таблицы начинают с клетки (1;1), при этом . Далее смещаются или по строке вправо или по столбцу вниз до клетки . Заполненные клетки должны распространяться так, чтобы их можно было соединить ломаной линией, звенья которой взаимно перпендикулярны.

Пример. Построить методом северо-западного угла начальный опорный план для транспортной задачи: поставщики а = (20; 30; 40); потребители = (15; 35; 20; 20); тарифы перевозок

Найти стоимость перевозок.

Решение. Строим распределительную таблицу и находим груз х ₁₁ = min (20; 15) = 15. По первому столбцу не перемещаемся, так как спрос І потребителя удовлетворен. Перемещаемся по І строке в клетку (1; 2):

х ₁₂ = min (а ₁ – х ₁₁; b ₂) = min (5; 35) = 5.

Теперь переходим по ІІ столбцу в клетку (2; 2):

х ₂₂ = min (30; b ₂ – х ₁₂) = min (30; 30) = 30.

Так как спрос ІІ потребителя удовлетворен и у ІІ поставщика продукция уже выбрана, то переходим к клетке (3; 3):

х ₃₃ = min (40; 20) = 20.

х ₃₄ = min (а ₃ – х ₃₃; b ₄) = min (20; 20) = 20.

Таким образом, получен план перевозок:

 

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

.

Б) Метод минимального элемента (наименьшей стоимости).

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

Пример. Построить начальный опорный план методом минимальной стоимости и найти транспортные расходы для транспортной задачи: поставщики а = (20; 30; 40); потребители = (15; 35; 20; 20); тарифы перевозок

Решение. Строим распределительную таблицу и начинаем ее заполнять с клетки (2; 1), т.к. в ней наименьший тариф х ₂₁ = min (30; 15) = 15.

 

Потом заполняем клетку (3; 2) с тарифом с ₃₂ = 3;

х ₃₂ = min (40; 35) = 35.

Далее х ₃₃ = min (а ₃ – х ₃₂; b ₃) = (5; 20) = 5;

х ₁₄ = min (20; 20) = 20;

х ₂₃ = min (а ₂ – х ₂₁; b ₃ – х ₃₃) = min (15; 15) = 15.

.

Сравнивая значение Z в а) и б), видим, что учитывая стоимости перевозок, затраты при втором методе значительно меньше.

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

В пунктах а) и б) , а число заполненных клеток 5. Следовательно, полученные планы – вырожденные.

Метод потенциалов. Признак оптимальности опорного плана.

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

I. для всех заполненных клеток; (5)

II. для всех пустых клеток. (6)

На основании первого условия оптимальности потенциалы находят из условий и один, произвольно выбранный, потенциал приравнивают к нулю, например .

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

Переход к нехудшему опорному плану.

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

Приведем примеры разновидностей форм циклов:

В каждом случае только одна вершина цикла находится в незаполненной клетке. Ее называют началом цикла и определяют по наибольшему нарушению условия оптимальности (6), т.е. по максимальной оценке . Клетке начала цикла присваивают знак «+», во всех остальных вершинах цикла знаки чередуют «–»,«+» и т.д. Из клеток цикла со знаками «–» выбирают ту, в которой находится минимальный груз. Это и будет то количество груза, которое нужно перераспределить по циклу, т.е. в клетке со знаком «+» это количество груза прибавляется, а со знаком «–» – вычитается. Клетки, которые не задействованы в цикле, остаются неизменными.

Таким образом, получаем новый опорный план. Подсчитываем транспортные расходы, которые должны быть не более предыдущих. В противном случае где-то допущена ошибка. Новый план опять проверяем на оптимальность, используя условия (5) и (6). Если план оптимальный, то задача решена. Если же план опять не оптимальный, то работаем, согласно пункту 3) до получения оптимального плана и нахождения Z_min.