4.3. Задача оптимального выбора

Во многих случаях применения ТПР рассматривают следующие задачи. Имеется множество объектов (предметов, процессов, проектов, зданий и т.д.), требуется выбрать из этого множества оптимальное подмножество объектов, удовлетворяющих заданному требованию.

Пусть в распоряжении ЛПР имеется объектов. Факт выбора или не выбора j-го объекта осуществляется с помощью переменной

. (4.43)

На выбор объекта обычно накладываются технические, экономические и другие ограничения, которые в общем виде записываются как

, (4.44)

где и – вектора неконтролируемых факторов, – вектор искомых переменных вида (4.43).

Мощность искомого подмножества объектов может быть как ограниченной так и не ограниченной, в частности, если это подмножество должно включать не более и не менее элементов, то

. (4.45)

Если по условию задачи необходимо выбрать из элементов только один элемент, то условие (4.45) примет вид:

. (4.46)

Формирование оптимального множества объектов осуществляется с помощью скалярной или векторной целевой функции (один или много критериев), которая записывается как:

. (4.47)

Таким образом, выражения (4.47), (4.45), (4.44), (4.43) описывают многокритериальную, нелинейную, дискретную модель задачи оптимального выбора. При получим однокритериальную модель решаемой задачи. В настоящее время на практике в основном используют однокритериальные линейные модели. Рассмотрим примеры задач оптимального выбора.

4.3.1. Задача о ранце

Имеется ранец объемом b. Дано N предметов, при этом j-й предмет имеет ценность и объем a_j, . Требуется определить, какие предметы следует загрузить в ранец, чтобы суммарная ценность предметов была максимальной при ограничении на допустимый объем ранца.

Из постановки задачи следует, что она имеет смысл при .

Пусть – признак загрузки j-го предмета в ранец, .

Формализуем целевую функцию и ограничения суммарного объема предметов в следующем виде:

. (4.48)

Ограничения на допустимый объем запишем так:

; (4.49)

. (4.50)

Таким образом, выражения (4.48) - (4.50) представляют собой ММ задачи о ранце. Для решения задач о ранце используют различные методы, имеющие разную трудоемкость, при этом иногда необходимо получить не оптимальное решение, а близкое к нему. Поэтому в этом случае используют эвристический метод. Алгоритм эвристического метода включает в себя следующие этапы:

1) Отсортировать все предметы по убыванию ценности , .

2) Загрузить в ранец самый ценный предмет.

3) Выбрать следующий j-й предмет и проверить ограничение на объем b ранца с учетом уже загруженных предметов.

4) Если ограничение выполнено, то загрузить j-й предмет в ранец, в противном случае этот предмет не загружать, а выбрать следующий по ценности (j+1)-й предмет с проверкой ограничения и т.д.

5) Выбрать следующий, менее ценный предмет и проверить ограничение. Далее – согласно п. 4 до тех пор, пока все предметы будут выбраны.

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

,

где m_j – масса каждого предмета.