4 / 10
Выпуклые матрицы и многомерная задача о ранце общей лестничной структуры
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 6
35
Оптимальное решение задачи (10)–(12):
2 4 6 7 8 9
1 3 5 10
1,
0.
x x x x x x x x x x
Задачу (10)–(12) можно эквивалентным образом записать как совокупность
двух задач с одним ограничением каждая.
Первая задача
1
2
3
4
5
6
7
16 17
4 6 4, 5 5, 5 5,1
max
3
3
x x
x
x
x
x
x
(13)
при ограничении (6).
Вторая задача
3
4
5
6
7
8
9
10
10 11 7
2, 5 3, 5 2, 9
4 3
max
3
3 2
x
x
x
x
x x x x
(14)
при ограничении (7).
Третья задача с двумя ограничениями содержит ограничения (7) и (8) и це-
левую функцию
3
4
5
6
7
8
23 25
2, 5 3, 5 6, 9
7
3
3
x
x
x
x
x x
9
10
11
12
13
8 6 4 3 2
max.
x x x x x
(15)
Целевая функция (15) представляет собой разность целевых функций (9) и
(13). Оптимальное решение задачи (7), (8), (15):
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
7 23 19 22 17
3,1
4 3 2
max.
2 6
6
6
6
x x
x
x
x
x x x x
(16)
Задача с двумя ограничениями (6) и (7) имеет целевую функцию вида
1
2
3
4
5
6
7
8
9
10
19 61 23 26 19
4 6 7 9 8, 9
max.
2
6
6
6
6
x x x x
x
x
x
x
x
x
(17)
Целевая функция (17) получена вычитанием целевой функции (16) из целе-
вой функции (9).
Оптимальное решение задачи (6), (7), (17):
2 4 6 7 8 9
1 3 5 10
1,
0.
x x x x x x x x x x
Для формирования целевой функции задачи с двумя ограничениями необ-
ходимо получить целевую функцию задачи с ограничением (6):