2020-05-12
112
По определенным переменным эффект вычисляем по их значениям, а по неопределенным по очередному максимальному значению коэффициента 
.
Правило выбора очередной подзадачи для рассмотрения:
Выбирается подзадача с максимальной оценкой целевой функции.
Правило исключения подзадачи из рассмотрения (элиминации):
Исключаются из рассмотрения (элиминируются) все подзадачи у которых оценка целевой функции ниже значения целевой функции для известного решения задача.
Рассмотрим задачу.
Определить оптимальный решение по распределению ресурсов А = 1040 между шести проектами. Данные о потребности ресурсов проектов аi и эффектов от проектов ci представлены в таблице.
| i | 1 | 2 | 3 | 4 | 5 | 6 |
| ai | 300 | 240 | 350 | 370 | 460 | 340 |
| ci | 600 | 580 | 900 | 430 | 690 | 640 |
| 2 | 2,4 | 2,6 | 1,2 | 1,5 | 1,9 |
Упорядочим проекты в порядке убывания
| i | 1 | 2 | 3 | 4 | 5 | 6 |
| ai | 350 | 240 | 300 | 340 | 460 | 370 |
| ci | 900 | 580 | 600 | 640 | 690 | 430 |
|
| 2,6 | 2,4 | 2 | 1,9 | 1,5 | 1,2 |
Обозначим
Требуется найти оптимальное распределение ресурса между проектами, т.е.
|
|
|
при ограничении
Решение задачи представим в графическом виде: ветвления, выбор подзадачи, оценки целевой функции, элиминация подзадач
Определим правило разбиения множества решений
по некоторой переменной, например 
:
,
и 
, т.е. в G1 включены все решения, в которых x1 = 1, а G2 включены все решения, в которых x1 = 0, для разбиения будем выбирать переменные из таблицы последовательно лева направо.
Определим верхнюю оценку целевой функции на множестве M с определенными t первыми компонентами:
Обозначим 
– объем нераспределенного ресурса на множестве 
.
В качестве правила выбора очередного подзадачи (подмножества) для разбиения примем, выбор подмножества с максимальной верхней границей.
На рис. через Аi обозначено "нераспределенный" ресурс для множества Gi. Приведем в развернутом виде расчеты оценок и значений целевой функции для вершин (подмножеств):
f(G10) = 690·1,9 = 1311
f(G11) = 900·1 + 580·1 + 600·1 + 640·0 + 150·1,5 = 2305
f(G12) = 900·1 + 580·1 + 600·0 + 640·1 + 110·1,5 = 2285
f(G13) = 900·1 + 580·1 + 600·0 + 640·0 + 450·1,5 = 2155
f(G14) = 900·1 + 580·1 + 600·1 + 640·0 + 690·0 + 150·1,2 = 2260
f(G15) = 900·1 + 580·1 + 600·0 + 640·1 + 690·0 + 110·1,2= 2252
F(X1) = 900·1 + 580·1 + 600·1 + 640·0 + 690·0 + 430·0 = 2080
F(X2) = 900·1 + 580·1 + 600·0 + 640·1 + 690·0 + 430·0 = 2120
Таким образом, оптимальное решение:
X2 = (1,1,0,1,0,0);
F(X2) = 2120,
т.е. средства распределяются в проекты 1,2,4 или 2,3 и 6 в исходной нумерации.
А = 1040 f(G0) = 1040 · 2,6 = 2704
G0
x1 = 1 x1 = 0
|
|
|
а1 = 350
А1 = 690 А2 = 1040
f (G1) = 900 · 1 + 690 · 2,4 = 2556 f (G2) = 1040 · 2,4 = 2496
G1 G2
x2 = 1 x2 = 0 x2 = 1 x2 = 0
а2 = 240 а2 = 240
А3 = 450 А4 = 690 А5 = 800 А6 = 1040
f (G3) = 900 · 1 + G3 f(G4) = 900 · 1+ G4 G5 f (G5) = 900 · 0 + G6 f (G6) = 1040·
580 · 1+450 · 2 690 · 2 = 2280 580 · 1 + 800 · 2 = 2180 · 2 = 2080
= 2380
x3 = 1 x3 = 0 x3 = 1 x3 = 0
а3 = 300 а3 = 300
А7 = 150 А8 = 450 А9 = 390 А10 = 690
f (G7) = 2365 G7 f (G8) = 2335 G8 G9 f (G9) = 2241 G10 f (G10) = 1311
x4 = 1 x4 = 0 x4 = 1 x4 = 0
а4 = 340 а4 = 340
А11 = 150 А12 = 110 А13 = 450
Ø G11 F(G11)= 2305 G12 F(G12) = 2285 G13 F(G13) = 2155
т.к.
А4 > А7
x5 = 1 x5 = 0 x5 = 1 x5 = 0
а5 = 460 а5 = 460
S14 = 150 А15 =110
Ø G14 F(G14) = 2260 Ø G15 F(G15) = 2252
т.к. т.к.
а5 > А11 x6 = 1 x6 = 0 а5 > А12
а6 = 370 x6 = 1 а6 = 370 x6 = 0
Ø А16 = 150 Ø А17 =110
т.к. G16={ X1} X1 = (1,1,1,0,0,0) т.к. G17={ X2} X2= (1,1,0,1,0,0)
а6 > S14 F(X1)=2080 а6 > А15 F(X2)=2120
|
|
|
Xr =X1 , Fr =2080 Xr =X2,, Fr =2120
Продолжите разбиение подзадач G9 и G13 и убедитесь, что далее они также элиминируются
Таким образом, оптимальное решение:
X2 = (1,1,0,1,0,0);
F(X2) = 2120,
т.е. средства распределяются в проекты 1,2,4 или 2,3 и 6 в исходной нумерации.
