Условие
Максимизируйте x₁+x₂+x₃ при 2x₁+x₂+3x₃≤10, x₁−x₂+x₃≤6 и x₁,x₂,x₃≥0. Введите запасы x₄,x₅ и выполните симплекс-переход.
Решение источника
Источник получает (0,10,0,0,16), значение цели 10.
Редакционное объяснение
Стартовые запасы равны 10 и 6. Вводим x₂. В первой строке его коэффициент +1, во второй −1: рост x₂ расходует первый ресурс, но увеличивает запас второго ограничения. Поэтому вторую строку нельзя использовать для ограничивающего отношения 6/(−1). Выходит x₄.
Из первого равенства x₂=10−2x₁−3x₃−x₄. После подстановки во второе x₅=16−3x₁−4x₃−x₄. Цель принимает вид z=10−x₁−2x₃−x₄. Максимум 10 требует x₁=x₃=x₄=0; значит x₂=10 и x₅=16. Запас оказался больше стартового, поскольку второй левый член при оптимуме равен −10, а не положительному расходу.
Проверка
Исходные ограничения: 10≤10 и −10≤6. Запас второго равен 6−(−10)=16. Также z=(2x₁+x₂+3x₃)−x₁−2x₃≤10; это независимая верхняя оценка. Перебор допустимых базисов точными дробями даёт ту же единственную точку.
Что не следует из ответа
Отрицательный коэффициент ограничения не означает неограниченность всей задачи. Другие строки могут ограничивать входящую переменную. Нельзя механически делить все правые части на все коэффициенты столбца.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 970 · CC0 1.0. Адаптация damirock.com: объяснено исключение отрицательной строки из правила отношений и проверено происхождение запаса 16.