На рис. 3, в изображена невыпуклая функция. Если функция выпуклая, то ее max (M) или min (m) является глобальным, как показано на рис. 3,а (точка М) и рис.3,б (точка m). При этом условием отыскания max функции является ее выпуклость вверх, а min - выпуклость вниз. Невыпуклые функции обладают многоэкстремальностью, т.е. одновременным наличием нескольких max и min (см. рис. 3, в, точки М1, М2, m1 и т.д.), что значительно осложняет решение подобных задач. Условие выпуклости используется во многих вычислительных аспектах математического программирования.
1.4. Линейное и нелинейное программирование
Как уже отмечалось выше, в состав задач математического программирования входят задачи линейного и нелинейного программирования, причем нелинейному программированию в настоящем учебном пособии будет отведено несколько глав. В них кратко будут рассмотрены экономико-математические постановки и основные методы их решения. Кроме того, будут освещены вопросы использования градиентных и безградиентных методов поиска экстремумов (определения оптимальных значений параметров) одномерных и многомерных функций в рамках задач нелинейного программирования. В этой же главе мы сосредоточим внимание на разновидностях этих двух классов задач математического программирования.
Линейное программирование является наиболее развитой и законченной областью математического программирования. К этому классу задач относятся также и задачи целочисленного (дискретного) линейного программирования. Задача линейного программирования является не полностью целочисленной, если ограничение целочисленности касается лишь части переменных. В целочисленном линейном программировании можно выделить несколько характерных задач, из которых в инженерной практике нашли наиболее широкое применение задачи с неделимостями, переменные которых представляют собой физически неделимые величины. Действительно, при решении, например, транспортной задачи, если за единицу измерения однородного продукта принят вагон, контейнер и т.п., при решении задачи о назначениях в качестве исполнителей приняты самолеты, автобусы и другие машины и механизмы, то решение должно быть только целочисленным (дискретным).
10
Общие методы линейного программирования к задачам целочисленного программирования применять нельзя, так как в большинстве случаев они дают дробные решения. Округление компонент целочисленного решения до ближайших целых чисел может не только увести от оптимального целочисленного решения, но и вывести за пределы области допустимых решений. Существует класс задач целочисленного программирования, среди оптимальных решений которых всегда имеется целочисленное. К этому классу относятся, например, транспортная задача, сетевая транспортная задача, задача о назначениях, задача о кратчайшем пути и некоторые другие. Но этот класс узок и почти исчерпывается перечисленными проблемами. Поэтому возникла необходимость в разработке специальных методов решения задач целочисленного программирования.
Американскими учеными Дж. Данцигом, Д. Фалкерсоном и С. Джонсоном была предложена идея метода отсечения для решения задач линейного целочисленного программирования. Вначале задача решается без ограничений целочисленности. Если полученное решение целочисленно, то оно является оптимальным решением задачи целочисленного программирования. В противном случае к условиям исходной задачи добавляется линейное ограничение, которому удовлетворяют все целочисленные решения исходной задачи, но не удовлетворяет полученное положительное решение. Описанная процедура отсечения продолжается вплоть до получения на некотором шаге целочисленного оптимального решения либо до выявления неразрешимости задачи. Таким образом, решение задачи целочисленного программирования сводится к решению последовательности задач линейного программирования. Впервые правило формирования дополнительных ограничений для полностью целочисленных, а затем и частично целочисленных линейных задач было разработано американским ученым Р.Гомори в 1958 г. Метод Гомори при достаточно естественных предположениях о задаче приводит к оптимальному целочисленному решению за конечное число шагов. Известны и другие методы, использующие идею отсечения.
Важным и наиболее известным из комбинаторных методов является метод ветвей и границ и различные его модификации, использующие специфические особенности задачи в процессе решения. Методы случайного поиска применяются к задачам целочисленного программирования при их большой размерности, для
11
которых точные методы малоэффективны.
Нелинейное программирование – это совокупность нескольких принципиально различных групп задач, для каждой из которых характерен свой набор отличительных особенностей и способов их решения. Так, если критерий оптимальности (3) или ограничения (4) –
(6) являются квадратичными функциями, то задача называется задачей квадратичного программирования. Примером задачи квадратичного программирования является задача (3) – (6). Как самостоятельная группа задач в математическом программировании существует динамическое программирование, разработанное в 50-е г.г. XX столетия американским математиком Р. Беллманом и его учениками. В основе решения задачи динамического программирования лежит принцип оптимальности Беллмана. Его концепция сводится к следующему: имеется физическая система, характеризуемая на любом шаге параметрами состояния; на каждом шаге поиска решения принимается одно из допустимого множества решений, результатом чего является преобразование параметров состояния системы; предыстория системы не имеет никакого значения при определении будущих действий.
Любое правило для поиска решения, которое дает допустимую последовательность решения, называется поведением (политикой). Целью процесса является оптимизация некоторой функции параметров состояния и политики - функции критерия (дохода). Поведение, оптимизирующее функцию критерия, называется оптимальным поведением. Математическая формулировка этого принципа приводит к уравнениям, решение которых определяет оптимальное поведение и оптимальный доход.
Методы решения задач нелинейного программирования делятся на безградиентные и градиентные. В свою очередь безградиентные методы подразделяются на детерминированные и случайные. Если в детерминированных методах направление поиска заранее известно, то
вслучайных методах это направление выбирается случайно.
Вградиентных методах движение по поверхности отклика осуществляется по кратчайшему направлению, которое принято называть градиентом.
12
Вопросы для самоконтроля
1.Сформулируйте математическую постановку задачи математического программирования.
2.Дайте определение геометрической интерпретации задачи математического программирования.
3.Какова постановка задачи линейного программирования?
4.Каковы особенности задачи целочисленного линейного программирования?
5.В чём заключается идея метода Гомори?
6.Какова сущность метода ветвей и границ?
7.Сформулируйте задачу нелинейного программирования.
8.Перечислите безградиентные методы поиска экстремума.
9.Перечислите градиентные методы поиска экстремума?
10.Дайте краткую характеристику динамического пограммирования.
11.В чём заключается идея принципа оптимальности Беллмана?
13
Глава 2. БЕЗГРАДИЕНТНЫЕ МЕТОДЫ ПОИСКА ЭКСТРЕМУМА
Типичная постановка задачи нелинейного программирования сводится к тому, что заданы целевая функция
R(x1x2 ,...,xn ) max(min)
и система ограничений
j (x1,x2,...,xn ) 0.
(8)
(9)
Если нельзя целевую функцию выразить непосредственно через все неизвестные или ограничения системы (9) являются весьма сложными выражениями, то данную задачу нельзя решить иначе как методом непосредственного подбора неизвестных, доставляющих экстремум целевой функции. Эта группа методов объединена единым наименованием – нелинейным программированием. Эффективность использования методов нелинейного программирования связана с применением компьютера, поскольку они требуют значительного объема вычислений.
В составе нелинейного программирования можно выделить две группы поисковых методов: безградиентные и градиентные.
Для более подробного рассмотрения этих методов введем некоторые термины, характерные для поисковых задач. Наименьшая величина из всех имеющихся минимумов называется глобальным минимумом рассматриваемой целевой функции. Наибольшее из всех имеющихся величин называется глобальным максимумом.
Поисковые методы связаны с осуществлением пробных движений. Величина пробного движения носит название шага поиска. В результате поиска определяется направление уменьшения (либо возрастания) целевой функции для того, чтобы определить, каким образом следует изменять независимые переменные хi от начальных
значений (x10 ,x20 ,...,xk0 ), чтобы приблизиться к экстремуму рассматриваемой функции.
Безградиентные методы поиска экстремума имеют в своем составе методы детерминированного и случайного поиска. Если в детерминированных методах направление поиска заранее известно, то в методах случайного поиска это направление избирается самым
14