Типовые задачи оптимизации и их решение средствами Excel

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

ХАРЬКОВСКАЯ ГОСУДАРСТВЕННАЯ  АКАДЕМИЯ КУЛЬТУРЫ

 

 

 

 

Кафедра информационных технологий

 

 

 

 

 

 

 

 

 

 

 

 

 

«ТИПОВЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ И ИХ РЕШЕНИЕ СРЕДСТВАМИ EXCEL»

 

Курсовая работа

 

 

 

 

 

 

 

Выполнила:

студентка III к. I гр.

Ф-та ДИД

                                                                              Чайка Л.В.

 

  Научный руководитель:

  канд. техн. наук, доц.

  Абрамов О.М.

 

 

 

 

 

 

 

Харьков - 2010

 

Содержание

 

ВВЕДЕНИЕ

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

Объект курсовой роботы — типовые задачи оптимизации процессов современного предприятия.

Предмет исследования — технологии решение задач оптимизации в среде табличного процессора Excel.

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

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

Метод исследования: сравнительный анализ литературных источников и электронных ресурсов сети Интернет.

Опредиление задач оптимизации  подробно рассматривается в источнике [13], функции и классификации задач оптимизации описаны в работах [1, 13, 14]. Технологии решения задач в MS Excel подробно рассмотрено в работах [4, 6, 7]. Описания технологии решения задач средствами Excel рассмотрено в работах [1, 3, 8, 9, 12, 15], способ решения транспортных задач в источнике [10]. Примеры и задачи оптимизации рассмотрены в источнике [11].

 

1. ЗАДАЧИ ОПТИМИЗАЦИИ

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

Оптимизация - целенаправленная деятельность, заключающаяся в получении  наилучших результатов при соответствующих  условиях[13].

 Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно. Особенно большие трудности возникали при решении задач оптимизации процессов в химической технологии из-за большого числа параметров и их сложной взаимосвязи между собой. При наличии ВМ задача заметно упрощается[14].

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

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

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

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

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

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

4. Учет ограничений[13].

 

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

 

Математическое абстрагирование  позволяет, казалось бы, различные задачи привести к общей форме. Все задачи оптимизации можно классифицировать как задачи минимизации вещественнозначной функции f(x) N-мерного векторного аргумента x=(x₁, x₂,..., x_n), компоненты которого удовлетворяют системе уравнений h_k(x)=0, набору неравенств g_i(x) 0, а также ограничены сверху и снизу, т.е. x_i^(u) x_i x_i^(l). Функция f(x) - называется целевой функцией. Уравнения h_k(x)=0 – называеются ограничениями в виде равенств, а неравенства g_i(x) 0 - ограничениями в виде неравенств. При этом предполагается, что все фигурирующие в задаче функции являются вещественнозначными, а число ограничений конечно[14].

Задача общего вида:

Минимизировать f(x) при ограничениях

h_k(x)=0, k=1, ..., K,

g_j(x) 0 j=1, ..., J,

x_i^(u) x_i x_i^(l), i=1, ..., N

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

Задача, в которой нет  ограничений, т.е.

J=K=0;

x_i^(u)= - x_i^(l) = , i=1, ..., N,

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

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

Также один из классификационных  признаков делит оптимизационные  задачи на два класса: задачи безусловной оптимизации и задачи условной оптимизации. Первые из них характеризуются тем, что минимум функции f: R^m ® R ищется на всем пространстве:

f(x) ® min,   x О Rm.

(2)

В задачах же второго  класса поиск минимума идет на некотором  собственном подмножестве W пространства R^m:

f(x) ® min,   x О W.

(3)

Множество W часто выделяется ограничениями типа равенств

g0(x) = Q,

(4)

где g₀: R^m ® R^k, и/или ограничениями типа неравенств

g1(x) Ј Q,

(5)

где g₁: R^m ® R^l.

Другой классификационный признак  задач оптимизации — свойства функций f и множеств W. Например, задачи (2) и (3) называются линейными (часто говорят о задачах линейного программирования), если функция f — аффинная, а множество W — многогранное (множество W называется многогранным, если оно выделяется ограничениями вида (4) и (5) с аффинными функциями g₀ и g₁)[13].

 

2. ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

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

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

1. Подбор параметров  – один из самых мощных средств,  которым располагает табличный  процессор Excel. С помощью сравнительно простых приёмов можно находить оптимальные решения многих задач. Этот процесс подробно описан в 2.2.

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

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

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

3. При работе с командами Подбор параметра и Поиск решения не существует удобного способа сравнения результатов вычислений – при каждом изменении данных предыдущее значение пропадает. 
Чтобы устранить эти ограничения, разработчики Excel создали Диспетчер сценариев, помогающий работать с несколькими моделями «что – если». Командой Сервис/Сценарии можно создавать новые и просматривать существующие сценарии для решения задач, и отображать консолидированные отчеты[7].

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

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

2.1. Создание таблиц

 

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

• нажать клавишу ввода <Enter>;
• щёлкнуть на кнопке с галочкой в строке формул;
• щёлкнуть мышью на другой ячейке;
• клавишей управления курсором перевести активную клетку в другое место.

При использовании программы MS Excel существенным является соблюдение следующих правил:

• символьный текст по умолчанию выравнивается по левому краю ячейки, а числа - по правому;
• если содержимое превышает ширину клетки и соседняя справа пустая, то оно видимо на экране полностью, а если соседняя справа клетка заполнена, в левой клетке на экране присутствует только часть содержимого, поместившееся в этой клетке[8].

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

Если ошибка замечена во время ввода информации в клетку, её можно сразу же исправить. При этом допустимо использование клавиши <Backspace> (клавиши с символом ¬ в верхнем ряду алфавитно-цифровой клавиатуры). Если же ошибка обнаружена после ввода информации или просто содержимое нужно подкорректировать, то можно поступить различными способами:

• сделать нужную ячейку активной и ввести новое содержимое - прежнее содержимое заменяется новым;
• сделать активной нужную ячейку и щёлкнуть мышью в строке формул - в строке формул появляется мигающий курсор. После этого можно нужным образом откорректировать содержимое строки формул и нажать клавишу <Enter>;
• выполнить двойной щелчок на нужной клетке или сделать её активной и нажать клавишу <F2> - в клетке появляется мигающий курсор. Выполнить нужные изменения и нажать клавишу <Enter>.

Табличный процессор  позволяет созданную таблицу  оформить рамками различного типа. Для этого следует выделить нужный фрагмент таблицы, выбрать пункты меню Формат, Ячейка... и выбрать вкладку Рамка. В списке Рамка отметить, где в выделенном фрагменте должны проходить линии рамки, в списке Тип линии выбрать нужный тип, если необходимо, в раскрывающемся списке Цвет: задать цвет линии и щёлкнуть на кнопке OK.