Системный анализ пиццерии

Для конечного неориентированного графа можно определить его диаметр, как максимальное расстояние между  двумя его вершинами:

Соответствующие кратчайшие простые цепи, связывающие  две вершины с максимальным расстоянием, можно называть диаметральными простыми цепями [6].

Выберем некоторую фиксированную  вершину с и обозначим через

максимальное значение от с до G назовем с₀ центром графа G, если величена r(c) принимает для этой вершины минимальное значение

Значение r₀ назовем кратчайшей простой цепью от с₀ до какой-нибудь вершины. Это и будет кратчайший маршрут, который мы искали.

Теперь рассмотрим возможный  алгоритм нахождения кратчайшего пути в графе. Будем рассматривать  графы вида , дугам которых приписаны веса [4]. Это означает, что каждой дуге поставлено в соответствие некоторое вещественное число , называемое весом данной дуги. Полагаем, что , если не существует дуга . Если последовательность вершин определяет путь в графе G, то его длинна определяется как сумма . Нас будет интересовать нахождение кратчайшего пути между двумя фиксированными вершинами . Длину такого пути обозначим и назовем расстояние от s до t (расстояние, определенное таким образом, может быть и отрицательным). Если не существует ни одного пути из s в t, то полагаем , но у нас такого быть не может из условий поставленной перед нами задачи. Отметим, что если контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем [5].

Практическая интерпретация:

1. вершины – магазины, дуги – пути между городами, длины которых представлены весами. Ищем кратчайшие пути между магазинами;
2. вес дуги – время движения между вершинами. Тогда ищем самый скорый путь движения.

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

Далее рассмотрим нашу задачу на примере  “алгоритма равных цен”. Суть алгоритма  заключается в следующем, есть точка  отправления (вершина А), есть конечная точка прибытия (Вершина Цель), нам  необходимо найти кратчайший путь из А в Цель. Из всех дуг выходящих с вершины A выбираем дугу с наименьшим весом, (в данном случае AB). С вершины B выходит ещё две дуги BF и BE. Теперь у нас есть 4 варианта выбора пути: ABE, ABF, AC и AD. Также выбираем путь с наименьшим весом дуг (ABE - 3) и проверяем, достигли мы вершины или нет. Если достигли, то соответственно кратчайший путь найден, иначе продолжаем тем же способом проверять оставшиеся вершины. В нашем случае дальнейшие действия будут выглядеть следующем образом. ABF – 6, AC – 7, ACG – 12, A-C-G-Цель – 14. Наименьшим путем в данном графе является путь с вершинами A-C-G-Цель.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пример реализации «алгоритма равных цен»

 

 

 

Заключение

 

 

При выполнении курсового проекта  по дисциплине «Теория систем и системный  анализ» была подвергнута анализу  организация, которая занимается производством и реализацией пиццы.

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

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

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

 

 

 

 

 

Литература

 

 

1. Павлов С.Н. Теория систем и системный анализ: Учебное пособие. – Томск: изд-во ТУСУР, 2003. – 134 с
2. Силич М.П. Реинжиниринг бизнес-процессов: Учебное пособие. – Томск: ТМЦДО 2000. – 108с.
3. Тимаков С.О. Теория систем и системный анализ: Учебное методическое пособие. – Томск: ТМЦДО, 2003. – 34с.
4. Горитов А.Н. Структуры и алгоритмы обработки данных в ЭВМ: Учебное пособие. – Томск: ТМЦДО, 2000. – 122с.
5. Оре О. Теория графов. – 2-е изд. – М.: Наука, 1980, 336с.
6. Татт У. Теория графов: Пер. с англ. – М.: Мир, 1988. – 424с., ил.