Пример решения транспортной задачи

На три базы А₁,А₂,А₃ поступил однородный груз в количествах, соответственно равных 6, 8, 10 (ед.) Этот груз требуется перевезти в четыре магазина В₁,В₂,В₃,В₄ соответственно в количествах 4, 6, 8, 8 (ед.). Стоимость доставки единицы груза с каждого из пункта отправления в соответствующие пункты назначения задана матрицей тарифов (в руб.).

i=1,2,3; j=1,2,3,4.

Составить план перевозок однородного груза с минимальными транспортными издержками.

Проверим необходимое и достаточное условие разрешимости задачи.

=6+8+10=24.

=4+6+8+6=26

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на трех базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу А₄ с запасом груза, равным 26–24=2 (ед.) Тарифы перевозки единицы груза из базы А₄ во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу 5.

Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Среди тарифов из всей таблицы наилучшим является с₁₁=1, поэтому в клетку A₁B₁ направляем максимально возможный груз. Он равен min{6,4}=4. Тогда x₁₁=4 и из базы A₁ не вывезен, груз 2 ед., а потребность магазина B₁ удовлетворена полностью. Столбец таблицы В₁ выходит из рассмотрения. Из оставшихся тарифов строки наименьший - с₁₂=2. В клетку A₁B₂ направляем максимально возможный груз, равный min{2,6}=2. Тогда строка А₁ выходит из рассмотрения, поскольку из базы A₁ вывезен весь груз. Из оставшихся тарифов наилучший с₂₂=3 и с₃₄=2. В клетку А₂В₂ направляем груз, равный min{8,4}=4. При этом вычеркивается столбец В₂ из рассмотрения. Из оставшихся тарифов наименьший с₃₄=3. В клетку А₃В₁ направляем груз, равный min{10,8}=8. При этом потребность четвертого магазина удовлетворена, а из третьей базы не вывезено 2 ед. Этот нераспределенный груз направляем в клетку А₃В₃, х₃₃=2. Потребность третьего магазина не удовлетворена на 2 ед. Направим от фиктивного поставщика - базы А₄ 2 ед. в клетку А₄В₃, т.е. х₄₃=2.

Таблица 5

Bj   Аi	В1	B2	B3	B4	Потенциалы α i
b1=4	b2=6	b3=8	b4=8
А1	a1=6	4 –	2–	+		α1=0
А2	a2=8		4+	4–		α 2=1
A3	a3=10					α3=-l
А4	a4=2					α 4=-7
Потенциалы β1	β1=1	β2=2	β3=7	β2=4

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

Подсчитаем число занятых клеток таблицы, их -7, а должно быть m+n-1=4+4-1=7. Следовательно, опорный план является невырожденным.-

3. Определяем значение целевой функции первого опорного плана

F(X₁)=4·1+2·2+4·3+4·8+2·6+8·3+2·0=88 руб.

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

4. Найдем потенциалы α_i, β_i. по занятым клеткам таблицы, решая систему уравнений, полагая, что α_i +β_i.=С и α₁=0

Занесем рассчитанные потенциалы в таблицу 5, подсчитаем оценки свободных клеток, полагая, что для них Δ_ij=c_ij–(α_i+β_j):

Δ₁₃= 4-7=-3; Δ₁₄=3-4=-1; Δ₂₁=4-2=-2; Δ₂₄=5-5=0; Δ₃₁=2-0=2;

Δ₃₂=7-1=6; Δ₄₂=6; Δ₄₄=3;

Первый опорный план является не оптимальным, так как Δ₁₃<0 и Δ₁₄<0, поэтому переходим к его улучшению. Выбираем максимальную по модулю оценку свободной клетки - Δ₁₃=|–3|=3.

4. Для клетки A₁B₃ построим цикл перераспределения груза. Для этого в перспективную клетку A₁ B₃ поставим знак +, а в остальных вершинах многоугольника чередующиеся знаки -, +, -:

Затем из чисел x_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. min{2,4}=2. Прибавляем 2 г объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из хij. стоящих в минусовых клетках. В результате получим новый опорный план II.

6. Определяем значение целевой функции:

F(X₂)=F(X₁)+0·α₁₃=88+(-3)·2=88-6=82 (руб)

7. Число занятых клеток в II плане 7, следовательно, план не вырожденный.

8. Проверяем оптимальность плана методом потенциалов для этого находим потенциалы α_i β_j по занятым клеткам, полагая α₁=0.

Затем рассчитаем оценки свободных клеток

Δ₁₂=-2-(-1)=3; Δ₁₄=3-1=2; Δ₂₁,4-5=-1; Δ₂₄₌5-5=0

Δ₃₁=2-3=-1; Δ₃₂= 7-1 =6; Δ₄₁3; Δ₄₂=5; Δ₄₄₌₃.

План, полученный в таблице 6. не оптимальный, так как Δ₂₁<0 и Δ₂₁<0.

Таблица 6

План II

Bj Аi	В1	B2	B3	B4	Потенциалы α i
b1=4	b2=6	b3=8	b4=8
А1	a1=6	4 − –		+ 2		α1=0
А2	a2=8	4 +		− 2		α 2=4
A3	a3=10	+				α3=l
А4	a4=2					α 4=-4
Потенциалы β1	β1=4	β2=-1	β3=4	β2=1

9. Проводим улучшение плана II путем перераспределения грузов. В качестве перспективной клетки для загрузки выбираем А₃ В₁, в которую записываем +, затем строим цикл перераспределения:

Груз перераспределения равен:

Это единственная положительная оценка, поэтому строим цикл для клетки A₄B₁. Θ=min (4,2)=2.

Перераспределив груз получаем новый план III.

Таблица 7

План III

Bj   Аi	В1	B2	B3	B4	Потенциалы α i
b1=4	b2=6	b3=8	b4=8
А1	a1=6	1 2 −		+ 4		α1=0
А2	a2=8	+		– 2		α 2=4
A3	a3=10					α3=l
А4	a4=2					α 4=-4
Потенциалы β1	β1=4	β2=-1	β3=4	β2=2

10. Число занятых клеток 7, а должно быть m+n-1=7, следовательно план III невырожденный.

11. Вычислим значение целевой функции:

F(X₃)=F(X₂)+Θ•А₃₁ = 82 + 2(-1) = 82- 2 = 80.

12. Проверяем оптимальность плана III методом потенциалов.

Находим потенциалы по занятым клеткам:

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

Δ₁₂=2-(-1)=3; Δ₁₄=3-(2+0)=1; Δ₂₁=4-5=-1; Δ₂₄=5-(2+4)=-1;

Δ₃₂=7-(1+1)=7; Δ₃₃=6-(1+4)=1; Δ₄₁=0-(-4+1)=3; Δ₄₂=0-(-4+4)=0;

Δ₄₄=4-0-(-4+2)=2.

План не оптимальный. Δ₂₁=-1, Δ₂₄=-1.

13. Проводим улучшение плана III путем перераспределения груза. В качестве перспективной клетки для загрузки выбираем А₂ В₁, в которую записываем +, затем строим цикл перераспределения:

Определяем груз перераспределения Θ=min(2;2)=2, после исследования операции перераспределения получаем план IV

Таблица 8

План IV

Bj   Аi	В1	B2	B3	B4	Потенциалы α i
b1=4	b2=6	b3=8	b4=8
А1	a1=6					α1=0
А2	a2=8					α 2=3
A3	a3=10					α 3=l
А4	а4 =2					α 4=-4
Потенциалы β1	β1=1	β2=0	β3=4	β2=2

14. План получается вырожденный поскольку в минусовых клетках цикла находятся два одинаковых минимальных объема груза 2. При перераспределении две клетки A₁ B₂ и А₂ В₃ оказались свободными, поэтому число занятых клеток 6 будет меньше, чем m+n-1=7. Для продолжения решения в одну из освободившихся клеток записываем нуль A₁ B₁ т.к. тариф С₁₁ меньше С₂₃.

15. Вычисляем значение целевой функции:

F(X₄)=F(X₃)+Θ·Δ₂₁=80+2·(-1)=78

15. Проверяем оптимальность плана IV методом потенциалов. Находим потенциалы по занятым клеткам:

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

Δ₁₂=2-1=1; Δ₁₄=3-2=1; Δ₂₃=8-(3+4)=1; Δ₂₄=5-(3+2)=0

Δ₃₂=7-(0+1)=6; Δ₃₃=6-(4+1)=1; Δ₄₁=0-(-4+1)=3; Δ₄₂=0-(-4+0)=4

Δ₄₄=0-(-4+2)=2

Поскольку все оценки больше или равны нулю, то план оптимален

Анализ плана. Из первой базы необходимо весь груз направить в третий магазин, из второй базы направить в первый и второй магазин в количестве 2 ед. и 6 ед., а груз с третьей базы следует вывозить в первый и второй магазин в количестве 2 и 8 ед. соответственно. При этом плане потребность третьего магазина В₃ остается неудовлетворительной в размере 2 ед. Общая стоимость доставки груза потребителям будет минимальной и составлять 78 тыс. руб. Так как оценка свободной клетки Δ₂₄=0, то задача имеет множество оптимальных планов.

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

2. Каковы необходимые и достаточные условия разрешимости транспортной задачи?

3. Какая транспортная задача называется открытой, закрытой?

4. Kак строится первый опорный план транспортной задачи методом наименьших тарифов?

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

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

7. Как определяется объем передвигаемого по циклу груза?

8. Как осуществляется переход к новому опорному плану?

9. Каковы особые случаи при решении транспортной задачи методом потенциалов?