Примеры решения открытой модели транспортной задачи

Математические модели и методы их расчета

Мацнев А.П.

1. Понятие операционного исследования

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

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

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

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

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

Чтобы человеку принять решение без ЭВМ, зачастую ничего не надо, кроме опыта и интуиции. Правда, никакой гарантии правильности, а тем более оптимальности при этом нет. Подчеркнем, что ЭВМ никаких решений не принимает. Решение принимает человек (ЛПР). А ЭВМ только помогает найти варианты решений. Непременное присутствие человека (как окончательный инстанции принятия решений) не отменяется даже при наличии полностью автоматизированной системы управления. Нельзя забывать о том, что само создание управляющего алгоритма, выбор одного из возможных его вариантов, есть тоже решение. По мере автоматизации управления функции человека перемещаются с одного уровня управления на другой - высший. Основные этапы решения задачи принятия оптимальных решений с помощью ЭВМ показаны на Рис. 1.

Исходные

данные

Объект

Задача

Модель

Алгоритм

Программа

ЭВМ

Пакет прикладных программ (ППП)

Решение

Рис. 1. Основные этапы решения задачи принятия решения с помощью ЭВМ.

Выбор задачи - важнейший вопрос. Какие основные требования должна удовлетворять задача? Таких требований два:

должно существовать, как минимум, два варианта ее решения (ведь если вариант один, значит и выбирать не из чего);

надо четко знать в каком смысле искомое решение должно быть наилучшим (кто не знает, куда ему плыть - тому нет и попутного ветра).

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

Хорошую модель составить не просто. Известный математик Р.Беллман сказал так: «Если мы попытаемся включить в нашу модель слишком много черт действительности, то захлебнемся в сложных уравнениях; если слишком упростим ее, то она перестанет удовлетворять нашим требованиям». Таким образом, исследователь должен пройти между западнями Переупрощения и болотом Переусложнения. Для выполнения успеха моделирования надо выполнить три правила, которые, по мнению древних, являются признаками мудрости. Эти правила применительно к задачам математического моделирования и формулируются так: учесть главные свойства моделируемого объекта; пренебрегать его второстепенными свойствами; уметь отделить главные свойства от второстепенных.

Составление модели - это искусство, творчество. Древние говорили: «Если двое смотрят на одно и то же, это не означает, что оба видят одно и то же». И слова древних греков: «Если двое делают одно и то же, это не значит, что получится одно и то же». Эти слова в полной мере относятся к составлению математических моделей. Если математическая модель - это диагноз заболевания, то алгоритм - это метод лечения.

Можно выделить следующие основные этапы операционного исследования:

наблюдение явления и сбор исходных данных;

постановка задачи;

построение математической модели;

расчет модели;

тестирование модели и анализ выходных данных. Если полученные результаты не удовлетворяют исследователя, то следует либо вернуться на этап 3, т.e. предложить для решения задачи другую математическую модель; либо вернуться на этап 2, т.e. поставить задачу более корректно;

применение результатов исследований.

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

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

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

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

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

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

2. Классификация и принципы построения математических моделей

Можно выделить следующие основные этапы построения математической модели:

Определение цели, т.e. чего хотят добиться, решая поставленную задачу.

Определение пapaметров модели, т.е. заранее известных фиксированных факторов, на значения которых исследователь не влияет.

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

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

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

Выражение цели через управляющие переменные, параметры и неизвестные факторы, т.e. формирование целевой функции, называемой также критерием эффективности или критерием оптимальности задачи.

Введем следующие условные обозначения:

- параметры модели;

x - управляющие переменные или решения;

X - область допустимых решений;

- случайные или неопределенные факторы;

W - целевая функция или критерий эффективности (критерий оптимальности).

W=W (x, a, x)

В соответствии с введенными терминами, математическая модель задачи имеет следующий вид:

W=W (x, a, x) ® max (min) (2.1)

x I X

? Решить задачу - это значит найти такое оптимальное решение x*IX, чтобы при данных фиксированных параметрах a и с учетом неизвестных x факторов значения критерия эффективности W было по возможности максимальным (минимальным).

W*=W (x*, a, x) = max (min) W (x, a, x)

x I X

Таким образом, оптимальное решение - это решение, предпочтительное перед другими по определенному критерию эффективности (одному или нескольким).

Перечислим некоторые основные принципы построения математической модели:

Необходимо соизмерять точность и подробность модели, во-первых, с точностью тex исходных данных, которыми располагает исследователь, и, во-вторых, с теми результатами, которые требуется получить.

Математическая модель должна отражать существенные черты исследуемого явления и при этом не должна его сильно упрощать.

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

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

По числу критериев эффективности математические модели делятся на однокритериальные и многокритериальные. Многокритериальные математические модели содержат два и более критерия.

По учету неизвестных факторов математические модели делятся на детерминированные, стохастические и модели с элементами неопределенности.

В стохастических моделях неизвестные факторы - это случайные величины, для которых известны функции распределения и различные статистические характеристики (математическое ожидание, дисперсия, среднеквадратическое отклонение и т.п.). Среди стохастических характеристик можно выделить:

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

- модели теории случайных процессов, предназначенные для изучения процессов, состояние которых в каждый момент времени является случайной величиной;

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

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

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

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

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

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

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

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

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

Список литературы

Примеры решения открытой модели транспортной задачи

Похожие курсовые работы