MOP
.pdfЗМІСТ
Вступ……………… .......................... . .………………………… ..........................…....4 Вибір варіанта завдання…………………………………………………………….…..4
Частина 1. Лінійне і цілочисельне програмування …………………………........5 Геометрична інтерпретація задач лінійного програмування…………………….…..5 Завдання №1……………………………………………………………………………..7 Симплексний метод вирішення загальної задачі лінійного програмування………..9 Завдання №2 …………………………………………………………………………..12 Транспортна задача……………………………………………………………………14
Завдання №3.…………………………………………………………..................…….19 Задача вибору або задача про призначення………………………………………….21
Завдання №4 ………… . .……………………………………………………………...25
Частина 2. Нелінійне програмування……………………………………………..26 Методи одновимірної пошукової оптимізації……………………………………….26
Завдання №5 ……….. .....……………………………………………………….....….33
Нелінійна багатовимірна безумовна оптимізація…………………………………...34 Завдання №6 .....……………………………………………………….....…………….43
Нелінійна багатовимірна умовна оптимізація……………………………………….44
Завдання №7 ..…………………………………………………………...……………..46
Частина 3. Теорія розкладу. Задача Джонсона …………………………………..47 Завдання №8 .……………………………………………………………..……….…...50 ЛІТЕРАТУРА …...………………………………………………………………......…53
3
ВСТУП
Даний навчально-методичний посібник рекомендується студентам напряму підготовки 7.091501- “Комп`ютерні системи та мережі” при виконанні семестрової роботи з дисципліни “Методи оптимізації”. Передбачається, що студенти вивчили дисципліни “Вища математика”, “Дискретна математика” і “Теорія імовірностей і математична статистика”.
В методичному посібнику наведено перелік усіх завдань семестрової роботи, що складається із семи завдань. Перед кожним завданням подано теоретичний матеріал, необхідний для рішення поставленої задачі, тому посібник можна використати для самостійної підготовки.
Отримані знання будуть використані при вивченні дисциплін “Організація обчислювальних процесів”, “Програмування” та ін.
ВИБІР ВАРІАНТА ЗАВДАННЯ
Варіант завдання студенти вибирають із таблиці за двома останніми цифрами шифру в заліковій книжці.
шифру |
|
|
|
|
Остання цифра шифру студента |
|
||||||
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
0 |
20 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
1 |
1 0 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
|
Передостання цифра |
|
|||||||||||
студента |
2 |
20 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
3 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
||
4 |
20 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
||
5 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
||
6 |
20 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
||
7 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
||
8 |
20 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
||
|
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
|
|
|
4
ЧАСТИНА 1. ЛІНІЙНЕ І ЦІЛОЧИСЕЛЬНЕ ПРОГРАМУВАННЯ
ГЕОМЕТРИЧНА ІНТЕПРЕТАЦІЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Множина припустимих рішень (багатогранник рішень) задача лінійного програмування являє собою опуклий багатогранник ( або опуклу багатогранну область ), а оптимальне рішення задачі знаходиться, принаймні, в одній із кутових точок багатогранника рішень.
Розглянемо задачу в стандартній формі з двома змінними:
L 3x1 3x2 min(max)
x1 x2 8,
2x1 x2 1,x1 2x2 2,
x1 0, x2 0;
До такої форми може бути зведена і канонічна задача ( з обмеженнями у виді рівнянь), коли число змінних n більше числа рівнянь m на 2, тобто n - m = 2.
Множина рішень кожної нерівності із системи обмежень є напівплощина.
Побудуємо границі напівплощин - прямі
x1 x2 8, 2x1 x2 1, x1 2x2 2, x1 0, x2 0 .
Для визначення розміщення на малюнку шуканих напівплощин (верхніх або нижніх) рекомендується задати довільну контрольну точку, що не лежить на межах побудованих прямих (наприклад, точка з координатами (0,0)). Якщо нерівність виконується в контрольній точці, то вона виконується у всіх точках напівплощини, що містить контрольну точку, і не виконується у всіх точках іншої напівплощини. Геометричним зображенням системи обмежень є багатогранник
ABCD (мал.1).
5
Нанесемо на малюнку лінію рівня лінійної функції L: 3x1+3x2=9 (функцію цілі прирівняли до довільної константи ). Важлива властивість лінії рівня полягає в тому, що при паралельному зсуві лінії в одну сторону значення функції цілі тільки зростає, а при зсуві в іншу сторону - тільки убуває. Отже, при зсуві лінії рівня вбік зростання функції цілі можна визначити точку максимуму - це точка, у
якому лінія рівня і багатогранник рішень стикнуться востаннє. Аналогічним способом можна визначити точку мінімуму. У розглянутому прикладі точкою мінімуму є точка D, а точкою максимуму буде будь-яка точка, що належить відрізку АВ (лінії рівня паралельні граничнії прямії другої напівплощини ).
Визначимо ці точки.
Варто зауважити, що точка D знаходиться на перетині двох прямих :
2x1-x2=1 і x2=0.
6
2x |
x |
1; |
x |
0.5; |
|
|
|
1 |
2 |
|
1 |
|
Тобто точка мінімуму має координати (0.5; 0). Аналогічно |
x2 |
0 |
|
x2 |
0. |
|
визначаємо координати точки А (3 ; 5) і точки В (2 ; 6).
У результаті одержуємо:
найменше значення Lmin=1.5 функція цілі набуває в точці D (0.5 ;0);
найбільше значення Lmax=24 функція цілі набуває в будь-якій точці відрізка АВ.
ЗАВДАННЯ №1
Використовуючи геометричну інтепретацію задач лінійного програмування,
визначити екстремальні значення функції цілі при заданій системі обмежень (або переконатись в її нерозв'язності).
1. |
L=3x1+4x2 min(max) |
11 |
L=5x1+4x2 min(max) |
||||||||||||||
|
x1 x2 |
|
3, |
|
3x1 10x2 30, |
||||||||||||
|
|
|
|
3x2 |
9, |
|
|
|
8x2 8, |
||||||||
|
5x1 |
|
5x1 |
||||||||||||||
|
|
|
7x2 7, |
|
|
3x2 3, |
|||||||||||
|
x1 |
|
x1 |
||||||||||||||
|
|
|
0,x2 |
|
0. |
|
|
0,x2 0. |
|||||||||
|
x1 |
|
|
x1 |
|||||||||||||
2 |
L=-x1+4x2 min(max) |
12 |
L=5x1+x2 min(max) |
||||||||||||||
|
x1 5x2 1, |
|
10x 3x |
2 |
2, |
||||||||||||
|
|
|
|
1 |
|
|
|
||||||||||
|
6x x |
|
|
|
7, |
|
|
|
4x2 6, |
||||||||
|
2 |
|
|
9x1 |
|||||||||||||
|
|
|
1 |
|
|
|
|
|
2x1 |
|
|
|
|
|
|||
|
9x |
3x |
2 |
3, |
|
7x2 |
|
14, |
|||||||||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
x |
0,x |
|
|
|
0. |
|
x |
0,x |
2 |
|
0. |
||||
|
|
2 |
|
|
1 |
|
|
|
|
|
|||||||
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
3 |
L=-x1+5x2 min(max) |
13 |
L=x1-5x2 min(max) |
||||||||||||||
|
3x1 x2 9, |
|
x1 5x2 0, |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
15, |
||||
|
2x1 3x2 5, |
|
x1 |
||||||||||||||
|
|
|
4x2 |
|
4, |
|
|
|
x2 4, |
||||||||
|
x1 |
|
|
x1 |
|||||||||||||
|
x 0,x |
2 |
0. |
|
x 0,x |
2 |
0. |
||||||||||
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
7
4 |
L=x1+2x2 min(max) |
14 |
L=x1-x2 min(max) |
||||||||||||||||||
|
3x x |
|
|
|
|
|
9, |
|
|
x |
5x |
|
|
|
10, |
||||||
|
|
|
1 |
2 |
|
|
|
|
|
12, |
|
1 |
x2 |
2 |
|
|
|
||||
|
2x1 3x2 |
|
|
x1 |
|
15, |
|||||||||||||||
|
|
|
4x2 4, |
|
|
|
x2 4, |
||||||||||||||
|
x1 |
|
|
x1 |
|||||||||||||||||
|
x 0,x |
2 |
|
0. |
|
|
x 0,x |
2 |
0. |
||||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
||||
5 |
L=9x1+2x2 min(max) |
15 |
L=x1+2x2 min(max) |
||||||||||||||||||
|
x 4x |
|
|
|
|
5, |
|
|
x 3x |
|
|
|
0, |
||||||||
|
|
1 |
x2 |
|
2 |
|
|
|
|
|
|
|
1 |
|
2 |
|
|
|
|||
|
x1 |
|
3, |
|
|
|
2x1 x2 26, |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7x1 3x2 7, |
|
4x1 x2 8, |
||||||||||||||||||
|
|
|
0,x2 0. |
|
|
|
0,x2 0. |
||||||||||||||
|
x1 |
|
|
x1 |
|||||||||||||||||
6 |
L=10x1+11x2 min(max) |
16 |
L=x1+3x2 min(max) |
||||||||||||||||||
|
x |
4x |
|
|
|
|
5, |
|
|
2x 5x |
|
20, |
|||||||||
|
|
1 |
|
|
2 |
|
|
|
21, |
|
|
1 |
|
|
|
2 |
24, |
||||
|
7x1 3x2 |
|
|
4x1 3x2 |
|||||||||||||||||
|
|
|
x2 |
|
5, |
|
|
|
|
|
|
|
|
|
|
||||||
|
x1 |
|
|
|
|
3x1 4x2 |
36, |
||||||||||||||
|
x 0,x |
2 |
|
0. |
|
|
x 0,x |
2 |
0. |
||||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
||||
7 |
L=5x1+3x2 min(max) |
17 |
L=5x1-3x2 min(max) |
||||||||||||||||||
|
6x1 5x2 1, |
|
x1 x2 4, |
||||||||||||||||||
|
x 2x |
|
|
|
|
3, |
|
|
|
|
|
|
|
|
|
||||||
|
2 |
|
|
|
2x1 3x2 6, |
||||||||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4x1 9x2 1, |
|
3x1 2x2 6, |
||||||||||||||||||
|
|
|
0,x2 0. |
|
x |
0,x |
|
|
0. |
||||||||||||
|
x1 |
|
1 |
|
|
|
2 |
|
|||||||||||||
8 |
L=-x1+x2 min(max) |
18 |
L=7x1-2x2 min(max) |
||||||||||||||||||
|
4x1 x2 6, |
|
|
5x1 2x2 3, |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
18, |
|
|
x2 |
|
|
1, |
||||
|
9x1 8x2 |
|
|
x1 |
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3x1 11x2 1, |
|
3x1 x2 3, |
||||||||||||||||||
|
|
|
0,x2 0. |
|
|
0,x2 0. |
|||||||||||||||
|
x1 |
|
x1 |
||||||||||||||||||
9 |
L=5x1+7x2 min(max) |
19 |
L=3x1-3x2 min(max) |
||||||||||||||||||
|
3x 14x |
2 |
7, |
|
x 4x |
2 |
|
4, |
|||||||||||||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
||
|
5x 6x |
2 |
2, |
|
3x1 2x2 6, |
||||||||||||||||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
x1 2x2 2, |
||||||||
|
x 4x |
2 |
2, |
|
|
||||||||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
x |
0,x |
|
|
|
0. |
|
x |
0,x |
2 |
0. |
|||||||||
|
|
2 |
|
|
1 |
|
|
|
|
||||||||||||
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8
10 L=4x1+3x2 min(max) |
20 |
L=2x1+x2 min(max) |
||||||
2x |
x |
4, |
|
x |
x |
|
3, |
|
|
1 |
2 |
|
|
|
|||
|
3, |
|
1 |
|
2 |
|
||
x1 |
3x2 |
|
6x1 7x2 42, |
|||||
|
|
|
|
|
x x |
|
4, |
|
4x1 9x2 2, |
|
2 |
||||||
|
|
|
|
|
1 |
|
|
|
|
0,x2 |
0. |
|
|
0,x2 0. |
|||
x1 |
|
x1 |
СИМПЛЕКСНИЙ МЕТОД ВИРІШЕННЯ ЗАГАЛЬНОЇ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Розглянемо задачу лінійного програмування в загальному вигляді:
|
|
|
n |
|
|
|
|
|
|
L c j x j |
max(min) |
|
|
|
|||||
|
|
|
j 1 |
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
bi , |
bi 0, |
i 1, m ; |
||||||
|
aij x j |
||||||||
граничні умови |
j 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
j |
0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Довільну задачу лінійного програмування можна вирішити за допомогою універсального математичного методу, який отримав назву симплексного методу.
Але для його використання необхідно привести систему граничних умов поставленої задачі до канонічного вигляду, добавивши додаткові змінні xn i 0, i 1, m . В результаті отримали розширену задачу, еквіваленту вихідній задачі. У функцію цілі додаткові змінні вводяться з нульовими коефіцієнтами:
n |
m |
|
L c j x j |
0 xn i |
max(min) . |
j 1 |
i 1 |
|
Якщо кожна гранична умова системи обмежень має змінну, що входить у ліву частину умови з коефіцієнтом, рівним 1, а в усі інші – рівним 0, (при не негативних вільних елементах) то система подана у бажаному вигляді. Такі змінні можна назвати базисними. Щоб отримати опорне рішення, необхідно всі змінні, крім базисних, прирівняти до нуля, а базисним надати значення правих
9
частин відповідних рівнянь. Змінні, що набули значення нуля, називаються
вільними.
Складаємо симплексну таблицю по принципу:
Xbj |
X1 |
X2 |
… |
Xn |
п.ч. (bj) |
|
Базис |
Коефіціє |
Коефіціє |
|
Коефіціє |
Стовпець |
|
нти a1j |
нти a2j |
|
нти anj |
вільних |
||
ні |
. . . |
|||||
при X1 в |
при X2 в |
при Xn в |
членів в |
|||
змінні |
|
|||||
умовах |
умовах |
|
умовах |
умовах |
||
|
|
|||||
|
|
|
|
|
|
|
L |
- C1 |
- C2 |
… |
- Cn |
0 |
|
|
|
|
|
|
|
Далі виконуємо симплексні перетворення:
обчислення проводяться доти доти, поки в оцінному рядку не будуть знаходитись невід`ємні оцінки для задачі максимізації або з недодатні оцінки для задачі мінімізації;
вибираємо стовпцем, для якого оцінка буде найбільшим за модулем
негативним (позитивним) числом, якщо вирішується задача максимізації
(мінімізації) – цей стовпець буде вирішаючим;
у вирішаючому стовпці , вибираємо позитивний елемент, що відповідає найменьшому позитивному відношенню елементів вільного стовпця до відносних елементів вирішаючого стовпця;
рядок, у якому знаходиться вибраний елемент вирішаючого стовпця,
називається вирішаючим;
далі будуємо нову симплексну таблицю на основі елементів вихідної таблиці :
1. Елементи вирішаючого рядка діляться на вирішаючий елемент. Нехай
вирішаючим буде r-й рядок.
10
2. Елементи вирішаючого стовпця, всі, крім вирішаючого, діляться на
вірішаючий елемент з протилежним знаком, а вирішаючий дорівнює своєму оберненому значенню. Нехай вирішаючим буде s-й стовпець.
3.Елементи, що залишилися, у таблиці обчислюються за правилом прямокутника,
завжди починаючи з вирішаючого елемента:
ai j |
ai s |
aij-шуканий елемент, |
ars- вирішаючий |
|||||
елемент |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
ar j |
ar s |
aij aij |
|
ais arj |
, |
bi bi |
|
ais br |
|
ars |
|||||||
|
|
|
|
ars |
|
|
Тобто, у вихідній таблиці виділяємо прямокутник, вершинами якого служать наступні елементи: вирішаючий, шуканий, а також елементи з вирішаючого рядка і стовпця. Діагональ, що містить вирішаючий і шуканий елементи, назвемо
головною, а другу - побічною. З твору кутових елементів головної діагоналі відраховується твір кутових елементів побічної діагоналі й отримане число поділяють на вирішаючий елемент. Це - правило прямокутника.
Розглянемо крок симплексних перетворень на прикладі:
L 2 x1 |
x2 |
7 x3 |
max |
|
|
|
L 2 x1 x2 7 x3 |
0 x4 |
0 x5 |
max |
||||||||||||||||||
x 2x |
|
3x |
|
|
4 ; |
|
|
|
x 2x |
|
3x |
|
x |
|
4 ; |
|
|
|||||||||||
|
1 |
|
|
2 |
|
|
3 |
|
|
|
в канонічному виді |
1 |
|
|
2 |
|
|
3 |
|
4 |
|
|
|
|||||
x1 4x2 10x3 7 ; |
|
|
|
x1 4x2 10x3 x5 7 ; |
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0, |
|
j 1,3 |
|
|
|
|
|
|
|
0, |
j 1,5 |
|
|
|
|
|
||||||||||
x |
j |
|
|
|
|
|
|
|
x |
j |
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
Xb |
|
|
X1 |
|
|
|
|
X2 |
X3 |
bj |
|
Qj |
|
|
|
|
|
|
|
|
|
|
|
||||
|
X4 |
|
|
1 |
|
|
|
|
2 |
3 |
4 |
|
4/3 |
|
|
|
|
|
|
|
|
|
|
|
||||
|
X5 |
|
|
-1 |
|
|
|
|
-4 |
10 |
7 |
|
7/10 |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
L |
|
|
-2 |
|
|
|
|
-1 |
-7 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Xb |
|
|
X1 |
|
|
|
|
X2 |
X5 |
bj |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
X4 |
|
|
13/10 |
|
|
32/10 |
-3/10 |
19/10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
X3 |
|
|
-1/10 |
|
|
-4/10 |
1/10 |
7/10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
L |
|
|
-27/10 |
|
|
-38/10 |
7/10 |
49/10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11
Xb |
X1 |
X4 |
X5 |
bj |
|
|
Qj |
|
|
|
|
X2 |
13/32 |
10/32 |
-3/32 |
19/32 |
|
19/13 |
|
|
|
|
|
X3 |
1/16 |
2/16 |
1/16 |
15/16 |
|
|
15 |
|
|
|
|
L |
-37/32 |
19/32 |
11/32 |
229/32 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xb |
X2 |
X4 |
X5 |
bj |
|
|
|
|
|
|
|
X1 |
32/13 |
10/13 |
-3/13 |
19/13 |
|
|
|
|
|
|
|
X3 |
-2/13 |
1/13 |
1/13 |
11/13 |
|
|
|
|
|
|
|
L |
37/13 |
27/13 |
1/13 |
115/13 |
|
|
|
19 |
|
|
, 0, 0 . |
|
|
|
|
|
|
|
|
|
|
||
Отримали оптимальне рішення |
Lmax 115 |
|
, X opt |
, 0, |
11 |
||||||
|
|
|
|
13 |
|
13 |
|
13 |
|
ЗАВДАННЯ 2
Є декілька серій інтегральних мікросхем з різноманітним ступенем інтеграції. Мікросхеми кожної серії містять функціонально повні набіри логічних елементів у базисах (АБО-НЕ), (І-НЕ), ( , І, 1). На даному наборі ІМС можна побудувати декілька різноманітних вузлів ЕОМ: дешифратор, шифратор і мультиплексор. У таблиці наведені дані про кількість логічних елементів ІМС кожної серії, що використовуються при проектуванні на її базі відповідних вузлів у змішаному базисі (тобто при використанні логічних елементів усіх серій).
Також у таблиці наведена кількість мікросхем кожної серії і число логічних елементів що вони містять, а також вартість кожного вузла. Необхідно скласти такий план виробництва вузлів, при якому їхня сумарна вартість буде максимальною.
№ |
|
Серія мікросхеми |
|
Найменування вузла ЕОМ |
Кількіс |
|
Кіл-ть |
|||||
вар. |
|
|
|
|
DC |
MUX |
Coder |
ть ІМС |
|
елементів |
||
|
|
|
|
|
|
|
|
|
|
|
ІМС |
|
1 |
|
K1 (АБО-НЕ) |
3 |
4 |
4 |
15 |
|
5 |
|
|||
|
|
K2 (І-НЕ) |
2 |
0 |
3 |
24 |
|
3 |
|
|||
|
|
K3 ( , І, 1) |
|
10 |
12 |
10 |
18 |
|
|
8 |
|
|
|
|
|
|
6 |
12 |
10 |
|
|
|
|
|
|
|
|
Вартість вузла |
|
|
|
|
|
|||||
2 |
|
K1 (АБО-НЕ) |
4 |
3 |
2 |
4 |
|
4 |
|
|||
|
|
K2 (І-НЕ) |
3 |
2 |
0 |
5 |
|
5 |
|
|||
|
|
K3 ( , І, 1) |
|
8 |
10 |
10 |
|
|
|
|
|
|
|
|
|
|
36 |
40 |
42 |
|
|
|
|
|
|
|
|
Вартість вузла |
|
|
|
|
|
|||||
|
|
|
|
|
|
12 |
|
|
|
|
|
|