Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Блок вопроса 1
1)Постановка задачи линейного программирования. Задача использования сырья. Обобщение задачи использования сырья.
2)Напишите задачу составления рациона. Обобщение задачи составления рациона.
3) Замена неравенств уравнениями. Теорема 1
4)Переход к равенствам в задаче использования сырья и задаче составления рациона.
5) Общая задача линейного программирования. Три формы записи. Определения
6) Выпуклые множества. Определения (выпуклое, замкнутое множества; граничная точка и т.д)
7)Теорема 2( о замкнутом, ограниченном, выпуклом многограннике)
8) Теорема3( о множестве планов задачи использования линейного программирования )
9) Теорема 4(о достижении минимального значения в угловой точке)
10) Симплексный метод. Построение опорных планов.
11) Симплексный метод. Отыскание оптимального плана. Условие оптимальности. Теорема 5
12) Симплексный метод. Отыскание оптимального плана. Условие оптимальности. Теорема 6
13) Симплексный метод. Метод искусственного базиса. Теорема
14) Симплексный метод. Задача со смешанными ограничениями.
15)Замена неравенств уравнениями. Теорема 1
.
Блок 2
1.Вариационное исчисление. Введение. Задача о брахистохроне.
Были изучены основы теории и численных методов определения наименьшего значения функции на заданном множестве U из , где – пространство n векторов . Пусть теперь вместо возьмем пространство непрерывно дифференцируемых функций на отрезке и обозначим , a в качестве – некоторое множество из . Чтобы сопоставить каждому элементу некоторое число из Ε1, необходимо вместо взять определенный интеграл . В результате снова получим оптимизационную задачу . В вариационном исчислении изучается основа теории решения данной оптимизационной задачи.
Задача о брахистохроне. В 1696 г. всем математикам мира И. Бернулли предложил следующую задачу. В вертикальной плоскости даны две точки – А и В, расположенные на разных уровнях. Требуется соединить их такой гладкой линией, двигаясь по которой, тело под действием собственной тяжести пройдет путь от А до В за кратчайшее время.
Говорят, что решение данной задачи было дано самим И. Бернулли, Г.В. Лейбницем, Я. Бернулли и еще одним автором без подписи. Позже выяснилось, что решение без подписи дал И. Ньютон.
Пусть выбранная система координат имеет начало в точке А(0, 0), ось x направлена горизонтально, ось у – вертикально вниз и точка А находится выше точки . Пусть – некоторая точка на искомой кривой y=y(x), проходящая через точки А и В. Поскольку трение отсутствует, то сумма кинетической Т и потенциальной П энергии постоянна в любой точке кривой . Так как в точке А тело находится в покое, то , а в точке Μ сумма . Отсюда определим скорость в точке М, равную . Поскольку мгновенная скорость , то . Следовательно, .
Отсюда имеем
(1)
Формула (1) определяет время движения тела по любой кривой , проходящей через точки А и В.
Заметим, что функция , множество , а сама задача запишется так:
(2)
2.Простейшая задача вариационного исчисления. Определение.
Простейшая задача. Обобщением задачи (2) является следующая простейшая задача. Минимизировать функционал
(3)
на множестве
. (4)
Заметим, что если х, t заменить на у, x соответственно и то из (3), (4) следует задача (2). Вводя обозначения где – непрерывная функция, задачу (3), (4) можно записать в виде
. (5)
Определение 1. Говорят, что функция доставляет сильный локальный минимум функционалу в задаче (5) (или (3), (4)), если найдется число , такое, что для любой допустимой функции , для которой выполняется неравенство , где
Определение 2. Говорят, что функция доставляет слабый локальный минимум функционалу в задаче (5) (или (3), (4)), если найдется число ε > 0, такое, что для любой допустимой функции , для которой
(6)
выполняется неравенство .
Заметим, что в определении 1 сравнивается значение функционала со значением на множестве допустимых функций, расположенных в ε-окрестности для каждого , а в определении 2 такое сравнение осуществляется на множестве допустимых функций, у которых x(t) и находятся в ε-окрестности для каждого t, соответственно и . Поэтому необходимые условия слабого локального минимума в точке будут необходимыми условиями сильного локального минимума. С другой стороны, если в точке достигается сильный локальный минимум, то на ней будет достигаться и слабый локальный минимум, так как условие , в частности, выполняется и для тех , для которых Обратное утверждение неверно.
3. Необходимые условия слабого локального минимума. Теорема.
Как следует из включения , . Следовательно, допустимую функцию целесообразно выбрать в виде , где – некоторое число. Таким образом, функция . Поскольку разность , , то путем выбора числа γ можно обеспечить выполнение неравенств, приведенных в определениях 1, 2.
Пусть функция F(x,и,t) дважды непрерывно дифференцируема по совокупности аргументов . Тогда разность
(7)
где x0 =x0(t)U. Вводя обозначения
, (8)
, (9)
соотношение (7) запишем в виде
. (10)
Величина , определяемая по формуле (8), называется первой вариацией функционала в точке , а величина из (9) – второй вариацией функционала в точке .
Теорема 1. Пуcть функция доставляет слабый локальный минимум функционалу на множестве U. Тогда необходимо выполняются следующие условия:
=0, 0. (11)
Доказательство. Пусть для некоторого числа γ и функций выполнены неравенства (6) где и . Покажем, что верны соотношения из (11). Согласно выражению (10) разность
где – достаточно малое число; при . Отсюда следует, что если 0, то всегда можно выбрать число γ знака, противоположного ; при этом . Это противоречит условию . Следовательно, =0. Далее, поскольку =0, то Отсюда следует, что если <0, то при достаточно малом , что противоречит условию . Теорема доказана.
4.Основная лемма вариационного исчисления. Лемма Лагранжа. Уравнение Эйлера.Теорема.
Лемма Лагранжа. Если – непрерывная функция и определенный интеграл
(12)
то .
Доказательство. Предположим противное, т. е. в некоторой точке . Пусть для определенности число . Тогда в силу непрерывности функции , найдется число ε0>0, такое, что при . Выберем функцию в следующем виде:
Тогда интеграл
Это противоречит равенству (12). Лемма доказана.
Уравнение Эйлера. Покажем, что искомая функция является решением некоторого дифференциального уравнения, называемого уравнением Эйлера. Первый вывод уравнения Эйлера можно получить на основе леммы Лагранжа.
Теорема 2. Для того чтобы функция доставляла слабый локальный минимум функционалу в задаче (5) необходимо, чтобы она удовлетворяла уравнению Эйлера:
(13)
Доказательство. Пусть для всех , удовлетворяющих неравенству (б), выполнено . Покажем, что функция является решением уравнения (13). Согласно необходимому условию первого порядка в точке первая вариация
(14)
После интегрирования по частям второе слагаемое запишется в виде
Теперь соотношение (14) можно представить в виде
Отсюда согласно лемме Лагранжа, где функция
получим уравнение (13). Теорема доказана.
5. ЛЕММА ДЮБУА – РЕЙМОНДА. Примеры Гильберта и Вейерштрасса.
Лемма Дюбуа – Реймонда. Если функция , непрерывна и для любой непрерывной функции , равной нулю в среднем, т. е., (1)
определенный интеграл (2)
то
Доказательство. Предположим противное, т. е. что существуют точки и из , такие, что . Для определенности считаем, что . Выберем достаточно малое число ε0 так, чтобы отрезки не пересекались друг с другом, причем и . Поскольку функция , непрерывна, то последнее неравенство имеет место. Построим функцию равную нулю в среднем [см. формулу (1)] следующим образом:
Тогда интеграл
.
Это противоречит равенству (2). Лемма доказана.
П р и м е р 2 (пример Гильберта). Минимизировать функционал при условиях . В данном случае . Уравнение Эйлера имеет вид , . Решение дифференциального уравнения запишется так: . Из условия следует, что . Тогда . Однако функция не является непрерывно дифференцируемой на отрезке [0, 1].
Пример 3 (пример Вейерштрасса). Пусть . Уравнение Эйлера имеет вид . Решение данного уравнения . Однако через точки не проходит ни одна кривая этого семейства.
6. Задача Больца. Теорема 1 (о слабом локальном минимуме)
Задача Больца. Минимизировать функционал, (6)
где – фиксированные числа, а в отличие от простейшей задачи величины не фиксированы.
Теорема 1. Пусть функции и дважды непрерывно дифференцируемы по совокупности переменных. Для того чтобы функция доставляла слабый локальный минимум функционалу (6) необходимо, чтобы она была решением уравнения Эйлера
(7) и удовлетворяла условиям
(8)
Доказательство. Пусть для некоторого числа функции удовлетворяют условиям , . Тогда приращение функционала (6) запишется в виде
,
где при , а величина
.
Интегрируя по частям, получаем
Теперь первая вариация имеет ви
Если – искомое решение задачи (6), то необходимо, чтобы . Из независимости частичных приращений и из следует, что . Отсюда следуют формулы (7), (8). Теорема доказана.
Заметим; что решение уравнения (7), функция , постоянные определяются из условия (8).
7. Необходимое условие Вейерштрасса. Теорема 2 (о сильном локальном минимуме).
Необходимое условие Вейерштрасса. Снова рассмотрим простейшую задачу. Поскольку необходимое условие слабого локального минимума будет необходимым условием сильного локального минимума, то функция , доставляющая сильный локальный минимум функционалу, является решением уравнения Эйлера. Однако, кроме этого, должно быть дополнительное необходимое условие сильного локального минимума, непосредственно связанное с его определением. Таким условием является необходимое условие Вейерштрасса.
Определение 1. Функцией Вейерштрасса для простей-шей задачи называют функцию от четырех переменных , определяемую по формуле
.
Заметим, что если функция выпукла, по переменной и при фиксированных , то функция при всех в силу теоремы 1 (лекция 4), где .
Теорема 2. Для того чтобы функция доставляла сильный локальный минимум функционалу в простейшей задаче, необходимо, чтобы для любой точки вдоль решения уравнения Эйлера выполнялось неравенство
. (9)
Доказательство. Пусть функции , такие, что и . Покажем, что выполнено неравенство (9). Заметим, что при выводе уравнения Эйлера была взята функция , которая является частным случаем функции .
В общем случае приращение функционала
Отсюда следует, что величина. (10)
Следует отметить, что если , то для того, чтобы , необходимо, чтобы величина , так как в этом случае знак совпадает со знаком при достаточно малом γ > 0. Функцию выберем следующим образом:
(11)
Таким образом, функция линейна на отрезках и следовательно, ее производная (12)
напоминает иголку, поэтому часто называют „игольчатыми" вариациями. Поскольку функции определяются формулами (11), (12),
Вычислим первую вариацию согласно формуле (10):
,
где. (13)
Поскольку функция – решение уравнения Эйлера, то верна формула (3). Из тождества (3) имеем
, (14)
. (15)
Вычитая из (15) выражение (14), получаем
Теперь выражение (13) запишется в виде
Отсюда с учетом того, что
при , получим
. (16) Обозначая , для фиксированного неравенства (16) записываем в виде
для любого Теорема доказана.
8. Условие Лежандра. Теорема.
Условие Лежандра. Рассмотрим простейшую задачу. Выше было доказано, что необходимые условия слабого локального минимума на U имеют вид: 1) ; 2) . До сих пор рассматривался случай, когда . Теперь рассмотрим, кроме , неотрицательность второй вариации функционала, чтобы получить усиленные необходимые условия слабого локального минимума.
Пусть функция – решение уравнения Эйлера, удовлетворяющее граничным условиям . Вводя обозначени
вторую вариацию [см. формулу (9) из лекции 23] запишем в виде. (1)
Теорема 1. Для того чтобы функция доставляла слабый локальный минимум в простейшей задаче, необходимо, чтобы вдоль решения уравнения Эйлера выполнялось неравенство (2)(условие Лежандра).
Доказательство. Пусть вдоль решения уравнения Эйлера выполнено неравенство . Покажем, что верно неравенство (2). Предположим противное, т. е. в точке величина .
Пусть функция . Представим функцию , где и
а функция сглаживает три угла функции с тем, чтобы . Производная
Поскольку значения функции достаточно малы по сравнению со значениями , a также достаточно мала производная по сравнению с , то знак выражения (1) определяется знаком величины
Итак, . Это противоречит тому, что . Теорема доказана.
9. Условие Якоби. Теорема 2.
Условие Якоби. Вдоль решения уравнения Эйлера вторая вариация является функционалом от функции , т. е. (3)
где .
Для простейшей задачи (3) уравнение Эйлера имеет вид.
Отсюда с учетом того, что получим
(4)
Предположим, что выполнено усиленное условие Лежандра . Тогда уравнение (4) запишется в виде (5)
где .
Пусть функция – решение дифференциального уравнения (5).
Определение. Нули функции , отличные от , называются точками, сопряженными с точкой .
Теорема 2. Для того, чтобы функция доставляла слабый локальный минимум в простейшей задаче, необходимо, чтобы на интервале не было точек, сопряженных с точкой (условие Якоби).
Доказательство. Пусть при всех , для которых . Покажем, что функция . Предположим противное, т. е. что существует точка , такая, что . Заметим, что , в противном случае уравнение (5) имеет решение . Пусть функция
Поскольку и , в силу того, что , то .
Тогда функционал можно записать в виде.(6)
Значение.
В самом деле, производная
Интегрируя данное выражение по в пределах от до , с учетом , получаем (6). Теперь рассмотрим простейшую задачу с вариацией функции
где – достаточно малое число. Производная
Вычислим значение функционала
(7)
где согласно формуле (6) и .
Заметим, что по теореме о среднем
.
Тогда из формулы (7) по теореме о среднем интеграла имеем
где .
Заметим, что , причем , а производная . Следовательно, существуют числа , такие, что при , величина . Это противоречит условию . Для корректности выкладки остается сгладить функцию в точках и , как в случае доказательства теоремы Лежандра. Теорема доказана.
10. Функционалы, зависящие от n неизвестных функций. Теорема 3.
Функционалы, зависящие от n неизвестных функций. Рассмотрим простейшую задачу, когда – –вектор-функция. Итак, минимизировать функционал
(8)
при условиях
(9)
Введя обозначение
задачу (8), (9) можно записать в виде
Теорема 3. Для того чтобы вектор-функция доставляла слабый локальный минимум функционалу на U, необходимо, чтобы она была решением уравнения Эйлера
. (10)
Доказательство. Выберем допустимую вектор-функцию , где , причем . Тогда первая вариация функционала равна
где
. (11)
Так как приращения независимы, то из следует, что . Тогда из (11) в силу леммы Лагранжа получим уравнения Эйлера (10). Теорема доказана.
Заметим, что уравнение (11) является дифференциальным уравнением порядка и его решение ; постоянные определяются из условия .
11. Функционалы, зависящие от производных высших порядков. Теорема 4 (Уравнение Эйлера-Пуассона).
Функционалы, зависящие от производных высших порядков.
Рассмотрим следующую задачу. Минимизировать функционал
(12)
при условиях
, (13)
Теорема 4. Для того чтобы функция доставляла слабый локальный минимум функционалу (12) при условиях (13), необходимо, чтобы она была решением следующего уравнения Эйлера – Пуассона:
. (14)
Доказательство. Для функции
, т.е. первая вариация функционала после интегрирования по частям имеет вид
.
Тогда из условия в силу леммы Лагранжа получим уравнение (14). Теорема доказана.
Заметим, что (14) является дифференциальным уравнением порядка , а его решение ; постоянные определяются из условий .
12. ИЗОПЕРИМЕТРИЧЕСКАЯ ЗАДАЧА. Теорема 1.
Изопериметрическая задача. Изопериметрической называется следующая задача: минимизировать функционал (1)
при условиях (2)
где – дважды непрерывно дифференцируемые функции в области – заданное число.
Теорема 1. Если функция доставляет слабый локальный минимум функционалу (1) при условиях (2) и не является экстремалью функционала (3)
то существует постоянная , такая, что функция является решением дифференциального уравнения
(4)
Доказательство. Выберем точки . Пусть , где – точка слабого локального минимума функционала (1) на U, а функция . Тогда приращение функционала (1) равно
(5)
где . Заметим, что имеет порядок , т.е. . Поскольку , то , следовательно,
(6)
из (6) следует, что. (7)
Подставляя значение из (7) в правую часть выражения (5), получаем
(8)
где число . Таким образом,
.
Отсюда следует утверждение (4). Теорема доказана.
13. Изопериметрическая задача в общем случае(от n переменных). Теорема 2.
В общем случае изопериметрическая задача сформулируется так: минимизировать функционал
(9)
при условиях
. (10)
Теорема 2. Если вектор-функция доставляет слабый локальный минимум функционалу (9) при условиях (10), то существуют числа , не все равные нулю, такие, что вектор-функция является решением следующих уравнений:
, (11)
где функция , называемая лагранжианом, определяется по формуле
.
Для случая доказательство теоремы приведено выше. В общем случае теорема доказывается, аналогичными приемами. Заметим, что решение уравнения (11), вектор-функция , постоянные определяются из условий .
14. Условный экстремум. Задача Лагранжа. Теорема 3.
Условный экстремум. Рассмотрим следующую задачу Лагранжа: минимизировать функционал (12)
при условиях
. (13)
Иными словами, минимизировать функционал на множестве непрерывно дифференцируемых функций , принадлежащих заданной поверхности .
Теорема 3. Если функция доставляет слабый локальный минимум функционалу (12) при условиях (13) и производные и , не обращаются в нуль одновременно, то существует функция , такая, что функция является решением дифференциальных уравнений
(14)
(15)
Доказательство. Пусть функции , где если . Тогда приращение функционала (12) равно
,(16)
. Поскольку , то
. Подставляя значение в правую часть выражения (16), получаем приращение функционала (12) с учетом ограничения, как в случае простейшей задачи, в виде
Отсюда и из необходимого условия слабого локального минимума , следует, что
(17)
из (17), получаем дифференциальные уравнения (14), (15), Теорема доказана.
Задача Лагранжа. Обобщением задачи на условный экстремум является следующая задача Лагранжа: минимизировать функционал (18) при условиях , (19) (20) при .
15. Обобщение задачи на условный экстремум. Функционал Лагранжа. Теорема 4.
Все рассмотренные задачи являются частными случаями задачи (18) – (20). В самом деле, простейшую задачу можно записать в виде
Изопериметрическая задача может быть записана в виде
Для задачи (18) – (20) функция
называется лагранжианом, а функционал
называется функционалом Лагранжа.
Теорема 4. Для того чтобы пара доставляла слабый локальный минимум в задаче (18) – (20), необходимо, чтобы существовали множители Лагранжа , не все равные нулю, такие, что:
Общие замечания к простейшей задаче.
1. Как было показано выше, для простейшей задачи уравнение Эйлера имеет вид . Данное уравнение можно записать в виде
(21)
Отсюда видно, что, несмотря на то, что функция ищется в классе , уравнение Эйлера сводится к определению функций . Тогда возникает вопрос: когда искомая функция ? Поскольку первые три слагаемые вдоль – непрерывные функции по , то для существования необходимо, чтобы . Данное условие называется условием Гильберта.
2. Может оказаться так, что производная функции имеет разрывы первого рода в изолированных точках отрезка . В таких случаях в интервалах между точками функция удовлетворяет уравнению Эйлера, и в угловых точках выполняются условия .