Решение задачи на определение кратчайшего пути

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«БРАТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ФАКУЛЬТЕТ ЭКОНОМИКИ И УПРАВЛЕНИЯ

Кафедра «Государственное и муниципальное управление»

Профиль «Государственное и муниципальное управление»

Отчет по лабораторной работе №4

по дисциплине

«Экономико-математические методы»

Решение задачи на определение кратчайшего пути

Работу выполнил

студент гр. ГМУ-14 _______________ А.В. Шестаков

(подпись)

Поверил

доцент кафедры ГиМУ, к.э.н. _______________ С.В. Либеровская

(подпись)

Братск 2016

Содержание

1. Теоретические аспекты сетевой оптимизации 4

2. Решение задачи на определение кратчайшего пути 5

Введение

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

Система СПУ позволяет устанавливать взаимосвязь планируемых работ и получаемых результатов, более точно рассчитывать план, а также своевременно осуществлять его корректировку.

Основная цель сетевого планирования - сокращение до минимума продолжительности проекта.

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

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

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

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

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

1) граф – фигура (состоит из вершин и соединяющих их линий/ребер);

2) маршрут/путь (соединяет вершины графов, в которых каждые 2 ребра имеют общую кольцевую точку);

3) цепь – граф, каждое ребро которого встречается не более одного раза;

4) цикл – цепь, у которой начальная и конечная точки совпадают;

5) дерево – граф, который не имеет циклов, при этом число его вершин равно В, а число его ребер D, и они связаны как D=В-1.

Граф может быть связанный, если любая пра его вершин связана, и может быть несвязанный.

Вершины могут быть четные, если в этой вершине сходится четное количество ребер, и может быть нечетным.

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

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

В графике есть 2 элемента:

Данная задача решается как транспортная с промежуточными пунктами.

При этом транспортные расходы при перевозке будут равны расстояниям между вершинами.

1 единица груза определяется из вершины 1 (исходный пункт) в вершину 8 (пункт назначения). При этом вершины 2-7 являются промежуточными.

Решение:

1.Строим матрицу и вводим основные и дополнительные данные:

100 обозначим случаи, когда между вершинами нет пути, а для решения берем численную длину значительно больше самого данного (Рисунок 1).

Рисунок 1. Данные задачи

2.Вводим формулы:

3.Вводим параметры поиска решений (Рисунок 2).

Рисунок 2. Окно «Параметры поиска решений»

4. Поиск решения (Рисунок 3).

Рисунок 3. Решение задачи

Вывод: маршрут - 1248; транспортные расходы 5.