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