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

Введение

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

Для решения данного типа проблем, были изобретены такие программы как:

1. пакетMathCAD;

2. MicrosoftExcel;

3. PascalABC.

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

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

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

Данные методы используются для малых размерностей. Но они не подходят для расчета многомерных интегралов.

Объектом исследования является задача на нахождение экстремумов. Предметом исследования является численные методы решения (метод поразрядного поиска).

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

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

1.1 Постановка общей задачи оптимизации

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

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

При постановке задачи оптимизации могут возникать некоторые конкурирующие свойства, такие как:

расход сырья – количество продукции;

количество продукции – качество продукции.

Нахождение компромисса в данной ситуации и является решением оптимизационной задачи.

Для постановки оптимизационной задачи нужно:

Цель и объект оптимизации.Формулирование оптимизационной задачи требует экстремум только одного компонента.

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

Правильной постановкой является:

получение максимальной производительности с определенной себестоимостью;

получение минимальной себестоимости с определенной производительностью;

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

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

Характеристики оптимизации – это изменение при оптимизации величины, входящие в математическую модель объекта оптимизации, а сами соотношения, устанавливающие пределы возможного изменения этих параметров – ограничениями, ограничения задаются в форме равенств или неравенств[1].

Несмотря на разнообразные постановки задачи, структура оптимизационной задачи однотипна и включает следующие компоненты:

1. Целевая функция – мерного векторного аргумента

т.е.

2. Ограничения в виде неравенств

3. Ограничения в виде равенств

4. Область допустимых значений

Задача оптимизации в общем виде:;

Ограничения первого рода ;

Ограничения второго рода;.

Самой обобщенной постановкой оптимизационной задачи, есть экономическая оценка, которая состоит из:

1. себестоимости продукции;

2. рентабельности;

3. прибыли;

4. производительности.

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

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

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

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

1.2 Классификация задач оптимизации

Процессы которые протекаю в установившемся режиме, разделяют надва вида это –динамическая оптимизация;

статическая оптимизация.

В случае статической оптимизации, создают и реализуютоптимальную

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

Условная оптимизация – оптимизация, которая нужна для установки экстремума целевой функции когда заданы некоторые условия, накладывающийся на множество других компонентов[16].

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

Ограничения возможно применять и к экономическим, и к технологическим соображениям.

Исходя из управляющих параметров задачи делят на:

1. Одномерную оптимизацию (с одной управляющей переменной);

2. Оптимизацию (с несколькими управляющими переменными);

3. Оптимизацию при неопределённости данных;

4. Оптимизацию с дискретными и смешанными типами значений управляющих воздействий.

Оптимизацию разделяют по критериям:

а) критерий оптимальности единственный (с одним критерием);

б) с многими критериями (если критериев больше чем один).

Так же есть классификация задач параметрической оптимизации, которые разделяют на:

1. Задачи центрирования, которые определяю центры областей работоспособности;

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

3. Локальная оптимизация, производит поиск локального экстремума;

4. Глобальная оптимизация, осуществляет поиск глобальных экстремумов;

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

6. Метод дискретного математического программирования, в данном методе сокращение перебора достигает ограничение области поиска, гиперсфера маленького радиуса, у которого центр находится в данной точке;

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

8. Классификация по величине векторов;

9. Классификация, зависящая от характера искомого решения;

10. Классификация, в которой отсутствую или присутствуют ограничения на вектор изменяющихся параметров

11. Классификация, которая зависит от числа предыдущих шагов.

12. Классификация по порядку используемых производных.

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

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

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

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

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

С помощью задач линейного программирования, решается широкий спектр задач, таких как:

1. Задачи о смесях (планировка состава продукции);

2. Задачи об оптимальном использовании ресурсов с помощью производственного планирования;

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

4. Транспортные задачи.

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

В общем виде модель имеет вид:

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

(1)

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

(2)

требования не отрицательности имеет вид:

(3)

заданные постоянные величины имеют вид:

Целью данной задачи, является поиск оптимального значения функции (1), если ограничения (2) и (3) соблюдаются.

Функциональное ограничение задачи, называется система ограничений, имеющая вид:

Прямые ограничения имеют вид:

Допустимое решение задачи линейного программирования есть вектор, который удовлетворяет ограничения (2) и (3).

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

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

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

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

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

Электронные таблицы MSExcel дают возможность сделать отчет результатов, состоящий из трех столбцов:

ограничения, отображаются не только имена ограничений, но и столбцы (статус, значение, формула, разница);

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

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

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

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

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

Графический метод есть самым наглядным и удобным для пользования методом линейного программирования. Его применяют в случае задач линейного программирования двух переменных[13].

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

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

(4)

Координаты точек, которые принадлежат области определения, есть допустимым решением задач [1].

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

(5)

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

(6)

Расположена перпендикулярно относительно вектора-градиента, есть линия уровня целевой функции. Целевая функция имеет одинаковые значения в любой точки линии. Если приравнять к целевой функции константу "g", и изменив это значение, мы можем получить семейство параллельных прямых, которые являются линиями уровней [3].

Графический метод решения ЗЛП включает в себя такие этапы как:

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

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

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

2.3 Пример решения задачи линейного программирования

Для изготовления двух видов продукции А₁ и А₂используют три вида ресурсов S₁, S₂, S₃, запасы которых составляют 18, 16 и 5 условных единиц Расход ресурсов на 1единицу продукции приведен в таблице 1 (Таблица 1):

Таблица 1– Исходные данные

Виды ресурсов	Запасы ресурсов	Расходы ресурсов на 1 изд.
		А1	А2
S1	18	1	3
S2	16	2	1
S3	5	–	1
Прибыль		2 руб.	3 руб.

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

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

1. Запишем исходные данные:

- количество продукта ;

- количество продукта ;

2. запишем целевую функцию:

3. Введем ограничения:

3.1 ограничения по ресурсам

3.2 по цело численности:

3.3 по не отрицательности:

Графический метод решения задачи линейного программирования будет иметь вид:

Введем значения исходных данных в таблицыExcel, как показано на рисунке 1:

Рисунок 1 – Таблица исходных данных

С помощью команды (=МУМНОЖ(I7:J8;L3:L4) найдем значение:

Рисунок 1 – Решение ЗЛП в MS Excel (продолжение)

С помощью команды (=2*M7+3*M8) найдем значение целевой функции в точкеА:

Рисунок 1 – Значение целевой функции расположенной в точке А (продолжение)

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

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

Аналитическое решения Задачи линейного программирования в электронных таблицах Excel имеет вид:

Рисунок 3 – Решение задачи линейного программирования аналитическим методом в среде электронных таблиц MSExcel

2.5 Математическая модель графического метода решения задач линейного программирования в среде пакета MathCAD

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

1. Необходимо задать исходные данные;

2. Задать целевую функцию;

3. С помощью команды Given найти решение.

Аналитический метод решение задачи линейного программирования в среде пакета MathCAD будет иметь вид:

Рисунок 4 – Аналитический метод решения ЗЛП

Графический метод решения задачи линейного программирования в среде пакет MathCAD, рисунок 4:

Рисунок 4 – Графический метод решения задачи линейного программирования (продолжение)

Найдём координаты точек с помощью таких команд как:

Given-Find;

Обратная матрица.

Рисунок 5 – Поиск координат точки С

3. Численные методы нахождения экстремума

3.1 Численные методы нахождение экстремума

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

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

1. метод первого а так же более высоких порядков;

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

Прямые методы обладают некоторыми достоинствами, например:

а) не требуют больших затрат памяти ЭВМ;

б) обладают простыми алгоритмами и программами оптимизации;

в) дают возможность исследовать целевую функции различного уровня, даже те которые не дифференцируются[14].

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

1. Чтобы получить наиболее точное решение, нужно произвести большое количество исчислений функций;

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

3.2. Метод поразрядного поиска

Метод поразрядного поиска имеет вид усовершенствованного метода перебора. С помощью переменного шага, можно найти точку минимума функции[6].

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

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

до того момента, когда, начнет увеличиваться функция, то есть условие:

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

Процесс можно считать законченным только в том случае, если выбор точек по заданному направлению завершен, а значение шага Δ не превышает значение точности ε [11].

3.3 Метод поразрядного поиска в программе PascalABC

Методом поразрядного поиска решим задачу, которая имеет вид функции:

Покажем, что значениюзаданная точность .

Для решения данной задачи с помощью программы PascalABC, необходимо:

1. Задать переменные;

2. Указываем шаг;

3. Ввести необходимую функцию;

4. Сравниваем начальную функцию с получившейся;

5. Затем приравниваем эти функции;

6. Проверяем на завершение[7].

Решение будет иметь вид:

Рисунок 6 – Метод поразрядного поиска в PascalABC

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

Рисунок 6 – Решение задачи методом поразрядного поиска, с помощью программы PascalABC (продолжение)

3.4. Метод поразрядного поиска в электронных таблицах MSExcel

1. Введём исходные данные в таблицы, как показано на рисунке 7:

Аргумент Х;

Функция У;

Х min.

Рисунок 7 – Исходные данные в ЭТ MSExcel

С помощью команды (=МИН(B2:B50)) найдем минимальное значение функции:

Рисунок 7 – Минимальное значение функции (продолжение)

Построим график данной функции и отмети на нем точку минимума:

Рисунок 8 – Графическое изображение функции

3.5. Метод поразрядного поиска среде пакета MathCAD.

Введем исходную функцию в MathCAD и построим график, это показано на рисунке 9:

Рисунок 9 – Построение функции в среде пакета MathCAD

Рисунок 9 – Решение методом поразрядного поиска в MathCAD (продолжение)

Получаем искомые данные:

Рисунок 9 – Значения искомых данных (продолжение)

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

Для решения данной задачи были задействованы такие программы как :

пакет прикладных программ MathCAD;

электронные таблицы MSExcel;

программа PascalABC.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

программный пакет MathCAD;

электронные таблицы MSExcel;

среда программ Pascal ABC.

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

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

1. Аверьянова С.Ю., Растеряев Н.В. Содержательные задачи линейного программирования и их решение с помощью ЭТ MSEXCELи пакета MATHCAD: учебное пособие/ Южный федеральный университет. – Ростов-на-Дону: Издательство ЮФУ, 2014. – 132 с.

2. Акулич И.Д. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993.

3. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. Теория. Примеры. Задачи. – М.: Наука, 1984.

4. Жданов С.А. Методы и рыночная технология экономического управления. – М.: Дело и Сервис, 1999.

5. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. – М.: Высшая школа, 1979.

6. Колемаев В.А. Математическая экономика: Учебник для вузов. – М.:ЮНИТИ, 1998.

7. Сборник задач по математике для втузов / Под ред. А.В. Ефимова. Методы оптимизации. Уравнения в частных производных. Интегральные уравнения. – М.: Наука, 1990

8. Растеряев Н.В. Графическое решение задач линейного программирования: методичное пособие / 2011. – 14 с.

9. Алексеев В. М. Сборник задач по оптимизации: Теория. Примеры. Задачи / В. М. Алексеев, Э. М. Галлеев, В. М. Тихомиров. – М., 1984. – 288 с.

10. Романовский, И. В. Алгоритмы решения экстремальных задач / И. В. Романовский. – М.: Наука, 1977.

11. Базара, М. Нелинейное программирование. Теория и алгоритмы / М. Базара, К. Шетти. – М.: Мир, 1982.

12. Гилл, Ф. Практическая оптимизация / Ф. Гилл, У. Мюррей, М. Райт. Пер. с англ. – М.: Мир, 1985.

13. Зайченко, Ю. П. Исследование операций: учеб. пособие для вузов / Ю. П. Зайченко. – Киев: Вища школа, 1975. – 320 с.

14. Гончаров В.А. Методы оптимизации / М.: Высшее образование,2009. – 191 с.

15. [Электронный ресурс] – 2010. – Режим доступаhttp://tc.nsu.ru/uploads/met-opt-pr-zad.pdfсвободный.

16. [Электронный ресурс] – 2010. – Режим доступаhttp://math.semestr.ru/optim/optim-manual.php свободный.

17. [Электронный ресурс] – 2010. – Режим доступаhttp://www.webmath.ru/poleznoe/formules_8_22.php свободный.

18. [Электронный ресурс] – 2010. – Режим доступаhttp://studopedia.su/7_22264_metod-porazryadnogo-poiska.htmlсвободный.

19. [Электронный ресурс] – 2010. – Режим доступаhttp://all4study.ru/modelirovanie/zadacha-minimizacii-metodami-naiskorejshego-spuska-i-porazryadnogo-priblizheniya.html свободный.

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