Page 273 - Bkhargava_-_Grokaem_algoritmy

272 Глава 11. Что дальше?

Алгоритм Диффи-Хеллмана продолжает применяться на практике вместе
с его наследником RSA. Если вы интересуетесь криптографией, алгоритм
Диффи-Хеллмана станет хорошей отправной точкой: он элегантен и не
особо сложен.

Линейное программирование

Самое лучшее я приберег напоследок. Линейное программирование - одна
из самых интересных областей, которые мне известны.

Линейное программирование используется для максимизации некоторой
характеристики при заданных ограничениях. Предположим, ваша компа­
ния выпускает два продукта: рубашки и сумки. На рубашку требуется 1 м
ткани и 5 пуговиц. На изготовление сумки необходимо 2 м ткани и 2 пуго­
вицы. У вас есть 11 м ткани и 20 пуговиц. Рубашка приносит прибыль $2,
а сумка - $3. Сколько рубашек и сумок следует изготовить для получения
максимальной прибыли?
Здесь мы пытаемся максимизировать прибыль, а ограничения определяют

количество имеющихся материалов.
Другой пример: вы политик, пытающийся получить максимальное ко­
личество голосов. Исследования показали, что на каждый голос жителя
Сан-Франциско требуется примерно час работы (маркетинг, . rсследования
и т. д. ), а на каждый голос жителя Чикаго - 1,5 часа. Вам нужны голоса
как минимум 500 жителей Сан-Франциско и как минимум 300 жителей
Чикаго. В вашем распоряжении 50 дней. Кроме того, затраты на жителя
Сан-Франциско составляют $2, а на жителя Чикаго - $1. Ваш бюджет
составляет $1500. Какое максимальное количество голосов вы сможете
получить (Сан-Франциско+ Чикаго)?

На этот раз вы стремитесь к максимуму голосов при ограничениях по вре­
мени и деньгам.

Возможно, вы думаете: ~в этой книге много говорилось о вопросах оптими­
зации. Как они связаны с линейным программированием?» Все алгоритмы,
работающие с графами, могут быть реализованы средствами линейного
программирования. Линейное программирование - намного более общая
область, а задачи с графами составляют ее подмножество.

www.trk.kg