симплекс - алгебраическая интуиция за базисом канонической формы

Question

Я пытаюсь понять симплексную итерацию проблемы с n переменными и m технологическими ограничениями, следуя этому тексту . Я хорошо понимаю геометрическую интерпретацию итерации - перемещение между смежными вершинами.

Однако я не понимаю алгебраической интуиции. Теперь мы pivoting между смежными basic feasible solutions = bfs в стандартной форме AX + IS = b, X,S >= 0:

1. Почему у bfs n переменные равны 0?
2. Почему остальные переменные должны образовывать basis? Не является ли базис набором линейно независимых векторов, охватывающих подпространство? Что мы здесь охватываем, мы просто ищем вершину, не так ли?

Спасибо!

Answer 1

1. BFS должна правильно иметь n-m неосновные переменные, установленные на 0. Некоторые из m основных переменных сами могут быть 0, но это вырожденное решение.

2. Основой действительно является минимальный набор линейно независимых переменных, охватывающих вектор b. Обратите внимание, что b является m-vector. Таким образом, m векторов, соответствующих переменным, может образовать BFS. Общее количество переменных составляет n. Следовательно, число базисов экспоненциально n Choose m.

Поворот или перемещение из одной вершины в другую - это не что иное, как замена одной из неосновных переменных (связанного вектора столбца) в базу и удаление ранее существующей переменной из базы. Таким образом, базис всегда будет иметь m (столбец) векторов.

В любой момент времени, учитывая разбиение A на базовые и неосновные переменные, такие как A = [B|N], затем Bx = b и, следовательно, x переменные являются коэффициентами диапазона B, который дает b.

Фундаментальным результатом линейного программирования является то, что каждая вершина ограниченного линейно ограниченного выполнимого многогранника LP соответствует базовому решению и наоборот. Справка: https://press.princeton.edu/titles/413.html