Леоненков а в решение задач оптимизации в среде ms excel
Обновлено: 07.07.2024
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
СПб.: БХВ-Петербург, 2005. — 701 с. — ISBN: 5941575033.
Решение задач оптимизации в среде MS Excel — Рассматриваются методы и алгоритмы практического решения типовых задач оптимизации всех основных классов. Подробно описываются теоретические основы и практические особенности постановки и решения соответствующих задач. Для типовых задач оптимизации предлагаются несколько способов их решения и приводятся рекомендации по выбору наиболее эффективного из них.
Представлены пошаговые инструкции по выполнению практических действий, связанных с подготовкой исходных данных и последующего решения прикладных задач оптимизации всех основных классов. Содержится доступное введение в программирование на языке VBA и приводятся листинги программ, расширяющих функциональность MS Excel.
Содержание:
Предисловие.
Задачи оптимизации и их основные свойства.
Общая характеристика задач оптимизации.
Основные приемы практической работы в среде MS Excel.
Задачи непрерывной оптимизации.
Задачи нелинейного программирования.
Задачи линейного программирования.
Задачи дискретной и комбинаторной оптимизации.
Задачи целочисленного линейного программирования.
Задачи оптимизации с булевыми переменными.
Задачи оптимизации на графах.
Задачи комбинаторной оптимизации.
Задачи многокритериальной оптимизации.
Задачи многокритериального линейного и целочисленного программирования.
Задачи многокритериальной булевой оптимизации.
Программирование задач оптимизации в среде Excel.
Алгоритмы и программы решения задач оптимизации на графах.
Алгоритмы и программы решения задач комбинаторной оптимизации.
Приложения:
Основные понятия теории множеств, теории графов и комбинаторного анализа.
Назначение операций главного меню программы электронных таблиц MS Office Excel 2003.
Назначение операций главного меню редактора Visual Basic пакета MS Office System 2003.
Список литературы.
Предметный указатель.
Читайте также: