Математическое программирование

Математическое программирование

Часть I

Математические основы

Отыскание экстремума функций многих переменных

Численные методы отыскания безусловного экстремума

Линейное программирование

Литература

Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.:Наука, 1978, 351 с.

С. Гасс. Линейное программирование. М. 1961, 300 с.

А. Кофман. Методы и модели исследования операций. М.: Мир, 1966, 523 с.

Д. Химмельблау. Прикладное нелинейное программирование. М: Мир, 1975, 522 с.

С. Гасс. Путешествие в страну линейного программирования. М.: Мир, 1973, 175 с.

Введение

* Математическое программирование ― раздел, математически направленный на решение оптимизационных задач.

(Термин введен в ≈ 1950 г. Робертом Дорфманом)

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

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

Задача, допускающая лишь одно решение, не требует оптимизации!

Математическое программирование имеет дело с задачами о наиболее эффективном использовании или распределении ограниченных ресурсов.

Можно (условно) провести следующую классификацию задач МП (математического программирования).

I

II

III

И т. д.

Классы задач МП определяются видом математических моделей, используемых в этих задачах.

2. Математические модели и методы их построения

* Математическая модель ― некое математическое подобие реального объекта. Модель может представлять собой математическое выражение, содержащее переменные, поведение которых аналогично поведению реальной системы.

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

Математические модели могут быть получены на основе:

- фундаментальных физических законов (закон Ома, всемирного тяготения и т.д.)

- на основе имеющихся данных об объекте (журналы работы участка и т.д.)

- на основе отдельно выполненных экспериментов (задачи обработки результатов измерений и т.д). (Курс "Методы обработки данных")

Предпочтительнее использование моделей 1-ого вида, т.к в них отражен (сконцентрирован) опыт многих поколений человечества.

Пример 1: детерминированная модель ― движение маятника

- гармоническое колебание с периодом

Пример 2:

получены следующие данные о расходах горючего:

y=kX, k=0,1л/км, y=0.1a, y=[л], x=[км]

3. Выбор целевой функции. Характер ограничений

При определении цели всегда встает вопрос: "Какой ценой эта цель будет достигнута?"

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

Подлежащая оптимизации экономическая функция должна быть единственной!

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

Пусть требуется производить два товара P1 и P2. Первый продается с прибылью 100р. за штуку, второй - 50 за штуку.
x1 и x2 - количество производимых товаров.

Общая средняя прибыль равна: B = 100x1 + 50x2

Изделия по мере производства подвергаются обработке, которая длится 5 сек для P1 и 1 сек для P2.

Рассмотрим систему уравнений

(1)

(первое уравнение - характеристика снабжения, связывающая количество поставляемого товара Q с ценой P? второе - характеристика спроса)

Компоненты вектора.

Вектор-столбец х = , вектор строка х' = х = , " ' " или "Т" - операция транспонирования.

Геометрически вектор-столбец и вектор-строка - эквивалентны. Нулевой вектор задает начало координат О' = . Любая точка пространства может быть задана линейной комбинацией двух единичных векторов I'₁ = и I'₂ = (I₁ и I₂ - два возможных базиса в данной системе координат)

Пример: Точка (2, 3) = 2 +3 =2I₁ + 3I₂

2. Операции над векторами

2.1 Умножение вектора на скаляр (действительное число)

A =

При умножении длина вектора увеличивается в k раз (если k отрицательно - меняется направление вектора)

2.2 Сложение векторов - складываются их соответствующие компоненты.

Пусть А = , B = А+В =

Итак, получаем

Y₁ = P'₁Х = =

Y₂ = =

Сложение

Умножение на скаляр

Умножается каждый элемент (умножение на скаляр коммутативно kA = Ak)

4. Транспонирование X→X' (или Х^Т)

Треугольные виды матриц

1.) Квадратная матрица (m = n)

2.) Единичная матрица I - диагональные элементы =1, все остальные =0

Умножение матриц

А = X и Y - матрицы

A X c

Пример: вычислить определитель

|A| =

Возможные произведения	Число инверсий	Знак
		+
		-
		-
		+
		+
		-

|A| = + -( )

Определитель порядка n содержит n! таких произведений.

На основе определения (*) можно установить следующие свойства определителей:

1. Определитель равен 1, если все элементы на главной диагонали ( ) равны 1, а остальные элементы - нули.

2. Определитель равен 0, если равны нулю все элементы какой-либо строки (или столбца) или если равны или пропорциональны элементы произвольных двух строк (или столбцов).

3. Величина определителя остается постоянной по модулю при перестановке его строк (столбцов).

4. Знак определителя меняется при замене местами двух его строк (столбцов).

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

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

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

Минором элемента Aij, обозначаемым Mij (иногда |Mij|), называется определитель, получаемый путем вычеркивания i-ой строки и j-ого столбца А.

Пусть |A| = = =

Алгебраическим дополнением Cij определителя называется минор Mij со знаком + или -

C_ij = (-1)^i+jM_ij

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

|A| = A_i1C_i1+A_i2C_i2+...+A_inC_in

Пример 1.

А = |А|=0 Удалив 2-ую строку и 3-ий столбец, получим: = -6 R = 2 (ранг = 2)

В данном примере столбцы линейно-зависимы

k₁ + k₂ = 0

При k₁=1; k₂=-2; k₃=1

(Действительно, получаем 3 уравнения с 3-мя неизвестными:

разрешив эту систему, получим k₁=k₃= -0,5k₂

Множество решений. Одно из них k₁=1; k₂=-2; k₃=1).

Пример 2.

А = имеет ранг <=3, матрица [3х4].

Таким образом ранг матрицы равен максимальному числу линейно-независимых векторов (строк или столбцов).

Присоединенной матрицей (adj A) называется транспонированная матрица алгебраических дополнений

adj A = (cof A)' =

III.4 Обратная матрица

Систему

Можно записать в виде

AX = b,

где А = (a_ij); X= ; b=

Получим

P₁х₁+ P₂х₂+ P₃х₃= P₀ (2)

Т.к А - неособенная матрица, то система векторов P₁, P₂, P₃ линейно-независимо и, следовательно, образует базис в трехмерном пространстве.

Вектор Y находится как

Y= А^-1Р₄

Таким образом, задавая любой вектор Р₄ в 3-х мерном пространстве, можно найти его разложение по базису.

Шаг 1.

а) Первое уравнение умножаем на 2 и складываем со вторым.

б) Первое уравнение умножаем на -1, складываем с третьим.

Получаем:

Шаг 2. Исключаем х₂ из всех уравнений, кроме второго. Уравнения должны быть расположены таким образом, чтобы коэффициент при х₂ во втором уравнении не был равен нулю. В начале итерации удобно сделать коэффициент при исключаемой переменной равным 1. Для этого делим второе уравнение на 3. Коэффициент 3 - направляющий элемент. (в шаге 1 направляющий элемент а₁₁=1)

Умножая преобразованное второе уравнение:

на -1 и складывая его с первым, получим

Шаг 3. Теперь направляющий элемент 2. Поделив на 2 третье уравнение, полученное после шага 2, и умножив результат на и , сложим полученные уравнения с 1-ым и 2-ым соответственно. Получим:

- это решение системы (1)

Шаг 1

Шаг 2

Шаг 3

Итак

А^-1=

Ответ найден методом перебора.

Примеры: нестрогий минимум и строгий минимум

Если возможно неравенство <=f(x) при х¹ то реализуется нестрогий минимум. В этом случае под решением понимается множество { хÎХ : f(x)= }.

Определение 3. Точка ÎХ доставляет локальный минимум функции f(x) на множестве Х, если при некотором достаточно малом e>0 для всех х¹ хÎХ и удовлетворяющих условию | х |<=e

выполняется неравенство <=f(x)

Пример:

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

Т. 1.1. Задача минимизации непрерывной функции f(x) на замкнутом ограниченном множестве Х разрешима, т.е. непрерывная функция f(x) достигает на замкнутом ограниченном множестве своего минимума (во внутренней или граничной точке).

I.2 Необходимое и достаточное условие экстремума

Будем предполагать, что f(x) имеет в окрестности исследуемой точки непрерывные 1-ую и 2-ую производные.

Т. 1.2. Для того чтобы функция f(x), определенная на вещественной оси, имела безусловный локальный экстремум в точке , необходимо, чтобы выполнялось условие =0.

Доказательство: Пусть точка доставляет локальный безусловный минимум f(x) (для максимума доказательство аналогично). Тогда, по определению минимума, найдется такая окрестность этой точки радиуса e, что для всех x, удовлетворяющих неравенству |x|<=e

f( +x) - f( ) >=0 (1)

По формуле Тейлора имеем:

f( +x)= f( )+ x f '( )+0(x²) (2)

(*) Пусть f ' ( ) ¹0

Выберем x= - f ' ( )r, где r>0 - любое малое число, такое, что | f( )| r<e.

Тогда (3)

[(3) следует из (2): f( +x)- f( )=(- f '( f '( )+ 0(x²)

Т.к. , то найдется такое малое r*,

(([[ ] - член, порядка а]))

что < | |

Из этого следует, что

f( +x) - f( )<0,

т.е. f( )>f( +x), т.е. f( ) - не является локальным минимумом, что противоречит условию (1)

Противоречие возникло из-за предположения (*)

(доказательство от противного)

Итак: f '( )=0

x₂ - точка абсолютного глобального минимума.

Слева от х₂ функция убывает, справа - возрастает.

В точке х₂ убывание функции приостанавливается, т.е. х₂ - стационарная точка.

Все точки х, удовлетворяющие условию =0 - называются стационарными.

(В том числе и точки перегиба - пример: точка х₁)

I.3 Необходимые условия второго порядка

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

>=0 ( <=0)

Доказательство. По теореме 1.2 =0.

Пример: Определить экстремальные значения функции

f(x)= , a¹0, b¹0, xÎE₂

Необходимые условия

=0;

=0; = - стационарная точка

Коэффициенты квадратичной формы ; = 0; .

Имеем следующие случаи:

1) a>0; b>0 матрица вторых производных положительно определена, в точке {0, 0} - минимум.

Условия Сильвестра: а₁₁>0; - положительно определена.

(-1)ⁿа₁₁>0, , (-1)ⁿ - отрицательно определена.

2) a<0; b>0; - экстремума нет

3) a>0; b<0; - экстремума нет

4) a<0; b<0; - функция f(x) имеет в точке {0, 0}^T максимум.

I. Введение

Квадратичная сходимость

||х_k+1- x_*||<=с||x_k - x_*||², с>=0.

Метод с дроблением шага

2. Метод наискорейшего спуска. (минимизируется на каждом функция f(x_k-af '(x_k)) от a).

II.1. Градиентные методы с дроблением шага. Методы с постоянным шагом

В выражении (1) х_k+1= x_k - a_kf '(x_k) выбрав достаточно малый шаг a_k получим

(3) f(x_k-af '(x_k))< f(x_k), т.е. f(х_k+1)< f(x_k).

Проблема: при малом a_k - слишком много шагов

при большом a_k - может нарушиться неравенство (3)

Пример: необходимо минимизировать функцию f(x)=ax²; a>0

Формула (1) принимает вид [ = x_k - a_kf '(x)]

х_k+1=(1 - 2a_ka)x_k

Если a_k=const, то процесс сходится, при 0<a_k< и расходится при a_k> . (В данном случае х_*=0, и процесс будет сходиться, если | х_k+1|<| x_k|, т.е. |1 - 2a_ka |<1

, т.к. а>0, то >0, , )

Если a_k = , то x₁ = - x₀; x₂ = x₀; x₃ = - x₀; и т.д., т.е. происходит зацикливание.

Если a_k> , процесс расходится: пусть a = > . Тогда х_k+1=(1-4)x_k= -3x_k. Пусть x₀=1, тогда x₁=-3; x₂=9; x₃=-27 и т.д.

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

(4) f(x_k-af '(x_k)) - f(x_k)<= -ea_k|| f '(x_k)||,

т.е. f(х_k+1) - f(x_k)<= -ea_k|| f '(x_k)||,

где 0<e<1

Требование (4) на выбор шага более жесткое, чем требование (3). В (3) необходимо только, чтобы f(х_k+1)<f(x_k).

Алгоритм, реализующий метод с дроблением шага:

1. Выбирается a>0.

Математическое программирование

Часть I

Математические основы