нехай
- кількість одиниць в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.