Поиск решений. Исследование операций в экономике

Лабораторная работа № 6

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

Цель работы: освоить навыки работы с надстройкой Microsoft Excel «Поиск решений»

Задачи работы: научиться решать задачи линейного программирования (ЛП) в табличном редакторе Microsoft Excel.

 

1 Общие положения

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

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

Если команда Поиск решения или группа Анализ отсутствует, необходимо загрузить надстройку«Поиск решения».

1. Щелкните значок Кнопка Microsoft Office , щелкните Параметры Excel, а затем выберите категорию Надстройки.
2. В поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти.
3. В поле Доступные надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК.

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

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

1. Ввести условие задачи:
1. создать экранную форму для ввода условия задачи:
• переменных,
• целевой функции (ЦФ),
• ограничений,
• граничных условий;
2. ввести исходные данные в экранную форму:
• коэффициенты ЦФ,
• коэффициенты при переменных в ограничениях,
• правые части ограничений;
3. ввести зависимости из математической модели в экранную форму:
• формулу для расчета ЦФ,
• формулы для расчета значений условий;
4. задать ЦФ (в окне "Поиск решения"):
• целевую ячейку,
• направление оптимизации ЦФ;
5. ввести ограничения и граничные условия (в окне "Поиск решения"):
• ячейки со значениями переменных,
• граничные условия для допустимых значений переменных,
• соотношения между правыми и левыми частями условия.
2. Решить задачу:
1. установить параметры решения задачи (в окне "Поиск решения");
2. запустить задачу на решение (в окне "Поиск решения");
3. выбрать формат вывода решения (в окне "Результаты поиска решения").

 

2 Содержание работы

2.1 Рассмотрим пример решения задачи

2.1.1 Ввод исходных данных

Экранная  форма для ввода условий задачи вместе с введенными в нее исходными данными представлена на рисунке 1.

Рисунок1. Экранная форма задачи

В экранной форме на рисунке 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel.

2.1.2 Ввод зависимостей из математической модели в экранную форму

В ячейку G6, в которой будет отображаться значение ЦФ, необходимо ввести формулу, по которой это значение будет рассчитано. Согласно задаче, значение ЦФ определяется выражением:

Используя обозначения  соответствующих ячеек в Excel, формулу для расчета ЦФ можно записать как сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3, D3, E3, F3), на соответствующую ячейку, отведенную для коэффициентов ЦФ (B6, C6, D6, E6, F3), то есть:

Чтобы задать формулу необходимо в ячейку G6 ввести следующее выражение и нажать клавишу "Enter"

=СУММПРОИЗВ(B$3:F$3;B6:F6)

где символ $ перед номером строки 3 означает, что при копировании этой формулы в другие места листа Excel номер строки 3 не изменится.

После этого  в целевой ячейке появится 0 (нулевое значение) (рисунок 2).

Рисунок 2. Экранная форма задачи после ввода формулы для ЦФ (курсор в ячейке G6)

 

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

 

2.1.3 Дальнейшие действия производятся в окне "Поиск решения", которое вызывается на панели Данные ► Анализ (рисунок 3):

• поставьте курсор в поле "Установить целевую ячейку";
• введите адрес целевой ячейки $G$6;
• введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке "максимальному значению".

 

Рисунок 3 Окно "Поиск решения"

2.1.4 Ввод ограничений и граничных условий

В окно "Поиск решения" в поле "Изменяя ячейки" впишите адреса $B$3:$F$3. Необходимые адреса можно вносить выделением мышью соответствующих ячеек переменных.

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

• Нажмите кнопку "Добавить", после чего появится окно "Добавление ограничения"
• В поле "Ссылка на ячейку" введите адреса ячеек переменных $B$3:$F$3.
• В поле знака откройте список предлагаемых знаков и выберите >=.
• В поле "Ограничение" введите адреса ячеек нижней границы значений переменных, то есть $B$4:$F$4.
• Нажмите кнопку "Добавить" в окне "Добавление ограничения".
• В поле "Ссылка на ячейку" введите адрес ячейки $G$10
• В соответствии с условием задачи выбрать в поле знака <=.
• В поле "Ограничение" введите адрес ячейки правой части рассматриваемого ограничения $I$10.
• Аналогично введите оставшиеся условия
• Подтвердите ввод всех перечисленных выше условий нажатием кнопки OK.

Окно "Поиск решения" после ввода всех необходимых данных задачи представлено на рисунке 4

Рисунок 4 Окно «Поиск решения» после ввода всех ограничений»

 

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

 

2.1.5 Задача запускается на решение в окне "Поиск решения". Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна "Параметры поиска решения" (рисунок 5).

 

Рисунок 5. Параметры поиска решения

Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).

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

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

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

Параметр "Сходимость" применяется только при решении нелинейных задач.

Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.

Подтвердите установленные параметры нажатием кнопки "OK".

2.1.6 Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить".

После запуска  на решение задачи на экране появляется окно "Результаты поиска решения" с результатами решения (рисунок 6).

Рисунок 6 Результаты поиска решения

Если  при заполнении полей окна "Поиск решения" были допущены ошибки, не позволяющие Excel решить задачу или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено.

В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы". Они необходимы при анализе полученного решения. Для получения ответа (значений переменных, ЦФ и левых частей ограничений) необходимо нажать кнопку "OK". После этого в экранной форме появится оптимальное решение задачи (рисунок 7).

Рисунок 7 Экранная форма задачи после получения решения

2.2 Решить задачу из приложения А (по указанию преподавателя).

 

3 Требования к отчету

Отчет по данной работе должен содержать:

• название работы, ее цель и задачи;
• ход выполнения работы;
• ответы на контрольные вопросы.

 

4 Контрольные вопросы

1. Каковы основные этапы решения задач ЛП в MS Excel?
2. Каков вид и способы задания формул для целевой ячейки и ячеек левых частей ограничений?
3. В чем смысл использования символа $ в формулах MS Excel?
4. Каким образом в MS Excel задается направление оптимизации ЦФ?
5. Какие ячейки экранной формы выполняют иллюстративную функцию, а какие необходимы для решения задачи?
6. Поясните общий порядок работы с окном "Поиск решения".
7. Каким образом можно изменять, добавлять, удалять ограничения в окне "Поиск решения"?
8. Объясните смысл параметров, задаваемых в окне "Параметры поиска решения".

Приложение А

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

№ варианта	Математическая модель
1
2
3
4
5
6
7
8
9