Метод Минти нахождения кратчайшего пути
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
СОДЕРЖАНИЕ
Введение
. Математическое обеспечение
.1 Постановка задачи о кратчайшем пути на сети
.2 Описание метода Минти
. Алгоритмическое обеспечение
. Программное обеспечение
.1 Обоснование выбора среды разработки
.2 Описание интерфейса и параметров программного продукта
. Тестирование программного продукта
.1 Тестовая задача 1
.2 Тестовая задача 2
.3 Тестовая задача 3
Заключение
Список использованных источников
ПРИЛОЖЕНИЕ А Листинг основного модуля программы
Введение
Исследование операций - применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Исследование операций начинается тогда, когда для обоснования решений применяется тот или другой математический аппарат. Операция - всякое мероприятие (система действий), объединённое единым замыслом и направленное к достижению какой-то цели (напр., мероприятия задач 1-8, указанных ниже, будут операциями). Операция всегда является управляемым мероприятием, то есть зависит от человека, каким способом выбрать параметры, характеризующие её организацию (в широком смысле, включая набор технических средств, применяемых в операции). Решение (удачное, неудачное, разумное, неразумное) - всякий определённый набор зависящих от человека параметров. Оптимальное - решение, которое по тем или другим признакам предпочтительнее других.
Цель исследования операций - предварительное количественное обоснование оптимальных решений. Само принятие решения выходит за рамки исследования операций и относится к компетенции ответственного лица (лиц). Элементы решения - параметры, совокупность которых образует решение: числа, векторы, функции, физические признаки и т. д. Если элементами решения можно распоряжаться в определённых пределах, то заданные (дисциплинирующие) условия (ограничения) фиксированы сразу и нарушены быть не могут (грузоподъёмность, размеры, вес). К таким условиям относятся средства (материальные, технические, людские), которыми человек вправе распоряжаться, и иные ограничения, налагаемые на решение. Их совокупность формирует множество возможных решений.
...,,.,.">Характерная особенность исследования операций - системный подход к поставленной проблеме и анализ. Системный подход является главным методологическим принципом исследования операций. Он заключается в следующем. Любая задача, которая решается, должна рассматриваться с точки зрения влияния на критерии функционирования системы в целом. Для исследования операций характерно то, что при решении каждой проблемы могут возникать новые задачи.
Объект исследования: исследование операций в экономике.
Предмет исследования: метод Минти для нахождения кратчайшего пути.
Цели исследования: изучить метод нахождения кратчайшего пути (метод Минти).
Для достижения поставленной цели необходимо выполнить следующие задачи:
1Изучить математическое описание данного метода оптимизации;
2Сформулировать алгоритм реализации данного метода;
Разработать пользовательский интерфейс программного продукта, реализующего метод Минти;
Разработать рабочую версию программы для реализации метода Минти;
Разработать демонстрационные примеры для тестирования программы.
1. Математическое обеспечение
.1 Постановка задачи о кратчайшем пути на сети
На сети, что задается графом (I,U), где I множество вершин, U множество дуг, с определенной на ней функцией стоимости сіj ((і,j) дуга с U), для фиксированных i1 и is найти путь
= ((i1,i2),(i2,i3)...,(is-1,is))
из вершины i1 в вершину is, длина которого
наименьшая.
1.2 Описание метода Минти
Метод Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в ходе которого строится путь L=(s=i0, i1, ..., ip-1, ip=t).
На предварительном (нулевом) этапе алгоритма:
формируется массив значений так называемых модифицированных длин i,j, которые перед началом первой итерации полагаются равными сi,j ?0;
осуществляется отметка вершины i0 = s числом mi0 = 0.
Стандартная итерация включает этапы:
. Отметка вершин сети. Обозначим множество вершин cети, отмеченных на пред?/p>