нехай
- кількість одиниць вj-м стовпці
,i = 1, m, j = 1, n.
Потрібно врахувати 2 умови.
Так як вектор рішення Х - логічний, то з (1) слід: чим менше
, тим доцільніше відповідну компоненту
покласти рівною 1, j = 1, n.
Бажано, щоб змінну, яку виберемо дорівнювала 1, входила в якомога більшу кількість умов (2), тобто при цьому виходимо з якомога більшої величини
,j = 1.n
З огляду на сказане, введемо відношення
,j = 1, n
Крок 1. Якщо в деяких стоках U1, U2. Unматріци маємо лише по 1-ій одиниці в стовпці
, то компонента, що випливає з (2). Якщо (2) виконується, то кінець. Якщо немає, то переходимо на щаг 2.
Крок 2. У
викреслимо рядки
стовпці
вони стають нульовими. отримаємо
.
=
Зауваження.
показує, що вj-му стовпці
немає жодної вершини, але відповідає компонента
, з ціною
може бути дорівнює 0 або 1. розглянемо решту рядка
. В
виберемо мінімальну компоненту, нехай це буде
, тоді
= 1. Якщо кілька. то за одиницю приймаємо кожну з них
матиме вигляд:
=
Так як minкомпоненте, то полагаемX
= 1
=
Так як С1 з С4 (
), То
.
Неважко бачити, що Х =
задовольняє (2,3) і достігаетmin (1), що дорівнює 4.
Схожі статті
