Решение принимает вид




НазваниеРешение принимает вид
страница1/3
Дата30.08.2012
Размер0.52 Mb.
ТипРешение
  1   2   3




Тогда критерий оптимальности запишется: z = –550 + 5x3.

В этой форме базисное допустимое решение принимает вид:

x1 = 0, x2 = 150, x3 = 0, x4 = 1500,

в котором нулевые значения принимают свободные неизвестные. Это базисное допустимое решение оптимально, так как коэффициенты при всех (единственном x3) свободных неизвестных в критерии неотрицательны. Таким образом оптимальное решение имеет вид: затраты на один километр пути принимают наименьшее значение при следующих исходных переменных задачи x1 = 0, x2 = 150. Трактовку этого решения оставим до конца следующего пункта Б данного параграфа, здесь лишь отметим, что в качестве математической модели для оптимизации авиаперевозок задача линейного программирования неприемлема.

Б) f, g, H – алгебраические нелинейные функции, не зависящие от времени. Это – задача нелинейного программирования. Методы решения ее существенно зависят от формы записи (и вычисления) H. Рассмотрим эти формы.

1) Случай, когда H имеет достаточно простой вид и позволяет определить не только значения всех частных производных в каждой точке пространства аргументов, но и решить систему уравнений вида:



Решение этой системы уравнений дает множество точек, среди которых могут находиться точки оптимального решения, т.е. minH. Но такого может и не быть, если среди этого множества нет точек минимума внутри области допустимых управлений и фазовых координат. Поэтому следует дополнительно вычислить значения критерия оптимальности H и на границе допустимой области (или найти хотя бы точки, имеющие наименьшее значение H на каждой границе). Только после сравнения всех найденных значений H можно найти решение оптимизационной задачи. Этот метод не имеет специального наименования, но его можно было бы назвать классическим методом отыскания наименьшего значения функции в заданной области аргументов. Простейшая иллюстрация этого метода с акцентом на необходимость проверки границ приведена на рис. 36 для одномерного случая.

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

Р
ис. 36.

ПРИМЕР. Рассмотрим дальнейшее развитие примера предыдущего пункта А – построения математической модели для оптимизации авиаперевозок.

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

Р
ис. 37.

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



Решение выглядит следующим образом: x1 = 0, x2 = 40, т.е. подозрительной на экстремум является лишь одна точка (кстати, лежащая на границе допустимой области), в которой критерий оптимальности принимает значение: zо(0; 40) = 0. Классифицировать эту точку нет необходимости, как это будет очевидно из последующих исследований. Проверим теперь все границы допустимой области.

Для верхней границы x2 = 150, и z = –550x1. Так как x1 изменяется в пределах от 0 до 1500, то наименьшее значение критерий оптимальности принимает в правой крайней точке этой границы: zв(1500; 150) = –5501500 = –825000.

Для нижней границы x2 = 0, и z = 200x1. Так как x1 изменяется в пределах от 0 до 3000, то наименьшее значение критерий оптимальности принимает в левой крайней точке этой границы: zн(0; 0) = 0.

Для левой границы x1 = 0, и zл = 0 при любом x2.

Для правой, наклонной границы x1 = 3000 – 10x2, поэтому

.

Это выражение принимает наименьшее значение, и притом единственное, в точке, где . Эта точка лежит на прямой, являющейся продолжением наклонной границы, при x2 = 170, т.е. вне области допустимых значений переменных. Однако заметим, что z на этой прямой ведет себя монотонно по обе стороны от точки минимума x2 = 170, т.е. и на рассматриваемом отрезке границы. Поэтому наименьшее значение z на интервале изменения x от 0 до 150 будет в точке на этой наклонной прямой, ближайшей к x2 = 170: zп(1500; 150) = –5501500 = –825000.

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

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

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

Если аналитическая запись производной H возможна, то это – частный случай рассмотренного выше п. 1. В противном случае можно воспользоваться одним из методов последовательных приближений, описанных ниже.

Метод деления отрезка пополам (название, но не сам метод, совпадает с названием одного из методов решения алгебраических уравнений) реализуется по следующему алгоритму.

1► Выделяется отрезок [a,b] области изменения аргумента x, в котором гарантированно находится решение (эту гарантию можно получить из дополнительных исследований функции H или, что тоже допустимо, из практических соображений о физической сути задачи).

2► В средней точке этого отрезка вычисляется значение H [½(a+b)].

3► Вычисляется значение H [½(a+b)+] в точке, расположенной рядом со средней точкой отрезка на расстоянии, равном требуемой точности решения задачи по величине аргумента (или гарантирующем "чувствительность" алгоритма расчетов величины H к изменению x).

4► Выбирается та из половин отрезка, в сторону которой H внутри отрезка уменьшается, что можно определить по внутренним точкам, найденным в п.п. 2 и 3 (см. рис. 38, на котором условно показана зависимость H (x), на самом деле априори неизвестная в данной задаче).

Р
ис. 38.

5► Для выбранной половины отрезка повторяются процедуры пунктов 2 – 4 алгоритма, т.е. отыскивается уже четверть исходного отрезка, на которой находится минимум. Такая процедура уменьшения области поиска (вдвое на каждой итерации) продолжается до тех пор, пока длина рассматриваемого отрезка не станет удовлетворять требованиям заданной точности (допустимой погрешности).

Метод золотого сечения (название, но не сам метод, совпадает с названием одного из методов решения алгебраических уравнений) реализуется по следующему алгоритму:

1► Выделяется отрезок [a,b] области изменения аргумента x, в котором гарантированно находится решение (эту гарантию можно получить из дополнительных исследований функции H или, что тоже допустимо, из практических соображений о физической сути задачи).

2► Производится золотое сечение отрезка [a,b] точками: u1, u2 (см. одноименный метод в § 4.1).

3► Вычисляются значения H (u1) и H (u2). Для продолжения алгоритма выбирается одна из бóльших частей отрезка: если H (u1)  H (u2), то – левая: [a,u2], если H (u1) > H (u2), то – правая: [u1,b] (см. рис. 39).

4► Производится золотое сечение вновь полученного отрезка, как это делалось в п. 2 алгоритма, при этом одна из точек уже известна из предыдущего шага, так как по свойству золотого сечения одна его точка для всего отрезка является точкой золотого сечения той его части, на которой она расположена. Это позволяет экономить количество расчетов функции H.

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


Р
ис. 39.

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

(по i-ой координате: ),

где x[j] – точка в допустимой области, а [j] каждого j-ого шага подбирается из соображений, свойственных конкретному методу, но так, чтобы x[j+1] тоже была бы допустимой точкой.

Градиентные методы имеют простой геометрический смысл. Рассмотрим пример функции H (x1,x2) двух аргументов x1, x2 (см. рис. 40) и построим на плоскости их изменения линии уровней функции H. (Линией уровня функции называется геометрическое место точек, в которых функция принимает одинаковые значения.) Градиент в любой точке, так же как и антиградиент всегда направлен по нормали к линии уровня, проходящей через эту точку. Поэтому реализация градиентных методов означает спуск по поверхности H в наиболее крутом направлении (антиградиента ) на некоторый шаг. Последовательное повторение таких шагов при некоторых условиях обеспечивает спуск к минимуму H.

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


Рис. 40.

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

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

В) fне зависит явно от управлений и содержит производные от фазовых координат: ; ограничения области допустимых управлений отсутствуют, но зато есть граничные условия вида:

,

где G и F – векторные функции; критерий оптимальности имеет вид H – функционала, независящего явно от управлений:

.

В этой задаче могут вообще отсутствовать управления u(t).

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

Вариационное исчисление рассматривает вариации функций в некоторой области значений аргумента, аналогично тому, как в математическом анализе рассматриваются приращения значений функций. Однако, если приращение значения функции x(t) имеет вид: x = x(t + t) – x(t), то вариация функции x(t) в вариационном исчислении имеет смысл функции-разности между исходной x(t) и новой функцией X(t), получаемой изменением x(t): x(t) = X(t) – x(t) (см. рис. 41).

Р
ис. 41.

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

Упомянутые непрямые методы основаны на решении дифференциальных уравнений необходимых условий экстремальности Эйлера–Лагранжа:

,

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

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

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

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

Г) f, g – функции, зависящие явно от управлений, причем f такова, что уравнения связей f = 0 могут быть приведены к виду: – т.е. разрешены относительно производной; критерий оптимальности H – функционал вида:

,

тоже в общем случае явно зависящий от управлений.

Это – задача оптимального управления: нахождение (синтез) оптимального управления , которое переводит систему из одного состояния в другое таким образом, что реализуется минимум H. Задачи оптимального управления решаются с помощью принципа максимума или методом динамического программирования.

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

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

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

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

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

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

ПРИМЕР 1. Прокладка наивыгоднейшего (по минимуму суммарных затрат W) пути из пункта A в пункт B.

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



Рис. 42.

Следуя принципу динамического программирования, решение нужно начать с последнего шага, т.е. от пункта B. В эту точку за один последний шаг можно попасть только из точек C или D. Из C в B можно построить дорогу единственным способом: на восток. Т.е. оптимальные (единственно возможные) затраты на этот путь составляют 10 единиц, что и записано в кружке этой точки, а оптимальное управление на восток показано стрелкой. Аналогично, в кружке точки D записано число 14 и стрелка указывает на север. Последний шаг рассмотрен и все его оптимальные варианты просчитаны.

Перед предпоследним шагом мы могли оказаться в одной из точек E, F, G. Для каждой из них необходимо просчитать оптимальный путь предпоследнего шага. Из E путь единственно возможный (по условиям задачи): на восток с затратами в 11 единиц. В этом случае оставшийся (вынужденный) путь из E в B обойдется минимум в 21 единицу, это число и запишем в кружок точки E, стрелка оптимального управления которого показывает на восток. Аналогичная ситуация, только с движением на север, складывается при нахождении в начале предпоследнего шага в точке G. Путь из этой точки до конечной точки B обойдется минимум в 22 единицы. В точке F есть две возможности выбрать предпоследний шаг: на север и на восток. Путь из F на север, через точку C, требует затрат в 13 единиц плюс минимум 10 (помеченных в кружке) на последнем шаге, т. е. 23 единицы. Вторая возможность (через точку D) потребует минимум 14 + 14 = 28 единиц. Таким образом, оптимальный путь из точки F на север с учетом всех последующих шагов требует минимум 23 единицы затрат. Это число со стрелкой на север и стоит в точке F. Рассмотрен предпоследний шаг.

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

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

Рассмотренный пример является классической задачей о кратчайшем пути из теории графов. Следующий пример относится к задаче теории графов типа оптимального назначения или распределения ресурсов.


Таблица 3.



1(x)

2(x)

3(x)

4(x)

5(x)

1

0,5

0,1

0,6

0,3

1,0

2

1,0

0,5

1,1

0,6

1,2

3

1,4

1,2

1,2

1,3

1,3

4

2,0

1,8

1,4

1,4

1,3

5

2,5

2,5

1,6

1,5

1,3

6

2,8

2,9

1,7

1,5

1,3

7

3,0

3,5

1,8

1,5

1,3

8

3,0

3,5

1,8

1,5

1,3
  1   2   3

Похожие:

Решение принимает вид iconПравила для
Решение о публикации принимает редакционная коллегия журнала после рецензирования, учитывая научную значимость и актуальность представленных...
Решение принимает вид iconОбучения
Предварительная. Самостоятельная работа участников (Участник связывает специальность мр и обучение в такой мере, что принимает решение...
Решение принимает вид iconРешение о допуске к егэ принимает педагогический совет школы, оформляя его приказом до 25 мая
С 2009 года егэ – это основная форма государственной итоговой аттестации для выпускников школ Российской Федерации
Решение принимает вид iconОбъединенных наций
Конвенции для подписания и датой ее вступления в силу Межправительственный комитет для ведения переговоров принимает решение относительно...
Решение принимает вид iconРешение комиссии от 14. 09. 11г
Вид и оборудование классной доски – доска открывается, магнитная (3), переносная
Решение принимает вид iconФинансовый навигатор: классический полис каско
Человек, который находится за рулем, по статистике принимает решение каждые 4 секунды, а в большом и плотном транспортном потоке...
Решение принимает вид iconА. Клещинский применение методов бизнес-прогнозирования в системах бюджетирования
Бюджетирование – это процесс составления, исполнения и последующего анализа бюджетов. Процесс бюджетирования, внедренный в какой-либо...
Решение принимает вид iconП. А. Флоренский и гете: мифосимвол или протофеномен?
Неведомость мира захватывает сознание П. А. Флоренского, и он принимает твёрдое решение «…познать мир именно как неведомый, не нарушая...
Решение принимает вид iconМетодические указания по подготовке, выполнению и защите дипломных работ для студентов специальностей 0604, 0605
Охватывают работу в целом. Однако консультант может лишь корректировать отдельные элементы организационно-методической работы руководителя...
Решение принимает вид iconРеферат Тема «Объекты Всемирного наследия юнеско в Карелии»
Юнеско. Эта организация при помощи приглашённых экспертов принимает решение о включении объектов в список Всемирного наследия и далее...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница