48942 (Симплекс метод решения задачи линейного программирования), страница 2
Описание файла
Документ из архива "Симплекс метод решения задачи линейного программирования", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48942"
Текст 2 страницы из документа "48942"
Шаг 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
это и есть кратчайший путь.