1. Введение
1.1 Какие-то примеры (Задача о диете?)
1.2 Формы задачи
1.2.1 стандартная Ax=b, x>=0, c^T x-> min
1.2.2 каноническая Ax<=b, x>=0, c^T x-> min
1.2.3 Ax <= b, c^T x-> min
1.2.4 (шутка) Ax=b
1.3 Эквивалентности 1<->2, 2<->3, идея Slack Variables, x=xplus-xminus.
1.4 Несущественность оптимизации (бинпоиск)
1.5 Стандартные термины:
1.5.1 feasible solution
1.5.2 feasible/infeasible system
1.5.3 optimal solution
1.5.4 unbounded program

2. Фурье Моцкин
2.1 Обычный
2.2 С оптимизацией
2.3 Следствие про существование решения

3. Полиэдр и вершины
3.1 Определение Полиэдра, Политопа, вершины
3.2 Мысль: оптимум в вершине....
3.3 ...Разве что может не быть вершин
3.4 Утверждение про сдвиг в вершину

4. Алгебраические свойства
4.1 A_x это линейно-независимое множество столбцов iff x вершина
4.2 Дополняем A_x до базисно допустимого решения (b.f.s.)

5. Отвлеклись на Гаусса, понаходили базисный поднабор строк в матрице

6. Решение LP через перебор C_m^n b.f.s.

---------

7. Simplex-метод
7.1 Инициализация: дали нам b.f.s., обращаем матрицу и исправяем вектор c.
7.2 Шаг симплекс-метода: переходим от одного решения к другому
7.3 Правило Блэнда
7.4 Не полиномиальное время работы
7.5 Поиск начального решения: решаем Ax-t=b, решение всегда есть, хотим t->min
7.6 Технические моменты:
7.6.1 Приводим систему Ax-t=b в правильный вид для симплекса (pivot)
7.6.2 Аккуратно выкидываем в конце столбец t, возможно нужен pivot
7.6.3 Подцепляем новый вектор c и нормализуем его.

---------

Reference:

Симплекс:
https://archive.lksh.ru/2019/august/A0/simplex.pdf

Линейное программирование вообще:
https://compsciclub.ru/media/courses/2011-spring/spb-linearprogramming/materials/notes-lp.ps

Видеозаписи курса Бабенко на csclub