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

Глава 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-ой степени относительно переменных, а ограничения линейны. В ряде случаев может быть применён метод штрафных функций, сводящей задачу поиска экстремума при наличии ограничений к аналогичной задаче при отсутствии ограничений, которая обычно решается проще.

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

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

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

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

Графиком функции y = f (x) называется множество всех точек, у которых абсциссы принадлежат области определения функции, а ординаты равны соответствующим значениям функции.

Другими словами, график функции y = f (х) — это множество всех точек плоскости, координаты х, у которых удовлетворяют соотношению y = f (x).

Рис. 1 и 2: приведены графики функций у=2x+1 и у=х2−2х

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

С помощью графика можно находить значение функции в точке. Именно, если точка х = а принадлежит области определения функции y=f (x), то для нахождения числа f (а) (то есть значения функции в точке х = а) следует поступить так:

1) через точку с абсциссой х = а провести прямую, параллельную оси ординат;

2) эта прямая пересечет график функции y = f (x) в одной точке;

3) ордината этой точки и будет, в силу определения графика, равна f (а) (рис. 2).

Рис. 3

Например, для функции у=х2−2х с помощью графика (рис. 46) находим f (-1) = 3, f (0) = 0, f (1) = -l, f (2) = 0 и т. д.

График функции наглядно иллюстрирует поведение и свойства функции. Например, из рассмотрения рис. 2 ясно, что функция у=х2−2х принимает положительные значения при х < 0 и при х > 2, отрицательные — при 0 < x < 2; наименьшее значение функция у=х2−2х принимает при х = 1.

Для построения графика функции f (x) нужно найти все точки плоскости, координаты х, у которых удовлетворяют уравнению y=f (x). В большинстве случаев это сделать невозможно, так как таких точек бесконечно много. Поэтому график функции изображают приблизительно — с большей или меньшей точностью. Самым простым является метод построения графика по нескольким точкам. Он состоит в том, что аргументу х придают конечное число значений — скажем, х1, х2, x3 ,…, хk и составляют таблицу, в которую входят выбранные значения функции.

Таблица выглядит следующим образом:

Таблица 1.

Составив такую таблицу, мы можем наметить несколько точек графика функцииy=f (x). Затем, соединяя эти точки плавной линией, мы и получаем приблизительный вид графика функции y=f (x).

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

Пример 1. Для построения графика функции y = f (x) некто составил таблицу значений аргумента и функции:

Таблица 2.

Рис. 4. График на основе таблицы 2.

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

Для обоснования своего утверждения рассмотрим функцию

.

Вычисления показывают, что значения этой функции в точках -2, -1, 0, 1, 2 как раз описываются приведенной выше таблицей. Однако график этой функции вовсе не является прямой линией (он показан на рис. 5). Другим примером может служить функция y=x+l+sinрx. Ее значения тоже описываются приведенной выше таблицей.

Рис. 5.

Эти примеры показывают, что в «чистом» виде метод построения графика по нескольким точкам ненадежен. Поэтому для построения графика заданной функции, как правило, поступают следующим образом. Сначала изучают свойства данной функции, с помощью которых можно построить эскиз графика. Затем, вычисляя значения функции в нескольких точках (выбор которых зависит от установленных свойств функции), находят соответствующие точки графика. И, наконец, через построенные точки проводят кривую, используя свойства данной функции.

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

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

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

Рис. 7. Текстовые поля для ввода констант В программном коде в качестве констант в формуле используются переменные, в которые записаны числовые значения констант.

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

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

Рис. 9. График функции y=x2, выполненный в табличном процессоре Excel

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

Стандартная математическая задача оптимизации формулируется таким образом. Среди элементов x, образующих множества Ч, найти такой элемент x*, который доставляет минимальное значение f (x*) заданной функции f (x). Для того, чтобы корректно поставить задачу оптимизации необходимо задать:

1. Допустимое множество — множество ;

2. Целевую функцию — отображение ;

3. Критерий поиска (max или min).

Тогда решить задачу означает одно из:

1. Показать, что .

2. Показать, что целевая функция не ограничена снизу.

3. Найти .

4. Если, то найти .

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

Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует.

В каждом конкретном случае способ выбирается в зависимости от вида функции F (x).

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

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

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

При системе ограничений:

Чтобы найти ее оптимальное решение, нужно выполнить следующие действия:

1. Выразить аргумент, уравняв ограничения. Построить графики полученных функций. Подставить координаты произвольно взятой точки в ограничения, таким образом выяснить в каких полуплоскостях действительны ограничения. Многоугольник, заключенный в ограничивающие прямые, является ОДР.

2. Отметить на графике точку О, с координатами (|c1|,|c2|). Если О принадлежит ОДР, то она является точкой минимума. Подставив ее координаты в целевую функцию, найти искомое минимальное значение. Если О не принадлежит ОДР, построить концентрические окружности с центром в точке О. Точка, в которой окружность с наименьшим радиусом касается ОДР является точкой минимума. Точка, в которой окружность с наибольшим радиусом касается ОДР является точкой максимума.

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

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

Пример 1:

Задана целевая функция:

И ее ограничения:

Построим график целевой функции, ограничений и выделим область допустимых решений:

Рис. 10. График примера 1.

Выразим Х2, уравняв каждое ограничение:

6x2=20+7,5x1

x2 = 3,33+1,25x1

3x2=30−4,5x1

x2=10−1,5x1

Точка О (7,5;6) не принадлежит ОДР, значит она не является точкой минимума. Из точки О строим концентрические окружности. Первое пересечение с ОДР находится в точке пересечения графиков ограничений, следовательно, приравняв правые части обоих равенств, выведенных из ограничений, мы получим координаты данной точки:

3,33 + 1,25×1 = 10 — 1,5×1; x1 = 2,5; x2 = 6,25

Подставив полученные коэффициенты в целевую функцию, найдем точку минимума:

Самой дальней точкой является точка пересечения графика второго ограничения с осью ox2, следовательно координата x1 данной точки равна нулю. Подставив полученное значение в функцию ограничения, найдем точку координату x2 точки максимума равную 10-ти.

Подставив полученные коэффициенты в целевую функцию, найдем точку минимума:

Ответ:Lmin = 25,06; Lmax = 72,25.

Пример 2:

Задана целевая функция:

И ее ограничения:

Построим график целевой функции, ограничений и выделим область допустимых решений:

Рис. 11. График примера 2.

Выразим Х2, уравняв каждое ограничение:

X1+2×2=12×2=6-x½

x1+x2=9×2=9-x1

Т.к. точка О принадлежит ОДЗ, она является точкой минимума, следовательно Lmin= 0.

Самой дальней точкой является точка пересечения графика второго ограничения с осью ox1, следовательно координата x2 данной точки равна нулю. Подставив полученное значение в функцию ограничения, найдем точку координату x1 точки максимума равную 9-ти.

Подставив полученные коэффициенты в целевую функцию, найдем точку минимума:

Ответ: L min = 0; L max = 59.

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

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

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

графический нелинейный алгоритм программирование

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

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

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

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

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

Математическая модель этой задачи имеет вид: определить такие переменные х1 и х2, удовлетворяющие условиям:

при которых функция:

достигает экстремумов (минимума и максимума).

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

Программному средству, для расчетов требуются следующие входные данные: коэффициенты c1, c2, a11, a12, b1, a21, a22, b2. Возможно изменение точности вычислений, по умолчанию равной 0,01. Выходными данными является график решения задачи, координаты x1, x2точек экстремума и точки О, значения экстремумов целевой функции.

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

Рис. 11. Блок-схема реализации программы на ЭВМ Рис. 12. Блок-схема процедуры calcMax () — нахождение максимального значения целевой функции Рис. 13. Блок-схема процедуры calcMin () — нахождение минимального значения целевой функции

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

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

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

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

Рис. 14. Поля ввода данных После нажатия кнопки «Рассчитать» происходит вычисление координат точки О и точек экстремума, максимума и минимума целевой функции.

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

Рис. 16. Вывод графика.

Для того, чтобы рассчитать другую задачу, не нужно перезапускать программу. Достаточно ввести новые данные и снова нажать кнопку «Рассчитать», чтобы программа самостоятельно перезаписала новые данные в переменные, очистила график и построила новый.

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

Качество программного обеспечения — характеристика программного обеспечения (ПО) как степени его соответствия требованиям. При этом требования могут трактоваться довольно широко, что порождает целый ряд независимых определений понятия. Чаще всего используется определение ISO 9001, согласно которому качество есть «степень соответствия присущих характеристик требованиям».

Фактор качества ПО — это нефункциональное требование к программе, которое повышает качество программы.

Факторы качества программного средства (ПС) разработанного в рамках курсового проекта:

— Понятность — интерфейс и назначение ПС понятно любому человеку, знакомому с задачами оптимизации;

— Полнота — ПС располагает всеми необходимыми возможностями для решения частного случая задач нелинейного программирования;

— Краткость — интерфейс ПС состоит из одной краткой формы, без лишней, дублируемой информации;

— Портируемость — ПС не требует установки, корректно работает на системах WindowsXP/Vista/7, а для запуска необходим всего один исполняемый файл;

— Согласованностьпо всей программе и в документации используются одни и те же форматы и обозначения;

— Сопровождаемость — ПС легко изменить, отредактировав исходный кол, состоящий из трех небольших процедур, снабженных комментариями;

— Тестируемость — ПС позволяет выполнять проверку с любыми числовыми данными;

— Надёжность — при вводе корректных данных во время выполнения программы отсутствуют отказы и сбои;

— Структурированность — все элементы кода и интерфейса, сгруппированы по смыслу и имеют вложенную иерархическую структуру;

— ЭффективностьПС в среднем решает семь из десяти задач с погрешностью ±0,8; оставшиеся три из десяти задач решаются наполовину — происходит поиск только минимального значения. Соответственно оценка качества равняется 8,5.

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

В разделе 2.2 главы 2 был освещен пример решения задачи нелинейного программирования графическим метом самостоятельно, без использования программного обеспечения.

Были получены результаты: Lmin = 25,06; Lmax = 72,25.

С такими же исходными данными программное средство выдало следующий результат: Lmin = 25,9433 и Lmax = 72,2 499 999 999 987.

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

Координаты точек экстремума разнятся незначительно, что можно объяснить как округлениями, так и погрешностью программы.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

1. Акулич И. Л. Математическое программирование в примерах и задачах / И. Л. Акулич — М.: Высшая школа, 1986. — 319 с.

2. Балакирева И. А. Методические указания для выполнения курсового проекта по дисциплине «Прикладная математика» для студентов специальности «Компьютерные системы и сети» дневной и заочной форм обучения / И. А. Балакирева, А.В. СкатковСевастополь: Изд-во СевНТУ, 2003. — 15 с.

3. Бережная Е. В. Математические методы моделирование экономических систем / Е. В. Бережная, В. И. Бережной. — М.: Финансы и статистика 2008. — 232 с.

4. Вентцель Е. С. Исследование операций. Задачи, принципы методология / Е.С. ВентцельМ.: Дрофа. 2006. — 206 с.

5. Ермаков В. И. Общий курс высшей математики для экономистов / В. И. Ермаков.- М.: ИНФА, 2003 — 656 с.

6. Зайченко Ю. П. Исследование операций / Ю. П. Зайченко, С. А. Шумилова — М.: Высшая школа, 1990. — 239 с.

7. Зуховидский С. И. Линейное и выпуклое программирование / С. И. Зуховидский, Л. И. Авдеева — М.: Наука, 1964.

8. Карасев А. Н. Математические методы в экономике / А. Н. Карасев, Н. Ш. Кремер, Т. Н. Савельева, М.: Дрофа, 1996. — 354 с.

9. Карпелевич Ф. И. Элементы линейной алгебры и линейного программирования / Ф. И. Карпелевич, Л. Е. Садовский — М.: Наука, 1967. — 230 с.

10. Кузнецов Ю. Н. Математическое программирование / Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко — М.: Наука, 1980 г.

11. Лященко И. Н. Линейное и нелинейное программирования / И. Н. Лященко, Е. А. Карагодова, Н. В. Черникова. -М.: «Высшая школа», 1975. 372 с.

12. Партыкина Т. Л. Математические методы / Т. Л. Партыкина, И. И. Попов — М.: Форум, 2005. — 464 с.

13. Скатков А. В. Методические указания по изучению дисциплины «Прикладная математика», раздел «Методы глобального поиска и одномерной минимизации» / А. В. Скатков, И. А. Балакирева, Л. А. Литвинова — Севастополь: Изд-во СевГТУ, 2000. — 31с.

14. Тах Х. А.

Введение

в исследование операций/ Х. А. Тах — М.: Издательский дом «Вильяме», 2005. — 912 с.

15. Чеснокова О. В. Delphi 7. Алгоритмы и программы / О. В. Чеснокова — М.: Пресс, 2008. — 368 с.

ПРИЛОЖЕНИЕ

unit Comps;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Buttons, ExtCtrls, Series, TeEngine, TeeProcs, Chart;

type

TForm1 = class (TForm)

StaticText1: TStaticText;

Label1: TLabel;

EditK1: TEdit;

EditK2: TEdit;

StaticText2: TStaticText;

StaticText4: TStaticText;

StaticText3: TStaticText;

Edit11: TEdit;

Edit12: TEdit;

Edit21: TEdit;

Edit22: TEdit;

EditB1: TEdit;

EditB2: TEdit;

Label2: TLabel;

BitBtn1: TBitBtn;

EditLmin: TEdit;

EditLmax: TEdit;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

EditOx1: TEdit;

EditOx2: TEdit;

Label7: TLabel;

StaticText5: TStaticText;

Bevel1: TBevel;

Bevel2: TBevel;

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Label8: TLabel;

Label9: TLabel;

Label10: TLabel;

Label11: TLabel;

Label12: TLabel;

Label13: TLabel;

Label14: TLabel;

Chart: TChart;

Series1: TFastLineSeries;

Series2: TFastLineSeries;

Series3: TPointSeries;

LabeledEdit1: TLabeledEdit;

Series4: TPointSeries;

Series5: TPointSeries;

procedure BitBtn1Click (Sender: TObject);

procedure calcMin ();

procedure calcMax ();

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

k1,k2,a11,a12,b1,a21,a22,b2:double;

Ox1,Ox2,Lmin, Lmax, X, Y, E: double;

implementation

{$R *.dfm}

procedure TForm1. BitBtn1Click (Sender: TObject);

var i, j: double;

oE:boolean;

begin

k1:=strtofloat (editk1.Text); k2:=strtofloat (editk2.Text);

a11:=strtofloat (edit11.Text); a12:=strtofloat (edit12.Text); b1:=strtofloat (editb1.Text);

a21:=strtofloat (edit21.Text); a22:=strtofloat (edit22.Text); b2:=strtofloat (editb2.Text);

E:=strtofloat (labelededit1.Text);

//Очищаемграфики

Chart.Series[0]. Clear ();

Chart.Series[1].Clear ();

Chart.Series[2].Clear ();

Chart.Series[3].Clear ();

Chart.Series[4].Clear ();

//строимграфики

i:=0; j:=0;

repeat

j:=(b1-a11*i)/a12;

if j>=0 then Chart. Series[0]. AddXY (i, j);

i:=i+1;

until (j<0) or (j>30);

i:=0; j:=0;

repeat

j:=(b2-a21*i)/a22;

if j>=0 then Chart. Series[1]. AddXY (i, j);

i:=i+1;

until (j<0) or (j>30);

//точка О

Ox1:=k1;

Ox2:=k2;

editOx1.Text:=floattostr (Ox1);

editOx2.Text:=floattostr (Ox2);

Chart.Series[2]. AddXY (Ox1,Ox2);

//принадлежит ли О области допустимых значений

if ((Ox1*a11+Ox2*a12<=b1) and (Ox1*a21+Ox2*a22<=b2) and (Ox1>=0) and (Ox2>=0))

then

begin

statictext5.Caption:='Принадлежит';

oE:=true;

end

else

begin

statictext5.Caption:='Непринадлежит';

oE:=false;

end;

//считаем координаты точки пересечения графиков (самая удобная точка)

X:=(b2*a12-b1*a22)/(a21*a12-a11*a22);

Y:=(b1-a11*X)/a12;

//находим точки экстремума и считаем макс/мин целевой функции

if oE=true

then

begin

Lmin:=0;

editLmin.Text:=floattostr (Lmin);

edit1.Text:=floattostr (Ox1);

edit2.Text:=floattostr (Ox2);

calcMax ();

end

else if oE=false

then

begin

calcMin ();

calcMax ();

end;

end;

procedure TForm1. calcMin (); //находим точку минимума

var i, j, x1,x2:double;

begin

x1:=X; x2:=Y;

i:=0; j:=0;

repeat

repeat

if (a11*i+a12*j<=b1) and (a21*i+a22*j<=b2) and ((abs (Ox1-i)<=abs (Ox1-x1)) or (abs (Ox2-j)<=abs (Ox2-x2)))

then

begin

x1:=i; x2:=j;

end;

j:=j+E;

until j>50;

j:=0;

i:=i+E;

until i>50;

Lmin:=(x1-k1)*(x1-k1)+(x2-k2)*(x2-k2);

editLmin.Text:=floattostr (Lmin);

edit1.Text:=floattostr (x1);

edit2.Text:=floattostr (x2);

Chart.Series[3]. AddXY (x1,x2);

end;

procedure TForm1. calcMax (); //находимточкумаксимума

var i, j, x1,x2:double;

begin

x1:=X; x2:=Y;

i:=0; j:=0;

repeat

repeat

if (a11*i+a12*j<=b1) and (a21*i+a22*j<=b2) and ((abs (Ox1-i)>=abs (Ox1-x1)) or (abs (Ox2-j)>=abs (Ox2-x2)))

then

begin

x1:=i; x2:=j;

end;

j:=j+E;

until j>50;

j:=0;

i:=i+E;

until i>50;

Lmax:=(x1-k1)*(x1-k1)+(x2-k2)*(x2-k2);

editLmax.Text:=floattostr (Lmax);

edit3.Text:=floattostr (x1);

edit4.Text:=floattostr (x2);

Chart.Series[4]. AddXY (x1,x2);

end;

end.