Постановка задачи и основные понятия
Рассмотрим задачу оптимизации на примере хорошо знакомого всем объекта - школьного расписания уроков. По крайней мере, автор верит, что большинство читателей этого текста хотя бы раз в жизни видели этот объект.
Школьное расписание представляет собой таблицу, в которой указаны связи между объектами нескольких типов: классы (как группы учеников), учебные кабинеты (аудитории), учителя (сотрудники школы), предметы (математика, физика, биология и т.д.)
Интуитивно понятно, что существует довольно много способов составить формально корректное расписание. То есть такое, которое соответствует чисто физическим ограничениям, свойственным людям и помещениям, например:
- ни один учитель не может проводить уроки в двух классах одновременно;
- учителям назначаются только те предметы, которые они способны преподавать;
- в одном кабинете в одно время может находиться только один класс;
- ни у одного класса нет "пустых" уроков в середине дня (хотя может допускаться приход в школу ко 2-3 уроку или учеба во вторую смену;
- в расписании учтено то, что некоторые предметы можно вести только в специально оборудованных кабинетах (информатика, физика, химия, биология, физкультура);
Помимо чисто физических ограничений могут быть и другие. Которые не обязательны, но крайне желательны для участников происходящего, например:
- количество уроков в день для конкретного класса должно быть примерно одинаковым;
Также возможны пожелания разной степени важности и критичности, исходящие от конкретных сотрудников или здравого смысла составителя расписания. Например:
- некоторые учителя могут работать только в определенные дни или в определенное время;
- некоторым учителями было бы удобно, чтобы классы одной параллели (например 8-е или 9-е) шли у них в какой-то день подряд (такое могут пожелать, например, физики, чтобы было удобнее проводить лабораторные работы);
- по просьбам родителей некоторым классам могут постараться сделать физкультуру последним уроком в какой-то день (или, наоборот, первым; или "когда угодно, но не сразу после обеда");
Оптимальным было бы такое расписание, в котором учитывались бы вообще все пожелания. Однако, мир несовершенен, и такой вариант встречается редко. Тем не менее, можно ввести числовую оценку того, насколько близко конкретное расписание к идеальному.
В первом приближении, можно принять в качестве такой оценки количество пожеланий, которые не учитываются в данном варианте расписания. Тогда вариант А будет лучше варианта B, если оценка варианта A < оценки варианта B. (Далее будем обозначать такую оценку как F(A) или F(B)).
Таким образом, вариант A лучше варианта B, если F(A) < F(B).
Задачу о составлении максимально комфортного расписания можно сформулировать так: среди всех возможных вариантов расписания нужно выбрать такой, у которого величина F() будет наименьшей.
В нашем случае выражение F() будет называться целевой функцией, так как именно на эта величина отображает насколько мы близки к цели работы.
На практике, разные пожелания и требования к расписанию могут учитываться с разными коэффициентами. Так, чисто физическому ограничению можно приписать коэффициент 1000 (чтобы в случае его нарушения значение F() заметно увеличивалось), а простому пожеланию - коэффициент 1. Или пожеланиям администрации - коэффициент 100.
Итог: процесс поиска оптимального варианта среди всех возможных называется оптимизацией. Показателем того, насколько решение близко к идеальному (оптимальному) служит некоторое математическое выражение - целевая функция. При программировании требуется найти такой вариант решения, чтобы значение целевой функции было наименьшим (в некоторых задачах - наибольшим, но эти критерии легко взаимозаменяемы).
Для приведенного примера интуитивно понятно, что прямой перебор всех возможных вариантов будет занимать существенное время, так как помимо формирования нового варианта расписания, требуется также провести его оценку на соответствие физическим критериям (возможно ли его осуществить в принципе).
Для более быстрого решения подобных задач существуют специальные алгоритмы, которые и будут (поверхностно) рассмотрены в этом разделе.