"Информатика", Поляков К.Ю., Еремин Е.А.
Оптимизация — это поиск лучшего варианта среди тех, которые подходят по условиям задачи. Нужно определить, что именно можно выбирать, какие правила ограничивают выбор и какой результат требуется улучшить: например, стоимость уменьшить или выручку увеличить. Для этого вводят переменные, задают целевую функцию и записывают ограничения. Оптимальным будет допустимый вариант, который даёт наибольшее или наименьшее значение этой функции. Такой подход помогает обоснованно сравнивать варианты.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Оптимизационная задача — задача, в которой нужно выбрать наилучший вариант по заданному критерию. Например, из нескольких способов добраться до школы можно искать самый быстрый. Это понятие нужно, чтобы отличать поиск лучшего варианта от простого поиска любого подходящего.
Целевая функция — выражение, значение которого требуется максимизировать или минимизировать. Если x и y обозначают количество изделий, то выручку можно записать, например, как R = 500x + 700y. Функция переводит выбранные значения переменных в число, по которому сравнивают варианты.
Ограничения — условия, которым должны удовлетворять допустимые варианты решения. Например, расход материала не может превышать имеющийся запас, а количество изделий не бывает отрицательным. Ограничения отбрасывают невозможные варианты, даже если по целевой функции они выглядят выгодно.
Оптимальное решение — допустимый вариант, при котором целевая функция достигает наибольшего или наименьшего значения. Для задачи о расходах это самый дешёвый вариант, который всё ещё выполняет нужные условия. Термин нужен, чтобы не называть лучшим решение, которое лишь подходит по ограничениям.
Сначала выясняют, нужно ли действительно искать лучший вариант. Если условие просит найти любой способ выполнить требование, сравнение всех возможностей может быть лишним. Оптимизационная задача возникает тогда, когда вариантов несколько и среди подходящих нужно выбрать, например, самый дешёвый или самый быстрый.
Затем переводят условие на язык переменных: определяют, что именно выбирают и какие значения может принимать выбор. Если планируют выпуск двух изделий, можно обозначить их количества через x и y. Переменные связывают реальную ситуацию с вычислениями, а их возможные значения сразу исключают бессмысленные ответы: например, отрицательное или дробное количество изделий.
После этого формулируют цель — величину, которую требуется улучшить. Выручку, стоимость или площадь выражают через переменные и получают целевую функцию. Слова «наибольший», «максимальный» означают поиск максимума, а «наименьший», «минимальный» — минимума; без точного критерия нельзя понять, какой вариант считать лучшим.
Ограничения записывают по всем условиям задачи: запас материала не должен быть превышен, время работы укладывается в отведённое, а переменные могут быть неотрицательными или целыми. Варианты, которые выполняют все ограничения, образуют область допустимых решений. Если забыть хотя бы одно условие, в эту область попадут невозможные варианты, и найденный ответ может оказаться непригодным.
Наконец, сравнивают значения целевой функции только для допустимых решений. Одного удачного примера недостаточно: другой подходящий вариант может дать больший доход или меньшие затраты. Поэтому оптимальность обосновывают перебором всех возможных вариантов, если их немного, или рассуждением, которое показывает, что лучшее значение достигнуто и превзойти его нельзя.
| Элемент | Что означает | Пример |
|---|---|---|
| Переменные выбора | Величины, значения которых выбирают | x и y — количество двух видов изделий |
| Целевая функция | Величина, зависящая от выбора и служащая критерием | R = 500x + 700y — выручка |
| Требуемое направление: максимум или минимум | Нужно ли увеличить или уменьшить целевую функцию | Максимизировать выручку |
| Ограничения | Условия, которым должен удовлетворять выбор | Расход материала не выше запаса |
| Допустимые решения | Варианты, выполняющие все ограничения | Пары (x; y), при которых хватает материалов |
| Оптимальное решение | Лучший допустимый вариант по целевой функции | Допустимая пара с наибольшей выручкой |
Пользуйся таблицей как проверочным списком: у каждой задачи найди переменные, критерий, направление поиска и все условия. Затем отдельно установи, какие варианты допустимы, и только среди них ищи оптимальный. Если один из элементов не удаётся заполнить, вернись к условию и уточни смысл выбора.
Условие: нужно выбрать тариф для 80 минут разговора и 20 сообщений. Тариф A стоит 120 рублей и включает до 100 минут и 50 сообщений, а тариф B стоит 150 рублей и включает до 150 минут и 100 сообщений. Требуется потратить как можно меньше, не превышая включённые объёмы.
Проверяем условия: обоих пакетов хватает на 80 минут и 20 сообщений, значит, оба тарифа допустимы. Если бы нужный объём превышал лимит какого-либо тарифа, его пришлось бы исключить или отдельно учесть доплату.
В качестве целевой функции берём стоимость тарифа, а направление поиска — минимум. Стоимости уже указаны в условии, поэтому пересчитывать использование минут и сообщений в деньги не требуется.
Сравниваем допустимые варианты: 120 рублей меньше, чем 150 рублей. Ответ: тариф A; так как проверены оба подходящих тарифа, более дешёвого допустимого варианта среди них нет.
Условие: изделие A приносит 500 рублей выручки и требует 2 кг материала и 3 часа работы. Изделие B приносит 700 рублей и требует 4 кг материала и 2 часа. Запас составляет 20 кг материала и 18 часов; количества изделий целые и неотрицательные. Нужно получить наибольшую выручку.
Обозначим количества изделий через x и y. Целевая функция — R = 500x + 700y, её нужно максимизировать; ограничения записываются как 2x + 4y ≤ 20, 3x + 2y ≤ 18, x ≥ 0, y ≥ 0, причём x и y — целые числа.
Проверяем допустимые комбинации, а не любые значения функции. Например, при x = 4 и y = 3 расходуется 20 кг материала и 18 часов, поэтому такой план подходит; выручка равна 500 · 4 + 700 · 3 = 4100 рублей.
Сравнение целых пар, удовлетворяющих ограничениям, показывает, что остальные варианты дают не больше 4100 рублей. Например, x = 2, y = 4 приносит 3800 рублей, а x = 6, y = 0 — 3000 рублей. Ответ: изготовить 4 изделия A и 3 изделия B; максимальная выручка — 4100 рублей.
Условие: периметр прямоугольного участка равен 40 м, а длина и ширина должны быть целыми положительными числами. Требуется найти размеры с наибольшей площадью. Здесь нельзя просто выбрать любую пару сторон с нужным периметром: площадь у разных допустимых пар различается.
Обозначим стороны через x и y. Из условия 2x + 2y = 40, поэтому y = 20 − x; положительные целые стороны требуют, чтобы x было целым числом от 1 до 19.
Площадь выражается через одну переменную: S = xy = x(20 − x). Проверяем целые значения x; пары с переставленными сторонами повторяют те же площади, поэтому достаточно рассмотреть значения до середины и сравнить их с соответствующими парами.
Наибольшая площадь получается при равных сторонах: x = 10 и y = 10, тогда S = 100 м². Ответ: участок размером 10 м на 10 м; он допустим, а остальные целые пары при сумме сторон 20 дают меньшую площадь.
Выбирают не ту целевую функцию. Можно, например, стремиться к наибольшему количеству изделий, хотя в условии требуется максимальная выручка. Так происходит, если ориентироваться на числа в задаче, не уточнив критерий выбора. Проверь себя: целевая функция должна выражать именно то, что просят увеличить или уменьшить.
Забывают одно из условий. План может укладываться в запас материала, но превышать доступное время. Часто внимание сосредотачивают на самом заметном ограничении и пропускают остальные. Перед проверкой ответа выпиши все условия отдельно и подставь найденные значения в каждое из них.
Считают любое допустимое решение оптимальным. Подходящий план ещё не обязательно лучший: другой вариант может дать большую выручку или меньшую стоимость. Ошибку допускают, остановившись на первом решении, которое выполняет условия. Проверь себя сравнением целевой функции для остальных допустимых вариантов или докажи, что улучшить результат невозможно.
Игнорируют требования к переменным. При расчётах может получиться дробное или отрицательное количество изделий, хотя в реальности это невозможно. Такое случается, когда учитывают ограничения на ресурсы, но забывают об области значений переменных. Укажи отдельно, должны ли переменные быть целыми и неотрицательными, а затем проверь им ответ.
Для решения оптимизационных задач нужны навыки чтения условия: важно выделить данные, неизвестные и ограничения, а затем обозначить неизвестные переменными. Чтобы записать целевую функцию и ограничения, пригодятся выражения и неравенства. Оптимизация применяется при планировании ресурсов, выборе маршрутов и тарифов, а также при создании эффективных алгоритмов: в каждом случае приходится искать удачный вариант, не нарушая заданных условий.
Чем оптимизационная задача отличается от обычной задачи на вычисление?
В задаче на вычисление обычно нужно получить конкретное значение по известным данным. В оптимизационной задаче приходится сравнивать несколько вариантов и выбрать лучший по заданному критерию. При этом выбор ограничен условиями задачи.
Как понять, что выбрать в качестве целевой функции?
Нужно найти величину, по которой в условии сравнивают варианты: стоимость, прибыль, время, площадь или другую характеристику. Если её требуется увеличить, ищут максимум, если уменьшить — минимум. Выбранная функция должна выражать именно этот критерий.
Зачем нужны ограничения, если целевая функция уже задана?
Ограничения задают, какие варианты вообще можно осуществить. Без них функция может улучшаться за счёт невозможного выбора, например использования большего количества материалов, чем есть в запасе. Поэтому максимум или минимум ищут только среди допустимых решений.
Можно ли считать оптимальным любое решение, которое удовлетворяет ограничениям?
Нет, такое решение лишь допустимое: оно выполняет условия задачи. Чтобы назвать его оптимальным, нужно показать, что ни один другой допустимый вариант не даёт лучшего значения целевой функции. Это подтверждают сравнением вариантов или доказательством.
Что делать, если переменные должны принимать только целые значения?
Это требование нужно включить в описание задачи: переменные могут принимать только целые значения, а иногда ещё и быть неотрицательными. Затем проверяют подходящие целые варианты, не рассматривая дробные значения как возможный ответ. Например, число изделий не может быть 2,5.
§ 29. Оптимизация
