Задачи и ответы
Раздел собирает задачи по методам оптимальных решений: выпуклые комбинации и конусы, линейное программирование и симплекс-метод, двойственность, транспортная задача, кратчайшие пути и потоки в сетях, условные экстремумы через неравенство о средних, динамическое программирование. На каждой странице отдельно обозначены решение исходного задачника (если оно есть) и редакционный разбор с проверкой ответа. Если в исходном решении найдена ошибка или пропуск, это сказано прямо.Последовательность подготовки
Начните с геометрии допустимых множеств: выпуклые комбинации, конусы, графическое решение задач на плоскости. Затем переходите к базисным допустимым решениям, симплекс-таблицам и особым случаям — пустому допустимому множеству, неограниченной задаче, неединственному оптимуму. Следующий блок — двойственная задача и условия дополняющей нежёсткости, транспортная задача и метод потенциалов, кратчайшие пути и максимальный поток. Завершают курс условная оптимизация (неравенство о средних, проверка множителями Лагранжа) и динамическое программирование: обратная индукция, уравнение Беллмана, игры с камнями, задача о рюкзаке, оптимальная остановка. Многосоставные задания сохраняются на одной странице.Происхождение материалов
Основной источник подборки — открытый задачник «Задачки по методам оптимальных решений» Бориса Демешева (репозиторий optimal-solution-pro); по словам автора, задачи использовались в курсе методов оптимальных решений весной 2024 года. Задачник распространяется по лицензии CC0 1.0. На каждой странице указаны зафиксированная редакция исходника, строка задачи и характер адаптации. Содержательные исправления не маскируются под исходные ответы.Обзор курса с вопросами и ответами
Каталог по темам
В разделе 26 страниц. Раскройте нужную тему; внутри группы названия расположены по алфавиту.Линейное программирование и симплекс-метод — 17
- Базисные допустимые решения при ограничении «больше»: почему x₃ = −8 не годится и откуда четыре вершины
- Базисные и допустимые решения системы x₁+3x₂+x₃=10, 2x₁+x₂+x₄=11: четыре вершины
- Бесконечно много оптимумов: весь отрезок от (1/2,1/2) до (1,0)
- Все базисные допустимые решения системы из трёх ограничений: три вершины из десяти базисов
- Два шага симплекс-метода: максимум x₁+x₂ равен 5 в точке (3,2)
- Линейное программирование с параметром c: порог 2/3 и целый отрезок оптимумов
- Минимизация 2x₁−3x₂: как получить −15 и не перепутать знак цели
- Неограниченная задача: допустимый луч (1+t,0) и отсутствие конечного максимума
- Неограниченное множество оптимумов при конечном минимуме: луч (t,t), t≥1/2
- Оптимальный луч из симплекс-таблицы: правильное значение 12, а не 15
- Отрезок оптимумов из таблицы: x₂=6−3t, а не 6−t
- Параметр в ограничении 2x₁+ax₂≤6: неограниченность при a≤0 и порог a=6
- Постоянная цель z=20: две вершины и два луча всех оптимальных решений
- Пустая допустимая область: противоречие 0≤−1 и первая фаза симплекс-метода
- Решение, базисное решение, допустимое решение: пять векторов для системы 2x₁+3x₂+x₃=8, x₁−x₂+x₄=9
- Три переменные и вырожденный оптимум: z=15, а запас x₄ равен нулю
- Четыре вершины из симплекс-таблицы: все допустимые решения и минимум 2