Решить задачу, добавив условие целочисленности переменных. Если при решении задачи (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)}. Для этой задачи справедливо следующее функциональное
соотношение Беллмана:
Wn(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 Wn(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(fi(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) Оптимальное значение функционала будет равно W0(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) возможно применение алгоритма, описанного выше.
