Лекции.Орг

Поиск:


Устал с поисками информации? Мы тебе поможем!

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




Пример. Задача целочисленного линейного программирования ( ЦЛП ).

Задачей ЦЛП называют следующую задачу оптимизации:

- целочисленно.

Здесь , , . Элементы матрицы и векторов и предполагаются целыми. На рис.1 приведен пример двумерной задачи ЦЛП.

 

Рис.1. Четыре целочисленные точки, ближайшие к оптимуму задачи ЛП, недопустимы.

 

В некоторых приложениях дробные решения недопустимы, например, в приложении, где - число самолетов, назначаемых на маршрут . Задачи ЛП, формулируемые как задачи ЦЛП, как правило, по своей природе не допускают подхода, основанного на округлении. Один из эффектов округления - это потеря допустимости решения (см. рис.1).

Пример. (Задача коммивояжера (ЗК)). Коммивояжеру необходимо объехать городов , начиная с города 1, и посещая каждый город ровно 1 раз, по самому короткому маршруту.

Обозначим матрицу расстояний между городами. Сопоставим дуге переменную и, положив , если дуга содержится в обходе, и в противном случае, можно сформулировать ЗК следующим образом:

(a) (4.1.1)

(б)

- целые

Равенства (а) выражают тот факт, что в каждую вершину входит ровно одна дуга, а равенства (б) - тот факт, что из каждой вершины выходит ровно одна дуга.

В действительности, задача (4.1.1) описывает задачу о назначении и содержит в своем допустимом множестве маршрутов маршруты, состоящие из нескольких замкнутых циклов. Нужны дополнительные ограничения для исключения подобных решений.






Дата добавления: 2015-02-12; Мы поможем в написании ваших работ!; просмотров: 452 | Нарушение авторских прав | Изречения для студентов


Читайте также:

Поиск на сайте:

Рекомендуемый контект:





© 2015-2021 lektsii.org - Контакты - Последнее добавление

Ген: 0.002 с.