Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Оптимизация
| Харчистов Б.Ф.. Методы оптимизации, 2004 | |
КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ |
|
|
Задачей квадратичного программирования (КП) называется задача оптимизации с квадратичной целевой функцией и линейными ограничениями. Задача КП, в которой целевая функция подлежит минимизации, имеет вид n n n f (x) = E c,x, + n djkxjxk ^min, j=1 j=1 k=1 E aijXj < b, i = 1, m, j=1 xf > 0, j = ГП. j ' ^ ' Допустимое множество X является выпуклым, матрица D = [djk ] предполагается симметричной неотрицательно определенной. При этом f (x) является выпуклой на X и задача КП является частным случаем задачи выпуклого программирования. Для решения задачи КП используются необходимые усло - вия Куна - Таккера, которые в силу выпуклости задачи КП оказываются также достаточными для установления наличия решения. Предварительно составляется функция Лагранжа L( x, Я) = f (x) + E hg (x), i =1 где gj(x) = E aijxj - b. j=1 Условия Куна - Таккера имеют следующий вид: dL( x,X) > 0, j = 1,n; (3.1) dL( x,X) . -Ч x,-^ = 0, j = 1, n; (3.3) xj > 0, j = 1,n; (3.2) (x dx, dxj dL( x, X) < 0, i = 1, m; (3.4) dX, X > 0, i = 1m; (3.5) dL( x, X) X Ч= 0, i = 1, m. (3.6) ' dX Соотношения (3.3) и (3.6) определяют условия дополняющей нежесткости. Непосредственное решение данной системы очень громоздко. Поэтому используется следующий прием. Неравенства (3.1) и (3.4) преобразуют в равенства, вводя соответственно две группы дополнительных переменных V., j = 1, n, и wt, i = 1, m, удовлетворяющих требованиям неотрицательности. В результате от системы (3.1)-(3.6) переходят к следующей системе: dL( x, X) . -Ч dx - vj = 0 j =1 n; (3 7) x. > 0, v. > 0, j = Щ (3.8) x jV j = 0, j = Щ (3.9) dLX) + w, = 0, i = (3.10) оХ. X > 0, w, > 0, i = (3.11) X,w, = 0, i = 1, m. (3.12) Система уравнений (3.7) и (3.10) содержит (m + n) линейных уравнений с 2(m + n) неизвестными. Таким образом, исходная задача эквивалентна задаче нахождения допустимого, т.е. удовлетворяющего требованиям неотрицательности (3.8) и (3.11), базисного решения системы линейных уравнений (3.7) и (3.10), удовлетворяющего также условиям дополняющей нежесткости (3.9) и (3.12). Так как задача КП является выпуклой задачей оптимизации, то допустимое решение, которое удовлетворяет всем этим условиям, является оптимальным. Для нахождения допустимого базисного решения системы линейных уравнений может быть применен метод искусственных переменных, используемый в линейном программировании (ЛП) для определения начального базиса. При этом в уравнения системы (3.7), (3.10), в которых знаки дополнительных переменных v- или wi совпадают со знаками свободных членов, вводятся неотрицательные искусственные переменные zl, l = 1, /max, /max < m + n, знаки которых не совпадают со знаками соответствующих свободных членов. Затем решается вспомогательная задача ЛП F (z) = E zx ^ min / при ограничениях (3.7) - (3.12) с введенными неотрицательными искусственными переменными. Для решения этой задачи исполь-зуется симплекс-метод. В процессе решения необходимо учитывать условия дополняющей нежесткости (3.9) и (3.12). Выполнение этих условий означает, что x, и v-, Я и wi не могут быть положительными одновременно, т.е. переменную x j нельзя сделать базисной, если vj является базисной и принимает положительное значение, также и Я с wi. В результате решения вспомогательной задачи могут быть два случая. min F (z) = 0, т.е. все искусственные переменные выве- z дены из базиса. Полученное оптимальное допустимое базисное решение вспомогательной задачи ЛП является допустимым базисным решением системы (3.7) - (3.12) и, следовательно, решением задачи КП. min F(z) > 0, т.е. среди базисных остались искусствен- z ные переменные. Это означает, что система (3.7) - (3.12) не имеет допустимого базисного решения и, следовательно, задача КП не имеет решения. Итак, алгоритм решения задачи КП заключается в сле- дующем. Ограничения задачи КП преобразуются к виду g, (x) < 0, i = 1, m. Составляется функция Лагранжа L( x, X) = f (x) +lXg, (x). i=1 3 Н dL , 1 dL Находятся частные производные , j = 1, n; , dx ^ dX J 1 i = 1,m , и составляются условия Куна - Таккера (3.1) - (3.6). Посредством введения дополнительных переменных Vj, j = 1, n; w,, i = 1, m , неравенства dL > 0, dk < 0 dxj ' ЭХ преобразуются в равенства dL n dL v, = 0, + w, = 0, dxj j dX, ' в результате получается система (3.7) - (3.12). Вводятся искусственные переменные zx, составляется вспомогательная задача ЛП минимизации F(z) = Е zt при огра- i ничениях (3.7) - (3.12) с введенными неотрицательными искусственными переменными. Решается вспомогательная задача ЛП симплекс- методом с учетом условий дополняющей нежесткости. Если в результате решения min F(z) = 0, то оптимальное z допустимое базисное решение вспомогательной задачи определяет решение x* задачи КП. Если min F(z) > 0, то задача КП не имеет решения. z Пример. Решить следующую задачу КП: f (x) = 2x12 + 2x1 x2 + 2 x22 - 4x1 - 6x2 ^ min, x1 + 2x2 < 2, xj > 0, x2 > 0. Решение. Преобразуем ограничение исходной задачи к виду g (x) < 0: g(x) = x1 + 2x2 - 2 < 0. Составляем функцию Лагранжа L(x, Я) = 2xj2 + 2x1x2 + 2x22 - 4x1 - 6x2 + Я(x1 + 2x2 - 2). Находим частные производные и составляем условия Куна - Таккера: Ч = 4x + 2x2 -4 + Я> 0, x > 0, x - = 0; 1 2 1 1 dx1 dx1 Ч = 2x + 4x2 - 6 + 2Я > 0, x2 > 0, x2 - = 0; 1 2 2 2 dx2 dx2 Ч = x> + 2x2 -2< 0, Я> 0, ЯЧ = 0. дЯ 1 2 ЭЯ Вводим дополнительные переменные v1, v2 и w, обра-щающие неравенства в равенства, в результате получаем 4x1 + 2x2 - 4 + Я - v1 = 0, x1 > 0, v1 > 0, x1v1 = 0; 2x1 + 4x2 - 6 + 2Я - v2 = 0, x2 > 0, v2 > 0, x2v2 = 0; x1 + 2x2 -2 + w = 0, Я> 0, w > 0, Яw = 0. Получили систему 3-х линейных уравнений с шестью неизвестными, которые должны также удовлетворять требованиям неотрицательности и условиям дополняющей нежесткости. Вводим в первое и второе уравнения соответственно искусственные переменные z1 и z2: 4x1 + 2x2 - 4 + Я - v1 + z1 = 0, 2x1 + 4x2 - 6 + 2Я - v2 + z2 = 0. Разрешая первое уравнение относительно z1, а второе уравнение относительно z2, находим целевую функцию F (z) вспомогательной задачи ЛП: F (z) = z1 + z 2 = (-4 x1 - 2 x2 + 4 - X + v1) + + (-2x1 - 4x2 + 6 - 2X + v2) = 10 - 6x1 - 6x2 - 3X + v1 + v2. Составляем вспомогательную задачу ЛП: F(z) = 10 - 6x1 - 6x2 - 3X + v1 + v2 ^ min, 4x1 + 2x2 + X - v1 + z1 = 4, 2 x1 + 4 x2 + 2X - v2 + z2 = 6, x1 + 2 x2 + w = 2, x1, x2, X, v1, v2, w, z1, z2 > 0. Решаем задачу симплекс-методом с учетом условий дополняющей нежесткости. В качестве базисных выберем переменные z1, z2 и w . Таким образом, начальный базис Б0 = {z1, z2, w}. В результате приходим к табл. 3.1. Таблица 3. 1 Базис Своб. член x1 x2 X v1 v2 w z1 z2 z1 4 4 2 1 -1 0 0 1 0 4/4=1 z 2 6 2 4 2 0 -1 0 0 1 6/2=3 w 2 1 2 0 0 0 1 0 0 2/1=2 F 10 6 6 3 -1 -1 0 0 0 Начальное допустимое базисное решение ДБР0= = (zj = 4, z2 = 6, w = 2). ДБР0 не является оптимальным, поскольку в строке целевой функции есть положительные коэффициенты FXi = 6, FX2 = 6, Fx= 3. Согласно условиям дополняющей нежесткости, в базис можно вводить x1, так как v1 = 0, либо x2, так как v2 = 0, но нель- зя вводить Я, так как w > 0 . Находим Б1: Fx > 0 ^ x1 вводим в базис, min J - = 1, - = 3, 2 = 21 = 1 ^ z1 выводим из базиса. 14 2 '1 I 1 Таким образом, Б1 = {x1, z2, w}. В результате приходим к табл. 3.2. i Таблица 3.2 Базис Своб. член x1 x2 Я v1 V2 w Z1 Z2 x1 1 1 1/2 1/4 -1/4 0 0 1/4 0 2 Z2 4 0 3 3/2 1/2 -1 0 -1/2 1 4/3 w 1 0 3/2 -1/4 1/4 0 1 -1/4 0 2/3 F 4 0 3 3/2 1/2 -1 0 -3/2 0 Получили ДБР1 = (x1 = 1, z2 = 4, w = 1). ДБР1 не является оптимальным, поскольку в строке целевой функции есть положи- 31 тельные коэффициенты Fx2 = 3, Fx = и Fv^ = . Согласно условиям дополняющей нежесткости, в базис можно вводить x2, так как v2 = 0, но нельзя вводить Я, так как w > 0, и v1, так как x1 > 0. Находим Б2 : Fx > 0 ^ x2 вводим в базис, . J1 Х 2 _ 4 1 Х 2 21 2 2, , min < ж - f = - ^ w выводим из базиса. ^ 1 3 3 3 J 3 Таким образом, Б2 = {x1, x2, z2} . В результате приходим к табл. 3.3.? Таблица 3.3 Базис Своб. член xi X2 Я V1 V2 w z1 z2 Xi 2/3 1 0 1 /3 -1/3 0 -1/3 1/3 0 X2 2/3 0 1 -1/6 1/6 0 2/3 -1/6 0 z2 2 0 0 2 0 -1 -2 0 1 F 2 0 0 2 0 -1 -2 -1 0 Получили ДБР, 2 ' 2 =2 = 2 1 . ДБР2 не явля v 1 3 3 ется оптимальным, поскольку в строке целевой функции есть положительный коэффициент Fx = 2. Согласно условиям дополняющей нежесткости, в базис можно вводить Я, так как w = 0 . Находим Б3: > 0 ^ Я вводим в базис, {2Х3 2 1 = 2, - = 1 > = 1 ^ z 2 выводим из базиса. 3 Хl 2 J 2 Таким образом, Б3 = {x1, х2,Я}. В результате приходим к табл. 3.4. Таблица 3.4 Базис Своб. член X1 X2 Я V1 V2 w z1 z2 X1 1/3 1 0 0 -1/3 1/6 0 1/3 Ч1/6 X2 5/6 0 1 0 1/6 -1/12 1/2 -1/6 1/12 Окончание табл. 3.4 Я 1 0 0 1 0 -1/2 -1 0 1/2 F 0 0 0 0 0 0 0 -1 -1 Получили ДБР3 = (xj = 1/3, х2 = 5/6, Я = l). ДБР3 является оптимальным решением. Таким образом, вспомогательная задача ЛП решена. Поскольку min F(z) = 0, то оптимальное ДБР вспомога тельной задачи определяет решение х задачи КП. Поэтому полагаем * I 2 х = 1х, (х* = 1/ 3, х2* = 5/6), /ж2 /.,2. _ 1 _ 1 5 Д25 Д1 ^5 Д1 f = f(х ) = 2 - + 2 + 2 4 6 - = -49 3 6 36 3 6 6 / V Ответ: х 21 f = -4-. 6 1, 5 3, 6 . |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ" |
|
|