конкретных направлениях. Представим, например, что в рассматриваемой задаче мы налагаем дополнительное ограничение «0,25.
Проблема здесь заключается в том, что мы не знаем заранее, будет ли наше дополнительное ограничение задействовано. Конечно, мы можем разрешить этуЛдилемму, просто решая две задачи, в одной из которых ;мы не имеем ограничений для xj, и, если ответ дает значение Wc > 0,25, тогда то ограничение, на котором мы настаиваем, составляет Wc = 0,25. Однако с двумя подобными ограничениями будут существовать четыре возможности для проверки - ни одно из ограничений не является жестким; первое - жесткое, а второе - нет; второе жесткое, а первое - нет; оба - жесткие. При десяти подобных ограничениях существует 210 = 1024 возможности. Так как избежать этого комбинаторного взрыва нельзя, было бы полезным иметь возможность каким-то образом автоматизировать поиск. Условия Кю-на-Такера предоставляют такой механизм.
Заметьте, что мы теперь не способны гарантировать, что окажемся на границе эффективности, поэтому мы также должны ослабить наши ограничения в виде равенств по поводу полного инвестирования и/или требуемого дохода - мы можем прийти к более рискованному портфелю, но нам не нужно будет использовать все свои деньги, и/или мы можем прийти к большему доходу!
УСЛОВИЯ КЮНА-ТАКЕРА
(Kuhn-Tucker)
Первый шаг в этом анализе - манипулирование неравенствами, так чтобы задача была выражена в стандартной форме
минимизировать Z = flJV)
при = 0 для / в некоторой совокупности Е (т.е.
совокупность ограничений в виде равенств) #Ш) 0 для / в некоторой совокупности / (ограничения в виде неравенств)
Следовательно, для нашей задачи (заметьте, что теперь не существует ограничений в виде равенств)
минимизировать Z= 0,00015 И,2 + 0,00025 w\ + 0,00010 И2 +
0,00010 Wa W4-0,00014 Wa И-0,00006 Wb Wc при \-W-Wb-Wc>Q
0,11 Wa + 0,15 Wb + 0,08 tVc-Q,l 1 0 0,25 - WC>Q
Заметьте, что необходимо представить неравенство Wa + Wb + Wr<\ в стандартной форме, т.е. \-Wa-Wb-Wc> 0.
Снова строится лагранжиан и рассматриваются аналитические методы для нахождения его неограниченного минимума. Однако появляется сложность - не все ограничения в виде неравенств должны действовать. Анализ справляется с этим посредством приведения соответствующих множителей Лагранжа к нулю (существуют обстоятельства исключений, когда множители Лагранжа для действующих выражений могут также быть равны нулю).
Это выражается формально в виде поиска точек Кюна- Такера, т.е. точек, удовлетворяющих условиям Кюна-Такера
8L(W Х\
-. ~ = 0 для каждого значения / (9.33)
&Ш = 0 для i в Е
gffl) 0 для / в / Я, £ 0 для всех /
Я /Ш) = 0 для всех /.
Последнее условие называется условием комплиментарности и говорит о том, что недействующие ограничения имеют нулевой множитель.
И снова для нашей задачи (принимая во внимание третий множитель Лагранжа, относящийся к 0,25- Wc 0)
0,00030 И/ + 0,00010 и/4-0,00014И/.-л,-0,1и2 + Я3 = 0 0,00010 Wa + 0,00050 И-СООООбИ/.-Л, -0,15Я2 + я3 = о 0,00020И/ - 0,000l4We + 0,00006и/-л1-0,08Я2 + Л3 = 0 \-Wtt-Wb-Wc*Q 0,11 Wa + 0,15 Wb + 0,08 fVc-0,l 1 > 0 0,25- Wc> 0 Я,>0 Я2;>0 1 Я3£0 Я ( 0 = 0 для всех /.
Анализ Кюна-Такера предоставляет базу для адаптации линейного программирования к решению этой задачи.
метоп алмиигл-вольФА
(Dantzig-Wolfe)
Установив условия Кюна-Такера, будем искать точку Кюна- Такера, т.е. точку, удовлетворяющую каждому из этих условий. Заметьте, что у нас есть девять линейных ограничений. Следовательно, за исключением комплиментарности и отсутствия целевой функции мы имеем случай линейного программирования. Наша задача заключается в нахождении точки возможного решения для определения оптимальной точки.
Нахождение первой точки возможного решения - это фактически первый шаг симплексного алгоритма. Оно включает в себя создание искусственного решения, в котором все "реальные" переменные имеют нулевые значения, а искусственные переменные щ,..., 09 добавлены по одной к каждому ограничению при значениях, равных соответствующим правым сторонам. В этом случае цель состоит в минимизации суммы ар. Когда решение найдено при этой сумме, равной нулю, мы будем иметь возможное решение нашей задачи.
Таким образом, все, что требуется, - это взять начальную часть симплексного алгоритма и добавить дополнительные ограничения. В нашем примере присутствую! три подобных условия:
по меньшей мере один из Х\ и (Wa + Wb + Wc- 1) должен быть нулем;
по меньшей мере один из Д2 и (0,11» + 0,15И, + 0,08-0,11) должен быть нулем;
по меньшей мере один из Я3 и (0,25- Wc) должен быть нулем.
Эти условия легко проверить. Следовательно, использование до сих пор чисто теоретических условий Кюна-Такера дает возможность преобразовать нашу конкретную задачу квадра-тического программирования в модифицированную задачу линейного программирования.
Результат, полученный для нашей задачи, составляет Wa = 0,266, Wb = 0,405 и Wc = 0,25. Это решение с минимальной дис-