«Анализ и проектирование алгоритма симплекс-метода для решения задач линейного программирования.»

Теорема 1. Любой вектор n-мерного векторного пространства можно представить, как линейную комбинацию векторов базиса, притом единственным образом. Определение 2.5. Максимальное число линейно независимых векторов линейного пространства называется размерностью линейного пространства. Линейное пространство обычно обозначают, R_n где n – его размерность. Выпуклой оболочкой точек называется множество всевозможных выпуклых комбинаций этих точек. Множество называется выпуклым, если вместе с двумя любыми его точками оно содержит и их произвольную выпуклую линейную комбинацию. С геометрической точки зрения это означает, что выпуклое множество содержит вместе с любыми двумя своими точками и соединяющий их отрезок. Выпуклое множество совпадает со своей выпуклой оболочкой. Примерами выпуклых множеств являются прямолинейный отрезок, квадрат, круг, прямая, полуплоскость, куб, шар, полупространство и другие. Угловыми точками выпуклого множества называются точки, не являющиеся выпуклой линейной комбинацией двух произвольных точек множества. Например, угловыми точками треугольника являются его вершины, угловыми точками круга – точки окружности. Таким образом, выпуклое множество может иметь конечное или бесконечное число угловых точек, но может не иметь их совсем. Например, прямая, плоскость, полуплоскость, пространство, полупространство угловых точек не имеют. Одним из основных понятий теории линейного программирования является понятие выпуклого многогранника в n-мерном пространстве, частными случаями которого являются при n = 1 отрезок на прямой, при n = 2 выпуклый многоугольник на плоскости. Выпуклым многоугольником называется выпуклое замкнутое ограниченное множество точек на плоскости, имеющее конечное число угловых точек, называемых вершинами. Прямолинейные отрезки, соединяющие две вершины и образующие границу, называются сторонами многоугольника.
Опорной прямой выпуклого многоугольника называется прямая, имеющая с многоугольником, расположенным по одну сторону от нее, хотя бы одну общую точку.
Выпуклым многогранником называется выпуклое замкнутое ограниченное множество точек пространства, имеющее конечное число угловых точек, называемых его вершинами. Многоугольники, ограничивающие многогранник, называются его гранями, а отрезки, по которым пересекаются грани, называются ребрами. Опорной плоскостью многогранника называется плоскость, имеющая с многогранником, расположенным по одну сторону от нее, хотя бы одну общую точку.