Государственное образовательное учреждение высшего

профессионального образования

Санкт-Петербургский государственный технологический институт

(Технический университет)

Кафедра Экономики и логистики     Факультет Экономики и менеджмента

                                               Курс          3

                                                                         Группа       6598

Учебная дисциплина                                            Основы Логистики

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

Тема                                           Логистика и внешняя среда бизнеса_

Студент                                          Личная подпись                                          Расшифровка подписи

Гаврилова  К. А.                            ______________                                          ___________________

Руководитель,                            Личная подпись                                          Расшифровка подписи

Должность

Власенко М. Н.                            ______________                                          ___________________

Оценка

За курсовую работу                            _______________                                          Личная подпись

                                                                                                                                            руководителя

Санкт-Петербург

2012

Содержание

Введение              3

Нелинейное программирование              3

Градиентные методы              6

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

Алгоритм наискорейшего спуска              12

Пример: Метод наискорейшего спуска              14

Решение задач              19

Заключение              24

Список используемых источников              25

Введение

Нелинейное программирование

       

        Рис. Нелинейное программирование

НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ [nonlinear programming] — раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями. В экономике это соответствует тому, что результаты (эффективность) возрастают или убывают непропорционально изменению масштабов использования ресурсов (или, что то же самое, масштабов производства): напр., из-за деления издержек производства на предприятиях на переменные и условно-постоянные; из-за насыщения спроса на товары, когда каждую следующую единицу продать труднее, чем предыдущую; из-за влияния экстерналий  и т. д.

В краткой форме задачу нелинейного программирования можно записать так:

F (x) → max при условиях g (x) ≤ b, x ≥ 0,

где x — вектор искомых переменных; F (x) — целевая функция; g (x) — функция ограничений (непрерывно дифференцируемая); b — вектор констант ограничений (выбор знака ≤ в первом условии здесь произволен, его всегда можно изменить на обратный).

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

Иначе говоря, задача состоит в выборе таких неотрицательных значений переменных, подчиненных системе ограничений в форме неравенств, при которых достигается максимум (или минимум) данной функции. При этом не оговариваются формы ни целевой функции, ни неравенств. Могут быть разные случаи: целевая функция нелинейна, а ограничения линейны; целевая функция линейна, а ограничения (хотя бы одно из них) нелинейны; и целевая функция, и ограничения нелинейны.

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

Например, задачу для двух переменных (выпуск продукта x и выпуск продукта y) и вогнутой целевой функции (прибыль Р) можно геометрически представить на чертеже (рис.; заштрихована область допустимых решений).

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

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

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

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

Градиентные методы

В этом разделе излагается стратегия градиентных (наискорейшего спуска) методов оптимизации без ограничений; в вычислительном аспекте эти методы используют только первые производные целевой функции. На k-м этапе переход из точки x(k) в точку x(k+1) описывается следующим соотношением:

(1)

где

∆ x(k) - вектор перехода  из точки x(k) в точку x(k+1) ;

-  единичный вектор в направлении   ∆ x(k) ;          

                              s(k)  -  любой вектор в направлении ∆ x(k) ;

  - скаляры, определяемые соотношениями:

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

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

Градиент целевой функции f(x) в любой точке х есть вектор в направлении наибольшего локального  увеличения f(x) . Следовательно, нужно двигаться в направлении, противоположном градиенту f(x) , т. е. в направлении наискорейшего спуска, поскольку отрицательный градиент f(x) в точке x(k) направлен в сторону наибольшего уменьшения f(x)  по всем компонентам х и ортогонален линии уровня f(x)  в точке x(k) . Введение направления, противоположного нормированному (единичному) градиенту f(x), т. е. направления наискорейшего спуска, определяемого в точке x(k) по формуле

                                                                                                                                        (2)

В  (1) дает следующую формулу перехода из x(k) в x(k+1) ;

                                                                                                              (3)

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

Процедура строго наискорейшего допуска может закончится в стационарной точке (в которой составляющие градиента f(x) равны нулю) различного типа. Обычно бывает необходимо определить, является ли данная точка точкой локального минимума (т. е. решением) или седловой точкой. Если это седловая точка, то следует применить какой-либо неградиентный метод, чтобы выйти из нее, после чего минимизация может продолжаться, как и ранее. Тип стационарной точки может быть проведен путем  исследования матрицы Гессе (если ее возможно получить) целевой  функции, взятой в данной стационарной точке. Если матрица не является положительно определенной, то стационарная точка – седловая. В качестве критерия окончания последовательной процедуры  при движении в направлении наискорейшего спуска применяются различные правила, основанные либо на значение f(x) и величинах х, λ, либо на некоторой их комбинации, а также на соответствующих значениях этих величин на предыдущих шагах. Успех того или иного метода в смысле эффективности сходимости к локальному минимуму зависит от этих правил, а также и от самой задачи.

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

Рассмотрим сначала случая, когда λ выбирается так, чтобы минимизировать f(x) в заданном направлении. При этом на каждом шаге старая информация отбрасывается и заменяется новой информацией, так что никакого ускорения оптимизации осуществить нельзя. Сходимость метода наискорейшего спуска в такой постановке может быть доказана. Можно показать, что для выпуклой целевой функции, имеющие производные до третьего порядка (и для некоторых других функций при еще более слабых ограничениях), этот метод в пределе сходится при k → ∞. Тем не менее упомянутое свойство метода наискорейшего спуска не является большим его достоинством на практике, поскольку скорость сходимости может быть слишком медленной, как это оказывалось в многочисленных экспериментах, а также предсказывается теорией.

При определении точки  x(k+1) на основе формулы (3) f(x) может быть формально минимизирована путем вычисления λ из уравнения

В качестве конкретного примера предложим, что f(x) – квадратичная функция [имея это в виду подставим в уравнение

вместо (х- x(k) )]. Тогда

                         (4)

что дает следующие выражение для λ(k) :

                                                      (5)

Функцию f(x) можно минимизировать также с помощью одного из методов одногомерного численного поиска.

Интересной чертой процедуры минимизации в случае квадратичной целевой функции является то, что              ортогонален               

Фиг. 1.Иллюстрация того, что для квадратичной целевой функции

Если f(x) минимизируется в направлении s(k).

Фиг. 2.Зигзагообразная траектория оптимизации при использовании метода наискорейшего спуска.

Это можно показать следующим образом. Отметим, что если

то градиент f(x) равен

                                                    (6)

так что

Подстановка выражения для в (4) приводит к уравнению

После подстановки x(k+1) - x(k) вместо и преобразования получаем

или

                            (7)

Другими словами, градиент в x(k+1) ортогонален предыдущему  направлению поиска s(k)(фиг.1.). Если  в методе наискорейшего спуска выбирается фиксированное значение скаляра λ или величина λ переменная, то она должна тщательно контролироваться во избежание как неожиданного роста  f(x), так и чрезмерного числа шагов, необходимого для достижения решения. Первое произойдет, если λ слишком велико, а второе, если λ очень мало или если λ настолько велико, что приводит к колебаниям возле точки минимума (фиг.2.).

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

угла θ между последовательными  векторами шагов в процессе минимизации. Например, если этот угол становится меньше, чем некоторая заданная величина, то величина λ должна быть умножена на некоторую заранее определенную константу α; если угол становится больше, то λ нужно разделить на α;

Алгоритм наискорейшего спуска

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

              (1)

Общая формула для нахождения значения аргумента x(k+1) по значению x(k), найденному на k-м шаге работы алгоритма наискорейшего спуска:

                             (2)

где: s(k) - вектор единичной длины в направлении, противоположном направлению градиента , определенном в точке x(k) (далее будет использоваться обозначение );

 - норма (например, длина) вектора градиента :

- шаг градиентной процедуры (определяет число векторов единичной длины (если >0 - целое) или долей длины вектора (если дробное), которое укладывается в направлении, противоположном градиенту при совершении (k+1)-го шага).

Геометрическая интерпретация алгоритма наискорейшего спуска: траектория x(k) ортогональна линиям равного уровня минимизируемой функции. Поскольку шаг движения к экстремуму имеет конечную длину, по мере перемещения к точке x(k+1) ортогональность нарушается. В точке x(k+1) направление корректируется и снова становится ортогональным к линиям равного уровня.

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

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

Рассмотрим задачу;  минимизировать:

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

Начиная с точки х(0) = [2 2]Т , поиск минимума осуществляем следующими этапами:

На фиг. 3, а можно проследить траекторию поиска.

Для того, чтобы метод сходился, λ обычно нужно уменьшать, иначе при переходе к минимуму возникнут колебания («назад – вперед»). Заметим, что в точке минимума х = [0 0]Т 

Ниже приводится результаты трех соответствующих этапов вычисления, в которых вместо использования фиксированного λ ищется минимум f(x) в направлении наискорейшего спуска:

Следует обратить внимание на то, что на фиг. 3, а градиент f(x) в начале поиска не направлен в точку минимума, поскольку коэффициенты при х1 и х2 различны.

Путем замены переменной

y = 5x2

минимизируемая функция принимает вид

И вектор градиента в точке х1 = 2, y = 5х2 = 10 действительно направлен в точку минимума, поскольку коэффициенты при х1 и y теперь одни и те же; фиг. 3,б.

Фиг.3

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

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

на каждый цикл k.

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

Для иллюстрации ниже приводятся компоненты градиента для данного примера, вычисленные по разностным формулам (а) и (б) при

Из таблицы видно, что на некотором расстоянии от минимума разностная аппроксимация  производных вполне приемлема, однако вблизи минимума она недостаточно удовлетворительна. Конечно, можно уменьшать величину δi в процессе поиска или использовать более подходящие аппроксимирующие  формулы для производных.

Основной трудностью при использовании метода наискорейшего спуска, как уже видно из приведенного примера, является его зависимость от выбора масштаба оптимизируемых переменных. Если гиперпространство слишком вытянуто, так что образует «хребет» или «овраг» (отношение максимального значения H (x) к  минимальному в каждой точке велико), процедура наискорейшего спуска сходится слишком медленно, чтобы быть эффективной, или может вообще не сойтись за разумное время.

На фиг. 4 иллюстрируется эта трудность; направление наискорейшего спуска оказывается почти ортогональным наилучшему направлению достижения  минимизации f(x). Одним из выходов в этой ситуации является использование информации второго порядка ( информации, даваемой вторыми частыми производными целевой функции по независимым переменными или их приближениями).

Фиг. 4. Типичная зигзагообразная траектория оптимизации при использовании метода наискорейшего спуска в узкой впадине.

Решение задач

Задача № 1

Определить градиентным методом максимум функции  начав итерационный процесс из точки Х=(4,5).

Решение: В данном случае

.

Итерация 1. Имеем

.

Используя необходимое условие экстремума:

Получим

Откуда λ0=0.5.

Так как ,

то найденное значение λ является точкой максимума ∆z.

С помощью величины λ0 получаем новую точку

Итерация 2. Начальная точка ;

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

(в начальной точке z0 = -10)

Задача № 2

Найти минимум функции . Начальная точка (4; -1; 2) и начальный шаг равен 4.

Решение: Очевидно, что минимум равен нулю при x1 =1; х2 = 3; х3 = -5   Итерационный процесс приведен в таблице 1.

Таблица 1.

Оптимальное значение находится на 11 шаге при f =1,966782E значениях

x1 =1; х2 = 2.9999; х3 = -5.

Задача № 3

Проведите два этапа оптимизации методом наискорейшего спуска, начиная из х = [1 1]Т для целевой функции f(x) = , с фиксированной длиной λ = 1.

Решение:

Задача №4

Найти минимум функции f(x) = , без фиксированного λ. Начальная точка (2; 2) .

Решение:

Так как коэффициенты неодинаковы, то сделаем замену:

y = 5x2 f(x) =

Вектор градиента в точке х1 = 2, y = 10 направлен  в точку минимума, так как теперь коефициенты одинаковы.

Заключение

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

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

Список используемых источников

1. Д. Химмелъблау /Перевод с английского И. М. Быховской и Б. Т. Вавилова. По редакцией М. Л. Быховского Прикладное нелинейное программирование. – Изд. «Мир» Москва 1975.

2. Н.И.Глебов, Ю.А.Кочетов, А.В.Плясунов. Методы оптимизации. 2000.

3. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах; Учеб. Пособие. М.: Высшая школа, 2002. 544 с.

4 Введение в теорию и методы оптимизации для экономистов. 2-изд. – СПб: Питер, 2002. – 320с.

5. Консультационный центр matlab компании Softline/ А.Г.Трифонов. "Постановка задачи оптимизации и численные методы ее решения".

2