Задача коммивояжера. Использование нелинейных разрешающих функций

Предлагаются два способа получения нижних границ для задачи коммивояжера (ЗК). Первый способ, основанный на линейном задании разрешающей функции $\varphi(t,y)$, использует для своего решения двухиндексную модель ЗК. Эта модель имеет достаточно много приложений. Второй способ, основанный на нелинейном задании разрешающей функции $\varphi(t,y)$, использует для своего решения одноиндексную модель ЗК. Эта модель оригинальная и позволяет существенно сократить процедуру ветвления в методе ветвей и границ для точного решения ЗК. Двухиндексную модель ЗК не позволяет использовать нелинейное задание разрешающей функции $\varphi(t,y)$.

Статья представлена к публикации членом редколлегии: А. А. Лазарев