Материал: Математический пакет Maple

;

игрок II стремится выбрать стратегию , на которой достигается

;

Если , то пара  составляет седловую точку игры, то есть выполняется двойное неравенство

Число  называется значением игры; стратегии  называются оптимальным и чистыми стратегиями игроков I и II соответственно. Если , то всегда ; в этом случае в игре седловой точки нет, а оптимальные стратегии игроков следует искать среди их смешанных стратегий (то есть вероятностных распределений на множестве чистых стратегий). В этом случае игроки оперируют уже с математическими ожиданиями выигрышей.

Основная теорема теории Матричные игры (теорема Неймана о минимаксе) утверждает, что в любой Матричные игры существуют оптимальные смешанные стратегии , на которых достигаемые «минимаксы» равны (общее их значение есть значение игры). Например, игра с матрицей  имеет седловую точку при , а значение игры равно 2; игра с матрицей  не имеет седловой точки. Для неё оптимальные смешанные стратегии суть ; значение игры равно .

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

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

.1.3 Транспортная задача

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

В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может также решаться с ограничениями и без ограничений.

.1.4 Потоки в сетях

Потоки в сетях - функция, сопоставляющая дугам данной сети (ориентированного графа) некоторые числа.

Сетью называется связный граф (обычно, не орграф и не мультиграф), в котором заданы «пропускные способности» ребер, т. е. числа . Это числа большие или равные нулю, причем , тогда и только тогда, когда нет ребра, соединяющего вершины  и . Таким образом, можно считать, что пропускные способности ребер заданы для любой пары вершин. В дискретной математике пропускные способности ребер, как и все возникающие константы, считаются целыми числами (или рациональными, что одно и то же, так как рациональные числа отличаются от целых только единицами измерения). Заметим, что сети имеют огромные приложения, в частности, «сети планирования» (имеется в виду планирование производства некоторых новых, достаточно сложных изделий), где «пропускные способности» ребер - это время, за которое нужно из нескольких узлов изделия (вершин графа) получить другой (более сложный) узел. Сетевое планирование здесь не исследуется, так как гораздо больший интерес представляет сеть связи, где пропускные способности ребер - это обычно «количество одновременных разговоров», которые могут происходить между телефонными узлами (вершинами графа).

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

) числа , причем если , то  (нет встречных перевозок);

) числа  (соответствующих пропускных способностей ребер);

) если вершина с номером  - промежуточная (не совпадает с источником и стоком), то

,

т.е. количество «груза», вывозимого из вершины , равно количеству «груза», ввозимого в эту вершину;

) количество «груза», вывозимого из источника , должно быть равно количеству груза, ввозимого в сток :

.

Число  называется величиной данного потока или просто потоком между  и .

.1.5 Сетевое планирование

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

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

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

Сетевая модель - это план выполнения некоторого комплекса взаимосвязанных работ, заданного в форме сети, графическое изображение которой называется сетевым графиком.

Главными элементами сетевой модели являются работы и события.

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

Во-вторых, это ожидание - протяжённый во времени процесс, не требующий затрат труда (например, процесс сушки после покраски, старения металла, твердения бетона и т.п.).

В-третьих, это зависимость, или фиктивная работа - логическая связь между двумя или несколькими работами (событиями), не требующими затрат труда, материальных ресурсов или времени. Она указывает, что возможность одной работы непосредственно зависит от результатов другой. Естественно, что продолжительность фиктивной работы принимается равной нулю.

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

Основные элементы сетевой модели

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

¡ - событие,

- работа (процесс),

фиктивная работа - применяется для упрощения сетевых графиков (продолжительность всегда равна 0).

Среди событий сетевой модели выделяют исходное и завершающее события. Исходное событие не имеет предшествующих работ и событий, относящихся к представленному в модели комплексу работ. Завершающее событие не имеет последующих работ и событий.

Существует и иной принцип построения сетей - без событий. В такой сети вершины графа означают определённые работы, а стрелки - зависимости между работами, определяющие порядок их выполнения. Сетевой график «работы-связи» в отличие от графика «события-работы» обладает известными преимуществами: не содержит фиктивных работ, имеет более простую технику построения и перестройки, включает только хорошо знакомое исполнителям понятие работы без менее привычного понятия события.

Вместе с тем сети без событий оказываются значительно более громоздкими, так как событий обычно значительно меньше, чем работ (показатель сложности сети, равный отношению числа работ к числу событий, как правило, существенно больше единицы). Поэтому эти сети менее эффективны с точки зрения управления комплексом. Этим и объясняется тот факт, что в настоящее время наибольшее распространения получили сетевые графики «события-работы».

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

2.1.6 Целочисленное программирование

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

2.2 Математические пакеты Maple и MATLAB

Сколь значителен спектр задач, которые решаются при помощи пакета Maple видно из следующего перечисления:

o   проведение математических исследований, требующих вычислений и аналитических выкладок;

o   разработка и анализ алгоритмов;

o   математическое моделирование, компьютерный эксперимент;

o   анализ и обработка данных;

o   визуализация, научная и инженерная графика,

o   разработка графических и расчетных приложений.

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

Система Maple создавалась как пакет компьютерной алгебры, то есть основным объектом здесь являются формулы и операции с ними. Без дополнительных указании символ, например х, считается фактически математической переменной, как х в формуле Т(х). Такая специфика систем компьютерной алгебры позволяет проводить точные вычисления.

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

Пакет Maple - интерактивная программа, позволяющая проводить анали тические выкладки и вычисления, снабженная средствами двумерной и трехмерной графики, имеющая мощный язык программирования и богатую библиотеку математических формул и сведений. Работа с Maple заключается в том, что пользователь вводит математические выражения и инструкции (команды), а система пытается их выполнить и представить ответ. Получив (или не получив) ответ, пользователь вводит новые инструкции и так далее - взаимодействие с пакетом происходит в диалоговом режиме. Благодаря собственному язык программирования высокого уровня введенные выражения и инструкции, а также результаты выполнения команд - формулы, графики, таблицы и числа - запоминаются в едином документе (worksheet). Это обеспечивает уникальную технологию работы, когда чуть ли не все этапы математического исследования можно отразить в одном документе, и итоговый документ становится (быть может, с минимальными дополнениями) научной статьей, разделом в учебнике, отчетом.

Основы Maple.

В данной главе рассмотрен ряд общих вопросов: интерфейс (системы меню, значков и справки), кратко описана организация документа Maple, изложены общие сведения об основных объектах (переменных, константах, выражениях) и синтаксисе, а также дан обзор базовых типов Maple и основных математических функций.

Работа с Maple и интерфейс

Графический интерфейс Maple аналогичен имеющемуся в системах редактирования и подготовки текста и использует обычные средства работы с файлами и редактирования (мышь и клавиатура). После запуска выполняемого модуля wmapte или xmaple в среде Unix появляется оболочка с новым документом (worksheet). В верхней части окна расположено меню (пункты File, Edit и т. д.), чуть ниже - строка значков Toolbar для ряда часто выполняемых операций, еше ниже - строка значков Context Ваг, организующих представление данных в сеансе. Затем следует одно или несколько окон с документами, в которых размешаются формулы, рисунки, сопровождающий текст и др. В нижней части окна находится полоса Status Une, которая содержит информацию о системе. Работа в Maple проходит в режиме сессии (session) - пользователь вводит команды. математические выражения, процедуры, которые воспринимаются и интерпретируются Maple. Каждая команда должна завершаться точкой с занятой (;) или двоеточием (:). В первом случае в строке под предложением будет выведен результат исполнения команды или сообщение об ошибке, во втором случае результат не выводится. Для отмены всех сделанных назначений и начала нового сеанса без выхода из Maple используется команда restart.