5 / 10
А.А. Гурченков, А.С. Есенков, А.П. Тизик, В.И. Цурков
36
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 6
1
2
3
4
5
6
7
9 11 163 35 37
4 6
max.
2 2
30
6
6
x x x x
x
x
x
(18)
Целевую функцию задачи с ограничениями (7), (8) находят как разность
функций (9) и (18):
3
4
5
6
7
8
197 43 47
2, 5 3, 5
7
30
6
6
x
x
x
x
x x
9
10
11
12
13
8 6 4 3 2
max.
x x x x x
(19)
Оптимальное решение задачи (7), (8), (19):
5 6 7 8 9 11
3 4 10 12 13
1,
0.
x x x x x x x x x x x
Целевая функция с одним ограничением (8) может быть равна
5
6
7
8
9
10
11
12
13
3, 03 3, 2 3, 5 3, 2 3, 7 2, 7 4 3 2
max.
x
x
x
x
x
x x x x
(20)
Целевая функция задачи с ограничениями (6), (7) — это разность функций
(9) и (20):
1
2
3
4
5
6
7
4 6 7 9 8, 97 9, 8 10, 5
x x x x
x
x
x
8
9
10
3, 8 4, 3 3, 3
max.
x
x
x
(21)
Оптимальное решение задачи (6), (7), (21):
2 4 6 7 8 9
1 3 5 10
1,
0.
x x x x x x x x x x
Оптимальные решения задач с ограничениями (6), (7) и (7), (8) остаются раз-
личными в части, относящейся к общему ограничению (7). Однако предельное
состояние части целевой функции, относящееся к ограничению (7), это различие
неизбежно отменит, что и подтверждают дальнейшие вычисления. Предельное
значение коэффициента в целевой функции при переменной
5
x
в задаче с огра-
ничением (8) равно 3, соответственно в задаче с ограничениями (6), (7) этот ко-
эффициент будет равен 9. Ввиду равенства коэффициентов при переменных
4
x
и
5
x
их разделения для задач с одним ограничением ((6) и (7)) также будут совпа-
дать. Таким образом, оптимальных решений исходной задачи (6)–(9) будет два:
2 4 6 7 8 9 11 12
1 3 5 10 13
1,
0;
x x x x x x x x
x x x x x
2 5 6 7 8 9 11
1 3 4 10 12 13
1,
0.
x x x x x x x x x x x x x
Заключение.
Авторы настоящей работы выражают уверенность, что пред-
ложенный декомпозиционный прием может оказаться полезным и при реше-
нии других задач.
ЛИТЕРАТУРА
1.
Таха Х.
Введение в исследование операций. М.: Вильямс, 2001.
2.
Кагиров Р.Р.
Многомерная задача о рюкзаке: новые методы решения // Вестник Си-
бирского государственного аэрокосмического университета им. академика М.Ф. Ре-
шетнева. 2007. Вып. 3. С. 16–20.