Задание 9. Решить задачу, добавив условие целочисленности переменных

Решить задачу, добавив условие целочисленности переменных. Если при решении задачи (4.2) решение оказалось целочисленным, то задание скорректировать у преподавателя.

Вариант	З а д а н и е	Вариант	З а д а н и е
1	-3 x1 - 2 x2 - x3 --> min x1 + x2 + 2x3 = 1 x1 - x2 + x3 = 1 x i ≥ 0, i=1, 2, 3	16	x1 - x2 + 4 x3 --> max x1 + 2x2 - 3 x3 =3 2 x1 - x2 + 4 x3 = 1 x i ≥ 0, i=1, 2, 3
2	2 x1 +3 x2 +5 x3 --> max x1 + x2 + x3 ≤ 1 x1 - x2 + x3 = 1 x i ≥ 0, i=1, 2, 3	17	- x1 + 4 x2 - x3 --> max x1 + 2 x2 + x3 =3 2x1 + x2 - x3 = 0 x i ≥ 0, i=1, 2, 3
3	x1 - 4 x2 +5 x3 --> max 2x1 + x2 +2 x3 = 4 x1 - x2 - x3 ≤ 2 x i ≥ 0, i=1, 2, 3	18	x1 - 2 x2 - 4 x3 --> min x1 - x2 - 2 x3 ≥ 1 x1 + x2 + x3 ≤ 3 x i ≥ 0, i=1, 2, 3
4	x1 - 4 x2 +5 x3 --> max 2x1 + x2 + x3 ≤ 4 x1 - x2 - x3 = 2 x i ≥ 0, i=1, 2, 3	19	4x1 + x2 + 5x3 --> max x2 + x3 ≤ 2 3x1 + 2 x2 - x3 ≤ 1 x i ≥ 0, i=1, 2, 3
5	- x1 + 4 x2 - 5x3 --> min 2x1 + x2 + x3 ≤ 4 x1 - x2 - x3 ≥ 2 x i ≥ 0, i=1, 2, 3	20	x1 + x2 + x3 --> max x1 - x2 + x3 =1 3x1 + 2 x2 +2 x3 =17 x i ≥ 0, i=1, 3
6	3x1 - 2 x2 - 2x3 -3x4--> max x1 - x2 + x3 + x4 = 1 x1 - x2 - x3 - x4 =1 x i ≥ 0, i=1, 2, 3	21	x1 + 4 x2 - 7 x3 --> max 2 x1 - 2 x2 + 14 x3 ≥ 2 x1 - 2 x2 + 10 x3 = 0 x i ≥ 0, i=1, 2, 3
7	x1 + x2 + x3 --> min x1 + x2 +x3 ≥ 1 x1 - x2 + x3 ≤ 1 x i ≥ 0, i=1, 2, 3	22	8 x1 + 2 x2 - 3 x3 --> max x1 + x2 + x3 = 5 3 x1 + x2 - x3 = - 3 x i ≥ 0, i=1, 2, 3
8	x1 - x2 - x3 --> max 10 x1 + x3 ≤ 10 10x2 + x3 ≥ 10 x i ≥ 0, i=1, 2, 3	23	3 x1 + 2 x2 + 10 x3 --> min x1 +10 x2 + 11 x3 =31 x1 - x2 = - 2 x i ≥ 0, i=1, 2, 3
9	x1 + x2 + 2 x3 --> min 10 x1 + x3 ≥ 10 10x2 + x3 ≤ 10 x i ≥ 10, i=1, 2, 3	24	2 x1 + x2 + x3 + x4 --> max x1 - x2 + x3 - x4 ≤ 2 x1 + x3 - x4 ≥ 1 x i ≥ 0, i=1, 2, 3, 4
10	-x1 - x2 -2 x3 --> max 10 x1 + x3 ≥ 1 10x2 + x3 ≤ 1 x i ≥ 0, i=1, 2, 3	25	2 x1 + x2 + x3 + 2x4--> max - x1 - x2 + 4 x3 + x4 = 2 x1 - x2 - 2 x3 ≤ 2 x i ≥ 0, i=1, 2, 3, 4
11	x1 + x2 + x3 + x4 --> max x1 + x2 +3x3 + 4x4 = 12 x1 - x2 + x3 - x4 =2 x i ≥ 0, i=1, 2, 3, 4	26	x1 + x2 +2 x4 --> max x1 + x3 + x4 =4 x1 - 2 x2 - 3x3 + x4 = 0 x i ≥ 0, i=1, 2, 3, 4
12	x1 +2x2 - x3 - x4 -x5 --> min x1 + x2 +2x3 -x4 ≤ 2 x1+ x2 + 3x3 + 4x4 = 12 x i ≥ 0, i=1, 2, 3, 4, 5	27	x1 - x2 + x3 + 2 x4 --> max x1 + x2 + x3 + 2x4 = 7 x2+ x3 + x4 = 5 x i ≥ 0, i=1, 2, 3, 4
13	x3 + x4 --> max x1 + x2 + 3x3 + 4x4 = 12 x1 + x2 + x3 - x4 ≤ 2 x i ≥ 0, i=1, 2, 3, 4	28	- x1 - x2 - x3 -5x4 --> min x1 - x2 - x4 £ 3 2 x1 + x2 + x3 -x4 = 5 x i ≥ 0, i=1, 2, 3, 4
14	-x1 - x2 + x3 --> min x1 + x2 +x3 + x4 = 4 x1 - 3x2 +x3 - x4 = - 2 x i ≥ 0, i=1, 2, 3, 4	29	x1 + x2 - x3 --> max x1 + x3 =2 x1 + 0, 5 x2 - x3 = 0 x i ≥ 0, i=1, 2, 3
15	-x1 +2 x2 - x3 --> max x1 - x2 + 2x3 ≤ 0 x1 + x2 +5x3 ≥ 2 x i ≥ 0, i=1, 2, 3	30	x1 + x2 + x3 --> max 2 x1 + x2 + x3=3 x1 +2x2 - x3 = 3 2 x1 + x2 + x3 -x4 = 5 x i ≥ 0, i=1, 2, 3, 4

 

Лабораторная работа 10. Задача оптимизации многошаговых процессов, задача о ранце.

Задача оптимизации многошаговых процессов имеет вид

S {f°_i(x(i-1), u(i))| iÎ [1..n]}® max (4.19)

при ограничениях

x(0)=a(0), (4.20)

x(i)=f _i(x(i-1), u(i)), i Î [1..n], (4.21)

x(i) Î X(i), i Î [1..n], (4.22)

u(i) Î U(i), i Î [1..n], (4.23)

где X(i), U(i), iÎ [1..n], - конечные множества.

Положим X(0)={ a(0)}. Для этой задачи справедливо следующее функциональное

соотношение Беллмана:

W_n(x)=0, x Î X(n),

W _i(x)=max{f° _i(x, u)+W _i((f _i(x, u)) | u Î U _i(x)}, (4. 24)

x Î X(i), i Î [0..n-1],

где U _i(x)= {u Î U(i) | f _i(x, u) Î X(i+1) }.

Для того, чтобы решение x (i), i Î [0..n], u (i), i Î [1..n], удовлетворяющее ограничениям (4.20 – 4.23) было оптимальным, необходимо и достаточно, чтобы

f° _i(x (i), u (i+1))+W _i(f _i(x (i), u (i+1))) = max{f° _i(x (i), u)+

W _i(f _i(x (i), u)) | u Î U _i(x (i))}.

Исходя из сказанного выше, получаем следующий алгоритм решения задачи (1-5):

 

Алгоритм.

 

Первый этап.

for xÎ X(n) do W_n(x): =0;

for i: =n-1 downto 0 do

for xÎ X(i) do

begin

W _i(x)=max{f° _i(x, u)+W _i(f _i(x, u)) | uÎ U _i(x)};

u _i(x): =argmax{f°_i(x, u)+W _i(f_i(x, u))| uÎ U _i(x)}

end;

Второй этап.

x (0): = a(0);

for i: =1 to n do

begin

u (i): =u _i(x (i-1));

x (i): =f _i(x (i-1), u (i))

end;

Полученное в результате работы алгоритма решение x (i), u (i) iÎ [1..n], будет оптимальным для задачи (4.19– 4.23) Оптимальное значение функционала будет равно W₀(a(0)).

Задача о ранце имеет вид

S { c(i)´ u(i)| iÎ [1..n]} -® max (4. 25)

при ограничениях

S { a(i) ´ u(i)| iÎ [1..n]} £ b (4. 26)

где u(i)- целые числа, a(i) также рассматриваем целыми, i Î [1..n].

Введем переменные x(0)=0, x(i)= S { a(k) ´ u(k): k Î [1..i]}. Из задачи (4.25) - (4.26) получим эквивалентную задачу (4.27) - (4. 31):

S { c(i) ´ u(i)| iÎ [1..n]} -® max, (4.27)

x(0) = 0, (4.28)

x(i)=x(i-1)+a(i) ´ u(i), iÎ [1..n], (4.29)

x(i) Î X(i)={0, 1, 2,..., b}, iÎ [1..n], (4.30)

u(i) Î U(i)={0, 1, 2,..., b}, iÎ [1..n]. (4.31)

Задача (4.27) - (4. 31) имеет такой же вид, как и задача (4.19– 4.23), поэтому для решения задачи (4.27) - (4. 31) возможно применение алгоритма, описанного выше.