Контрольная работа: Симплекс метод решения задачи линейного программирования
Шаг 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)