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

Задание. В хозяйстве имеются три земельных участка с различным плодородием почвы. Площадь первого участка 700 га, второго – 1000 га, третьего – 800 га. На этих участках планируется разместить посевы трех зерновых культур: рожь – 700 га, пшеница 1400 га, овес – 500 га. Составить оптимальный план размещения зерновых культур по участкам, чтобы общий валовой сбор зерна был максимальным. Урожайность культур на участках с различным плодородием почв известна (таблица 1). Таблица 1 – Урожайности культур с 1 га, ц.
1 2 3 Посевы
1 15 18 22 700
2 19 22 23 1400
3 26 18 24 500
Емкость 700 1000 800
Решение находим с помощью онлайн сервиса Транспортная задача. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 700 + 1400 + 500 = 2600
∑b = 700 + 1000 + 800 = 2500
Как видно, суммарная емкость площадей участков превышает необходимую площадь для посевов. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный (фиктивный) участок, площадь которого равна 100 (2600—2500). Урожайность для этого участка для всех посевов будет равна нулю.
Занесем исходные данные в распределительную таблицу.
1 2 3 4 Посевы
1 15 18 22 0 700
2 19 22 23 0 1400
3 26 18 24 0 500
Емкость 700 1000 800 100

Этап I. Поиск первого опорного плана.
1. Используя метод наибольшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наибольшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, Посевы которого полностью израсходованы, либо столбец, соответствующий потребителю, Емкость которого полностью удовлетворены, либо и строку и столбец, если израсходованы Посевы поставщика и удовлетворены Емкость потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наибольшую стоимость, и процесс распределения запасов продолжают, пока все Посевы не будут распределены, а Емкость удовлетворены.
Искомый элемент равен 26
Для этого элемента Посевы равны 500, Емкость 700. Поскольку минимальным является 500, то вычитаем его.
x31 = min(500,700) = 500.

15 18 22 0 700
19 22 23 0 1400
26 x x x 500 - 500 = 0
700 - 500 = 200 1000 800 100 0


Искомый элемент равен 23
Для этого элемента Посевы равны 1400, Емкость 800. Поскольку минимальным является 800, то вычитаем его.
x23 = min(1400,800) = 800.

15 18 x 0 700
19 22 23 0 1400 - 800 = 600
26 x x x 0
200 1000 800 - 800 = 0 100 0


Искомый элемент равен 22
Для этого элемента Посевы равны 600, Емкость 1000. Поскольку минимальным является 600, то вычитаем его.
x22 = min(600,1000) = 600.

15 18 x 0 700
x 22 23 x 600 - 600 = 0
26 x x x 0
200 1000 - 600 = 400 0 100 0


Искомый элемент равен 18
Для этого элемента Посевы равны 700, Емкость 400. Поскольку минимальным является 400, то вычитаем его.
x12 = min(700,400) = 400.

15 18 x 0 700 - 400 = 300
x 22 23 x 0
26 x x x 0
200 400 - 400 = 0 0 100 0


Искомый элемент равен 15
Для этого элемента Посевы равны 300, Емкость 200. Поскольку минимальным является 200, то вычитаем его.
x11 = min(300,200) = 200.

15 18 x 0 300 - 200 = 100
x 22 23 x 0
26 x x x 0
200 - 200 = 0 0 0 100 0


Искомый элемент равен 0
Для этого элемента Посевы равны 100, Емкость 100. Поскольку минимальным является 100, то вычитаем его.
x14 = min(100,100) = 100.

15 18 x 0 100 - 100 = 0
x 22 23 x 0
26 x x x 0
0 0 0 100 - 100 = 0 0



1 2 3 4 Посевы
1 15[200] 18[400] 22 0[100] 700
2 19 22[600] 23[800] 0 1400
3 26[500] 18 24 0 500
Емкость 700 1000 800 100

В результате получен первый опорный план, который является допустимым, так как все участки заполнены, площадь для посевов распределена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 15*200 + 18*400 + 0*100 + 22*600 + 23*800 + 26*500 = 54800
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 15; 0 + v1 = 15; v1 = 15
u3 + v1 = 26; 15 + u3 = 26; u3 = 11
u1 + v2 = 18; 0 + v2 = 18; v2 = 18
u2 + v2 = 22; 18 + u2 = 22; u2 = 4
u2 + v3 = 23; 4 + v3 = 23; v3 = 19
u1 + v4 = 0; 0 + v4 = 0; v4 = 0

v1=15 v2=18 v3=19 v4=0
u1=0 15[200] 18[400] 22 0[100]
u2=4 19 22[600] 23[800] 0
u3=11 26[500] 18 24 0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 19 < 22; ∆13 = 0 + 19 - 22 = -3
Выбираем максимальную оценку свободной клетки (1;3): 22
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

1 2 3 4 Посевы
1 15[200] 18[400][-] 22[+] 0[100] 700
2 19 22[600][+] 23[800][-] 0 1400
3 26[500] 18 24 0 500
Емкость 700 1000 800 100

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

1 2 3 4 Посевы
1 15[200] 18 22[400] 0[100] 700
2 19 22[1000] 23[400] 0 1400
3 26[500] 18 24 0 500
Емкость 700 1000 800 100

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 15; 0 + v1 = 15; v1 = 15
u3 + v1 = 26; 15 + u3 = 26; u3 = 11
u1 + v3 = 22; 0 + v3 = 22; v3 = 22
u2 + v3 = 23; 22 + u2 = 23; u2 = 1
u2 + v2 = 22; 1 + v2 = 22; v2 = 21
u1 + v4 = 0; 0 + v4 = 0; v4 = 0

v1=15 v2=21 v3=22 v4=0
u1=0 15[200] 18 22[400] 0[100]
u2=1 19 22[1000] 23[400] 0
u3=11 26[500] 18 24 0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 1 + 15 < 19; ∆21 = 1 + 15 - 19 = -3
Выбираем максимальную оценку свободной клетки (2;1): 19
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

1 2 3 4 Посевы
1 15[200][-] 18 22[400][+] 0[100] 700
2 19[+] 22[1000] 23[400][-] 0 1400
3 26[500] 18 24 0 500
Емкость 700 1000 800 100

Цикл приведен в таблице (2,1; 2,3; 1,3; 1,1; ).
Из площадей хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 200. Прибавляем 200 к емкости площадей, стоящих в плюсовых клетках и вычитаем 200 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 Посевы
1 15 18 22[600] 0[100] 700
2 19[200] 22[1000] 23[200] 0 1400
3 26[500] 18 24 0 500
Емкость 700 1000 800 100

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 22; 0 + v3 = 22; v3 = 22
u2 + v3 = 23; 22 + u2 = 23; u2 = 1
u2 + v1 = 19; 1 + v1 = 19; v1 = 18
u3 + v1 = 26; 18 + u3 = 26; u3 = 8
u2 + v2 = 22; 1 + v2 = 22; v2 = 21
u1 + v4 = 0; 0 + v4 = 0; v4 = 0

v1=18 v2=21 v3=22 v4=0
u1=0 15 18 22[600] 0[100]
u2=1 19[200] 22[1000] 23[200] 0
u3=8 26[500] 18 24 0

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj <= cij.
Максимальная прибыль составит:
F(x) = 22*600 + 0*100 + 19*200 + 22*1000 + 23*200 + 26*500 = 56600

Анализ оптимального плана

Рожь необходимо посеять только на третьем участке, пшеницу - на первом (200 га), на втором площадью 1000 га, на третьем площадью в 200 га. Овес следует посадить только на первом участке (площадью 500 га). При таком распределении посевы ржи будут недоиспользованы на 100 га.

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

загрузка...