Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

3.4. Векторный параметр состояния. Проблема большой размерности

Серьезные трудности возникают при появлении векторного параметра состояния Вq. Условия, в которых это

происходит, иллюстрирует следующая задача: найти


∀xj≥0-целые числа (случай m = 2).

Полагая, как и ранее, все a1j, a2j, b1n, b2n положительными и целыми, заметим, что любая функция из последовательности Ψq (q = 1,...,n) является теперь функцией

двух аргументов b1q и b2q, где


поскольку все хq, по которым ищутся максимумы вида max{fq(xq)+q-1}, должны удовлетворять требованиям


Это возможно тогда, когда неотрицательная величина хq не превышает меньшего из значений [biq/aiq] (i = 1, 2), т. е. 0≤xq≤min{[b1q/a1q], [b2q/a2q]}. Следовательно, приступая

к определению


необходимо предварительно найти


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

последовательность функций



Вместе с Ψq определяется и x̂q(b1q, b2q); для q = n имеем


Если свести всю информацию Ψq и x̂q в таблицы, то для каждого номера q придется включить b1nb2n значений δq и такое же количество значений Ψq, x̂q, найденных в результате решения задач об отыскании максимумов сумм fqq-1; после этого q-я таблица примет вид (табл. 3.3)

Таблица 3.3
Таблица 3.3

Ясно, что не только заполнить, но и использовать такие таблицы для получения оптимальных x*n-k = x̂n-k (b*1, n-k, b*2, n-k) чрезвычайно трудно (особенно когда b1n и b2n достигают десятков и сотен единиц) . В этом - главное препятствие на пути использования метода динамического программирования в задачах с векторным параметром Bq. Даже небольшое число составляющих Вq (порядка 3-4) может привести к неразрешимости задачи из-за чрезмерных требований к объемам памяти и быстродействию вычислительных машин. В основе этого утверждения лежит очевидная оценка


связывающая количество М чисел δq, х̂q, Ψq подлежащих запоминанию, с величинами bin, входящими в ограничения


(i = 1,....,m). Если m = 2, b1n = b2n = 10, то M=300 (объем таблицы типа 3.3), но при m = 4, bin = 100 (i = 1, 4) получаем М = 3 × 108. К тому же с ростом числа составляющих Вq усложняются процедуры поиска δq и особенно x̂q, что вызывает дополнительные затраты средств и времени на реализацию метода.

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


при


целые числа.

Сохраняя все предыдущие рассуждения, нетрудно показать, что основное функциональное уравнение записывается в рассматриваемом случае как


(для этого достаточно зафиксировать сначала величины хn, yn, затем представить x* в виде


Таким образом, особенностью здесь является усложнение исследований, проводимых в рамках очередного этапа с целью указать X̂q = (x̂q, ŷq) (решается многомерная оптимизационная задача).

Рис. 3.2
Рис. 3.2

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

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

вариации ограничивающих условий приводят лишь к изменению деталей этого соотношения, не затрагивая его структуры в целом (анализ функциональных уравнений другого типа станет необходимым при переходе к какому-либо новому классу задач). Линейные ограничения-неравенства,

рассмотренные выше, были выбраны из соображений простоты и наглядности оценок, характеризующих основные этапы решения (прежде всего упростилось определение пределов, в которых изменяются значения xq и bq (q = 1,...., n-1)). В более сложных случаях могут возникнуть трудности поиска и описания параметров bq, функций Ψq, решений x̂q. Ниже даны иллюстративные примеры.

Пример: найти x1, х2, х3 → max {z = ln (1 + х1) + х2 + х23} при x1 + x2 + x3 ≤ 1, ∀xj ≥0 (j = 1,...., 3), x3-целое число (здесь bn ≡ b3 = 1).

Решение: ищем первую функцию состояния Ψ1 = max {ln(1+x1)} при 0≤b2≤1, 0≤b1≤1, где b1 = 1-x3-x2; для этого достаточно построить график (рис. 3.2), дающий x̂1 = b1 и Ψ1 = ln (1+x̂1) = ln (1+b1);

функция 2 определяется как Ψ2 = max {x21} при 0≤b2≤1, 0≤b2≤1, где b2 = 1-x3; пользуясь соотношением b1 = b22, получаем Ψ1 = ln(1+b2-x2) и, следовательно,


производная


обращается в нуль при х2=b2, поэтому (после проверки достаточных условий экстремума) принимаем х̂2 = b2 и Ψ2 = x̂2+ln (1+b22) = b2;

функция


учитывая равенство b2 = 1 - х3, имеем


переменная х3 целочисленно и в условиях рассматриваемой задачи может принимать лишь значения 0, 1; независимо от этого x23+1-x3=1 следовательно, x̂3(I) = 0 и x̂3(II) = 1;

теперь остается выбрать из имеющихся x̂j (j = 1,....,3) те значения,, которые будут приняты в качестве x*j; положив x*3(I) = 0 и x*3(II) = 1, получаем b*2(I) = 1-x*3(I) = 1 и x*2(II) = 0, что дает x*2(I) = x*2(II) = 0; далее, b*1(I) = 1-x*3(I)-x*2(I) = 0, b*1(II) = 0, т. е. x*1(I) = x*1(II) = 0;

таким образом, найдены оптимальные решения: x*1 = 0, x*2 = 1, x*3 = 0, z* = 1 и x*1 = 0, x*2 = 0, x*3 = 1, z* = l.

Пример: найти


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

Решение: первая функция состояния представляется в данном случае как


где

b11 = 1 - x3, b221 = 1 - х23 и 0≤b11≤1, 0≤b221≤1; поскольку величина х3 не превышает 1, имеем b11≤b221 (знак равенства появляется лишь при x3 = 0 или x3 = 1); следовательно, достаточно рассматривать область допустимых x1, х2, показанную на рис. 3.3;

величина ex1+x2 тем больше, чем больше сумма с = х1 + х2; увеличение с (от значения b11) возможно до тех пор, пока система


имеет решения; предельным в этом смысле является с = b21√2 (рис. 3 3), поэтому х̂1 = х̂2 = b21√2/2 и Ψ1,2 = eb21√2;

функция Ψ3 ищется в виде


качественный анализ изменения величин в фигурных скобках показывает, что искомый максимум достигается при х̂3 = 0 и составляет e√2≈4,1;

положив х*3 = х̂3 = 0, находим b221 = 1, т. е. х*1 = х*2 = √2/2; решение задачи в целом есть x*1 = √2/2, х*2 = √2/2, х*3 = 0, z* = 4,1.

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

Рис. 3.3
Рис. 3.3

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"