минимизировать 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. Это решение с минимальной дис-

Персией, но заметьте, что не все наши деньги использованы: Wa + Wb + Wc = 0,921. Это не должно быть удивительным, так как наше дополнительное ограничение не дает нам использовать наименее рискованный актив, как этого мы хотим. Данное решение показывает, что возможно достичь нашего целевого дохода при использовании меньшего, чем мы можем себе позволить, объема более рискованных активов.

Если мы настаиваем на инвестировании всех наших денег, тогда можем вернуться к ЛП, меняя Wa + Wb + WX на Wa + + Wb+ Wc = 1. Это приводит к результату Wa - 0,281, Wb = 0,469 и Wc = 0,25. Доход сейчас составляет 0,121, что на 1,1% больше, чем нам было нужно.

Краткое изложение результатов дано в табл. 9.2.

Таблица 9.2

КРАТКИЙ ОБЗОР МЕТОПОВ ВОСХОЖДЕНИЯ НА ХОЛМЫ

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