Был как-то на одном вокзале и увидел табличку насчет ограничения на размер чемодана: сумма трех измерений должна быть меньше 150 см. И родилась идея этой заметки. Я покажу несколько типичных нюансов оптимизации.
Итак, предполагается,что чемодан - это прямоугольный параллелепипед. Сумма трех его измерений меньше 150 см. Какой чемодан нам заказать, чтобы его объем был максимален?
Оказывается, что такая задача решения не имеет. Точного решения. Чтобы это понять, давайте поставим задачу формально. Три измерения чемодана обозначим x, y, z и запишем целевую функцию (объем) в виде xyz. При этом мы ищем максимум не везде, а в некоторой области: все три переменные положительны и их сумма меньше 150. Область открытая, так что достаточно найти точки, в которых все три частные производные равны нулю.
Открытая область - это которая каждую точку содержит с небольшим шариком вокруг. В ней можно из любой точки хоть немного, но шагнуть в любом направлении, что и нужно для аппарата дифференциального исчисления. Если шаг в любую сторону почти ничго не дает, то такая точка может быть максимумом: там всегда так.
Частные производные равны yz, xz, xy. Приравнивая их нулю, мы ... не получаем ни одного решения внутри области. Решений нет.
Здесь должна быть соответствующая мелодия: уа уа уа уааа.
Даже если мы допустим нулевые значения переменных (тогда точки, в которых производные все нули, есть: это x=y=0, x=z=0 или y=z=0), но это минимум объема (нулевой), а не максимум.
Но приближенные решения есть! Можно взять замкнутую область, в которой сумма трех переменных может быть равна 150 (но не больше). Строго говоря, в замкнутой области еще и нулевые значения допускаются, но они все равно не решения задачи на максимум. Такая задача решение имеет и можно к нему сколь угодно приблизиться, оставаясь в рамках прежних ограничений.
Замкнутое множество - это дополнение открытого. То есть, если точка в множество не входит, то и некоторый шарик вокруг тоже не входит. Иными словами, граница множества ему полностью принадлежит (а граница открытого ему полностью не принадлежит). То же можно сказать и так: предел любой последовательности из множества принадлежит множеству: если можно приблизиться, то можно и взять.
И у вас постоянно будет дилемма. Либо у вас решение неоптимальное: например, сумма 147 см, и можно почти три сантиметра добавить, что, кстати, позволит распихать дополнительно до пятнадцати поллитровых емкостей! Либо вы рискуете выйти на границу и не пройти контроль. Маленькая, но катастрофа. И это типично: чтобы достичь максимума скорости, надо максимально облегчить конструкцию, то есть выйти на предел по прочности - и чуть что, случится поломка.
Давайте решим "замкнутую" задачу. Раз внутри области решений нет, то можно просто проверить точки границы: выразить из уравнения x+y+z=150 одну переменную и подставить в функцию. Мы, однако, пойдем другим путем: через множители Лагранжа.
Смысл в том, что мы добавляем еще одну переменную: штрафную ставку λ, и как бы предлагаем решить задачу поиска максимального объема без ограничений, но уменьшаем результат на λ куб.см. за каждый сантиметр превышения суммой числа 150 (штраф). Получается задача на поиск максимума функции четырех переменных:
xyz - λ(x + y + z - 150)
Приравнивая ее частные производные нулю, получаем, что все три длины (x, y, z) равны друг другу. Тогда они все равны 50 см и нам даже не понадобился множитель Лагранжа λ! Свою роль он сыграл.
Но найти его можно, он равен 2500 кв.см и показывает, насколько важно ограничение. Здесь это число ни о чем нам не говорит, но если ограничений два, то можно сравнить их по "важности".
Впрочем, кое-что он даёт: представление о том, сколько можно выиграть в объёме, если, например, 1 сантиметр по каждой стороне "простят". А выиграть можно 7.5 литров...
Итак, оптимальный чемодан - это куб с ребром в полметра. Не самый удобный чемодан...
Опять уа уа уа уааа.
А что я? Я ничего. Вы просили решить задачу - я ее решил. Я же не виноват, что решение вас не устраивает. Ставьте задачу иначе. Например, задайте предельные пропорции сторон. Скажем, самая короткая не длиннее трети самой длинной, а средняя не длиннее половины длинной.
Тогда оптимальный чемодан будет "максимально похож на куб", то есть ограничения будут выполнены в точности. Вы получите чемодан с короткой стороной 2х, средней 3х и длинной 6х. И сумма этих трех равна 150 см. То есть
2х + 3х + 6х = 150.
Отсюда х=150/11=13.63, и чемодан наш имеет размеры 27.27см на 40.9 см на 81.82 см.
При этом куб имеет объем 125 литров, а этот чемодан меньше на 34 литра: плата за ограничение!
Я не знаю, каковы типичные пропорции чемоданов, взял числа на глазок. Не в них дело. Выводы из этой краткой экскурсии такие:
- Задача может не иметь точного решения из-за незамкнутости области допустимых значений: решение на границе, а она "не считается", потому что надо "меньше", а не "не больше".
- Причем решение на границе уязвимо, неустойчиво: чуть-чуть погрешности, и вы за краем. И запас прочности - нарушение оптимальности.
- Задача может иметь решение, которое вам не понравится. Часто задача, наконец, ставится "как надо" только тогда, когда решение уже известно или до него осталось шаг шагнуть.
Классические примеры ведра сахара в качестве оптимального пайка (калорийность в макс) или "чтобы уменьшить число бедных, надо уменьшить число бедных" или "если вы хотите снизить вес, отрежьте себе руку" о том же: задачу оптимизации можно решить, но ее надо сначала правильно поставить! - При решении задачи может применяться довольно сложный математический аппарат, дающий дополнительную информацию (которая может быть полезной, а может и не быть).
- Усложнение задачи (ввод новой переменной) часто упрощает задачу: новая переменная в итоге не понадобилась, сделав всё необходимое одним своим присутствием.
Оптимизируйте с осторожностью. А то любят у нас оптимизацию...