Книги по разным темам Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |

Получаем задачу безусловной минимизации P(x, R)= x + R 2 - x min.

При этом предполагается, что x - внешняя точка, т.е.

x < 2, g(x) = 2 - x > 0.

Уравнение, определяющее стационарные точки P(x,R), имеет вид dP = 1- 2R 2 - x = 0.

dx Поскольку 2 - x > 0, то по определению срезки получим 2 - x = 2 - x.

Находим стационарную точку x(1)(R):

1- 2R 2 - x = 0 x(1) R = 2 -1 2R.

( ) ( ) ( ) При этом g(x(1) (R)) = 1 2R > 0 при R>0, ( ) т.е. при любом конечном R>0 соответствующая стационарная точка является недопустимой (внешней) точкой и сделанное предположение не нарушается.

Точка x*, являющаяся решением исходной задачи, определяется следующим образом:

x* = lim x(1) R = lim 2 -1 2R = 2.

( ) ( ( )) R R б) Метод внутренней точки.

огарифмическая штрафная функция имеет вид (R, g(x))= -R ln(x - 2).

Получаем задачу безусловной минимизации P(x, R)= x - R ln(x - 2) min.

При этом предполагается, что x - внутренняя точка, т.е.

x 2, g(x) = 2 - x 0.

Уравнение, определяющее стационарные точки P(x, R), имеет вид dP R =1- = 0.

dx x - Находим стационарную точку x(1)(R):

x(1)(R) = 2 + R.

При этом g(x(1) (R)) = -R 0 при R 0, т.е. при любом R0 соответствующая стационарная точка является допустимой (внутренней) точкой и сделанное предположение не нарушается.

Точка x*, являющаяся решением исходной задачи, определяется следующим образом:

x* = lim x(1)(R) = lim (2 + R) = 2.

R R 0 в) Метод внутренней точки.

Обратная штрафная функция имеет вид 1 R (R, g(x))= -R =.

2 - x x - Получаем задачу безусловной минимизации R P(x, R)= x + min.

x - При этом предполагается, что x - внутренняя точка, т.е.

x 2, g(x) = 2 - x 0.

Уравнение, определяющее стационарные точки P(x, R), имеет вид dP R = 1- = 0.

dx (x - 2)Находим стационарные точки x(1,2)(R):

x(1,2)(R) = 2 R.

При этом g(x(1) (R)) = - R 0 при R 0, т.е. при любом R0 стационарная точка x(1)(R) является допустимой (внутренней) точкой и сделанное предположение не нарушается.

С другой стороны g(x(2) (R)) = R > 0 при R > 0, т.е. при любом R>0 сделанное предположение нарушается, стационарная точка x(2)(R) является недопустимой (внешней) точкой и должна быть отброшена.

Решение x* исходной задачи определяется следующим образом:

x* = lim x(1)(R) = lim (2 + R ) = 2.

R 0 R Алгоритм численного решения задачи условной минимизации методом штрафных функций заключается в следующем.

1. Задаются, 1,, R0, c и x[0] ; определяется тип x[0] (внутренняя или внешняя); выбирается штрафная функция ;

строится расширенная функция P; полагается t=1.

2. Решается одним из численных методов задача безусловной минимизации P(x, Rt -1) min, x Rn.

При этом начальная точка x(0) = x[t -1], условие окончания вычислений () P x(k ), Rt -1.

Результатом решения задачи безусловной минимизации является точка x[t], в качестве которой используется оценка x(k ) точки минимума задачи безусловной минимизации.

3. Проверяется условие t=1.

Если оно выполняется, то осуществляется переход к п.5.

Если условие не выполняется, то осуществляется переход к п.4.

4. Проверяются условия окончания решения исходной задачи:

P(x[t ], Rt-1) - P(x[t-1], Rt-2 ) 1, P(x[t-1], Rt-2 ) x[jt ] - x[jt -1], j = 1,n.

x[jt-1] Если они выполняются, то полагается x* x[t], * f f (x[t ] ) и вычисления завершаются.

Если условия не выполняются, то осуществляется переход к п.5.

5. Определяется Rt, полагается t=t+1 и осуществляется переход к п.2.

Пример. Решить методом штрафных функций задачу условной минимизации f (x) = (x1 - 4)2 + (x2 - 4)2 min, x1 + x2 при = 0,2, 1 = 0,4, = 0,1, R0 = 10, c = 10, x[0] = (1,1). Для решения задачи безусловной минимизации применить градиентный метод с дроблением шага ( = 1, = 1 4).

Решение.

Преобразуем ограничение исходной задачи к виду g(x) 0:

g(x) = x1 + x2 - 5 0.

Определяем тип x[0]:

g(x[0]) = 1+1- 5 = -3 < 0.

Поскольку ограничение выполняется, то точка x[0] является внутренней (допустимой).

Выбираем обратную штрафную функцию, т.е.

(R, g(x)) = - R g(x).

При этом расширенная функция P(x,R) имеет вид P(x, R) = f (x) - R g(x).

Первый этап Решаем градиентным методом с дроблением шага (МДШ) задачу безусловной минимизации P(x, R0 ) = (x1 - 4)2 + (x2 - 4)2 + min.

5 - x1 - xНачальная точка x(0) = x[0] = (1, 1), =1, =, = 0,2.

Отметим, что в процессе решения нужно контролировать знак штрафной функции (R, g(x)). Если окажется, что на k-м шаге (R, g(x)) < 0, следует уменьшать (дробить) k.

Находим первые частные производные P(x, R0) :

P 10 P = 2(x1 - 4) +, = 2(x2 - 4) +.

x1 x(5 - x1 - x2)2 (5 - x1 - x2)Результаты вычислений заносим в табл. 9.1.

Таблица 9.P P Ном.

x1 x2 x2 P P x xитер. x0 1 1 3,33 21,3 -4,89 -4,89 6,1 1 0,707 0,707 1,71 1,71 6,33 16,82 -0,57 -0,57 0,2 1 0,707 0,707 2,42 2,42 62,5 67,P(x(2) ) > P(x(1) ) = = 0,2 0,25 0,177 0,177 1,89 1,89 8,20 17,P(x(2) ) > P(x(1) ) = = 0,2 0,0625 0,044 0,044 1,75 1,75 6,67 16,79 -0,055 -0,055 0,Поскольку условие окончания вычислений выполнено (0,078<0,2), то вычисления завершаются. В результате решения задачи безусловной минимизации получаем x[1] x(2) = (1,75;1,75), P(x[1], R0) P(x(2), R0) = 16,79.

Определяем R1 = R0 c = 10 10 = 1 и выполняем второй этап.

Второй этап Решаем МДШ задачу безусловной минимизации P(x, R1) = (x1 - 4)2 + (x2 - 4)2 + min.

5 - x1 - xНачальная точка x(0) = x[1] = (1,75; 1,75), =1, =, = 0,2.

Находим первые частные производные P(x, R1) :

P 1 P = 2(x1 - 4) +, = 2(x2 - 4) +.

x1 x(5 - x1 - x2 )2 (5 - x1 - x2)Результаты вычислений заносим в табл. 9.2.

Таблица 9.P P Ном.

x1 x2 x1 x2 P P x xитер.

0 1,75 1,75 0,67 10,79 -4,06 -4,06 5,1 1 0,707 0,707 2,46 2,46 12,5 17,P(x(1) ) > P(x(0) ) = = 0,1 0,25 0,177 0,177 1,93 1,93 0,88 9,45 -3,37 -3,37 4,2 0,25 0,177 0,177 2,10 2,10 1,25 8,47 -2,24 -2,24 3,3 0,25 0,177 0,177 2,28 2,28 2,27 8,19 1,72 1,72 2,4 0,25 -0,177 -0,177 2,10 2,10 1,25 8,P(x(4) ) > P(x(3) ) = = 0,4 0,0625 -0,044 -0,044 2,23 2,23 1,85 8,12 -0,11 -0,11 0,Поскольку условие окончания вычислений выполнено (0,156<0,2), то вычисления завершаются. В результате решения задачи безусловной минимизации получаем x[2] x(4) = (2,23; 2,23), P(x[2], R1) P(x(4), R1) = 8,12.

Проверяем условия окончания решения исходной задачи P(x[2], R1) - P(x[1], R0 ) 8,12 -16,= = 0,516 > 1 = 0,4.

16,P(x[1], R0) Поскольку условия не выполняются, то определяем R2 = R1 c = 1 10 = 0,1 и выполняем третий этап.

Третий этап Решаем МДШ задачу безусловной минимизации 0,P(x, R2 ) = (x1 - 4)2 + (x2 - 4)2 + min.

5 - x1 - xНачальная точка x(0) = x[2] = (2,23;2,23), = 1, =, = 0,2.

Находим первые частные производные P(x, R2 ) :

P 0,1 P 0,= 2(x1 - 4) +, = 2(x2 - 4) +.

x1 (5 - x1 - x2 )2 x2 (5 - x1 - x2 )Результаты вычислений заносим в табл. 9.3.

Таблица 9.P Ном. P P x1 x2 P x1 xитер.

x1 x0 2,23 2,23 0,185 6,45 -3,2 -3,2 4,1 1 0,707 0,707 2,94 2,94 -0,(R2, g(x)) = -0,114 < 0 = = 0,1 0,25 0,177 0,177 2,41 2,41 0,556 5,61 -0,09 -0,09 0,Поскольку условие окончания вычислений выполнено (0,127<0,2), то вычисления завершаются. В результате решения задачи безусловной минимизации получаем x[3] x(1) = (2,41; 2,41), P(x[3], R2 ) P(x(1), R2 ) = 5,61.

Проверяем условия окончания вычислений исходной задачи P(x[3], R2 ) - P(x[2], R1) 5,61 - 8,= = 0,309 < 1 = 0,4, 8,P(x[2], R1) x[3] - x[2] 2,41 - 2,j j = = 0,081 < 2 = 0,1, j = 1,2.

2,x[2] j Поскольку условия выполняются, то полагаем * x x[3] (2,41; 2,41), f f (x[3]) 5,06 и вычисления завершаются.

* Ответ: x* (2,41; 2,41), f 5,06.

Задачи 1. Дана задача условной минимизации f (x) = (x1 - 4)2 + (x2 - 4)2 min, x1 + x2 5.

Решить аналитически: а) методом внешней точки, б) методом внутренней точки (логарифмическая штрафная функция).

2. Дана задача условной минимизации f (x) = x1+ x2 min, x1 x2, x1 1.

Решить аналитически методом внутренней точки (логарифмическая штрафная функция).

10. МЕТОДЫ ОТСЕЧЕНИЙ Методы отсечений относятся к численным методам решения дискретных задач оптимизации (методам дискретного программирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП). Идея методов отсечения состоит в следующем.

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

1) полученное нецелочисленное решение ему не удовлетворяет;

2) все целочисленные точки допустимого множества исходной задачи ему удовлетворяют.

Такое ограничение называется правильным отсечением.

Затем решается расширенная непрерывная задача ЛП, т.е.

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

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

Обозначим через Lk и x(k ), k=0,1,..., соответственно k-ю расширенную непрерывную задачу ЛП и ее решение. Отметим, что L0 представляет собой исходную задачу без учета требований целочисленности. Задача Lk+1 получается в результате добавления к ограничениям задачи Lk (k+1)-го правильного отсечения.

Алгоритм решения целочисленной задачи ЛП методом отсечений заключается в следующем.

1. Решается задача ЛП L0.

Если задача L0 не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются.

2. Находится решение x(0).

Если решение x(0) является целочисленным, то полагается x = x(0), f = f (x(0)) и вычисления завершаются.

Если решение x(0) не является целочисленным, то полагается k = 1 и осуществляется переход к п. 3.

3. Определяется k-е правильное отсечение, составляется задача Lk.

4. Решается задача ЛП Lk.

Если задача Lk не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются.

5. Находится решение x(k ).

Если решение x(k ) является целочисленным, то полагается x = x(k ), f = f (x(k )) и вычисления завершаются.

Если решение x(k ) не является целочисленным, то полагается k = k +1 и осуществляется переход к п. 3.

Конкретные способы построения правильных отсечений приводят к конкретным вычислительным алгоритмам.

На практическом занятии рассматривается первый (дробный) алгоритм Гомори, предназначенный для решения полностью целочисленных задач ЛП. Рассмотрим полностью целочисленную задачу ЛП:

n f (x) = c x max, j j j=n aij x bi, i = 1, m, j j=x 0, = 1,n, j j xj - целые, j = 1, n.

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

Первоначально решается задача L0. Пусть решение x(0) этой задачи не является целочисленным. Согласно общему алгоритму, следует определить дополнительное ограничение (1-е правильное отсечение). Пусть последняя симплекс-таблица задачи L0 имеет следующий вид:

Своб.

Базис......

x1 xm x1 xn член 1... 0a11... a1n x1 b......

0... 1...

xm bm a a m1 mn f...

c b0 0... 0 1 c n Здесь через xi, i = 1, m, обозначены базисные переменные, а через xj, j = 1, n, - свободные переменные. Такая система обозначений выбрана из соображений удобства.

Строки симплекс-таблицы, которым соответствуют нецелые значения базисных переменных, т.е. нецелые bi, называют производящими. Каждая производящая строка задает правильное отсечение, которое определяется следующим образом: i-я производящая строка записывается в виде n (1+ 0)xi + ([aij ] +{aij})x = [bi ] +{bi}, j j=где [а] и {a} - соответственно целая и дробная части действительного числа а, a = [a] +{a}.

Эта производящая строка задает правильное отсечение следующего вида:

n - {aij}x + u1 = -{bi}, j j =где u1 - неотрицательная дополнительная переменная, которая (по определению) должна принимать целые значения.

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

Первое из них предписывает выбирать производящую строку, которой соответствует max{bi}, i второе - строку, которой соответствует n maxdi {b } {a }.

i ij i j= Если с помощью указанных правил не удается выбрать производящую строку для построения правильного отсечения, производящая строка выбирается произвольно.

В результате добавления к ограничениям задачи L0 дополнительного ограничения (1-го правильного отсечения) получаем задачу L1, т.е.

L0, n L1 {aij}xj + u1 = -{bi}, - j = u1 0.

Наиболее удобным методом решения задачи L1 в указанной постановке является двойственный симплекс-метод. При этом дополнительная переменная u1 вводится в базис, а дополнительное ограничение добавляется к итоговой симплекс-таблице задачи L0.

Пример. Решить методом отсечений следующую целочисленную задачу ЛП:

f (x) = 7x1 + 9x2 max, - x1 + 3x2 6, 7x1 + x2 35, x1 0, x2 0, x1, x2 - целые.

Решение.

Нулевой этап Записываем задачу L0 (исходная задача без учета требования целочисленности):

f (x) = 7x1 + 9x2 max, - x1 + 3x2 6, 7x1 + x2 35, x1 0, x2 0.

Решаем задачу L0 симплекс-методом. Для этого преобразуем задачу к канонической форме, вводя дополнительные переменные x3 и x4:

f (x) = 7x1 + 9x2 max, - x1 + 3x2 + х3 = 6, 7x1 + x2 + х4 = 35, x 0, j = 1,4.

j В качестве базисных выберем переменные x3 и x4. Таким образом, начальный базис Б0 = {x3, x4}. В результате приходим к табл. 10.1.

Из табл. 10.1 следует, что начальное допустимое базисное решение ДБР0 = (x3=6, x4=35). ДБР не является оптимальным, поскольку в строке целевой функции есть отрицательные коэффициенты fx = -7, fx = -9. Задача разрешима, поскольку в 1 столбцах x1 и x2 есть положительные коэффициенты. Находим Б1:

Таблица 10. Своб.

Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |    Книги по разным темам