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

Теорема 2.2. Выпуклый n-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.
Следствие 2.3. Из теоремы вытекает, что выпуклый многогранник порождается своими угловыми точками (вершинами): отрезок – двумя точками, треугольник – тремя точками, n – угольник на плоскости – n точками и т. д. В тоже время выпуклая многогранная область, содержащая бесконечно удаленную точку, являясь неограниченным множеством, не определяется однозначно своими угловыми точками: любую ее точку нельзя представить в виде выпуклой линейной комбинации угловых точек.
Элементы выпуклых множеств
Определение 1. Множеством называется совокупность элементов любой природы, для которых задано правило принадлежности к данному множеству.
Определение 2. е - о к р е с т н о с т ь ю точки х называется множество всех точек, расстояние которых до точки х меньше е.
Определение 3. Точка х₁ называется внутренней точкой множества M, если существует такая - окрестность данной точки, все точки которой принадлежат множеству M.
Определение 4. Точка х₂ называется в н е ш н е й т о ч к о й м н о ж е с т в а M, если существует такая - окрестность данной точки, все точки которой не принадлежат множеству М.
Определение 5. Точка х₃ называется г р а н и ч н о й т о ч к о й м н о ж е с т в а M, если в любой её - окрестности существуют точки как принадлежащие множеству M, так и не принадлежащие этому множеству.
Определение 6. Множество М называется з а м к н у т ы м, если оно содержит все свои граничные точки. х 2- незамкнутое множество, Пример. х 2 - замкнутое множество.
Определение 7. Множество М называется в ы п у к л ы м, если вместе с любыми двумя точками, принадлежащими данному множеству, оно содержит и отрезок их соединяющий. В общей форме ЗЛП каждый символ R1, R2, …, Rm означает один из знаков: = или ≠. В такой форме задачи линейного программирования часть переменных может быть подчинена условию неотрицательности (x_i ≥ 0), часть – условию неположительности (x_j ≤ 0), а какие-то переменные, возможно, могут принимать любые значения.
6. Общий алгоритм симплексного метода ЗЛП
Решается задача

Пусть система невырожденна и совместна, т.е. r_A = r_B = r = m - ранг.
Выделим m = r базисных переменных x₁, x₂, ..., x_m , ф = 1(1)m и k = n - m свободных переменных x_m+1, x_m+2, ..., x_n , j = m + 1(1)n ; ЦФ и базисные переменные выразим через свободные

Все введённые переменные в новых обозначениях удобно свести в таблицу, которая называется симплексной.