Понятие графика функции и его представление на ЭВМ. Алгоритм реализации, блок-схема и функциональные тесты графического метода решения частного случая задачи нелинейного программирования, его математическая модель. Диалог программы с пользователем.
Краткое сожержание материала:

Размещено на

19

Размещено на

Оглавление

ВВЕДЕНИЕ

Глава 1. Графический метод решения задач нелинейного программирования

1.1 Оптимизация в математике. Нелинейное программирование. Частный случай задачи нелинейного программирования

1.2 Понятие графика функции

1.3 Способ представления графика функции на ЭВМ

1.4 Постановка задачи и алгоритм реализации графического метода решения частного случая задачи нелинейного программирования

1.5 Функциональные тесты графического метода решения частного случая задачи нелинейного программирования

1.6 Экономическая суть

Глава 2. Математический анализ графического метода решения задач нелинейного программирования

2.1 Математическая модель метода

2.2 Входные и выходные данные

2.3 Блок-схема графического метода решения задач нелинейного программирования

Глава 3. Программная реализация графического метода решения задач нелинейного программирования для случая целевой функции второго порядка и линейных ограничений

3.1 Организация диалога программы с пользователем

3.2 Анализ качества программного средства

3.3 Анализ результатов решения задачи

ЗАКЛЮЧЕНИЕ

Список литературы

Приложение



ВВЕДЕНИЕ

Задачи линейного программирования были первыми подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 г. Ж. Фурье и затем в 1947 г. Дж. Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции -- симплекс-метод, ставший основным при решении задач линейного программирования.

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одновременно с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо то и другое нелинейны. В 1951 г была опубликована работа Куна и Таккера, в которой приведены необходимые и достаточные условия оптимальности для решения задач нелинейного программирования. Эта работа послужила основой для последующих исследований в этой области.

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

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

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

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

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

Для выполнения цели требуется осуществить следующие задачи:

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

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

- составить математическую модель задачи, определить входные и выходные данные;

- составить блок-схему решения задачи;

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

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

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

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

Экстремум-- максимальное или минимальное значение функции на заданном множестве. Точка, в которой достигается экстремум, называется точкой экстремума. Соответственно, если достигается минимум -- точка экстремума называется точкой минимума, а если максимум -- точкой максимума.

Нелинейная функция -- функция, которую нельзя выразить в линейном виде:

.

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

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

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

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



Глава 1. Графический метод решения задач нелинейного программирования

1.1 Оптимизация в математике. Нелинейное программирование. Частный случай задачи нелинейного программирования

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

В процессе проектирования ставится обычно задача определения наилучших, в некотором смысле, структуры или значений параметров объектов. Такая задача называется оптимизационной. Если оптимизация связана с расчетом оптимальных значений параметров при заданной структуре объекта, то она называется параметрической оптимизацией. Задача выбора оптимальной структуры является структурной оптимизацией.

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

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

То есть нелинейное программирование это случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.

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

где  -- параметры,  -- ограничения,  -- количество параметров,  -- количество ограничений.

Задачи нелинейного программирования на практике возникают довольно часто, когда, например, затраты растут не пропорционально количеству закупленных или произведённых товаров.

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

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

В данном проекте р...