Задача коммивояжера. Метод Гомори (постановка задачи, идея метода, построение отсечения)

↑

⇐ ПредыдущаяСтр 3 из 28Следующая ⇒

Постановка задачи. Бродячий торговец должен посетить п горо­дов и вернуться в исходный. Маршрут должен проходить через ка­ждый город, причем один и только один раз. Расстояния (транспорт­ные издержки, время на переезд и т.д.) между городами известны — . Требуется отыскать самый короткий маршрут.

Математическая модель:

 (1)

        (2)

          (3)

 — некоторый маршрут, L(x) — суммарные из­держки; (2) означает, что из каждого города торговец выезжает только раз; (3) означает, что в каждый город он въезжает один раз.

Метод Гомори.

Постановка задачи: найти  такое, что  при ограничениях — целые числа, -матрица.

Идея метода. Сначала решается соответствующая непрерывная задача (условия целочисленности не учитываются) симплекс-методом. Если полученный оптимальный план целочислен, то он будет решением исходной задачи. Если нет, то по одной из дробных компонент этого плана строится дополнительное ограничение (сечение Гомори ), которое "отсекает" его от множества планов, а все целочисленные остаются, непрерывная задача с дополнительным ограничением снова решается. При этом используется результат решения предыдущей задачи (последняя симплекс таблица) и ее удобно решать двойственным симплекс-методом. Если новый оптимальный план целочисленен, то получено решение исходной задачи, в противном случае операция (построения сечения Гомори) повто­ряется. И т.д. Доказано, что метод Гомори через конечное число таких операций позволяет построить решение задачи.

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США