Создание математической модели и решение задач с помощью систем уравнений
п.1. Алгоритм решения задач с помощью систем уравнений
Например:
Найдите два положительных числа, если известно, что сумма квадратов этих чисел равна 185, а разность квадратов равна 57.
Шаг 1
«От смысла к буквам»:
Пусть x > 0 и y > 0 – задуманные числа.
Шаг 4
«От букв к смыслу»:
Выбираем положительные корни $$ \mathrm
п.2. Примеры
Пример 1. Диагональ прямоугольника равна 10 см. Если меньшую сторону прямоугольника увеличить на 2 см, а большую уменьшить на 2 см, то диагональ не изменится. Найдите стороны прямоугольника.
Пусть a и b – стороны прямоугольника, a > b. Диагональ через стороны выражается по теореме Пифагора. По условию получаем: $$ \left\< \begin
Тогда a = b + 2 = 8
Ответ: 8 см и 6 см.
Пример 2. (задача Диофанта, III в.) Отношение двух чисел равно 3, а отношение суммы квадратов этих чисел к их сумме равно 5. Найдите эти числа.
Пусть x и y – искомые числа. По условию: $$ \left\< \begin
Пример 3. Двое рабочих могут выполнить работу за 12 дней. Если сначала один из них сделает половину всей работы, а потом остальное сделает другой, то им понадобится 25 дней. За сколько дней каждый рабочий может выполнить задание самостоятельно?
Пример 4. Бригада выполнила работу за 20 дней. Если бы в бригаде было на 4 человека больше, а рабочий день – на 1 ч дольше, то работа была бы выполнена за 10 дней. Если бы в бригаде было на 1 человека меньше, а рабочий день – на 1 ч короче, то работа была бы выполнена за 30 дней. Сколько человек было в бригаде, и сколько часов в день они работали?
II. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГРИТМА
Генетические алгоритмы достаточно универсальны и используются для решения большого числа задач, связанных с оптимизацией. Несмотря на то, что многие из таких задач имеют другие, возможно более быстрые и точные, способы решения применение генетических алгоритмов не теряет свой смысл. Это связано с тем, что в некоторых случаях, особенно при правильном применении различных технологий программирования (параллельное программирование), генетические алгоритмы могут быть более эффективны при решении поставленных задач.
Оптимизация запросов в базах данных
Разнообразные задачи на графах (задача коммивояжера, раскраска)
Настройка и обучение искусственной нейронной сети
Задачей оптимизации в математике, информатике и исследовании операций называется задача на хождения экстремума (минимума или максимума) целевой функции в некоторой области, конечно, мерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств [9].
Рассмотрим решение одной из задач на графах (задачи коммивояжера).
Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город [8].
Алгоритм решения задачи коммивояжёра с помощью генетического алгоритма:
1. Генерация первого поколения
5. Итоговое тело.
Рассмотрим решение данной задачи с помощью генетического алгоритма, предложенное В.А. Моровым [9].
Постановка задачи коммивояжера
Рассмотрим метрическую задачу коммивояжера, когда расстояния между городами можно вычислить (аналог точек на плоскости). При данной постановке задачи имеем: число городов, координаты каждого города на плоскости:
Таким образом, расстояние между городами можно находить как расстояние между двумя точками:
Необходимо найти такой путь через города g i , чтобы суммарное расстояние были минимальным/
Построение генетического алгоритма для задачи коммивояжера
Для применения генетического алгоритма необходимо определить основные структурные элементы: вид элемента популяции, процесс скрещивания, мутации и вид фитнесс-функции.
За элемент популяции (одно возможное решение) принимаем маршрут через все города. Каждый такой маршрут является возможным решением и не противоречит условиям задачи, хотя может быть совсем не оптимальным. Предполагаем, что все элементы популяции корректны, т.е. все они – потенциальные решения поставленной задачи и не являются противоречивыми.
В качестве фитнесс-функции мы принимаем функцию вида:
где Р – множество всех связей в маршруте.
Данная функция определяет минимизируемый параметр и позволяет оценивать получаемые решения. Метод мутации реализуется следующим образом: выбираем случайный город; находим связи, соответствующие этому городу; соединяем соседние города прямой связью (исключаем выбранный город из этой связи); вставляем город в случайное место.
Пример. Предположим, что решение до мутации имеет вид, представленный на рис. 2.
Решение до мутации
Применяя к нему алгоритм мутации, можем получить решение в виде представленном на рис. 3.
Решение, но после мутации
Метод скрещивания реализуется сложнее, так как требует дополнительных проверок на корректность получаемого маршрута.
Алгоритм метода скрещивания:
выбираем два маршрута из популяции, которые будут выступать в роли родителей;
в образуемые маршруты переносим связи, которые существуют в обоих маршрутах-родителях;
при несовпадающих связях предпочтение отдается связи в первом родителе для городов с четными номерами; если ее применить невозможно, то берем связи из второго родителя, если это также невозможно, то берем из первого маршрута.
При таком задании скрещивания для получения двух решений можно применять данный метод дважды, меняя маршруты-родители местами. Тогда второй потомок будет получен при условии, что при несовпадении связей предпочтение будет отдаваться второму маршруту. Пример. На рис. 4 представлен пример применения данного алгоритма скрещивания к двум решениям:
2.2 Описание программы решения линейного уравнения с помощью генетического алгоритма.
Опишем полную программу решения уравнения xa+yb+zc+rd=k, где a, b, c, d, k – переменные, x, y, z, r – угловые коэффициенты при них.
Для примера возьмем уравнение 2a+4b+5c+6d=30. Представим собственную программу его решения.
При выполнении работы были изучены генетические алгоритмы для решения различных классов оптимизационных задач и написана программа на языке Паскаль, реализующая алгоритм решения тестовой математической задачи. В качестве такой задачи было выбрано решение в натуральных числах уравнения xa+yb+zc+rd=e с четырьмя неизвестными x , y, z, r. В принципе можно легко заменить тестовое линейное уравнение на гораздо более сложное, при этом в программе придется изменять только алгоритм начального формирования популяции и функцию приспособленности.
Алгоритм существенно зависит от трех параметров: количества особей в поколении n , количества скрещиваний m , необходимых для получения следующего поколения, и вероятности мутаций ver . Так как решения тестового примера можно получить обычным перебором, есть возможность сравнивать получаемые генетическим алгоритмом решения с известным ответом. Автором работы был проделан ряд вычислительных экспериментов с целью подбора параметров алгоритма, обеспечивающих быстрое получение всех натуральных решений тестового уравнения.
Будем назвать особью набор из четырех генов ( x , y, z, r). В качестве функции приспособленности особи нами была взята функция 1/ (| xa+yb+zc+rd-e | + 1). Легко видеть, что она является неотрицательной и достигает максимума на решениях нашего уравнения.
На рисунке 5 показан процесс создания начальной популяции. Как уже было замечено выше, можно стартовать с более-менее любой начальной популяции, все равно эволюционный процесс приведет к правильным решениям. Как видно из текста программы, для создания первого поколения мы просто делаем все гены случайными числами, равномерно распределенными на промежутке [1; 20]. Попутно для каждой особи вычисляется ее функция приспособленности.
Создание массива первого поколения
Для проведения процесса скрещивания необходимо задавать вероятности каждой особи стать родителем. Логично данные вероятности делать пропорциональными функциям приспособленности, чтобы более приспособленная особь чаще становилась родителем. На рисунке 6 показан процесс вычисления данных вероятностей. Для получения вероятности i -й особи стать родителем ее функция приспособленности делится на сумму функций приспособленности всех особей. Таким образом, сумма всех вероятностей становится равной 1, а сами вероятности остаются пропорциональными функциям приспособленности. В дальнейшем единичный отрезок разбивается на отрезки, длины которых равны нашим вероятностям. Точки разбиения лежат в массиве WW .
Вычисление вероятностей скрещивания
Теперь приступаем к процессу скрещивания. Сначала выбираем двух родителей. Для этого генерируем два случайных числа, равномерно распределенных на [0;1]. Как мы помним, программа разбила единичный отрезок на отрезки, длины которых равны вероятностям особей стать родителями. Наше случайное число попадает в один из таких отрезков. Особь, которой он соответствует, делаем родителем.
Далее осуществляем скрещивание. Для этого используем метод одноточечного кроссовера. Он заключается в том, что внутри особи ставится черта. Гены, расположенные левее черты, потомок получает от одного родителя, правее – от другого. В нашем случае черту можно поставить тремя способами (отделив 1,2 или 3 гена). Таким образом, в результате одного скрещивания получаем 6 потомков.
Далее проводим мутации. Для каждого потомка генерируем случайное число, равномерно распределенное на [0;1]. Если число меньше пороговой вероятности ver , то один из генов потомка заменяем на случайное число от 1 до 20.
После этого проводим отбор. Если среди потомков есть решения уравнения, то переписываем их в массив решений и уничтожаем. Остальных потомков сортируем в порядке убывания функции приспособленности. Первые n потомков в этом списке будут образовывать следующее поколение. Соответствующий код изображен на рисунке 7.
Создание будущего поколения, определение для будущих особей функции приспособленности
В какой момент прекращать эволюционный процесс? На тестовом примере с известным ответом можно добиться появления всех решений. В реальной задаче необходимо прекращать процесс, если в течение нескольких поколений не появляются новые решения.
В ходе исследования были изучены генетические алгоритмы для разных задач оптимизации. В результате решения первой задачи исследования уточнили понятие генетического алгоритма. В своей работе, генетические алгоритмы мы рассматриваем, как поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, которые реализуют «выживание сильнейших» среди рассмотренных структур, формируя и изменяя поисковый алгоритм на основе моделирования эволюции поиска. Генетический алгоритм — это метод перебора решений для тех задач, в которых невозможно найти решение с помощью математических формул. Однако простой перебор решений в сложной многомерной задаче – это бесконечно долго. Поэтому генетический алгоритм перебирает не все решения, а только лучшие. Алгоритм берёт группу решений и ищет среди них наиболее подходящие. Затем немного изменяет их – получает новые решения, среди которых снова отбирает лучшие, а худшие отбрасывает. Таким образом, на каждом шаге работы алгоритм отбирает наиболее подходящие решения (проводит селекцию), считая, что они на следующем шаге дадут ещё более лучшие решения (эволюционируют).
В при решении второй задачи: «Рассмотреть схему генетического алгоритма» было выявлено, что существует несколько схем Генетического Алгоритма, но в основном он делится на четыре следующих этапа: создание популяции (инициализация); размножение (скрещивание); мутации; отбор (селекция).
Генетические алгоритмы достаточно универсальны и используются для решения большого числа задач, связанных с оптимизацией. В результате решения третьей задачи исследования были проанализированы возможности генетических алгоритмов для решения различных задач оптимизации: оптимизация функций; оптимизация запросов в базах данных; разнообразные задачи на графах (задача коммивояжера, раскраска); задачи компоновки; игровые стратегии и др. Более подобно в работе рассмотрено решение одной из задач на графах (задачи коммивояжера).
В результате решения четвертой задачи написана программа на языке Паскаль, реализующая разработанный алгоритм, подходящий для решения широкого класса уравнений в целых числах, данная программа проверена на тестовом примере линейного уравнения.
Таким образом, в результате работы изучены генетические алгоритмы для разных задач оптимизации и реализован алгоритм, подходящий для решения широкого класса уравнений в целых числах. Алгоритм проверен на тестовом примере линейного уравнения. Проведен ряд вычислительных экспериментов с целью подбора оптимальных параметров алгоритма. В дальнейшем планируется реализация модификаций алгоритма для задачи коммивояжера, задачи поиска локальных минимумов функции, а также некоторых других задач.
Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие / Под ред. Львовича Я.Е. — Воронеж, 1995.
Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием генетических алгоритмов: Учебное пособие. — Уфа: УГАТУ, 1999.
Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: Учебное пособие. – 2-е изд. – М: Физматлит, 2016.
Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. — М: Физматлит, 2014.
Зенович А. В., Должикова Н. Ю., Черевичная Н. В. Применение генетических алгоритмов для решения математических уравнений // Поиск (Волгоград). 2021. № 1 (11). С. 74-78.
Котлярова В.В., Бабаев А.М. Применение генетических алгоритмов для поиска решений оптимизационных задач // Сборник статей Международной научно-практической конференции : в 6 ч.. 2017. С. 20-25.
Курейчик В.М. Генетические алгоритмы. Обзор и состояние. // Новости искусственного интеллекта. 2008. №3. С. 23-26.
Курейчик, В.М. Поисковая адаптация: теория и практика / В.М. Курейчик, Б.К. Лебедев, О.К. Лебедев. – М.: Физматлит, 2006. – С. 272.
Морозов А.В. Применение генетического алгоритма к задачам оптимизации. Реализация генетического алгоритма для задачи коммивояжера // http://docplayer.ru/395699-Primenenie-geneticheskogo-algoritma-k-zadacham-optimizacii-realizaciya-geneticheskogo-algoritma-dlya-zadachi-kommivoyazhera.html (дата обращения: 12.02.2021).
Муксимова Р.Р., Кострицкая А.В. Применение генетических алгоритмов при моделирование транспортных задач (на примере задачи Коммивояжера) // Proceedings of the 4 th International Conference . 2016. С. 79-83.
Мунасыпов Р.А., Ахмеров К.А., Ахмеров К.А. Методика оптимизации нечеткого регулятора с помощью генетических алгоритмов // Фундаментальные исследования. – 2015. – № 2-15. – С. 3275-3280; URL: http://fundamental-research.ru/ru/article/view?id=37767 (дата обращения: 06.04.2021).
Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие / Т.В. Панченко. – Астрахань: Изд. дом «Астраханский университет», 2007.
Полупанов А.А. Адаптивная архитектура генетического поиска. // Перспективные информационные технологии и интеллектуальные системы, 2003.
Федоров Е.А. Исследование скорости работы генетического алгоритма и алгоритма полного перебора // Сборник избранных статей научной сессии ТУСУР. 2019. № 1-2. С. 107-109.
Алгоритмы решения простых и усложнённых уравнений в начальной школе.
Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.
Решить уравнение – найти его корень:
— решается уравнение по микро шагам , одна строка – одно действие делаем
— записывается строго в столбик
— в каждой строке только один знак = так как получаться должны равенства
— в каждой строке до проверки есть одно неизвестное , записанное буквой
— после нахождения корня уравнения эту строку подчеркнуть для проверки
— в части проверки не пишется неизвестное, вместо него пишут число – корень уравнения
Алгоритм решения простого уравнения :
1. Подчеркнуть неизвестное и вспомнить как называется компонент действия, на месте которого находится неизвестное число.
2. Вспомнить правило нахождения этого компонента.
3. Решить простое уравнение по озвученному правилу в одно действие.
4. Выполнить проверку правильности решения – переписать всё уравнение, подставив вместо неизвестного корень уравнения.
5. Записать ответ проверки – посчитать всё в левой части, записать равно под равно, и полученное число левой части написать перед равно. Оно должно получиться таким же, как и число в правой части уравнения.
1. Подчеркнуть неизвестное и вспомнить как называется компонент действия, на месте которого находится неизвестное число
Неизвестен второй множитель.
2. Вспомнить правило нахождения этого компонента.
Чтобы найти неизвестный множитель нужно произведение разделить на известный множитель.
3. Решить простое уравнение по озвученному правилу в одно действие.
4. Выполнить проверку правильности решения – переписать всё уравнение, подставив вместо неизвестного корень уравнения.
5. Записать ответ проверки – посчитать всё в левой части, записать равно под равно, и полученное число левой части написать перед равно. Оно должно получиться таким же, как и число в правой части уравнения.
Алгоритм решения усложнённого уравнения :
1. Найти и сразу упростить в выражении то, что можно — посчитать то действие, что сразу легко решается без дополнительных правил.
2. Подчеркнуть неизвестное и вспомнить как называется компонент действия, на месте которого находится неизвестное число
3. Вспомнить правило нахождения этого компонента.
4. Решить простое уравнение по озвученному правилу в одно действие.
5. Выполнить проверку правильности решения – переписать всё уравнение, подставив вместо неизвестного корень уравнения.
6. Записать ответ проверки – посчитать всё в левой части, записать равно под равно, и полученное число левой части написать перед равно. Посчитать всё в правой части и записать после равно полученное число Оба числа должны получиться равными.
1. Найти и сразу упростить в выражении то, что можно — посчитать то действие, что сразу легко решается без дополнительных правил.
Х + 500 × 3 = 2000 могу 500 ×3, получу 1500
Получим простое уравнение :
2. Подчеркнуть неизвестное и вспомнить как называется компонент действия, на месте которого находится неизвестное число.
Х + 1500 = 2000 неизвестное стоит на месте 1-го слагаемого
3. Вспомнить правило нахождения этого компонента.
Чтобы найти неизвестное слагаемое нужно из суммы вычесть известное слагаемое.
4. Решить простое уравнение по озвученному правилу в одно действие.
5. Выполнить проверку правильности решения – переписать всё уравнение, подставив вместо неизвестного корень уравнения.
500 + 500 × 3 = 2000
6. Записать ответ проверки – посчитать всё в левой части, записать равно под равно, и полученное число левой части написать перед равно. Посчитать всё в правой части и записать после равно полученное число Оба числа должны получиться равными.
Х + 500 × 3 = 2000
500 + 500 × 3 = 2000
Алгоритм решения сложного уравнения :
1. Найти и сразу упростить в выражении то, что можно — посчитать то действие, что сразу легко решается без дополнительных правил.(если есть)
2. Разбить выражения, записанные в одной или обеих частях уравнения, на части — расставить порядок действий. Определить неизвестный компонент по последнему действию и подчеркнуть его.
3. Вспомнить правило нахождения данного компонента, найти число по правилу — узнать чему будет равна часть с неизвестным.
4. Найти и вспомнить как называется новый компонент — неизвестное число в полученном простом уравнении
5. Решить полученное простое уравнение.
6. Выполнить проверку правильности решения – переписать всё уравнение, подставив вместо неизвестного корень уравнения.
7. Записать ответ проверки – посчитать всё в правой и левой части, записать равно под равно, должно получиться одинаковое число в правой и левой части.
1. Найти и сразу упростить в выражении то, что можно — посчитать то действие, что сразу легко решается без дополнительных правил.(если есть)
Пропускаем – нельзя упростить.
2. Разбить выражения, записанные в одной или обеих частях уравнения, на части — расставить порядок действий. Определить где находится неизвестный компонент –всё до последнего действия и подчеркнуть его.
3. Вспомнить правило нахождения данного компонента, найти число по правилу — узнать чему будет равна часть с неизвестным.
Неизвестно уменьшаемое, чтобы найти неизвестное уменьшаемое надо к вычитаемому прибавить разность.
4. Найти и вспомнить как называется новый компонент — неизвестное число в полученном уравнении
получили простое уравнение, такое уравнение мы умеем решать
Неизвестно слагаемое, чтобы найти неизвестное слагаемое надо из суммы вычесть известное слагаемое.
5. Решить полученное простое уравнение.
6. Выполнить проверку правильности решения – переписать всё уравнение, подставив вместо неизвестного корень уравнения.
( 109 + 29) – 48 = 90
7. Записать ответ проверки – посчитать всё в правой и левой части, записать равно под равно, должно получиться одинаковое число в правой и левой части.
http://school-science.ru/12/7/48343
http://infourok.ru/algoritmi-resheniya-prostih-i-uslozhnyonnih-uravneniy-v-nachalnoy-shkole-3158619.html