Консалтология Общая теория консалтинга (стр. 45 )

(9.123)

Наконец, неравенство (9.123) можно преобразовать в равенство, добавив дополнительную переменную xm+i:

(9.124)

где xm+i — целое, положительное.

Таким образом, если в исходную задачу добавить ли­нейное ограничение (9.124), задача все равно останется полностью целочисленной.

Уравнение отсекающей плоскости получается в резуль­тате вычитания из (9.124) уравнения (9.121):

(9.125)

где f(aij), f(bi) —дробная часть чисел аij и bi.

Заметим, что текущее решение задачи линейного про­граммирования не удовлетворяет ограничению (9.125), по­скольку значение

xm+i= —f(bi) строго отрицательно.

Алгоритм отсечения (алгоритм Гомори) состоит из сле­дующих шагов.

1. Найти оптимальное решение задачи линейного про­граммирования (9.117) — (9.119) без условия целочисленности (9.120).

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

3. Добавить к исходной задаче линейного программи­рования новое ограничение (9.125), найти оптимальное решение задачи с дополнительным ограничением и вернуться к шагу 2.

Введение на шаге 3 отсекающего ограничения (9.125) на­ряду с условием xm+i>0 делает текущее решение задачи линейного программирования недопустимым. Отсечение текущего оптимального решения означает, что на шаге 3 значение целевой функции в задаче максимизации не мо­жет возрасти, а может лишь уменьшиться. Отметим, что алгоритмы отсечения не гарантируют по­лучения допустимого целочисленного решения до самой по­следней итерации. Вследствие этого при преждевременном прекращении вычислений можно допустимое решение и не получить.

Методы возврата. В этой группе методов имеют­ся различные модификации. Наиболее распространенным среди них является метод ветвей и границ, который пред­назначен для решения частично целочисленных задач. Как и в методе отсечения, решение задачи начинается с оты­скания оптимального решения задачи линейного програм­мирования без учета условия целочисленности. Затем формируется семейство связанных, но различных задач ли­нейного программирования. Термин «возврат» определяет специфический способ формирования и решения последо­вательности задач.

Рассмотрим задачу максимизации (9.117) — (9.120). До­пустим, что для каждой целочисленной переменной можно задать верхнюю и нижнюю границы, в пределах которых безусловно содержатся ее оптимальные значения

(9.126)

Идея метода ветвей и границ основана на следующем элементарном факте. Рассмотрим любую переменную хj и примем, что R есть некоторое целое число, где Lj≤R ≤Uj-1. Тогда оптимальное решение задачи будет удовле­творять одному из ограничений

xj≥R + 1 или x j≤ R. (9.127)

К примеру, если при решении задачи линейного про­граммирования получено xi = 2,6, то можно поставить и решить две задачи линейного программирования, причем в одну из них вводится согласно (9.127) условие 3≤ x1 ≤U1, а к другую — условие L1≤ x1 ≤2. Предположим, что каж­дая из этих задач имеет оптимальное решение, удовлетво­ряющее условию целочисленности (9.120). Тогда решение, доставляющее большее значение целевой функции, явля­ется оптимальным решением исходной целочисленной за­дачи.

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

Алгоритм решения задачи целочисленного программи­рования методом ветвей и границ заключается в следую­щем. На каждой итерации (обозначим номер итерации че­рез t) имеются нижняя оценка F*t(X) оптимального значе­ния целевой функции и список задач линейного программирования, подлежащих решению. Процедура решения состоит в последовательном улучшении оценки F* (X) и приближении ее к оптимальному значению Fopt (Х).

На итерации 1 список задач содержит одну задачу (9.117) — (9.119). На итерации t из списка выбирают и ре­шают задачу линейного программирования. Если она не имеет допустимого решения или если полученное оптималь­ное значение целевой функции Ft opt (X)≤ Ft*(X), то нижняя оценка остается прежней и из списка выбирают очередную задачу для решения. Если полученное решение удовлетво­ряет условию целочисленности (9.120) и Ft opt (Х)>Ft*(X), то полученное оптимальное решение Ft opt (Х) на итерации t принимают в качестве нижней оценки для последующих итераций. Если полученное оптимальное решение задачи линейного программирования не удовлетворяет условиям целочисленности (9.120), то выбирают нецелочисленную пе­ременную хj и решаемую задачу разбивают на две новые задачи линейного программирования путем введения в каждую из них по одному ограничению (9.127).

При остановке алгоритма в случае, если допустимому решению соответствует значение целевой функции Ft opt (Х)=Ft*(X), полученное решение оптимально, в про­тивном случае допустимого решения не существует. Метод ветвей и границ особенно эффективен для решения ком­бинаторных задач, в частности задачи коммивояжера.

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

F opt ( (X) = min { FА opt (X), FB opt (X)}.

Поскольку множества А и В имеют меньшее число эле­ментов, чем множество V, т. е. возможность получить ниж­ние оценки качества F*А(Х) и F*B (X) более близкие к FА opt (X) и FB opt (X), чем в первоначальном множестве V, это означает, что оценка

min{F*А (X), F*B (X)} будет более близка к Fopt(X), чем оценка F*V (X).

Можно предположить, что оптимальное решение будет с большой вероятностью принадлежать тому из подмно­жеств А и В, которое имеет меньшую нижнюю оценку. Если оказалось, что F*B(X)<F*A (X), то есть все основания для детального исследования подмножества В. Последнее разбивают на два подмножества С и D с соответствующи­ми нижними оценками F*С (X) и F*D (X), и если оказалось, что

F*D(X)<F*С(X), то подобному разбиению подвергает­ся подмножество D. Эту процедуру продолжают до тех пор, пока не придут к подмножеству, состоя­щему из одного элемента с оценкой

F *(X)=F0(X). Про­цедура разбиения обычно представляется в виде дерева решений (рис. 9.13).

Рис. 9.13. Геометрическая иллюстрация мотода ветвей и границ

Найденное решение необходимо проверить на оптимальность. Для этого проверяют, нет ли среди нерассмот­ренных множеств А, С и т. д. элемента со значением нижней оценки F*(X)<F0(X). При этом множества, у которых F*(X)≥F0(X), дальше не рассматриваются.

Разбиение перспективных множеств либо приведет к решению с оценкой F*(X)<F0(X), которое должно быть принято за оптимальное, либо позволит убедиться в опти­мальности полученного ранее решения с оценкой F0(X). Из процедуры реализации метода ветвей и границ стано­вится ясным, почему этот метод получил название метода возврата.

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

Применение моделей и методов математического про­граммирования при консультировании проблем было рассмотрено в примерах п. 9.2. Ниже приводятся примеры постановки типовых задач структурного синтеза в терминах математического программирования.

Пример 9.8. Формирование рекомендаций по решению задачи оптимизация структуры сети электросвязи. Процесс консультирования по решению задачи проектирования региональных сетей электросвязи состоит из ряда вза­имосвязанных этапов: