математическое моделирование. 9420806_Транспортная. Решение Сначала проверим необходимое и достаточное условие разрешимости задачи

• Название: Решение Сначала проверим необходимое и достаточное условие разрешимости задачи
• Анкор: математическое моделирование
• Дата: 10.03.2023
• Размер: 25.53 Kb.
• Имя файла: 9420806_Транспортная.docx
• Тип: Задача; #978199

Задача № 2

Решить транспортную задачу методом потенциалов. Потребителям B1, B2, B3

и B4 требуется песок в количествах соответственно 120, 150, 130 и 120 тонн. На складах имеется следующее количество песка: A1 = 200 т, А2 = 160 т и А3 = 160 т. Расстояния между поставщиками и получателями песка приведены

в таблице

	B1	B2	B3	B4
A1	14	21	10	13
A2	9	17	17	14
A3	22	26	17	24

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

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

∑a = 200 + 160 + 160 = 520

∑b = 120 + 150 + 130 + 120 = 520

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

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

Искомый (минимальный) элемент равен c₂₁=9. Для этого элемента запасы равны 160, потребности 120. Поскольку минимальным является 120, то вычитаем его.

x₂₁ = min(160,120) = 120.

x	21	10	13	200
9	17	17	14	160 - 120 = 40
x	26	17	24	160
120 - 120 = 0	150	130	120

Далее, искомый элемент равен c₁₃=10. Для этого элемента запасы равны 200, потребности 130. Поскольку минимальным является 130, то вычитаем его.

x₁₃ = min(200,130) = 130.

x	21	10	13	200 - 130 = 70
9	17	x	14	40
x	26	x	24	160
0	150	130 - 130 = 0	120

Следующий искомый элемент равен c₁₄=13. Для этого элемента запасы равны 70, потребности 120. Поскольку минимальным является 70, то вычитаем его.

x₁₄ = min(70,120) = 70.

x	x	10	13	70 - 70 = 0
9	17	x	14	40
x	26	x	24	160
0	150	0	120 - 70 = 50

Минимальный элемент равен c₂₄=14. Для этого элемента запасы равны 40, потребности 50. Поскольку минимальным является 40, то вычитаем его.

x₂₄ = min(40,50) = 40.

x	x	10	13	0
9	x	x	14	40 - 40 = 0
x	26	x	24	160
0	150	0	50 - 40 = 10

Минимальный элемент равен c₃₄=24. Для этого элемента запасы равны 160, потребности 10. Поскольку минимальным является 10, то вычитаем его.

x₃₄ = min(160,10) = 10.

x	x	10	13	0
9	x	x	14	0
x	26	x	24	160 - 10 = 150
0	150	0	10 - 10 = 0

Искомый элемент равен c₃₂=26. Для этого элемента запасы равны 150, потребности 150. Поскольку минимальным является 150, то вычитаем его.

x₃₂ = min(150,150) = 150.

x	x	10	13	0
9	x	x	14	0
x	26	x	24	150 - 150 = 0
0	150 - 150 = 0	0	0

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

	B1	B2	B3	B4	Запасы
A1	14	21	10[130]	13[70]	200
A2	9[120]	17	17	14[40]	160
A3	22	26[150]	17	24[10]	160
Потребности	120	150	130	120

В скобках указаны перевезенные грузы от i-го поставщика j-му потребителю

Подсчитаем значение целевой функции для этого опорного плана:

F(x) = 10*130 + 13*70 + 9*120 + 14*40 + 26*150 + 24*10 = 7990
Улучшение первого опорного плана методом потенциалов

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 10; 0 + v₃ = 10; v₃ = 10

u₁ + v₄ = 13; 0 + v₄ = 13; v₄ = 13

u₂ + v₄ = 14; 13 + u₂ = 14; u₂ = 1

u₂ + v₁ = 9; 1 + v₁ = 9; v₁ = 8

u₃ + v₄ = 24; 13 + u₃ = 24; u₃ = 11

u₃ + v₂ = 26; 11 + v₂ = 26; v₂ = 15

	v1=8	v2=15	v3=10	v4=13
u1=0	14	21	10[130]	13[70]
u2=1	9[120]	17	17	14[40]
u3=11	22	26[150]	17	24[10]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(3;3): 11 + 10 > 17; ∆₃₃ = 11 + 10 - 17 = 4 > 0

Выбираем максимальную оценку свободной клетки (3;3): 17

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

	1	2	3	4	Запасы
1	14	21	10[130][-]	13[70][+]	200
2	9[120]	17	17	14[40]	160
3	22	26[150]	17[+]	24[10][-]	160
Потребности	120	150	130	120

Цикл приведен в таблице (3,3 → 3,4 → 1,4 → 1,3).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	B1	B2	B3	B4	Запасы
A1	14	21	10[120]	13[80]	200
A2	9[120]	17	17	14[40]	160
A3	22	26[150]	17[10]	24	160
Потребности	120	150	130	120

Опять проверяем оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 10; 0 + v₃ = 10; v₃ = 10

u₃ + v₃ = 17; 10 + u₃ = 17; u₃ = 7

u₃ + v₂ = 26; 7 + v₂ = 26; v₂ = 19

u₁ + v₄ = 13; 0 + v₄ = 13; v₄ = 13

u₂ + v₄ = 14; 13 + u₂ = 14; u₂ = 1

u₂ + v₁ = 9; 1 + v₁ = 9; v₁ = 8

	v1=8	v2=19	v3=10	v4=13
u1=0	14	21	10[120]	13[80]
u2=1	9[120]	17	17	14[40]
u3=7	22	26[150]	17[10]	24

Есть оценки свободных клеток, для которых u_i + v_j > c_ij – план не оптимален.

(2;2): 1 + 19 > 17; ∆₂₂ = 1 + 19 - 17 = 3 > 0

Выбираем максимальную оценку свободной клетки (2;2): 17

Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	14	21	10[120][-]	13[80][+]	200
2	9[120]	17[+]	17	14[40][-]	160
3	22	26[150][-]	17[10][+]	24	160
Потребности	120	150	130	120

Цикл приведен в таблице (2,2 → 2,4 → 1,4 → 1,3 → 3,3 → 3,2).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 40. Прибавляем 40 к объемам грузов, стоящих в плюсовых клетках и вычитаем 40 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	B1	B2	B3	B4	Запасы
A1	14	21	10[80]	13[120]	200
A2	9[120]	17[40]	17	14	160
A3	22	26[110]	17[50]	24	160
Потребности	120	150	130	120

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 10; 0 + v₃ = 10; v₃ = 10

u₃ + v₃ = 17; 10 + u₃ = 17; u₃ = 7

u₃ + v₂ = 26; 7 + v₂ = 26; v₂ = 19

u₂ + v₂ = 17; 19 + u₂ = 17; u₂ = -2

u₂ + v₁ = 9; -2 + v₁ = 9; v₁ = 11

u₁ + v₄ = 13; 0 + v₄ = 13; v₄ = 13

	v1=11	v2=19	v3=10	v4=13
u1=0	14	21	10[80]	13[120]
u2=-2	9[120]	17[40]	17	14
u3=7	22	26[110]	17[50]	24

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.

Минимальные затраты составят: F(x) = 10*80 + 13*120 + 9*120 + 17*40 + 26*110 + 17*50 = 7830

Мы существенно улучшили оптимальный план.

Таким образом

От поставщика А1 необходимо песок доставить В3 - 80 т., В4 - 120 т.

От поставщика А2 необходимо песок доставить В1 - 120 т., В2 - 40 т.

От поставщика А3 необходимо песок доставить В2 - 110 т., В3 - 50 т.