Симплекс метод решения задачи линейного программирования (стр. 2 из 2)

Шаг 1. Приведем матрицу расстояний по строкам и столбцам

(в строке вычитаем из каждого элемента минимальный, затем в столбцах)

1	2	3	4	5	6
1	∞	18,87	49,48	51,86	80,51	97,42	18,87
2	18,87	∞	32,06	34,48	65,15	84,01	18,87
3	49,48	32,06	∞	31,76	61,19	83,20	31,76
4	51,86	34,48	31,76	∞	32,14	53,15	31,76
5	80,51	65,15	61,19	32,14	∞	22,14	22,14
6	97,42	84,01	83,20	53,15	22,14	∞	22,14

↓

1	2	3	4	5	6
1	∞	0	30,61	32,99	61,64	78,55
2	0	∞	13,19	15,61	46,28	65,14
3	17,72	0,30	∞	0	29,43	51,44
4	20,10	2,72	0	∞	0,38	21,39
5	58,37	43,01	39,05	10,00	∞	0
6	75,28	61,87	61,06	31,01	0	∞
0	0	0	0	0	0

↓

1	2	3	4	5	6
1	∞	0	30,61	32,99	61,64	78,55
2	0	∞	13,19	15,61	46,28	65,14
3	17,72	0,30	∞	0	29,43	51,44
4	20,10	2,72	0	∞	0,38	21,39
5	58,37	43,01	39,05	10,00	∞	0
6	75,28	61,87	61,06	31,01	0	∞

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (5 – 6)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6-5 ставим ∞).

1	2	3	4	5
1	∞	0	30,61	32,99	61,64
2	0	∞	13,19	15,61	46,28
3	17,72	0,30	∞	0	29,43
4	20,10	2,72	0	∞	0,38
6	75,28	61,87	61,06	31,01	∞

Далее повторяем шаги 1 – 4, пока не дойдем до одной клетки.

Второй этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.

1	2	3	4	5
1	∞	0	30,61	32,99	61,64
2	0	∞	13,19	15,61	46,28
3	17,72	0,30	∞	0	29,43
4	20,10	2,72	0	∞	0,38
6	75,28	61,87	61,06	31,01	∞
0	0	0	0	0,38

↓

1	2	3	4	5
1	∞	0	30,61	32,99	61,26
2	0	∞	13,19	15,61	45,90
3	17,72	0,30	∞	0	29,05
4	20,10	2,72	0	∞	0
6	75,28	61,87	61,06	31,01	∞

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (1 – 2)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 2 – 1 ставим ∞).

1	3	4	5
2	∞	13,19	15,61	45,90
3	17,72	∞	0	29,05
4	20,10	0	∞	0
6	75,28	61,06	31,01	∞

Третий этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.

1	3	4	5
2	∞	13,19	15,61	45,90
3	17,72	∞	0	29,05
4	20,10	0	∞	0
6	75,28	61,06	31,01	∞
17,72	0	0	0

↓

1	3	4	5
2	∞	13,19	15,61	45,90	13,19
3	0	∞	0	29,05	0
4	2,38	0	∞	0	0
6	57,56	61,06	31,01	∞	31,01

↓

1	3	4	5
2	∞	0	2,42	32,71
3	0	∞	0	29,05
4	2,38	0	∞	0
6	26,55	30,05	0	∞

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (4 – 5)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 4 ставим ∞).

1	3	4
2	∞	0	2,42
3	0	∞	0
6	26,55	30,05	∞

Четвертый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.

1	3	4
2	∞	0	2,42	0
3	0	∞	0	0
6	26,55	30,05	∞	26,55

↓

1	3	4
2	∞	0	2,42
3	0	∞	0
6	0	3,50	∞

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (3 – 4)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 3 ставим ∞).

1	3
2	∞	0
6	0	∞

Пятый этап.

Остались не задействованными связи 2 – 3 и 6 – 1.

В результате получаем следующую цепочку:

1→ 2→ 3 → 4→ 5→ 6 →1

Длина пути составляет:

L=18,87+32,06+31,76+32,14+22,14+97,42=234,39

это и есть кратчайший путь.