Постановка задачи
Целочисленное программирование
При рассмотрении задачи линейного программирования считалось, что переменные могут меняться непрерывным образом в каких-то заранее известных пределах. Однако в силу экономического или физического смысла некоторые значения могут выражаться только натуральными числами (число станков, количество изделий и т.п.). Такое добавочное ограничение, как целочисленность переменных, весьма существенно, так как решение, достаточно близкое к решению непрерывной задачи, но целочисленное, может быть очень далеким от истинного решения задачи, изначально учитывающего такое новое ограничение, как целочисленность переменных.
Наиболее изучен класс задач целочисленного программирования детерминированного типа, в частности детерминированная задача дискретного линейного программирования. В общем виде такая задача имеет модель
,
где J – некоторое подмножество множества индексов N. Если J совпадает со всем множеством индексов N, то задачу называют полностью целочисленной, если же , – частично целочисленной.
Сущность методов дискретной оптимизации. Во всех случаях решение задачи, казалось бы, может быть найдено обычными методами с отброшенными условиями целочисленности и с последующими округлениями нецелых переменных в ответе. Однако такое округление может привести к решению, далекому от оптимального. Рассмотрим, например, геометрическую интерпретацию задачи дискретного линейного программирования (рис. 4.1).
Рис. 4.1. Графическое решение задачи целочисленного программирования
Оптимальным решением нецелочисленной задачи служит точка Анц. Как следует из рис. 4.1, точка В ближе всего к точке Анц в смысле округления. Но целой точкой, находящейся ближе всего к оптимальной линии уровня max Fнц, является точка D. Таким образом, попытка решить задачу с отброшенным условием целочисленности и последующим округлением полученного оптимального плана до ближайших целых значений не всегда состоятельна. С практической точки зрения подобный подход допустим в тех случаях, когда значения переменных, образующих оптимальное решение исходной задачи, достаточно велики и погрешностями округления можно пренебречь.
В первом приближении методы целочисленной оптимизации можно разделить на две основные группы: точные и приближенные. К точным относятся методы отсечения и комбинаторные (метод ветвей и границ). Это универсальные методы дискретной оптимизации. Кроме универсальных, имеется много специальных точных методов, учитывающих специфику задачи. Однако точные методы имеют слабую сходимость. Многие экспериментальные и прикладные задачи не удалось решить точными методами за десятки и сотни тысяч итераций, хотя их конечность теоретически доказана. Трудности машинной реализации точных методов привели к появлению различного рода приближенных, построенных на использовании особенностей конкретной задачи. Среди приближенных методов наметились два направления:
1) разработка детерминированных эвристических алгоритмов, учитывающих специфику задачи;
2) использование случайного поиска в сочетании с локальной оптимизацией.
Общая идея решения задачи дискретного программирования методами отсечения состоит в следующем. Исходная задача решается сначала без учета ограничений целочисленности. Если полученный оптимальный план удовлетворяет условиям целочисленности, то задача решена. В противном случае к ограничениям исходной задачи добавляется новое, обладающее следующими свойствами:
1) полученный нецелочисленный план нарушает это ограничение;
2) любой целочисленный допустимый план исходной задачи заведомо удовлетворяет и новому ограничению.
Затем задача решается с учетом нового ограничения. В случае необходимости добавляется еще одно ограничение и т. д. Геометрически добавление каждого нового ограничения отвечает проведению поверхности, которая отсекает от области допустимых решений некоторую его часть с оптимальной точкой с нецелыми координатами, но не затрагивает ни одной из целочисленных точек этого многогранника.
На основе этой идеи американский математик Р. Гомори предложил ряд сходящихся алгоритмов решения задач дискретного линейного программирования. Ему удалось обосновать правила построения дополнительных ограничений и доказать конечность алгоритмов.
Для решения других классов задач дискретного (особенно нелинейного) программирования получили широкое применение комбинаторные методы направленного частичного перебора допустимых планов. Из них наиболее универсален метод ветвей и границ, для выявления сущности которого воспользуемся известной задачей «математической смекалки» об отыскании фальшивой монеты.
Пусть в мешке с монетами одинакового достоинства имеется одна фальшивая, отличающаяся большим весом, которую нужно отыскать посредством взвешивания на рычажных весах без гирь. Поступим так. Разделим содержимое мешка на две равные по количеству монет части. В случае, если число монет п нечетное, разделим п-1 монет на две равные части. Положим на чашки весов равные по количеству монет части. Если чашки весов уравновесятся, то отложенная монета фальшивая; в противном случае она находится в более тяжелой части, с которой поступим аналогичным образом, и т. д., пока не обнаружим фальшивую монету. Здесь деление мешка есть процесс ветвления множества на подмножества, т. е. разбиение области допустимых решений на непересекающиеся подмножества. Взвешивание каждой части соответствует оценке целевой функции на подмножествах (оценкеихверхней или нижней границы). Если при этом удастся найти некоторый план, для которого верхняя (нижняя) оценка на множестве планов одного из подмножеств равна значению функции цели в этой точке и не меньше (не превосходит) оценок сверху (снизу) на всех подмножествах, то этот план оптимальный. Если такой план не обнаружен, то продолжаем процесс разбиения, начиная его с подмножества, имеющего самую высокую (низкую) оценку, и т. д. Поскольку множество всех планов задачи конечно, в конце концов оптимальный план будет найден.