Вариант 1: задача 3. Исходные данные KS= минут Решение. Для решения указанной задачи получим преобразованную матрицу

  • ID: 32603 
  • 4 страницы

Фрагмент работы:

ЗАДАЧА № 3

Исходные данные

KS=60 минут

Решение:

Для решения указанной задачи получим преобразованную матрицу. Заголовок в преобразованную матрицу записываем без изменения, а элементы основной части матрицы рассчитываем по формуле:

[image]

Преобразованная матрица будет иметь вид

Наибольший элемент среди элементов основной части матрицы равен 48. Таким образом, включаем в маршрут проход 11-9: 1-11-9-1

Выполняем контроль срока:

Тобсл=34+15+28=77 мин

Полученное время обслуживания больше KS=60, поэтому вычеркиваем этот элемент. Следующий максимальный элемент – это элемент 9-11. Проверка показывает, что он тоже не удовлетворяет контрольному сроку обслуживания.

Аналогично будут зачеркнуты элементы 4-11, 11-4, 13-4, 3-4, 4-3, 4-13, 3-9, 2-9, 9-3, 10-4, 4-9, 4-10, 11-10, 11-12, 12-11, 2-13, 9-4, 10-11, 13-2, 13-11, 7-9, 13-9, 9-2, 9-13, 4-12, 6-4, 11-13, 12-4, 12-9, 2-11, 9-12, 11-2.

Наконец, будет найден элемент, удовлетворяющий контрольному сроку. Это элемент 12-3.

Текущий маршрут: 1-12-3-1.

Тобсл=22+10+19=51 мин

Вычеркиваем из преобразованной матрицы 12 строку и 3 столбец и закрываем элемент 3-12. Получаем следующую матрицу:

В оставшейся части матрицы вновь находим максимальный элемент. Это элемент 4-6. Текущий маршрут: 1-4-6-1.

Тобсл=36+19+13=68 мин

Полученное время обслуживания больше KS=60, поэтому вычеркиваем этот элемент. Далее будут вычеркнуты элементы 5-11, 7-11, 9-7, 11-7 и 8 -2. Следующий элемент, удовлетворяющий контрольному сроку – это элемент 8-13. Текущий маршрут: 1-8-13-1.

Тобсл=21+13+21=55 мин.

Вычеркиваем из преобразованной матрицы 8 строку и 13 столбец и закрываем элемент 13-8. Получаем следующую матрицу:

Далее вычеркиваем элементы, не удовлетворяющие контрольному сроку: 2-4, 4-5, 11-5, 5-4, 5-9, 9-10, 10-9, 2-6, 2-8, 3-10, 4-7, 6-2, 6-9, 7-4, 4-2, 4-8, 9-5, 9-6, 2-12, 5-2, 7-2, 13-5, 13-12, 2-5, 3-2, 10-12, 2-7, 3-11, 5-8. Находим элемент, удовлетворяющий контрольному сроку. Это элемент 5-10.

Текущий маршрут: 1-5-10-1.

Тобсл=20+18+18=56 мин.

Вычеркиваем из преобразованной матрицы 5 строку и 10 столбец и закрываем элемент 10-5. Получаем следующую матрицу: