Cтраница 2
Общая идея решения задач линейного программирования была подсказана рассмотрением геометрической интерпретации задачи. Из геометрических соображений было очевидно, что решение задачи линейного программирования может находиться на границе допустимой области многогранного множества, причем достаточно ограничиться перебором только конечного множества вершин этой области. [16]
Согласно этой схеме, в каждом цикле алгоритма, т.е. при определении очередного улучшающего решения, нужно выбрать направление перехода от имеющегося решения к улучшенному и шаг вдоль этого направления. Геометрическая интерпретация задачи выбора направления поиска показана на рис. 5.2. Множество допустимых решений, определяемое условиями задачи, представляет собой некоторую поверхность D в пространстве искомых переменных. Пусть полученное решение лежит на поверхности D. Тогда выбор направления поиска сводится к определению такого направления, лежащего внутри D и исходящего из z, вдоль которого критерий оптимальности / быстрее всего возрастает. [17]
Прозрачная геометрическая интерпретация исходной негеометрической задачи может оказаться важным шагом на пути к ее решению. [18]
Если число переменных в прямой и двойственной задачах, образующих данную пару, равно двум, то, используя геометрическую интерпретацию задачи линейного программирования, можно легко найти решение данной пары задач. При этом имеет место один из следующих трех взаимно исключающих друг друга случаев: 1) обе задачи имеют планы; 2) планы имеет только одна задача; 3) для каждой задачи двойственной пары множество планов пусто. [19]
В конце 50 - х годов были начаты работы по обучению машин распознаванию ситуаций. Первое направление в этой области связано с введением геометрической интерпретации задачи как задачи разделения в некотором фиксированном пространстве множеств точек, если признаки, по которым точки относятся к каждому из этих множеств, заранее неизвестны, а известны лишь примеры точек, принадлежащих отдельным множествам. Была выдвинута интуитивная гипотеза о компактности подлежащих разделению множеств в пространстве рецепторов и были предложены два алгоритма обучения - алгоритм случайных плоскостей и алгоритм потенциальных функций. На основе этих алгоритмов были проведены опыты на универсальных цифровых машинах по обучению машин распознаванию пяти и сразу всех десяти цифр. [20]