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

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

Как лучше организовать полив.
Решаем задачу как транспортную с помощью калькулятора.
Математическая модель транспортной задачи:
F = ∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, 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. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, возможности которого полностью израсходованы, либо столбец, соответствующий потребителю,Участки которого полностью удовлетворены, либо и строку и столбец, если израсходованы Колодец поставщика и удовлетворены Участки потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все возможности не будут распределены, а потребности удовлетворены.
Искомый элемент равен 5
Для этого элемента элемента запасы колодца равны 180,Участки 120. Поскольку минимальным является 120, то вычитаем его.
x12 = 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, то вычитаем его.
x11 = 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, то вычитаем его.
x21 = 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, то вычитаем его.
x23 = 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, то вычитаем его.
x33 = 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. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 10; 0 + v1 = 10; v1 = 10
u2 + v1 = 23; 10 + u2 = 23; u2 = 13
u2 + v3 = 33; 13 + v3 = 33; v3 = 20
u3 + v3 = 39; 20 + u3 = 39; u3 = 19
u1 + v2 = 5; 0 + v2 = 5; v2 = 5

v1=10 v2=5 v3=20
u1=0 10[60] 5[120] 12
u2=13 23[40] 28 33[50]
u3=19 43 40 39[40]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 20 > 12; ∆13 = 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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 10; 0 + v1 = 10; v1 = 10
u2 + v1 = 23; 10 + u2 = 23; u2 = 13
u1 + v2 = 5; 0 + v2 = 5; v2 = 5
u1 + v3 = 12; 0 + v3 = 12; v3 = 12
u3 + v3 = 39; 12 + u3 = 39; u3 = 27

v1=10 v2=5 v3=12
u1=0 10[10] 5[120] 12[50]
u2=13 23[90] 28 33
u3=27 43 40 39[40]

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

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

загрузка...