Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Математика / Другие методич. материалы / Методические указания решения нелинейных оптимизационных профессиональных задач способами математического программирования.
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Математика

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

библиотека
материалов

18

ОГЛАВЛЕНИЕ







Введение

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

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

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

Задачи курсовой работы:

  1. Изучить специальную литературу по изучению математических методов решения задач нелинейного программирования;

  2. Рассмотреть ключевые понятия:

    • Математическое программирование;

    • Задачи нелинейного программирования, их классификация;

    • Различные методики решения.

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

  4. Реализация оптимального метода в программной среде.

Глава 1. Постановка задачи

1.1 Фундаментальные понятия и определение «математического программирования»

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

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

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

В общем виде классификация задач нелинейного программирования представлена в таблице 1:

Таблица 1. Классификация задач нелинейного программирования

Вид F(x)

Вид функции ограничений

Число переменных

Название задачи

Нелинейная

Отсутствуют

1

Безусловная однопараметрическая оптимизация

Нелинейная

Отсутствуют

Более 1

Безусловная многопараметрическая оптимизация

Нелинейная или линейная

Нелинейные или линейные

Более 1

Условная нелинейная оптимизация



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

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

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

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

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

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



при условии, что её переменные удовлетворяют соотношениям:





где f и – некоторые известные функции n переменных, а bi – заданные числа.

Обычно на некоторые переменные x1, x2, …,xn накладывается условие неотрицательности. Кроме того, ограничением может служить условие целочисленности решения для ряда переменных.

В данной курсовой работе рассмотрим задачу условной нелинейной оптимизации:

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

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

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

или  

Минимум этой функции находится при ограничениях:



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

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

,

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

(в данной задаче m=1, n=2).

На переменные накладывается условие неотрицательности.

3.1 Метод множителей Лагранжа.

Чтобы найти решение задачи нелинейной оптимизации методом множителей Лагранжа, существует следующий алгоритм:

  1. Оставить функцию Лагранжа;

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

  3. Решить полученную систему уравнений и тем самым определить стационарные точки функции Лагранжа;

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

Функция Лагранжа имеет вид

,

где – множители Лагранжа.

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

Так как ограничение дано в виде неравенства, задача предусматривает отклонение от алгоритма:

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



  1. Находят точки условного экстремума целевой функции F при условиях:

  2. Из найденных точек выбираем подходящие нам по условиям и ограничениям.

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

=-2,5.

>-141 – точка не соответствует условиям.

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

Для рассматриваемой задачи функция Лагранжа следующая:

.

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



Составим расширенную матрицу и решим систему матричным методом:



A=, X=







X=A-1*B

==

Решив систему линейных уравнений, получим стационарную точку с координатами x1=, x2=, λ=.


– точка соответствует условиям.

Рассмотрим достаточные условия экстремума, для чего найдём С==2, D==2, E==0. Составим определитель второго порядка Так как то точка с координатами x1=, x2= является точкой минимума.

Чтобы произвести пересчёт задачи при изменении N, необходимо только в векторе B изменить значение N, например:hello_html_682c3bf.gifhello_html_342522fb.gif







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

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

3.2 Квадратичное программирование

Для решения задачи квадратичного программирования



при ограничениях





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

  1. Составить функцию Лагранжа, она записывается в форме:



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



– локальных условий Куна-Такера (необходимых и достаточных условий существования седловой точки функции Лагранжа).

  1. Преобразовать неравенства системы в равенства, для чего добавить к левой части ограничений, если оно меньше или равно правой ( вычесть из неё, если оно больше или равно правой части) дополнительные неизвестные ). В результате система запишется в виде:





  1. Используя симплекс-метод (метод искусственного базиса), найти координаты седловой точки, решая систему с учётом условий, либо убедиться, что ограничения задачи противоречивы.

Искусственные переменные y 1 вводятся в те уравнения, где это необходимо.

  1. Записать оптимальное решение исходной задачи и вычислить значение целевой функции

Кроме рассмотренного подхода к решению задач квадратичного программирования , существует ряд других методов, таких как: метод Била, метод Баранкина-Дорфмана, метод М.Франка и Ф. Вулфа.

Итак, для решения рассматриваемой задачи, представим функцию в виде

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

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

Функция Лагранжа уже была составлена ранее, ей и воспользуемся:

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







Приведём к равенствам правые части ограничений посредством ввода дополнительных неизвестных :



Исходя из равенств можно определить:



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



и условии неотрицательности всех неизвестных. Разрешив систему относительно базисных неизвестных, получим:



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







-x1

-x2

-v1

-v2

1

y1

2

0

-1

-1

0

-3

y2

0

2

-1

0

-1

-1

W

-1

-1

0

0

0

-N

F

F1

0

0

0

0

0

0

M

-2

-2

2

1

1

4

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

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





-x1

y2

-v1

-v2

1

y1

2

0

-1

-1

0

-3

x2

0

1/2

-1/2

0

-1/2

-1/2

W

-1

1/2

-1/2

0

-1/2

(-2N-1)/2

F

M

-2

1

1

1

0

3



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



y1

-v1

-v2

1

x1

1/2

-1/2

-1/2

0

-3/2

x2

0

-1/2

0

-1/2

-1/2

W

1/2

-1

-1/2

-1/2

-N-2

F

M

1

0

0

0

0



w

-v1

-v2

1

x1

1/2

-1/4

1/4

(N-1)/2

x2

1/2

1/4

-1/4

(N+1)/2

λ

-1

1/2

1/2

N+2

F

M

0

0

0

0

Оптимальное решение задачи следующее: x1=(N-1)/2, x2=(N+1)/2, λ=N+2, w=0, v1=0, v2=0, y1=0, y2=0. Это решение удовлетворяет условию


Следовательно точка (x*, λ*)=(, ,N+2) является седловой точкой функции Лагранжа исходной задачи, x*=(,) – оптимальное её решение.



Из выведенной формулы видно, что чем выше N, тем выше минимум функции.

При N=141, x1=70, x2=71 является точкой минимума и минимальная себестоимость

При N=489, x1=244, x2=245 является точкой минимума и минимальная себестоимость .

Метод квадратичного программирования является одним из самых лёгких способов решения оптимизационных задач нелинейного программирования.

3.3 Графический метод решения задачи

Итак, вспомним условия задачи. Целевая функция имеет вид



при ограничениях



ОДР ограничена линейной функцией x1+x2 N и координатными прямыми, является неограниченным многогранником.

Положив имеем , приведём это уравнение к виду . Это уравнение окружности с центром в точке О( и радиусом . Изменяя значение Q, будем получать окружности различных радиусов, а следовательно и различные значения функции. Но из данной формулы видно, что чем больше значение функции, тем больше радиус найденной окружности. Так как целью задачи является отыскание минимума функции, следовательно решение данной задачи будет находиться в точке соприкосновения окружности и линейной функции ограничения. Так как центр окружности находится в точке О(, а вектор функции ограничения постоянен (то уравнение прямой на которой располагается точка минимума, следующее: . Так как точка минимума будет находить на пересечении прямой x1+x2 = N и , то точка с координатами x1=, x2= является точкой минимума.



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

3.4 Информационные технологии Exsel решения задач нелинейного программирования

Решение задач нелинейного программирования в Exsel осуществляется командой Поиск решения, в которой реализованы два метода: метод Ньютона и метод сопряженных градиентов. В методе Ньютона для определения направления и шага перемещения в новую точку используются вторые производные. Использование вторых производных ведет к большому объему вычислений на каждом шаге итерационного процесса, но сокращает число шагов для достижения оптимального решения. Метод сопряженных градиентов использует только первые производные, что приводит к сокращению объёма вычислений на каждом шаге итерационного процесса, но и к возможному увеличению числа шагов.

Чтобы решить задачу, введём данные в таблицу, подставив вместо N любое положительное число, например 141:

Ограничения и другие показатели

Переменные

Левая часть ограничений

Вид ограничений

Правая часть ограничений

x1

x2

Ресурс

=C20

=D20

=C14+D14

>=

141

Себестоимость

=3*C20+C20*C20

=D20+D20*D20

=C15+D15

 

 

В ячейках показаны формулы ограничения и целевой функции. Далее осуществляем Поиск решения:hello_html_mbce65a7.png

Выставляются параметры:

и полученный результат:hello_html_fcc6b5a.png

hello_html_m2e81150d.gif



,



что соответствует результатам, полученным при решении данной задачи представленными ранее методами.

Заключение

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

В первой главе были даны формулировка понятий «математическое программирование», «оптимизационные задачи нелинейного программирования», была описана общая классификация задач НЛП. Так же была представлена общая постановка задачи нелинейного программирования. Был предоставлен пример задачи НЛП для дальнейшего её исследования.

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

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

Литература

  1. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике. М.: ДИС, 2001.

  2. Костевич Л.С. Математическое программирование. М.:ООО «Новое знание», 2003.

  3. Кундышева Е.С. Математическое моделирование в экономике: Учебное пособие/ Под науч. ред. проф. Б.А. Суслакова. М.: Издательско-торговая корпорация «Дашков и К», 2004.


Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 20.06.2016
Раздел Математика
Подраздел Другие методич. материалы
Просмотров498
Номер материала ДБ-127167
Получить свидетельство о публикации
Похожие материалы

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