Матрица № 4 Матрица № 5

П₂

n₃

П₂

П₁

Сумма 3

В матрице № 5 самый большой штраф – для клетки П₁-4. Поэтому исключаем из матрицы № 5 строку П₁ и столбец 4. Получаем матрицу № 6, в которой в столбце 3 отсутствует нулевое значение. После приведения получаем матрицу № 7, а общее условное уменьшение увеличивается на 6 миль, то есть 185+6=191 миля.

Матрица № 6 Матрица № 7

	П₂				Сумма4		П₂
		¥				¥
			¥				¥
				¥				¥

n₄

В матрице № 7 наибольший штраф – для ячейки 1-3, поэтому вычеркиваем строку 1 и столбец 3, одновременно запрещаем выбор маршрута 3-1. Таким образом, получаем матрицу № 8, у которой в столбце 1 отсутствует нулевое решение. Снова применяем операцию приведения и получаем матрицу № 9. При этом общее условное уменьшение увеличивается еще на 9 единиц и теперь оно составляет 191+9=200 миль, то есть какой бы маршрут не был выбран, оценка его нижней границы критерия эффективности не может быть менее 200 миль.

Матрица № 8 Матрица № 9

	П₂			Сумма		П₂
			¥			¥
		¥			¥

n₅

В матрице № 9 находятся две нулевые ячейки с одинаковым максимальным значением штрафа: 3-П₂ и 5-2. Выбираем ячейку 5-2 и вычеркиваем строку 5 и столбец 2. Одновременно запрещаем переход 2-П₂, так как это привело бы к окончанию вычислений, а у нас остался неиспользован еще один переход. Так получается матрица № 10.

Матрица № 10

	П₂
	¥	¥
	¥	¥

Из матрицы № 10 выбираем маршрут 2-1, после чего выбираем оставшийся маршрут 3-П₂.

Таким образом, мы получили следующие наивыгоднейшие маршруты:

4-5; П₁-4; 1-3; 5-2; 2-1; 3-П₂

Расположив их в порядке следования получим следующее:

П₁®4®5®2®1®3®П₂

25+31+37+23+45+39=200 миль

Полученный результат совпадает с оценкой нижней границы критерия эффективности и является наиболее оптимальным из всех возможных вариантов.

Примечательно также и то, что в данном случае совпадает как результат, полученный при использовании алгоритма Литтла, так и результат, который мы получили, если бы выбрали путем подбора, то есть, если бы интуитивно выбирать на каждом этапе маршрута по минимуму расстояния на отрезке пути.

Алгоритм Литтла не является самым оптимальным по отношении к количеству общей вычислительной работы, но он, несомненно, лучше, чем простой перебор всех возможных решений.

Вопросы для самопроверки

1. Три основные режима обработки рыбы на траулере.

2. Расчет показателей работы промысловой системы.

3. Расчет оптимальной величины улова за траление.

4. Учет реальных условий при реализации оптимального режима траления.

5. Сущность задачи коммивояжера.

6. Исходная матрица расстояний и ее преобразования.

7. Использование результатов решения на практике.

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

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: