Условие
Максимизируйте z=2x₁+2x₂+x₃ при x₁+x₂+x₃≤10, x₁,x₂,x₃≥0. Найдите хотя бы один оптимум и все оптимальные решения.
Решение источника
Источник рассматривает альтернативные оптимальные решения на границе области. Полный ответ можно получить без перебора симплекс-таблиц — сравнением стоимости единицы ресурса.
Редакционное объяснение
У x₁ и x₂ отдача на единицу ресурса равна 2, у x₃ — 1. Поэтому z=2(x₁+x₂+x₃)−x₃≤20−x₃≤20. Равенство требует одновременно полного использования ресурса и x₃=0. Все оптимальные точки: (t,10−t,0), 0≤t≤10.
В канонической форме x₁+x₂+x₃+x₄=10, x₄≥0. Начальный базис x₄ даёт z=0. После ввода x₁ получаем x₁=10−x₂−x₃−x₄, z=20−x₃−2x₄. Коэффициент при небазисной x₂ равен нулю: её увеличение перераспределяет ресурс от x₁ к равноценной переменной, не меняя результат. Допустимый диапазон x₂ — от 0 до 10.
Все допустимые точки образуют выпуклую оболочку O=(0,0,0), A=(10,0,0), B=(0,10,0), C=(0,0,10). Это также все геометрические вершины; их канонические векторы — (0,0,0,10), (10,0,0,0), (0,10,0,0), (0,0,10,0) — все базисные допустимые решения. Например, O допустима. Базисные оптимальные векторы — A и B с нулевым запасом. Их выпуклые комбинации образуют весь оптимальный отрезок. Точка (5,5,0,0) оптимальна, но небазисна: в равенстве ранга 1 положительны две координаты.
Проверка
Подстановка концов даёт цель 20 и сумму 10. В произвольной допустимой точке с x₃>0 цель строго меньше 20. Если ресурс недоиспользован, то x₄>0 и из финального выражения также следует строгая потеря.
Что не следует из ответа
Не нужно выбирать между x₁ и x₂ по их номеру: они равноценны. Но x₃ в оптимум не входит, хотя его коэффициент цели положителен. Нулевая приведённая стоимость означает возможность альтернативного решения только вместе с допустимым движением.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1432 · CC0 1.0. Адаптация damirock.com: получено точное полное множество оптимумов и раскрыта связь ресурсной оценки с симплекс-переходом.