Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

2.7. Метод Вольфа в квадратичном программировании

Идея метода Вольфа в общих чертах такова: вводятся дополнительные переменные, позволяющие перейти от системы (2.12) к новой системе уравнений, для которой легко указать базисное решение, допустимое с точки зрения требований x*jp*j = 0 (j = 1,...,n) и λ*iq*i = 0 (i = 1,...., m); решается задача линейного программирования с целью обратить эти переменные в нуль (т. е. возвратиться к исходной системе 2.12, но так, чтобы получить при этом оптимальное базисное решение, определяющее X*). В процессе такого перехода все время приходится следить за соблюдением условий x*jp*j = 0 и что и определяет единственное отличие применяемого здесь симплекс-алгоритма от того, который известен в линейном программировании.

Метод Вольфа разработан в двух вариантах. Частный вариант метода позволяет получить решение задачи либо тогда, когда квадратичная форма, входящая в выражение z, является отрицательно определенной (т. е


либо тогда, когда ∀cj = 0 (j = 1,....,n).

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

Введем в (2.12) искусственные неотрицательные переменные yi (i = 1,....,), w'j (j = 1,...., n), w"j (j = 1,...,n) так, что

(2.13)

Для системы (2.13) можно сразу назвать базисное решение, удовлетворяющее условиям: не более n+m переменных отличны от нуля, выполнены требования x*jp*j = 0 (j = 1,....,n), λ*iq*i = 0 (i = 1,....,m). Таким решением является либо x*j = 0, p*j = 0, λi* = 0, q*i = 0, w"j = 0, yi = bi, w'j = cj (при ∀cj>0), либо x*j = 0, p*j = 0, λi* = 0, q*i = 0, w'j = 0, yi = bi, w"j = сj (при ∀cj>0). Если ∀ cj = 0 (j = 1,...,n), то безразлично, какое из названных решений использовать. Важно подчеркнуть, что такие решения не являются допустимыми для (2.12) и могут выступать лишь в качестве исходных в задачах линейного программирования, рассматриваемых ниже.

Первый этап реализации метода Вольфа предусматривает решение следующей вспомогательной задачи: найти


при ограничениях (2.13). Ясно, что минимизация суммы неотрицательных yi (i = 1, ...,m) должна привести к отысканию базисного решения, содержащего нулевые компоненты yi (i = 1,...,m) и удовлетворяющего поэтому "промежуточной" системе уравнений

(2.14)

Теперь можно отбросить все yi (они обращены в нуль), те w'j, которые входят в строки с cj>0, и те w"j, которые входят в строки с cj<0 (нужно оставить в каждой строке либо w'j, либо w"j в зависимости от знака соответствующего cj). Тем самым число переменных группы w сокращается до n, и появляется возможность сделать следующий шаг, направленный на окончательное их исключение.

Второй этап реализации метода Вольфа связан с решением следующей задачи: найти pj, hi, λi, qi,


при ограничениях (2.14). Оно проводится с соблюдением правила: при переходе к очередному базисному решению переменная pj(xj) не должна включаться в базис, если там уже находится xj(pj) (запрещается одновременное пребывание xj и pj с одинаковым номером у в числе переменных, отличных от нуля). Если min z̄̄ = 0, то соответствующее оптимальное базисное решение является одновременно и решением системы (2.12), т. е. всей задачи квадратичного программирования. Этим заканчивается вычислительная процедура, составляющая содержание метода Вольфа.

Выше было замечено, что рассмотренный здесь частный вариант метода Вольфа применим в случае, когда либо ∀cj = 0, либо


Если снять названные ограничения, может оказаться, что из-за требования обеспечить равенства x*jp*j = 0, λ*iq*i = 0 (j = 1,..., n; i = 1,...,m) переход от одного промежуточного базисного решения к другому будет невозможен, хотя z еще не обратится в нуль.

Ниже дан пример, иллюстрирующий возможности метода.

Пример: найти x1, х2→min{z = x1 + 2x2 - 0,5x21 - 0,5x22} при x1,x2≥0, 2x1+3x2≤6, x1+4x2≤5 (нетрудно видеть, что в роли слагаемого


здесь выступает сумма -0,5x21-0,5x22, причем она отрицательно определена в U; следовательно, допустимо применение частного варианта метода Вольфа).

Решение: составляем функцию Лагранжа


и находим


поскольку здесь cj < 0 (j = 1, 2), можно ограничиться введением всего n+m искусственных переменных yi (i = 1, 2), w"j = wj (j = 1, 2), и тогда первая задача линейного программирования принимает вид: найти x1, х2, p1, р2, λ1, λ2, q1, q2, y1, y2, w1, w2 минимизирующие

сумму z̄ = y1+y2 при условиях

(I)

Базисное решение системы (I), удовлетворяющее требованиям xjpj = 0 и λiqi=0, можно назвать сразу: x1 = x2 = 0, p1 = p2 = 0, x1 = x2 = 0, q1 = q2 = 0, y1 = 6, y2 = 5, w1 = 1, w2 = 2; используя его в качестве исходного в решении сформулированной линейной задачи, выразим yi, wj (i = 1,2; j = 1,2) и z через свободные переменные

в соответствии с уравнениями (I), что дает


Если теперь увеличить, например, q1 до 6 (при этом y1 обращается в нуль), то можно получить новое допустимое базисное решение х1 = х2 = 0, р1 = р2 = 0, λ1 = λ2 = 0, y1 = q2 = 0, q1 = 6; y2 = 5, w1 = 1, w2 = 2. Выражения новых связанных переменных и г приобретают вид


Увеличивая теперь q2 до 5, т. е. обращая y2 в нуль, имеем x1 = x2 = = 0, р1 = р2 = 0, λ1 = λ2 = 0, y1 = y2 = 0, q1 = 6, q2 = 5, w1 = 1, w2 = 2, z̄ = y1+y2.

Таким образом, достигнут минимум z̄ (не базисные переменные входят в выражение z̄ с положительными коэффициентами), и этот минимум оказался равным нулю, причем требования xjpj = λiqi = 0 и λiqi = 0 удовлетворены; именно возможность сохранять λi= 0 (i = 1,2) в процессе решения первой линейной задачи (это обеспечивается структурой выражений (I)) позволила избежать трудностей, связанных с необходимостью следить за соблюдением равенств λiqi = 0. Последнее из полученных выше базисных решений, удовлетворяющее всем ограничениям (I) и минимизирующее z̄, построено так, что одновременно удовлетворяет и уравнениям (II), являющимся ограничениями во второй задаче линейного программирования: найти х1, х2, р1, р2, λ1, λ2, q1, q2, w1, w2 → min{z̄̄ = w1 + w2} при

(II)

Отсюда следует


Нетрудно видеть, что добиться уменьшения z̄̄ можно за счет увеличения либо xj, либо λi (j = 1,2; i = 1,2). Выбирая для этого переменную x1 и увеличивая ее до единицы (при этом w1 обращается в нуль), получаем базисное решение w1 = x2 = 0, р1 = р2 = 0, λ1 = λ2 = 0, q1 = 4, q2 = 4, x1 = 1, w2 = 2 и новые выражения


Ясно, что дальнейшее уменьшение z̄̄ должно сопровождаться возрастанием только х2, так как при попытке увеличить λ1 или λ2 нарушаются равенства λiqi = 0; величина х2 может расти до единицы (при этом q2 обращается в нуль), что приводит к решению w2 = q2 = 0, p1 = p2 = 0, λ1 = λ2 = 0, q1 = 1, x1 = 1, x2 = 1, w2 = 1 и выражениям


Теперь увеличивать можно лишь λ2 (поскольку q2 = 0), причем до значения 4/17 (w2 обращается в нуль). Получаемое базисное решение w1 = q2 = 0, p1 = р2 = 0, λ1 = w2 = 0, q1 = 22/17, x1 = 13/17, х2 = 18/17, λ2 = 4/17 оказывается искомым, так как здесь 2 = 0 и удовлетворены все условия (II); таким образом, для исходной задачи квадратичного программирования имеем x*1 = 13/17, х*2 = 18/17.

В рассмотренном примере метод Вольфа выглядит довольно громоздким, однако его преимущество состоит в том, что он сводит процесс решения к последовательному применению симплекс-метода, который удобно реализовать с помощью ЭВМ. Вместе с тем известны и другие методы, основанные на интерпретациях условий Куна-Таккера, но их подробное изучение потребовало бы значительного увеличения объема данной главы.

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

В квадратичном программировании вопрос о двойственности начинает рассматриваться по существу вместе с изучением особенностей функции Φ(Х, Λ). Если нет требования не отрицательности xj (j = 1,...,n) и Φ(Х, Λ) имеет минимум по Λ в точке X°, Λ°, то можно ставить задачу об отыскании совокупности значений λ°i (i = 1,...,m), доставляющих минимум функции Φ(Х, Λ) при условиях

(dΦ/dxj)j = 0 (j = 1,...,n). Другими словами, задача: найти


при


является двойственной по отношению к задаче: найти


при


Обычно условия двойственности записываются здесь в несколько ином виде. Каждая строка-ограничение умножается на соответствующее xj, и после суммирования по номерам j возникает равенство


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


при


Если теперь ввести в указанную выше исходную квадратичную задачу требование ∀xj>0 (j = 1,..,n) и учесть условие (dΦ/dxj)j ≤ 0, то двойственная задача принимает вид: найти


при


Вследствие своей несимметричности двойственные квадратичным задачи (они оказываются линейными относительно Λ) не получили столь широкого распространения, как аналогичные задачи, изученные в § 1.5. Это объясняется, в частности, следующим: если X* есть решение прямой задачи (квадратичной), то компоненты X* совпадают с соответствующими x*j, получаемыми из анализа двойственной (линейной) задачи; обратное утверждение верно лишь тогда, когда


строго отрицательно (положительно) определена в U.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"