назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [ 151 ] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176]


151

конкретных направлениях. Представим, например, что в рассматриваемой задаче мы налагаем дополнительное ограничение «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. Это решение с минимальной дис-

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [ 151 ] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176]