Курс лекци Русакова по методам оптимизации (1083216), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

+ a1n x n ≤ b1...........................................a x + a x + ... + a x ≤ b ,m2 2mn nm m1 1гдеc j , aij , bK{{j = 1, n;(1.2)}i = 1, m; k = 1, m –известныеконстантыи}x j ≥ 0 j = 1, n .ОпределениеnФункция z = F ( x1 , x2 ,..., xn ) = ∑ c j x j , экстремум которой ищется,j =1называется целевой функцией.Словесно задачу линейного программирования можно сформулироватьтак: требуется найти такие значения n переменных x j ,{j = 1, n}, которыедоставляют экстремум (максимум или минимум) линейной формы отnпеременных при m ограничениях в виде неравенств или равенств.

Нетрудноубедиться, что всегда можно говорить только о равенствах, так каквведением дополнительных или слабых переменных x n + v (v = 1, p; p ≤ m)неравенства всегда можно свести к строгим равенствам.Так, например, ограничениеai1 x1 + ai 2 x 2 + ... + ain x n ≤ bi(1.3)можно свести к равенству, добавив переменную xn+1:ai1 x1 + ai 2 x2 + ... + ain xn + xn+1 = bi .6(1.4)В этом случае условие (1.3) сводится к условию (1.4) и условиюнеотрицательности xn+1.Таким образом, задача линейного программирования, путём введения вслучае необходимости вспомогательных переменных, сведена к стандартнойформе, к так называемой основной задаче линейного программирования(ОЗЛП).1.02 Выпуклые множества и выпуклые функцииОпределение.Множество S в Rn называется выпуклым множеством, если длялюбых точек x 1 ∈ S , x 2 ∈ S точки x = µx 1 + (1 − µ ) x 2 принадлежат S привсех 0 ≤ µ ≤ 1 .Замечание.Эта формула может быть записана также в следующем виде:x = x 1 + th , 0 ≤ t ≤ 1 ,где h = x 2 − x 1 .Геометрически это означает, что если x1 и x2 принадлежат S, то отрезокпрямой, соединяющий эти две точки, также принадлежит S.

Таким образом,выражение (1) является параметрическим представлением отрезка прямой,соединяющей x1 и x2 (см. рис.).7Рис. 1.1. Пример выпуклого множества на плоскости.Определение.Функция f (x ) , определенная на выпуклом множестве S, называетсявыпуклой, если выполняется неравенствоf ( µx 1 + (1 − µ ) x 2 ) ≤ µf ( x 1 ) + (1 − µ ) f ( x 2 ) ,где 0 ≤ µ ≤ 1 , илиf ( x 1 + µh ) ≤ µf ( x 1 + h ) + (1 − µ ) f ( x 1 ) ,где 0 ≤ µ ≤ 1 , h = x 2 − x 1 .Замечание.С геометрической точки зрения это уравнение устанавливает, чтомежду любыми двумя точками на графике функции график лежит нижехорды, соединяющей точки [x 1 , f ( x 1 )] и [x 2 , f ( x 2 )] (рис.1.6.2).Рис. 1.2.

Выпуклая функция.[Из рисунка видно, что точка P имеет координаты µx 1 + (1 − µ ) x 2 ,]µf ( x 1 ) + (1 − µ ) f ( x 2 ) .8Примеры.Множество точек, удовлетворяющих неравенствуx T Qx ≤ 1является выпуклым, когда матрица Q вещественна, симметрична иположительно полуопределена.Действительно, µx 1 + (1 − µ ) x 2 , Q ( µx 1 + (1 − µ ) x 2 == µ2 x1, Qx1 + 2µ(1− µ) x1, Qx2 + (1− µ)2 x2 , Qx2 ≤{согласнонеравенствуКоши-Буняковского-Шварца}x1 , Qx2 ≤x1 , Qx1 x 2 , Qx2 ≤ {согласно (1)} ≤≤ 1 ≤ µ 2 + 2 µ (1 − µ ) + (1 − µ ) 2 = 1.При n = 2 это множество представляет собой совокупность точек,лежащих внутри эллипса..Пусть n = 2, Q – знакоопределенная матрица, то есть пусть Q = 0 − 11Тогда множеством точек0x T Qx ≤ 1 являются точки, координатыкоторых x1 и x2 удовлетворяют условию x12 − x 22 ≤ 1 .

Это множество –невыпуклое. Так, например, отрезок, соединяющий точкисодержится в указанном множестве (рис.1.6.3).Рис. 1.3. Невыпуклое множество на плоскости.9AиB, неРассмотрим пространство Rn. В нём расстояние или метрику можноввести вполне определенным образом. Рассмотрим четыре метрическихпространства со следующими метриками:nа) d ( x, y ) =2∑ ( xi − y i )=x − y, x − y ,i =1nб) d ( x, y ) = ∑ xi − y i ,i =1в) d ( x, y ) = max xi − y i ,1≤i ≤ nг) d ( x, y ) = x − y , M ( x − y )12,где M – положительно определенная симметричная (n × n ) – матрица.Рис. 1.4. Точки, равноудаленные от начала координат, соответствующие различно определённымрасстояниям.На рисунке показаны геометрические места точек, равноудаленных отначала координат, соответствующие четырём различно определеннымрасстояниям для n=2.

Множество точек, например, с d ( x, y ) ≤ r , где ∀r > 0 ,–это выпуклые множества.На рисунке 1.6.4. это множества области сначалом координат {точкой (0,0) T }, ограниченные соответствующимикривыми.101.03 Определение экстремума и его видыКак известно из математического анализа, функция скалярнойпеременной может иметь в заданном интервале более одного локального илиотносительного экстремума. Аналогично и функция n переменных взаданной области пространстваRnможет обладать несколькимиэкстремумами.Определение.Функция называется унимодальной в данной области, если она в этойобласти имеет единственный экстремум.

В противном случае она называетсямультимодальной.Определение.ε -окрестностью точки x0∈N называется такое множество точек x∈N,0для которых x − x < ε (рис. 1.5).Рис. 1.5. Окрестность N точки x0 и область S определения функции.Определение.Пусть ƒ(x) определена в подмножестве S пространства Rn. Функцияƒ(x) достигает локального [строго локального] минимума в точке x0∈S,[00если существует окрестность N(x0) такая, что f ( x) ≥ f ( x ) f ( x ) > f ( x )11]0для ∀x ∈ N ( x ) и S отлична от x0.Замечание.То, что x0 является локальным минимумом, не исключает возможностисуществования другой точкиx*∈ Sвне малой окрестностиN(x0), длякоторой ƒ(x*)< ƒ(x0).Определение.Если ƒ(x*) ≤ ƒ(x) [ƒ(x*) < ƒ(x)] для всех x∈ S, отличных от x*, то x*является глобальным [строгим глобальным] минимумом функции ƒ(x) наS.При этом число ƒ(x*) есть минимальное значение функции на S.Определение.Функция ƒ(x) достигает локального [строго локального] максимумав точке x0∈S, если существует окрестность N(x0) такая, чтоƒ(x) ≤ ƒ(x0) [ƒ(x) < ƒ(x0)] для ∀x∈N(x0) и S отлична от x0.Определение.Если ƒ(x*) ≥ ƒ(x) [ƒ(x*) > ƒ(x)] для всех x∈S, отличных от x*, то x*является глобальным [строгим глобальным] максимумом функции ƒ(x) наS.

При этом число ƒ(x*) есть максимальное значение функции на S.Замечания.Если функция не унимодальна в S, то в общем случае локальный иглобальный экстремумы (минимумы или максимумы) могут различаться. Все12известные методы позволяют определять локальный, а не глобальныйэкстремум. В задачах минимизации часто приходится сталкиваться сомногими локальными минимумами. Только при некоторых дополнительныхусловиях локальный минимум будет совпадать с глобальным.1. При решении задач отыскания глобального минимума существенноезначение имеет понятие выпуклости.2.

В соответствии с данными определениями выделяют следующие видыэкстремума в математическом программировании:3. Безусловный абсолютный (глобальный) экстремум (БАЭ). В этомслучае число ограничений g i , {i = 1, m} , равно 0, то есть m =1.4. Безусловный относительный (локальный) экстремум (БОЭ). В этомслучае также число ограничений m = 0.5. Условный абсолютный (глобальный) экстремум (УАЭ). В этом случаечисло ограничений m ≠ 0.6. Условный относительный (локальный) экстремум (УОЭ).

В этомслучае число ограничений m ≠ 0.Замечание.Заметим, что для произвольной целевой функции Ζ = Ζ(x1, x2,…,xn)имеет место:MaxΖ = min(–Ζ) и minΖ = max(–Ζ).1.04 Основные задачи линейного программированияТребуется найти такие значения переменных x1, x2, …, xn, которыеминимизируют целевую функциюz = f ( x1 , x 2 ,... x n ) ≡ c1 x1 + c2 x 2 + ... + cn x n13(1.5)при m < n линейных ограничениях – равенствах{}ai1 x1 + ai 2 x2 + ... + ain x n = bi , i = 1, m ,(1.6)и n линейных ограничениях – неравенствах{}x k ≥ 0, i = 1, n .(1.7)Замечание.Строгое неравенство сильно усложняет задачу. Например, найти x1доставляющий z=x1 максимум при x1<1. Решение в этом случае не ∃ (1.1).Рисунок 1.6 . Максимум при x1<1 не существует.Определение.Допустимымрешениемилипланомзадачилинейногопрограммирования, данной в стандартной форме, называется упорядоченноемножество чисел (x1, x2, …, xn) (то есть точка n-мерного пространства Rn),удовлетворяющих ограничениям вида (1.6) и (1.7).Определение.Оптимальным решением или оптимальным планом называетсядопустимое решение, минимизирующее целевую функцию, представляющуюсобой линейную форму вида (1.5).Замечание.14Чаще всего оптимальное решение, если оно существует, единственно,однако возможны случаи, когда оптимальных решений бесчисленноемножество.

Для существования допустимого решения необходимо, (но недостаточно), чтобы система (1.6) была совместна.В дальнейшем при решении задачи линейного программированиясчитается, что система (1.6) совместна и ранг матрицы системы равенr{r ≤ m < n}. В этом случае r линейно независимых уравнений системы (1.6)определяют некоторые r неизвестных как линейные функции остальныхn − r неизвестных, так называемых свободных неизвестных.Фактически, выражая все переменные через свободные неизвестные,можно перейти к задаче линейного программирования, содержащей n − rпеременных иnлинейных ограничений –неравенств, выражающихнеотрицательность исходных n переменных.Определение.Допустимое решение, соответствующее нулевым значениям свободныхнеизвестных, называется базисным допустимым решением или опорнымпланом, при этом решение или план называются невырожденными, еслинесвободные переменные положительны и вырождены, если среди них естьхоть одно нулевое.Замечания.Еслисуществуеткакое-либодопустимоерешениедлязадачилинейного программирования, то существует и базисное допустимоерешение.

Если, кроме того целевая функция имеет нижнюю границу намножестве решений, то есть существует оптимальное решение, тосуществует и оптимальное базисное решение.15Множество всех допустимых решений данной задачи линейногопрограммирования есть выпуклое множество вn-мерном пространстверешений. Это значит, что каждая точка ( ξ1 ,ξ 2 ,...,ξ n ) прямолинейногоотрезка, соединяющего два допустимых решения (x1, x2, …, xn)T и{(x'1, x'2, …, x'n)T :}ξ K = α x K + (1 − α ) x ' K , 0 ≤ α ≤ 1; k = 1, n , — естьтакже допустимое решение.Другими словами, множество допустимых решений есть выпуклыймногоугольник или многогранник в плоскости или гиперплоскости,определяемой уравнениями (1.5) с граничными линиями, плоскостями илигиперплоскостями (1.6).Пример.Множество решений на плоскости (x1, x2) для задачи линейногопрограммирования.Найти x1,x2→доставляющиеz=3x1+2x2 минимум, то есть z=3x1+2x2=min приусловияхg1 ≡ x1 ≥ 0; g 2 ≡ x2 ≥ 0; g 3 ≡ 5 x1 + x2 − 5 ≥ 0 (рис.

2.2).16zz = 12=6z = 6 z = 9 z = 12z=9Рисунок 1.7. Геометрическое представление множества решений.1.05 Типовые задачиТранспортная задача.В трех месторождениях добывается определенное количество угля.Имеются три пункта потребления угля. Известны расстояния междупунктами добычи и потребления и стоимость перевозок cij{ i = 1,3; j = 1,3}.Необходимо так определить девять чисел xij , означающих количествогрузов, перевозимых с пункта добычи на пункт потребления, чтобысуммарная стоимость перевозок была минимальна:L = ∑ cij xij = min(1.8)i, jпри условияхL = ∑ cij xij = min ,i, j17(1.9)требующих, чтобы спрос bi удовлетворялся во всех пунктах, и приусловиях{}xi1 + xi 2 + xi 3 = a j , i = 1,3 ,(1.10)требующих, чтобы из каждого пункта добычи вывозилось угля небольше количества ai, которое на нем производится.Как правило, в таких задачах считается, что сумма добытогоколичества равна сумме потребляемого, то есть33∑ ai = ∑ b j , хотя это ограничение не принципиально.i =1j =1Задача о рациональном питании.При правильном питании калорийность пищевых продуктов должнаполностью возмещать расход энергии человека, причём потреблениеотдельных растительных и животных жиров, белков, углеводов и витаминовне должно превышать определенную норму.Предположим, что имеется n различных продуктов калорийностьюa1 j{j = 1, n}, равной числу калорий в единице массы.

Характеристики

Список файлов лекций