Программная реализация графического метода решения задач нелинейного программирования для случая нелинейной целевой функции и линейных ограничений
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
еменные, в которые записаны числовые значения констант.
Рис. 8. Использование переменных в качестве констант
Исходя из особенностей математических операций на ЭВМ, график проще строить на основе таблицы значений аргументов и функции. Известно, что количество элементов в таблице прямо пропорционально точности графика. Учитывая высокие характеристики скорости и точности вычислений на ЭВМ, а также автоматизированность всех подсчетов, таблица значений, размерность таблицы почти не ограничена, а следовательно и точность графика очень высока. Точность также зависит от шага приращения аргумента в таблице, но ЭВМ позволяет легко оперировать числами, к примеру, с шестнадцатью знаками после запятой.
График исполненный на ЭВМ выглядит точно так же как и на любом другом носителе и может быть представлен как в двумерном пространстве, так и в изометрической проекции трехмерного пространства.
Рис. 9. График функции y=x2, выполненный в табличном процессоре Excel
1.4Постановка задачи и алгоритм реализации графического метода решения частного случая задачи нелинейного программирования
Стандартная математическая задача оптимизации формулируется таким образом. Среди элементов x, образующих множества ?, найти такой элемент x* , который доставляет минимальное значение f(x*) заданной функции f(x). Для того, чтобы корректно поставить задачу оптимизации необходимо задать:
.Допустимое множество - множество ;
2.-">Целевую функцию - отображение ;
.(">Критерий поиска (max или min).
Тогда решить задачу означает одно из:
.Показать, что .
.Показать, что целевая функция не ограничена снизу.
.Найти .
.Если , то найти .
Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции при выполнении условий
где - параметры, - ограничения, - количество параметров, - количество ограничений.
Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует.
В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).
Рассмотрим графический метод решения задачи нелинейного программирования, при линейных ограничениях и нелинейного целевой функции второго порядка.
Графический метод основан на геометрической интерпретации задачи нелинейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.
Пусть задача нелинейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные. Так как мы рассматриваем частный случай, когда целевая функция нелинейна, а ограничения линейны, целевая функция будет иметь вид:
При системе ограничений:
Чтобы найти ее оптимальное решение, нужно выполнить следующие действия:
.Выразить аргумент, уравняв ограничения. Построить графики полученных функций. Подставить координаты произвольно взятой точки в ограничения, таким образом выяснить в каких полуплоскостях действительны ограничения. Многоугольник, заключенный в ограничивающие прямые, является ОДР.
.Отметить на графике точку О, с координатами (|c1|,|c2|). Если О принадлежит ОДР, то она является точкой минимума. Подставив ее координаты в целевую функцию, найти искомое минимальное значение. Если О не принадлежит ОДР, построить концентрические окружности с центром в точке О. Точка, в которой окружность с наименьшим радиусом касается ОДР является точкой минимума. Точка, в которой окружность с наибольшим радиусом касается ОДР является точкой максимума.
.На основе полученных координат вычисляем значения экстремумов целевой функции.
1.5Функциональные тесты графического метода решения частного случая задачи нелинейного программирования
Пример 1:
Задана целевая функция:
И ее ограничения:
Построим график целевой функции, ограничений и выделим область допустимых решений:
Рис. 10. График примера 1.
Выразим Х2, уравняв каждое ограничение:
6x2=20+7,5x1
x2 = 3,33+1,25x1
x2=30-4,5x1
x2=10-1,5x1
Точка О(7,5;6) не принадлежит ОДР, значит она не является точкой минимума. Из точки О строим концентрические окружности. Первое пересечение с ОДР находится в точке пересечения графиков ограничений, следовательно, приравняв правые части обоих равенств, выведенных из ограничений, мы получим координаты данной точки:
3,33 + 1,25x1 = 10 - 1,5x1; x1 = 2,5; x2 = 6,25
Подставив полученные коэффициенты в целевую функцию, найдем точку минимума:
Самой дальней точкой является точка пересечения графика второго ограничения с осью ox2, следовательно координата x1 данной точки равна нулю. Подставив полученное значение в функцию ограничения, найдем точку координату x2 точки максимума равн