Методы и алгоритмы решения задачи выбора (назначения) в классической постановке на расширенных множествах альтернатив

Постановка задач

Широкое применение во многих сферах управления техническими и экономическими объектами имеет следующая детерминированная задача принятия решения.

Имеется два равноценных множества элементов Qi и Qj , элементы которых нумеруются числами натурального ряда от 1 до n.

Множество управляющих воздействий характеризует наличие связи между элементами и , если , и отсутствие связи, если .

Каждой паре поставлено в соответствие неотрицательное число , характеризующее стоимость установления связи между и , т.е. y0Y определяется n числами .

Требуется для каждого найти единственный, связанный только с , элемент такой, при котором достигается минимум общей стоимости всех n связей, т.е. оценочная функция G имеет вид:

Множество допустимых управлений Uf ограничено условиями неповторяемости элементов и во всех связях:

Данную задачу называют задачей выбора или назначения.

Эту задачу можно трактовать как частный случай известных нелинейных распределений у задач.

Пусть имеется n складов, в каждом из которых хранится 1 единица ресурса, и n пунктов потребления, запрашивающих одну единицу ресурса, а также известны неотрицательные числа , определяющие стоимость доставки единицы ресурса из склада i в пункт потребления j.

Требуется распределить ресурсы между складами так, чтобы

(3.1)

и выполнялись ограничения

(3.2)

(3.3)

принимает значения только 1 или 0.

В первом случае ресурс со склада i поступит в пункт j , во втором случае этого не происходит.

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

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

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

Задача (3.1)…(3.3) - классическая задача выбора.

Задача, где (3.2), (3.3) имеют другой вид или отсутствуют - неклассическая.

Точные методы решения классической задачи выбора.

Точные методы - позволяют получать оптимальное решение задачи.

 
< Пред   СОДЕРЖАНИЕ   Скачать   След >