Математические методы в программировании

СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ
Серия основана в 2001 году





В.П. АГАЛЬЦОВ


МАТЕМАТИЧЕСКИЕ МЕТОДЫ В ПРОГРАММИРОВАНИИ

УЧЕБНИК
2-е издание, переработанное и дополненное




                            Рекомендовано Министерством образования Российской Федерации в качестве учебника для студентов учреждений среднего профессионального образования, обучающихся по группе специальностей «Информатика и вычислительная техника»


znanium.com

Москва
ИД «ФОРУМ» — ИНФРА-М
2023

УДК 51-7(075.32)
ББК 22.18я723 А23



       Рецензенты:
          Четвериков В.М., доктор физико-математических наук, профессор, заведующий кафедрой «Математическая экономика» Московского института электроники и математики (технический университет);
          Рубальская О.Н., кандидат технических наук, доцент кафедры «Информатика» Российского государственного социального университета

       Агальцов В.П.
А23 Математические методы в программировании : учебник / В.П. Агальцов. — 2-е изд., перераб. и доп. — Москва : ИД «ФОРУМ» : ИНФРА-М, 2023. — 240 с. — (Среднее профессиональное образование).
          ISBN 978-5-8199-0410-7 (ИД «ФОРУМ»)
          ISBN 978-5-16-016863-0 (ИНФРА-М, print)
          ISBN 978-5-16-109152-4 (ИНФРА-М, online)
          В учебнике рассматриваются прикладные математические методы и модели, в том числе методы математического программирования (поиск экстремума, линейное, нелинейное, динамическое программирование), системы массового обслуживания.
          Особое внимание уделено целостному, простому и ясному изложению учебного материала. Показаны связь между отдельными главами, использование однотипных методов (алгоритмов) для решения разных задач. Приведено подробное описание всех алгоритмов.
          Предназначен для учащихся средних профессиональных учебных заведении по группе специальностей «Информатика и вычислительная техника», также может быть полезен студентам высших учебных заведений, преподавателям и программистам.

УДК 51-7(075.32)
ББК 22.18я723











ISBN 978-5-8199-0410-7 (ИД «ФОРУМ»)
ISBN 978-5-16-016863-0 (ИНФРА-М, print)
ISBN 978-5-16-109152-4 (ИНФРА-М, online)


© Агальцов В.П., 2006
© Агальцов В.П., 2010,
   с изменениями
© ИД «ФОРУМ», 2010

                                          Горячо любимой Галине Серафимовне посвящаю

Предисловие
   Проблема выполнения различных вычислений Оыла актуальна во все времена. По мере развития общественно-экономических отношений усложнялись поставленные задачи, которые для своего решения требовали разработки новых методов вычислений. На смену простейшим арифметическим и геометрическим вычислениям пришли алгебраические и тригонометрические вычисления.
   Организация современного производства требует не только наличия современных станков и оборудования, но и разработки новых технологических процессов и современных методов управления производством. Для решения каждой из поставленных задач разрабатываются математические модели, анализируя которые удается найти наилучшее решение поставленной задачи. Создание математической модели — сложная и кропотливая работа, которая в современных условиях под силу коллективам разработчиков. Для создания математической модели одного и того же объекта различные коллективы могут использовать различный математический аппарат. В коллектив разработчиков математических моделей привлекаются высококвалифицированные специалисты, которые, с одной стороны, хорошо знают физические процессы, протекающие при работе объекта, и, с другой стороны, глубоко и всесторонне владеют соответствующим математическим аппаратом. После создания математической модели специалистами-аналитиками за дело принимаются специалисты-программисты, которые реализуют созданную модель в виде программных кодов. Далее с математической моделью работают специалисты-практики. Целенаправленно воздействуя на модель, они изучают ее поведение и подбирают оптимальный режим работы для реального объекта.
   Целью настоящего учебника является: научить студентов от словесного описания задачи перейти к абстрактной математической модели, реализовать математическую модель в виде программных кодов, провести исследование математической модели и получить вектор входных воздействий, доставляющий оптимальное решение. Конечно же, речь идет о простых математических моделях, позволяющих решить элементарные задачи.
   Учебник содержит девять глав, в которых рассмотрены следующие вопросы.
   В первой главе раскрыты основные принципы построения математических моделей, дана их классификация, введены основные определения.

Предисловие

    Вторая глава посвящена задаче линейного программирования и основному методу решения таких задач — симплексному методу. Показана последовательность решения задачи линейного программирования.
    В третьей главе рассматривается транспортная задача, т. е. нахождение оптимального плана перевозок грузов от производителей к потребителям. Рассмотрены три метода нахождения опорного плана перевозок и три метода нахождения оптимального плана перевозок.
    В четвертой главе даны методы целочисленного решения задачи линейного программирования. Простое округление результата, полученного симплексным методом, не приводит к приемлемому решению, и специальные целочисленные методы позволяют найти оптимальное целочисленное решение. В главе рассмотрены четыре метода.
    Пятая глава раскрывает принципы динамического программирования, позволяющие решить проблему нахождения оптимального (кратчайшего) пути при сооружении различных хозяйственных объектов.
    В шестой главе рассмотрены методы решения нелинейных задач. Некоторые практические задачи невозможно описать линейными уравнениями и необходимо использовать трудоемкие методы нелинейного программирования. В главе рассмотрены три метода.
    Седьмая глава посвящена сетевому планированию производства и распределения ресурсов. Излагаются вопросы, связанные с составлением сетевого графика выполнения работ, нахождения критического пути и определения временных ресурсов.
    В восьмой главе рассматриваются вопросы, связанные с функционированием систем массового обслуживания, определением характеристик этих систем и финальных вероятностей состояний системы.
    Девятая глава посвящена исследованию игровых моделей и поиску стратегий поведения в условиях полной или частичной неопределенности. Результаты исследования модели носят рекомендательный характер, позволяют ориентироваться в сложившейся ситуации и принять правильное решение.
    Учебник написан в полном соответствии с требованиями Государственного образовательного стандарта по специальностям 230105 и 230103 к минимуму знаний и практических умений. Объем учебника соответствует количеству часов аудиторных занятий по дисциплине «Математические методы».
    Автор будет благодарен читателям, которые пожелают прислать свои замечания и уточнения к тексту учебника по адресу редакции: forum-books@mail.ru.

Глава 1




                Понятие модели








        1.1. Классификация моделей

   По мерс развития науки и техники перед человеком все чаще встает проблема: «Как найти правильное решение?». Для облегчения решения этой задачи реальные процессы (или объекты) заменяются их аналогами или моделями. Затем производится анализ поведения модели в тех или иных условиях с помощью персонального компьютера. В этом случае говорят о компьютерном моделировании. Но персональный компьютер может работать только с математическими моделями, которые с помощью языков программирования переводятся в набор машинных кодов, которые и обрабатывает персональный компьютер. Какое же место занимают математические модели и как они получаются?
   Современные технические и экономические системы (объекты или процессы) имеют устойчивую тенденцию усложнения в своем развитии. Очень часто нельзя поставить эксперимент на реальной системе (объекте или процессе) по многим причинам: громоздкость систем и, как следствие, невозможно правильно управлять многими параметрами, длительность по времени прохождения процессов в реальной системе, слишком большая цена ошибки при неправильном управлении системой и т. д.
   Для изучения сложных систем различных видов, с целью оптимального управления ими необходимо создать их модели. На этих моделях изучается поведение реальных систем (объектов или процессов), влияние различных внешних воздействий на работу системы, изучение закономерностей их функционирования и развития.
   Построение математической модели процесса, явления или объекта начинается с построения упрощенного варианта модели, в котором учитываются только основные черты. В результате просле

Гпава 1. Понятие модели

живаются основные связи между входными параметрами, ограничениями и показателем эффективности. Общего подхода к построению модели нет. В каждом конкретном случае при построении математической модели учитывается большое количество факторов: цель построения модели, круг решаемых задач, точность описания модели и точность выполнения вычислений. Математическая модель должна отражать все существенные факторы, определяющие ее поведение, и при этом быть простой и удобной для восприятия результатов. Каждая математическая модель процесса, явления или объекта в своей основе имеет математический количественный метод.
   Применение математических количественных методов для обоснования выбора того или иного управляющего решения во всех областях человеческой деятельности называется исследованием операций. Целью исследования операций является нахождение с использованием специального математического аппарата решения, удовлетворяющего заданным условиям. На самом деле при решении практически любой задачи имеется неограниченное количество решений. Множество решений, удовлетворяющих заданным условиям (ограничениям), называется допустимым множеством решений. Выбор из множества допустимых решений одного решения, наилучшего в каком-либо смысле, называемого оптимальным решением, и есть задача исследования операций. Надо помнить, что оптимальное решение является наилучшим только при заданных ограничениях. Если изменить ограничения (увеличить или уменьшить ресурсы), то и оптимальное решение будет другим. При решении задачи исследования операций без ограничений на ресурсы можно ставить вопрос о нахождении наилучшего решения среди локальных оптимальных решений. Такое наилучшее решение называется глобальным экстремумом (минимумом или максимумом). Нахождение глобального экстремума — очень сложная задача и, как правило, найти его не удается.
   Поиск локального или глобального экстремума выполняется набором некоторых действий, подчиняющихся общей идее определения экстремума (плану поиска решения), оформленной в виде алгоритма поиска. Каждое отдельное действие, входящее в план решения, называется операцией. Операция всегда является управляемым воздействием на модель исследуемого объекта, т. е. исследователь задает набор входных воздействий на модель и получает реакцию на выполненное воздействие. Анализируя реакции на

1.1. Классификация моделей

7

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


   Модель — это материальный или идеальный объект, заменяющий оригинал, наделенный основными характеристиками (чертами) оригинала и предназначенный для проведения некоторых дей-ствий над ним с целью получения новых сведений об оригинале.


   Примеры моделей:
   1. Рисунок будущего здания.
   По этой модели можно оценить эстетические особенности здания, как оно вписывается в существующую застройку и т. д.
   2. Макет радиотелеграфа.
   Макет представляет собой уменьшенную копию реального радиотелеграфа и воспроизводит основные функциональные возможности оригинала. Эта модель предназначена для изучения основных принципов работы радиотелеграфа.
   3. Электрическая схема радиоприемника.
   Во время проведения лекций по радиотехнике по этой модели удобно рассказывать о назначении отдельных узлов (блоков) радиоприемника.
   4.     Система уравнений, описывающих полет артиллерийского снаряда.
   В этой модели в качестве коэффициентов используют массу порохового заряда, массу снаряда, угол наклона ствола орудия и т. д.

g                   Гпава 1. Понятие модели

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


Рис. 1.1. Классификация моделей

   Материальные модели. Модели этой группы реализованы в виде реальных физических объектов — макетов. Как правило, макет — это увеличенная или уменьшенная копия реального объекта. Макеты связаны с оригиналом различными характеристиками: геометрическими, физическими и т.д. Изучение оригинала производится путем воздействия на макет и обработкой реакций макета на суммарное воздействие. Такой метод исследования называется экспериментальным.
   Материальные модели подразделяются на макеты подобия (физические модели) и заменяющие макеты (аналоговые модели). Для создания аналоговых моделей используется принцип подобия. Различные по физической природе явления могут описываться одинаковыми математическими уравнениями, что допускает исследование различных явлений на одной модели.
   Идеальные модели. В этом случае создается либо мысленный образ (сущность) объекта или явления в памяти человека или компьютера, либо абстрактная математическая модель. Такая модель носит теоретический характер.
   Идеальные модели подразделяются на:
   •   сущностные (интерактивные), создаваемые в памяти человека или компьютера, для создания которых, как правило, не требуется строгих уравнений. Законы функционирования таких моделей строятся на ситуациях и предположениях, основанных на наблюдениях за оригиналом (объектом или явлением);

1.1. Классификация моделей

9

   •  символьные, построенные на наборе символов: алфавит, пиктограммы, технические символы и т. д. Символьные модели выступают в виде графиков, чертежей, рисунков, текстов, формул и т.д. Одним из видов символьных моделей являются математические модели (рис. 1.2).


Рис. 1.2. Классификация математических моделей

    Компьютерное моделирование имеет дело с математическими моделями. С помощью математических уравнений можно описать принцип функционирования практически любого реального объекта, явления или процесса, протекающего в природе, экономике или обществе. Естественно, что для описания всего многообразия объектов и явлений используется различный математический аппарат, что и определяет многообразие математических моделей (рис. 1.2). По степени точности математические модели бывают аналитические и статистические. В аналитических моделях устанавливаются точные зависимости между входными параметрами и выходным параметром целевой функции (критерием эффективности). Эти зависимости записываются в виде алгебраических уравнений, дифференциальных уравнений, уравнений в частных производных и т. д. Аналитические модели используются для описания простых процессов, явлений и объектов и учитывают небольшое количество факторов. Такие модели грубы, но лучше приспособлены к отысканию оптимального решения и имеют наглядные и простые решения. Если поведение модели зависит от многих факторов (входных параметров и ограничений), носящих случайный характер и коррели

Гпава 1. Понятие модели

рованных между собой, то аналитическую модель, как правило, построить невозможно и в этом случае используют статистическую модель.
   Статистическая модель строится на основе данных (наблюдений) за поведением реального процесса, явления или объекта. Исходные данные носят случайный характер. Каждое воздействие на такую модель называется реализацией. Реализация состоит из цепочки расчетов, выполняемых по специально разработанной процедуре, которая учитывает влияние случайных факторов. После выполнения большого количества реализаций полученные результаты обрабатываются специальными методами. В результате получают усредненные характеристики (математическое ожидание и дисперсия) процесса, явления или объекта. Статистические модели позволяют учитывать большое количество факторов, более точны, чем аналитические модели, но более громоздки и требуют много машинного времени для получения результата. Полученные результаты носят усредненный (приближенный) характер, плохо воспринимаются, плохо приспособлены к поиску оптимального решения.
   Дескриптивные модели — описательные модели (description — описание). Объект, явление или процесс описываются математическими уравнениями (законами функционирования). Наиболее часто дескриптивные модели используются в механике, физике, химии и т. д. и описывают протекающие процессы без вмешательства в ход событий.
   Оптимизационные модели предназначены для управления объектом, явлением или процессом. И строятся с целью получения наилучших результатов при изменении управляющих факторов (параметров).
   Игровые модели. Применяются для управления процессами, которые противодействуют исследователю.
   Имитационные модели. Используются для моделирования сложных технических систем или общественных процессов, когда не ясно, какую цель или цели надо достигнуть. То есть речь идет о прогнозе развития системы или процесса в зависимости от принятой стратегии управления.
   Многокритериальные модели. Применяются для нахождения наилучшего решения по нескольким целевым функциям (направлениям).
   Модели прогнозирования. Позволяют создать прогноз о поведении объекта или системы. Прогноз носит приближенный характер и используется для принятия решения ответственным лицом.