IX Международная студенческая научная конференция Студенческий научный форум - 2017

Введение

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

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

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

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

2) Ограничения характеризуют существующие связи между искомыми пере­менными. Согласно собственному происхождению связи могут быть детерминированными и статистическими.

3) Граничные условия демонстрируют предельно допустимые значения искомых переменных.

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

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

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

1. Общая задача оптимизации

1.1 Понятие оптимизационных задач

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

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

2) в технике: расчет полета ракеты по оптимальной линии движения, а также как управлять полетом ракеты, достигая при этом наименьшего расхода топлива.

3) в социологии: как распределить с целью убавления социальной напряженности в обществе ограниченные ресурсы в стране.

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

Методы оптимизации являются частью дисциплины исследования операций.

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

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

При решении определенной задачи управления предполагается выполнить:

1) построение экономических и математических моделей для принятия решений в условиях неопределенности либо в трудных ситуациях;

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

Если критериев множество, тогда задача считается многокритериальной.

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

Последующие задачи позволят показать особенности исследования операций.

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

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

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

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

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

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

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

Следовательно, под термином «модель» предполагается сложный объект, элементам которого разрешено поставить в соответствие элементы оригинала.

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

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

Таким образом, математическая модель (в общем виде) формируется из:

1) совокупности неизвестных величин, влияя на которые, систему можно совершенствовать. Их называют планом задачи;

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

3) системы ограничений, налагаемых на неизвестные величины. Эти обстоятельства следуют из недостатка ресурсов, которыми объект располагает в рассматриваемый момент времени (ресурсы могут быть финансовыми, трудовыми и материальными). Совокупность ограничений формирует область допустимых решений.

1.2 Постановка задачи оптимизации

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

Задача на минимум будет представлена в виде:

(1)

где - целевая функция;

- допустимое множество;

для любого - допустимая точка задачи

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

Точка называется

1) точкой глобального минимума функции на множестве или глобальным решением задачи Error: Reference source not found, если для любого (2)

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

Ясно, что глобальное решение является и локальным; обратное неверно.

Понятия локального и глобального оптимума для функции одной переменной предоставим на рисунке.

Рисунок 1 – График зависимости функции на множестве Х

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

2 Задачи линейного программирования (ЗЛП)

2.1 Линейное программирование

Линейное программирование – это такой раздел математики, который основан на поиске экстремума (максимума или минимума) в заданиях, описываемых линейными уравнениями.

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

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

Рисунок 2 – График зависимости экстремума целевой функции

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

max (или min)Z=z(X), (1)

XD.

Область допустимых решений представлена системой линейных уравнений или неравенств.

Вектор Х=(х₁, х₂, .... x_п) является вектором управления или управляющим воздействия.

Допустимый план Х, при котором критерий оптимальности Z=z(X) достигает экстремального значения, называется оптимальным и обозначается через X*, экстремальное значение целевой функции через Z*=z(X*).

2.2 Виды задач линейного программирования

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

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

При выпуске продукции предприятие ограничено имеющимися ресурсами, количество которых обозначим m, а вектор ресурсов В = (b₁, b₂, ..., b_т). Известны также технологические коэффициенты a_ij, которые показывают норму расхода i-го ресурса на производство единицы j-ой продукции.

Эффективность выпуска единицы j-и продукции характеризуется прибылью p_j.

Требуется определить план выпуска продукции Х=(х₁, х₂, ..., x_п), максимизирующий прибыль предприятия при заданных ресурсах.

Целевая функция выглядит следующим образом

, (1)

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

(2)

Часто ассортимент продукции устанавливается вышестоящей организацией, т. е. его объемы должны быть заключены в некоторых границах D^н_j и D^в_j: тогда задается следующее ограничение:

(3)

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

Сохраняя прежние обозначения, запишем через α_j и с_j соответственно отпускную цену и затраты на единицу j-й продукции. В качестве критерия оптимальности могут быть приняты:

1. максимум прибыли

2) минимум затрат на производство

3) максимум выпуска в стоимостном выражении (выручки от реализации продукции)

Графический метод решения ЗЛП

Рассмотрим на примере одну из задач линейного программирования с использованием таких программ, как Excel и Mathcad (смотри рис. 3-5).

Даны следующие условия: Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола – 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол – 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола – 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

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

Задачу решим графическими и аналитическими методами.

Сформулируем математическую модель задачи.

1. Определим переменные и их количество.

Пусть x₁ – количество(штук) стульев,

x₂ – количество(штук) столов.

2. Введем целевую функцию – F(x₁,x₂) = 45x₁ + 80x₂, и которую необходимо максимизировать.

3. Ограничения:

3.1.Ограничения по материалам

5x₁ + 20x₂ 400.

3.2.Ограничения по человеческим ресурсам

10x₁ + 15x₂ 450.

3.3. Условие целочисленности:

x₁,x₂ – целое.

3.4. Условие неотрицательности:

x_1,x₂≥ 0.

Рисунок 3 Скриншот графического метода решения ЗЛП в программе Excel

Рисунок 4 Скриншот аналитического метода решения ЗЛП в программе Excel

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

Рисунок 5 Скриншот аналитического метода решения ЗЛП в программе Mathcad

Рисунок 5 Скриншот графического метода решения ЗЛП в программе Mathcad (продолжение)

Рисунок 5 Скриншот графического метода решения ЗЛП в программе Mathcad (продолжение)

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

3 Классические методы оптимизации

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

Классические методы оптимизации подразделяются на:

1) Нахождение экстремума функции одной переменной;

2) Наибольшее и наименьшее значение функции на отрезке;

3) Безусловный экстремум функции многих переменных;

4) Условный экстремум – метод функций Лагранжа;

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

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

3.1 Условный экстремум функции многих переменных. Метод функций Лагранжа

3.1.1 Понятие функции двух и более переменных

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

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

Допустим, – это множество упорядоченных пар действительных чисел (x,y).

Определение 1. Если каждой упорядоченной паре чисел по некоторому закону поставлено в соответствие единственное действительное число , то говорят, что задана функция двух переменных или. Числа называются при этом независимыми переменными или аргументами функции, а число – зависимой переменной.

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

Значение функции в точке обозначают или и называют частным значением функции двух переменных.

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

плоскость или ее часть, ограниченную одной или несколькими линиями.

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

3.1.2 Частные производные первого порядка. Полный дифференциал

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

.

Аналогично, фиксируя аргумент и придавая аргументу прираще-ние ∆, получим частное приращение функции по переменной :

.

Величина называется полным прира-щениием функции в точке .

Определение 4. Частной производной функции двух переменных по одной из этих переменных называется предел отношения соответствующего частного приращения функции к приращению данной переменной, когда последнее стремится к нулю (если этот предел существует). Классифицируется частная производная так: или ,.

Таким образом, по определению имеем [4]:

,

.

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

Пример 3. Найти частные производные функций:

.

Решение.

Чтобы найти считаем постоянной величиной и дифференцируем как функцию одной переменной :

.

Аналогично, считая постоянной величиной, находим :

.

Определение 5. Полным дифференциалом функции называется сумма произведений частных производных этой функции на приращения соответствующих независимых переменных, т.е. [1]

.

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

.

Пример 4. Найти полный дифференциал функции .

Решение. Так как , то по формуле полного дифференциала находим

.

3.1.3 Частные производные высших порядков

Частные производные и называют частными производными первого порядка или первыми частными производными.

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

Частных производных второго порядка четыре. Они обозначаются следующим образом [6]:

; ;

; .

Аналогично определяются частные производные 3-го, 4-го и более высоких порядков. Например, для функции имеем:

, и т. д.

Частные производные второго или более высокого порядка, принятые согласно различным переменным, называются смешанными частными производными. Для функции таковыми являются производные . Заметим, что в случае, когда смешанные производные непрерывны, то имеет место равенство .

3.1.4 Экстремум функции нескольких переменных. Необходимые и достаточные условия существования экстремума

Определение 7. Точка называется точкой минимума (максимума) функции , если существует такая окрестность точки , что для всех точек из этой окрестности выполняется неравенство , .

Точки минимума и максимума функции называются точками экстремума, а значения функции в этих точках – экстремумами функции (минимумом и максимумом соответственно).

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

Теорема 1 (необходимые условия экстремума). Если – точка экстремума дифференцируемой функции , то ее частные производные и в этой точке равны нулю: ,.

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

Теорема 2 (достаточное условие экстремума). Пусть функция : а) определена в некоторой окрестности критической точки , в которой и ; б) имеет непрерывные частные производные второго порядка , , . Тогда, если , то функция в точке имеет экстремум: максимум, если А0; если , то функция в точке экстремума не имеет. В случае вопрос о наличии экстремума остается открытым.

При исследовании функции двух переменных на экстремум рекомендуется использовать следующую схему:

1) Найти частные производные первого порядка: и .

2) Решить систему уравнений и найти критические точки функции.

3) Найти частные производные второго порядка: , , .

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

5) Найти экстремумы функции.

Пример 6. Найти экстремумы функции .

Решение. 1. Находим частные производные и :

, .

2. Для определения критических точек решаем систему уравнений:

Из первого уравнения системы находим: . Подставляя найденное значение y во второе уравнение, получим

, , ,

откуда

.

Находим значения y, соответствующие значениям . Подставляя значения в уравнение , получим: .

Таким образом, имеем две критические точки: и .

3. Находим частные производные второго порядка:

; ; .

4. Вычисляем значения частных производных второго порядка в каждой критической точке. Для точки имеем:

, , .

Так как

,

то в точке экстремума нет.

В точке :

, ,

и, следовательно,

.

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

5. Находим значение функции в точке :

.

3.1.5 Условный экстремум

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

Пусть – функция двух переменных, аргументы x и y которой удовлетворяют условию , называемому уравнением связи.

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

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

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

3.1.6 Метод функций Лагранжа

Функцией Лагранжа называют функцию [3]

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

Определим стационарные точки функции Лагранжа. Необходимые условия [5]:

, (1)

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

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

4 Практическая часть

Рассмотрим нахождение условного экстремума функции двух переменных методом множителей Лагранжа в среде пакета Mathcad (смотри рис. 8).

1.Сначала определим исследуемую функцию двух переменных z=f(x,y) и уравнение связи φ=σ(x,y).

2. Составим функцию Лагранжа F(x,y,λ) и найдем ее стационарные точки.

4. Затем вычислим значения первых частных производных функции σ(x,y) и вторых частных производных функции F(x,y,λ) в найденных стационарных точках.

5. Составим определитель Δ для каждой стационарной точки и, по его знаку, определить существование и характер условного экстремума.

6. Следом вычислим значения исследуемой функции z в точках условного экстремума, если они есть.

7. В заключении сделаем вывод о проделанной работе.

Рисунок 6 – Скриншот метода множителя Лагранжа

Рисунок 6 Скриншот метода множителя Лагранжа (продолжение)

Рисунок 6 Скриншот метода множителя Лагранжа (продолжение)

Рисунок 6 Скриншот метода множителя Лагранжа (продолжение)

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

ЗАКЛЮЧЕНИЕ

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

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1) Белько И. В., Кузьмич К. К. Высшая математика для экономистов. I семестр: Экспресс-курс. – М.: Новое знание, 2002. – 140 с.

2) Гусак А. А.. Математический анализ и дифференциальные уравне-ния.– Мн.: ТетраСистемс, 1998. – 416 с.

3) Гусак А. А.. Высшая математика. Учебное пособие для студентов вузов в 2-х томах. – Мн., 1998. – 544 с. (1 т.), 448 с. (2 т.).

4) Кремер Н. Ш., Путко Б. А., Тришин И. М., Фридман М. Н. Высшая математика для экономистов: Учебник для вузов / Под ред. проф. Н. Ш. Кремера.– М.: ЮНИТИ, 2002. – 471 с.

5) Растеряев Н.В., Герасименко Ю.Я. Решение оптимизационных задач в среде MATHCAD и EXCEL: Учеб. пособие- Новочеркасск: Южно-российский гос. тех. ун-т (НПИ), 2004. – 100 с.

6) Яблонский А. И., Кузнецов А. В., Шилкина Е. И. и др. Высшая математика. Общий курс: Учебник / Под общ. ред. С. А. Самаля.– Мн.: Выш. шк., 2000. – 351 с.

Код для цитирования: Скопировать