Методы нелинейного и целочисленного программирования
Нелинейное программирование сегодня представляет собой самостоятельную научную дисциплину с широким арсеналом математических моделей, методов и алгоритмов. Тем не менее, трудности, связанные с решением задач нелинейного программирования, связаны с их многообразием и особенностями формализации целевой функции и ограничивающих условий, которые могут быть линейными, квадратичными, дискретными или более сложной структуры. Обычно в задачах нелинейного программирования не выдвигается требование целочисленности переменных, тем не менее, всегда можно включить дополнительные нелинейные ограничения, благодаря которым в допустимые решения будут входить только целочисленные значения тех или иных переменных. В большинстве случаев нелинейности, отображаемые в моделях, связаны с эмпирически наблюдаемыми соотношениями (непропорциональное изменение затрат, выхода продукции, показателей качества) и структурно обусловленными соотношениями (постулируемые физические явления, установленные руководством правила поведения).
В настоящее время применение нелинейного программирования в преобладающем большинстве реальных ситуаций сводится к моделям линейной аппроксимации. Наряду с этим при существенной нелинейности в связи с ее спецификой или влиянием на характер модели приходится применять методы оптимизации, гораздо более сложные но сравнению, например, с симплексным методом. Однако значимость нелинейного программирования постоянно возрастает. Это обусловлено быстро растущими познаниями руководителей и специалистов в сфере использования математических моделей, предназначенных для подготовки решений, а также все большей доступностью машинных программ решения нелинейных задач большой размерности.
Задачи с целочисленными решениями встречаются во всех областях человеческой деятельности. Интерес к целочисленному программированию со стороны экономистов и специалистов, занимающихся проблемами обработки информации, достаточно велик. Сегодня возрастает актуальность их использования в СППР. Целочисленное программирование ориентировано на решение задач, в которых все или некоторые переменные должны принимать только целочисленные значения.
Задача называется полностью целочисленной, если условие целочисленности наложено на все ее переменные. Когда это условие относится лишь к некоторым переменным, задача называется частично целочисленной. Если при этом целевая функция и функции, входящие в ограничения, линейные, то задача называется линейной целочисленной.
Несмотря на то, что к настоящему времени разработан ряд методов решения целочисленных задач, ни один из них не обеспечивает желаемой эффективности соответствующих вычислительных процедур, что особенно проявляется при увеличении размерности решаемой задачи. В отличие от задач линейного программирования, где время решения относительно невелико, реализация целочисленных алгоритмов в ряде случаев весьма затруднительна. Одна из основных трудностей в целочисленном программировании связана с эффектом ошибки округления, возникающим при использовании цифровых процессоров. Присущие целочисленному программированию трудности вычислительного характера обусловливают стремление исследователей искать альтернативные пути решения проблемы.
Далее мы более подробно рассмотрим основные вопросы, связанные с использованием методов нелинейного и целочисленного программирования.
4.5.7. Применение симплекс-метода для решения целочисленных задач нелинейного программирования
Особую сложность представляют задачи целочисленного или дискретного нелинейного программирования. Методы их решения в настоящее время наименее развиты. В частном случае, когда целевая функция линейна, а в систему ограничений входят нелинейные уравнения или неравенства, эффективным оказывается применение симплекс-метода.
Рассмотрим порядок решения задачи нелинейного программирования в следующей постановке: требуется определить значения целочисленных аргументов x 1 , x 2 ,…, x n , доставляющие максимум
вида q ( x 1 , x 2 . x n ) = c 0 + ∑ c i x i
ряющие системе ограничений:
= b j ; j= 1,2,… m ; x i ≥ 0 ; i= 1,2,… n ;
z j ( x 1 , x 2 . x n ) ≤ 0 ; j= 1,2,… l.
Принцип решения такой задачи на основе симплекс-метода является развитием принципа решения линейной целочисленной задачи, рассмотренного в подразд. 4.3. Задача решается в три этапа: как обычная линейная непрерывная задача, как линейная целочисленная задача и в полной постановке с учетом нелинейных ограничений. Укрупненный алгоритм выглядит следующим образом.
1. Строится линейный план без учета условий (55).
2. Стандартным симплекс-методом без учета требований целочисленности находится допустимое и оптимальное базисное решение.
3. Если получено целочисленное решение, переходят к п.6.
4. Если полученное решение не является целочисленным, вво-
дится правильное отсечение по одной из переменных в соответст-
5. Пункты 2. 4 повторяются до получения допустимого и оптимального целочисленного решения.
6. Проверяется соответствие полученного решения нелинейным ограничениям задачи (55). Если условия (55) выполняются, полученное в пункте 5 решение является окончательным.
7. Если условия (55) не выполняются, строится отсечение Данцига, вызывающее переход к задаче повышенной размерности с недопустимым базисным решением.
8. Пункты 2-7 повторяются до получения допустимого и оптимального целочисленного решения, соответствующего ограниче-
Отсечение Данцига вводится в соответствии с условием
где x ′′ j – свободные переменные текущего плана. Условие (56) яв-
ляется линейным ограничением в форме неравенства и сводится к равенству путем введения дополнительной базисной переменной:
что эквивалентно дополнению линейного плана строкой, все элементы которой равны –1. Таким образом, размерность задачи повышается за счет добавления одной базисной переменной, причем текущее базисное решение оказывается недопустимым. Это требует повторного решения линейной задачи (переход к п. 2 алгоритма).
Пример 33. Дополним пример 28, рассмотренный в под-
разд. 4.3, нелинейным ограничением 0,5 ≤ x 2 / x 1 ≤ 2. Полученное в примере 28 решение, представленное планом в табл. 13, такому условию не соответствует. Введем отсечение Данцига и новую
переменную x 10 = − 1 + x 8 + x 9 ≥ 0 . План дополнится соответст-
вующей строкой, причем текущее базисное решение теперь окажется недопустимым (значение базисной переменной x 10 <0). Требуется дальнейшее преобразование плана по рассмотренным выше правилам (табл. 20).
Уже после первого преобразования по правилам, используемым для линейной непрерывной задачи, получен план, представ-
ленный в табл. 21. Соответствующее ему базисное решение является допустимым, оптимальным, целочисленным и удовлетворяет нелинейному ограничению. Таким образом, решение задачи получено.
Рассмотренный пример демонстрирует высокую эффективность метода. Тем не менее, отметим, что в общем случае решение задачи может потребовать и большего количества преобразований.
Методы решения задач нелинейного программирования
Нелинейное программирование используется для решения однокритериальных задач оптимизации с детерминированной целевой функцией при накладываемых ограничениях в виде равенств или неравенств. Для данного класса задач снимается условие линейности функций или ограничений.
Особенности использования данных методов определяются тем, что нелинейность целевой функции f(x) требует исследования условий (необходимых и достаточных) наличия экстремума. Для этого надо уметь получить аналитические выражения по меньшей мере двух производных этой функции.
При наличии линейных ограничений эти производные ищут только в точках, удовлетворяющих данным ограничениям. Нелинейность ограничений может привести к тому, что пространство возможных решений становится невыпуклым, и тогда оптимальному решению не всегда будет соответствовать одна из угловых точек этого пространства.
Универсальных алгоритмов решения нелинейных задач не существует из-за большого разнообразия вида нелинейности.
Разработанные ныне методы решения задач нелинейного программирования могут быть разделены на ряд больших групп:
¨ методы линеаризации целевой функции и ограничений, основанные на их разложении в ряд, логарифмирование и т.д., с последующим применением методов линейного программирования для решения задачи;
¨ аналитические методы нахождения экстремальных значений целевой функции при наличии ограничений. Они могут применяться при условии, что неизвестные величины непрерывны, или на этот счет сделаны соответствующие допущения, а также целевая функция и ограничения имеют частные производные хотя бы до второго порядка включительно;
¨ поисковые методы оптимизации, обеспечивающие решение нелинейной задачи путем последовательного перехода от одного допустимого решения к другому, в направлении экстремума целевой функции, до тех пор, пока дальнейшее ее улучшение станет невозможным или нецелесообразным.
Методы решения задач дискретного (целочисленного) программирования
Дискретное программирование используется для решения задач с детерминированной целевой функцией при ограничениях на значения переменных.
Примерами таких задач являются: определение очередности выполнения работ, назначение ресурсов по объектам использования, выбор маршрута на сети «задача о коммивояжере».
Основной особенностью является то, что все или некоторые переменные должны принимать только целочисленные (дискретные) значения. Обычно это бывает при описании неделимых объектов (людей, машин и т.п.) или при наложении жестких ограничений типа равенств.
При решении задач возникают сложности с выбором специальных дополнительных ограничений для отсечения области решений с нецелочисленными переменными, которые часто приходится выбирать по эвристическим правилам.
Различают два класса методов решения задач дискретного программирования: методы отсечения и комбинаторные методы.
Методы отсечений используются при решении линейных целочисленных задач без булевых переменных. Их идея заключается в ослаблении ограничений (за счет отказа от требований целочисленности) и решении обычной задачи линейного программирования. Затем, если полученное оптимальное решение не удовлетворяет требованию целочисленности, вводят специальные дополнительные требования, тем самым отсекая некоторую область возможных решений, и вновь решают задачу линейного программирования с проверкой результатов на целочисленность переменных.
Процесс повторяется до выполнения требований по целочисленности. Для решения целочисленных задач используется алгоритм Гомори и алгоритм Дальтона и Ллевелина (см. [6.57]).
Комбинаторные методы используются для решения нелинейных задач с булевыми переменными. Для таких задач используется так называемый аддитивный алгоритм, вычислительные операции в котором осуществляют вычитанием. Идея аддитивного алгоритма заключается в переборе 2 N возможных решений (где N — число булевых переменных) и выбор лучшего из них (см. [6.45; 6.55]).