Постановки задач целочисленного программирования
Пример. Задача целочисленного линейного программирования ( ЦЛП ).
Задачей ЦЛП называют следующую задачу оптимизации:
- целочисленно.
Здесь ,
,
. Элементы матрицы
и векторов
и
предполагаются целыми. На рис.1 приведен пример двумерной задачи ЦЛП.
Рис.1. Четыре целочисленные точки, ближайшие к оптимуму задачи ЛП, недопустимы.
В некоторых приложениях дробные решения недопустимы, например, в приложении, где - число самолетов, назначаемых на маршрут
. Задачи ЛП, формулируемые как задачи ЦЛП, как правило, по своей природе не допускают подхода, основанного на округлении. Один из эффектов округления - это потеря допустимости решения (см. рис.1).
Пример. (Задача коммивояжера (ЗК)). Коммивояжеру необходимо объехать городов
, начиная с города 1, и посещая каждый город ровно 1 раз, по самому короткому маршруту.
Обозначим матрицу расстояний между городами. Сопоставим дуге
переменную
и, положив
, если дуга
содержится в обходе, и
в противном случае, можно сформулировать ЗК следующим образом:
(a)
(4.1.1)
(б)
- целые
Равенства (а) выражают тот факт, что в каждую вершину входит ровно одна дуга, а равенства (б) - тот факт, что из каждой вершины выходит ровно одна дуга.
В действительности, задача (4.1.1) описывает задачу о назначении и содержит в своем допустимом множестве маршрутов маршруты, состоящие из нескольких замкнутых циклов. Нужны дополнительные ограничения для исключения подобных решений.