Оптимизация при ограничении числа проектных переменных

Для производственных, транспортных, вычислительных и других систем важно эффективное функционирование подсистем планирования и принятия решений. Обычно на вход подобных подсистем поступают сведения о множестве ресурсов, таких как люди, материалы, оборудование, устройства, капитал, время, и множестве операций (поручений, требований), которые с помощью данных ресурсов должны быть выполнены; их выходом служит распределение ресурсов по операциям. Под улучшением характеристик рассматриваемых подсистем понимают повышение эффективности использования ресурсов, а именно уменьшение потребности в ресурсах без соответствующего изменения в объёме, стоимости и прибыли или увеличение прибыли при сохранении прежней потребности в ресурсах [1-3].

В статье представлен алгоритм решения одного класса задач комбинаторной оптимизации, возникающих при решении дискретных задач линейного и нелинейного программирования с концептуально важным дополнительным ограничением на число используемых в решении переменных [4-10]. Алгоритм является глубокой модификацией метода динамиче- ского программирования [11, 12]. В отличие от классического метода определения функции Беллмана, в предложенном алгоритме на первом этапе находятся экстремальные значения целевой функции при использовании только одной переменной, определяемой в процессе поиска экстремума на каждом допустимом значении ресурсов. На последующих этапах используется рекурсия поиска экстремальных значений целевой функции путём пошагового увеличения числа переменных, используемых в решении.

Большинство задач комбинаторной оптимизации являются NP-трудными [8, 13, 14], что обусловливает сложность построения эффективных алгоритмов их решения. Для многих задач хорошо известные классические методы решения (динамическое программирование, методы ветвей и границ, «жадные» алгоритмы) оказываются неэффективными, что обусловливает необходимость разработки новых методов.

1 Постановка и решение задачи линейного программирования

Большое число задач можно сформулировать в терминах линейного программирования [4-6, 15]. Многие из них приобретают новое прикладное значение, если рассматривать задачу отыскания экстремума линейной функции n переменных при использовании в решении d переменных, где d < n. Математически задача формулируется так: найти max (c 1 x 1 + — + cnxn)(1)

при ограничениях a 11 x 1 + — + a 1 nxn < b* 1

• -        *(2)

• a m 1 ^x 1 ⁺ — ⁺ a mn x n <  b m

a ji > 0, i = 1,..., n , j = 1,..., m ,

Z n=1 xi< d *,(3)

где

x i >  0, d * <  n , x i =

1, x i >  0, 0, x i = 0.

От традиционной постановки задачи линейного программирования [4, 5] рассматриваемую задачу отличает наличие ограничений (3), которые определяют задачу выбора не более d переменных (процессов), между которыми необходимо разделить ограниченные ресурсы, определяемые ограничениями (2) при условии нахождения максимума целевой функции (1).

Одним из примеров такого класса задач является выбор d типов изделий для производства. Пусть для создания некоторого типа изделий требуется m видов ресурсов и по условиям производства можно выпускать d типов изделий, но при этом есть возможность выбора типов из n возможных ( n >  d ). Расход ресурса номера j при единичном выпуске изделия типа i обозначен через a ji . Через c i обозначен доход от продажи единицы i -го типа продукции, а через x i - количество продукции i -го типа. Зависимость расходов и доходов от количества выпускаемых изделий i -го типа принята линейной, а производству доступно b j единиц j -го ресурса. В этом случае задача выбора оптимальной номенклатуры типов изделий и объёмов их выпуска имеет вид (1)-(3), если требуется максимизировать доход.

При d = n задача сводится к обычной задаче линейного программирования [4-6].

Требование целочисленности решения не несёт принципиальных изменений предлагаемого подхода, считается, что переменные x i могут принимать только целые значения, когда это необходимо.

Используя приём динамического программирования [13, 14], рассматривается множество задач типа (1)-(3) при всевозможных значениях b j и d (0 <  b j <  b j , j = 1,..., m ; 1 <  d <  d ).

Тогда при d = 1 решается задача отыскания максимума (1) по одной переменной при всех 0 <  b j <  b j , j = 1,..., m , что можно записать так:

f X b 1 ,..., b_m ) = max i < i < n C i X i                                    (4)

при ограничениях для каждого выбираемого значения x i и всевозможных значений b j

X i >  0, 0 <  b j <  b *j , j = 1,..., m.                                    (5)

На практике каждое b j , как правило, принимает конечное множество значений, образующее некоторую e j -сеть на [0, b j ].

Найденные значения максимумов при использовании в решении одной переменной из n при всевозможных допустимых значениях выделяемых ресурсов Abi,..., Abm обозначены f.(Abi,..., Abm),                                              (6)

где 0 <  A b j <  b j , 0 <  b j <  b j , j = 1,..., m . Здесь A b j , j = 1,..., m - это всевозможные значения ресурсов, на которых найдены максимумы в соответствии с (4) и (5). Необходимо заметить, что для каждого набора A b j , j = 1,..., m максимальное значение f XA b ₁,..., A b_m ) может давать любая из n возможных переменных.

Для получения максимума в (1) при использовании в решении не более двух переменных, т.е. при d = 2, необходимо найти максимальные значения от одной переменной для всех возможных допустимых значений ресурса и просуммировать их с максимальными значениями целевой функции также от одной переменной, найденных на остающихся после выделения первой переменной ресурсах. Доказательство этого утверждения может быть получено следующим образом. В рамках динамического подхода рекуррентное выражение для поиска максимума при использовании двух переменных запишется так:

f . ( b 1 ,..., b m ) = max [ c i X i + f X b 1 - A b 1 ,..., b m - A b m )], 1 <  i <  n ,                   (7)

при следующих ограничениях для каждого возможного значения x i и значений b j :

a ji X i < A b j , 0 <  A b j <  b j , j = 1,..., m .                                 (8)

В (7) f X b ₁ - A b ₁,..., b_m - A b_m ) - найденное на первом шаге алгоритма максимальное значение функции от одной переменной на конкретном значении выделенных ресурсов, которое складывается со значением c i x i , где i выбирается из множества {1,..., n } и определяется так же на конкретном (в момент выбора) наборе значений ресурсов A b j , j = 1,..., m .

Для получения максимума двух слагаемых, одно из которых имеет фиксированное значение при выбранных на текущий момент значениях A b j , j = 1,..., m , нужно выбрать переменную с номером i , которая даст максимальное значение c i X i на выделенном ресурсе A b j , j = 1,..., m . На первом шаге алгоритма такое значение уже было определено и записано в (6). Вариант с возможным совпадением номеров переменных даёт значения f X b ₁ - A b ₁,..., b_m -A b_m ) и f XA b ₁,..., A b_m ). Следовательно, выражения (7) и (8) можно записать так:

f X b 1 ,..., b_m ) = max [f (Ab 1 ,..., A b m ) + f X b 1 - A b 1 ,..., b m - A b m )],                 (9)

при выполнении ограничений:

0 <  A b j <  b j , 0 <  b j <  b *j , j = 1,..., m .

Максимальное значение целевой функции не более чем от двух переменных на ресурсах b ₁,..., b_m получено перебором сумм максимальных значений двух функций, каждая из которых использует только одну из n возможных переменных, определённых на первом шаге алгоритма для всевозможных значений ресурсов.

Если вернуться к исходным обозначениям, выражение (9) после вычисления f₂ ( b ₁,..., b_m ) можно записать так:

f.(b 1,..., bm) = max (CkXk + cxi), где максимальное значение суммы получено после выполнения полного перебора вариантов возможных распределений ресурсов между двумя переменными. При этом на каждом варианте распределения ресурса выбирались две переменные, дающие максимальное значение целевой функции на выделенных им ресурсах. Найденные номера переменных, их значения и соответствующе им ресурсы обозначены так: номера - к и l,значения переменных - хк и xl, значение целевой функции - ckxk + cx, ограничения - ajkxk < Abj, ajlxl < bj - Abj, j = 1,..., m.

Можно предположить, что существуют переменные с номерами у и z со значениями х_у и x z , которые на тех же выделенных ресурсах дают значение больше значения f₂ ( b 1 ,..., b_m ). Это означает, что либо на ресурсе A b j , либо на ресурсе b j - A b j (j' = 1,..., m ) выполняется хотя бы одно из неравенств

С у Х у >  С к Х к , C z X z > C i X i , что невозможно в силу определения значений c_kx_k и cx i как максимальных на этих ресурсах.

Аналогичные рассуждения можно провести для любого возможного распределения ресурсов между двумя любыми переменными. Это означает, что если в исходной постановке задачи не добавляется условие (3) выбора переменных, участвующих в решении задачи, т.е. если предложенным методом решается классическая задача линейного программирования с двумя переменными в целевой функции, то будет найдено глобальное оптимальное решение.

Таким образом, доказано, что вычисленное значение f₂ ( b 1 ,..., b_m ) является глобальным максимумом на всех допустимых значениях b 1 ,..., b_m .

Продолжая процесс, можно получить рекуррентное уравнение относительно числа используемых в решении переменных:

f d ( b 1 ,..., b m ) = max f , (A b 1 ,..., A b m ) + f d -i ( b 1 - A b 1 ,..., b m - A b m )],               (10)

для всех 0 <  A b j <  b j, , 0 <  b j <  b * , j = 1,..., m , d = 2,..., d* .

Используя метод математической индукции и свойства линейных операций, можно доказать, что для линейной целевой функции и линейных ограничений значение f_d ( b 1 ,..., b_m ) является глобальным максимумом для всех допустимых b 1 ,..., b m .

При использовании в решении только одной переменной ( d = 1) значения f _( b 1 ,..., b_m ) являются максимальными для допустимых значений b 1 ,..., b_m (в том числе и для значений A b 1 ,..., A b_m , используемых в рекурсивном выражении (10)). Вычисленное значение f₂ ( b 1 ,..., b_m ) является глобальным максимумом на всех допустимых значениях b 1 ,..., b_m . Можно предположить, что выражение (10) даёт максимальное значение при использовании в решении не более ( d - 1) переменных. Оно даёт максимальное значение и при использовании в решении не более d переменных. Действительно, в выражении (10) значения f d _- 1 по допущению являются максимальными на всех допустимых значениях ресурсов, а значения f , (A b 1 ,..., A b_m ) являются максимальными в силу алгоритма их вычисления. Пусть значение максимума f_d ( b 1 ,..., b_m ) получено суммированием

A 1(Ab 1,..., Abm) + fd-1(b 1 - Ab 1,..., bm - Abm), где A 1(Ab 1,..., Abm) - некоторое значение целевой функции при использовании в решении какой-то одной переменной из n возможных. По определению значение f.(Ab 1,..., Abm) является максимальным на ресурсе Ab 1,..., Abm. Это означает, что A 1(Ab 1,..., Abm) = f ,(Ab 1,..., Abm), иначе значение максимума fd(b 1,..., bm) не было бы получено. Таким образом, доказано, что вычисленное значение fd(b 1,..., bm) является глобальным максимумом на всех допустимых значениях b1,..., bm.

Если на любом шаге d значение fd(b 1,..., bm) получается при повторном использовании хотя бы одной из n переменных (т.е., некоторая переменная с номером i входит в оба слагаемых соотношения (10)), то fa(b 1,..., bm) = fd-1( b 1,..., bm).                                        (11)

Действительно, пусть fa(b 1,..., bm) = max [f,d(Ab 1d,..., Abm) + fa-1(b 1 - Ab 1,..., bm - Abm)], 0 < Abj < bj, а число использованных переменных для получения fd не увеличилось. Это означает, что некоторая переменная xi, которой соответствует f.d(Ab 1d,..., Abmd), была использована на одном из предыдущих шагов при получении fd—1(b 1 - Ab 1,..., bm - Abm). Согласно (4)-(10), значение целевой функции формируется таким образом, что будет справедливо выражение fd(b 1,..., bm) = f1d(Ab 1d,..., Abmd) + f1 k(Ab 1 k,..., Abmk) + fd-2(b 1 - Ab 1d - Ab 1 k,..., bm - Abmd - Abmk), где f_d(Ab 1d,..., Abmd) и f.k(Ab 1k,..., Abmk) по предположению, получены при использовании одной и той же переменной 1 со значениями xid и xik.

В силу линейности функций и ограничений можно показать, что для xid и xik справедливо равенство f1d(Ab 1d,..., Abm) + f.k(Ab 1k,..., Abmk) = f(Ab 1d + Ab 1k,..., Abm + Abmk). Действительно, это соответствует свойству линейных операций cxf + cxk = cixi, где xi = xid + xik, и преобразованию ограничений для этой переменой ajxd < Abjd, ajix^ < Abk, j = 1,..., m, в ограничения               ajixd + ajixik < Abjd + Abjk, j = 1,..., m, или, что то же самое, в ограничения ajiXi < Abjd + Abjk, j = 1,..., m, где значения Abjd + Abjk для переменной с номером i рассмотрены на первом шаге алгоритма, и соответствующее значение cixi использовано для формирования значения fd-1(b 1,..., bm) на шаге (d - 1). Отсюда следует, что найденное повторное включение переменной 1 в целевую функцию можно записать так

C i ( X i^d + C i X ik ) + f d -2 ( b 1 - A b 1 ^d - A b 1 ^k ,..., b m - A b m^d - A b m^k ) =

= C i X i + f d -2 ( b 1 - A b 1 i ,..., b m - A b m ) = f d -1 ( b 1 ,..., b m ).

Здесь A b 1 ¹ = A b 1 ^d + A b 1 ^k ,..., A b m = A b_m ^d + A b mk ; c i x i = c i ( x i^d + x ik ) - линейные ограничения для x i^d и x ik складываются и дают ограничение для x i .

Таким образом, показано отсутствие нарушения структуры целевой функции при попытке повторного включения в решение уже использованной переменной. Поэтому если на шаге d значение f_d ( b 1 ,..., b_m ) увеличилось, то оно получено при использовании d переменных, так как в противном случае это увеличение произошло бы на одном из предыдущих шагов (имеется в виду минимальное число используемых переменных).

Для определения фактических номеров, числа и значений переменных, на которых достигается f_d ( b 1 ,..., b_m ), можно использовать соотношение (10), двигаясь по шагам в обратном направлении и определяя:

• ■    на шаге d - значение f _ ^d (A b 1 ^d ,..., A b_m ^d ), равное f . (A b 1 ,..., A b_m ) в (10) при получении f_d ( b 1 ,..., b_m ), и соответствующие номер и значение переменной;

• ■    на шаге ( d - 1) - значение f 1 ^{d -1}(A b 1 ^{d -1},..., A b_m ^{d -1}), дающее f_d -1 ( b 1 - A b 1 ^d ,..., b_m - A b_m ^d ) и соответствующие номер и значение переменной.

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

В классическом представлении функция Беллмана определяется последовательно по пронумерованным переменным [11]. Когда ресурс выделяется переменной 1, то предполагается, что оставшийся ресурс оптимально распределён по уже рассмотренным (1 - 1) упорядоченным по номерам переменным. Задача будет решена, когда будут получены результаты для последней переменной в списке. В результате ограничение на число используемых в решении переменных не будет учтено. Чтобы его учесть при использовании классического рекуррентного уравнения Беллмана [13] придётся решить Cd задач, последовательно перебирая варианты наборов d* переменных из n возможных, и выбрать из этих решений наилучшее. Такой же подход (с перебором вариантов) можно использовать и при применении других традиционных методов решения задач линейного программирования с дополнительным ограничением на число используемых переменных.

Для иллюстрации работы предложенного метода рассмотрена задача:

найти max ( x 1 + 4 x ₂ + 6 x ₃ + 9 x ₄)

при ограничениях x 1 + 3 x 2 + 5 x 3 + 7x 4 < 10,

1, x i >  0, 0, x i = 0.

x i e {0, 1, 2,...}, i = 1,..., 4; £ ⁴ _{= 1} x i <  2,, x i =

Данные, получаемые в результате вычислений по (4)-(10) для возможных значений b 1 = 1, 2,..., 10, объединены в таблице 1. В примере используется только один тип ресурса, который обозначен как b 1 .

На первом шаге получены значения fXb 1) = max1 < i < 4 cxi для всех b 1 при выполнении ограничений для каждого возможного значения ресурса. Результаты вычислений f1 показаны во второй строке таблице. Каждый результат в отдельном столбце соответствует:

• ■    значению ограничения на ресурс, показанному в первой строке таблицы;

• ■    номеру i выбранной по алгоритму вычисления f . ( b 1 ) переменной, показанному в третьей строке;

• ■    значению переменной x i , вычисленному при условии выполнения ограничения на ресурс, показанному в четвёртой строке.

На втором шаге алгоритма для каждого возможного значения ресурса вычисляется значение целевой функции от двух переменных по формуле (10), при этом используются результаты вычислений первого шага:

f _;( b 1 ) = max f . (A b 1 ) + f X b 1 - A b 1 )], 0 <  A b 1 <  b 1 , при ax i < A b 1 ; i = 1, 2,...,4; b 1 <  b * 1 , b * 1 = 10; b 1 e {1, 2,..., 10}.

Для ресурса, принимающего значения от 1 до 3, значения целевой функции получаются при использовании в решении только одной переменной и совпадают с результатами первого шага. Эти результаты показаны в пятой строке таблицы 1, обозначенной как « f = f² + f '».

При значении ресурса b 1 = 4 после просмотра возможных значений f XA b 1 ) при A b 1 e {1, 2, 3, 4} получено максимальное значение f₂ (4) = f (1) + f 1 (4 - 1) = 1 + 4 = 5 при x 1 = 1, x ₂ = 1. Эти результаты показаны в строках 5-8 таблицы 1 и столбце со значением b 1 = 4. В строке, обозначенной «f² + f '», показаны значения f 1 (A b 1 ) + f 1 ( b 1 - A b 1 ), на которых получен максимум; в строке, обозначенной « i, j », показаны номера переменных, формирующих оптимальное значение, а в строке 8, обозначенной как «x i , X j », значения соответствующих переменных.

При значении ресурса b 1 = 5 на втором шаге получено оптимальное значение при двух вариантах использования ресурса. Первым получается значение целевой функции равное 6 при f _( A b 1 = 0) = 0 и f 1 (5 - 0) = 6 при x ₃ = 1. Этот же результат получается при f _( A b 1 = 2) = 2 и f 1 (5 - 2) = 4 при x 1 = 2, x ₂ = 1:

f 2 (5) = f . (0) + f , (5 - 0) = 6 = f , (2) + f , (5 - 2) = 2 + 4 = 6.

Так как в задаче не требуется обязательного использования двух переменных в решении, то в таблице записан первый результат. Продолжая процесс для значения ресурса b . = 10, значение целевой функции получается равное 13, когда f₂ (10) = f . (1) + f . (9) = 13 при x . = 1, x ₂ = 3.

В данном примере вычисление значений f₂ ( b . ) для всех возможных значений b 1 е {1, 2,..., 10} было избыточным. Достаточно было сразу рассмотреть вариант с b . = 10, так как третьего шага в случае поиска оптимального решения при использовании трёх переменных нет. Если бы в задаче было условие использования в решении не менее трёх переменных из четырёх возможных, то в рекуррентных выражениях для поиска f₃ ( b 1 ) следовало бы использовать f₂ ( b 1 ) для всех возможных значений b 1 , хотя f₃ ( b 1 ) опять можно было вычислять только для b 1 = 10 и A b 1 е {1, 2,..., 10}. Такое правило можно использовать и в общем случае на последнем шаге алгоритма.

Из таблицы 1 видно, что при использовании в решении одной переменной максимум целевой функции равен 12 при х ₂ = 3, а максимум при использовании в решении двух переменных равен 13 при х 1 = 1, х ₂ = 3.

Таблица 1 - Данные, получаемые при решении примера:

возможные значения ресурса b 1, соответствующие им значения целевой функции от одной используемой переменной f1, значения номеров используемой переменной i, значения переменной xi, значения целевой функции от не более двух используемых переменных f2 = f2 + f11, значения f2 + f11 при получении f2, i, j - значения номеров используемых переменных i, j для, соответственно, f2 и f11, значения переменных xi, х2 в f2 = f2 + f11

1	b 1	1		2		3		4		5		6		7		8		9		10
2	f	1		2		4		4		6		8		9		9		12		12
3	i	1		1		2		2		3		2		4		4		2		2
4	х i	1		2		1		1		1		2		1		1		3		3
5	f 2 = f 2 + f?	1		2		4		5		6		8		9		10		12		13
6	f2 + f?	0 + 1 1		0+2 2		0+4 4		1+4 4		0+6 6		0+8 8		0+9 9		1+9 9		0+12 12		1+12
7	i,j		1		1		2	1	2		3		2		4	1	4		2	1	2
8	X i , X j	0	1	0	2	0	1	1	1	0	1	0	2	0	1	1	1	0	3	1	3

При использовании рекуррентного соотношения (10) для определения последовательности {f d ( b 1 ,..., b m )} в общем случае считается, что b j может принимать значения 0, A j , 2A j ,..., K j A j = b j , j = 1,..., m . Тогда в памяти вычислительной среды необходимо хранить минимум П m ₌₁( K j + 1) значений f d _-1( b 1 ,..., b_m ) для последующего получения f d ( b 1 ,..., b_m ).

Объём вычислений в общем случае можно оценить величиной O ( n + d * х K m ), где n - общее число переменных, d * - ограничение на число переменных в решении, K - максимальное количество точек дискретизации среди всех ограничений, m - количество ограничений. Вычисления просты и используют результаты предыдущих шагов. При использовании для решения классического рекуррентного уравнения Беллмана объём вычислений оценивается как ^* *                           *

O ( C d х d х K ). При d = n получаются оценки O ( n + n х K m ) и O( n х K m ) соответственно. Таким образом, вычисления на основе уравнения Беллмана [11, 12] немного эффективнее, если в решении можно использовать все описанные в задаче переменные.

При решении задачи с большим числом ограничений m и больших числах K j может потребоваться большой объём памяти, либо нахождение решения может быть достаточно долгим. В то же время число переменных n и d мало влияют на эффективность рассматриваемого алгоритма, поэтому возможности метода весьма широки при решении дискретных задач линейного программирования с большим числом переменных и с малым числом ограничений. Кроме того, количество точек дискретизации во многих задачах может выбираться кратно наибольшему общему делителю коэффициентов в каждом конкретном ограничении j , что может существенно уменьшить величины K j , j = 1,., m.

2 Нелинейный целевой функционал

Пусть вместо (1) рассматривается задача вида: найти max [ci(xi) + .. + Cn(x„)]                                   (12)

при ограничениях (2-3).

Используя идею динамического программирования, можно рассматривать множество задач типа (1)-(3), при всевозможных значениях b j и d (0 <  b j <  b j , j = 1,..., m ; 1 <  d <  d ), но при этом имея ввиду, что функции c i ( x i ) нелинейные.

При d = 1 решается задача отыскания максимума (12) при использовании одной из n переменных при всех 0 <  b j <  b j , j = 1,..., m :

f _ ( b 1 ,..., b m ) = max 1 <  i <  n C i ( x , )                                    (13)

при ограничениях (2)-(3).

Далее используется рекуррентное соотношение (10).

По определению значение f X b ₁,..., b_m ) является максимумом целевой функции при распределении ресурсов b ₁,..., b_m для одной из n переменных.

Пусть хотя бы одна функция c i ( x i ) удовлетворяет следующему условию для значений аргумента x i равных x и у :

d ( x ) + C i (у ) >  C i ( x + y).                                    (14)

Тогда при поиске максимума по соотношениям (13) и (10) может возникнуть ситуация, когда вычисленное по (10) значение f_d ( b ₁,..., b_m ) будет получено за счёт «постепенной» выдачи ресурсов i -му процессу. Однако, при выполнении условия (14) фактическое значение f_d ( b ₁,..., b_m ) не будет максимальным значением на выделенных ресурсах. Чтобы избежать этого, следует ограничиться задачами, в которых для всех i е { 1,., n } выполняется условие:

d ( x ) + C i ( у ) <  C i ( x + y).                                    (15)

При d = 1 значение f d ( b ₁,..., b_m ) максимально по определению. Пусть при условии (15) выражение (10) даёт максимальное значение функционала при d = к . Можно показать, что при d = к + 1 соотношение (10) даст фактическое максимальное значение для всех 0 <  b j <  b j , j = 1,..., m .

Линейность ограничений и условие (15) исключают «повторное» распределение ресурса i -му процессу. Следовательно, в (10) при d = к + 1 достигается искомый максимум, а из метода математической индукции следует, что максимум достигается при любом d <  n .

В качестве примера рассмотрен поиск максимума целевой функции вида ( x 1 )² + 2( x 2 )⁴ + 3( x з )² при    x 1 + 2 x 2 + 4 x 3 <  5,

1, x i >  0, 0, x i = 0.

x i е {0, 1, 2,.}, i = 1, 2, 3; £ 3 = ₁ x i <  2,, x =

Следуя (13) и (10), вычисляются f 1 (1) = 1, f 1 (2) = 4, f 1 (3) = 9, f 1 (4) = 32, f 1 (5) = 32.

Далее, так как условие (15) выполняется для всех i , получаются согласно (10) f 2 (1) = 1, f 2 (2) = 4, f 2 (3) = 9, f 2 (4) = 32, f 2 (5) = 33.

Важно отметить, что, например, все функции вида a0 + a1x + a2(x2)2 +…+ an(xn)n, где ai ≥ 0, x ≥ 0, n > 0 удовлетворяют условию (15), т.е. класс задач, к которым применим разработанный метод, достаточно широк.

Заключение

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

Обоснована оценка вычислительной сложности решения поставленных задач. Приведено сравнение описываемого подхода с классическими методами решения рассматриваемых задач. Показано, что классические методы можно применять путём сведения исходной постановки задачи к C nd задачам без дополнительных ограничений на число используемых в решении процессов, где d * - число процессов в решении, выбираемых из n возможных. После решения C nd задач необходимо выбрать из них оптимальное.

Рассмотренные в статье математические постановки задач и их решения имеют ряд актуальных практических приложений. Например, можно сформулировать задачу для оптимального размещения ограниченной номенклатуры грузов на ограниченных складских площадях [2], или задачу выбора ограниченного числа типов ракет-носителей из возможного набора типов для оптимального выполнения программ космических исследований [16] и другие подобные [17].

При решении практических задач приходится сталкиваться с многокритериальной оптимизацией. Если многокритериальный функционал качества каким-либо способом приводится к одному критерию [18-21], то затем можно применять предложенный метод решения.