prosdo.ru
добавить свой файл
1
БИЛЕТ 1


1)Определение локальных и глобальных экстремумов

Пусть дана функция f:m \subset \r \to \r,и x_0 \in m^0 — внутренняя точка области определения f. Тогда


  • x0 называется точкой локального максимума функции f, если существует проколотая окрестность \dot{u}(x_0)такая, что

\forall x \in \dot{u}(x_0) \quad f(x) \le f(x_0);

  • x0 называется точкой локального минимума функции f, если существует проколотая окрестность \dot{u}(x_0)такая, что

\forall x \in \dot{u}(x_0) \quad f(x) \ge f(x_0).

Если неравенства выше строгие, то x0 называется точкой строгого локального максимума или минимума соответственно.

  • x0 называется точкой абсолютного (глобального) максимума, если

\forall x\in m\quad f(x) \le f(x_0);

  • x0 называется точкой абсолютного минимума, если

\forall x\in m\quad f(x) \ge f(x_0).

Значение функции f(x0) называют (строгим) (локальным) максимумом или минимумом в зависимости от ситуации. Точки, являющиеся точками (локального) максимума или минимума, называются точками (локального) экстремума.


Замечание

Функция f, определённая на множестве M, может не иметь на нём ни одного локального или абсолютного экстремума. Например, f(x) = x,\; x\in (-1,1).

БИЛЕТ 2

2)Необходимые и достаточные условия экстремума для гладкой функции одной переменной.

Необходимые условия существования локальных экстремумов


  • Лемма Ферма. Пусть функция f\in \mathcal{d}(x_0)дифференцируема в точке локального экстремума x0. Тогда:

~f\'(x_0) = 0.

  • Если в точке экстремума существует первая частная производная (по какому-либо аргументу), то она равна нулю.

Достаточные условия существования локальных экстремумов

  • Пусть функция f\in c(x_0)непрерывна в x_0\in m^0,и существуют конечные или бесконечные односторонние производные ~f\'_+(x_0), f\'_-(x_0). Тогда при условии

f\'_+(x_0) < 0,\; f\'_-(x_0)></a>  0

x0 является точкой строгого локального максимума. А если

f\'_+(x_0)></a> 0,\; f'_-(x_0) < 0,


то x0 является точкой строгого локального минимума.

Заметим, что при этом функция не дифференцируема в точке x0


  • Пусть функция f непрерывна и дважды дифференцируема в точке x0. Тогда при условии

~f\'(x_0)=0и ~f\'\'(x_0) < 0

x0 является точкой локального максимума. А если

~f\'(x_0)=0и ~f\'\'(x_0)></a>  0

то x0 является точкой локального минимума.

БИЛЕТ 3

3)Знакоопределенность матрицы. Критерий Сильвестра.

Критерий Сильвестра определяет, является ли
симметричная квадратная матрица положительно (отрицательно, неотрицательно) определённой.

Если все миноры матрицы Гессе положительны,то она положительноопределена, если чередоваться (первый меньше нуля а далее чередуются), то матрица отрицательноопределенна.

БИЛЕТ 4

4)Необходимые условия экстремума в гладкой задачи без ограничений

Воспользуемся правилом Лагранжа для решения задачи. Для этого:

1)     Составим функцию Лагранжа

http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm8.gif


Числа http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm10.gif - называют множителями Лагранжа. Причем, функция, экстремум которой ищется, также должна быть домножена на неопределенный множитель. Если этого не сделать, то правило Лагранжа может оказаться неверным.

2)     Выпишем необходимые условия экстремума

http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm11.gif

БИЛЕТ 5

5)Достаточное условие экстремума в гладкой задачи без ограничений.

БИЛЕТ 6

6)Правило решения гладкой задачи без ограничения

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

1. Рассмотрим принцип Лагранжа на примере конечномерных задач с ограничениями типа равенств.

Пусть http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm1.gif; http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm2.gif      (3) где http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm3.gif.

Ограничение http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm4.gif задается системой равенств.


Функционал http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm5.gif и функции http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm6.gif, задающие уравнения связи http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm7.gif, предполагаются непрерывно дифференцируемыми (т.е. все их частные производные первого порядка непрерывны).

Воспользуемся правилом Лагранжа для решения задачи (3). Для этого:

1)     Составим функцию Лагранжа

http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm8.gifhttp://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm9.gif

Числа http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm10.gif - называют множителями Лагранжа. Причем, функция, экстремум которой ищется, также должна быть домножена на неопределенный множитель. Если этого не сделать, то правило Лагранжа может оказаться неверным.

2)     Выпишем необходимые условия экстремума

http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm11.gif

3) Найдем стационарные точки из полученных n – уравнений, дополненных m – уравнениями связи.


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

Причем, не все http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm12.gif равны нулю.

В задаче на min можно положить http://www.math.asu.ru/variation/pictures%5cbezusloptim.gladkiezadbezogran%5c22.htm13.gif или другой положительной константе. В задаче на max – равным минус единице или любой другой положительной константе.

Билет 9

Правило решения.

1. Составить функцию Лагранжа

2. Выписать необходимые условия экстремума (2.2), дополненные m уравнениями связи

3. Из полученной системы алгебраических уравнений найти стационарные точки задачи, для которых существует нетривиальный набор множителей Лагранжа, т.е. не все равны нулю, . В задаче на минимум можно положить или другой положительной константе. В задаче на максимум – равным минус единице или любой другой отрицательной константе.

4. Отыскать решение среди стационарных точек или доказать, что решения нет.

Билет 11

Правило решения.

1. Составить функцию Лагранжа

2. Выписать необходимые условия:

а) стационарности

б) дополняющие нежесткости

в) неотрицательности

3. Найти критические точки, т.е. допустимые точки, удовлетворяющие условиям п.2 с множителями Лагранжа и , одновременно не равными нулю.

4. Отыскать решение среди критических точек или доказать, что решения нет.

БИЛЕТ 12

Теорема Веерштрасса

Пусть дана непрерывная числовая функция, определённая на отрезке, то есть f\colon[a,\;b]\to\rи f\in c\bigl([a,\;b]\bigr). Пусть


m=\sup\limits_{x\in[a,\;b]}f(x),\quad m=\inf\limits_{x\in[a,\;b]}f(x)

— точные верхняя и нижняя грани множества значений функции f соответственно. Тогда эти значения конечны (-\infty<m\leqslant m<\infty) и достигаются (существуют x_m,\;x_m\in[a,\;b]такие, что f(x_m)=m,\;f(x_m)=m).

Билет 15

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

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


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

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

Ниже конспективно излагается материал по двойственности для различных классов задач МП (преимущественно линейных), а именно: стандартных задач ЛП, несобственных, лексикографических, паретовских, дизъюнктивных и др.

Билет 19

Задачи одномерной минимизации представляют собой простейшую математическую модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси:

f(x) -> min ,

x принадлежит [a, b].

Максимизация целевой функции эквивалента минимизации ( f(x) -> max ) эквивалентна минимизации противоположной величины ( -f(x) -> min ), поэтому, не умаляя общности можно рассматривать только задачи минимизации.


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

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

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

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f(x), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f(x) унимодальной на отрезке [a, b].

Метод перебора

Метод поразрядного поиска

Метод деления попалам

Метод золотого сечения

Билет 23

Основные теоремы линейного программирования


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

Теорема 1.1. Если целевая функция f принимает максимальное значение в некоторой точке множества допустимых планов D, то она принимает это значение и в некоторой угловой точке данного множества.


Доказательство.

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

Для доказательства воспользуемся следующим известным свойством ограниченных выпуклых множеств:

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

* Строгое доказательство данного утверждения см., например, в [14].

Пусть х1, х2,…,хm — угловые точки множества D, а х* — точка, в которой целевая функция f достигает максимума.

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

http://ecosyn.ru/imag1/image033.gif

Так как х* — точка максимума, то для любого х D сх* ≥ сх. Функция f(x) — линейная, поэтому

http://ecosyn.ru/imag1/image034.gif

cледовательно,

http://ecosyn.ru/imag1/image035.gif

где xr — угловая точка, удовлетворяющая условию

http://ecosyn.ru/imag1/image036.gif

Из (1.10) видно, что сх* ≤ схr. В то же время справедливо обратное неравенство: сх* ≥ схr. Откуда следует, что сх* = схr, т. е. существует по крайней мере одна угловая точка хr, в которой целевая функция принимает максимальное значение. A


Билет 24

Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

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

Билет 25

Метод искусственного базиса.

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

max{F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0}.

В ограничения и в функцию цели вводят так называемые «искусственные переменные» Rj следующим образом:

∑ajix+Rj=bj, j=1,m;F(x)=∑cixi-M∑Rj

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑cixi, , а другая – для составляющей M ∑Rj

Билет 26

Двойственность в линейном программировании

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ [принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу,

Связь между прямой и двойственной задачами устанавливается двумя теоремами.

1. “Теорема двойственности”. Если обе задачи имеют допустимые решения, то они имеют и оптимальные решения, причем значение целевых функций у них будет одинаково:

http://slovari.yandex.ru/illustrations/lopatnikov/pictures/g71_1.gif


(обозначения см. в ст. “Линейное программирование”). Если же хотя бы одна из задач не имеет допустимого решения, то ни одна из них не имеет оптимального решения.

2. “Признак оптимальности”. Чтобы допустимое решение x прямой задачи было оптимальным, необходимо и достаточно, чтобы нашлось такое решение двойственной задачи v, что

http://slovari.yandex.ru/illustrations/lopatnikov/pictures/g71_2.gif

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


Билет 27

Двойственный симплекс-метод.


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

соответсвие прямой и двойственной задачи

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

Билет 28

ТРАНСПОРТНАЯ   ЗАДАЧА

Постановка задачи


        Классическая транспортная задача ЛП формулируется следующим образом.

            Имеется  m  пунктов производства (поставщиков) и n  пунктов

потребления (потребителей) однородного продукта. Заданы величины:

http://www.snipetz.com/math/sysanalysys/line/images/08.htm90.gif - объем производства (запас) i-го поставщика,  i=1, m  ;

http://www.snipetz.com/math/sysanalysys/line/images/08.htm91.gif - объем потребления   (спрос) j-го потребителя, i=1, n ;


http://www.snipetz.com/math/sysanalysys/line/images/08.htm92.gif  - стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к  j-му потребителю.

            Требуется составить такой план перевозок, при котором спрос

всех потребителей был бы выполнен и при этом общая стоимость всех

перевозок была бы минимальна.

            Математическая модель транспортной задачи имеет вид

                        http://www.snipetz.com/math/sysanalysys/line/images/08.htm93.gif

Транспортная задача, в которой суммарные запасы                                                http://www.snipetz.com/math/sysanalysys/line/images/08.htm94.gif

и суммарные потребности                                                http://www.snipetz.com/math/sysanalysys/line/images/08.htm95.gif

совпадают, называется закрытой моделью;  в противном случае - открытой. Открытая модель решается приведением к закрытой.

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

                                               http://www.snipetz.com/math/sysanalysys/line/images/08.htm96.gif

вводится фиктивный n+1 потребитель, потребности которого                                                http://www.snipetz.com/math/sysanalysys/line/images/08.htm97.gif


В случае, когда суммарные потребности превышают суммарные

запасы,  т.е.                                                http://www.snipetz.com/math/sysanalysys/line/images/08.htm98.gif

, вводится фиктивный m+1 поставщик, запасы которого                                               http://www.snipetz.com/math/sysanalysys/line/images/08.htm99.gif

Стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика

полагают равными нулю, так как груз в обоих случаях не перевозится.

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

Билет 29

Метод потенциалов. Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

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


Билет 30

Алгоритм решения задачи о назначениях



















Задача о назначениях - частный случай транспортной задачи, в которой количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства в каждом пункте равен 1.
Данная задача решается с помощью алгоритма, носящего название "Венгерского метода", состоящего из 3 этапов:
1 этап:
1 Формализация проблемы в виде транспортной таблицы
2 В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки
3 Повторить ту же процедуру для столбцов
Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью. Оптимальное значение целевой функции в этом случае равно нулю.
2 этап:
1 Найти строку, содержащую только одно нулевое значение, в его клетку помещается один элемент (0 обводится квадратиком). Если такие строки отсутствуют, допустимо начать с любой строки.
2 Зачеркнуть оставшиеся нулевые значения данного столбца
3 Повторять пп.1-2, пока продолжение указанной процедуры окажется невозможным
Если окажется, что имеется несколько нулей, которым не соответствуют назначения, и которые остались незачеркнутыми, необходимо:
4 Найти столбец, содержащий только одно нулевое значение, в его клетку помещается один элемент.
5 Зачеркнуть оставшиеся нули в данной строке
6 Повторять пп.4-5, пока продолжение указанной процедуры окажется невозможным

Если выяснится, что таблица содержит неучтенные нули - повторить пп. 1-6

Если решение является допустимым, оно оптимально. Если нет - перейти к этапу 3.
3 этап: (Если решение является недопустимым)
1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице
2 Найти наименьший из элементов, через которые не проходит ни одна прямая
3 Вычесть его из всех элементов, через которые не проходят прямые
4 Прибавить его ко всем элементам, лежащим на пересечении прямых
5 Элементы, через которые проходит только одна прямая, оставить неизменными
В результате в таблице появится как минимум одно новое нулевое значение. Вернуться к этапу 2 и повторить решение заново.
Пример решения задачи
Компания имеет 4 сбытовых базы и 4 заказа, которые необходимо доставить потребителям. Складские помещения каждой из баз достаточны для размещения любого из этих заказов.