принимаем в качестве верхней оценки Ц целевой функции последующих ите-

Р^ Л' второй итерации формируем две задачи, каждая из которых содержит гхолную задачу, дополненную одним из ограничений-(7.132) или (7.133), е Б списке задач имеется две задачи, которые необходимо решить и сравнить соответствующие значения целевой функции каждой задачи с имеющейся ее

° Пусть выполнено 1 итераций. Итерация / содержит следующие три шага.

Шаг 1. Проверить, имеются ли в списке задачи. Если задач нет, прекратить вычисления, зафиксировать целочисленное решение (если оно имеется) о наилучшей оценкой Щ. В противном случае выбрать одну задачу из списка.

Шаг 2. Решить выбранную из списка задачу. Если задача не имеет допустимого решения или целевая функция оптимального решения меньше или равна нижней оценке Щ, то эта задача считается прозондированной, ее исключить из рассмотрения, принять = g* и перейти к шагу 1. Если оптимальное решение задачи линейного программирования удовлетворяет условию цело-числсьгости, зафиксировать его, принять равным оптимальному значению

- ; функции и вернуться к шагу 1. В противном случае перейти к шагу 3. Ш а г 3. В векторе управления X = (х ...,Хп) выбрать любую нецелочисленную переменную Xj = dj, j = 1, п, сформировать две новые задачи линейного программирования, добавив к задаче, выбранной на шаге 1, ограничение, в котором нижняя граница Xj заменена на [dj] + I, а к другой - ограничение, в котором верхняя граница Xj заменена на [dj], т. е. в одной задаче Xj > [dj] + 1, в другой a:j< [dj].

Принять g+i = и вернуться к шагу 1.

Таким образом, процесс ветвления продолжается до тех пор, пока каждая из задач будет иметь целочисленное решение Или улучшить полученное решение невозможно.

Метод неявного перебора вариантов. Метод неявного частичного перебора вариантов применим к решению задач, модель которых имеет вид: максимизировать

при ограничениях

JlCjXj (7.134)

atjXj aio, i= l,m; (7.135)

Xj = { =T. (7.136)

Предполагается, что каждый коэффициент Cj - рациональное Целое число.

Полностью целочисленные задачи всегда можно преобразовать к задаче с булевыми переменными, так как если для любой целочисленной переменной Ozk, а Zi, Zi,z - булевые переменные, т. е.

Z = Zi +22Н-----\-Zk

ИЛИ

z=lzi + 2Z2 + 223 + - + 2P-izp, где p - наименьшее целое число, определяемое условием

2Р - 1 k.

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

Ограничения булевости переменных (7.136) определяют 2 возможных выборов значений вектора управляемых переменных X={xi, ...,Хп). Ограничения (7.135) делают многие из этих вариантов недопустимыми; только некоторые из допустимых вариантов являются оптимальными.

Подмножество переменных Xj, в котором каждому х, соответствует числовое значение, равное нулю или единице, называется частичным решением. Те переменные Xi, которые не входят

а частичное решение, называются свободными переменными. Любой набор свободных переменных Xi, l=/=j, каждая из которых принимает конкретное значение, равное нулю или единице, называется дополнением соответствуюи^его частичного решения. Если в частичное решение входит k переменных, то существует 2 - дополнений.

В аддитивном алгоритме возможные дополнения порождают ветви дерева, частичное решение - вершины.

Пусть л=5 и частичное решение (л;2=0, Xi=\). Свободными переменными являются х^, х^, х^. Существует 2-=8 дополнений частичного решения, содержащего две переменные; одним из дополнений, например, является Xi=Q, х^-О, x-l.

Предположим, что известна нижняя оценка ° оптимального значения целевой функции и соответствующее допустимое решение.

Допустим построено некоторое частичное решение.

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

Таким образом, при зондировании частичного решения, содержащего k переменных, неявным образом перебирается 2 - возможных вариантов решений, удовлетворяющих условию булевости (7.136).

Частичные решения зондируются по следующему правилу. Частичное решение является прозондированным, если не выполняется соотношение

Е ацХз < Gio - Е (ijXh i = О, 1,2, т, (7.137)

е не существует допустимого дополнения, которому соответствует, значение целевой функции, превосходящее нижнюю оценку при в^шолнении соотношения

2 min (ац, 0) > Gio - Z aijXi, i = О, 1, 2, m, (7.138)

где аоз = -Cj H aoo = -*-1; S - подмножество индексов свободных переменных; L - подмножество индексов переменных частичного решения, которое зондируется.

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

Если для свободной переменной Xk выполняется соотношение 2] min(Gij, 0) -Н JGiftj > aio-TaijXj при любом i, (7.139)

I 0, если G,. > 0;

I 1, если Gift < 0.

Иногда более удобно зондирование частичного решения по правилу (7.138) и проверку выполнения соотношения (7.140) проводить для составных ограничений, образованных по правилу

п т т.

(Ц Угац) Xj < XI УггО, (7-141)

1 г=1 г=1

где У]>-0. Такой подход позволяет сократить количество проверяемых ограничений (7.135), т. е. ведет к уменьшению затрат машинного времени.

С помощью рассмотренного метода можно решать задачи, содержащие не более 100 переменных и не более 50 ограничений.

Рассмотрим алгоритм реализации метода неявного перебора вариантов. Перед первой итерацией в список задач помещают две задачи, соответствующие двум частичным решениям: дгд = О и дГд = 1.

При задаче максимизации индекс д определяют по правилу

9 = {/Imaxcj, / = \,п}. (7.142)

Шаг 1. Проверить, имеются ли задачи в списке. Если имеются, выбрать одну из них для зондирования, вычеркнуть ее из списка. В противном случае прекратить вычисления.

Шаг 2. Прозондировать выбранное частичное решение по правилу (7.138). Если не существует допустимого дополнения, для которого значение целевой функции превосходит достигнутый рекорд (наилучшее значение целевой функции, достигнутое на предыдущей итерации), то частичное решение прозондировано, полагают g+i = и возвращаются к шагу 1.

Если частичное решение не прозондировано, его необходимо расширить за счет свободных переменных по правилу (7.13©)-(7.140) и перейти к шагу 3.

Ш а г 3. Если частичное решение (расширенное) содержит все п переменных, зафиксировать его, определить соответствующее значение целевой функции <рекорд) g+i и вернуться к шагу 1. В противном случае перейти к шагу 4.

Шаг 4. Расширить частичное решение за счет некоторой свободной переменной Хд, образуя две задачи, первая из которых соответствует частичному решению, расширенному за счет переменной дгд = О (Хд = 1), вторая -за счет переменной Хд = 1 (дгд = 0). Принять +* = и вернуться к шагу 1.

После прекращения вычислений на шаге 1 в случае, когда зафиксировано допустимое решение и рекорд g, это решение является оптимальным. В противном случае допустимого решения не существует.

Пример. Дана задача, описываемая следующей моделью: максимизировать

4X1+Х2)

при ограничениях

20xi + 10X2 <75; 12xi + 7X2<55; Xi > О, Х2>0; Xi, Х2 - целые.

Решение. Перепишем модель задачи в канонической форме: максимизировать

(Xi + Хг)

при ограничениях

20xi + 10*2 + Хз = 75; 12xi -f 7x2 + Xi = 55; Xi>0, X20, Хз>0, X4>0; X\, X2, Xs, X4 - целые.

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

тимальное

/ 15 5 \

решение задачи линейнего программирования: X = 1 О,-, О,- I

15 \ 2 2 /

и значение целевой функции иоо = -.

Решение нецелочисленно. Для нахождения целочисленного решения можно использовать метод отсекающих плоскостей либо метод ветвей и границ. Метод отсекающих плоскостей

Построим правильное отсечение по переменной Хг =

20 = Х20- [Х20] =

-7 =

2 -

Таблица 7.15

==Х2з- [Xza]

. -0 =

-Xfs. в результате получена

Ти.дй отсечение имеет вид: --- = хъ---

табл. 716.

Находим решение с помощью двойственного симплекс-метода. Направляющий элемент д^бз, так как только дгв <; О и emin = вз = 1.

Проделав симплексные преобразования, получим табл. 7.17.

Получено оптимальное решение, так как все элементы индексной строки

неотрицательные. Решение . = (0,7,5,6) - целочисленно. Поэтому оптимальным решением исходной задачи является: х, = 0; д^г = 7. Значение целевой

функции /max = 7.

Метод ветвей и границ

Верхняя оценка на множестве решений G равна (G°) =-. Разбиваем

исходное множество С на два подмножества:

L J

-f 1

Находим решения и оценки на этих подмножествах.

Строим две задачи линейного программирования добавлением к исходной задаче ограничений л:2 < 7 и дгг > 8, т. е. л:2 -Ь лгв = 7 и -дгг -Ь < = -8. Полу-

ченные ограничения дописываем к табл. 7.15 и получим табл. 7.18.

Таблица 7.17

Вместо строки Xs(x) записываем строку Xslx ), представляющую собой ли-

нейную комбинацию строк и Хъ{х').

Решаем полученные задачи двойственным симплекс-методом. Поскольку в строке х' имеем дГбо < О, а все Xsj > О, то на множестве

задача неразрешима.

Проделав симплексные преобразования с направляющим элементом xi = = -2, получим табл. 7.19.

Полученное решение нецелочисленно.

Строим две задачи, дополняя предыдущую ограничением Xi < - или

-Xl:

L 4 J

-- 1, т. е. разбиваем множество GJ на два подмножества:

Таблица 7.19

X.XG[\Xl

I 4 J 1 T

Ha множестве получается решение Af] = 0; X2 = 7 и значение целевой функций равно 7, т. е. (G) =7. Дальнейшие вычисления прекращаются, так как

не может быть решения с лучшей оценкой, ибо KG ) =-Таким образом,

решение исходной задачи следующее:

л;; = 0; ДГг = 7 и /max = 7.

7.4. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Строго линейные модели, в которых использовалась пропор-

лльность, линейность и аддитивность, являются далеко не адекватными многим реальным ситуациям. В действительности такие зависимости, как^бщие затраты, выпуск продукции и т. п., от плана производства Z= (х х„) носят нелинейный характер.

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

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

Значимость нелинейного программирования и его использование постоянно возрастают.

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

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

Всегда необходимо проанализировать размерность и сложность Модели и оценить влияние линеаризации на принимаемое решение.

Часто пользуются двухэтапным подходом к решению задач: строят нелинейную модель небольшой размерности, находят область, содержащую ее оптимальное решение, а затем используют более детальную модель линейного программирования большей

размерности, аппроксимация параметров которой базируется на полученном решении нелинейной модели.

Для решения задач, описываемых нелинейными моделями, не существует такого универсального метода решения, как симплекс-метод решения задач линейного программирования.

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

Большинство методов нелинейного программирования не всегда обеспечивает сходимость за конечное число итераций. Некото-, рые методы обеспечивают монотонное улучшение значения целевой функции при переходе от одной итерации к другой.

Общая задача нелинейного программирования описывается моделью следующего вида:

минимизировать (максимизировать) целевую функцию

fo{xuX2,...,Xn) (7.143)

при ограничениях

fi {Хи Х2,.... Хп) < о, = l.m, (7.144)

где fo{Xi,Хп) и fi{xi,...,Xn), i = l,m,- действительные нелинейные, но регулярные функции п действительных переменных.

Итак, общая задача нелинейного программирования формулируется следующим образом: требуется найти я-мерный вектор X- = {хи...,Хп), который минимизирует (максимизирует) целевую функцию (7.143) и удовлетворяет ограничениям (7.144).

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

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

Решение задачи может быть внутри области допустимых решений или на ее границе.

Функция цели обычно имеет несколько локальных и глобальных экстремумов, что затрудняет решение задачи.

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

Точка области допустимых решений является локальным (относительным) минимумом, если ни в какой точке малой ее области

елевая функция не принимает меньшего значения, т. е. Хо - точка локального минимума целевой функции /о(Л:), если fo{Zo) fo{X) для всех точек X таких, что Х-ХоКе (где 8>0),-- произвольно малое число.

Глобальный минимум совпадает с одним из локальных, но локальный минимум не всегда совпадает с глобальным.

В задачах выпуклого программирования локальный и глобальный экстремумы совпадают.

Функция f{X) называется выпуклой вниз (выпуклой), если

f{kXi+ {l~k)X2) kfiXi) + {l-k)f{X2)

для любых точек Хь Хг и Ol. Функция ср(Х) называется выпуклой вверх (вогнутой), если -ф(Х) выпуклая вниз. При выполнении строгого неравенства функция называется строго выпуклой (вогнутой).

Если все fi{Xi, Х2,...,Хп), i=0, 1,...,п,- выпуклые вниз функции, го задача нелинейного программирования (7.143) - (7.144) яг тся задачей выпуклого программирования.

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

Градиентные методы. Пусть необходимо определить минимум функции f{Xi,...,Xn). Допустим выбрана произвольная точка Хо- = (х°,...,х° ). В каком направлении необходимо двигаться от этой

точки Хо, чтобы значение функции f{X), Х== (Хь..., х„), уменьшилось при достаточно малом шаге, т. е. чтобы }{Хо) f{X)}

Предположим, что имеется так£е направление движения, характеризуемое п-мерным вектором U= (иь ы„). Согласно формуле Тейлора,

f{Хо + pU) (Хо) + р(/.(Хо),и)+0{р), (7.145)

где р-достаточно малый шаг движения от точки X в направлении U; f:c(Xo)-градиент функции /(Хо), т. е. Ы(Х) =

/а/ df \ -

~ \ .- j = V/; 0(р)-малая величина, для которой 0(9)

Поскольку значение функции /(X) в каждой из последующих точек должно убывать и р>0, то

(fx(Xo),U)<0. (7.146)

Если направление U будет совпадать с направлением антигради-нта, т. е. и~-fx(Xo), то движение по этому направлению приведет к точке, в которой функция /(X) будет иметь меньшее значение, т. е. будет убывать.

Если точка X = (хи Хп) стационарна, то в ней достигается

минимум (максимум) и -=- = 0.

Методы последовательного улучшения значений непрерывно дифференцируемых функций при решении задач минимизации (максимизации) называются релаксационными.

Таким образом,решение задачи определения минимума нелинейной функции f{X) сводится к отысканию точки X, удовлетворяющей условию

Если найденная точка не удовлетворяет этому условию, необходимо найти новую стационарную точку, являющуюся локальным минимумом.

Одним из релаксационных методов решения задачи минимизации более сложной функции является градиентный метод, предложенный в 1848 г. математиком Коши. Этот метод заключается в вычислении и сравнении значений функции в ряде точек, опреде- ляемых точно против направления градиента функции при задаче минимизации по правилу:

, Xk+i = Xk- pkhiXk), k = 0, 1, (7.148)

где pfe -шаг движени^ на k-& итерации; fx{Xh) -градиент функции f(X) в точке Xk, Хо - произвольная точка, с которой начинается движение в окрестность точки Xi (окрестность соизмерима с шагом движения ро).

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

min / {Xk - pf. {Xk)) = f {Xk - Pkh (Xk)). (7.149)

По условию (7.149) juiar определяется так, чтобы на лучевыходящем из точки Xk в направлении антиградиента (-fx{Xk))> функция f{X) достигла минимального значения. Движение происходит с выбранным шагом, пока направление движения не изменится.

Для непрерывно дифференцируемой функции f{X) последовательность градиентов с ростом количества итераций, т. е. при k со, стремится к нулю. Поэтому множество предельных точек последовательности {Xt:}k, генерируемой в методе наискорейшего спуска, является подмножеством стационарных точек. Если количество этих точек конечное, то последовательность {Xh} либо сходится к одной из стационарных точек, либо имеет несколько предельных точек, причем значения функции в этих точках должны быть одинаковыми.