ТОР 5 статей:
Методические подходы к анализу финансового состояния предприятия
Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века
Характеристика шлифовальных кругов и ее маркировка
Служебные части речи. Предлог. Союз. Частицы
КАТЕГОРИИ:
- Археология
- Архитектура
- Астрономия
- Аудит
- Биология
- Ботаника
- Бухгалтерский учёт
- Войное дело
- Генетика
- География
- Геология
- Дизайн
- Искусство
- История
- Кино
- Кулинария
- Культура
- Литература
- Математика
- Медицина
- Металлургия
- Мифология
- Музыка
- Психология
- Религия
- Спорт
- Строительство
- Техника
- Транспорт
- Туризм
- Усадьба
- Физика
- Фотография
- Химия
- Экология
- Электричество
- Электроника
- Энергетика
Задача об использовании сырья
А.А. Усков
НАДСТРОЙКА «ПОИСК РЕШЕНИЯ» MS EXCEL
УЧЕБНОЕ ПОСОБИЕ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ ПО ДИСЦИПЛИНЕ “ЭКОНОМЕТРИКА ”
Надстройка «поиск решения» MS Excel. Усков А.А. Смоленск, 2006. – 20 с.
В учебном пособии рассмотрена методика применения надстройки «Поиск решения» MS Excel для решения задач экономического планирования.
Введение
Построение моделей и оптимизация экономических систем относится к разряду особо трудных «не решаемых» задач. Поэтому, на практике в большинстве случаев при принятии решений в области экономическо-управленческой деятельности руководствуются экспертными оценками, опытом и интуицией. В тоже время, для ряда экономических задач возможно получить формальную математическую модель, однозначно и достоверно описывающую происходящие процессы. В указанном случае применение математических методов достаточно эффективно. В частности, для статических задач применим аппарат математического программирования (поиск минимума или максимума, в общем случае, нелинейной функции при нелинейных ограничениях). Наиболее разработаны методы решения частного случаем задач математического программирование – задач выпуклого программирования. Особенностью выпуклого программирования является одноэкстремальность целевой функции на множестве допустимых решений. Примером таких задач является задача линейного программирования (поиск экстремума линейной целевой функции при линейных ограничениях).
В пакете MS Excel есть удобное средство для решения задач нелинейного программирования – надстройка «Поиск решения» [1, 2].
В надстройке «Поиск решения» реализованы алгоритмы условного метода Ньютона и условного метода сопряженных градиентов [3, 4], отлично справляющиеся с задачами выпуклого программирования, в частности линейного, но при решении задач с целевой функцией имеющей несколько экстремумов или при наличии дискретных ограничений (например, в задачах целочисленного программирования [5, 6]) возникают определенные сложности, проявляющиеся в том, что полученное решение соответствует не глобальному экстремуму, а локальному, т. е. носит лишь приближенный, не самый эффективный из возможных характер.
Указанные сложности преодолимы, по крайне мере, частично, так для решения многоэкстремальных задач можно многократно запускать процедуру локального поиска из различных начальных точек и выбирать наилучшее решение, а при решении дискретных задач использовать более сложные методы, сводящиеся к многократному решению недискретных задач, например, для решения задач линейного целочисленного программирования можно использовать метод ветвей и границ, сводящийся к последовательности решений составленных специальным образом задач «обычного» линейного программирования [5, 6].
Учебное пособие посвящено систематическому изложению методики применения надстройки MS Excel «Поиск решения».
В учебном пособии использован материал книг [1, 2].
1 Надстройка «Поиск решения» MS Excel
Рассмотрим задачу нахождения точек, в которых достигаются максимальные и минимальные значения функции нескольких переменных, при линейных и нелинейных ограничениях. Другими словами – находится оптимальное решение задачи статического управления с ограничениями.
Для решения задач будем использовать Поиск решения MS Excel. Для запуска этого инструмента необходимо выполнить команду Сервис | Надстройки. Появится окно диалога "Надстройки", в котором нужно установить флажок на строке Поиск решения и нажать кнопку ОК (рисунок 1).
Рисунок 1 – Окно диалога "Надстройки"
После загрузки инструмента Поиск решения в списке опций ниспадающего меню Сервис появится новая команда Поиск решения. В результате выполнения этой команды появляется окно диалога "Поиск решения" (рисунок 2).
Рисунок 2 – Окно диалога "Поиск решения"
В поле ввода Установить целевую ячейку указывается ссылка на ячейку с целевой функцией, значение которой должно быть максимальным, минимальным или равным заданному значению в зависимости от выбранного положения переключателя.
В поле ввода Изменяя ячейки указываются ячейки, которые отведены под переменные целевой функции.
Поле Ограничения должно содержать ограничения, накладываемые на изменение переменных целевой функции.
Кнопка Параметры вызывает окно диалога "Параметры поиска решения" (см. рисунок 3), в котором можно изменять параметры алгоритма поиска решения.
Рисунок 3 – Окно диалога "Параметры поиска решения"
Установки по умолчанию подходят для решения большинства типов оптимизационных задач. В таблице 1 приведены параметры надстройки Поиск решения и их описание.
Таблица 1 – Параметры надстройки Поиск решения
| Параметр | Действие |
| Максимальное время | Максимальное время в секундах (не превышающее 32 767), которое может быть затрачено на поиск решения |
| Предельное число итераций | Максимальное число итераций, которые могут быть сделаны. Каждая итерация заключается в вычислении очередного значения (приближения) и проверке, насколько это значение подходит в качестве ответа |
Таблица 1 – Параметры надстройки Поиск решения (продолжение)
| Относительная погрешность | Задает точность выполнения ограничений. Поле должно содержать число из интервала от нуля до единицы |
| Допустимое отклонение | В случае целочисленных ограничений задает, насколько близко в процентном отношении должен быть ответ к возможному наилучшему решению. При работе со сложными целочисленными задачами увеличение допустимого отклонения может привести к значительному ускорению работы. Используется только для целочисленных задач |
| Сходимость | Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в этом поле, поиск прекращается. Сходимость применяется только к нелинейным задачам (когда снят флажок Линейная модель). Поле должно содержать число из интервала от нуля до единицы |
| Линейная модель | Служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи путем использования методов линейного программирования. Если рабочий лист содержит нелинейную модель, при запуске средства Поиск решения будет появляться предупреждение |
| Неотрицательные значения | Устанавливает неотрицательность всех переменных, для которых не заданы явные ограничения в виде неравенств |
| Автоматическое масштабирова-ние | Служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по порядку величины, например максимизация прибыли в процентах по отношению к вложениям, исчисляемым в млн руб. |
| Показывать результаты итераций | Выводит промежуточный результат и делает паузу при каждой итерации. Для продолжения поиска решения необходимо каждый раз нажимать кнопку Продолжить. С помощью кнопки Стоп можно остановить процесс |
| Оценки | Выбор линейного или квадратичного метода оценки. Квадратичный метод имеет смысл использовать, если зависимости в модели сильно отличаются от линейных |
| Разности | Служит для указания метода численного дифференцирования (прямые или центральные производные), который используется для вычисления частных производных целевых и ограничивающих функций. Прямые производные предназначены для гладких непрерывных функций. Центральные производные — для функций, имеющих разрывную производную |
Таблица 1 – Параметры надстройки Поиск решения (продолжение)
| Метод поиска | Служит для выбора алгоритма оптимизации (метод Ньютона или сопряженных градиентов) для указания направления поиска. При методе Ньютона запрашивается больше памяти, но выполняется меньше итераций, чем в методе сопряженных градиентов. Метод сопряженных градиентов следует использовать, если задача достаточно велика и необходимо экономить память, а также если итерации дают слишком малое отличие в последовательных приближениях |
Параметры поиска решения могут быть сохранены и затем загружены, для чего необходимо воспользоваться кнопками Сохранить модель… и Загрузить модель….
По найденным результатам можно создавать отчеты. Такие отчеты полезны для сравнения влияния на решение различных ограничений или исходных данных. Отчеты бывают трех типов: Результаты, Устойчивость, Пределы. Тип выбирается по окончании поиска решения в диалоговом окне Результаты поиска решения в списке Отчеты (рисунок 4). Можно выбрать сразу два или три типа с помощью мыши при нажатой клавише <Ctrl>. Каждый отчет будет создан на отдельном рабочем листе. Содержание отчетов кратко описано в таблица 2.
Рисунок 4 – Окно «Результаты поиска решения»
Для сохранения значений в ячейках таблицы служит кнопка Сохранить сценарий… (см. рисунок 4). Для того чтобы загрузить сохраненный ранее сценарий необходимо выполнить команду в меню MS Excel Сервис / Сценарии…
Таблица 2 – Содержание отчетов
| Тип отчета | Содержание |
| Результаты | Отчет состоит из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях |
| Устойчивость | Отчет содержит сведения о чувствительности решения к малым изменениям в формуле модели или в формулах ограничений. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. В случае нелинейных моделей отчет содержит данные для градиентов и множителей Лагранжа. В отчет по нелинейным моделям включаются ограниченные затраты, фиктивные цены, объективный коэффициент (с некоторым допуском), а также диапазоны ограничений справа |
| Пределы | Отчет состоит из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно верхним пределом называется наибольшее значение |
Сохранение параметров модели. Последние использованные параметры модели сохраняются на рабочем листе, для этого применяются именованные формулы. При следующем открытии рабочего листа и запуске средства Поиск решения появится диалоговое окно с теми же параметрами, которые были установлены при предыдущем запуске. Каждый рабочий лист в рабочей книге также имеет установки, определенные в предыдущем сеансе MS Excel.
Задача об использовании сырья
Предположим необходимо определить оптимальный план выпуска продукции в условиях дефицита сырья.
Предприятие выпускает два вида продукции. Цена единицы продукции вида 1 равна 25000 руб., вида 2 – 50000 руб.
Для изготовления продукции используются три вида сырья, запасы которого оцениваются в 37, 57,6 и 7 тонн соответственно. На каждый вид сырья есть коэффициент его расхода на единицу продукции. Соответствующие коэффициенты приведены в таблице 3.
Таблица 3 – Коэффициенты расхода сырья на единицупродукции
| Вид сырья | Продукция | Запасы сырья | |
| Вид 1 | Вид 2 | тонн | |
| 1,2 | 1,9 | ||
| 2,3 | 1,8 | 57,6 | |
| 0,1 | 0,7 |
Обозначим количество произведенной продукции вида 1 через с1, вида 2 вида – с2. Целевая функция в данном случае есть выражение следующего вида:
J(cl, c2) = 25000*cl + 50000*с2.
Это есть цена произведенной продукции. Наше решение должно обеспечить максимальное значение этой функции.
Таблица 1 налагает на величины cl и с2 ограничения следующего вида:
1,2*с1 + 1,9*с2 <= 37
2,3*с1 + 1,8*с2 <= 57,6
0,1*с1 + 0,7*с2 <= 7
c1 >= 0
c2 >= 0
Выполним следующие действия:
1. Введем в ячейку А1 формулу для целевой функции:
=25000*с1+50000*с2.
2. Введите в ячейку A3 формулу для ограничения: =1, 2*с1+1, 9*с2.
3. Введите в ячейку А4 формулу для ограничения: =2.3*cl+1,8*c2.
4. Введите в ячейку А5 формулу для ограничения: =0,1*с1+0, 7*с2.
5. Введите в ячейку А6 формулу для ограничения: =cl.
6. Введите в ячейку А7 формулу для ограничения: =с2.
7. Введите в ячейки С1:C2 начальные значения переменных (положим их нулевыми).
8. Выполним команду Сервис | Поиск решения. Появится окно диалога «Поиск решения».
9. В поле ввода Установить целевую введем ссылку на ячейку А1.
10. В поле ввода Изменяя ячейки укажем ссылки на ячейки С1:С2.
11. Начинаем вводить информацию в поле ввода Ограничения. Нажмем кнопку Добавить. Появится окно диалога "Добавить ограничения". Вполе ввода Ссылка на ячейку введем ссылку на ячейкуA3. В поле ввода Ограничение введем <= и число 37 (рисунок 3).
Рисунок 3 – Окно «Добавление ограничения»
12. Воспользуемся кнопкой Добавить для ввода остальных ограничений. После ввода параметров окно диалога "Поиск решения" будет иметь вид показанный на рисунке 4. При необходимости, для изменения ограничения установите на него курсор и нажмите кнопку Изменить.
Рисунок 4 – Окно «Поиск решения» после ввода параметров
13. Нажмем кнопку Выполнить. После окончания расчета Excel откроет окно диалога "Результаты поиска решения" (рисунок 5).
14. Выберем в окне "Тип отчета" Результаты и нажмите кнопку ОК. Перед тем листом, где записана постановка задачи, будет вставлен лист "Отчет по результатам 1". В ячейках Сl и Сl отображаются значения переменных, на которых достигается максимальное значение целевой функции (рисунок 6).
Рисунок 6 – Решение задачи
15. Нажмем мышью ярлык «Отчет по результатам 1». На экране появится отчет о решении задачи (рисунок 7).
Рисунок 7 – Отчет по результатам
Не нашли, что искали? Воспользуйтесь поиском: