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

Пример №1. В хозяйстве имеются три земельных участка с различным плодородием почвы. Площадь первого участка 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. Используя метод наибольшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наибольшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, Посевы которого полностью израсходованы, либо столбец, соответствующий потребителю, Емкость которого полностью удовлетворены, либо и строку и столбец, если израсходованы Посевы поставщика и удовлетворены Емкость потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наибольшую стоимость, и процесс распределения запасов продолжают, пока все Посевы не будут распределены, а Емкость удовлетворены.
Искомый элемент равен 26
Для этого элемента Посевы равны 500, Емкость 700. Поскольку минимальным является 500, то вычитаем его.
x₃₁ = 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, то вычитаем его.
x₂₃ = 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, то вычитаем его.
x₂₂ = 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, то вычитаем его.
x₁₂ = 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, то вычитаем его.
x₁₁ = 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, то вычитаем его.
x₁₄ = 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. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 15; 0 + v₁ = 15; v₁ = 15
u₃ + v₁ = 26; 15 + u₃ = 26; u₃ = 11
u₁ + v₂ = 18; 0 + v₂ = 18; v₂ = 18
u₂ + v₂ = 22; 18 + u₂ = 22; u₂ = 4
u₂ + v₃ = 23; 4 + v₃ = 23; v₃ = 19
u₁ + v₄ = 0; 0 + v₄ = 0; v₄ = 0

	v₁=15	v₂=18	v₃=19	v₄=0
u₁=0	15[200]	18[400]	22	0[100]
u₂=4	19	22[600]	23[800]	0
u₃=11	26[500]	18	24	0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;3): 0 + 19 < 22; ∆₁₃ = 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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 15; 0 + v₁ = 15; v₁ = 15
u₃ + v₁ = 26; 15 + u₃ = 26; u₃ = 11
u₁ + v₃ = 22; 0 + v₃ = 22; v₃ = 22
u₂ + v₃ = 23; 22 + u₂ = 23; u₂ = 1
u₂ + v₂ = 22; 1 + v₂ = 22; v₂ = 21
u₁ + v₄ = 0; 0 + v₄ = 0; v₄ = 0

	v₁=15	v₂=21	v₃=22	v₄=0
u₁=0	15[200]	18	22[400]	0[100]
u₂=1	19	22[1000]	23[400]	0
u₃=11	26[500]	18	24	0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(2;1): 1 + 15 < 19; ∆₂₁ = 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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₃ = 22; 0 + v₃ = 22; v₃ = 22
u₂ + v₃ = 23; 22 + u₂ = 23; u₂ = 1
u₂ + v₁ = 19; 1 + v₁ = 19; v₁ = 18
u₃ + v₁ = 26; 18 + u₃ = 26; u₃ = 8
u₂ + v₂ = 22; 1 + v₂ = 22; v₂ = 21
u₁ + v₄ = 0; 0 + v₄ = 0; v₄ = 0

	v₁=18	v₂=21	v₃=22	v₄=0
u₁=0	15	18	22[600]	0[100]
u₂=1	19[200]	22[1000]	23[200]	0
u₃=8	26[500]	18	24	0

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

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

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

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

Пример №2. Проверить задачу на сбалансированность:

составить план базисным способом северо-западного угла, рассчитать значение функции цели базисного плана;
составить базисный план методом наилучшего элемента (максимального элемента) на максимальное значение функции цели. Рассчитать функцию цели (F);
сравнить результат решения двух базисных планов;
проверить базисный план методом наилучшего элемента на максимальном значении функции цели на оптимальном потенциале и проверить улучшение плана до оптимального результата;

Участок севооборота	Урожайность культур при размещении на данном участке, т с 1 га
Участок севооборота	Оз. рожь	Ячмень	Однолетние травы	Рожь	Проектируемая площадь участка, га
1	55	42	34	29	420
2	33	4	34	29	480
3	22	13	52	25	1430
4	52	6	45	23	660
5	38	25	41	29	1360
Посевная площадь культур, га	200	1450	1500	900	4050/4350

Как решить транспортную задачу на максимум

транспортная задача online;
Выбираем количество переменных (строки и столбцы);
Целевая функция "Максимальная прибыль".

Пример. Семь угольных карьеров добывают уголь и поставляют его на пять электростанций. Потребности в угле по электростанциям распределены следующим образом: для электростанции М1 требуется 200 тыс. тонн угля в месяц, для М2 – 600, М3 – 800, М4 – 900 и для М5 – 1200 тысяч тонн угля в месяц. Качество угля, оптовые цены и транспортные издержки отражены в показателях прибыли, приведенных в табл. 1.

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

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

Как решить транспортную задачу на максимум

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

Поиск

Процесс

Сообщение