РАЗДЕЛ 2
ВОЗМОЖНЫЕ ПОДХОДЫ К РЕШЕНИЮ СЛОЖНЫХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ
Многие важные задачи дискретного программирования, например, задачи о ранце, о
нахождении максимальной клики и др., являются трудно решаемыми – они
принадлежат к множеству NP-полных задач [68]. Это означает, что неизвестны
точные полиномиальные алгоритмы для их решения.
Точные методы при решении задач больших размерностей зачастую просто не могут
гарантировать получение окончательного результата за приемлемое время, так как
с увеличением числа переменных и ограничений трудоемкость вычислений резко
возрастает. Многие же важные задачи планирования, проектирования и управления
характеризуются большой размерностью. Часто в пользу приближенных методов
говорит и сам опыт решения реальных дискретных оптимизационных задач:
получаемые приближенные решения удовлетворяют запросам практики, а на их поиск
тратится нередко несравненно меньше машинного времени и других ресурсов (что
особенно важно, когда оптимизационные задачи решаются в реальном масштабе
времени). Кроме того, следует учесть, что в большинстве случаев при решении
задач используются модели, которые лишь приближенно отражают действительные
взаимоотношения и реальные ситуации, а исходные данные задач являются
случайными, весьма приближенными и получение точного решения этих задач лишено
смысла.
Перечисленные обстоятельства свидетельствуют о том, что разработка
быстродействующих приближенных алгоритмов, различных подходов к получению
приближенных решений является актуальной задачей.
Этой проблеме и посвящен данный раздел.
2.1. Метод вероятностной декомпозиции для решения задач целочисленного
линейного программирования с булевыми переменными
В данном подразделе предлагается следующий подход к решению задач
целочисленного линейного программирования с булевыми переменными большой
размерности: рассматриваемая задача случайным образом разбивается на несколько
подзадач меньшей размерности, решение которых затем используется для получения
приближенного решения исходной задачи. Этот подход, именуемый в дальнейшем
методом вероятностной декомпозиции, базируется на идеях работы [85]. Далее
описана и проанализирована процедура случайного разбиения рассматриваемой
задачи на подзадачи; установлены условия, при которых решение, полученное из
решений подзадач, будет близким (по функции цели) к оптимальному решению
исходной задачи; получены оценки этой близости. Метод вероятностной
декомпозиции позволяет свести решение обычной определенной задачи к решению
множества случайно задаваемых задач, которые, являясь задачами с
неопределенными данными, тем не менее, несут в себе информацию об исходной
задаче.
Рассмотрим следующую задачу:
максимизировать
(2.1)
при ограничениях
(2.2)
(2.3)
целые, j=1,…,n. (2.4)
Предполагается, что
Определим способ случайного разбиения исходной задачи на подзадачи. Зададим
натуральные числа такие, что Введем независимые случайные величины :
. (2.5)
Пусть реализация случайного вектора . Определим множества и .
Для r=1,...,q рассмотрим задачи вида:
максимизировать
(2.6)
при ограничениях
(2.7)
, (2.8)
целые, , (2.9)
где
. (2.10)
Если выполняются условия (2.10), то будем говорить, что исходная задача (2.1) -
(2.4) случайным образом разбита на подзадач
Пусть - точное решение подзадачи где – мощность множества Jr. Из условий (2.10)
следует, что вектор является допустимым решением исходной задачи (2.1) - (2.4).
Установим точность этого решения.
Для некоторого >0 введем ограничения
. (2.11)
Обозначим и соответственно точные решения задач (2.1) - (2.4) и (2.1), (2.11),
(2.3), (2.4).
Определение 2.1. Вектор x называется -оптимальным решением задачи (2.1) -
(2.4), если он удовлетворяет условиям (2.2) - (2.4) и .
Пусть , а – множество
- оптимальных решений задачи (2.1) - (2.4).
Зададим величины
(2.12)
(2.13)
(2.14)
Справедливо утверждение.
Теорема 2.1. Если задача (2.1) – (2.4) и числа q, , r=1,...,q, такие, что > 0,
то .
Доказательство. Рассмотрим случайные величины
, i=1,…,m, r=1,…q.
Если для всех i=1,…,m, то , r=1,…,q, является допустимым решением задачи вида
(2.6) – (2.9) и, следовательно, вектор при – -оптимальное решение задачи (2.1)
– (2.4).
Используя соотношения (2.5), (2.10), (2.12) и неравенство Хефдинга [72], оценим
вероятность этого события
Теорема доказана.
Замечание 2.1. Пусть i=1,...,m, величины и вычисляются не по формулам (2.10), а
следующим образом:
i=1,...,m, r=1,...,q, (2.15)
(2.16)
Тогда можно показать, что для величины , рассчитанной по формулам (2.13) и
(2.16), теорема 2.1 будет также справедлива.
Следствие 2.1. Если исходная задача (2.1) - (2.4) разбита с помощью описанной
выше случайной процедуры на q подзадач , r=1,..,q, - их точные решения, и , то
Пусть коэффициенты задачи (2.1) - (2.4) удовлетворяют следующим условиям:
i=1,..,m, j=1,..,n. В табл. 2.1 приведены значения вычисленные для различных
m,n (предполагается, что m=n, = n/q, r=1,..,q, q=10).
Таблица 2.1
Значения
m=n
0.09
0.03
0.01
0.003
0.0012
0.0004
При практическом решении задач вида (2.1)-(2.4) c использованием метода
вероятностной декомпозиции возникает вопрос: можно ли уменьшить значение и
насколько завышена оценка (насколько велика разность ). Анализ доказательства
теоремы 2.1 показывает, что значение можно уменьшить за счет снижения дисперсии
сумм i=1,..,m, r=1,..,q. Из формулы (2.12) следует, что наилучший в этом смысле
такой выбор - = n/q, r=1,..,q.
Опишем случайную процедуру получения множеств которая позволяет уменьшать
дисперсии сумм
- Київ+380960830922