Лекция 7

Тема: Алгоритм решения транспортной задачи.

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

План: 1) Алгоритм решения ТЗ.

2) Решение контрольного примера.

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

1. Проверяем, выполняется ли условие баланса, те. равенства запасов и потребностей.

Если выполняется – приступаем к п.2, если нет – вводим фиктивного поставщика (потребителя) с с_ij=0 (если задача решается на максимум, то ).

2. Распределяем груз используя любой способ составления опорного плана (например, метод северо-западного угла). приэтом должно соблюдаться условие и (все запсы вывезены, все потребности удовлетворены).

3. Проверяем составленный опорный план на вырожденность. Для решения ТЗ план должен быть невырожденным, т.е. кол-во заполненных клеток плана должно быть равно m+n-1

4. Оптимизируем полученный план, например методом потенциалов.

Для этого рассчитываем потенциалы u_i и v_j из условия, что с_ij= u_i+ v_j

Изначально, u₁ или v₁ приравнивается к 0.

5. Для незаполненных клеток плана рассчитываются коэффициенты

L_ij=c_ij-(u_i+v_j).

Если L_ij  0 (при решении задачи на минимум), то полученный опорный план оптимальный и решение задачи прекращается.

6. Если нет – из всех отрицательных L выбираем наибольший по моду

лю. Из клетки, соответствующей данному коэффициенту L строится

замкнутый контур. На углах контура должны быть заполненные

клетки, за исключение клетки с максимальным по модулю отрица-

тельным коэффициентом L, которая называется «плохой».

Клетки контура по кругу помечаются знаками «+» и «-», начиная от

«плохой», которая всегда «+».

Производится перераспределение грузов между клетками контура

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

наименьшим количеством груза, указанный груз вычитается из из

грузов отрицательных клеток и прибавляется к грузу положительных

клеток.

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

методом потенциалов и так до тех пор, пока все коэффициенты L

не будут неотрицательными.

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

Решим контрольный пример.

Дано:

В хозяйстве имеются 3 склада, где хранится 600т минеральных удобрений., на первом – 200т, на втором – 150т, на третьем – 250т. Эти удобрения должны быть вывезены на 4 поля, причем на первое поле должно попасть 100т, на второе – 150т, на третье – 150т и на четвертое – 75т. Транспортные издержки перевозки удобрений от соответствующих складов на поля известны.

Найти:

Составить такой план перевозок, при котором общие транспортные

расходы были бы минимальными.

Решение:

1. Сформируем все исходные данные в виде специальной таблицы.

Числа в нижнем правом углу каждой клетки – тарифы перевозок 1т удобрений с соответствующего склада на соответствующее поле (например, в тыс. тенге)

Таблица 1 – исходные данные задачи.

потреб. полей, тонн	100	150	150	75
запасы складов, тонн
200
	4	2	3	1
150
	3	6	2	5
250
	6	3	4	2

2. Проверим, выполняется ли условие баланса между наличием и потребностями удобрений. Наличие – 600т, потребности – 475т. Следовательно, для выполнения условия баланса необходимо ввести фиктивное поле с потребностью 600-475=125т.

3. Сформируем первый опорный план, используя метод северо-западного угла. Особенность этого метода – распределение грузов начинается с левого верхнего угла таблицы (клетки). Распределение производится независимо от величин тарифов клеток, потребности полей стараются удовлетворить максимально возможно с данного склада. В итоге имеем первый опорный план:

Таблица 2 – первый опорный план

потреб. полей, тонн	100	150	150	75	125
запасы складов, тонн
200	100	100
	4	2	3	1	0
150		50	100
	3	6	2	5	0
250			50	75	125
	6	3	4	2	0

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

4. Вычислим общие затраты на перевозку всех грузов при данном плане. Они составят Z=4100+2100+650+2100+450+275+0125=1450 (тыс. тенге).

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

6. Оптимизируем его методом потенциалов. Примем u₁=0, остальные потенциалы рассчитаем по формуле с_ij= u_i+ v_j В итоге имеем:

v₁=4-0=4, v₂=2-0=2, u₂=6-4=4, v₃=2-4=-2, u₃=4-6=-2, v₄=2-6=-4, v₅=0-6=-6

Потенциалы можно записывать в сверху и слева от соответствующих столбцов таблицы.

7. Проверим план на оптимальность. Для этого для свободных клеток рассчитаем L-коэффициенты, из условия L_ij=c_ij-(u_i+v_j). В итоге имеем:

L₁₃=3-(-2+0)=5, L₁₄=1-(-4+0)=5, L₁₅=0-(+6+0)=6, L₂₁=3-(4+4)=-5,

L₂₄=5-(-4+4)=5, L₂₅=0-(-6+4)=2, L₃₁=6-(4+6)=-4, L₃₂=3-(2+6)=-5.

Как видно из расчетов, имеем три отрицательных L-коэффициента,

это говорит о том, что первоначальный план неоптимален и может быть оптимизирован.

8. Для улучшения плана выберем из отрицательных значений L-

коэффициентов максимальный по модулю, например L₂₁. Это –

«плохая клетка». Она помечается в таблице звездочкой. Построим

замкнутый контур из этой клетки, при условии, что остальные вер

шины контура будут лежать в заполненных клетках. «Плохая»

клетка помечается знаком +, остальные клетки чередуются знаками

+ и -. В результате имеем контур:

Рисунок 7 – Построение контура.

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

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

Таблица 3 – Новый план перевозок.

потреб. полей, тонн	100	150	150	75	125
запасы складов, тонн
200	50	150
	4	2	3	1	0
150	50		100
	3	6	2	5	0
250			50	75	125
	6	3	4	2	0

Для полученного плана рассчитаем заново потенциалы и L-коэффициенты. Имеем: u₁₌0, u₂=-1, u₃=1, v₁=4, v₂=2, v₃=3, v₄=1, v₅=-1.

L₁₃=0, L₁₄=1, L₁₅=1, L₂₂=1, L₂₄=5, L₂₅=2, L₃₄=1, L₃₂=0.

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

Z для нового плана равно 1200 (тыс. тенге), таким образом оптимизировав первоначальный план перевозок, мы съэкономили 200 (тыс тенге).

Литература: 2, 25-35 с.

Контрольные вопросы:

1. С чего начинается решение ТЗ?

2. Что такое потенциал?

3. Что такое «плохая точка»?