Решение задач оптимизации в excel
Основной целью экономики является рациональное функционирование хозяйствующих субъектов или, иначе говоря, оптимальная деятельность при ограниченных ресурсах. Поэтому в экономической области существует широкий класс задач оптимизации, или, как их еще называют, экстремальных задач. В задачах оптимизации вычисляются значения параметров некоторой функции
при которых она принимает экстремальное значение (максимальное или минимальное) и при условии, что на эти параметры наложены ограничения.
Эту функцию называют целевой функцией, а набор количественных значений между переменными, выражающих определенные требования к параметрам экономической задачи в виде уравнений или неравенств называют системой ограничений.
Совокупность соотношений, содержащих целевую функцию и ограничения на ее аргументы, называют математической моделью экономической задачи оптимизации.
Если целевая функция линейна и на ее аргументы наложены линейные ограничения, то такую задачу оптимизации называют задачей линейного программирования.
Существуют различные методы решения задач линейного программирования. В MS Excel для этой цели предназначен инструмент Поиск решения. Принцип его работы заключается в использовании итерационного способа подбора параметров целевой функции в сочетании с градиентным методом. Применение этого инструмента позволяет решать задачи оптимизации с высокой точностью. Технологическая последовательность решения задачи включает следующие шаги:
1. На основе постановки задачи и уяснения ее экономической сути, разрабатывается математическая модель, аналитически представляющая целевую функцию и функции ограничений.
2. Ввод исходных данных и формул, реализующих математическую модель в электронную таблицу.
3. Настройка параметров инструмента Поиск решения и его применение для решения задачи.
Оптимальный план выпуска продукции
Покажем последовательность решения задачи линейного программирования на простом примере.
Пример . Фирма производит два вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг готового продукта и их суточные запасы приведены в таблице.
Суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того известно, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженого 16 ден. ед., шоколадного – 14 ден. ед.
Требуется определить в каком количестве мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным.
Шаг 1 – разработка математической модели
Введем обозначения: x1 – суточный объем производства сливочного мороженого, х2 - суточный объем производства шоколадного мороженого. Исходя из условия задачи целевая функция будет иметь вид
На этой странице вы найдете примеры решений различных оптимизационных задач с использованием пакета электронных таблиц MS Excel (используется как надстройка Поиск решения, так и ручные вычисления).
Задачи оптимизации и Excel
Задачи оптимизации имеют огромное прикладное значение и возникают в самых разных разделах экономики, техники, военного дела и т.п. В таких задачах нас интересуют поиск некоторого оптимального решения (минимизующего или максимизирующего целевую функцию: прибыль, затраты, калорийность и т.п.) в условиях ограничений (наличия ресурсов, дорог, времени, продуктов и т.п.).
Вот некоторые примеры экономических задач: минимизация расходов при формировании состава сырья (например, на текстильных предприятиях), оптимизация раскроя (например, на швейных производствах), минимизация расходов при формировании штатного расписания, оптимизация калорийности и стоимости рациона (как для людей, так и для животных), минимизация расходов на перевозку грузов по маршрутам, оптимизация расходов на изготовление при выборе ассортимента продукции, максимизация прибыли при формировании инвестиционной программы и др.
Часто эти задачи (даже учебные, даже в случае линейности) содержат более десяти переменных(а в случае, например, транспортных задач, и вовсе десятки), что делает ручные расчеты нерациональными. В то же время привычная для всех программа Excel прекрасно подходит для поиска решения.
Алгоритм решения с помощью надстройки "Поиск решения" следующий:
- составить математическую модель задачи: выделить и обозначить переменные, ограничения на них в виде равенств и неравенств (естественные, например, неотрицательность количества, и дополнительные, например, "запасов железной руды не более 10 т"), целевую функцию (то, что нужно оптимизировать) выразить через переменные.
- выделить место под переменные задачи; внести ограничения (левые части - в виде формул от переменных, правые - в виде констант) в файл электронной таблицы Excel,
- внести в ячейку формулу для целевой функции,
- запустить надстройку Поиск решения,
- установить нужные параметры решения (ограничения в листе, ограничения неотрицательности, условие линейности при необходимости и т.п.) и запустить выполнение.
Excel вычислит оптимальные значения переменных и покажет их в ячейках, а также значение целевой функции. Дополнительно можно построить отчеты для анализа решения задачи.
Некоторые задачи оптимизации решаются не с помощью надстройки Поиск решения, а путем подбора параметра или ручных расчетов. Ниже вы найдете примеры разных задач, а также ссылки на другие разделы со сходными заданиями.
Задачи оптимизации: примеры в Excel
Задача 2. Для производства двух видов изделий А и В предприятие использует три вида сырья. Нормы расхода каждого вида сырья на изготовление единицы продукции данного вида в таблице 6. В ней же указаны прибыль от реализации единицы изделия каждого вида и общее количество сырья данного, которое может быть использовано предприятием.
Требуется такой составить такой план производства изделий А и В, при котором прибыль от реализации будет максимальной?
Задача 3. Фирма N, имеющая филиалы (k), производит продукцию. Каждый филиал фирмы выпускает четыре вида продукции из пяти (i=1-5). Данные, характеризующие производство филиалов $b_$, приведены в табл.1.
Филиалы фирмы закупают сырье, из которого производят продукцию, у семи АО (j =1-7). Выход готового продукта из 1 тонны сырья $a_$ показан в табл.2.
Прибыль филиалов фирмы при закупке 1тн сырья у разных АО, $С_$ , показана в табл.3.
В разделе 1 работы требуется:
1.1.Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, ($x_j$), максимизируя прибыль филиала. Далее, студент формулирует экономико-математическую модель общей задачи линейного программирования (ОЗЛП).
1.2.С помощью полученных в результате реализации модели отчетов сделать рекомендации филиалу фирмы по расширению программы выпуска ассортимента продукции.
Задача 4. Для изготовления одного пирожка требуется 0,8 ед. начинки и 4 ед. теста, одного пирожного 4 ед. начинки и 0,5 ед. теста, одного рулета 2 ед. начинки и 2,5 ед. теста. Сколько пирожков, пирожных и рулетов нужно сделать кондитерской, если в наличии имеется 120 ед. теста и 300 ед. начинки?
Определите доход от реализации кондитерских изделий, если доход от продажи одного пирожка составляет 3 рубля, одного пирожного 2 рубля, одного рулета 1,5.
Для решения задачи используется ППП Excel.
Задача 5. Менеджер проекта по строительству нового торгового гипермаркета компании Наше дело надеется завершить проект за пару недель до Рождества.
После обзора оценок времени выполнения отдельных стадий выяснилось, что потребуются дополнительные инвестиции, чтобы сократить длительность проекта так, чтобы он действительно завершился вовремя. В таблице приведены оценки длительностей стадий и стоимость их сокращения на 1 и на 2 недели.
a. Нарисуйте сетевую диаграмму проекта и найдите критический путь.
b. Определите минимальную стоимость сокращения проекта на 5 недель.
Пользователи Excel давно и успешно применяют программу для решения различных типов задач в разных областях.
Excel – это самая популярная программа в каждом офисе во всем мире. Ее возможности позволяют быстро находить эффективные решения в самых разных сферах деятельности. Программа способна решать различного рода задачи: финансовые, экономические, математические, логические, оптимизационные и многие другие. Для наглядности мы каждое из выше описанных решение задач в Excel и примеры его выполнения.
Решение задач оптимизации в Excel
Оптимизационные модели применяются в экономической и технической сфере. Их цель – подобрать сбалансированное решение, оптимальное в конкретных условиях (количество продаж для получения определенной выручки, лучшее меню, число рейсов и т.п.).
В Excel для решения задач оптимизации используются следующие команды:
- Подбор параметров («Данные» - «Работа с данными» - «Анализ «что-если»» - «Подбор параметра») – находит значения, которые обеспечат нужный результат.
- Поиск решения (надстройка Microsoft Excel; «Данные» - «Анализ») – рассчитывает оптимальную величину, учитывая переменные и ограничения. Перейдите по ссылке и узнайте как подключить настройку «Поиск решения».
- Диспетчер сценариев («Данные» - «Работа с данными» - «Анализ «что-если»» - «Диспетчер сценариев») – анализирует несколько вариантов исходных значений, создает и оценивает наборы сценариев.
Для решения простейших задач применяется команда «Подбор параметра». Самых сложных – «Диспетчер сценариев». Рассмотрим пример решения оптимизационной задачи с помощью надстройки «Поиск решения».
Условие. Фирма производит несколько сортов йогурта. Условно – «1», «2» и «3». Реализовав 100 баночек йогурта «1», предприятие получает 200 рублей. «2» - 250 рублей. «3» - 300 рублей. Сбыт, налажен, но количество имеющегося сырья ограничено. Нужно найти, какой йогурт и в каком объеме необходимо делать, чтобы получить максимальный доход от продаж.
Известные данные (в т.ч. нормы расхода сырья) занесем в таблицу:
На основании этих данных составим рабочую таблицу:
- Количество изделий нам пока неизвестно. Это переменные.
- В столбец «Прибыль» внесены формулы: =200*B11, =250*В12, =300*В13.
- Расход сырья ограничен (это ограничения). В ячейки внесены формулы: =16*B11+13*B12+10*B13 («молоко»); =3*B11+3*B12+3*B13 («закваска»); =0*B11+5*B12+3*B13 («амортизатор») и =0*B11+8*B12+6*B13 («сахар»). То есть мы норму расхода умножили на количество.
- Цель – найти максимально возможную прибыль. Это ячейка С14.
Активизируем команду «Поиск решения» и вносим параметры.
После нажатия кнопки «Выполнить» программа выдает свое решение.
Оптимальный вариант – сконцентрироваться на выпуске йогурта «3» и «1». Йогурт «2» производить не стоит.
Решение финансовых задач в Excel
Чаще всего для этой цели применяются финансовые функции. Рассмотрим пример.
Условие. Рассчитать, какую сумму положить на вклад, чтобы через четыре года образовалось 400 000 рублей. Процентная ставка – 20% годовых. Проценты начисляются ежеквартально.
Оформим исходные данные в виде таблицы:
Так как процентная ставка не меняется в течение всего периода, используем функцию ПС (СТАВКА, КПЕР, ПЛТ, БС, ТИП).
- Ставка – 20%/4, т.к. проценты начисляются ежеквартально.
- Кпер – 4*4 (общий срок вклада * число периодов начисления в год).
- Плт – 0. Ничего не пишем, т.к. депозит пополняться не будет.
- Тип – 0.
- БС – сумма, которую мы хотим получить в конце срока вклада.
Вкладчику необходимо вложить эти деньги, поэтому результат отрицательный.
Для проверки правильности решения воспользуемся формулой: ПС = БС / (1 + ставка) кпер . Подставим значения: ПС = 400 000 / (1 + 0,05) 16 = 183245.
Решение эконометрики в Excel
Для установления количественных и качественных взаимосвязей применяются математические и статистические методы и модели.
Дано 2 диапазона значений:
Значения Х будут играть роль факторного признака, Y – результативного. Задача – найти коэффициент корреляции.
Для решения этой задачи предусмотрена функция КОРРЕЛ (массив 1; массив 2).
Решение логических задач в Excel
В табличном процессоре есть встроенные логические функции. Любая из них должна содержать хотя бы один оператор сравнения, который определит отношение между элементами (=, >, =, Пример задачи. Ученики сдавали зачет. Каждый из них получил отметку. Если больше 4 баллов – зачет сдан. Менее – не сдан.
- Ставим курсор в ячейку С1. Нажимаем значок функций. Выбираем «ЕСЛИ».
- Заполняем аргументы. Логическое выражение – B1>=4. Это условие, при котором логическое значение – ИСТИНА.
- Если ИСТИНА – «Зачет сдал». ЛОЖЬ – «Зачет не сдал».
Решение математических задач в Excel
Средствами программы можно решать как простейшие математические задачки, так и более сложные (операции с функциями, матрицами, линейными уравнениями и т.п.).
Условие учебной задачи. Найти обратную матрицу В для матрицы А.
- Делаем таблицу со значениями матрицы А.
- Выделяем на этом же листе область для обратной матрицы.
- Нажимаем кнопку «Вставить функцию». Категория – «Математические». Тип – «МОБР».
- В поле аргумента «Массив» вписываем диапазон матрицы А.
- Нажимаем одновременно Shift+Ctrl+Enter - это обязательное условие для ввода массивов.
Возможности Excel не безграничны. Но множество задач программе «под силу». Тем более здесь не описаны возможности которые можно расширить с помощью макросов и пользовательских настроек.
Оптимизационные модели при экономической и технической сфере.
Цель занятия: подобрать сбалансированное решение, оптимальное в конкретных условиях (количество продаж для получения определенной выручки, лучшее меню, число рейсов и т.п.).
В Excel для решения задач оптимизации используются следующие команды:
Подбор параметров («Данные» - «Работа с данными» - «Анализ «что-если»» - «Подбор параметра») – находит значения, которые обеспечат нужный результат.
Поиск решения (надстройка Microsoft Excel; «Данные» - «Анализ») – рассчитывает оптимальную величину, учитывая переменные и ограничения. Перейдите по ссылке и узнайте как подключить настройку «Поиск решения».
Диспетчер сценариев («Данные» - «Работа с данными» - «Анализ «что-если»» - «Диспетчер сценариев») – анализирует несколько вариантов исходных значений, создает и оценивает наборы сценариев.
Для решения простейших задач применяется команда «Подбор параметра». Самых сложных – «Диспетчер сценариев». Рассмотрим пример решения оптимизационной задачи с помощью надстройки «Поиск решения».
Условие. Фирма производит несколько сортов йогурта. Условно – «1», «2» и «3». Реализовав 100 баночек йогурта «1», предприятие получает 200 сом. «2» - 250 сом. «3» - 300 сом. Сбыт, налажен, но количество имеющегося сырья ограничено. Нужно найти, какой йогурт и в каком объеме необходимо делать, чтобы получить максимальный доход от продаж.
Известные данные (в т.ч. нормы расхода сырья) занесем в таблицу:
На основании этих данных составим рабочую таблицу:
Количество изделий нам пока неизвестно. Это переменные.
В столбец «Прибыль» внесены формулы: =200*B11, =250*В12, =300*В13.
Расход сырья ограничен (это ограничения). В ячейки внесены формулы: =16*B11+13*B12+10*B13 («молоко»); =3*B11+3*B12+3*B13 («закваска»); =0*B11+5*B12+3*B13 («амортизатор») и =0*B11+8*B12+6*B13 («сахар»). То есть мы норму расхода умножили на количество.
Цель – найти максимально возможную прибыль. Это ячейка С14.
Активизируем команду «Поиск решения» и вносим параметры.
После нажатия кнопки «Выполнить» программа выдает свое решение.
Оптимальный вариант – сконцентрироваться на выпуске йогурта «3» и «1». Йогурт «2» производить не стоит.
Лазаренко Виктория Сергеевна студент 4 курса, Ставропольский государственный педагогический институт, РФ, г. Ставрополь Кузина Наталья николаевна научный руководитель, Старший преподаватель кафедры математики и информатики, Ставропольский государственный педагогический институт, РФ, г. Ставрополь
« РЕАЛИЗАЦИЯ МНОГОМЕРНЫХ ЗАДАЧ ОПТИМИЗАЦИИ В excel» Аннотация: В статье рассмотрены основные методы многомерной оптимизации, ПРИВЕДЁН ПРИМЕР РЕАЛИЗАЦИИ ЗАДАЧИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ (МЕТОДА ПОКООРДИНАТНОГО СПУСКА) В среде Excel. КЛЮЧЕВЫЕ СЛОВА: многомерная оптимизация, условная оптимизация, БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.
Изучение задач многомерной оптимизации заключается в нахождении точек минимума функции почти всех переменных на всем промежутке определенной размерности.
Такая задача сложнее задачи минимизации функции одной переменной, в связи с тем, что с увеличением размерности места переменных, растёт размер вычислений и возникает трудность в построении алгоритмов, тем самым возникают трудности в изучении поведения мотивированной функции.
В данной статье мы рассмотрим численные методы оптимизации, т.е. способы построения алгоритмов нахождения оптимального (минимального или максимального) познания некой функции и для наглядности реализуем пример многомерной оптимизации в Excel. Ведь Excel – это одна из наиболее узнаваемых и известных программ, возможности которой разрешают стремительно отыскивать действенное решение, начиная с математических задач и заканчивая применением оптимизации в самых различных сферах работе человека.
Численные методы многомерной оптимизации
Существуют разные методы безусловной и условной оптимизации. К безусловной оптимизации относятся методы: покоординатного спуска, метод наискорейшего спуска и подпрограмма EXCEL “Поиск решения”. Линейное программирование, метод штрафных функций и подпрограмма EXCEL “Поиск решения” – это условная оптимизация.
Суть методов безусловной оптимизации состоит в поиске минимуму функции методом неоднократных вычислений, при разных значениях характеристик х = k>, где k = 0, 1, 2, . Методы условной оптимизации применяются при наличии ограничений. Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x1, …,xn на каждой итерации.
Рассмотрим более подробно безусловную оптимизацию, её методы и реализацию примера в Excel.
Метод покоординатного спуска (метод прямого поиска), в котором используются лишь значения целевой функции. Чтобы воспользоваться этим методом, необходимо иметь такие исходные данные, как: формулу целевой функции, имеющую вид f(X1,X2, . , Xn); Е - точность нахождения значений независимых переменных, при которых функция достигает минимума; начальные приближения X10,X20 . , Xn0.
Стоит отметить, что метод покоординатного спуска сводит многомерную задачу оптимизации к многократному решению одномерных задач по каждой независящей переменной.
Приведём пример, чтобы показать наглядно сущность метода и его разрешение.
Условие задачи: число независимых переменных равняется двум. Ограничения отсутствуют. Требуется найти минимум функции
из начальной точки (0,5;0,5) c точностью 0,0001. Проанализировав функцию, заметим, что она будет иметь минимум, равный нулю. Для чего и первое, и второе слагаемое тоже должны быть равны нулю. Откуда координаты точки минимума (1;1).
Решим эту задачу на EXCEL. Откроем новый рабочий лист, где столбец А -значения X1, столбец В - значения X2, а столбец С - значения целевой функции и, наконец, столбец D - значения погрешности D.
Занесем в ячейки А3 и В3 значения начальных приближений, равных 0,5 и в ячейку С3 формулу =(В3-А3^2)^2+(1-A3)^2. Скопируем эту формулу в блок ячеек С4:С17. На этом заканчивается подготовительный этап.
Опишем первую итерацию, для этого скопируем содержимое ячейки В3 в ячейку В4. Сделаем текущей ячейку С4. Процесс одномерной оптимизации для нахождения X1 выполним с помощью подпрограммы EXCEL «Поиск решения». Вызовем эту подпрограмму командой меню Сервис - Поиск решения.
Теперь скопируем содержимое ячейки А4 в ячейку А5. Сделаем текущей ячейку С5. Зададим команду меню Сервис - Поиск решения. В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С5, а в поле Изменяя ячейки - адрес В5. В результате в ячейке В5 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С5 по координате X2.
Вычислим погрешности решения на первом шаге, для этого внесём в ячейку D5 формулу =ABS(A3-A5)+ABS(B3-B5). На этом заканчивается первая итерация.
Вторая и все последующие итерации проводятся аналогично, но с учетом соответствующих адресов ячеек.
Можно построить диаграмму изменения на каждой итерации, на которой видны перпендикулярные ломаные линии движения от точки к точке параллельно одной из осей координат.
Реализация метода покоординатного спуска представлена в Excel на рисунке 1.
Рисунок 1. Метод покоординатного спуска в Excel
Можно сказать, что сегодня оптимизационные задачи и задачи принятия решений моделируются и решаются в самых различных областях[1], в связи с этим растёт необходимость развития математического аппарата оптимизации. Решение задач с помощью Excel, позволяем наглядно разобраться с задачей и решить её.
Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев.
Список литературы
1. Корнеенко В. П. Методы оптимизации: Учебник / В. П. Корнеенко. - М.: Высш. шк., 2007.
2. Пантелеев А. В. Методы оптимизации в примерах и задачах: Учеб. пособие / А. В. Пантелеев, Т. А. Летова. - М.: Высш. шк., 2005.
3. Батищев Д. И. Оптимизация в САПР: Учебник / Д. И. Батищев, Я. Е. Львович, В. Н. Фролов. - Воронеж: Изд-во ВГУ, 1997.
Читайте также: