Промышленный лизинг Промышленный лизинг  Методички 

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

где ж, v и z - JV-мерные вектора, а г*1 и и2 - то-мерные вектора; координаты всех этих векторов неотрицательны. Система ограничений из р линейных уравнений относительно q неизвестных имеет вид

Ах = В,

(10.12)

2Сж -v + Avt-Avt + Gz =-Р.

G - это диагональная матрица размера N х N, точный вид которой приведен ниже, а искать максимум будем для функции

L(x, V, U1,U2, Z) = - Z\ - Z2 - ... - Zjf.

Если найденный максимум функции L будет равен 0, это будет означать, что

zi = z2 = ... = zN = 0,

а вектора х, v т и = и1 - и2 удовлетворяют системе уравнений (10.11) и условиям (10.7), (10.8). Пока оставим в стороне вопрос о выполнении условия (10.9).

Теперь дадим точное описание матрицы G. Она конструируется таким образом, чтобы было возможно построить исходный g-мерный вектор (ж,v,и1, и2, z) с неотрицательными координатами, удовлетворяющий системе уравнений (10.12). С этого вектора будет начат перебор при решении задачи линейного программирования симплексным методом. Сначала найдем какой-нибудь iV-мерный вектор ж0 с неотрицательными координатами, удовлетворяющий условию

Ах° = В.



Это можно сделать, решив вспомогательную задачу линейного программирования, рассмотренную в конце первой части данного параграфа. Будем предполагать, что у исходного 5-мерного вектора составляющие v = 0 и и1 = и2 = 0. Положим

ti = -Pi-ECiixl i = 1,2.....ЛГ.

Будем считать, что матрица G диагональная, т. е. все элементы, расположенные вне главной диагонали матрицы, равны 0, и обозначим элементы, стоящие на главной диагонали этой матрицы, через Gu, G22, , Gnn- Положим


1, если Sj > 0, - 1, если 8j < 0

при j = 1,2,..., N.

Если определить ЛГ-мерный вектор z° = (z°, z2,.. , z%) при помощи равенства z°- = Sj , то координаты этого вектора неотрицательны, и 5-мерный вектор (x°,v,v},u2, z°) (напомним, что v = 0, и1 = и2 = 0) удовлетворяет системе уравнений (10.12). Все координаты этого g-мерного вектора неотрицательны, а положительных координат у него не больше, чем р. Поэтому соответствующая точка является вершиной многогранного множества задачи линейного программирования, и с этой вершины может быть начат перебор при поиске максимума функции (ж,,!*1,!*2, z) симплексным методом.

Для построенного исходного 5-мерного вектора

(ж°,0,0,0,г°)



выполняется также условие (10.9), поскольку v = 0. В силу неотрицательности координат векторов жиг; условие (10.9) может быть записано в следующей комбинаторной форме:

если Xj > 0, то vj - 0;

если Vj > 0, то Xj = 0;

j - 1,2,..., iV. Поэтому для выполнения условия (10.9) в симплексный метод достаточно добавить следующее ограничение:

если при некотором j, 1 < j < N, в базис входит столбец Dj, то при продолжении перебора вершин в базис не может быть включен столбец Dj+n;

если при некотором j, 1 < j; < N, в базис входит столбец Dj+N-> то при продолжении перебора вершин в базис не может быть включен столбец Dj.

Как и для задач линейного программирования, для задач квадратичного программирования требуется накладывать некоторые условия невырожденности, которые гарантируют сходимость симплексного метода (см., например, [36]). Но практически применение симплексного метода может оказаться успешным и в тех случаях, когда эти условия не выполнены.

3. Метод критических линий для построения эффективных фронтов. В начале §9 сформулирована задача квадратичного программирования, решив которую, можно найти эффективный портфель, соответствующий некоторому значению параметра А. При изменении А от 0 до +оо таким образом описывается весь эффективный фронт. При фиксированном А задача квадратичного программирования может быть решена симплексным или каким-нибудь другим



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