Теоретическая часть. Поиск оптимального решения

Лабораторная работа №2.

Поиск оптимального решения. Решение задач оптимизации в MS Excel.

Цель работы: Научиться решать задачи оптимизации различных типов
средствами MS Excel.

Требования к содержанию, оформлению и порядку выполнения

Для выполнения лабораторной работы необходимо создать новую рабочую книгу Excel под именем «Ваша фамилия, Лабораторная работа №2, (например: «Иванов И.П. Лабораторная работа №2»).

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

Рабочие листы рабочей книги должны быть именованы Задание1, Задание2, Задание3. Результаты решения задач поместите в файл отчета.

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

Теоретическая часть

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

Все оптимизационные задачи имеют три свой­ства:

· имеется единственная максимизируемая или минимизируемая цель (прибыль, производительность, ре­сурсы и т.д.);

· имеются ограничения, выражающиеся, как правило, в виде неравенств (напри­мер, объем используемого сырья не может превышать объем имеющегося сы­рья на складе, или время работы станка за сутки не должно быть больше 24 часов минус время на обслуживание);

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

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

* Математическую модель;

* Целевую функцию.

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

Целевая функция f(x) представляет собой числовую характеристику, максимальному или минимальному значению которой соответствует оптимальное решение.

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

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

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

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

(1)

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

(2)

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

Найти (3)

при условии (1) и

(4)

Условие (4), указывает на неотрицательность выпуска продукции.

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

Найти (5)

при условии (6) (7)

(8)

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

Обозначим через степень влияния на прибыль объема выпуска j-го изделия. Тогда целевая функция задачи может быть записана в следующем виде:

(9)

а сама задача примет вид

(10)

при условиях (6), (7), (8).

Заметим, что если , то прибыль не зависит от объема выпуска j-го изделия.

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

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

· Оформление рабочего листа (ввод на рабочий лист исходных данных и формул);

· Вызов диалогового окна Поиск решения.

· Указание целевой ячейки (ячейки в которой хранится целевая функция);

· Указание изменяемых значений;

· Указание условий (ограничений);

· Изменение настроек поиска решения (при необходимости);

На этапе оформления необходимо:

1.Ввести исходные данные в ячейки рабочего листа Excel;

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

3.Сформировать на рабочем листе EXCEL элементы математической модели и целевую функцию.

Рис.1. Пример оформления рабочего листа для решения задачи оптимизации связанной с минимизацией расходов на перевозки (транспортная задача).

Когда рабочий лист будет оформлен, нужно активизировать компонент Поиск решения. В результате откроется диалоговое окно Поиск решения (рис.2).

Рис.2. Вид диалогового окна Поиск решения.

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

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

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

С помощью кнопки Добавить можнодобавлять ограничения, а с помощью двух других можно изменять имеющиеся ограничения или удалять. После нажатия на кнопку Добавить открывается диалоговое окно Добавление ограничения (рис.3).

Рис.3. Вид диалогового окна Добавление ограничения.

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

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

Рис.4. Вид диалогового окна Результаты поиска решения.

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

· Сохранить найденное решение на место изменяемых ячеек;

· Восстановить исходные значения в изменяемых ячейках;

· Создать несколько отчетов по процедуре поиска. Причем можно выбрать три типа отчетов (используя клавишу Ctrl или Shift):

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

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

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

· Сохранить сценарий. Для сохранения решения в виде сценария, который можно будет использовать в с помощью диспетчера сценариев Microsoft Excel.

С помощью кнопки Параметры диалогового окна Поиск решения (рис.2) можно вызвать диалоговое окно Параметры поиска решения (рис.5) и с помощью его элементов изменить параметры работы инструмента Поиск решения.

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

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

С помощью элементов диалогового окна Параметры поиска решения можно изменить следующее:

· Максимальное время. Если появится сообщение о том, что время на поиск решение истекло, то нужно добавить время на поиск решения;

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

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

· Допустимое отклонение. Позволяет установить максимальное отклонение в % для целочисленных итераций.

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

· Линейная модель. Служит для ускорения поиска решения линейной задачи оптимизации. Можно использовать, если все зависимости в модели линейные. Нельзя использовать эту опцию, если изменяемые ячейки умножаются или делятся или в задаче используется возведение в степень.

· Неотрицательные значения. Позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых не были установлены ограничения.

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

· Показывать результаты итераций. Позволяет просматривать результаты отдельных итераций.

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

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

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

Поиск по сайту: