Н и шадрина н д берман решение задач оптимизации в microsoft excel 2010
Пользователи 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 не безграничны. Но множество задач программе «под силу». Тем более здесь не описаны возможности которые можно расширить с помощью макросов и пользовательских настроек.
1 Министерство образования и науки Российской Федерации Федеральное агентство по образованию Саратовский государственный технический университет РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ В СРЕДЕ MS EXCEL Методические указания к изучению дисциплины «Информатика» для студентов и слушателей строительных специальностей Одобрено редакционно-издательским советом Саратовского государственного технического университета Саратов 2007
2 ВВЕДЕНИЕ В методических указаниях приводятся задания и рассматриваются задачи оптимизации инженерных задач и решение их в среде MS Excel. Функции MS Excel обладают развитым аппаратом численного анализа данных, позволяющим решать сложные задачи линейного и нелинейного программирования со многими неизвестными и ограничениями, что делает его очень удобным инструментом решения задач оптимизации. В MS Excel для решения различных задач оптимизации есть средство Поиск решения. Эта команда находится в меню Сервис. Если команда не обнаруживается, это значит, надстройка Поиск решения не загружена. Для загрузки надо выбрать Надстройки из меню Сервис. Из списка диалогового окна выбирается Поиск решения и в квадратике устанавливается флажок. В случае отсутствия в списке надстройки Поиск решения, запускается программа установки MS Excel. Данные методические указания предназначены для студентов и слушателей курса информатики и информационных технологий в строительстве, знакомых с основами работы в Excel. 3
3 1. ЗАДАЧИ ОПТИМИЗАЦИИ Часто возникает ситуация, когда необходимо выбрать из предложенных вариантов один, удовлетворяющий каким-то определенным требованиям. Очевидно, что этот вариант является оптимальным, т.е. наилучшим решением поставленной задачи. Введение нескольких характеристик (требований) для оценки наилучшего варианта приводит к задачам оптимизации. Задачи оптимизации разделяются на классические и неклассические. В классических задачах требуется найти значения одной или нескольких переменных. При этом ищется максимум или минимум значения некоторой непрерывной функции. В неклассических задачах имеются дополнительные ограничения, формирующие в совокупности множество допустимых альтернатив. Задачи оптимизации на сегодняшний день разнообразны по своему характеру. Универсальных методов для их решения практически нет, но существуют типовые классы задач оптимизации, которые могут быть успешно решены с помощью программы электронных таблиц MS Excel. Некоторые из них рассмотрим в данных методических указаниях. Задача о строительстве объекта относится к классу задач нелинейного программирования и является примером задачи многомерной нелинейной оптимизации. В математической модели этой задачи используются две независимые переменные, каждая из которых представляет отдельную координату точки на плоскости ПОСТАНОВКА ЗАДАЧИ О РАЗМЕЩЕНИИ СТРОЯЩЕГОСЯ ОБЪЕКТА Задача может иметь несколько возможных вариантов постановки, отличающихся друг от друга количеством жилых домов и их расположением на координатной плоскости. Рассмотрим конкретно один из вариантов этой задачи. Имеются четыре жилых дома, расположенных в некотором микрорайоне города. Определить местоположение объекта для строительства. Для примера объектом строительства выберем школу. Требуется построить школу в удобном для всех жителей микрорайона месте, предполагая, что сумма расстояний от 4
4 построенного объекта до всех жилых домов будет минимальным значением (рис. 1). Это значение и является целевой функцией, которую необходимо определить, используя функции среды MS Excel. Рис. 1 Другие варианты задачи о строительстве объектов могут быть сформулированы как для различных значений количества домов, местоположения этих домов, так и для различных видов целевой функции. 5
5 1.2. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ О МЕСТОПОЛОЖЕНИИ ВНОВЬ СТРОЯЩЕГОСЯ ОБЪЕКТА Для математической постановки задачи следует ввести обозначения четырех координат, используя прямоугольную систему координат, в которой исходные дома и школа будут представлять отдельные точки на плоскости (рис. 2). x 1 x 2 x x 3 x 4 Рис. 2 Координаты исходных домов могут быть записаны как координаты соответствующих точек в виде (х i,у i ), где i Є . Координаты для школы, которую предполагается построить, можно положить равными (х, у). Очевидно, они служат переменными рассматриваемой задачи оптимизации, каждая из которых по своему характеру может принимать действительные значения. В некоторой фиксированной прямоугольной системе координат значения переменных х,у могут быть как положительными, так и отрицательными. Задачу о строительстве школы можно считать задачей оптимизации без ограничений. В качестве целевой функции данной задачи будем рассматривать сумму расстояний от искомой точки (х, у) до каждой из заданных точек (х i,у i ), где i Є . 6
6 Расстояние от i-го дома до школы определим по формуле: r 2 2 ( x x ) ( y y ) i i i, где i ª. Общее расстояние от всех четырех домов до школы будет определяться выражением: r r 1 r2 r3 r 4. Таким образом, математическая постановка задачи о строительстве школы может быть записана в следующем виде: 4 f ( x, y) i ( x x ) i 2 ( y y 1 x, y R i ) 2 min, где R область значений для х и у. Поскольку целевая функция данной задачи является нелинейной, задача о строительстве школы относится к классу задач нелинейного программирования без ограничений РЕШЕНИЕ ЗАДАЧИ О МЕСТОПОЛОЖЕНИИ СТРОЯЩЕГОСЯ ОБЪЕКТА С ПОМОЩЬЮ MS EXCEL Для решения данной задачи с помощью программы МS Ехсеl создадим новый лист. Переименуем его, например, «Задача о строительстве школы». Выполним подготовительный этап для решения, т.е. создадим макет листа (рис. 3). Для этого применим знания, приобретенные при выполнении второй контрольной работе по освоению МS Ехсеl, например, такие как объединение ячеек, обрамление ячеек, автозаполнение ячеек, написание формул с использованием Мастера формул, знание функций математических категорий и т.д. Покажем умение пользоваться процедурой поиска решения, которая позволяет найти оптимальное значение формулы, содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, связанных с формулой в целевой ячейке. 7
7 Рис. 3 В ячейке G12 будет помещено значение целевой функции. Формула для ее вычисления: =СУММ(B7:B10). В ячейку B7 будет введена формула: =КОРЕНЬ(($B$12-B2)^2+($D$12-D2)^2). Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню Сервис Поиск решения (рис. 4). 8
8 Рис. 4 В поле с именем Установить целевую ячейку ввести абсолютный адрес ячейки $G$12 значение целевой функции, а в поле с именем Изменяя ячейки ввести абсолютный адрес ячеек $B$12:$D$12 (рис. 4). Поля с ограничениями можно оставить пустыми, поскольку целевая функция является выпуклой на всем множестве допустимых значений. Параметры поиска решения можно оставить без изменения (рис. 5). Параметры поиска решения задаются в каждом случае отдельно. Рис. 5 9
9 Результат выполнения задачи о строительстве школы вместе с графическим представлением показан на рис. 6. Рис. 6 Замечание. Графическое представление размещения домов и школы выполнено с применением Мастера диаграмм (рис. 7). Для этого выделяют предварительно массив данных, т.е. ячейки B14:C19. Затем выбирают тип диаграммы Стандартные Точечная, заполняют последовательно четыре шага Мастера диаграмм и получают рис.6. Тема применения и использования Мастер диаграмм была изучена ранее при выполнении второй контрольной работы ([2], [3]). 10
10 Рис. 7 Достоинство использования MS Excel для решения поставленной задачи наглядно продемонстрировано в данном примере. 2. ЗАДАЧА ОБ ИЗГОТОВЛЕНИИ СТЕРЖНЕЙ Задача об изготовлении стержней является разновидностью типовой задачи планирования производства и по своему характеру относится к классу задач геометрического программирования. Задачи этого класса после предварительных преобразований могут быть эффективно решены с помощью модели целочисленного линейного программирования ПОСТАНОВКА ЗАДАЧИ ОБ ИЗГОТОВЛЕНИИ СТЕРЖНЕЙ Изготовление стержней заключается в разрезании исходной заготовки на отрезки заданной длины. Задача состоит в том, чтобы из имеющихся исходных заготовок изготовить нужный комплект стержней требуемых длин наиболее эффективным способом разрезания исходного материала, при 11
11 котором на изготовление необходимого количества комплектов стержней потребуется наименьшее количество исходных заготовок. Аналогичные задачи встречаются часто на практике. В качестве исходных заготовок могут выбираться самые различные материалы, поступающие на строительство объектов в виде целых единиц, например, труб, досок, бревен, арматуры и т.д. Для их использования в строительстве приходится разрезать эти единицы заготовок на нужные отрезки. Длины этих отрезков должны соответствовать требуемым размерам. При неправильном выборе разрезания заготовок теряется часть материала, остатки выбрасываются. Для более эффективного и экономичного способа разрезания предлагается применить математический метод оптимизации, причем он должен быть применен для всей партии заготовок. При использовании метода должны быть рассмотрены все возможные способы разрезания исходных заготовок. На этой основе попытаемся разработать математическую модель задачи об изготовлении стержней МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ ОБ ИЗГОТОВЛЕНИИ СТЕРЖНЕЙ Сущность задачи об изготовлении стержней заключается в следующем. Производственное предприятие изготавливает металлические стержни трех видов фиксированной длины: 2,9 м, 2,1 м и 1,5 м соответственно. Для изготовления этих стержней поступает партия заготовок исходного материала, который также представляет собой металлические стержни длиной 7,4 м. Способ изготовления стержней заключается в разрезании исходной заготовки на отрезки заданной длины. Длины отрезков задаются, исходя из нужд производства. Рассмотрим шесть способов разрезания указанных отрезков, например, как показано в табл. 1. В последней, седьмой, строке указаны остатки, полученные при разрезании стержня длиной 7,4 м на отрезки требуемых длин, размеры которых указаны во 2-й, 3-й, 4-й и 5-й строках табл
12 Таблица 1 Способы 1-й 2-й 3-й 4-й 5-й 6-й разрезания Длина 1 2,9 2,9 2,1 2,9 2,1 2,9 Длина 2 1,5 2,9 2,1 2,1 1,5 2,1 Длина 3 1,5 1,5 1,5 2,1 1,5 1,5 Длина 4 1,5 0 1,5 0 1,5 0 Сумма отрезков 7,4 7,3 7,2 7,1 6,6 6,5 Остаток 0 0,1 0,2 0,3 0,8 0,9 Задача состоит в том, чтобы из имеющихся исходных заготовок изготовить 100 комплектов стержней требуемых длин наиболее эффективным способом разрезания исходного материала. При этом учесть, чтобы на изготовление необходимого количества комплектов стержней потребовалось наименьшее количество исходных заготовок. Из стержня длиной 7,4 м можно, например, изготовить один комплект деталей, длины отрезков которых соответственно равны 2,9; 2,1; 1,5 м. Остаток после разрезания стержня будет равен 0,9 м. Следовательно, если нужно получить 100 таких комплектов потребуется 100 стержней заготовок и оставшийся отход будет в сумме составлять 90 м. В случае других предложенных методов, например, первого способа разрезания, остатков материала совсем не будет, но не будет и длины отрезка, равной 2,1 м, а такой стержень необходим. Исходная задача преобразуется в задачу определения оптимального числа различных способов разрезания исходных заготовок. При этом будет изготовлено заданное число стержней требуемой длины, а общее число исходных заготовок должно быть минимальным. Исходными переменными математической модели задачи об изготовлении стержней являются x i количество исходных заготовок, разрезанных i-м способом для изготовления отдельных деталей. Математическая постановка данной задачи может быть записана в виде: x x x x x x min , x 13
13 где множество допустимых альтернатив формируется следующей системой ограничений типа неравенств: x 2x x x x3 2x4 x5 x x1 x2 2x3 3x5 x6 100 x1, x2, x3, x4, x5, x6 0 x1, x2, x3, x4, x5, x6 целые числа, (1) т.к. из табл. 1 видно, что размер 2,9 м для х 1 встречается один раз, для х 2 два раза, для х 3 и х 5 не выбираются, х 4 и х 6 один раз. Отрезков длиной 2,9 м выбирают не меньше 100 штук. Получаем первое неравенство системы. Точно также рассматриваем отрезки длиной 2,2 м и 1,5 м. Получаем следующие два неравенства. Значения не могут быть отрицательными числами, поэтому четвертое неравенство системы показывает, что каждое значение x i больше или равно нулю. Предлагается коэффициенты при x i первоначально выбрать равными единице и полагать x i целыми. Математическая модель (1) относится к классу задач целочисленного линейного программирования, которая может быть решена с помощь MS Excel РЕШЕНИЕ ЗАДАЧИ ОБ ИЗГОТОВЛЕНИИ СТЕРЖНЕЙ С ПОМОЩЬЮ MS EXCEL Для решения данной задачи с помощью программы МS Ехсеl создадим новый лист. Переименуем его, например, «Изготовление стержней». Выполним подготовительный этап для решения, т.е. создадим макет листа для исходных данных (рис. 8). Для удобства и наглядности в ячейки А10:A16, B10:G10, H10, I10, H13 вносим необходимый текст, ячейки В13 и G13 объединяем и также вносим текст в полученную ячейку. Текст не влияет на решение рассматриваемой задачи. В ячейки B12:G12 вводим единицы значения целевой функции. В ячейку H11 размещаем формулу для целевой функции: =СУММПРОИЗВ(B11:G11;B11:G11). 14
14 Рис. 8 Ячейки B11:G11 оставляем незаполненными, в них будут размещены значения, являющиеся результатом решения задачи. В ячейку Н14, используя Мастер функций, вводим формулу: =СУММПРОИЗВ($B$11:$G$11;B14:G14). Эту формулу копируем в ячейки Н15: Н16. Вызвав мастер поиска решения из меню Сервис Поиск решения, устанавливаем в появившемся диалоговом окне целевую функцию, указываем изменяемые ячейки и ограничения (рис. 9), заполняем необходимые данные в параметрах поиска решения, указывая Линейная модель Неотрицательные значения (рис. 10). Рис. 9 15
15 Рис. 10 Выполнив Поиск решения, нажав предварительно ОК в окне Параметры поиска решения, получаем найденное решение (рис. 11). Рис
16 Результатом решения задачи об изготовлении стержней являются найденные оптимальные значения переменных: х 1 = 30, х 2 = 10, х 3 = 0, х 4 = 50, х 5 = 0, х 6 = 0, которым соответствует значение целевой функции f орт = 90. Вывод. Из имеющихся заготовок для изготовления 100 комплектов деталей требуемых длин следует первым способом разрезать 30 стержней, вторым способом 10 стержней и четвертым способом 50 стержней. Общее число израсходованных заготовок будет равно 90, что является минимальным из всех возможных вариантов разрезания исходных заготовок. 17
17 3. ЗАДАНИЯ ЗАДАНИЕ 1. ОПРЕДЕЛЕНИЕ МЕСТОПОЛОЖЕНИЯ СТРОЯЩЕГОСЯ ОБЪЕКТА 1. По последней цифре номера зачетной книжки (студенческого билета) выбрать номер варианта. 2. По номеру варианта в табл. 2 выбрать соответственно количество домов микрорайона, координаты каждого дома и строящегося объекта. Таблица 2 варианта Количество домов Координаты домов Строящийся объект (3,-4), (6,-8), (18,20) почта 1 4 (3,-6), (7,-10), (15,18), (26,-5) универсам 2 5 (4,-6), (8,-12), (16,11), (12,-24), (24,-48) поликлиника 3 6 (5,-5), (10,-10), (1,-20), (15,-15), (20,-7), (30,-2) аптека 4 7 (0,-5), (5,-10), (10,-20), (15,-15), (19,-7), (28,-2), (30, 10) школа 5 8 (-10,-5), (10,-1), (1,-20), (15,-15), (20,-17), (30,-2), (25,-30), (5,-10) библиотека 6 4 (11,-5), (20,-10), (30,-20), (15,-15) аптека 18
18 Окончание табл (5,-6), (10,-11), (1,-22), (15,-17), (20,-20), (30,-2), (0,1) стадион 8 6 (8,-5), (11,-14), (1,-25), (15,1), (20,-9), (30,-25) школа 9 5 (7,-5), (10,-10), (1,-20), (15,-15), (-4,10) магазин Замечание. Значения координат объектов могут быть как положительными числами, так и отрицательными. 3. Создать на листе MS Excel макет задачи строящегося объекта, подписать ячейки с входными и выходными данными. 4. Внести нужные формулы. 5. Показать графическое расположение домов и строящегося объекта микрорайона 6. Выделить на графике имеющиеся дома и строящийся объект в виде черных квадратиков. 7. Получить решение задачи и сделать соответствующие выводы. ЗАДАНИЕ 2. ИЗГОТОВЛЕНИЕ ДЕТАЛЕЙ ОПРЕДЕЛЕННЫХ РАЗМЕРОВ ИЗ ЦЕЛЫХ ЗАГОТОВОК Задача состоит в том, чтобы из имеющихся исходных заготовок изготовить n комплектов требуемых длин стержней наиболее эффективным способом разрезания исходного материала, при котором на изготовление необходимого количества комплектов стержней потребуется наименьшее количество исходных заготовок. 1. По последней цифре номера зачетной книжки выбрать номер варианта из табл Продумать метод разрезания заготовки из материала. 19
19 варианта Количество способов разрезания заготовки Количество комплектов деталей требуемой длины, шт Материал Заготовки Длина, м Детали Требуемые длины, м Таблица арматура 8,0 1,5 1,6 1, доски 6,0 2,1 2,4 2, трубы 7,0 1,4 1,9 0, бревна 4,5 3,1 2,1 0, уголок 12,4 2,4 2,6 2, швеллер 8,4 1,8 1,5 2, доски 6,4 2,4 1,5 0, арматура 6,5 1,7 1,4 1, трубы 5,5 2,1 2,7 3, двутавр 7,2 1,9 2,1 2,4 3. Построить математическую модель. 4. Заполнить пустые ячейки табл. 4. Размер таблицы зависит от номера варианта. Количество столбцов этой таблицы соответствует указанному количеству способов разрезания заготовки. Таблица 4 Способы разрезания Длина 1 Длина 2 Длина 3 Длина 4 Длина n Сумма отрезков Остаток Замечание. Метод указан в [1]. заполнения таблицы и решение задачи 20
20 5. Построить макет на листе MS Excel, при этом подписывая все исходные данные, т.е. поясняя, в какой ячейке находится то или иное значение. 6. Вписать в ячейки нужные формулы для расчета суммы отрезков, подсчета остатка. 7. Написать формулу для целевой функции. 8. Получить решение задачи и сделать соответствующие выводы. Указание. Требования к оформлению заданий такие же, как и для второй контрольной работы, т.е. составить пояснительную записку в MS Word, создать рабочий файл в MS Excel, работу разместить на дискете или на диске СD-RW, напечатать пояснительную записку на листах формата А4 и сдать работу до начала сессии в ауд. 1/
21 ЛИТЕРАТУРА 1. Леоненков А. В. Решение задач оптимизации в среде MS Excel / А. В.Леоненков. СПб.: БХВ Петербург, Лавренов С. М. Excel. Сборник примеров и задач / С. М. Лавренов. М.: Финансы и статистика, Уэллс Э. Microsoft Excel 97: Разработка приложений / Э. Уэллс, С. Хешбаргер, пер. с англ. М.: Microsoft Press,
22 СОДЕРЖАНИЕ ВВЕДЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ. 4 Постановка задачи о размещении строящегося объекта. 4 Математическая постановка задачи о местоположении вновь строящегося объекта. 6 Решение задачи о местоположении строящегося объекта с помощью MS Excel ЗАДАЧА ОБ ИЗГОТОВЛЕНИИ СТЕРЖНЕЙ. 11 Постановка задачи об изготовлении стержней. 11 Математическая постановка задачи об изготовлении стержней. 12 Решение задачи об изготовлении стержней с помощью MS Excel ЗАДАНИЯ Задание 1. Определение местоположения строящегося объекта Задание 2. Изготовление деталей определенных размеров из целых заготовок. 19 ЛИТЕРАТУРА
23 РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ В СРЕДЕ MS EXCEL Методические указания к изучению дисциплины «Информатика» Составили: МОЖАЕВА Надежда Алексеевна КОЗЛОВ Вячеслав Викторович ЗУЕВА Наталья Геннадьевна Рецензент Ф.С. Селиванов Редактор О.А. Луконина Подписано в печать Формат 60 х 84 1/16 Бум. тип. Усл.печ.л 1,39 (1,5) Уч.изд.л. 1,3 Тираж 100 экз Заказ Бесплатно Саратовский государственный технический университет , Саратов, Политехническая ул., 77 Отпечатано в РИЦ СГТУ , Саратов, Политехническая ул., 77 24
На этой странице вы найдете примеры решений различных оптимизационных задач с использованием пакета электронных таблиц 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 недель.
Лекции
Лабораторные
Справочники
Эссе
Вопросы
Стандарты
Программы
Дипломные
Курсовые
Помогалки
Графические
Доступные файлы (1):
Практическая работа 12
Тема: ЗАДАЧИ ОПТИМИЗАЦИИ (ПОИСК РЕШЕНИЯ)
Цель занятия. Изучение технологии поиска решения для задач оптимизации (минимизации, максимизации).
Задание 12.1. Минимизация фонда заработной платы фирмы.
Пусть известно, что для нормальной работы фирмы требуется 5. 7 курьеров, 8. 10 младших менеджеров, 10 менеджеров, 3 заведующих отделами, главный бухгалтер, программист, системный аналитик, генеральный директор фирмы.
Общий месячный фонд зарплаты должен быть минимален. Необходимо определить, какими должны быть оклад
ы сотрудников фирмы, при условии, что оклад курьера не должен быть меньше 1400 р.
В качестве модели решения этой задачи возьмем линейную модель. Тогда условие задачи имеет вид
Ni * А1* х + N2 * (А2 * х + В2) + . . . + N8 * (A8 * х + B8) = Минимум, где N, — количество работников данной специальности; х — зарплата курьера; А,- и В, — коэффициенты заработной платы сотрудников фирмы.
Порядок работы
1. Запустите редактор электронных таблиц Microsoft Excel и откройте созданный в Практической работе 11 файл «Штатное расписание».
Скопируйте содержимое листа «Штатное расписание 1» на новый лист и присвойте копии листа имя «Штатное расписание 2».
2. В меню Сервис активизируйте команду Поиск решения (рис.
3. В окне Установить целевую ячейку укажите ячейку F14, содержащую модель — суммарный фонд заработной платы.
Поскольку необходимо минимизировать общий месячный фонд зарплаты, активизируйте кнопку равный — Минимальному значению.
В окне Изменяя ячейки укажите адреса ячеек, в которых будет отражено количество курьеров и младших менеджеров, а также зарплата курьера — $E$6:$E$7:$D$3 (при задании ячеек Е6, Е7 и D3 держите нажатой клавишу [Ctrl]).
Рис. 12.1. Задание условий для минимизации фонда заработной платы
Рис. 12.2. Добавление ограничений для минимизации фонда заработной!
Используя кнопку Добавить в окнах Поиск решения и Добавление ограничений, опишите все ограничения задачи: количество курьеров изменяется от 5 до 7, младших менеджеров от 8 до 10, зарплата курьера > 1400 (рис. 12.2). Ограничения наберите в виде
$D$3 > = 1400 $Е$6 > = 5
Активизировав кнопку Параметры, введите параметры поиска как показано на рис. 12.3.
Окончательный вид окна Поиск решения приведен на рис. 12.1.
Запустите процесс поиска решения нажатием кнопки Выполнить. В открывшемся диалоговом окне Результаты поиска решение задайте опцию Сохранить найденное решение (рис. 12.4).
Решение задачи приведено на рис. 12.5. Оно тривиально: чем меньше сотрудников и чем меньше их оклад, тем меньше месячный фонд заработной платы.
Рис. 12.3. Задание параметров поиска решения по минимизации фонда
Рис. 12.4. Сохранение найденного при поиске решения
Рис. 12.5. Минимизация фонда заработной платы
Фирма производит несколько видов продукции из одного и того же сырья — А, В и С. Реализация продукции А дает прибыль 10 р., В — 15 р. и С — 20 р. на единицу изделия.
Продукцию можно производить в любых количествах, поскольку известно, что сбыт обеспечен, но ограничены запасы сырья. Необходимо определить, какой продукции и сколько надо произвести, чтобы общая прибыль от реализации была максимальной.
Нормы расхода сырья на производство продукции каждого вида приведены в табл. 12.1.
Порядок работы
1. Запустите редактор электронных таблиц Microsoft Excel и создайте новую электронную книгу.
2. Создайте расчетную таблицу как на рис. 12.6. Введите исходные данные и формулы в электронную таблицу. Расчетные формулы имеют такой вид:
Расход сырья 1 = (количество сырья 1) * (норма расхода сырья А) + (количество сырья 2) * (норма расхода сырья В) + (количество сырья 3) * (норма расхода сырья С).
Значит, в ячейку F5 нужно ввести формулу = В5 * $В$9 + С5 * $С$9 + D5 * $D$9.
Обратите внимание, что значения количества сырья каждого вида пока не известны и будут подобраны в процессе решения задания (ячейки B9:D9 пока пустые).
(Общая прибыль по А) = (прибыль на ед. изделий А) * (количество А), следовательно в ячейку В10 следует ввести формулу = В8 * В9.
Итоговая общая прибыль = (Общая прибыль по А) + (Общая прибыль по В) + (Общая прибыль по С), значит в ячейку Е10 следует ввести формулу = СУММ(В10:О10).
Рис. 12.6. Исходные данные для Задания 12.2
3. В меню Сервис активизируйте команду Поиск решения и введите параметры поиска, как указано на рис. 12.7.
В качестве целевой ячейки укажите ячейку «Итоговая общая прибыль» (ЕЮ), в качестве изменяемых ячеек — ячейки количества сырья — (B9:D9).
Не забудьте задать максимальное значение суммарной прибыли и указать ограничения на запас сырья:
Установите параметры поиска решения (рис. 12.8). Для этого кнопкой Параметры откройте диалоговое окно Параметры поиска
Рис. 12.8. Задание параметров поиска решения
Кнопкой Выполнить запустите Поиск решения. Если вы сделали все верно, то решение будет как на рис. 12.9.
Сохраните созданный документ под именем «План производства».
^ Дополнительные задания
Используя файл «План производства» (см. задание 12.2), определить план выгодного производства, т.е. какой продукции и сколько необходимо произвести, чтобы общая прибыль от реализации была максимальной.
Выберите нормы расхода сырья на производство продукции каждого вида и ограничения по запасам сырья из таблицы соответствующего варианта (5 вариантов):
Тема: Задачи оптимизации (поиск решения) в MS Excel .
Цель: - изучение технологии поиска решения для задач оптимизации (минимизации, максимизации).
Вид работы: фронтальный
Время выполнения: 2 часа
Задания к практической работе
Задание 1. Минимизация фонда заработной платы фирмы.
Пусть известно, что для нормальной работы фирмы требуется 5…7 курьеров, 8…10 младших менеджеров, 10 менеджеров, 3 заведующих отделами, главный бухгалтер, программист, системный аналитик, генеральный директор фирмы.
Общий месячный фонд зарплаты должен быть минимален. Необходимо определить, какими должны быть оклады сотрудников фирмы, при условии, что оклад курьера не должен быть меньше 1400 р.
В качестве модели решения этой задачи возьмем линейную модель. Тогда условие задачи имеет вид N1*A1*x+N2*(A2*x+B2)+. +N8*(A8*x+B8) = Минимум, где Ni – количество работников данной специальности; x – зарплата курьера; Ai и Bi – коэффициенты заработной платы сотрудников фирмы.
Ход работы
1. Запустите редактор электронных таблиц Microsoft Excel и откройте созданный в Практической работе 4 файл «Штатное расписание».
Скопируйте содержимое листа «Штатное расписание 1» на новый лист и присвойте копии листа имя «Штатное расписание 2».
2. В меню Данные – Анализ «что – если» активизируйте команду Поиск решения (рис. 1).
3. В окне Установить целевую ячейку укажите ячейку F14, содержащую модель – суммарный фонд заработной платы.
Рисунок 1 - Задание условий для минимизации фонда заработной платы
Поскольку необходимо минимизировать общий месячный фонд зарплаты, активизируйте кнопку равный – Минимальному значению.
В окне Изменяя ячейки укажите адреса ячеек, в которых будет отражено количество курьеров и младших менеджеров, а также зарплата курьера - $E$6:$E$7:$D$3 (при задании ячеек E6, E7 и D3 держите нажатой клавишу [Ctrl]).
Используя кнопку Добавить в окнах Поиск решения и Добавление ограничений, опишите все ограничения задачи: количество курьеров изменяется от 5 до 7, младших менеджеров од 8 до 10, а зарплата курьера >1400 (рис.2).
Рисунок 2 - Добавление ограничений для минимизации фонда заработной платы
Ограничения наберите в виде
Активизируйте кнопку Параметры, введите параметры поиска, как показано на рис. 3.
Рисунок 3 - Задание параметров поиска решения по минимизации фонда заработной платы.
Окончательный вид окна Поиск решения приведен на рис. 1.
Запустите процесс поиска решения нажатием кнопки Выполнить. В открывшемся диалоговом окне Результаты поиска решения задайте опцию Сохранить найденное решение (рис. 4).
Рисунок 4 - Сохранение найденного при поиске решения
Решение задачи приведено на рис. 5. Оно тривиально: чем меньше сотрудников и чем меньше их оклад, тем меньше месячный фонд заработной платы.
Рисунок 5 - Минимизация фонда заработной платы
Задание 2. Составление плана выгодного производства.
Фирма производит несколько видов продукции из одного и того же сырья – А, В и С. Реализация продукции А дает прибыль 10 р., В – 15 р. и С – 20 р. на единицу изделия.
Продукцию можно производить в любых количествах, поскольку известно, что сбыт обеспечен, но ограничены запасы сырья. Необходимо определить, какой продукции и сколько надо произвести, чтобы общая прибыль от реализации была максимальной.
Нормы расхода сырья на производство продукции каждого вида приведены в табл. 1.
Читайте также: