Решение задачи о назначении методом потенциалов

Исходная матрица:

23	46	40	15	22	9	37	37
23	26	5	29	36	38	14	40
12	38	29	33	22	3	49	49
34	48	10	3	21	17	48	13
16	34	1	43	32	40	11	19
26	25	25	9	16	5	48	11
10	2	37	18	11	18	39	45
24	41	36	33	9	35	47	39

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

	1	2	3	4	5	6	7	8
1	23	46	40	15	22	9	37	37	1
2	23	26	5	29	36	38	14	40	1
3	12	38	29	33	22	3	49	49	1
4	34	48	10	3	21	17	48	13	1
5	16	34	1	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11	1
7	10	2	37	18	11	18	39	45	1
8	24	41	36	33	9	35	47	39	1
	1	1	1	1	1	1	1	1

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8
∑b = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 1. Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x₅₃= min(1,1) = 1.

23	46	x	15	22	9	37	37	1
23	26	x	29	36	38	14	40	1
12	38	x	33	22	3	49	49	1
34	48	x	3	21	17	48	13	1
x	x	1	x	x	x	x	x	1 - 1 = 0
26	25	x	9	16	5	48	11	1
10	2	x	18	11	18	39	45	1
24	41	x	33	9	35	47	39	1
1	1	1 - 1 = 0	1	1	1	1	1	0

Искомый элемент равен 2
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x₇₂= min(1,1) = 1.

23	x	x	15	22	9	37	37	1
23	x	x	29	36	38	14	40	1
12	x	x	33	22	3	49	49	1
34	x	x	3	21	17	48	13	1
x	x	1	x	x	x	x	x	0
26	x	x	9	16	5	48	11	1
x	2	x	x	x	x	x	x	1 - 1 = 0
24	x	x	33	9	35	47	39	1
1	1 - 1 = 0	0	1	1	1	1	1	0

Искомый элемент равен 3
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x₃₆= min(1,1) = 1.

23	x	x	15	22	x	37	37	1
23	x	x	29	36	x	14	40	1
x	x	x	x	x	3	x	x	1 - 1 = 0
34	x	x	3	21	x	48	13	1
x	x	1	x	x	x	x	x	0
26	x	x	9	16	x	48	11	1
x	2	x	x	x	x	x	x	0
24	x	x	33	9	x	47	39	1
1	0	0	1	1	1 - 1 = 0	1	1	0

Искомый элемент равен 3
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x₄₄= min(1,1) = 1.

23	x	x	x	22	x	37	37	1
23	x	x	x	36	x	14	40	1
x	x	x	x	x	3	x	x	0
x	x	x	3	x	x	x	x	1 - 1 = 0
x	x	1	x	x	x	x	x	0
26	x	x	x	16	x	48	11	1
x	2	x	x	x	x	x	x	0
24	x	x	x	9	x	47	39	1
1	0	0	1 - 1 = 0	1	0	1	1	0

Искомый элемент равен 9
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x₈₅= min(1,1) = 1.

23	x	x	x	x	x	37	37	1
23	x	x	x	x	x	14	40	1
x	x	x	x	x	3	x	x	0
x	x	x	3	x	x	x	x	0
x	x	1	x	x	x	x	x	0
26	x	x	x	x	x	48	11	1
x	2	x	x	x	x	x	x	0
x	x	x	x	9	x	x	x	1 - 1 = 0
1	0	0	0	1 - 1 = 0	0	1	1	0

Искомый элемент равен 11
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x₆₈= min(1,1) = 1.

23	x	x	x	x	x	37	x	1
23	x	x	x	x	x	14	x	1
x	x	x	x	x	3	x	x	0
x	x	x	3	x	x	x	x	0
x	x	1	x	x	x	x	x	0
x	x	x	x	x	x	x	11	1 - 1 = 0
x	2	x	x	x	x	x	x	0
x	x	x	x	9	x	x	x	0
1	0	0	0	0	0	1	1 - 1 = 0	0

Искомый элемент равен 14. x₂₇= min(1,1) = 1.

23	x	x	x	x	x	x	x	1
x	x	x	x	x	x	14	x	1 - 1 = 0
x	x	x	x	x	3	x	x	0
x	x	x	3	x	x	x	x	0
x	x	1	x	x	x	x	x	0
x	x	x	x	x	x	x	11	0
x	2	x	x	x	x	x	x	0
x	x	x	x	9	x	x	x	0
1	0	0	0	0	0	1 - 1 = 0	0	0

Искомый элемент равен 23. x₁₁= min(1,1) = 1.

23	x	x	x	x	x	x	x	1 - 1 = 0
x	x	x	x	x	x	14	x	0
x	x	x	x	x	3	x	x	0
x	x	x	3	x	x	x	x	0
x	x	1	x	x	x	x	x	0
x	x	x	x	x	x	x	11	0
x	2	x	x	x	x	x	x	0
x	x	x	x	9	x	x	x	0
1 - 1 = 0	0	0	0	0	0	0	0	0

	1	2	3	4	5	6	7	8
1	23[1]	46	40	15	22	9	37	37	1
2	23	26	5	29	36	38	14[1]	40	1
3	12	38	29	33	22	3[1]	49	49	1
4	34	48	10	3[1]	21	17	48	13	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 15. Следовательно, опорный план является вырожденным.
Строим новый план. Значение целевой функции для этого опорного плана равно: F(x) = 23*1 + 14*1 + 3*1 + 3*1 + 1*1 + 11*1 + 2*1 + 9*1 =66

	1	2	3	4	5	6	7	8
1	23[1]	46	40	15	22	9	37	37	1
2	23	26	5	29	36	38	14[1]	40	1
3	12	38	29	33	22	3[1]	49	49	1
4	34	48	10	3[1]	21	17	48	13	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 15. Следовательно, опорный план является вырожденным.
Значение целевой функции для этого опорного плана равно: F(x) = 23*1 + 14*1 + 3*1 + 3*1 + 1*1 + 11*1 + 2*1 + 9*1 = 66
Для получения невырожденного плана принудительно добавляем нуль [0] в клетку (1;2); (1;3); (1;4); (1;5); (1;6); (1;7); (1;8);

Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i+ v_i= c_ij, полагая, что u₁ = 0.
u₁+ v₁= 23; 0 + v₁= 23; v₁= 23
u₁+ v₂= 46; 0 + v₂= 46; v₂= 46
u₇+ v₂= 2; 46 + u₇= 2; u₇= -44
u₁+ v₃= 40; 0 + v₃= 40; v₃= 40
u₅+ v₃= 1; 40 + u₅= 1; u₅= -39
u₁+ v₄= 15; 0 + v₄= 15; v₄= 15
u₄+ v₄= 3; 15 + u₄= 3; u₄= -12
u₁+ v₅= 22; 0 + v₅= 22; v₅= 22
u₈+ v₅= 9; 22 + u₈= 9; u₈= -13
u₁+ v₆= 9; 0 + v₆= 9; v₆= 9
u₃+ v₆= 3; 9 + u₃= 3; u₃= -6
u₁+ v₇= 37; 0 + v₇= 37; v₇= 37
u₂+ v₇= 14; 37 + u₂= 14; u₂= -23
u₁+ v₈= 37; 0 + v₈= 37; v₈= 37
u₆+ v₈= 11; 37 + u₆= 11; u₆= -26

	v₁=23	v₂=46	v₃=40	v₄=15	v₅=22	v₆=9	v₇=37	v₈=37
u₁=0	23[1]	46[0]	40[0]	15[0]	22[0]	9[0]	37[0]	37[0]
u₂=-23	23	26	5	29	36	38	14[1]	40
u₃=-6	12	38	29	33	22	3[1]	49	49
u₄=-12	34	48	10	3[1]	21	17	48	13
u₅=-39	16	34	1[1]	43	32	40	11	19
u₆=-26	26	25	25	9	16	5	48	11[1]
u₇=-44	10	2[1]	37	18	11	18	39	45
u₈=-13	24	41	36	33	9[1]	35	47	39

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i+ v_i> c_ij
(2;3): -23 + 40 > 5; ∆₂₃= -23 + 40 - 5= 12
(3;1): -6 + 23 > 12; ∆₃₁= -6 + 23 - 12= 5
(3;2): -6 + 46 > 38; ∆₃₂= -6 + 46 - 38= 2
(3;3): -6 + 40 > 29; ∆₃₃= -6 + 40 - 29= 5
(4;3): -12 + 40 > 10; ∆₄₃= -12 + 40 -10 = 18
(4;8): -12 + 37 > 13; ∆₄₈= -12 + 37 -13 = 12
max(12,5,2,5,18,12) = 18
Выбираем максимальную оценку свободной клетки (4;3): 10
Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	7	8
1	23[1]	46[0]	40[0][-]	15[0][+]	22[0]	9[0]	37[0]	37[0]	1
2	23	26	5	29	36	38	14[1]	40	1
3	12	38	29	33	22	3[1]	49	49	1
4	34	48	10[+]	3[1][-]	21	17	48	13	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

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

	1	2	3	4	5	6	7	8
1	23[1]	46[0]	40	15[0]	22[0]	9[0]	37[0]	37[0]	1
2	23	26	5	29	36	38	14[1]	40	1
3	12	38	29	33	22	3[1]	49	49	1
4	34	48	10[0]	3[1]	21	17	48	13	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

Проверим оптимальность опорного плана.
u₁+ v₁= 23; 0 + v₁= 23; v₁= 23
u₁+ v₂= 46; 0 + v₂= 46; v₂= 46
u₇+ v₂= 2; 46 + u₇= 2; u₇= -44
u₁+ v₄= 15; 0 + v₄= 15; v₄= 15
u₄+ v₄= 3; 15 + u₄= 3; u₄= -12
u₄+ v₃= 10; -12 + v₃= 10; v₃= 22
u₅+ v₃= 1; 22 + u₅= 1; u₅= -21
u₁+ v₅= 22; 0 + v₅= 22; v₅= 22
u₈+ v₅= 9; 22 + u₈= 9; u₈= -13
u₁+ v₆= 9; 0 + v₆= 9; v₆= 9
u₃+ v₆= 3; 9 + u₃= 3; u₃= -6
u₁+ v₇= 37; 0 + v₇= 37; v₇= 37
u₂+ v₇= 14; 37 + u₂= 14; u₂= -23
u₁+ v₈= 37; 0 + v₈= 37; v₈= 37
u₆+ v₈= 11; 37 + u₆= 11; u₆= -26

	v₁=23	v₂=46	v₃=22	v₄=15	v₅=22	v₆=9	v₇=37	v₈=37
u₁=0	23[1]	46[0]	40	15[0]	22[0]	9[0]	37[0]	37[0]
u₂=-23	23	26	5	29	36	38	14[1]	40
u₃=-6	12	38	29	33	22	3[1]	49	49
u₄=-12	34	48	10[0]	3[1]	21	17	48	13
u₅=-21	16	34	1[1]	43	32	40	11	19
u₆=-26	26	25	25	9	16	5	48	11[1]
u₇=-44	10	2[1]	37	18	11	18	39	45
u₈=-13	24	41	36	33	9[1]	35	47	39

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i+ v_i> c_ij
(3;1): -6 + 23 > 12; ∆₃₁= -6 + 23 - 12= 5
(3;2): -6 + 46 > 38; ∆₃₂= -6 + 46 - 38= 2
(4;8): -12 + 37 > 13; ∆₄₈= -12 + 37 -13 = 12
(5;7): -21 + 37 > 11; ∆₅₇= -21 + 37 -11 = 5
max(5,2,12,5) = 12
Выбираем максимальную оценку свободной клетки (4;8): 13
Для этого в перспективную клетку (4;8) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	7	8
1	23[1]	46[0]	40	15[0][+]	22[0]	9[0]	37[0]	37[0][-]	1
2	23	26	5	29	36	38	14[1]	40	1
3	12	38	29	33	22	3[1]	49	49	1
4	34	48	10[0]	3[1][-]	21	17	48	13[+]	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

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

	1	2	3	4	5	6	7	8	Запасы
1	23[1]	46[0]	40	15[0]	22[0]	9[0]	37[0]	37	1
2	23	26	5	29	36	38	14[1]	40	1
3	12	38	29	33	22	3[1]	49	49	1
4	34	48	10[0]	3[1]	21	17	48	13[0]	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
Потребности	1	1	1	1	1	1	1	1

Проверим оптимальность опорного плана.
u₁+ v₁= 23; 0 + v₁= 23; v₁= 23
u₁+ v₂= 46; 0 + v₂= 46; v₂= 46
u₇+ v₂= 2; 46 + u₇= 2; u₇= -44
u₁+ v₄= 15; 0 + v₄= 15; v₄= 15
u₄+ v₄= 3; 15 + u₄= 3; u₄= -12
u₄+ v₃= 10; -12 + v₃= 10; v₃= 22
u₅+ v₃= 1; 22 + u₅= 1; u₅= -21
u₄+ v₈= 13; -12 + v₈= 13; v₈= 25
u₆+ v₈= 11; 25 + u₆= 11; u₆= -14
u₁+ v₅= 22; 0 + v₅= 22; v₅= 22
u₈+ v₅= 9; 22 + u₈= 9; u₈= -13
u₁+ v₆= 9; 0 + v₆= 9; v₆= 9
u₃+ v₆= 3; 9 + u₃= 3; u₃= -6
u₁+ v₇= 37; 0 + v₇= 37; v₇= 37
u₂+ v₇= 14; 37 + u₂= 14; u₂= -23

	v₁=23	v₂=46	v₃=22	v₄=15	v₅=22	v₆=9	v₇=37	v₈=25
u₁=0	23[1]	46[0]	40	15[0]	22[0]	9[0]	37[0]	37
u₂=-23	23	26	5	29	36	38	14[1]	40
u₃=-6	12	38	29	33	22	3[1]	49	49
u₄=-12	34	48	10[0]	3[1]	21	17	48	13[0]
u₅=-21	16	34	1[1]	43	32	40	11	19
u₆=-14	26	25	25	9	16	5	48	11[1]
u₇=-44	10	2[1]	37	18	11	18	39	45
u₈=-13	24	41	36	33	9[1]	35	47	39

	1	2	3	4	5	6	7	8	Запасы
1	23[1]	46[0][-]	40	15[0][+]	22[0]	9[0]	37[0]	37	1
2	23	26	5	29	36	38	14[1]	40	1
3	12	38	29	33	22	3[1]	49	49	1
4	34	48	10[0]	3[1][-]	21	17	48	13[0][+]	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25[+]	25	9	16	5	48	11[1][-]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
Потребности	1	1	1	1	1	1	1	1

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

	1	2	3	4	5	6	7	8
1	23[1]	46	40	15[0]	22[0]	9[0]	37[0]	37	1
2	23	26	5	29	36	38	14[1]	40	1
3	12	38	29	33	22	3[1]	49	49	1
4	34	48	10[0]	3[1]	21	17	48	13[0]	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25[0]	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

Проверим оптимальность опорного плана.
u₁+ v₁= 23; 0 + v₁= 23; v₁= 23
u₁+ v₄= 15; 0 + v₄= 15; v₄= 15
u₄+ v₄= 3; 15 + u₄= 3; u₄= -12
u₄+ v₃= 10; -12 + v₃= 10; v₃= 22
u₅+ v₃= 1; 22 + u₅= 1; u₅= -21
u₄+ v₈= 13; -12 + v₈= 13; v₈= 25
u₆+ v₈= 11; 25 + u₆= 11; u₆= -14
u₆+ v₂= 25; -14 + v₂= 25; v₂= 39
u₇+ v₂= 2; 39 + u₇= 2; u₇= -37
u₁+ v₅= 22; 0 + v₅= 22; v₅= 22
u₈+ v₅= 9; 22 + u₈= 9; u₈= -13
u₁+ v₆= 9; 0 + v₆= 9; v₆= 9
u₃+ v₆= 3; 9 + u₃= 3; u₃= -6
u₁+ v₇= 37; 0 + v₇= 37; v₇= 37
u₂+ v₇= 14; 37 + u₂= 14; u₂= -23

	v₁=23	v₂=39	v₃=22	v₄=15	v₅=22	v₆=9	v₇=37	v₈=25
u₁=0	23[1]	46	40	15[0]	22[0]	9[0]	37[0]	37
u₂=-23	23	26	5	29	36	38	14[1]	40
u₃=-6	12	38	29	33	22	3[1]	49	49
u₄=-12	34	48	10[0]	3[1]	21	17	48	13[0]
u₅=-21	16	34	1[1]	43	32	40	11	19
u₆=-14	26	25[0]	25	9	16	5	48	11[1]
u₇=-37	10	2[1]	37	18	11	18	39	45
u₈=-13	24	41	36	33	9[1]	35	47	39

Опорный план не является оптимальным.
(3;1): -6 + 23 > 12; ∆₃₁= -6 + 23 - 12= 5
(5;7): -21 + 37 > 11; ∆₅₇= -21 + 37 -11 = 5
max(5,5) = 5
Выбираем максимальную оценку свободной клетки (3;1): 12

	1	2	3	4	5	6	7	8
1	23[1][-]	46	40	15[0]	22[0]	9[0][+]	37[0]	37	1
2	23	26	5	29	36	38	14[1]	40	1
3	12[+]	38	29	33	22	3[1][-]	49	49	1
4	34	48	10[0]	3[1]	21	17	48	13[0]	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25[0]	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

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

	1	2	3	4	5	6	7	8
1	23[0]	46	40	15[0]	22[0]	9[1]	37[0]	37	1
2	23	26	5	29	36	38	14[1]	40	1
3	12[1]	38	29	33	22	3	49	49	1
4	34	48	10[0]	3[1]	21	17	48	13[0]	1
5	16	34	1[1]	43	32	40	11	19	1
6	26	25[0]	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

Проверим оптимальность опорного плана.
u₁+ v₁= 23; 0 + v₁= 23; v₁= 23
u₃+ v₁= 12; 23 + u₃= 12; u₃= -11
u₁+ v₄= 15; 0 + v₄= 15; v₄= 15
u₄+ v₄= 3; 15 + u₄= 3; u₄= -12
u₄+ v₃= 10; -12 + v₃= 10; v₃= 22
u₅+ v₃= 1; 22 + u₅= 1; u₅= -21
u₄+ v₈= 13; -12 + v₈= 13; v₈= 25
u₆+ v₈= 11; 25 + u₆= 11; u₆= -14
u₆+ v₂= 25; -14 + v₂= 25; v₂= 39
u₇+ v₂= 2; 39 + u₇= 2; u₇= -37
u₁+ v₅= 22; 0 + v₅= 22; v₅= 22
u₈+ v₅= 9; 22 + u₈= 9; u₈= -13
u₁+ v₆= 9; 0 + v₆= 9; v₆= 9
u₁+ v₇= 37; 0 + v₇= 37; v₇= 37
u₂+ v₇= 14; 37 + u₂= 14; u₂= -23

	v₁=23	v₂=39	v₃=22	v₄=15	v₅=22	v₆=9	v₇=37	v₈=25
u₁=0	23[0]	46	40	15[0]	22[0]	9[1]	37[0]	37
u₂=-23	23	26	5	29	36	38	14[1]	40
u₃=-11	12[1]	38	29	33	22	3	49	49
u₄=-12	34	48	10[0]	3[1]	21	17	48	13[0]
u₅=-21	16	34	1[1]	43	32	40	11	19
u₆=-14	26	25[0]	25	9	16	5	48	11[1]
u₇=-37	10	2[1]	37	18	11	18	39	45
u₈=-13	24	41	36	33	9[1]	35	47	39

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i+ v_i> c_ij
(5;7): -21 + 37 > 11; ∆₅₇= -21 + 37 -11 = 5
Выбираем максимальную оценку свободной клетки (5;7): 11
Для этого в перспективную клетку (5;7) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	7	8
1	23[0]	46	40	15[0][+]	22[0]	9[1]	37[0][-]	37	1
2	23	26	5	29	36	38	14[1]	40	1
3	12[1]	38	29	33	22	3	49	49	1
4	34	48	10[0][+]	3[1][-]	21	17	48	13[0]	1
5	16	34	1[1][-]	43	32	40	11[+]	19	1
6	26	25[0]	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

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

	1	2	3	4	5	6	7	8
1	23[0]	46	40	15[0]	22[0]	9[1]	37	37	1
2	23	26	5	29	36	38	14[1]	40	1
3	12[1]	38	29	33	22	3	49	49	1
4	34	48	10[0]	3[1]	21	17	48	13[0]	1
5	16	34	1[1]	43	32	40	11[0]	19	1
6	26	25[0]	25	9	16	5	48	11[1]	1
7	10	2[1]	37	18	11	18	39	45	1
8	24	41	36	33	9[1]	35	47	39	1
	1	1	1	1	1	1	1	1

Проверим оптимальность опорного плана.
u₁+ v₁= 23; 0 + v₁= 23; v₁= 23
u₃+ v₁= 12; 23 + u₃= 12; u₃= -11
u₁+ v₄= 15; 0 + v₄= 15; v₄= 15
u₄+ v₄= 3; 15 + u₄= 3; u₄= -12
u₄+ v₃= 10; -12 + v₃= 10; v₃= 22
u₅+ v₃= 1; 22 + u₅= 1; u₅= -21
u₅+ v₇= 11; -21 + v₇= 11; v₇= 32
u₂+ v₇= 14; 32 + u₂= 14; u₂= -18
u₄+ v₈= 13; -12 + v₈= 13; v₈= 25
u₆+ v₈= 11; 25 + u₆= 11; u₆= -14
u₆+ v₂= 25; -14 + v₂= 25; v₂= 39
u₇+ v₂= 2; 39 + u₇= 2; u₇= -37
u₁+ v₅= 22; 0 + v₅= 22; v₅= 22
u₈+ v₅= 9; 22 + u₈= 9; u₈= -13
u₁+ v₆= 9; 0 + v₆= 9; v₆= 9

	v₁=23	v₂=39	v₃=22	v₄=15	v₅=22	v₆=9	v₇=32	v₈=25
u₁=0	23[0]	46	40	15[0]	22[0]	9[1]	37	37
u₂=-18	23	26	5	29	36	38	14[1]	40
u₃=-11	12[1]	38	29	33	22	3	49	49
u₄=-12	34	48	10[0]	3[1]	21	17	48	13[0]
u₅=-21	16	34	1[1]	43	32	40	11[0]	19
u₆=-14	26	25[0]	25	9	16	5	48	11[1]
u₇=-37	10	2[1]	37	18	11	18	39	45
u₈=-13	24	41	36	33	9[1]	35	47	39

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.
F(x) = 9*1 + 14*1 + 12*1 + 3*1 + 1*1 + 11*1 + 2*1 + 9*1 = 61

23	46	40	15	22	9	37	37
23	26	5	29	36	38	14	40
12	38	29	33	22	3	49	49
34	48	10	3	21	17	48	13
16	34	1	43	32	40	11	19
26	25	25	9	16	5	48	11
10	2	37	18	11	18	39	45
24	41	36	33	9	35	47	39

	1	2	3	4	5	6	7	8
1	23	46	40	15	22	9	37	37	1
2	23	26	5	29	36	38	14	40	1
3	12	38	29	33	22	3	49	49	1
4	34	48	10	3	21	17	48	13	1
5	16	34	1	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11	1
7	10	2	37	18	11	18	39	45	1
8	24	41	36	33	9	35	47	39	1
	1	1	1	1	1	1	1	1

23	46	40	15	22	9	37	37
23	26	5	29	36	38	14	40
12	38	29	33	22	3	49	49
34	48	10	3	21	17	48	13
16	34	1	43	32	40	11	19
26	25	25	9	16	5	48	11
10	2	37	18	11	18	39	45
24	41	36	33	9	35	47	39

	1	2	3	4	5	6	7	8
1	23	46	40	15	22	9	37	37	1
2	23	26	5	29	36	38	14	40	1
3	12	38	29	33	22	3	49	49	1
4	34	48	10	3	21	17	48	13	1
5	16	34	1	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11	1
7	10	2	37	18	11	18	39	45	1
8	24	41	36	33	9	35	47	39	1
	1	1	1	1	1	1	1	1

Решение задачи о назначении методом потенциалов

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

Поиск

Процесс

Сообщение

23	46	40	15	22	9	37	37
23	26	5	29	36	38	14	40
12	38	29	33	22	3	49	49
34	48	10	3	21	17	48	13
16	34	1	43	32	40	11	19
26	25	25	9	16	5	48	11
10	2	37	18	11	18	39	45
24	41	36	33	9	35	47	39

	1	2	3	4	5	6	7	8
1	23	46	40	15	22	9	37	37	1
2	23	26	5	29	36	38	14	40	1
3	12	38	29	33	22	3	49	49	1
4	34	48	10	3	21	17	48	13	1
5	16	34	1	43	32	40	11	19	1
6	26	25	25	9	16	5	48	11	1
7	10	2	37	18	11	18	39	45	1
8	24	41	36	33	9	35	47	39	1
	1	1	1	1	1	1	1	1