Условие
Рассмотрите min z при x₁−x₃−2x₄=5, x₂+3x₃−x₄=6, xᵢ≥0 и целевой строке 0=20−z. Найдите допустимые, базисные и оптимальные решения.
Решение источника
Источник указывает z=20, вершины A=(5,6,0,0), B=(7,0,2,0) и лучи u=(2,1,0,1), v=(7,0,1,3).
Редакционное объяснение
В этой задаче цель постоянна на всей допустимой области. Поэтому задача поиска оптимумов равносильна полному описанию допустимых решений. Положим t=x₃,s=x₄. Тогда x=(5+t+2s,6−3t+s,t,s), где t,s≥0, 3t−s≤6. Первая координата автоматически положительна.
На плоскости параметров есть две вершины (0,0),(2,0) и два крайних направления (0,1),(1,3). Их образы дают A,B и u,v. Полный ответ: x=(1−α)A+αB+βu+γv, где 0≤α≤1, β,γ≥0. Все эти точки оптимальны с z=20. Базисные допустимые, а значит и базисные оптимальные, векторы — только A и B.
Чтобы увидеть полноту представления, рассмотрим t≤2 и t>2. В первом случае можно взять α=t/2, γ=0, β=s. Во втором случае положим α=1, γ=t−2, β=s−3(t−2). Последний коэффициент неотрицателен именно благодаря ограничению s≥3t−6. Таким образом, формула охватывает каждый допустимый вектор.
Проверка
Для A и B левые части равны (5,6), а для u и v — (0,0). Все координаты четырёх векторов неотрицательны. Точный перебор базисов подтверждает две различные допустимые вершины. Постоянство z следует непосредственно из 0=20−z.
Что не следует из ответа
Запись «выпуклая оболочка A,B» без конуса пропустила бы большую часть области. Коэффициенты при вершинах должны суммироваться в 1; коэффициенты при направлениях этого требования не имеют. В этом и состоит различие оболочки и конуса.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1352 · CC0 1.0. Адаптация damirock.com: добавлено конструктивное доказательство полноты разложения на отрезок и конус.