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

Для формирования алгоритмов решения классической задачи выбора на расширенных множествах альтернатив построим орграф специального вида, который назовём графом структур решения (ГСР). Каждая дуга этого графа будет соответствовать конкретному решению задачи или части задачи и нагружена компонентами критериев, по которым проводят оценку качества и сложности решения.

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

Каждая вершина в ГСР (кроме начальной с номером 0 - фиктивной) будет отражать факт решения соответствующей локальной задачи (подзадачи), а последняя вершина N - факт решения общей задачи.

Для классической задачи выбора один из вариантов ГСР представлен на рисунке 1. Здесь дуги имеют следующий смысл:

0-1 - расчёт элементов матрицы исходных данных А;

1-2 - решение задачи выбора каким-либо из точных методов, причём каждому методу должна соответствовать отдельная дуга и вершина;

1-3 - решение задачи каким-либо приближённым методом;

1-4 - декомпозиция задачи каким-либо методом на М локальных подзадач;

4-5 - решение каждой из М локальных задач каким-либо точным методом;

4-6 - решение каждой из М локальных задач каким-либо приближённым методом;

5-7 и 6-7 - формирование объединённого решения (рекомпозиция локальных решений);

1-8 - формирование вместо исходной задачи новой задачи;

8-9 - решение новой задачи;

9-10 - формирование решения исходной задачи по решению новой;

0-11 - формирование опорного решения из n независимых элементов матрицы А;

11-12 - последовательное формирование новых элементов матрицы А и улучшение опорного решения;

12-7 - контроль за выполнением условий останова решения и останов решения;

i-N - оформление и выдача решения (i=2, 3, 7, 10)

Рис. 34 ГСР классической задачи

Очевидно, что представленный на рисунке 1 граф структуры решения классической задачи выбора можно дополнить новыми маршрутами и каждый из имеющихся маршрутов детализировать и по последовательности решаемых подзадач, и по вариантам решения каждой подзадачи.

Рассмотрим маршрут ГСР, проходящий через вершины 0, 1, 8, 9, 10 и N, т.е. способ решения классической задачи выбора, состоящий в замене исходной задачи некоторой новой.

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

Будем считать, что каждый пункт потребления может переработать не одну единицу ресурса, а k_j (j=1,…,n) единиц, причём если для некоторого j k_jn, то возможен вариант решения, когда j-й пункт потребления один перерабатывает ресурсы всех складов.

В соответствии с этим запишем вместо (3.1)…(3.3) следующую задачу:

(3.13)

(3.14)

Очевидно, что для решения этой задачи необходимо найти минимальные элементы в каждой строке матрицы А:

(3.15)

и составить из них решение.

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

Назовём метод, реализующий данный подход, методом поэтапного выбора (МПВ).

С помощью МПВ можно получить приближённое решение исходной задачи. Для увеличения точности используем предварительное упорядочивание строк:

по мере уменьшения сумм их элементов;

по мере минимальных элементов строк;

по мере сумм минимальных и ближайших к ним () элементов строк;

по мере разностей и т.п.

Если в (3.14) хотя бы для одного j имеет место k_j1, k_jn, структуру решения не меняют, но в алгоритм вводят счётчики задействованных пунктов потребления. Столбец j исключают из рассмотрения, как только содержимое j-го счётчика станет равным k_j. Предварительное упорядочивание строк можно сохранить, хотя эта процедура и будет иметь меньшее значение.