Математические методы в принятии решений

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

Идея метода заключается  в том, что находятся значения частных производных по всем независимым  переменным – ∂Q / ∂uι , ι = 1, n , которые определяют направление градиента в рассматриваемой точке и осуществляется шаг в направлении обратном направлению градиента, т.е. в направлении наибыстрейшего убывания целевой функции (если ищется минимум). Итерационный процесс имеет вид

где параметр αk ≥ 0 задает длину шага.

Алгоритм метода градиента  при непосредственном его применении включает в себя следующие этапы.

1. Задается начальное значение вектора независимых переменных (u₁ ⁰, u₂⁰, ..., u_n⁰), определяющего точку, из которой начинается движение к минимуму.
2. Рассчитывается значение целевой функции в начальной точке Q₀(u₁ ⁰, u₂⁰, ..., u_n⁰).
3. Определяется направление градиента в начальной точке (рис. 3.10).

4. Делается шаг в направлении антиградиента при поиске минимума, в результате чего попадают в точку u₁.
5. Процесс поиска продолжается, повторяя все этапы с п. 2, т.е. вычисляется Q₁(u₁ ⁰, u₂⁰, ..., u_n⁰)4, определяется направление градиента в точке u₁, делается шаг и т.д.

Важной задачей в этом методе является выбор шага. Если размер шага слишком мал, то движение к оптимуму будет долгим из-за необходимости  расчета целевой функции и  ее частных производных в очень  многих точках. Если же шаг будет  выбран слишком большим, то в районе оптимума может возникнуть "рыскание", которое либо затухает слишком медленно, либо совсем не затухает. На практике сначала  шаг выбирается произвольно. Если окажется, что направление градиента в  точке u₁ существенно отличается от направления в точке u₂, то шаг уменьшают, если отличие векторов по направлению мало, то шаг увеличивают. Изменение направления градиента можно определять по углу поворота градиента рассчитываемого на каждом шаге по соответствующим выражениям.

Итерационный процесс  поиска обычно прекращается, если выполняются  неравенства u_k −u_k −1 ≤ ε, Q(u_k )−Q(u_k −1 ) / Q(u_k −1 )≤ δ, ∂Q(u_k )/ ∂u ≤ γ , где ε, δ, γ – заданные числа.

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

 

3.4.3 Метод наискорейшего  спуска

При применении метода градиента  на каждом шаге вычисляются значения всех частных производных оптимизируемой функции Q по всем независимым переменным U, что при большом числе этих переменных приводит к весьма большому времени поиска оптимума. Сократить время поиска позволяет метод наискорейшего спуска, блок-схема которого отображена на рис. 3.4, где ε – точность вычисления, H – величина шага, n – размерность вектора u, Q – алгоритм вычисления целевой функции Q (u), L – количество шагов по конкретному направлению градиента функции Q.

Таким образом, в начальной  точке u0 определяется градиент целевой функции δQ/δu_i и, следовательно, направление ее наибыстрейшего убывания; далее делается шаг спуска в этом направлении. Если значение целевой функции уменьшились, то делается следующий шаг в этом же самом направлении. Процедура повторяется до тех пор, пока в этом направлении не будет найден минимум, после чего только вычисляется градиент и определяется новое направление наибыстрейшего убывания целевой функции.

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

 

3.4.4 Метод квантования  симплексов

Симплексный метод относится  к группе безградиентных методов  детерминированного поиска. Основная идея метода заключается в том, что  по известным значениям функции  в вершинах выпуклого многогранника, называемого симплексом, находится  направление, в котором требуется  сделать следующий шаг, чтобы  получить наибольшее уменьшение (увеличение) критерия оптимальности. Примером симплекса  на плоскости является треугольник, в трехмерном пространстве – четырехгранная пирамида, в n-мерном пространстве – многогранник с n + 1 вершиной. Основным свойством симплекса является то, что против любой из вершин симплекса расположена только одна грань, на которой можно построить новый симплекс, отличающийся от прежнего расположением новой вершины, остальные вершины обоих симплексов – совпадают.

Наглядную иллюстрацию симплексного метода удобнее рассматривать на примере задачи отыскания минимального значения целевой функции двух независимых  переменных (рис. 3.11). Алгоритм поиска заключается  в следующем.

1. Определяются значения целевой функции в трех точках S10, S20, S30, соответствующих вершинам симплекса. Из найденных значений выбирается наибольшее. В рассматриваемом примере – это S10 (рис. 3.12).
2. Строится новый симплекс, для этого вершина S10 исходного симплекса заменяется вершиной S11, расположенной симметрично вершине S10 относительно центра грани, расположенной против вершины S10. Построение нового симплекса S20 S30 S11 осуществляется определением центра А стороны S20 S30 треугольника S10 S20 S30, после чего проводится прямая S10A, на продолжении которой откладывается отрезок АS11 равный S10А.
3. Вычисляется значение целевой функции в вершине S11, которое сравнивается с известными значениями в вершинах S20 и S30. В результате определяется вершина S30 с наибольшем значением целевой функции, подлежащая исключению при построении следующего симплекса S11 S20 S31, и т.д.

Исключение из рассмотренных  вершин симплексов с наибольшим значением  целевой функции приводит к сходимости процесса к минимальному значению.

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

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

 

3.4.5 Поиск при  наличии "оврагов" целевой  функции

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

1. Все независимые переменные разбиваются на две группы: первая группа включает в себя переменные, изменение которых существенно влияет на значение целевой функции, вторая группа содержит переменные, при изменении которых значение целевой функции изменяется не столь значительно.
2. Выбирается начальная точка u₀ , из которой производится поиск, будем считать для определенности, минимума любым методом локального поиска. Этот поиск закончится на дне "оврага", в результате чего будет найдена некоторая критическая точка u₁ (рис. 3.13).
3. Из выбранной начальной точки u₀ делается шаг в направлении наибольшего изменения переменных, несущественно влияющих на значение целевой функции, При этом получается некоторое состояние u₀¹ (рис. 3.13).
4. Из состояния u₀¹ производится поиск минимума, в результате которого определяется еще одна критическая точка u2, расположенная на дне "оврага" (рис. 3.13).

5. Две найденные критические точки u₁ и u₂ соединяются прямой и выполняется "шаг по оврагу" в направлении убывания целевой функции. Это дает новое исходное состояние u1¹ .
6. Из состояния u₁¹ производится спуск на "дно оврага" и находится критическая точка u3. Далее определяется состояние u₂¹ и т.д. (рис. 3.13).

Процесс поиска продолжается до тех пор, пока значение целевой  функции во вновь найденной критической  точке u_k+1 Q (u_k+1) не окажется больше, чем в предыдущей точке u_k – Q (u_k). Минимум в этом случае находится между точками u_k–1 и u_k+1. Далее процесс поиска можно повторить, но уже с меньшими "шагами по оврагу", пока не будет достигнута требуемая точность.

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

4.ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

 

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

4.1 Краткий исторический очерк

 

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

В 1936 году появилась первая публикация американского экономиста и статистика В.В. Леонтьева о межотраслевой модели производства и распределении продукции США, которая вошла в литературу под названием метода анализа экономики "затраты – выпуск".

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

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

Термин "линейное программирование" появился впервые только в 1951 году в  работах Дж. Б. Данцига и Т. Купманса (США). В эти же годы Дж. Б. Дансингом  разработан эффективный метод решения задач линейного программирования – симплекс метод.

Наиболее эффективно линейное программирование развивалось в  СССР и США в 1955 – 65 годах, именно в этот период оно было одним из наиболее "модных" разделов прикладной математики. В настоящее время линейное программирование стало важным инструментом современной теоретической и прикладной математики.

4.2 Типичные задачи линейного программирования

 

Задача об оптимальном  выпуске продукции

Эта задача возникает при  составлении планов выпуска продукции  предприятием и поэтому имеет важное практическое значение.