Метод дробления шага 1 страница

Для нахождения шага l, в методе наискорейшего спуска требу­ется решить уравнение (2.13), которое может оказаться доста­точно сложным. Поэтому часто ограничиваются «подбором» такого значения l, что . Для этого задаются некото­рым начальным значением l₁ (например, l₁ =1) и проверяют условие . Если оно не выполняется, то полагают

и т. д. до тех пор, пока не удается найти подходящий шаг, с кото­рым переходят к следующей точке х^(q+1). Критерий завершения алгоритма, очевидно, будет таким же, как и в методе наискорей­шего спуска.

21. Общий вид задач нелинейного программирования.

Можно выделить класс нелинейных задач, которые относятся к классическим методам оптимизации. Допустим что среди ограничений нет неравенств. Не обязательны условия неотрицательности. Переменные не являются дискретными, m < n, функции и f(X) непрерывны и имею т частные производные по крайней мере второго порядка. В этом случае задачу оптимизации можно сформулировать так: найти переменные х₁, х₂,…,х_n, удовлетворяющие системе уравнений (1)

и обращающее в максимум (минимум) целевую функцию z = f(х₁, х₂,…,х_n). (2)

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

Примером типичной и простой нелинейной задачи является следующая: данное предприятие для производства какого-то продукта расходует два средства в количестве х₁ и х₂ соответственно. Это факторы производства, например мамашины и труд, два различных вида сырья и т.п., а величины х₁ и х₂ – затраты факторов производства. Факторы производства впредь будем считать взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат машин в сопоставлении с величиной затрат труда больше или меньше (производство более или менее трудоемкое). В сельском хозяйстве взаимозаменяемыми факторами могут быть посевные площади или минеральные удобрения (экстенсивный или интенсивный метод производства).

Объем производства (выраженный в натуральных или стоимостных единицах) является функцией затрат производства z = f(х_1, х₂). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (х₁ и х₂) и от этих факторов (с₁ и с₂). Совокупные издержки выражаются формулой b = c₁ х₁ + c₂ х₂. требуется при данных совокупных издержках определить такое количество факторов производства. Которое максимизирует объем продукции z.

Математическая модель этой задачи имеет вид: определить такие переменные х₁ и х₂, удовлетворяющие условиям

(3) c₁ х₁ + c₂ х₂ = b,

х₁ , х₂ , при которых функция (4) z = f(х_1, х₂) достигает максимума.

Как правило, функция (4) может иметь произвольный нелинейный вид.

Пример решения ЗНП методом допустимых на­правлений. Рассмотрим процесс применения метода допусти­мых направлений на конкретном примере. Пусть дана ЗНП:

(2.26)

(2.27)

Итерация 1. В качестве начального приближения возьмем точку х⁽¹⁾ = (0,0). Нетрудно заметить, что она удовлетворяет системе неравенств (2.27), т. е. . Для х⁽¹⁾ все неравенства выполняются как строгие, т. е. множество индексов активных ограничений Æ. Следовательно, в х⁽¹⁾ любое направле­ние является допустимым, и нам остается определить, с каким шагом , можно двигаться вдоль градиента целевой функции . Система неравенств типа (2.18), из решения которых определяется интервал допустимых значений для , для данной задачи примет вид:

Тогда

достигается при . Отсюда получаем следующую точку

Итерация 2. Путем подстановки координат точки х⁽²⁾ в (2.27) определим множество активных ограничений в точке . Соответственно, задача (2.24) - (2.25), кото­рую требуется решить для определения допустимого прогрес­сивного направления s⁽²⁾ с учетом того, что и , примет вид:

В данном случае оптимальный план ЗЛП находится доволь­но просто и равен . Отбросив дополнитель­ную переменную s, получаем вектор s⁽²⁾ = (1,0), т. е. очередная точка будет определяться как

Действуя по аналогии с предыдущей итерацией, для опреде­ления промежутка допустимых значений шагового множителя составляем систему неравенств (2.18):

Окончательно имеем .

Тогда

достигается при . Отсюда получаем следующую точку x⁽³⁾ = (3,4).

Итерация 3. В точке х⁽³⁾ множество активных ограничений будет иметь вид . Найдем значения градиентов: , и .

Задача определения допустимого прогрессивного направле­ния (2.24)-(2.25) будет иметь вид:

Значение т из практических соображений следует брать до­статочно малым, например t = 0,001. Опуская решение данной задачи, приведем интересующие нас компоненты ее оптималь­ного плана: s⁽³⁾ = (0,0). Итак, не существует прогрессивного на­правления, исходящего из точки х⁽³⁾. Таким образом, оптималь­ный план рассматриваемой задачи (2.26)-(2.27) х^* = (4,3), а максимальное значение целевой функции .

Графическая иллюстрация проведенного процесса решения представлена графически на рис.

Рис.

22. Графический метод решения задач нелинейного программирования.

Пусть дана система неравенств вида (1) и функция (2), причем все функции являются выпуклыми на некотором выпуклом множестве М, а функция Z либо выпукла на множестве М, либо вогнута. Задача выпуклого программирования (ВП) состоит в отыскании такого решения системы ограничений (1), при котором целевая функция Z достигает минимального значения, или вогнутая функция Z достигает максимального значения. (Условия неотрицательности переменных можно считать включенными в систему(1)).

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

Задача: геометрически решить следующую задачу ВП: найти минимум функции при ограничениях:

Решение: Строим область допустимых решений данной задачи:

а). - окружность с центром в начале координат и радиусом R = 2 (рис.1). область решений неравенства состоит из точек, лежащих внутри этой окружности и на ней самой;

б). - прямая, которую можно построить, например по точкам (0,0) и (2,1). Область решений неравенства - полуплоскость, лежащая над этой прямой, включая и саму прямую;

в). - прямая, которая строится, например по точкам (0,0) и (1,2). Область решений неравенства - полуплоскость, лежащая под этой прямой, включая и саму прямую. Таким образом, с учетом условий неотрицательности переменных, областью допустимых решений данной задачи является замкнутый сектор ОАВ (рис.1).

Теперь построим линию уровня функции Z и определим направление убывания Z. Все линии уровня имеют уравнение Z=C, т.е. .При С = 3 получаем линию уровня - это окружность с центром в точке О₁(1,1) и радиусом R = 1.Ясно, что в любой точке этой линии уровня при перемещении от центра окружности О₁ функция Z возрастает, а при перемещении к центру – убывает. Таким образом, минимум Z достигается в точке (1,1), Z_min = 2 (нетрудно убедиться, что точка (1,1) является стационарной точкой функции Z).

Х₂

Рси.1

					В

Х₁

х₁=2х₂

х₂=2х₁

23. Динамическое программирование.

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

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

Общим для задач динамического программирования является то, что переменные рассматриваются не вместе, а последовательно, одна за другой. Сущность состоит в том, что строится такая вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом переменных (обычно даже одной) в каждой. Это значительно сокращает объем вычислений. Однако такое преимущество достигается лишь при двух условиях: когда критерий оптимальности аддитивен, т. е. общее оптимальное решение является суммой оптимальных решений каждого шага, и когда будущие результаты не зависят от предыстории того состояния системы, при котором принимается решение. Это вытекает из принципа оптимальности Беллмана, лежащего в основе теории динамического программирования. Из него же вытекает основной прием — нахождение правил доминирования, на основе которого на каждом шаге производится сравнение вариантов будущего развития и заблаговременное отсеивание заведомо бесперспективных вариантов. Когда эти правила обращаются в формулы, однозначно определяющие элементы последовательности один из других,' их называют разрешающими правилами. Несмотря на выигрыш в сокращении вычислений, их объем остается очень большим.

Можно выделить два наиболее общих класса задач, к которым в принципе мог бы быть применим этот метод, если бы не «проклятие размерности» (на самом деле на таких задачах, взятых в крайне упрощенном виде, пока удается лишь демонстрировать общие основы метода и анализировать экономико-математические модели). Первый — задача планирования деятельности экономического объекта (предприятия, отрасли и т. п.) с учетом изменения потребности в производимой продукции во времени. Второй класс задач — оптимальное распределение ресурсов между различными направлениями во времени. Сюда можно отнести, в частности, такую задачу: как распределить урожай зерна каждого года на питание и на семена, чтобы за ряд лет получить наибольшее количество хлеба?

Особенно эффективно применяется динамическое программирование тогда, когда по самому существу задачи приходится принимать решения по этапам. Покажем это на простом примере задачи ремонта и замены оборудования. На литейной машине шинного завода изготавливаются одновременно две шины — в двух формах. Если одна форма выходит из строя, машину приходится разбирать. При этом может оказаться выгодным заменить также и вторую форму, чтобы лишний раз не разбирать машину, если и эта форма выйдет из строя на следующем этапе. Более того, бывает, что есть смысл заменить обе формы до того, как одна из них выйдет из строя. Методом динамического программирования (с помощью дерева решений) определяется наилучшая стратегия в вопросе о замене форм с учетом всех факторов: выгоды от продолжения эксплуатации формы, потерь от простоя машины, стоимости забракованных шин и т. д.

24. Основные понятия динамического программирования.

Общая постановка и алгоритм решения задач методом динамического программирования. Будем считать, что состояние х^(к) рассматриваемой системы S на k-м шаге {к- 1, 2,..., n) определяется совокупностью чисел х^(к) = (, ,…, ),которые получены в результате реализации управления m_k, обеспечивающего переход системы S из состояния х^(к-1) в состояние х^(к).

Пусть также выполняются два условия:

1. Условие отсутствия последействия. Состояние х^(к), в которое перешла система S, зависит от исходного состояния х^(к-1) и выбранного управления m_k, и не зависит от того, каким образом система S перешла в состояние х^(к-1).

2. Условие аддитивности. Если в результате реализации k-го шага обеспечен определенный доход G _k(x_(k-1), m_k), также зависящий от исходного состояния системы х^(k-1) и выбранного управления m_k, то общий доход за n шагов составит , где m = (m₁, m₂,..., m_k)

Задача состоит в нахождении оптимальной стратегии управления, т. е. такой совокупности управлений m* = (m₁*, m₂*,..., m_k*),в результате реализации которых система S за n шагов переходит из начального состояния S_s = x⁽⁰⁾ в конечное S_f = x⁽ⁿ⁾ и при этом функция дохода G(m) принимает наибольшее значение.

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

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

Чтобы построить алгоритм решения задач, дадим математическую формулировку принципа оптимальности. Для этого введем некоторые дополнительные обозначения. Обозначив через максимальный доход, получаемый за n шагов при переходе системы S из начального состояния х⁽⁰⁾ в конечное состояние x⁽ⁿ⁾ при реализации оптимальной стратегии управления m* = (m₁*, m₂*,..., m_k*), а через F (x^(k)) — максимальный доход, получаемый при переходе из любого состояния х^(k) в конечное состояние х⁽ⁿ⁾ при оптимальной стратегии управления на оставшихся (n - к) шагах. Тогда

(1)

(2)

при к = 0, 1,2,..., n - 1.

Выражение (2) представляет собой математическую запись принципа оптимальности Беллмана и носит название основного функционального уравнения Беллмана. Используя уравнение (2) находится решение рассматриваемой задачи динамического программирования. Рассмотрим этот процесс более подробно.

Полагая к = n- 1 в уравнении Беллмана (2), получаем следующее функциональное уравнение: (3)

В (3) можно считать известным. Используя теперь уравнение (3) и рассматривая всевозможные допустимые состояния системы S на (n - 1)-м шаге ,..., находим условные оптимальные решения и соответствующие значения функции (3):

Таким образом, на п-и шаге находим условно оптимальное управление при любом допустимом состоянии системы после (n - 1)-го шага, т. е. в каком бы состоянии система не оказалась после (n - 1)-го шага, нам уже известно, какое следует принять решение на n-м шаге.

Перейдем теперь к рассмотрению функционального уравнения при
к = n – 2: (4)

Решая функциональное уравнение (4) при различных состояниях на (n - 2)-м шаге, получим условно оптимальные управления . Каждое из этих управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах.

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

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

25. Общая постановка задачи динамического программирования.

Общая постановка и алгоритм решения задач методом динамического программирования. Будем считать, что состояние х^(к) рассматриваемой системы S на k-м шаге {к- 1, 2,..., n) определяется совокупностью чисел х^(к) = (, ,…, ),которые получены в результате реализации управления m_k, обеспечивающего переход системы S из состояния х^(к-1) в состояние х^(к).

Пусть также выполняются два условия:

1. Условие отсутствия последействия. Состояние х^(к), в которое перешла система S, зависит от исходного состояния х^(к-1) и выбранного управления m_k, и не зависит от того, каким образом система S перешла в состояние х^(к-1).

2. Условие аддитивности. Если в результате реализации k-го шага обеспечен определенный доход G _k(x_(k-1), m_k), также зависящий от исходного состояния системы х^(k-1) и выбранного управления m_k, то общий доход за n шагов составит , где m = (m₁, m₂,..., m_k)

Задача состоит в нахождении оптимальной стратегии управления, т. е. такой совокупности управлений m* = (m₁*, m₂*,..., m_k*),в результате реализации которых система S за n шагов переходит из начального состояния S_s = x⁽⁰⁾ в конечное S_f = x⁽ⁿ⁾ и при этом функция дохода G(m) принимает наибольшее значение.

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

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