элементами подмножества Ω_l ^* , образованного на шаге Y_k – c(x_i ).

Если "i, j; R(x_i )∩R(x_j )= Æ, то G_i =0 и

f(Y_k )=max {Q_i + f[Y_k – c(x_i )]} (2)

iЄI_Y

Для решения интересующей нас задачи опишем простой численный метод, не требующий предварительного определения всех допустимых наборов и основанный на рекуррентных соотношениях (1). Для всех целых Υ = Υ₀ , С по формуле (1) вычисляются величины f(Y_k ) и при этом фиксируются индексы i_Yk ^* , на которых достигаются максимумы в (1). Искомый вектор Ω формируется последовательно включением в набор параметра i_Yk и подмножества Ω_l ^* , зафиксированного на шаге Y_k – c(x_i ). При этом, если Y_k Є Ω_l *, то на данном шаге этот параметр исключается из рассмотрения, так как каждый параметр может включаться в набор не более одного раза. Если на некотором ν-м шаге окажется, что f(Y_ν )< f(Y_{ν -1} ), то в качестве Ω_ν * принимается подмножество Ω_{ν -1} * и фиксируется параметр i_{Y ν -1} , причем за f(Y_ν )< принимается значение f(Y_{ν -1} ). Заметим, что если в задаче P(Ω)=max при

∑x_i ·c(x_i )≤C

iЄΩ

принять более жесткое ограничение, а именно ∑c(x_i )=C, то последнее не допустимо, iЄΩ так как в этом случае maxf(Y_k ) может быть меньше maxf(Y_{k -1} ) из-за того, что он достигается на другом подмножестве параметров.

Общая сложность метода, очевидно, φ(n) ≤ c(n+1), т.е. экспоненциальная функция при переборе заменена линейной функцией. При этом для запоминания промежуточных значений необходимо k≤2c ячеек памяти. Если в качестве максимизируемого критерия использовать P(Ω)=∏(1-p_i )/∏(1-p_i ), то необходимо решить задачу динамического iЄR(S) iЄR(Ω) программирования с мультипликативным критерием. Для этого достаточно прологарифмировать это выражение и обозначить

V=lgP(Ω)=lgР₀ -∑lg(1-p_i ). (3)

iЄR(Ω)

Так как выражение, стоящее под знаком ∑ в (3), отрицательно, то, V= V_max тогда, когда максимальна величина суммы, т.е. в этом случае получим новую целевую функцию

V=∑ν_i , где ν_i =lg (1-p_i ),

iЄR(Ω)

обладающую свойством аддитивности и обращающуюся в максимум одновременно с P(Ω).

1.2 Практическая часть

Ручной счёт

Данные для расчета:

С≤16

Таблица 1

N	1	2	3	4	5	6	7	8	9	10
Qi	0.17	0.03	0.15	0.09	0.13	0.08	0.07	0.02	0.06	0.04
с(xi)	5	1	4	2	6	3	2	3	1	1

Для удобства расчетов проранжируем таблицу1 следующим образом:

Таблица 2

N	9	10	2	4	7	6	8	3	1	5
Qi	0.06	0.04	0.03	0.09	0.07	0.08	0.02	0.15	0.17	0.13
с(xi)	1	1	1	2	2	3	3	4	5	6

Вычисления сведем в таблицу 3:

Таблица 3

Yk	f(Yk)	iYk	Ωl*
1	0,06	9	9
2	0,1	10	9,10
3	0,15	4	4,9
4	0,19	4	4,10,9
5	0,22	7	7,4,9
6	0,26	7	7,4,10,9
7	0,3	3	3,4,9
8	0,34	3	3,4,10,9
9	0,37	3	3,7,4,9
10	0,41	7	7,3,4,10,9
11	0,44	2	2,7,3,4,10,9
12	0,47	1	1,3,4,9
13	0,51	1	1,3,4,10,9
14	0,54	2	2,1,3,4,10,9
15	0,58	7	7,1,3,4,10,9
16	0,61	1	1,2,7,3,4,10,9

Оптимальный набор включает параметры Ω^* = {1,2,7,3,4,10,9} при этом

P(Ω) = 0,61+0,16 = 0,77 и С = 16.

Листинг программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ToolWin, ComCtrls, mdCONTROLS, Grids, StdCtrls, ExtCtrls, Unit2,

Buttons;

type