Текст уведомления здесь

Как найти главного неудачника в городе

Симплекс-метод по-человечески

Представьте, что вы решили узнать, кто самый большой неудачник в городе. Можно, конечно, угадывать, а можно воспользоваться методами оптимизации, например симплекс-методом. Простую, понятную и неожиданную интерпретацию «Чердаку» предложил математик Юрий Дорн.
Добавить в закладки
Комментарии
Представьте, что вы решили узнать, кто самый большой неудачник в городе.

Пусть каждый человек про каждого из своих знакомых что-то эдакое знает и может оценить, кто из них больший неудачник, а кто — меньший. Вы думаете обо всех своих друзьях и выбираете самого большого неудачника, например Витю, идете к нему и говорите: «Витя, мне очень жаль, но ты самый большой неудачник, потому что у тебя самая маленькая заработная плата, почти нет опубликованных статей и жена страшная». Витя расстраивается и начинает в уме перебирать друзей. Тут его осеняет: «У Пети-то и зарплата ниже, и жена страшнее». Идет к Пете и говорит ему об этом в лицо. В итоге цепочка все больших неудачников растет и в конце концов останавливается на Шуре, у которого ни денег, ни жены, ни статей, и вообще, он стартапер и любит смузи. Шура понимает, что как ни крути, а он самый большой неудачник, и начинает плакать.

Это если неформально. А если формально, то речь идет о методе решения задачи линейного программирования. Ну то есть когда целевая функция и ограничения задаются линейными функциями.

Например, вот так:

3x - 2y + z ---> min
s.t.
x - y = 3
z - y = 1
x, y, z >=0

Целевая функция как раз определяет, что такое хорошо, а что такое плохо.

Например, x — уровень зарплаты. Чем он выше, тем больше значение целевой функции и тем дальше ты от неудачника. z — число статей. Ну а «y», соответственно, мера некрасивости жены. Чем жена страшнее, тем меньше значение целевого функционала и тем ближе ты к званию неудачника.

Ограничения (в данном случае странные: чем больше зарплата, тем страшнее жена, и чем страшнее жена, тем больше статей) определяют выпуклый многогранник. В нем нас будут интересовать особые вершины, у которых максимум две компоненты (ну или m, если m — число ограничений) не равны нулю. Можно доказать, что существует точка, которая удовлетворяет этому условию и в которой достигается минимум.

Так вот, именно такие точки и есть условные люди. Симплекс-метод проверяет, если у текущей вершины соседняя вершина (то есть у них общее ребро в многограннике, который задается ограничениями), в которой значение функции меньше. Если да, метод переходит туда и повторяет процедуру проверки.
Добавить в закладки
Комментарии
Вам понравилась публикация?
Расскажите, что вы думаете, и мы подберем подходящие материалы