Глава 4. Транспортная задача

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

В общем виде транспортную задачу можно представить следующим образом: в m пунктах производства имеется однородный груз в количествах , соответственно. Этот груз необходимо доставить в n пунктов назначения в количествах , соответственно. Стоимость перевозки 1 ед.груза (тариф) из пункта в пункт равна .

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

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

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

Если это равенство не выполнено, то транспортная задача называется открытой.

Закрытая транспортная задача

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

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

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

1) поиск исходного опорного решения;

2) проверка этого решения на оптимальность;

3) переход от одного опорного решения к другому.

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

Поиск исходного опорного решения

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

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

Проверка решения на оптимальность

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

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

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

Переход от одного решения к другому

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

Для свободной клетки с строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак «+», затем поочередно расставляются знаки «¾» и «+». У вершин со знаком «¾» выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком «+», и отнимают от грузов у вершин со знаком «¾».

В результате перераспределения груза получается новое опорное решение, которое проверяется на оптимальность и так далее до получения оптимального решения.

Пример 2.4. На складах имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей .

Решение.

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

Таблица исходной транспортной задачи имеет вид

Потребители
Поставщики

Таблица заполняется следующим образом:

1) в правом верхнем углу клеток проставлены тарифы из заданной матрицы тарифов;

2) в левом нижнем углу записываем количество перевозимого груза:

а) берем первый столбец и ищем минимальный тариф, он равен 2 и соответствует клетке первой строки. Проставляем количество груза, равное 90, так как у первого поставщика есть 90 т груза. Однако первому потребителю надо 140 т, следовательно, выбираем из оставшихся двух клеток минимальный тариф. Он равен 3 и соответствует третьей строке. Проставляем в этой клетке 50 (140¾90=50). Спрос первого потребителя удовлетворен;

б) берем второй столбец и ищем минимальный тариф во второй и третьей строке, так как у первого поставщика уже нет свободного груза. Минимальный тариф равен 1 и соответствует второй строке. Проставляет количество перевозимого груза 300. Спрос второго потребителя удовлетворен;

в) берем третий столбец и ищем минимальный тариф во второй и третьей строке, так как у первого поставщика уже нет свободного груза. Минимальный тариф равен 5 и соответствует второй строке. Проставляет количество перевозимого груза 100 (это все, что осталось у второго поставщика). Остаток необходимого груза 60 т проставляем в третьей строке, так как больше нигде груза не осталось. Спрос третьего потребителя удовлетворен.

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

Проверяем решение на оптимальность. Для этого добавим в таблицу строку и столбец .

Потребители
Поставщики
					¾2

Значения в строке и столбце получаются следующим образом:

1) полагаем ;

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

3) далее надо рассматривать ту из занятых клеток, для которой один из потенциалов известен. В нашем случае это клетка , для нее выполняется условие . Получаем, что ;

4) для клетки выполняется условие . Получаем, что ;

5) для клетки выполняется условие . Получаем, что ;

6) для клетки выполняется условие . Получаем, что .

Теперь вычисляем оценки свободных клеток:

;

;

;

.

Наличие положительной оценки свободной клетки свидетельствует о том, что план не оптимален.

Строим цикл для клетки так, чтобы все вершины были занятыми клетками, кроме исходной. Около свободной клетки ставим знак «+», далее знаки «+» и «¾» чередуем по часовой стрелке.

Потребители
Поставщики
		2

У вершин со знаком «¾» выбираем минимальный груз, он равен 60. Прибавляем его к грузам, стоящим у вершин со знаком «+», и отнимаем у вершин со знаком «¾». Получаем новое опорное решение

Потребители
Поставщики
		¾2

Проверяем это решение на оптимальность.

Значения в строке и столбце получаются следующим образом:

1) полагаем ;

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

3) далее надо рассматривать ту из занятых клеток, для которой один из потенциалов известен. В нашем случае это клетка , для нее выполняется условие . Получаем, что ;

4) для клетки выполняется условие . Получаем, что ;

5) для клетки выполняется условие . Получаем, что ;

6) для клетки выполняется условие . Получаем, что .

Теперь вычисляем оценки свободных клеток:

;

;

;

.

Наличие положительной оценки свободной клетки свидетельствует о том, что план не оптимален.

Строим цикл для клетки так, чтобы все вершины были занятыми клетками, кроме исходной. Около свободной клетки ставим знак «+», далее знаки «+» и «¾» чередуем по часовой стрелке.

Потребители
Поставщики
		2

У вершин со знаком «¾» выбираем минимальный груз, он равен 30. Прибавляем его к грузам, стоящим у вершин со знаком «+», и отнимаем у вершин со знаком «¾». Получаем новое опорное решение

Потребители
Поставщики
		¾2

Проверяем это решение на оптимальность.

Значения в строке и столбце получаются следующим образом:

1) полагаем ;

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

3) далее надо рассматривать ту из занятых клеток, для которой один из потенциалов известен. В нашем случае это клетка , для нее выполняется условие . Получаем, что ;

4) для клетки выполняется условие . Получаем, что ;

5) для клетки выполняется условие . Получаем, что ;

6) для клетки выполняется условие . Получаем, что .

Теперь вычисляем оценки свободных клеток:

;

;

;

.

Положительных оценок нет, следовательно, полученное решение является оптимальным и стоимость транспортных расходов составляет руб. По сравнению с исходным опорным решением транспортные расходы уменьшились на 1610 ¾ 1280 = 330 руб.

Вырожденная транспортная задача

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

Открытая транспортная задача

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

1) если , то есть объем запасов превышает объем потребления, то все потребители будут удовлетворены полностью и часть запасов останется не вывезенной. Для решения такой задачи вводят фиктивного потребителя, потребности которого равны разности объемов запаса и потребления .

Модель такой задачи будет иметь вид при ограничениях , , , , .

2) если , то есть объем потребления превышает объем запасов. Для решения такой задачи вводят фиктивного поставщика, с объемом поставки равным разности объемов потребления и поставок .

Модель такой задачи будет иметь вид при ограничениях , , , , .

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