Постановка задачи

Целочисленное программирование

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

Наиболее изучен класс задач целочисленного программирования детерминированного типа, в частности детерминированная задача дискретного линейного программирования. В об­щем виде такая задача имеет модель

,

где J – некоторое подмножество множества индексов N. Если J совпадает со всем множеством индексов N, то задачу называют полно­стью целочисленной, если же , – частично целочис­ленной.

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

Рис. 4.1. Графическое решение задачи целочисленного программирования

 

Оптимальным решением нецелочисленной задачи служит точка А_нц. Как следует из рис. 4.1, точка В ближе всего к точке А_нц в смысле округления. Но целой точкой, на­ходящейся ближе всего к оптимальной линии уровня max F_нц, является точка D. Таким образом, попытка ре­шить задачу с отброшенным условием целочисленности и последующим округлением полученного оптимального плана до ближайших целых значений не всегда состоя­тельна. С практической точки зрения подобный подход допустим в тех случаях, когда значения переменных, обра­зующих оптимальное решение исходной задачи, доста­точно велики и погрешностями округления можно прене­бречь.

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

1) разработка детерминированных эвристических алгоритмов, учитывающих специфику задачи;

2) использование случайного поиска в сочетании с ло­кальной оптимизацией.

Общая идея решения задачи дискретного программи­рования методами отсечения состоит в следующем. Исход­ная задача решается сначала без учета ограничений целочисленности. Если полученный оптимальный план удовлет­воряет условиям целочисленности, то задача решена. В противном случае к ограничениям исходной задачи добавляется новое, обладающее следующими свойствами:

1) полученный нецелочисленный план нарушает это огра­ничение;

2) любой целочисленный допустимый план исход­ной задачи заведомо удовлетворяет и новому ограниче­нию.

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

На основе этой идеи американский математик Р. Гомори предложил ряд сходящихся алгоритмов решения задач дискретного линейного программирования. Ему удалось обосновать правила построения дополнительных ограниче­ний и доказать конечность алгоритмов.

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

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