Методы отсечения

Задача о назначениях.

Экстремальные, комбинированные задачи

Необходимо найти экстремум целевой функции, заданной на конечном множестве.

Пусть имеется n-работ и n-кандидатов на выполнение этих работ. Назначение i-того кандидата на j-работу связано с затратами

Требуется найти назначение всех кандидатов на все работы, дающие минимальные суммарные затраты. При этом каждого кандидата можно назначить только на одну работу и каждая работа может быть занята одним кандидатом.

Обозначим кандидатов и работы числами 1,2,…,n .

Тогда каждое назначение можно представить вектором , компонентами которого являются числа 1,2,…,n. При этом номер компоненты определяет номер кандидата, а значение компоненты – номер работы

Пусть n=5, p=(5,3,2,1,4), где р– перестановки.

Требуется найти такую перестановку из чисел 1,2,…,n, при которой достигается минимум суммы по всем перестановкам.

Решать можно простым перебором, если величина предельно мало. Так как n=5 cведем данную задачу к задаче целочисленного программирования.

Каждую перестановку мы можем представить в виде матрицы :

Матрица и ее элементы должны удовлетворять следующим условиям:

(5.1)

(5.2)

(5.1) – i-кандидат, а j-работа, суммирование по строке. Означает, что каждый кандидат может занять одну работу.

(5.2) – i-кандидат, а j-работа, суммирование по столбцу. Означает, что каждая работа может быть предназначена для одного кандидата.

Матрица в этом случае примет вид:

– матрица перестановки

Запишем модель задачи о назначениях:

Задача о коммивояжере.

Имеется n-городов, задана матрица . расстояний между городами (может быть и время, и стоимость). не обязательно равно .Выехав

Выехав из исходного города, коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в исходный город. Требуется найти маршрут минимальной длины.

Задача схожа с задачей о назначениях. Представим каждый маршрут перестановкой где

– номер города, в который коммивояжер переезжает с номером города i.

Затем требуется минимизировать «расстояние» .

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

циклическая перестановка нециклическая перестановка