Дискретная оптимизация. Задачи и методы дискретной оптимизации, страница 2

Частным случаем данной задачи является задача о выборе заявок – дано  заявок на проведение занятий в одной и той же аудитории. Для каждого занятия известно время его проведения , где  - соответственно время начала и окончания занятия. Два разных занятия не могут перекрываться по времени, но начало одного может совпадать с окончанием другого. Требуется выбрать максимальное число совместимых по времени занятий.

     К числу распространённых задач дискретной оптимизации также относятся задачи нахождения кратчайшего пути на графе и максимального потока в сети.

     Следует отметить, что для решения разных задач может быть использован один и тот же метод (в рамках которого могут быть использованы различные алгоритмы), а также – одна и та же задача может быть решена различными методами (и, соответственно, различными алгоритмами). Это обстоятельство проиллюстрируем следующим примером соответствия между задачами дискретной оптимизации и существующими методами их решения (рис. 1).

                   МЕТОДЫ                                    ЗАДАЧИ

  ВЕТВЕЙ И ГРАНИЦ                                     О РЮКЗАКЕ

   ДИНАМИЧЕСКОГО                                        О КРАТЧАЙШЕМ ПУТИ

ПРОГРАММИРОВАНИЯ

           ЖАДНЫЙ                                                КОММИВОЯЖЁРА

Рис. 1

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

     Хорошей иллюстрацией общей идеи МВГ служит задача отыскания фальшивой монеты в мешке с монетами, если известно, что фальшивая монета весит меньше настоящей, посредством деления мешка на части и взвешивания этих частей.

          Общая схема МВГ следующая. Вначале исходное множество

решений (вариантов) по некоторым признакам разбивается на некоторое число подмножеств , одно из которых обязательно включает оптимальный вариант . (Например, в задаче о кратчайшем пути это есть подмножества тех путей, которые могут быть получены продолжением одной из исходящих из начальной вершины дуг.) Для каждого из подмножеств  находится нижняя оценка целевой функции , т.е. такие числа , что .

     Затем определяется оценка , удовлетворяющая условию

, после чего соответствующее подмножество  разбивается на некоторое число подмножеств, для каждого из которых отыскивается своя оценка, т.е. и  и т.д.

        Если после некоторого числа ветвлений, например, , получается оценка , удовлетворяющая условию , то оптимальным решением будет , т.е. соответствующему граничному подмножеству и при этом . Следует отметить, что МВГ – точный метод решения комбинаторных задач.

     В приближённых методах, исходя из определённых эвристических предпосылок по относительно простым правилам строятся допустимые решения, которые могут быть удовлетворительными с практической точки зрения, хотя они могут и не быть оптимальными.  К числу таких методов относится жадный (или метод жадного выбора решений), общая идея которого состоит в том, что на каждом шаге выбирается самый лучший вариант. При решении большинства задач данный метод будет приближённым в силу того, что при формировании окончательного решения не учитывается предистория решений, полученных на предыдущих шагах. В то же время для некоторых задач данный метод позволяет получить оптимальное решение.

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