Примеры решений Транспортная задача Теория игр Поток сети Параметры сетевой модели Задача коммивояжера Метод Гомори Симплексный метод Графический метод Многоканальные СМО

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

Исходная матрица:
234640152293737
232652936381440
123829332234949
344810321174813
163414332401119
26252591654811
102371811183945
244136339354739

Решение можно найти через калькулятор.
Преобразуем матрицу к матрице тарифов, добавим фиктивных поставщиков и фиктивных потребителей (значения каждого из них равно единице).
12345678
12346401522937371
22326529363814401
31238293322349491
43448103211748131
51634143324011191
6262525916548111
71023718111839451
82441363393547391
11111111

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8
∑b = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 1. Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x53= min(1,1) = 1.
2346x1522937371
2326x29363814401
1238x3322349491
3448x3211748131
xx1xxxxx1 - 1 = 0
2625x916548111
102x18111839451
2441x3393547391
111 - 1 = 0111110

Искомый элемент равен 2
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x72= min(1,1) = 1.
23xx1522937371
23xx29363814401
12xx3322349491
34xx3211748131
xx1xxxxx0
26xx916548111
x2xxxxxx1 - 1 = 0
24xx3393547391
11 - 1 = 00111110

Искомый элемент равен 3
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x36= min(1,1) = 1.
23xx1522x37371
23xx2936x14401
xxxxx3xx1 - 1 = 0
34xx321x48131
xx1xxxxx0
26xx916x48111
x2xxxxxx0
24xx339x47391
100111 - 1 = 0110

Искомый элемент равен 3
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x44= min(1,1) = 1.
23xxx22x37371
23xxx36x14401
xxxxx3xx0
xxx3xxxx1 - 1 = 0
xx1xxxxx0
26xxx16x48111
x2xxxxxx0
24xxx9x47391
1001 - 1 = 010110

Искомый элемент равен 9
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x85= min(1,1) = 1.
23xxxxx37371
23xxxxx14401
xxxxx3xx0
xxx3xxxx0
xx1xxxxx0
26xxxxx48111
x2xxxxxx0
xxxx9xxx1 - 1 = 0
10001 - 1 = 00110

Искомый элемент равен 11
Для этого элемента запасы равны 1, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x68= min(1,1) = 1.
23xxxxx37x1
23xxxxx14x1
xxxxx3xx0
xxx3xxxx0
xx1xxxxx0
xxxxxxx111 - 1 = 0
x2xxxxxx0
xxxx9xxx0
10000011 - 1 = 00

Искомый элемент равен 14. x27= min(1,1) = 1.
23xxxxxxx1
xxxxxx14x1 - 1 = 0
xxxxx3xx0
xxx3xxxx0
xx1xxxxx0
xxxxxxx110
x2xxxxxx0
xxxx9xxx0
1000001 - 1 = 000

Искомый элемент равен 23. x11= min(1,1) = 1.
23xxxxxxx1 - 1 = 0
xxxxxx14x0
xxxxx3xx0
xxx3xxxx0
xx1xxxxx0
xxxxxxx110
x2xxxxxx0
xxxx9xxx0
1 - 1 = 000000000
12345678
123[1]46401522937371
22326529363814[1]401
312382933223[1]49491
43448103[1]211748131
516341[1]43324011191
626252591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111
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
12345678
123[1]46401522937371
22326529363814[1]401
312382933223[1]49491
43448103[1]211748131
516341[1]43324011191
626252591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111

Подсчитаем число занятых клеток таблицы, их 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. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vi. по занятым клеткам таблицы, в которых ui+ vi= cij, полагая, что u1 = 0.
u1+ v1= 23; 0 + v1= 23; v1= 23
u1+ v2= 46; 0 + v2= 46; v2= 46
u7+ v2= 2; 46 + u7= 2; u7= -44
u1+ v3= 40; 0 + v3= 40; v3= 40
u5+ v3= 1; 40 + u5= 1; u5= -39
u1+ v4= 15; 0 + v4= 15; v4= 15
u4+ v4= 3; 15 + u4= 3; u4= -12
u1+ v5= 22; 0 + v5= 22; v5= 22
u8+ v5= 9; 22 + u8= 9; u8= -13
u1+ v6= 9; 0 + v6= 9; v6= 9
u3+ v6= 3; 9 + u3= 3; u3= -6
u1+ v7= 37; 0 + v7= 37; v7= 37
u2+ v7= 14; 37 + u2= 14; u2= -23
u1+ v8= 37; 0 + v8= 37; v8= 37
u6+ v8= 11; 37 + u6= 11; u6= -26

v1=23v2=46v3=40v4=15v5=22v6=9v7=37v8=37
u1=023[1]46[0]40[0]15[0]22[0]9[0]37[0]37[0]
u2=-232326529363814[1]40
u3=-612382933223[1]4949
u4=-123448103[1]21174813
u5=-3916341[1]4332401119
u6=-2626252591654811[1]
u7=-44102[1]371811183945
u8=-13244136339[1]354739

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vi> cij
(2;3): -23 + 40 > 5; ∆23= -23 + 40 - 5= 12
(3;1): -6 + 23 > 12; ∆31= -6 + 23 - 12= 5
(3;2): -6 + 46 > 38; ∆32= -6 + 46 - 38= 2
(3;3): -6 + 40 > 29; ∆33= -6 + 40 - 29= 5
(4;3): -12 + 40 > 10; ∆43= -12 + 40 -10 = 18
(4;8): -12 + 37 > 13; ∆48= -12 + 37 -13 = 12
max(12,5,2,5,18,12) = 18
Выбираем максимальную оценку свободной клетки (4;3): 10
Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
12345678
123[1]46[0]40[0][-]15[0][+]22[0]9[0]37[0]37[0]1
22326529363814[1]401
312382933223[1]49491
4344810[+]3[1][-]211748131
516341[1]43324011191
626252591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111

Цикл приведен в таблице (4,3; 4,4; 1,4; 1,3; ).
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
12345678
123[1]46[0]4015[0]22[0]9[0]37[0]37[0]1
22326529363814[1]401
312382933223[1]49491
4344810[0]3[1]211748131
516341[1]43324011191
626252591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111

Проверим оптимальность опорного плана.
u1+ v1= 23; 0 + v1= 23; v1= 23
u1+ v2= 46; 0 + v2= 46; v2= 46
u7+ v2= 2; 46 + u7= 2; u7= -44
u1+ v4= 15; 0 + v4= 15; v4= 15
u4+ v4= 3; 15 + u4= 3; u4= -12
u4+ v3= 10; -12 + v3= 10; v3= 22
u5+ v3= 1; 22 + u5= 1; u5= -21
u1+ v5= 22; 0 + v5= 22; v5= 22
u8+ v5= 9; 22 + u8= 9; u8= -13
u1+ v6= 9; 0 + v6= 9; v6= 9
u3+ v6= 3; 9 + u3= 3; u3= -6
u1+ v7= 37; 0 + v7= 37; v7= 37
u2+ v7= 14; 37 + u2= 14; u2= -23
u1+ v8= 37; 0 + v8= 37; v8= 37
u6+ v8= 11; 37 + u6= 11; u6= -26
v1=23v2=46v3=22v4=15v5=22v6=9v7=37v8=37
u1=023[1]46[0]4015[0]22[0]9[0]37[0]37[0]
u2=-232326529363814[1]40
u3=-612382933223[1]4949
u4=-12344810[0]3[1]21174813
u5=-2116341[1]4332401119
u6=-2626252591654811[1]
u7=-44102[1]371811183945
u8=-13244136339[1]354739

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vi> cij
(3;1): -6 + 23 > 12; ∆31= -6 + 23 - 12= 5
(3;2): -6 + 46 > 38; ∆32= -6 + 46 - 38= 2
(4;8): -12 + 37 > 13; ∆48= -12 + 37 -13 = 12
(5;7): -21 + 37 > 11; ∆57= -21 + 37 -11 = 5
max(5,2,12,5) = 12
Выбираем максимальную оценку свободной клетки (4;8): 13
Для этого в перспективную клетку (4;8) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
12345678
123[1]46[0]4015[0][+]22[0]9[0]37[0]37[0][-]1
22326529363814[1]401
312382933223[1]49491
4344810[0]3[1][-]21174813[+]1
516341[1]43324011191
626252591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111

Цикл приведен в таблице (4,8; 4,4; 1,4; 1,8; ).
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 8) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
12345678Запасы
123[1]46[0]4015[0]22[0]9[0]37[0]371
22326529363814[1]401
312382933223[1]49491
4344810[0]3[1]21174813[0]1
516341[1]43324011191
626252591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
Потребности11111111

Проверим оптимальность опорного плана.
u1+ v1= 23; 0 + v1= 23; v1= 23
u1+ v2= 46; 0 + v2= 46; v2= 46
u7+ v2= 2; 46 + u7= 2; u7= -44
u1+ v4= 15; 0 + v4= 15; v4= 15
u4+ v4= 3; 15 + u4= 3; u4= -12
u4+ v3= 10; -12 + v3= 10; v3= 22
u5+ v3= 1; 22 + u5= 1; u5= -21
u4+ v8= 13; -12 + v8= 13; v8= 25
u6+ v8= 11; 25 + u6= 11; u6= -14
u1+ v5= 22; 0 + v5= 22; v5= 22
u8+ v5= 9; 22 + u8= 9; u8= -13
u1+ v6= 9; 0 + v6= 9; v6= 9
u3+ v6= 3; 9 + u3= 3; u3= -6
u1+ v7= 37; 0 + v7= 37; v7= 37
u2+ v7= 14; 37 + u2= 14; u2= -23
v1=23v2=46v3=22v4=15v5=22v6=9v7=37v8=25
u1=023[1]46[0]4015[0]22[0]9[0]37[0]37
u2=-232326529363814[1]40
u3=-612382933223[1]4949
u4=-12344810[0]3[1]21174813[0]
u5=-2116341[1]4332401119
u6=-1426252591654811[1]
u7=-44102[1]371811183945
u8=-13244136339[1]354739

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vi> cij
(3;1): -6 + 23 > 12; ∆31= -6 + 23 - 12= 5
(3;2): -6 + 46 > 38; ∆32= -6 + 46 - 38= 2
(5;7): -21 + 37 > 11; ∆57= -21 + 37 -11 = 5
(6;2): -14 + 46 > 25; ∆62= -14 + 46 -25 = 7
max(5,2,5,7) = 7
Выбираем максимальную оценку свободной клетки (6;2): 25.
12345678Запасы
123[1]46[0][-]4015[0][+]22[0]9[0]37[0]371
22326529363814[1]401
312382933223[1]49491
4344810[0]3[1][-]21174813[0][+]1
516341[1]43324011191
62625[+]2591654811[1][-]1
7102[1]3718111839451
8244136339[1]3547391
Потребности11111111
Цикл приведен в таблице (6,2; 6,8; 4,8; 4,4; 1,4; 1,2; ).
12345678
123[1]464015[0]22[0]9[0]37[0]371
22326529363814[1]401
312382933223[1]49491
4344810[0]3[1]21174813[0]1
516341[1]43324011191
62625[0]2591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111

Проверим оптимальность опорного плана.
u1+ v1= 23; 0 + v1= 23; v1= 23
u1+ v4= 15; 0 + v4= 15; v4= 15
u4+ v4= 3; 15 + u4= 3; u4= -12
u4+ v3= 10; -12 + v3= 10; v3= 22
u5+ v3= 1; 22 + u5= 1; u5= -21
u4+ v8= 13; -12 + v8= 13; v8= 25
u6+ v8= 11; 25 + u6= 11; u6= -14
u6+ v2= 25; -14 + v2= 25; v2= 39
u7+ v2= 2; 39 + u7= 2; u7= -37
u1+ v5= 22; 0 + v5= 22; v5= 22
u8+ v5= 9; 22 + u8= 9; u8= -13
u1+ v6= 9; 0 + v6= 9; v6= 9
u3+ v6= 3; 9 + u3= 3; u3= -6
u1+ v7= 37; 0 + v7= 37; v7= 37
u2+ v7= 14; 37 + u2= 14; u2= -23
v1=23v2=39v3=22v4=15v5=22v6=9v7=37v8=25
u1=023[1]464015[0]22[0]9[0]37[0]37
u2=-232326529363814[1]40
u3=-612382933223[1]4949
u4=-12344810[0]3[1]21174813[0]
u5=-2116341[1]4332401119
u6=-142625[0]2591654811[1]
u7=-37102[1]371811183945
u8=-13244136339[1]354739

Опорный план не является оптимальным.
(3;1): -6 + 23 > 12; ∆31= -6 + 23 - 12= 5
(5;7): -21 + 37 > 11; ∆57= -21 + 37 -11 = 5
max(5,5) = 5
Выбираем максимальную оценку свободной клетки (3;1): 12
12345678
123[1][-]464015[0]22[0]9[0][+]37[0]371
22326529363814[1]401
312[+]382933223[1][-]49491
4344810[0]3[1]21174813[0]1
516341[1]43324011191
62625[0]2591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111

Цикл приведен в таблице (3,1; 3,6; 1,6; 1,1; ).
12345678
123[0]464015[0]22[0]9[1]37[0]371
22326529363814[1]401
312[1]38293322349491
4344810[0]3[1]21174813[0]1
516341[1]43324011191
62625[0]2591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111

Проверим оптимальность опорного плана.
u1+ v1= 23; 0 + v1= 23; v1= 23
u3+ v1= 12; 23 + u3= 12; u3= -11
u1+ v4= 15; 0 + v4= 15; v4= 15
u4+ v4= 3; 15 + u4= 3; u4= -12
u4+ v3= 10; -12 + v3= 10; v3= 22
u5+ v3= 1; 22 + u5= 1; u5= -21
u4+ v8= 13; -12 + v8= 13; v8= 25
u6+ v8= 11; 25 + u6= 11; u6= -14
u6+ v2= 25; -14 + v2= 25; v2= 39
u7+ v2= 2; 39 + u7= 2; u7= -37
u1+ v5= 22; 0 + v5= 22; v5= 22
u8+ v5= 9; 22 + u8= 9; u8= -13
u1+ v6= 9; 0 + v6= 9; v6= 9
u1+ v7= 37; 0 + v7= 37; v7= 37
u2+ v7= 14; 37 + u2= 14; u2= -23
v1=23v2=39v3=22v4=15v5=22v6=9v7=37v8=25
u1=023[0]464015[0]22[0]9[1]37[0]37
u2=-232326529363814[1]40
u3=-1112[1]3829332234949
u4=-12344810[0]3[1]21174813[0]
u5=-2116341[1]4332401119
u6=-142625[0]2591654811[1]
u7=-37102[1]371811183945
u8=-13244136339[1]354739

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vi> cij
(5;7): -21 + 37 > 11; ∆57= -21 + 37 -11 = 5
Выбираем максимальную оценку свободной клетки (5;7): 11
Для этого в перспективную клетку (5;7) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
12345678
123[0]464015[0][+]22[0]9[1]37[0][-]371
22326529363814[1]401
312[1]38293322349491
4344810[0][+]3[1][-]21174813[0]1
516341[1][-]43324011[+]191
62625[0]2591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111

Цикл приведен в таблице (5,7; 5,3; 4,3; 4,4; 1,4; 1,7; ).
12345678
123[0]464015[0]22[0]9[1]37371
22326529363814[1]401
312[1]38293322349491
4344810[0]3[1]21174813[0]1
516341[1]43324011[0]191
62625[0]2591654811[1]1
7102[1]3718111839451
8244136339[1]3547391
11111111

Проверим оптимальность опорного плана.
u1+ v1= 23; 0 + v1= 23; v1= 23
u3+ v1= 12; 23 + u3= 12; u3= -11
u1+ v4= 15; 0 + v4= 15; v4= 15
u4+ v4= 3; 15 + u4= 3; u4= -12
u4+ v3= 10; -12 + v3= 10; v3= 22
u5+ v3= 1; 22 + u5= 1; u5= -21
u5+ v7= 11; -21 + v7= 11; v7= 32
u2+ v7= 14; 32 + u2= 14; u2= -18
u4+ v8= 13; -12 + v8= 13; v8= 25
u6+ v8= 11; 25 + u6= 11; u6= -14
u6+ v2= 25; -14 + v2= 25; v2= 39
u7+ v2= 2; 39 + u7= 2; u7= -37
u1+ v5= 22; 0 + v5= 22; v5= 22
u8+ v5= 9; 22 + u8= 9; u8= -13
u1+ v6= 9; 0 + v6= 9; v6= 9
v1=23v2=39v3=22v4=15v5=22v6=9v7=32v8=25
u1=023[0]464015[0]22[0]9[1]3737
u2=-182326529363814[1]40
u3=-1112[1]3829332234949
u4=-12344810[0]3[1]21174813[0]
u5=-2116341[1]43324011[0]19
u6=-142625[0]2591654811[1]
u7=-37102[1]371811183945
u8=-13244136339[1]354739

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
F(x) = 9*1 + 14*1 + 12*1 + 3*1 + 1*1 + 11*1 + 2*1 + 9*1  = 61
Метод Гомори
Метод Гомори
Метод Гомори. Решение задачи целочисленного программирования
Решить онлайн
Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн
Курсовые на заказ