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

ВВЕДЕНИЕ

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

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

Целью данной курсовой работы является оптимизация задачи об использовании мощностей оборудования и ее решение в среде ЭТ MSExcel и математического пакета Mathcad и углубление знаний в определенной проблеме дисциплины.

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

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

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

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

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

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

Теорию и методы решения задачи оптимизации изучает математическое программирование.

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

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

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

Модель задачи оптимизации включает в себя:

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

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

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

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

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

(1)

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

– ограничения в виде неравенств,

(2)

– ограничение в виде равенства

(3)

Число неизвестных называется размерностью задачи.

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

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

Допустимое решение, при котором функция (1) принимает экстремальное значение, называется оптимальным решением.

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

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

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

В настоящее время разработано множество методов ориентированных ППП, позволяющих решить широкие классы задач математического программирования. Мощный и достаточно простой инструмент решения задач математического программирования предлагает электронный табличный процессор Microsoft Excel: пример практического использования представлены в [4] и [5].

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

1.  
   Задача линейного программирования

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

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

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

Задачей линейного программирования (ЛП) называется задача условной максимизации (минимизации) линейной целевой функции (1) при линейных ограничениях (2), (3). В литературе принят ряд специальных, эквивалентных между собой, форм записи таких задач, каждая из которых удобнее других в том или ином круге вопросов. Приведем наиболее общую формулировку задачи ЛП:

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

(4)

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

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

3. Оптимизационная задача об использовании мощностей оборудования и ее решение в среде ЭТ MSExcel и математического пакета Mathcad

3.1 Понятия и основы пакета MathCad

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

MathCad был задуман и первоначально написан Алленом Раздовым из Массачусетского технологического института (MIT), соучредителем компании Mathsoft, которая с 2006 года является частью корпорации PTC (Parametric Technology Corporation).

MathСad имеет простой и интуитивный для использования интерфейс пользователя. Для ввода формул и данных можно использовать как клавиатуру, так и специальные панели инструментов.

Некоторые из математических возможностей MathСad (версии до 13.1 включительно) основаны на подмножестве системы компьютерной алгебры Maple (MKM, Maple Kernel Mathsoft). Начиная с 14 версии используется символьное ядро MuPAD. [3]

Работа осуществляется в пределах рабочего листа, на котором уравнения и выражения отображаются графически, в противовес текстовой записи в языках программирования. При создании документов-приложений используется принцип WYSIWYG (What You See Is What You Get - "что видишь, то и получаешь").

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

MathCad достаточно удобно использовать для обучения, вычислений и инженерных расчетов. Открытая архитектура приложения в сочетании с поддержкой технологий .NET и XML позволяют легко интегрировать MathCad практически в любые ИТ-структуры и инженерные приложения. Есть возможность создания электронных книг (e-Book).

Основные возможности MathCad.

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

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

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

проведение математических расчетов (как аналитических, так и при помощи численных методов);

подготовка графиков с результатами расчетов;

ввод исходных данных и вывод результатов в текстовые файлы или файлы с базами данных в других форматах;

подготовка отчетов работы в виде печатных документов;

подготовка Web-страниц и публикация результатов в Интернете;

получение различной справочной информации из области математики.

Среди возможностей MathСad можно выделить:

Решение дифференциальных уравнений, в том числе и численными методами.

Построение двумерных и трёхмерных графиков функций (в разных системах координат, контурных, векторных и т. д.).

Использование греческого алфавита как в уравнениях, так и в тексте.

Выполнение вычислений в символьном режиме.

Выполнение операций с векторами и матрицами.

Символьное решение систем уравнений.

Аппроксимация кривых.

Выполнение подпрограмм.

Поиск корней многочленов и функций.

Проведение статистических расчётов и работа с распределением вероятностей

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

Интеграция с САПР системами, использование результатов вычислений в качестве управляющих параметров.

С помощью MathCad инженеры могут документировать все вычисления в процессе их проведения.

Вычислительный блок решения Find.

Рассмотрим решение системы n нелинейных уравнений с m неизвестными

Здесь , … , – некоторые скалярные выражения, зависящие от скалярных переменных и, возможно, от еще каких-либо переменных. Уравнений может быть как больше, так и меньше числа переменных. Заметим, что систему можно формально переписать в виде:

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

Given ключевое слово;

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

возможно, неравенств;

Find – встроенная функция для решения системы уравнений относительно переменных .

Вставлять логические операторы следует, пользуясь панелью инструментов Boolean (Булевы операторы). Если вы предпочитаете ввод с клавиатуры, помните, что логический знак равенства вводится сочетанием клавиш +. Значение функции Find представляет собой матрицу, составленную из всевозможных решений по каждой переменной, причем количество ее строк в точности равно числу аргументов Find.

Поиск экстремума функции:

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

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

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

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

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

3.2 Возможности ЭТ MSExcel

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

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

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

оперативно выполнять вычисления различной сложности;

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

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

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

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

4. Задача об спользование мощностей оборудования

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

Предприятие имеет n моделей машин М 1 ,М 2 ,…, М n различных мощностей. На этих машинах предприятие выпускает m видов продукции П 1, П 2 ,…,П m . Известны производительность каждой i-й машины по выпуску j- го вида продукции − b ij и стоимость единицы времени, затрачиваемого i-й машиной и на выпуск одного изделия j- го вида продукции − c ij . Задан план по времени и номенклатуре: T − время работы каждой машины, при этом, продукции j- го вида должно быть выпущено не менее N j единиц. Требуется составить такой план работы оборудования, чтобы обеспечить минимальные затраты на производство. Для решения поставленной задачи сформулируем её математическую модель, первоначально сведя исходные данные в следующую таблицу:

Таблица 2. Производительность машин

Машины	Производительность i-ой машины при производстве j-го вида продукции
	Виды продукции
			…
M1			…
М2			…
…	…	…	…	…
Mn			…
Минимальный объем выпуска j-го вида продукции, Nj			…

Таблица 3. Стоимость затрачиваемого времени.

Машины	Стоимость ед. времени, затрачиваемогоi-ой машины на выпуск j-го вида продукции
	Виды продукции
			…
M1			…
М2			…
…	…	…	…	…
Mn			…

1.  
   Решение в среде ЭТ MSExcel

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

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

Более подробно разберем задачу о диете на следующем примере: Обозначим х ij − время работы i-й машины (i=1,2,…,n) по выпуску j- го вида продукции (j=1,2,…,m), обеспечивающее минимальные затраты на производство при соблюдении ограничений по общему времени работы машин Т и заданному количеству продукции j-го вида Nj.

Запишем целевую функцию F(X) − затраты на производство, которую необходимо минимизировать

Сформулируем ограничения рассматриваемой задачи.

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

(6)

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

(7)

Условие не отрицательности переменных:

Таким образом, целевая функция (5) и ограничения (6−8) образуют математическую модель задачи использования мощностей оборудования.

Требуется:

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

Таблица 4. Данные для задачи использования мощностей

Машины	Производительность i-ой машины при производстве j-го вида продукции
	Виды продукции
M1	0,38	0,35	0,37	0,56
М2	0,44	0,34	0,2	0,43
М3	0,25	0,42	0,09	0,46
Минимальный объем выпуска j-го вида продукции, Nj	300	300	30	100

Таблица 5. Данные для задачи использования мощностей

Машины	Стоимость ед. времени, затрачиваемогоi-ой машины на выпуск j-го вида продукции
	Виды продукции
M1	0,21	0,22	0,41	0,32
М2	0,18	0,19	0,35	0,29
М3	0,37	0,25	0,48	0,51

Все станки работают заданное время Т, равное 1000 временных единиц.

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

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

Обозначим х ij − время работы i-го станка (i=1,2,3) по выпуску j-го вида продукции (j=1,2,3,4), обеспечивающее минимальные затраты на производство при соблюдении ограничений по общему времени работы машин Т и заданному количеству продукции N j . Определим целевую функцию F(X) – суммарные затраты на производство, которую необходимо минимизировать.

Запишем ограничения нашей задачи:

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

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

Условие не отрицательности переменных:

Таким образом, целевая функция (5´) и ограничения (6´− 8´) образуют математическую модель задачи использования мощностей оборудования.

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

Создать таблицу для ввода условий и ввести исходные данные, дополнив ее столбцами.

Рисунок 8 – MS Excel – документ решения оптимизационной задачи

Создадим ещё одну таблицу, указав в ней переменные математической модели. В ячейках В21:Е23 поместите нулевые (начальные) значения искомых переменных.

В ячейку Е25 введите формулу целевой функции. Завершив ввод получим в ячейке Е25 нулевое значение, так как пока равны нулю переменные.

Рисунок 9 – MS Excel – время работы станка по выпуску продукции

Наберем команду Данные → Поиск решения. В появившемся диалоговом окне Поиск решения необходимо выполнить необходимые установки.

Рис.10– MS Excel – диалоговое окно, ограничения

Щелкните по кнопке «Выполнить». Если решение найдено, то появится диалоговое окно:

Рис.11– MS Excel – сохранение найденного решения

Щелчок по кнопке «ОК» позволяет сохранить найденное оптимальное решение, имеющее следующий вид:

Рис.10– MS Excel – документ решения оптимизационной задачи

1.  
   Решение с помощью пакета MathCad

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

Рис.13– Mathcad– документ решения оптимизационной задачи

Рис.14– Mathcad– документ решения задачи в виде матрицы

ЗАКЛЮЧЕНИЕ

Данная работа показывает широкие возможности работы с пакетами ЭТ MS Excel и MathCad. Результатом данного исследования является разработка идеального плана диеты, с одной стороны учитывая минимальную стоимость продуктов, с другой – калорийность диеты.

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. – М.: Наука, 1986.

2. Математические методы и модели исследования операций: Учебник для студентов вузов/ под ред. В.А. Колемаева. – М.:ЮНИТИ-ДАНА, 209.

3. Супрун А.Н., Найденко В.В. Вычислительная математика для инженеров – экологов. – М.: АСВ, 1996.

4. Леоненков А.В. Решение задач оптимизации в среде MS Excel СПб.: БХВ – Петербург, 2005.

5. И. Спира. Microsoft Excel и Word 2013. Учится некогда не поздно. Издательство: Питер, 2014.

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

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