XXVII Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Применение математических методов при выборе кружков и секций

• Авторы
• Руководители
• Файлы работы

Царев Л.А. 1

---

1МОУ СОШ «Образовательный комплекс имени Б.Н. Богачева» Центр образования лицей № 2

Лапина Е.Ю. 1

---

1МОУ СОШ «Образовательный комплекс имени Б.Н. Богачева» Центр образования лицей № 2

Работа в формате PDF

206.1 KB

Введение

Почти все мои одноклассники посещают кружки и секции. Дополнительные занятия в кружках и секциях дают возможность реализовать свои увлечения, попробовать и почувствовать свои возможности, раскрыть и развить свои способности. Исследования медицинской школы Гарварда показывают, что хобби делает людей счастливыми.

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

В литературе [1, 2, 4] рассматриваются возможности применения методов оптимизации в экономике, технике, автоматике, управлении производством. В представленной работе «Применение математических методов при выборе кружков и секций» исследована возможность применения известных математических методов оптимизации к решению практической проблемы выбора внеурочных занятий.

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

Объект исследования: задача выбора оптимального варианта решения.

Предмет исследования: методы поиска наилучшего решения при наличии альтернатив.

Гипотеза: в повседневной жизни возникают проблемы, которые можно сформулировать как математическую задачу и применить для её решения математические методы.

Цель исследования: определить возможность применения математических методов для решения задачи выбора кружков и секций.

Задачи исследования:

1. Узнать, что такое оптимизация.

2. Узнать, какие методы применяются при решении задач оптимального выбора.

3. Научиться решать задачу подбора варианта кружков и секций.

4. Разработать алгоритм решения задачи с применением электронных таблиц.

Методы исследования:

1. Изучение;

2. Анализ;

3. Вычислительный эксперимент.

Работа носит прикладной характер.

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

Основная часть

1. История развития методов оптимизации

На протяжении всей своей эволюции человек, совершая те или иные действия, стремился вести себя так, чтобы достигаемый результат оказался в определенном смысле наилучшим. Двигаясь из одного пункта в другой, он стремился найти кратчайший среди возможных путь. Строя жилище, он искал такую его геометрию, которая при наименьшем расходе топлива, обеспечивала приемлемо комфортные условия существования. Занимаясь строительством кораблей, он пытался придать им такую форму, при которой вода оказывала бы наименьшее сопротивление. А практики – землеустроители еще в 17 веке использовали основные положения оптимального проектирования (кратчайшее расстояние между двумя точками – прямая и др.) [6].

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

Оптимизация (по латыни optimus – наилучший) – целенаправленная деятельность, заключающаяся в получении наилучших результатов при некоторых условиях. Термин «оптимум» был введен в 18 веке Готфридом В. Лейбницем и в основном рассматривался в применении к теологии, учении о религиозных догматах и религиозной культуре и их необходимости для человека. Термин связывают с именем богини древнеиталийского племени сабинов Опы (богиня плодородия, урожая и богатства). Опа – жена бога времени Сатурна и мать Юпитера (хранителя римского государства). В одной руке Опа держит рог изобилия (мифический источник благ), а в другой – символ измерения и решения весы [1].

Лейбниц в своей философской теории излагал соображения о существующем мире как об оптимуме. Это переводилось как наилучший из всех возможных миров.

Большой вклад в развитие основных положений теории внесли – Пьер Ферма, Даниил Бернулли, Леонард Эйлера, Жозеф Л. Лагранж, Карл Вейерштрасс, Карл Г. Якоби, Жозеф Фурье, Леонид Витальевич Канторович, Джордж Б. Данциг, Ричард Беллман.

Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись редко, так как это требовало огромной вычислительной работы. Без вычислительной техники такие методы реализовать было очень трудно. С появлением компьютеров к 70-м годам 20 века сформирован раздел прикладной математики – теория оптимизации, а для решения таких задач стали использоваться специализированные пакеты прикладных программ, например MS Excel, а также специальные языки программирования.

2. Общая постановка задачи оптимизации

Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема.

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

Решение задачи оптимизации – это поиск определенного набора значений параметров, которому соответствует оптимальное (минимальное или максимальное) значение критерия оптимизации.

Математическая постановка задачи включает несколько шагов:

1. Определить искомые параметры:

   1. Что нужно найти?

   2. Что можно изменять, чем можно управлять при решении задачи?

2. Определить допустимые решения:

   1. Какие есть ограничения на значения параметров?

3. Определить критерий оптимизации:

   1. Что является показателем качества?

   2. Как этот показатель зависит от параметров?

3. Средства пакетов прикладных программ для решения задач оптимизации

Для решения математических задач созданы мощные математические пакеты, но при этом они же и очень сложные.

«Простые задачи должны решаться просто». Этому требованию соответствуют вычислительные возможности программы MS Excel. Применение электронных таблиц упрощает работу с данными и позволяет получать результаты без проведения расчётов вручную или специального программирования. Для решения задач оптимизации в MS Excel используется инструмент «Поиск решения» [3]. Применение этого инструмента может помочь в решении огромного количества задач. Функция берет данные, перебирает их и выдает самое лучшее решение из возможных.

Общий алгоритм решения оптимизационных задач в MS Excel:

1. Составить математическую модель.

2. Ввести на рабочий лист Excel условия задачи:

а) создать таблицу на рабочем листе для ввода условий задачи;

б) ввести исходные данные, критерий оптимизации, ограничения.

3. Выполнить команду «Данные»  «Анализ»  «Поиск решения».

4. Указать параметры в диалоговом окне «Параметры поиска решения», выполнить решение.

5. Проанализировать полученные результаты.

4. Построение модели задачи выбора кружков и секций

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

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

Задача выбора кружков и секций похожа на классическую задачу, называемую проблемой «рюкзака», которая взяла свое название из аналогии с практической ситуацией, подобной проблеме упаковки рюкзака. Необходимо упаковать как можно больше ценных предметов, не превышая грузоподъемности багажа [4].

В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную ценность при одновременном соблюдении ограничения на суммарный вес [4, 5].

Сформулируем задачу подбора кружков и секций аналогичным образом. Пусть школьник выбрал n различных кружков и секций, которые хотел бы посещать. Ценность i-го кружка составляет v_i. V_i. – экспертная оценка, то есть дается школьником самостоятельно. Также по каждому кружку задается w_i– трудоемкость в часах. Нужно подобрать такой набор занятий, чтобы суммарная занятость не превысила W часов, а ценность занятий была наибольшей.

Я решил, что смогу уделять дополнительным занятиям не более 10 часов в неделю, а ценность предметов задается самостоятельно по трёхбалльной шкале. Каждый кружок или секцию можно либо взять один раз, либо не взять (взять – 1, не взять – 0). Тогда каждому кружку и секции соответствует переменная х_i– выбор кружка (0 или 1).

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

Таблица 1

Пример исходной таблицы для решения задачи выбора

Для того, чтобы определиться с выбором, нужно рассмотреть все возможные варианты и выбрать наиболее ценные.

Возможные варианты решений (трудоемкость 10 часов):

{С, Ш, Х, Я} Приоритетная оценка = 10 баллов

{С, Ш, П, Я} Приоритетная оценка = 10 баллов

{С, Ш, К, Я} Приоритетная оценка = 10 баллов

{С, Ш, П, Х} Приоритетная оценка = 8 баллов

{С, Ш, П, К} Приоритетная оценка = 8 баллов

{С, Ш, Х, К} Приоритетная оценка = 8 баллов

{С, Х, К, Я, М} Приоритетная оценка = 10 баллов

{С, Х, К, П, М} Приоритетная оценка = 10 баллов

{С, Х, П, Я, М} Приоритетная оценка = 10 баллов

{С, П, К, Я, М} Приоритетная оценка = 10 баллов

{Ш, Х, К, Я, М} Приоритетная оценка = 10 баллов

{Ш, Х, К, П, М} Приоритетная оценка = 10 баллов

{Ш, Х, П, Я, М} Приоритетная оценка = 10 баллов

{Ш, П, К, Я, М} Приоритетная оценка = 10 баллов

11 вариантов имеют ценность 10 баллов.

Возможные варианты решений (трудоемкость 9 часов):

{С, Ш, М, Я} Приоритетная оценка = 11 баллов

{С, Ш, М, Х} Приоритетная оценка = 10 баллов

Можно заметить, что и у других наборов с трудоёмкостью 9 часов приоритетная оценка будет ниже 11 баллов. Таким образом, решением будет набор {С, Ш, М, Я} Трудоемкость = 9 часов Приоритетная оценка = 11 баллов.

Полный перебор вариантов решения является очень трудоёмким методом решения задачи. Формировать наборы можно добавлением в изначально пустой набор. Естественно, выбрать сначала те, у которых самый высокий приоритет. Суммарная трудоемкость составила 8 часов в неделю, а ценность равна 9. Я могу добавить еще занятия, так как есть еще 2 свободных часа. Это можно сделать двумя способами: либо выбрать один из кружков с приоритетом 1, тогда ценность увеличится на 1 и будет равна 10, либо выбрать кружок в ценностью 2, но трудоемкостью 1, тогда ценность будет равна 11, а трудоемкость равна 9. Если выбирать лучший вариант их этих двух, то следует выбрать второй, так как он дает большее значение по приоритетам. Тогда мой выбор будет: Спортивная секция, Шахматы, Английский язык, Актерское мастерство, а недельная нагрузка составит 9 часов.

Можно предложить другой способ формирования наборов: считать набором весь список кружков и секций, а затем «выкидывать» наименее ценные, пока не будет верно ограничение по суммарной нагрузке.

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

При выборе кружков и секций возможна ситуация, когда два кружка по расписанию идут в одно и то же время, поэтому не могут быть выбраны одновременно. Для формализации этой ситуации я ввёл ограничение: «Вместе не могут быть выбраны Художественная студия и Актерское мастерство, а также Конструирование и Программирование». Для моделирования ограничения «Вместе не могут быть выбраны …» используется ограничение в виде неравенства: , где х_i, х_j – переменные, соответствующие кружкам и секциям, участвующим в ограничении.

Математическая постановка задачи (для приведенного примера) имеет вид:

5. Решение задачи выбора кружков и секций в MS Excel

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

Затем я добавил в таблицу исходные данные: столбец Выбран кружок (значения в ячейках этого столбца могут быть 0 или 1). Сначала я задал все значения равными 0. Это будет область изменяемых ячеек (неизвестные), значения которых будут найдены в процессе решения. Еще добавил два столбца «Нагрузка» (значения вычисляются по формуле «Выбран кружок» * «Трудоемкость») и «Ценность» (значения вычисляются по формуле «Выбран кружок» * «Приоритетная оценка») для расчёта суммарной нагрузки и ценности, а также строку «Итого», содержащую итоговые значения суммарной нагрузки и ценности для того, чтобы определить ограничение по нагрузке, и значение, в какой ячейке должно быть наибольшим. Для моделирования ограничения «Вместе не могут быть» я добавил столбец в таблицу, где записал формулы: сумма значений ячеек из столбца «Выбран кружок» и строк, соответствующих кружкам, которые не должны быть выбраны одновременно. Таким образом, в этом столбце две заполненные ячейки (2 ограничения: «Конструирование» + «Программирование» и «Художественная студия + Актерское мастерство»). Значения в этих ячейках не должны превышать 1.

После подготовки исходных данных необходимо выполнить команду «Данные»  «Анализ»  «Поиск решения». В диалоговом окне «Параметры поиска решения» (Приложение 1) указать параметры: значение, в какой ячейке должно быть максимальным, значения в каких ячейках изменять при поиске решения, ограничения. Решение (изменяемые ячейки) могут принимать значения либо 0, либо 1, поэтому я установил для них тип «бинарное», а также значения удовлетворять ограничению по недельной нагрузке (не больше 10 часов). Также задал ограничения для кружков, которые не могут быть одновременно. После указания необходимых параметров, можно найти решение. Найденное решение показано в Приложении 1. Значение 1 в ячейке в столбце Выбран кружок означает, что кружок выбран, 0 – не выбран.

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

Заключение

В результате проведенного исследования, я доказал свою гипотезу о возможности применения математических методов при решении вопросов, которые возникают в повседневной жизни, в частности при выборе набора кружков и секций. Я получил решение задачи с помощью математического пакета MS Excel. Таким образом, математика помогла мне решить проблему подбора кружков и секций.

В результате проделанной работы я узнал, как сформулировать практическую задачу математически, и применил эти знания для задачи подбора кружков. Одним из методов решения задачи подбора кружков является метод полного перебора вариантов, но он очень трудоемкий, занимает много времени, поэтому для решения практических задач он применяется редко. Я узнал общий алгоритм решения оптимизационных задач в MS Excel и на основе общего алгоритма разработал алгоритм для решения своей задачи. Недостатком предложенного способа решения является следующее: если существуют равнозначные оптимальные решения, получено будет только одно из них. Поэтому направлением дальнейших исследований может быть разработка инструмента, позволяющего получать несколько равнозначных решений при их наличии.

Список использованных источников

1. История становления и развития теории оптимизации [Электронный ресурс]: Теория и методы оптимизации. – URL: https://studme.org/183569/ matematika_himiya_fizik/istoriya_stanovleniya_razvitiya_teorii_optimizatsii.

2. Методы оптимизации: пособие / Р. Габасов [и др.]. – Минск: Четыре четверти, 2011. – 472 с.

3. Самоучитель Excel с примерами для пользователей среднего уровня [Электронный ресурс]: ExcelTABLE.com. – URL: https://exceltable.com/uroki-excel/samouchitel-excel-s-primerami

4. Ковалёв, М. М. Дискретная оптимизация: Целочисленное программирование / М. М. Ковалёв. – Изд. 3-е.- M.: Ленанд, 2011. – 192 с.

5. Элементы математики в задачах (с решениями и комментариями). Ч. I/ Т. И. Голенищева-Кутузова, А. Д. Казанцев, Ю. Г. Кудряшов и др. – М.: МЦНМО, 2010. – 248 с.

6. Кордемский, Б. А. Математическая смекалка / Б.А. Кордемский. – 3-е изд., [испр.]. – М.: Гостехиздат, 1956. – 576 с.

Приложение 1

Решение задачи средствами MS Excel

Подготовка данных для задачи подбора кружков и секций в MS Excel

Начальные значения задачи

Параметры и ограничения

Решение сформировано