Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 19. Тема: Транспортная задача. Цель: Рассмотреть метод «северо-западного угла». Узнать понятие цикла пересчета и его свойства. Метод потенциалов решения транспортной задачи.

Метод Северо- западного угла. Метод минимальной стоимости (элемента).

ПРИМЕР. В резерве трех железнодорожных станций A, B, C находятся соответственно 60, 80, 100 вагонов. Составить оптимальный план перегона этих вагонов к 4-ем пунктам погрузки хлеба, если пункту 1 необходимо 40 вагонов, 2 – 60, 3 – 80, 4 – 60. Стоимость перегонов одного вагона со станции A в в указанные пункты соответственно равны 1, 2, 3, 4 ден.ед., со станции B – 4, 3, 2, 0 ден.ед. и со станции C – 0, 2, 2, 1 ден.ед..

m = 3; n = 4; m+n –1 = 6 => План опорный

Общая стоимость составленного плана: Z=40·1+20·2+40·3+40·2+40·2+60·1= =420 Это не оптимальное решение.

Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то очевидно, что план будет ближе к оптимальному.

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

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

Итак, опорный план трансформированной задачи построен, теперь надо из него получит оптимальный. Можно было получить оптимальный план используя симплекс-метод, но в нашем случае симплексная таблица будет содержать mn неизвестных, что приведет к громоздким вычислениям.

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

Метод потенциалов.

Числа и называют потенциалами поставщиков и потребителей.

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

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

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

Выбор клетки в которую необходимо послать перевозку: транспортная задача линейного программирования решается на min линейной функции, поэтому алгоритм ее решения тот же, что и алгоритм симплекс-метода. Загрузке подлежит в первую очередь клетка, которой соответствует

Построение цикла и определение величины перераспределения груза: отмечаем знаком « + » незанятую клетку, которую надо загрузить (знаки (-;+) чередуются). Затем находим min, где – перевозки, стоящие в вершинах цикла, отмеченных знаком « - ». Величина min определяет сколько единиц груза надо перераспределить.

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

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

Открытая модель транспортной задачи.

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

Вопросы: 1)Чем различаются открытая и закрытая модели транспортной задачи? 2)В чем заключается метод потенциалов решения транспортной задачи?