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

Задача. Для полива различных участков сада, на которых растут сливы, яблони, груши, служат три колодца. Колодцы могут дать соответственно 180, 90, и 40 ведер воды. Участки сада требуют для полива соответственно 100, 120 и 90 ведер воды. Расстояние (в метрах) от колодцев до участков сада указаны в следующей таблице:

Колодцы	Участки
Колодцы	сливы	яблони	груши
1	10	5	12
2	23	28	33
3	43	40	39

Как лучше организовать полив.
Решаем задачу как транспортную с помощью калькулятора.
Математическая модель транспортной задачи:
F = ∑∑c_ijx_ij, (1)
при условиях:
∑x_ij = a_i, i = 1,2,…, m, (2)
∑x_ij = b_j, j = 1,2,…, n, (3)
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 180 + 90 + 40 = 310
∑b = 100 + 120 + 90 = 310
Условие баланса соблюдается. Возможности колодца равны потребностям полива. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.

	1	2	3	Колодец
1	10	5	12	180
2	23	28	33	90
3	43	40	39	40
Участки	100	120	90

Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, возможности которого полностью израсходованы, либо столбец, соответствующий потребителю,Участки которого полностью удовлетворены, либо и строку и столбец, если израсходованы Колодец поставщика и удовлетворены Участки потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все возможности не будут распределены, а потребности удовлетворены.
Искомый элемент равен 5
Для этого элемента элемента запасы колодца равны 180,Участки 120. Поскольку минимальным является 120, то вычитаем его.
x₁₂ = min(180,120) = 120.

10	5	12	180 - 120 = 60
23	x	33	90
43	x	39	40
100	120 - 120 = 0	90	0

Искомый элемент равен 10
Для этого элемента запасы колодца равны 60,Участки 100. Поскольку минимальным является 60, то вычитаем его.
x₁₁ = min(60,100) = 60.

10	5	x	60 - 60 = 0
23	x	33	90
43	x	39	40
100 - 60 = 40	0	90	0

Искомый элемент равен 23
Для этого элемента запасы колодца равны 90, потребности для участков - 40. Поскольку минимальным является 40, то вычитаем его.
x₂₁ = min(90,40) = 40.

10	5	x	0
23	x	33	90 - 40 = 50
x	x	39	40
40 - 40 = 0	0	90	0

Искомый элемент равен 33
Для этого элемента запасы колодца равны 50,Участки 90. Поскольку минимальным является 50, то вычитаем его.
x₂₃ = min(50,90) = 50.

10	5	x	0
23	x	33	50 - 50 = 0
x	x	39	40
0	0	90 - 50 = 40	0

Искомый элемент равен 39
Для этого элемента запасы колодца равны 40,Участки 40. Поскольку минимальным является 40, то вычитаем его.
x₃₃ = min(40,40) = 40.

10	5	x	0
23	x	33	0
x	x	39	40 - 40 = 0
0	0	40 - 40 = 0	0

	1	2	3	Колодец
1	10[60]	5[120]	12	180
2	23[40]	28	33[50]	90
3	43	40	39[40]	40
Участки	100	120	90

В результате получен первый опорный план, который является допустимым, так как все ведра распределены, потребность участков удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 10*60 + 5*120 + 23*40 + 33*50 + 39*40 = 5330
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 10; 0 + v₁ = 10; v₁ = 10
u₂ + v₁ = 23; 10 + u₂ = 23; u₂ = 13
u₂ + v₃ = 33; 13 + v₃ = 33; v₃ = 20
u₃ + v₃ = 39; 20 + u₃ = 39; u₃ = 19
u₁ + v₂ = 5; 0 + v₂ = 5; v₂ = 5

	v₁=10	v₂=5	v₃=20
u₁=0	10[60]	5[120]	12
u₂=13	23[40]	28	33[50]
u₃=19	43	40	39[40]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;3): 0 + 20 > 12; ∆₁₃ = 0 + 20 - 12 = 8
Выбираем максимальную оценку свободной клетки (1;3): 12
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	Колодец
1	10[60][-]	5[120]	12[+]	180
2	23[40][+]	28	33[50][-]	90
3	43	40	39[40]	40
Участки	100	120	90

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,3; ).
Из ведер х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 50. Прибавляем 50 к ведрам, стоящих в плюсовых клетках и вычитаем 50 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	Колодец
1	10[10]	5[120]	12[50]	180
2	23[90]	28	33	90
3	43	40	39[40]	40
Участки	100	120	90

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 10; 0 + v₁ = 10; v₁ = 10
u₂ + v₁ = 23; 10 + u₂ = 23; u₂ = 13
u₁ + v₂ = 5; 0 + v₂ = 5; v₂ = 5
u₁ + v₃ = 12; 0 + v₃ = 12; v₃ = 12
u₃ + v₃ = 39; 12 + u₃ = 39; u₃ = 27

	v₁=10	v₂=5	v₃=12
u₁=0	10[10]	5[120]	12[50]
u₂=13	23[90]	28	33
u₃=27	43	40	39[40]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j <= c_ij.
Минимальные затраты составят:
F(x) = 10*10 + 5*120 + 12*50 + 23*90 + 39*40 = 4930
Анализ оптимального плана.
Из 1-го колодца необходимо ведра направить на 1-й участок (10 шт.), на 2-й участок (120 шт.), на 3-й участок (50 шт.). Из 2-го колодца необходимо все ведра направить на 1-й участок. Из 3-го колодца необходимо все ведра направить на 3-й участок.
Скачать решение

Перейти к онлайн решению своей задачи

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

Правила ввода данных

Поиск

Процесс

Сообщение