5.10.2. СЛУЧАЙ ЛИНЕЙНО РАЗДЕЛЯЕМЫХ МНОЖЕСТВ

Пусть имеется множество из п выборок уі, . . ., и требуется найти весовой вектор а, удовлетворяющий неревенству а*уг^ >йі>0 при всех і. Как сформулировать эту задачу в терминах линейного программирования? Один из способов состоит в введении так называемой искусственной переменной t с помощью выражений

и

Если t достаточно велико, эти условия выполняются без труда, например если а=0 и t=maxbi *). Однако такой случай не представляет

интереса с точки зрения решения поставленной задачи. Нас интересует как раз случай, когда і~0, т. е. тот случай, когда і принимает минимальное значение, при которрм еще выполняется условие ^>0. Таким образом, мы приходим к следующей задаче: найти минимальное значение і среди всех t и а, удовлетворяющих условиям  и ^О. Если в результате t окажется равным нулю, то выборки линейно разделяемы и полученный весовой вектор и будет искомым. Если же t окажется положительным, то разделяющего вектора не существует и, следовательно, выборки линейно неразделяемы.

Формально наша задача состоит в том, чтобы найти вектор и, минимизирующий целевую функцию z=a*u и удовлетворяющий ограничениям Ли и и >0, где

Таким образом, задача линейного программирования содержит m=2d+\ переменных и /=пограничений плюс ограничения симплекс-метода и>0. Симплекс-метод позволяет за конечное число шагов найти минимальное значение целевой функции г=а*и =t\ одновременно с этим определяется и вектор и, доставляющий г это значение. Если выборки линейно разделяемы, то минимальное значение t равно нулю, и вектор решения а может быть получен из и. Если же выборки неразделяемы, то минимальное значение t будет положительным числом. Полученное значение вектора и обычно не пригодно в качестве приближенного решения, но по крайней мере позволяет получить доказательство неразделяемости взятых выборок.