Типовые задачи оптимизации и их решение средствами 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 ищется на всем пространстве:

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

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

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

где 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.

Оформить таблицу рамками  можно и с помощью кнопки Линии рамки панели инструментов Форматирование[12].

2.2. Подбор параметров

Большинство функций, которые  используются при моделировании, могут в данный момент отсутствовать в меню. При необходимости, отсутствующие функции можно загрузить. Для этого следует выбрать пункты меню Сервис, Надстройки… - открывается диалоговое окно «Надстройки». В открывшемся окне установить флажок у нужной программы и щёлкнуть на кнопке ОК – нужная надстройка загружается и в меню появляется соответствующий пункт.

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

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

Рис. 2. Исходная таблица

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

Доход = Цена продукции*Количество экземпляров;

Себестоимость реализованной продукции = Себестоимость продукции*Количество экземпляров;

Валовая прибыль = Доход – Себестоимость  реализованной продукции;

Накладные расходы = % накладных расходов * Доход;

Валовые издержки = Затраты на зарплату + Затраты на рекламу + Накладные расходы;

Прибыль от продажи = Валовая  прибыль – Валовые издержки.

Пусть требуется  увеличить прибыль от продажи  до 50000 р. Решить эту задачу можно различными способами: увеличить количество экземпляров; уменьшить валовые издержки за счёт уменьшения % накладных расходов, затрат на зарплату или рекламу; снижения себестоимости экземпляра продукции; увеличения цены продукции.

Посмотрим, как  это можно сделать за счёт увеличения цены продукции. Выполнить эту операцию можно в таком порядке:

1. Выбрать пункты меню Сервис, Подбор параметра – открывается диалоговое окно «Подбор параметра» (рис. 3.).
2. В поле Установить в ячейке: указывается абсолютный адрес целевой ячейки. В данном случае - $B$14. Ввести этот адрес можно с клавиатуры, либо щелчком мыши в пределах соответствующей ячейки.

Рис. 3. Диалоговое окно Подбор параметра

3. Перевести курсор в поле Значение и ввести требуемую величину (например, 50000).
4. Перевести курсор в поле Изменяя значение ячейки: и ввести туда абсолютный адрес изменяемой ячейки. В данном случае $B$16.
5. Щёлкнуть на кнопке ОК – на экран выводится результат подбора (рис. 4.).

Как видно из приведенного примера, чтобы увеличить прибыль  от продажи до 50000 р., нужно поднять цену одного экземпляра продукции до 6,86 р.

Рис. 4. Таблица и диалоговое окно Результат подбора параметра

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

2.3. Поиск решений

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

Некоторое предприятие  производит некоторую условную продукцию (Товар 1, Товар 2, …, Товар 6). Все необходимые данные сведены в таблицу (рис. 5).

В этой таблице:

Всего издержки = Издержки * Штук;

Прибыль = Всего издержки * % прибыли;

Объём продаж = Всего издержки + Прибыль.

Исходными данными являются: Издержки (издержки на производство единицы соответствующего товара), Штук и % прибыли.

В строке Суммы выводятся суммарные данные по соответствующим столбцам.

Перед предприятием стоит задача организовать производственный процесс так, чтобы не допустить превышения определённой суммы издержек (например, 4,5 млн.). Кроме того, ограничивается суммарное количество товара (например, 35000).

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

Рис. 5. Таблица Планирование загрузки оборудования

Чтобы решить эту задачу, нужно выбрать пункты меню Сервис, Поиск решения – открывается диалоговое окно «Поиск решения» (рис. 6).

В поле Установить целевую следует ввести абсолютный адрес целевой ячейки (в данном случае - $D$11). В области Равной: активизировать переключатель значению: и в поле справа от него ввести требуемое значение (в данном случае – число 4500000).

В области Изменяя ячейки: в данном случае нужно ввести абсолютный адрес блока ячеек $C$4:$C$9.

Рис. 6. Диалоговое окно Поиск решения

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

Рис. 7. Диалоговое окно Добавление ограничений

Первым является ограничение  на максимально допустимое суммарное количество товаров – не более 35000. Поэтому в поле Ссылка на ячейку: следует ввести абсолютный адрес $C$11, выбрать оператор <=, в поле Ограничение: ввести значение 35000. Затем щёлкнуть на кнопке Добавить и ввести второе ограничение (адрес блока ячеек $C$4:$C$9, в списке операторов – целое). После этого щёлкнуть на кнопке ОК – возвращается окно «Поиск решения». Введённые ограничения записаны в поле Ограничения:.

Затем щелчком на кнопке Параметры следует открыть диалоговое окно «Параметры поиска решения» (рис. 8) и в нём задать нужные параметры (для данной задачи, например, следует ввести величину относительной погрешности, равную 0,001) и щёлкнуть на кнопке ОК – возвращается окно «Поиск решения»[4].

Рис. 8. Диалоговое окно Параметры поиска решения

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

В диалоговом окне предлагается Сохранить найденное решение или Восстановить исходные значения. В списке Тип отчета можно задать, а затем сохранить отчёт. Отчёт создаётся на отдельном листе. Пример такого отчёта для типа Результаты приведен на рис. 10 и рис. 11.

Рис. 9. Таблица Планирование загрузки оборудования с найденным решением

Рис. 10. Отчёт (начало отчёта)

В области Изменяя ячейки: в данном случае нужно ввести абсолютный адрес блока ячеек $C$4:$C$9.

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

Рис. 11. Отчёт (продолжение отчёта)

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

В области Целевая ячейка (Значение) отображаются абсолютный адрес целевой ячейки, её имя, исходное значение и результат решения. Подобные сведения отображаются в области Изменяемые ячейки (исходные значения и результаты решения по типам товаров).

В области Ограничения отображаются ограничения, которые были заданы при решении задачи, результирующие значения, статус и разница[11].

2.4. ДИСПЕТЧЕР СЦЕНАРИЕВ  «ЧТО – ЕСЛИ»

2.4.1. Создание  сценария.

Создание сценариев  происходит следующим образом:

• Выполнить команду Сервис/Сценарии. Открывается изображение окна диалога Диспетчер сценариев.

• Нажать кнопку Добавить, чтобы создать первый сценарий. Откроется окно диалога Добавление сценария.

• Ввести Лучший вариант (или любое другое имя) в поле Название сценария, затем с помощью окон диалога ввести изменяемые ячейки. Когда этот сценарий будет готов, ввести следующий.
• Нажать кнопку Добавить, чтобы создать второй сценарий. Ввести название Худший вариант. После завершения создания двух сценарием можно приступить к просмотру результатов.
• Закрыть окно диалога Диспетчер сценариев кнопкой Закрыть.
• Просмотр сценария Excel сохраняет сценарии вместе с листом текущей книги, и просмотр их командой Сервис /Сценарии возможен только при открытии данного листа. Просмотр сценария выполняется следующим образом:
• Выполнить команду Сервис/Сценарии. Открывается окно диалога:
• Выбрать из списка сценарий для просмотра.
• Нажать кнопку Вывести. Excel заменяет содержимое ячеек листа значениями из сценария и отображает результаты на листе.
• Выбрать из списка другие сценарии и воспользоваться кнопкой Вывести для сравнения результатов моделей «что – если». После завершения нажать кнопку Закрыть. Значения последнего активного сценария остаются в ячейках листа[3].

2.4.2. Создание отчетов по сценарию

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

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

3. Примеры решения задач оптимизации

3.1. Транспортная  задача

Некоторая фирма имеет 4 фабрики и 5 центров распределения её товаров. Фабрики располагаются в четырёх разных городах. Условно назовём их соответственно Фабрика 1, Фабрика 2, Фабрика 3, Фабрика 4. Их производственные возможности составляют соответственно 200, 150, 225 и 175 единиц продукции ежедневно. Распределительные центры располагаются в пяти городах. Условно назовём их Центр 1, Центр 2, Цунтр3, Центр 4, Центр5. Потребности их соответственно составляют 100, 200, 50, 250 и 150 единиц продукции ежедневно. Хранение на фабрике не поставленной в центр распределения единицы продукции обходится в 3,75 грн в день, а штраф за просрочку поставки заказанной потребителем в центре распределения единицы продукции, но там не находящейся, равен 12,5 грн в день. Стоимость перевозки единицы продукции с фабрик в пункты распределения приведены в таблице 1.

Таблица 1

Транспортные расходы

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

Данная модель сбалансирована, т. е. суммарный объём произведенной продукции (200+150+225+175=750) равен суммарному объёму потребностей в ней (100+200+50+250+150=750). Поэтому здесь не нужно учитывать издержки, связанные как со складированием, так и с недопоставками продукции. В противном случае в модель следует ввести: