Решение задач на тему: Математическое обеспечение. Постановка задачи о кратчайшем пути сети

Введение

Исследование операций - применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Исследование операций начинается тогда, когда для обоснования решений применяется тот или другой математический аппарат. Операция - всякое мероприятие (система действий), объединённое единым замыслом и направленное к достижению какой-то цели (напр., мероприятия задач 1-8, указанных ниже, будут операциями). Операция всегда является управляемым мероприятием, то есть зависит от человека, каким способом выбрать параметры, характеризующие её организацию (в широком смысле, включая набор технических средств, применяемых в операции). Решение (удачное, неудачное, разумное, неразумное) - всякий определённый набор зависящих от человека параметров. Оптимальное - решение, которое по тем или другим признакам предпочтительнее других.

Цель исследования операций - предварительное количественное обоснование оптимальных решений. Само принятие решения выходит за рамки исследования операций и относится к компетенции ответственного лица (лиц). Элементы решения - параметры, совокупность которых образует решение: числа, векторы, функции, физические признаки и т. д. Если элементами решения можно распоряжаться в определённых пределах, то заданные ("дисциплинирующие") условия (ограничения) фиксированы сразу и нарушены быть не могут (грузоподъёмность, размеры, вес). К таким условиям относятся средства (материальные, технические, людские), которыми человек вправе распоряжаться, и иные ограничения, налагаемые на решение. Их совокупность формирует множество возможных решений.

Характерная особенность исследования операций - системный подход <http://ru.wikipedia.org/wiki/%D0%А1%D0%В8%D1%81%D1%82%D0%В5%D0%ВС%D0%ВD%D1%8В%D0%B9_%D0%ВF%D0%ВЕ%D0%В4%D1%85%D0%ВЕ%D0%В4> к поставленной проблеме и анализ. Системный подход является главным методологическим принципом исследования операций. Он заключается в следующем. Любая задача, которая решается, должна рассматриваться с точки зрения влияния на критерии функционирования системы в целом. Для исследования операций характерно то, что при решении каждой проблемы могут возникать новые задачи.

Объект исследования: исследование операций в экономике.

Предмет исследования: метод Минти для нахождения кратчайшего пути.

Цели исследования: изучить метод нахождения кратчайшего пути (метод Минти).

Для достижения поставленной цели необходимо выполнить следующие задачи:

1 Изучить математическое описание данного метода оптимизации;

2 Сформулировать алгоритм реализации данного метода;

Разработать пользовательский интерфейс программного продукта, реализующего метод Минти;

Разработать рабочую версию программы для реализации метода Минти;

Разработать демонстрационные примеры для тестирования программы.

Оглавление

- Введение

- Математическое обеспечение

- Постановка задачи о кратчайшем пути на сети

- Описание метода Минти

- Алгоритмическое обеспечение

- Программное обеспечение

- Обоснование выбора среды разработки

- Описание интерфейса и параметров программного продукта

- Тестирование программного продукта

- Тестовая задача

- Тестовая задача

- Тестовая задача

- Заключение

- Список использованных источников

- ПРИЛОЖЕНИЕ А Листинг основного модуля программы

Заключение

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

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

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

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

. Конюховский П.В. Математические методы исследования операций в экономике. - СПб: Питер, 2000. - 208с.

2. <http://ru.wikipedia.org/wiki/%D0%90%D0%ВВ%D0%В3%D0%ВЕ%D1%80%D0%В8%D1%82%D0%BC_%D0%94%D0%В5%D0%В9%D0%ВА%D1%81%D1%82%D1%80%D1%8В>

. <http://coolreferat.com/%D0%9С%D0%В0%D1%82%D0%В5%D0%ВС%D0%В0%D1%82%D0%В8%D1%87%D0%В5%D1%81%D0%ВА%D0%В8%D0%B5_%D0%ВС%D0%В5%D1%82%D0%ВЕ%D0%В4%D1%8B_%D0%В8%D1%81%D1%81%D0%ВВ%D0%В5%D0%В4%D0%ВЕ%D0%В2%D0%В0%D0%ВD%D0%В8%D1%8F_%D0%ВЕ%D0%ВF%D0%В5%D1%80%D0%В0%D1%86%D0%В8%D0%B9_%D0%B2_%D1%8D%D0%ВА%D0%ВЕ%D0%ВD%D0%ВЕ%D0%ВС%D0%В8%D0%ВА%D0%B5_%D1%87%D0%В0%D1%81%D1%82%D1%8С=17>

Приложение А

Листинг основного модуля программы

(5, 6, 2));InArr(const Arr:TVertexArray; const Num:Integer):Boolean;I:Integer;:=False;I:=0 tо High(Arr) doArr[I]._vertex = Num then:=True;;;;TForm1.Button1Click(Sender: TObject);.Clear;.Clear;.Clear;.Clear;;TForm1.cmdAddClick(Sender: TObject);I:Integer;.RowCount:=Grid.RowCount + 1;I:=0 tо 2 dо Grid.Cells[I, Grid.RowCount - 1]:='0';;TForm1.FormCreate(Sender: TObject);I, J:Integer;.OnKeyPress:=txtHandlerKeyPress;.OnKeyPress:=txtHandlerKeyPress;.OnKeyPress:=txtHandlerKeyPress;.RowCount:=EdgesCount + 1;.Text:=IntToStr(VertexCount);.Text:=IntToStr(VertexSrc);.Text:=IntToStr(VertexDest);.Cells[0, 0]:='Начало';.Cells[1, 0]:='Конец';.Cells[2, 0]:='Вес';I:=1 tо EdgesCount doJ:=1 tо 3 dо Grid.Cells[J-1, I]:=IntToStr(Edges[I, J]);;TForm1.cmdCompClick(Sender: TObject);I, _from, _to:Integer;, VertArr:TVertexArray;:Boolean;:array оf TElement;Process;I, Min, MinPos:Integer;InArr(VertArr, VertexDest) then Exit;

// ищем ребро с минимальным весом в оба направления

_from:=Massiv[MinPos]._end;;.Lines.Add('Нашли минимальный вес ребра - ' + IntToStr(Min) + ' из ' + IntToStr(_from) + ' в ' + IntToStr(_to));

// вычитаем из стоимости всех проверенных ребер стоимость наименьшего

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

// и отмечаем ребро с мин. стоимостью

// звем рекурсию для добавленной в список вершины

Process;;Res:string;:Integer;VertexSrc = VertexDest then(Handle, 'Исходный и конечный пункты совпадают', '', MB_ICONEXCLAMATION);;;(VertexCount < VertexSrc) оr (VertexCount < VertexDest) then

begin(Handle, 'Неверное значение источника или назначения', '', MB_ICONEXCLAMATION);

Exit;;.Clear;(Massiv, Grid.RowCount - 1);I:=0 tо High(Massiv) dо[I]._start:=StrToInt(Grid.Cells[0, I+1]);[I]._end:=StrToInt(Grid.Cells[1, I+1]);[I]._weight:=StrToInt(Grid.Cells[2, I+1]);[I]._initial:=Massiv[I]._weight;[I]._checked:=False;;(Vertex, VertexCount);I:=0 tо High(Vertex) dо Vertex[I]._vertex:=-1;[VertexSrc-1]._vertex:=0;(VertArr, 1);[0]._vertex:=VertexSrc; // задаем начальный узел

Memo1.Lines.Add('Процесс рекурсии:');;:=VertexDest - 1; // считаем стоимость маршрута

Res:=IntToStr(VertexDest);:=0;Vertex[I]._vertex > 0 dо:=IntToStr(Vertex[I]._vertex) + ' - ' + Res;:=Sum + Vertex[I]._data;:=Vertex[I]._vertex - 1;; // ---------------.Lines.Add(#13#10 + 'Решение:' +

#13#10 + 'Маршрут с минимальной стоимостью ребер: ' + Res +

#13#10 + 'Полная стоимость маршрута: ' + IntToStr(Sum));