Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Создание схемы логических элементов
Примеры решений Теория игр Задача о назначениях Поток сети
Транспортная задача Графический метод Решение дифф уравнений
Симплексный метод Двойственная задача Параметры сетевой модели

Пример решения задачи коммивояжера венгерским методом

Исходная матрица имеет вид:
M 3 4 2 7
5 M 8 4 3
2 3 M 7 5
3 2 9 M 1
1 2 3 5 M

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
M 1 2 0 5 2
2 M 5 1 0 3
0 1 M 5 3 2
2 1 8 M 0 1
0 1 2 4 M 1

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
M 0 0 0 5
2 M 3 1 0
0 0 M 5 3
2 0 6 M 0
0 0 0 4 M
0 1 2 0 0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
M [-0-] [-0-] [0] 5
2 M 3 1 [0]
[0] [-0-] M 5 3
2 [0] 6 M [-0-]
[-0-] [-0-] [0] 4 M

В результате получаем эквивалентную матрицу Сэ:
M 0 0 0 5
2 M 3 1 0
0 0 M 5 3
2 0 6 M 0
0 0 0 4 M

4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
M [-0-] [-0-] [0] 5
2 M 3 1 [0]
[0] [-0-] M 5 3
2 [0] 6 M [-0-]
[-0-] [-0-] [0] 4 M

Cmin = 2 + 3 + 2 + 2 + 3 = 12 Скачать в формате doc

Пример 2. Исходная матрица имеет вид:

M 69 15 41 46 62
22 M 77 43 41 60
57 78 M 13 27 82
61 61 53 M 43 68
38 54 34 22 M 43
2 8 78 81 52 M

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
M 54 0 26 31 47 15
0 M 55 21 19 38 22
44 65 M 0 14 69 13
18 18 10 M 0 25 43
16 32 12 0 M 21 22
0 6 76 79 50 M 2

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
M 48 0 26 31 26
0 M 55 21 19 17
44 59 M 0 14 48
18 12 10 M 0 4
16 26 12 0 M 0
0 0 76 79 50 M
0 6 0 0 0 21

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
M 48 [0] 26 31 26
[0] M 55 21 19 17
44 59 M [0] 14 48
18 12 10 M [0] 4
16 26 12 [-0-] M [0]
[-0-] [0] 76 79 50 M

В результате получаем эквивалентную матрицу Сэ:
M 48 0 26 31 26
0 M 55 21 19 17
44 59 M 0 14 48
18 12 10 M 0 4
16 26 12 0 M 0
0 0 76 79 50 M

4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
M 48 [0] 26 31 26
[0] M 55 21 19 17
44 59 M [0] 14 48
18 12 10 M [0] 4
16 26 12 [-0-] M [0]
[-0-] [0] 76 79 50 M

 Cmin = 15 + 22 + 13 + 43 + 43 + 8 = 144

Скачать в формате doc