УМК (1013374), страница 10
Текст из файла (страница 10)
На каждой k-й итерации ищется точка x ∗ ( r k ) миниму-ма смешанной вспомогательной функции при заданном параметре r k с помощью одногоиз методов безусловной минимизации. Полученная точка x ∗ (r k ) используется в качестве начальной на следующей итерации, выполняемой при уменьшающемся значении па-54раметра штрафа. При r k → +0 последовательность точек x ∗ (r k ) стремится к точке условного минимума x ∗ .АлгоритмШаг 1. Задать начальную точку x 0 так, чтобы g j ( x) < 0 , j = m + 1, … , p ; начальное значение параметра штрафа r 0 > 0 ; число C > 1 для уменьшения параметра штрафа;малое число ε для остановки алгоритма. Положить k = 0 .Шаг 2. Составить смешанную вспомогательную функцию:(F x, rkm) = f ( x) + 2r k ∑j =1 [ g j ( x) ]12−rkp(1= f ( x ) + P x, r kj = m +1 g j ( x )∑)или(F x, rkm) = f ( x) + 2r k ∑j =1 [ g j ( x) ]12−rkp∑j = m +1()ln[ − g j ( x) ] = f ( x ) + P x, r k .()Шаг 3.
Найти точку x ∗ (r k ) минимума функции F x , r k с помощью какого-либометода поиска безусловного минимума с проверкой выполнения справедливости неравенств: g j ( x) < 0 , j = m + 1, … , p . При этом задать все требуемые выбранным методомпараметры. В качестве начальной точки взять x k .()Шаг 4. Вычислить P x ∗ (r k ), r k и проверить условие окончания:(а) если P x ∗ (r k ), r k) ≤ ε , процесс поиска закончить:x ∗ = x ∗ (r k ),(б) если P x ∗ (r k ), r k)()f ( x ∗ ) = f x ∗ (r k ) ;> ε , то положить r k +1 =rk,Cx k +1 = x ∗ (r k ),k = k +1 иперейти к шагу 2.З а м е ч а н и я.1.
Метод предложен Фиакко и Мак-Кормиком (Fiacco, McCormick). Они рекомендуют r 0 = 1, C = 4 .2. Можно использовать разные параметры штрафа для внешних и внутреннихштрафов.55Лекция 76. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯA. СИМПЛЕКС-МЕТОД ДАНЦИГАА1. Решение канонической задачиПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ ai j x jj =1= bi , i = 1,… , m; m < n ,x j ≥ 0 , j = 1, … , n .Задача называется канонической, а искомое решение x ∗ = ( x1∗ ,..., x n∗ )T – оптимальным.З а м е ч а н и я.1. Максимизируемая функция и ограничения линейны по x j , j = 1, … , n .2. Задача содержит ограничения на неотрицательность переменных, присутствиекоторых диктуется процедурой описанного ниже симплекс-метода.3. Будем считать, что в ограничениях все числа bi ≥ 0 , i = 1, … , m .
Этого можнодобиться, умножая ограничения, где bi < 0 , на “ − 1 ”.Стратегия поискаСтратегия метода Данцига (Dantzig) решения задачи основана на особенностях постановки этой задачи. Множество⎧⎪X = ⎨x⎪⎩n∑ ai j x j = bi ;i = 1, … , m;j =1x ∈ R n;⎫⎪x j ≥ 0; j = 1, … , n ⎬⎪⎭допустимых решений задачи, определяемое ограничениями, есть выпуклое множество,которое геометрически представляет собой выпуклый политоп, имеющий конечное числокрайних точек.Крайней точкой выпуклого множества X называется точка x ∈ X , которая не может быть выражена в виде выпуклой комбинации других точек y ∈ X , x ≠ y .Классический метод Гаусса–Жордана решения систем линейных уравнений состоит в приведении их к виду56+ a1m +1 x m +1 + … + a1s x s + … + a1n x n = b1 ,x1xk+ ak m +1 x m +1 + … + ak s x s + … + ak n x n = bk ,x m + amm +1 x m +1 + … + am s x s + … + amn x n = bm .Переменные x1 ,… , x m , входящие только в одно из уравнений системы с коэффициентами 1, а во все остальные уравнения с коэффициентами, равными нулю, называются базисными, в то время как остальные n − m переменных называются небазисными(свободными).
Базисным решением системы называется решениеx i = bi , i = 1, … , m ; x m +1 = … = xn = 0 .Базисное решение называется допустимым, если xi ≥ 0 , i = 1, … , m . Базисное решение называется невырожденным, если xi > 0 , i = 1, … , m .Множество крайних точек политопа X, определяемого ограничениями, соответствует множеству допустимых базисных решений системы, и при этом одному базисномурешению соответствует одна крайняя точка.Утверждение. Если функция f ( x ) в канонической задаче достигает максимума наполитопе X, определяемом ограничениями, то она достигает его по крайней мере в одной крайней точке этого политопа. Если она достигает его в нескольких крайних точках, то она достигает его на любой выпуклой комбинации этих крайних точек.Теорема определяет стратегию решения задачи, реализованную с помощью симплекс-метода, – это направленный перебор базисных решений, определяющих крайниеточки политопа.
Направленность перебора предполагает следующую организацию вычислительного процесса.1. Нахождение начального базисного решения.2. Переход от одного базисного решения к другому таким образом, чтобы обеспечить возрастание f ( x) .А2. Решение основной задачиПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ aij x j ≥ bi ,j =1n∑ aij x j ≤ bi ,i = 1, … , m ;i = m + 1, … , p ;j =1x j ≥ 0 , j = 1, … , n .Данная задача линейного программирования называется основной. Предполагается, что bi ≥ 0 , i = 1, … , p .57Стратегия поискаДля решения основной задачи симплекс-методом она должна быть приведена кканонической задаче путем введения в каждое ограничение по одной дополнительной переменной: в каждое ограничение-неравенство со знаком « ≤ » вводится дополнительнаяпеременная со знаком « + » (она становится базисной), а в каждое ограничениенеравенство со знаком « ≥ » вводится дополнительная переменная со знаком «–».Каноническая задача записывается следующим образом:nf ( x) = ∑ c j x j → max ,j =1n∑ aij x j − x n +i = bi ,i = 1, … , m ;j =1n∑ aij x j + x n +i = bi ,i = m + 1, … , p ;j =1x1 ≥ 0, … , x n + p ≥ 0 .Так как в общем случае в уравнениях нет базисных переменных, то для того, чтобыможно было применить симплекс-метод, делается переход к М-задаче.
В каждое из mуравнений вводится искусственная переменная со знаком « + » (она становится базисной),а к целевой функции добавляется сумма искусственных переменных, умноженная на« − M ». В результате получаем задачу в расширенной форме:nf ( x) = ∑ c j x j − Mj =1nm∑ x n + p +i → max ,i =1∑ aij x j − x n +i + x n + p +i = bi ,i = 1, … , m ;j =1n∑ aij x j + x n +i = bi ,i = m + 1, … , p ;j =1x1 ≥ 0, … , x n + p + m ≥ 0 .З а м е ч а н и я.Если решается задача поиска минимума целевой функции, то при переходе к M задаче перед числом M ставится знак « + ».58Б. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯВ случае двух переменных задача линейного программирования имеет простуюгеометрическую интерпретацию и может быть решена графически с помощью следующего алгоритма.Алгоритм1.
Построить множество допустимых решений. В общем случае оно представляетсобой выпуклый многоугольник. Если ограничения в задаче несовместны, множество допустимых решений является пустым множеством, а задача поиска экстремума не имеетсмысла.2. Найти градиент целевой функции. В силу ее линейности градиент постоянен иможет быть построен в любой точке координатной плоскости (как правило, он строится вначале координат).3. Провести линию уровня функции, перпендикулярную градиенту.4. Передвигать линию уровня параллельно самой себе до касания с множествомдопустимых решений. Точки касания являются точками экстремума.5. Классифицировать точки касания с использованием свойств градиента.В случае непустого множества допустимых решений возможны три типовые ситуации:а) задача имеет единственное решение (линия уровня касается множества допустимых решений в одной точке);б) задача имеет бесконечное множество решений (линия уровня касается множества допустимых решений вдоль стороны многоугольника);в) задача не имеет решения (множество допустимых решений не ограничено).Заметим, что графически можно решать и задачи с ограничениями типа равенств,если число ограничений на единицу или на два меньше числа переменных.
Способ решения: сведение к задаче с одной или двумя переменными соответственно. Для этого следует выразить целевую функцию и базисные переменные через свободные и воспользоваться условием неотрицательности, типичным для задач линейного программирования. Далее необходимо пользоваться приведенным алгоритмом графического решения задач линейного программирования.Пример.
Решить графически следующие задачи линейного программирования:а) f ( x ) = − x1 + x 2 → extr ,б) f ( x ) = x1 → extr ,x1 + x 2 ≤ 1 ,x1 + x 2 ≤ 1 ,x1 ≥ 0, x 2 ≥ 0 ;x1 ≥ 0, x 2 ≥ 0 ;в) f ( x ) = − x1 − x 2 → extr ,x1 ≥ 1 , x 2 ≥ 1 . Воспользуемся приведенным алгоритмом графического решения задач линейного программирования.В задаче «a» в точке A = (0; 1)T достигается максимум, а в точке B = (1; 0)T – минимум. Очевидно, и минимум, и максимум единственные.59В задаче «б» в точке C = (1; 0)T достигается максимум, а на отрезке АВ – минимум, т.е. имеется бесконечное множество решений.x2∇fx2A 1f ( x) = 0f ( x) = 11 B1B−10x2−1C∇f 11 x1 0 AA0x11∇fаб−1x1f ( x) = 0вРис.
1В задаче «в» в точке A = (1; 1)T достигается максимум, а минимума нет, так какмножество допустимых решений в направлении антиградиента (наискорейшего убыванияфункции) неограниченное. 7. ЗАДАЧИ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГОПРОГРАММИРОВАНИЯ. МЕТОД ВЕТВЕЙ И ГРАНИЦПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ aij x jj =1≤ bi , i = 1, … , m ;x j ≥ 0 , целые, j = 1, … , n .Задача называется задачей линейного целочисленного программирования.60Стратегия поискаЗадача решается симплекс-методом без учета ограничений на целочисленность переменных (эта задача обозначается ЗЛП-0).
Считается, что она имеет решение. На опти-( )мальном решении x 0∗ = ( x10∗ ,… , x n0∗ ) T вычисляется значение целевой функции f x 0∗ .Если решение x 0∗ является целочисленным, то поставленная задача решена. Еслирешение x 0∗ оказывается нецелочисленным, то значение f ( x 0∗ ) является верхней границей возможных оптимальных значений f ( x ) на целочисленных решениях. При нецелочисленном решении дальнейшая процедура решения задачи состоит в ее ветвлении надве: ЗЛП-1 и ЗЛП-2 (рис.2). Целью этого ветвления является разбиение множества допустимых решений, определяемого ограничениями, на два подмножества путем формирования дополнительных ограничений таким образом, чтобы исключить нецелочисленнуюточку x 0∗ и сделать решение, по крайней мере одной из задач, целочисленным по однойвыбранной координате x k .Координатой x k может быть:• нецелочисленная координата с наименьшим или наибольшим индексом;• нецелочисленная координата с наименьшей или наибольшей дробной частью;• нецелочисленная координата, которой соответствует наибольший коэффициентв целевой функции;• нецелочисленная координата, выбранная на основании приоритетов, определяемых физическим содержанием задачи.ЗЛП-0x 0∗ , f (x 0∗ )[ ][ ]x k ≤ x k0∗x k ≥ x k0∗ + 1ЗЛП-1x , f (x 1∗ ) > f (x 2∗ )ЗЛП-2x , f ( x 2∗ ) > fнецелочисленноенецелочисленное2∗1∗xj ≤[ ][ ]x 1j∗ЗЛП-3x , f ( x 3∗ ) < f3∗нецелочисленноеx j ≥ x 1j ∗ + 1xi ≤[x ]2∗iЗЛП-4x , f (x 4∗ ) = fЗЛП-5x , f ( x 5∗ ) < fцелочисленноенецелочисленное4∗Рис.
2615∗[ ]x i ≥ x i2∗ + 1ЗЛП-6X =∅[ ]≤ [x ] ,Для формирования дополнительных ограничений выделяется целая часть x k0∗x k0∗ . Дополнительные ограничения имеют видзначения координаты[ ]xk0∗kx k ≥ x k0∗ + 1 .Задачи ЗЛП-1 и ЗЛП-2 записываются в следующем виде:ЗЛП-1ЗЛП-2nnf ( x) = ∑ c j x j → max ,f ( x) = ∑ c j x j → max ,j =1n∑ aij x jj =1j =1n∑ aij x j≤ bi , i = 1, … , m ,j =1[ ]≤ bi , i = 1, … , m ,[ ]x k ≤ x k0∗ ,x k ≥ x k0∗ + 1 ,x j ≥ 0 , j = 1, … , n ;x j ≥ 0 , j = 1, … , n .Формирование дополнительных ограничений позволило исключить из рассмотрения оптимальное нецелочисленное решение x 0∗ и обеспечить целочисленность значенийкоординаты x k .Задачи ЗЛП-1 и ЗЛП-2 решаются самостоятельно симплекс-методом без учета требований на целочисленность значений координат x j , j = 1, … , n . Вычисляются значенияфункции f ( x) на оптимальных решениях обеих задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
