Некоторые нелинейные методы решения оптимизационных задач

Воспользовавшись условиями касания, составим систему уравнений и найдем координаты решения:

Найдено решение задачи - точка - точка касания ограничения и линии уровня функции

.

Построим графическую иллюстрацию решения.

Ограничение в задаче - прямая с уравнением .

Определим конфигурацию линии уровня функции , вычислив инвариант:

т.к. , то искомая линия уровня эллипс.

Запишем уравнение линии уровня:



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

- каноническая уравнение эллипса

Центр эллипса - точка с координатами .

Главные диагонали эллипса прямые с уравнениями: и .

Найдем точки пересечения эллипса с главными диагоналями:

Получены точки с координатами: и

Получены точки с координатами: и

Найдем еще несколько точек для построения эллипса, выразив из канонического уравнения эллипса:



Табл. 8

0	1	1
0.5	2.5811	-0.5811
1	3	-1
1.5	3.1213	-1.1213
2	3	-1
2.5	2.5811	-0.5811
3	1	1

Построим на чертеже ограничение и линию уровня .

Рис. 15

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

Запишем классическую функцию Лагранжа:

Запишем необходимые условия экстремума функции при ограничениях типа равенства:

Решим полученную систему:

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

Определим характер полученной точки с помощью достаточных условий экстремума. Запишем второй дифференциал функции Лагранжа:



Запишем дифференциал ограничения :

В точке имеем:

при условии

получим:

при

Следовательно. в точке выполнены достаточные условия локального условного минимума.

в) Найти решение задачи методом исключений

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

Найдем безусловный экстремум функции :



функция имеет минимум при

Найдем оптимальное значение

Окончательно, найдена точка условного минимума функции с координатами

г) Найти решение задачи методом штрафной функции.

Составим штрафную функцию:

В случае поиска условного максимума, используют штрафную функцию вида:

Запишем необходимые условия безусловного минимума штрафной функции:

Преобразуем исходную систему к виду:

Разрешим полученную систему относительно переменных методом Крамера:

Тогда - стационарная точка штрафной функции.

Найдем координаты условного экстремума исходной задачи как предел решения задачи поиска безусловного экстремума штрафной функции:

Получена точка - точка условного экстремума исходной задачи.

Запишем матрицу Гессе для штрафной функции:

при

при

Следовательно, по критерию Сильвестра, достаточные условия минимума функции выполняются, и значит полученная точка - точка условного локального минимума функции .

Запишем оценку :

В случае поиска условного максимума, используют формулу:

.

3. Программирование задач нелинейного программирования в математическом пакете Mathcad

3.1 Градиентные методы в двумерном пространстве

Пример 1. При подкормке посева необходимо внести в расчете на один гектар почвы следующих веществ не менее: ед. , ед. и ед. . Есть возможность приобрести удобрения и . Цена единицы веса удобрения равна ден. ед., цена единицы веса удобрения равна ден. ед. Дана матрица

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

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

где - стоимость , весовых единиц удобрения , - стоимость весовых единиц удобрения .

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

(**)

Проводя аналогичные рассуждения в отношении веществ и , получим еще два неравенства, которым должны удовлетворять переменные и :

По смыслу задачи переменные и не могут выражаться отрицательными числами, т.е.

В итоге имеем следующую математическую модель задачи:

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

Изобразим на координатной плоскости множество планов данной задачи. Известно, что точки, координат которых удовлетворяют нестрогому линейному неравенству, располагаются по одну сторону от граничной прямой и на самой прямой, т.е. занимает одну из полуплоскостей, порождаемых этой граничной прямой. Уравнение граничной прямой получается приравниванием левой и правой частей данного неравенства. Так, на основании неравенства (**) получим уравнение

граничной с прямой, соответствующей этому неравенству. Переписав его в виде

замечаем, что прямая (35.4) отсекает на оси отрезок в ед., а на оси - в ед. Неравенство (**) определяет полуплоскость, в которой точка не принадлежит, поскольку ее координаты не удовлетворяют этому неравенству: .

Аналогичным образом, устанавливаются полуплоскости, порождаемые граничными прямыми

и соответствующие неравенствам (35.2).

Учитывая, что неравенства (35.3) определяют первую четверть координатной плоскости , находим множество планов как общую часть (пересечение) всех установленных полуплоскостей. В нашем случае это неограниченная многоугольная область с вершинами и (рис. 16).

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

Рис. 16. Множество планов

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

Итак, по оптимальному плану приобретать следует 8 вес ед. удобрения и 3 вес ед. (в расчете на 1 га посева). При этом затраты будут минимальными и составят 56 ден. ед.

Алгоритм решения задачи с помощью Mathcad следующий:

1. Задать целевую функцию:

2. Построить поверхность . Для этого вызвать шаблон трехмерного графика и на месте метки ввести идентификатор функции . Для получения необходимого изображения произвести настройку параметров рисунка: на вкладке General (общий) диалогового окна 3D Plot Format (Формат 3-мерного графика) в группе Display As (Отобразить как) выбрать опцию Surface Plot (График поверхности); на вкладке Appearance (Появление) выбрать опции Fill Surface (Заполнить поверхность), Wireframe (Сетка), Colormap (Цветная карта) (в группе Fill Options) и Solid Color (Непрерывный цвет) (в группе Line Options); на вкладке Special включить опции Fill (Заполнить), AutoContour (Автоконтур), Draw Lines ( Провести линии); на вкладке Advanced (Дополнительно) в раскрывающемся списке Choose Colormap выбрать Blues; на вкладке QuickPlot Data (параметры графика) в полях start установить -200, в полях end установить 200; на вкладках X-Axis, Y-Axis,Z-Axis ( Оси OX,OY,OZ) включить опции Show Numbers (Показать цифры), Auto grid (Автосетка), Draw Lines (Провести линии), Auto Scale (АвтоШкала) и отключить опцию Draw Ticks (Провести метки ). Закрыть диалоговое окно 3D Plot Format. Удерживая левую кнопку мыши, вращать график, добавившись его положение, показанного на рис. 17.



Рис. 17. Пример построения поверхности в Mathcad

3. Построить линии уровня поверхности . Для этого вести шаблон трехмерного графика и на месте метки вести идентификатор . Для получения необходимого изображения произвести настройку пареметров рисунка: на вкладке General в группе Display As выбрать опцию Contour Plot (Контурный график) ; на вкладке Appearance выбрать опцию No Fill (Не заполнять), Contour Lines, Solid Color (Непрерывный цвет); на вкладке QuickPlot Data в полях start установить -5, в полях end установить 20; на вкладке Special включить опции Auto Controur, Draw Lines, Numbered (Нумерация); на вкладке Axes для координат и включить опции Auto Scale , Show Numbers и отключить опции Auto Grid, Draw Lines, а в поле Number установить 8 на вкладке X-Axes b 10 - на вкладке Y-Axes; на вкладке Z-Axes отключить опцию Show Numbers. Закрыть диалоговое окно 3D Plot Format. Нажать клавишу <Enter>, после чего получить изображение, показанное на рис. 18.



Рис. 18. Пример построения линий уровня в Mathcad

4. Задать число планов N, которые будут изображены в виде точек на координатной плоскости, а также диапазоны , , в которых могут изменяться числа (координаты точек), генерируемые функцией :

Сформировать матрицу размера , i-я строка которой будет содержать генерируемые функцией координаты -й точки удовлетворяющие систему неравенств

Отметим, что знак в операторе вводится с подпанели Логический (Boolean).

5. Изобразить множество планов на координатной плоскости. Для этого ввести шаблон декартового графика клавишей <@>. В рамке под осью абсцисс на мести метки ввести вектор , а на мести метки слева от оси ординат ввести вектор . Ниже оси абсцисс ввести границы и изменения координаты , а слева от оси ординат ввести границы и изменения координат . После нажатия клавиши получить искомое изображение, как это показано на рис. 19.

Рис. 19. Множество планов на координатной плоскости

Пример 2. Предприятие выпускает изделия двух видов, при изготовлении которых используется сырье двух типов. Запасы сырья равны 90 и 88 единиц изделия соответственно. Оптовые цены на единицу изделия каждого вида равны соответственно 12 и 10. Дана матрица норм расхода сырья:

,

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

Целевая функция данной задачи имеет следующий вид:

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

.

Целевая функция определяет в трехмерном пространстве параболоид вращения. В пересечении этого параболоида с плоскостями, параллельными координатной плоскости будут окружности с центрами на оси параболоида. Каждой такой окружности отвечает определенное значение функции . Поэтому линиями уровня функции будут концентрические окружности с общим центром в точке , являющейся проекцией оси параболоида на плоскость . Чтобы найти координаты точки и радиусы этих окружностей, преобразуем целевую функцию , выделив в ней полные квадраты относительно переменных и :

,

,

.

Итак, координаты точки равны , а радиус окружностей вычисляются по формуле .

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

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

,

Рис. 20. Множество планов и линии уровня функции

где уравнение задает граничную прямую , а уравнение задает прямую , проходящую через точку перпендикулярно прямой , равной -. Решив данную систему, найдем точку и значение целевой функции в этой точке. Итак, для получения предприятием максимальной прибыли, составляющей 26 ден.ед., следует выпустить 6 изделий первого вида и 2 изделия второго вида.

Пример 2 может быть легко решен с помощью Mathcad следующим образом:

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

Математическая модель двухсекторной экономики имеет вид:

(3.1)

, (3.2)

где нормы выбытия капитала соответственно в первом и втором секторах, - коэффициент фондоотдачи, - норма капиталовложений в первый сектор.

В модели (3.1), (3.2) по заданным параметрам , . требуется найти (определить) . Данную задачу условимся называть, как и ранее, прямой задачей математической модели двухсекторной экономики.

В данном параграфе изучается обратная задача для первоначального капитала в рамках модели (3.1), (3.2): по заданным в (3.1), (3.2) параметрам и накопленному к моменту времени капиталу найти первоначальные капиталы соответственно в первом и втором секторах.

Методом исключения найдём решение задачи (3.1), (3.2):

(3.3)

.(3.4)

Разрешим (3.3), (3.4) относительно :

(3.5)

(3.6)

Пусть в момент времени известны значения , тогда соотношение (3.5), (3.6) однозначно определяют и поставленная обратная задача полностью решена.

Решение рассматриваемой обратной задачи несколько усложняется, если значения требуется определить по , значениям в дискретные моменты времени :

Табл. 9

			…
			…
			…

В этом случае по данным таблицы 3.1. в каждый момент времени , воспользовавшись соотношениями (3.5), (3.6), находим

Решая средствами Microsoft Excel по отдельности две задачи квадратичного программирования:

(3.7)

(3.8)

найдём оценки которые в среднеквадратичном смысле является наилучшими для .

Пример Пусть и заданы таблицей 10:

Табл. 10

	1	2	3
	60000	80000	100000
	75000	80000	90000

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

Решение. Воспользовавшись соотношением (3.5), (3.6), находим:

Решая средствами Microsoft Excel задачи квадратичного программирования:

найдём .

Этапы проведённых вычислений представлены на рисунках

Рис. 21. Приближённые значения (оценки)



Рис. 22. Ограничения, указанные в задачах квадратичного программирования

Рис. 23. Параметры поиска решения

Рис. 24. Результаты расчётов

Итак, результаты решения в табличном процессоре Microsoft Excel и в математическом пакете Mathcad (Приложение А) совершенно одинаковы, что убеждает в правильности выбранной методики решения.

Заключение

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

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

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

Приложение

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

Ввод данных:

Зададим квадратичную функцию

Зададим произвольные начальные значения:

Начало блок вычислений

Опишем ограничения:

Выполним операция минимизации

Зададим квадратичную функцию

Зададим произвольные начальные значения:

Начало блок вычислений

Опишем ограничения:

Выполним операция минимизации:

Размещено на Allbest.ru

...