Поиск решения средствами MS Excel

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

Методические указания

Команда «Подбор параметра» и надстройка «Поиск решения» являются основными инструментам анализа данных.

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

Для вызова Подбора параметра следует выделить ячейку с формулой, которая должна принять заданное значение и выбрать команду Сервис–Подбор параметра (рис. 9.1).

 

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

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

Пример 1. Используя «Подбор параметра», определите при каких значениях аргумента функция , примет значение 0,5.

Решение. Выделим ячейку с формулой, которая должна принять значение 0,5, затем выберем команду Сервис – Подбор параметра.

Для нахождения значения аргумента в диалоговом окне Подбор параметра введем ссылки на соответствующие ячейки (рис. 9.2) и нажмем кнопку ОК.

 

Рис. 9.2. Пример нахождения аргумента функции

В результате получим, что решение будет найдено (рис. 9.3) и аргумент примет значение (рис. 9.4) равное 2,249956.

 

Рис. 9.3. Результат подбора параметра

 

Рис. 9.4. Полученное значение аргумента X

 

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

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

1. Ассортимент продукции. Максимизация выпуска товаров при ограничениях на сырье для производства этих товаров.

2. Штатное расписание. Составление штатного расписания для достижения наилучших результатов при наименьших расходах.

3. Планирование перевозок. Минимизация затрат на перевозку товаров при условии удовлетворения потребностей покупателей.

4. Составление смеси. Получение заданного качества смеси при наименьших расходах.

Эти задачи имеют три свойства:

1. Наличие целевой функции (ЦФ).

2. Ограничения, выражающиеся, как правило, в виде неравенств.

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

Одним из подходов к решению таких задач является использование надстройки «Поиск решения» из пакета электронных таблиц Microsoft Excel (Сервис – Поиск решения). Диалоговое окно Поиск решения представлено на рис. 9.5.

 

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

 

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

В поле Изменяя ячейки следует задать адреса или имена ячеек, содержащих искомые значения. Ячейки должны влиять (прямо или косвенно) на значение целевой функции. Допускается до 200 изменяемых ячеек. Кнопка Предположить позволяет автоматически определить все ячейки, влияющие на ЦФ.

В поле Ограничения с помощью кнопок Добавить, Изменить, Удалить надо сформировать список условий.

Кнопка Выполнить инициализирует процесс поиска оптимального решения. Чрезмерно длительные вычисления можно прервать клавишей Esc.

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

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

 

Можно настроить следующие параметры поиска решения:

1. Максимальное время – это время в секундах, которое может быть затрачено на поиск решения. Максимально допустимое значение – 32767.

2. Предельное число итераций (шагов) – количество действий (вычисление очередного значения и проверка, насколько оно подходит в качестве ответа), которые могут быть сделаны. Максимально допустимое значение – 32767.

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

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

5. Сходимость – относительное изменение значения в целевой ячейке за последние пять шагов. Если эта величина становится меньше указанного числа, поиск прекращается. Задается числом в диапазоне от 0 до 1. Параметр применим только к нелинейным задачам. Уменьшение значения в поле сходимость (улучшение сходимости) приводит к увеличению времени поиска оптимального решения.

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

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

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

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

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

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

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

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

При успешном окончании поиска решения можно сохранить найденное решение, восстановить исходные значения изменяемых ячеек, сформировать один или несколько типов отчетов (рис. 9.7).

 

Рис. 9.7. Результаты поиска оптимального решения

 

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

 

Пример 2. Предприятие выпускает 3 вида изделий (А, Б, В), для изготовления которых используется фрезерное, токарное, сварочное и шлифовальное оборудование. Удельные затраты рабочего времени для каждого типа оборудования, общий фонд рабочего времени, а также прибыль от реализации единицы продукции каждого вида приведены в табл. 9.1. Требуется так спланировать объемы выпуска изделий, чтобы прибыль от их реализации была максимальной.

 

Таблица 9.1

Прибыль от реализации единицы продукции каждого вида

Тип оборудования	Затраты времени на обработку 1 изделия	Общий фонд рабочего времени
А	Б	В
Фрезерное
Токарное
Сварочное
Шлифовальное
Прибыль

Решение. Построим математическую модель задачи. Предположим, что будет изготовлено х ₁ единиц изделий вида А, х ₂ — вида Б, х ₃ — вида В. Поскольку прибыль от реализации должна быть максимальной, а общий фонд рабочего времени каждого вида оборудования ограничен, имеем

10 х₁ + 14 х₂ + 12 х₃ ® max,

2 х₁ + 4 х₂ + 5 х₃ £ 120,

х₁ + 8 х₂ + 6 х₃ £ 280,

7 х₁ + 4 х₂ + 5 х₃ £ 240,

4 х₁ + 6 х₂ + 10 х₃ £ 360,

х₁ ³ 0, х₂ ³ 0, х₃ ³ 0.

Реализация представленной математической модели средствами MS Excel представлена на рисунке 9.8.

 

Рис. 9.8. Реализация расчетных формул средствами MS Excel

 

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

 

Рис. 9.9. Реализация математической модели поиска оптимального решения

 

В результате получится решение: х ₁=24, х ₂=18, х ₃=0. Максимальная прибыль при этом составила 492 у.е.

Пример 3. Организация выделяет 25 млн. руб. для покупки краски. Стоимость 1 литра краски составляет 15000 руб. На заводе ее разливают в емкости объемом 25 и 50 литров. Краску можно покупать только полными емкостями. Стоимость пустой тары 20000 и 30000 руб. соответственно. Необходимо приобрести наибольшее количество краски. Решите задачу, пользуясь надстройкой «Поиск решения».

Решение. Обозначим количество банок по 25 и 50 литров переменными _x1 и x₂. Тогда (25 x₁+50 x₂) – общее количество литров краски, которое необходимо приобрести организации. Так как выделено всего 25000000 руб. для покупки краски, то неравенство примет вид: x₁ (25 15000+20000)+ x₂ (50 15000+30000)<=25000000, также известно, x₁ и x₂ – целые и x₁,x₂>0. Тогда целевая функция (необходимое количество литров краски) имеет вид:

 

F(x₁,x₂)=(25 x₁+50 x₂) max.

 

Ограничения по бюджету на закупку краски с учетом стоимости пустой тары составляют:

 

x₁ (25 15000+20000)+ x₂ (50 15000+30000)<=25000000.

Граничные условия также известны:

x₁,x₂ – целые

x₁>0,

x₂>0.

Таким образом, модель задачи оптимизации примет вид:

 

 

 

На новом листе рабочей книги создадим таблицу следующего вида (табл. 9.2).

 

Таблица 9.2

Исходные данные к примеру 2

 

Для решения задачи оптимизации, выделим ячейку с целевой функцией B7 и используем надстройку «Поиск решения» (рис. 9.10).

 

Рис. 9.10. Реализация математической модели поиска оптимального решения

В результате получится решение: х ₁=0, х ₂=32, т.е. организации выгоднее приобретать 50 литровые банки в количестве 32 шт., а 25 литровые банки покупать не выгодно. Общее количество литров краски, которое необходимо приобрести организации в результате будет равно 1600.