4. Решение задачи булевского программирования о распределении капиталовложения.
4.2Булевское программирование. Метод Баллаша
Задание:
Вариант |
Проект |
Расходы (млн. грн. в год) |
Прибыль (млн. грн) |
||
1-й год |
2-й год |
3-й год |
|
||
19 |
1 |
4 |
6 |
3 |
10 |
2 |
9 |
7 |
8 |
15 |
|
3 |
7 |
9 |
9 |
10 |
|
4 |
5 |
5 |
6 |
25 |
|
5 |
6 |
4 |
6 |
20 |
|
Доступный капитал |
30 |
30 |
30 |
|
|
Решение
задач с булевыми переменными можно
производить методом ветвей и границ,
как с обычными целочисленными переменными,
для которых заданы граничные условия
.
Однако применение такого метода для
данных задач в ряде случаев оказывается
нецелесообразным. Существуют специальные
методы частичного перебора для решения
таких задач, наиболее совершенный из
них называется аддитивным алгоритмом
Баллаша с фильтром.
Суть этого метода сводится к следующему:
1) расположить переменные по возрастанию коэффициентов при них в целевой функции;
2) принять некоторый набор значений X, удовлетворяющий всем ограничениям;
3) значение целевой функции при удовлетворении п. 2 принять в качестве дополнительного фильтрующего ограничения (фильтра);
4) методом перебора X определить значение фильтрующего ограничения и проверить удовлетворение его заданным ограничениям;
5) если при некотором наборе X значение фильтрующего ограничения окажется для целевой функции лучшим, следует от первоначального набора перейти к новому и продолжить процедуру.
Составим математическую модель данной ЗЛП с булевскими переменными
1: 4x1 + 9x2 + 7x3+ 5x4+6x5 ≤ 30
2: 6x1 + 7x2 + 9x3 + 5x4 + 4x5 ≤ 30
3: 3x1+ 8x2 + 9x3 + 6x4 + 6x5 ≤ 30
F = 10x1 + 15x2 + 10x3 + 25x4 + 20x5 max
Примем значение целевой функции на наборе 00000 за фильтрующее.
№ |
X1 |
X2 |
X3 |
X4 |
X5 |
Выполнение ограничений |
||||
F |
1 |
2 |
3 |
Fф |
||||||
1 |
0 |
0 |
0 |
0 |
0 |
0 |
+ |
+ |
+ |
Fф=0 |
2 |
0 |
0 |
0 |
0 |
1 |
20 |
+ |
+ |
+ |
20 |
3 |
0 |
0 |
0 |
1 |
0 |
25 |
+ |
+ |
+ |
25 |
4 |
0 |
0 |
0 |
1 |
1 |
45 |
+ |
+ |
+ |
45 |
5 |
0 |
0 |
1 |
0 |
0 |
10 |
|
|
|
- |
6 |
0 |
0 |
1 |
0 |
1 |
30 |
|
|
|
- |
7 |
0 |
0 |
1 |
1 |
0 |
35 |
|
|
|
- |
8 |
0 |
0 |
1 |
1 |
1 |
55 |
+ |
+ |
+ |
55 |
9 |
0 |
1 |
0 |
0 |
0 |
15 |
|
|
|
- |
10 |
0 |
1 |
0 |
0 |
1 |
35 |
|
|
|
- |
11 |
0 |
1 |
0 |
1 |
0 |
40 |
|
|
|
- |
12 |
0 |
1 |
0 |
1 |
1 |
60 |
+ |
+ |
+ |
60 |
13 |
0 |
1 |
1 |
0 |
0 |
25 |
|
|
|
- |
14 |
0 |
1 |
1 |
0 |
1 |
45 |
|
|
|
- |
15 |
0 |
1 |
1 |
1 |
0 |
50 |
|
|
|
- |
16 |
0 |
1 |
1 |
1 |
1 |
70 |
+ |
+ |
+ |
70 |
17 |
1 |
0 |
0 |
0 |
0 |
10 |
|
|
|
- |
18 |
1 |
0 |
0 |
0 |
1 |
30 |
|
|
|
- |
19 |
1 |
0 |
0 |
1 |
0 |
35 |
|
|
|
- |
20 |
1 |
0 |
0 |
1 |
1 |
55 |
|
|
|
- |
21 |
1 |
0 |
1 |
0 |
0 |
20 |
|
|
|
- |
22 |
1 |
0 |
1 |
0 |
1 |
40 |
|
|
|
- |
23 |
1 |
0 |
1 |
1 |
0 |
45 |
|
|
|
- |
24 |
1 |
0 |
1 |
1 |
1 |
65 |
|
|
|
- |
25 |
1 |
1 |
0 |
0 |
0 |
25 |
|
|
|
- |
26 |
1 |
1 |
0 |
0 |
1 |
45 |
|
|
|
- |
27 |
1 |
1 |
0 |
1 |
0 |
50 |
|
|
|
- |
28 |
1 |
1 |
0 |
1 |
1 |
70 |
|
|
|
- |
29 |
1 |
1 |
1 |
0 |
0 |
35 |
|
|
|
- |
30 |
1 |
1 |
1 |
0 |
1 |
55 |
|
|
|
- |
31 |
1 |
1 |
1 |
1 |
0 |
60 |
|
|
|
- |
32 |
1 |
1 |
1 |
1 |
1 |
80 |
- |
|
|
- |
Фильтрующее ограничение:
Максимальное значение 70 функция достигает на наборе 01111. С помошью фильтра Баллаша колличество вычислений было сокращено на 39%.