Министерство образования  и науки РФ

     Уральский государственный технический университет – УПИ

     ТЕПЛОЭНЕРГЕТИЧЕСКИЙ ФАКУЛЬТЕТ

     КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

     КУРСОВАЯ  РАБОТА

 
 
МЕТОДЫ  ОПТИМИЗАЦИИ

 
 
 
 
 
 
 
 
Оценка  работы:               .

Руководитель: Студент:

зав. каф., проф., докт. физ.-мат. наук,  Самойлов Е.О.

Сесекин Александр  Николаевич Группа: Т-330

__________________________ _____________________________

       (подпись,  дата)  (подпись, дата сдачи)

 
 
 
 
 
     Екатеринбург, 2005

 

     СОДЕРЖАНИЕ

 

1. ФОРМУЛИРОВКА ЗАДАНИЯ

 

     Требуется спроектировать трубопровод, направляющий добываемую в местечке Болотном нефть  на переработку в город Нефтезаводск (Рис. 1).

Рис. 1. Схема проектируемого нефтепровода

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

     Таблица 1. Проектируемые затраты.

 

     Норматив  эффективности капитальных вложений принимается равным 0,15. Приведенные  затраты S, связаны со строительством и эксплуатацией 1 км нефтепровода, рассчитываются по формуле

     S = C + E * K,

     где C – эксплутационные затраты;

          K – капитальные вложения;

E – норматив эффективности капитальных вложений (E = 0,15).

      Требуется:

      1. Построить математическую модель задачи в виде задачи оптимизации с ограничениями.

      2. Построить схему метода штрафных  функций.

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

      4. Провести вычисления на компьютере.

      5. Выполнить анализ результатов  и сделать заключение.

 

2. ВВЕДЕНИЕ

 

     Приведенные затраты S, связаны со строительством и эксплуатацией 1 км нефтепровода, рассчитываются по формуле

     S = C + E * K,

     учитывая  E = 0,15, получим

     S = C + 0,15*K,

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

     

, где

     S₁ = 15+0,15*140 = 36; BD = 200 км;

     S₂ = 10+0,15*90 = 23,5; DE = 100 км;

     S₃ = 5+0,15*40; x₃ = 100 – x₁ – x₂.

     Тогда получим

     

     Цель  курсовой работы: найти два параметра x₁, x₂ , при которых затраты Q, связаны со строительством и эксплуатацией всего нефтепровода будут минимальными, и вычислить значение функции Q(x₁, x₂) в этих точках.

 

3. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

 

     Функция, которую необходимо минимизировать: 

 (1) 

     Необходимо  решить задачу: 

                                 Q(x) à min, x Ω (2) 

     Множество Ω зададим системой неравенств (системой ограничений): 

                      (3) 

     Формально нашу задачу запишем, как задачу безусловной оптимизации функции: 

                            F(x) = Q(x) + δ(x| Ω), (4) 

      где δ(x| Ω) – индикаторная функция (штраф):

      

                                        если x Ω

                      δ(x| Ω) =  (5)

                                        если x Ω 

     Функцию δ(x| Ω) можно рассматривать как бесконечный штраф за нарушение ограничений x Ω. В большинстве случаев совсем нетрудно построить вполне конкретные штрафы δ_k(x| Ω), такие, что при всех x R_n: 

                             δ_k(x| Ω) = δ(x| Ω) (6) 

     Тогда задачу (2) можно свести к последовательности вспомогательных задач безусловной минимизации: 

                         F_k(x) = Q(x) + δ_k(x| Ω) à min, (7) 

     Существует  два подхода к построению штрафов  δ_k(x| Ω) – методы внутренней точки и методы внешней точки.

     Рассмотрим  метод внешних штрафных функций.

3. 2. Метод внешних штрафных функций.

 

     Множество допустимых значений Ω задано системой неравенств (системой ограничений): 
 
 

                              (8) 
 
 

     В качестве штрафов будем использовать функции 
 

                           δ_k(x| Ω)=r_k (9) 
 

     Здесь r_k – положительное число, называемое параметром штрафа. c_i – непрерывные функции из системы неравенств (8). Соотношение (6) выполняется, если r_k à+0 при k à ∞.

     В нашем случае получим следующий  штраф 
 

                     δ_k(x| Ω)=r_k  (10) 
 

     В результате получили следующую задачу безусловной минимизации функции 
 

               F(x₁, x₂) = Q(x₁, x₂) + δ(x| Ω) à min, (11) 
 

     где

       
 

     δ(x| Ω)=r_k . 
 

     Для отыскания безусловного минимума функции  двух переменных F(x₁, x₂) воспользуемся методом наискорейшего спуска.

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

 

     Известно, что градиент F(x) функции в некоторой точке x* направлен в сторону наискорейшего возрастания функции F(x) и ортогонален к поверхности F(x)=const, проходящей через точку x*.

     Представим  себе итерационный процесс следующего вида: 

             x_k+1 = x_k – α_k F(x_k),     α_k > 0, k = 0, 1, … (12) 

     То  есть новая итерация получается из предыдущей движением в направлении  наискорейшего убывания функции  F(x) в точке x_k с шагом α_k. Такие процессы называются градиентными методами и отличаются друг от друга способом выбора шага α_k.

     В методе наискорейшего спуска шаг α_k в формуле (12) выбирается из условия минимума функции F(x) в направлении движения, то есть является решением задачи одномерной минимизации: 

               F(x_k – α_k F(x_k)) = F(x_k – α F(x_k)) (13) 

     Задачу (13) нужно решать на каждом шаге каким-либо из методов одномерной минимизации. Будем использовать метод квадратичной интерполяции.

3. 4. Метод квадратичной интерполяции.

     

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

где А, В и С определяются из уравнений:

После преобразований этих уравнений получаем:

где . Ясно, что       будет иметь минимум в точке, если А > 0. Следовательно, можно аппроксимиро-вать точку минимума функции        значением

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

       Идеи и результаты, изложенные выше, преобразуются в вычислительные процедуры, описанные ниже. Предположим, что заданы унимодальная функция одной переменной       начальная аппроксимация положения минимума x₀ и длина шага h, являющаяся величиной того же порядка, что и расстояние от точки x₀ до точки истинного минимума x^* (условие, которое не всегда просто выполнить). Вычислительная процедура имеет следующие шаги:

1. Вычислить и
2. Если то взять в качестве третьей точки и вычислить . В противном случае в качестве третьей точки взять и найти .

Рис. Выбор  третьей точки при квадратичной интерполяции 

3. Используя эти  три точки, найти    из уравнения (5) и вычислить значение .
4. Если разница между наименьшим значением функции и следующим наименьшим значением функции меньше заданной точности, то процедура заканчивается.
5. Если процедура не завершилась на шаге 4, то точка с наибольшим значением обычно отбрасывается, и мы возвращаемся на шаг 3. Но если, оставив точку с наибольшим значением функции, мы определим конечные границы интервала, в котором лежит минимум, то следует действительно оставить это значение и затем вернуться на шаг 3. Например, на рис., в) оставлены точки                  а не точки