Алгоритм решения сбалансированной транспортной задачи

 

1) Строим исходный опорный план.

2) Проверяем его на оптимальность. Если план оптимален, задача решена. Иначе переходим к пункту 3).

3) Переходим к нехудшему опорному плану. Возвращаемся к пункту 2).

Построение исходного опорного плана (первый пункт алгоритма)

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

Существует несколько методов построения исходного опорного плана. Рассмотрим методы «северо-западного угла» и «минимального элемента» на следующем примере.

Пример 8

 В трех хранилищах  и  имеется соответственно 70, 90 и 50 т топлива. Требуется спланировать перевозку топлива четырем потребителям  и  спрос которых равен соответственно 50, 70, 40 и 40т так, чтобы затраты на транспортировку были минимальными. Стоимость перевозки 1т (в усл. ден. ед.) указана в таблице 15.

 

Таблица 15

Хранилища	Потребители				Запас топлива, т
	В1	В2	В3	В4
А1	5	4	3	6	70
А2	4	3	5	1	90
А3	2	4	1	5	50
Потребность в топливе, т	50	70	40	40	200\210

Решение

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

 

Таблица 16

Хранилища	Потребители					Запас топлива, т
	В1	В2	В3	В4	В5
А1	5	4	3	6	0	70
А2	4	3	5	1	0	90
А3	2	4	1	5	0	50
Потребность в топливе, т	50	70	40	40	10	210

 

Найдем начальный опорный план методом «северо-западного угла». Сущность его состоит в следующем. Пользуясь распределительной таблицей закрытой модели, будем распределять груз, начиная с максимально возможной загрузки левой верхней, условно называемой северо-западной клетки, т. е. клетки (1,1). В эту клетку занесем меньшее из чисел , то есть . Таким образом, потребности в топливе потребителя  удовлетворены и первый столбец из рассмотрения исключается («вычеркивается»), а в хранилище  осталось 70-50=20 т топлива. Теперь левой верхней клеткой оставшейся части таблицы является клетка (1,2) и . Так как в первом хранилище топлива больше нет, то первая строка из рассмотрения исключается («вычеркивается»), а потребителю  недостает 70-20=50 т топлива. Теперь заполним клетку (2,2) и . Столбец  «вычеркиваем», а в хранилище  осталось 90-50=40 т топлива. Теперь заполним клетку (2,3) и . Строку  и столбец  «вычеркиваем». Теперь заполним клетку (3,4) и . Столбец  «вычеркиваем», а в хранилище  осталось 50-40=10 т топлива. Незаполненной осталась одна клетка (3,5) и . Итак в распределительной таблице записан исходный опорный план (см. таблицу 17).

 

Таблица 17

Хранилища	Потребители					Запас топлива, т
	В1	В2	В3	В4	В5
А1						70
А2						90
А3						50
Потребность в топливе, т	50	70	40	40	10	210

 

или

Транспортные издержки для этого плана:

(усл. ден. ед.)

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

Итак, просматривая распределительную таблицу, замечаем, что наименьшие затраты на перевозку топлива соответствуют маршруту - , поэтому заполним любую клетку столбца , например клетку (1,5) и . Таким образом, потребности в топливе потребителя  удовлетворены и пятый столбец из рассмотрения исключается («вычеркивается»), а в хранилище  осталось 70-10=60 т топлива. Просматриваем оставшиеся клетки таблицы. Наименьшие тарифы имеют клетки (2,4) и (3,3): . Заполняем любую из этих клеток, например клетку (2,4) и . Столбец  «вычеркиваем», а в хранилище  при этом останется 90-40=50 т топлива. Просматриваем оставшиеся клетки таблицы. Наименьший тариф имеет клетка (3,3). Загрузим ее:  и «вычеркиваем» столбец , а в хранилище  осталось 50-40=10 т топлива. Просматриваем оставшиеся клетки таблицы. Наименьший тариф имеет клетка (3,1): . В клетку (3,1) помещаем  и «вычеркиваем» строку , а потребителю  недостает  50-10=40 т топлива. Далее по величине тарифа следует загружать клетку (2,2), так как . В клетку (2,2) помещаем  и «вычеркиваем» строку , а потребителю  недостает 70-50=20 т топлива. Далее по величине тарифа следует загружать клетку (1,2), так как . В клетку (1,2) помещаем  и «вычеркиваем» столбец , а в хранилище  осталось 60-20=40 т топлива. Заполняем оставшуюся клетку (1,1): . Итак, в распределительной таблице записан исходный опорный план (см. таблицу 18).

 

Таблица 18

Хранилища	Потребители					Запас топлива, т
	В1	В2	В3	В4	В5
А1						70
А2						90
А3						50
Потребность в топливе, т	50	70	40	40	10	210

 

или

Транспортные издержки для этого плана:

( усл. ден. ед.)

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

Так в последнем примере начальный опорный план, найденный методом «северо-западного угла» является вырожденным (6 занятых клеток, что меньше, чем ). Для преодоления вырожденности этого плана добавим «0», например, в клетку (3,3). Тогда число занятых клеток будет равно 7, и план становится невырожденным. Клетка (3,3) не образует цикла с остальными занятыми клетками.

 

 

Проверка на оптимальность невырожденного опорного плана методом потенциалов (второй пункт алгоритма)

1) Каждому поставщику поставим в соответствие потенциал , а каждому потребителю потенциал .

Тогда каждой занятой клетке будет соответствовать уравнение:

.

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

Система является линейно-зависимой, для нахождения одного из частных решений придадим одному из потенциалов числовое значение, например , тогда

2) Для исследования плана на оптимальность для каждой свободной клетки считаем оценки по формуле:

;

а) если все оценки положительны, то найденный опорный план оптимален и единственен ;

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

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

 

 

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

(третий пункт алгоритма)

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

Цикл пересчета

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

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

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

Так как оценка , то найденный план не оптимален. Его можно улучшить путем загрузки этой клетки.

Составим цикл пересчета относительно клетки (1,3) (см. таблицу 19).

 

Таблица 19

Хранилища	Потребители					Запас топлива, т
	В1	В2	В3	В4	В5
А1						70
А2						90
А3						50
Потребность в топливе, т	50	70	40	40	10	210

 

Из клеток, помеченных знаком «-» выбираем наименьшее количество груза . Прибавляем значение  к поставкам в клетках, помеченных знаком «+» и вычитаем из поставок в клетках, помеченных знаком «-», получим следующий план перевозок (см. таблицу 20).

 

Таблица 20

Хранилища	Потребители					Запас топлива, т
	В1	В2	В3	В4	В5
А1						70
А2						90
А3						50
Потребность в топливе, т	50	70	40	40	10	210

 

Полученный опорный план является вырожденным, так как число заполненных клеток равно 6<m+n-1=7. Для преодоления вырожденности плана, поставим ноль в любую пустую клетку, не образующую цикла с уже заполненными клетками, например в клетку (1,1) (см. последнюю таблицу).

Проверим найденный план на оптимальность, для этого найдем потенциалы строк и столбцов из решения системы:

Присвоив , найдем

Запишем потенциалы в последнюю таблицу.

Определим оценки свободных клеток:

Так как все оценки неотрицательны, то найденный опорный план является оптимальным, а так как имеется нулевая оценка ( ), то этот план не единственен.

Итак, получили оптимальный план:

.

Транспортные издержки для этого плана:

(усл. ден. ед.).

Итак, по оптимальному плану, необходимо из хранилища А₁ потребителю B₂ доставить 20 т топлива, потребителю B₃ – 40 т топлива; из хранилища А₂ потребителю В₂ доставить 50 т топлива, а потребителю В₄ – 40 т топлива; из хранилища А₃ доставить 50 т топлива потребителю В₁.

При этом затраты на транспортировку будут минимальными и составят 490 усл. ден. ед. Нераспределенное топливо, в размере 10 т останется в хранилище А₁.

---

Дата добавления: 2018-09-20; просмотров: 501; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!