Реферат Расчет сетевой модели методом Форда с программой
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Домашнее задание по дисциплине:
Алгоритмические методы исследования операций.
Тема: «Разработка программ для решения задач исследования операций в диалоговом режиме на ПК.»
Вариант №:
«Решение задачи о кратчайшем маршруте методом Форда.»
Руководитель домашнего задания:
Исполнитель:
1998 год.
Содержание:
1 Постановка сетевой транспортной задачи. 3
2 Описание метода и алгоритма решения. 4
2.1 Составление исходной таблицы расстояний. 4
2.2 Определение li и lj 4
2.3 Определение длинны кратчайших путей. 4
2.4 Нахождение кратчайшего пути. 5
3 Описание программы. 7
4 Описание подпрограмм и процедур. 8
4.1 Подпрограммы и функции. 8
4.2 Таблица идентификаторов. 9
5 Пример решения контрольной задачи. 11
6 Выводы. 12
7 Список литературы. 13
Приложение 1: Инструкция программисту и пользователю (содержимое README.TXT файла).
Приложение 2: Исходный текст программы.
1. Постановка сетевой транспортной задачи.
| |
На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P1,P2,...,Pn, причем некоторые упорядоченные пары (Pi,Pj) пунктов назначения соединены дугами заданной длинны r(Pi,Pj)=lij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.
На рис.1 построена ориентированная транспортная сеть, содержащая шесть пунктов P1,P2,...,P6, которые связаны между собой восьмью транспортными путями.
Необходимо определить кратчайший маршрут из пункта P1 в P6. Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута.
Например маршрут из пункта P1 в пункт P6: P1P2P4P6; L=l12+l24+l46=10.
Постановка задачи приобретает смысл в том случае, если имеется несколько вариантов маршрута из начального пункта в конечный. В этом случае физический смысл функции цели задачи состоит в минимизации общей длинны маршрута, т.е. в определении кратчайшего пути из P1 в Pn.
2
. Описание метода и алгоритма решения.
Метод Форда бал разработан специально для решения сетевых транспортных задач и основан, по существу, на принципе оптимальности.
Алгоритм метода Форда содержит четыре этапа (схема 1). На первом этапе производится заполнение исходной таблицы расстояний от любого i-го пункта в любой другой j-й пункт назначения. На втором этапе определяются для каждого пункта некоторые параметры li и lj по соответствующим формулам. Далее на третьем этапе определяются кратчайшие расстояния. Наконец, на четвертом этапе определяются кратчайшие маршруты из пункта отправления Р1 в любой другой пункт назначения Рj, j=1,2,...,n.
Рассмотрим подробнее каждый из этих четырех этапов.
2.1
Первый этап: Составление исходной таблицы расстояний.
Данная таблица содержит n+1 строк и такое же количество столбцов; Pi - пункты отправления; Pj - пункты назначения. Во второй строке и втором столбце проставляется значения параметров li иlj, определение значений которых производятся на втором этапе решения задачи. В остальных клетках таблицы проставляются значения расстояний lij из i-го пункта в j-й пункт. Причем заполняем клетки таблицы, лежащие выше главной диагонали. Если пункт Pi не соединен отрезком пути с пунктом Pj, то соответствующая клетка таблицы не заполняется.
2.2
Второй этап: Определение
l
i
и
l
j
.
Определяется значение параметров в соответствии с формулой:
l
j
=min(
l
i
+lij); i=1,2,...,n; j=1,2,...,n, (1)
где l1=0.
Эти значения заполняются во второй строке и во втором столбце.
2.3 Третий этап: Определение длинны кратчайших путей.
Возможны два случая определения длинны кратчайших путей из пунктов Pi в пункты Pj, i=1,2,...,n; j=1,2,...,n.
В первом случае, если выполняются неравенство:
l
j
-
l
i
£
lij; lij
¹
0; j=1,2,...,n; j=1,2,...,n, (2)
то значения параметров [IE1] l1,...,ln удовлетворяют условиям оптимальности. Каждое значение lj есть не что иное, как кратчайшее расстояние от пункта Pi до пункта Pj, j=2,3,...,n.
Во втором случае, если для некоторых клеток (i,j) таблицы имеет место неравенство:
l
j
-
l
i
> lij; i=1,...,n; j=1,...,n, (3)
то значения lj и li могут быть уменьшены.
Если справедливо (3), тогда исправим значение lj0, пересчитав его по формуле:
l
¢
j0
=
l
i0
+li0j0. (4)
2.4 Четвертый этап: Нахождение кратчайшего пути.
Определения последовательности пунктов кратчайшего маршрута. С этой целью для каждого столбца определяют величину:
lr1,j =
l
j
-
l
r1
,
(5)
где lr1,j берется из таблицы, причем lr1 выбирается так, чтобы выполнилось равенство (5). Таким образом определим r1. Далее продолжим ту же операцию, но будем считать, последней не Pn, а Pr1. Будем продолжать до тех пор, пока rn=1.
Таким образом кратчайший маршрут проходит через Pr1,Pr2,...,Prn, а длинна маршрута Lmin=lr2,r1+lr3,r2+...+lrn-1,rn.
3. Описание программы.
Программа «FORD» написана на языке высокого уровня - Pascal, в интегрированной среде разработки «Turbo Pascal 7.0» фирмы Borland Inc.
Программа предназначена для нахождения кратчайшего пути в сетевом графе по методу Форда. Программа легка в использовании, что достигается за счет использования дружественного интерфейса и иерархического меню. Вначале программы производится ввод данных, затем нахождение кратчайшего маршрута и вычисление его длинны, далее выводится результат. Вывод результатов возможен как в файл, так и на экран.
В программе предусмотрена возможность повторного решения задачи с другими исходными данными.
4. Описание подпрограмм и процедур.
4.1
Подпрограммы и функции.
| ТИП | НАЗВАНИЕ | НАЗНАЧЕНИЕ |
| Function type : real | min; | Вычисляет минимальное значение вектора k[i]; |
| Procedure | set_graph_mode; | Устанавливает графический режим; |
| Procedure | install_firewall; | Инициализирует огонь; |
| Procedure | fire; | Процедура рисования огня; |
| Procedure | ok; | Выводит сообщение о корректности операции; |
| Procedure | notok; | Выводит сообщение о некорректности операции; |
| Procedure | check_input_data; | Проверяет корректность ввода данных; |
| Procedure | keybord_input; | Ввод исходных данных с клавиатуры; |
| Procedure | ramka; | Выводит рамку по краям экрана; |
| Procedure | save; | Сохранение результатов в файл; |
| Procedure | about_program; | Выводит информацию о программе; |
| Procedure | about_method; | Выводит информацию о методе Форда; |
| Procedure | output_graph; | Рисует вершины графа; |
| Procedure | draw_ways; | Рисует дуги графа; |
| Procedure | draw_short_way; | Рисует кратчайший маршрут; |
| Procedure | count_point_coord; | Вычисляет экранные координаты вершин графа; |
| Procedure | set_font; | Инициализирует шрифт пользователя; |
| Procedure | calculate; | Основное математическое ядро программы; |
| Procedure | draw_menu; | Открытие меню; |
| Procedure | redraw_menu; | Закрытие меню; |
| Procedure | main_menu; | Основной механизм меню; |
| Procedure | pixel; | Ставит точку; |
| Procedure | stars; | Инициализирует массив со звездами; |
| Procedure | welcomescreen; | Заставка; |
4.2 Таблица идентификаторов.
| ИМЯ | тИП | НАЗНАЧЕНИЕ |
| Константы | ||
| menu | array of string | Описывает меню программы |
| menuof | array of byte | Описывает меню программы |
| menugo | array of byte | Описывает меню программы |
| name1 | string | Имя файла входных данных |
| name2 | string | Имя файла выходных данных |
| xxx | word | Размер огня по х |
| yyy | word | Размер огня по у |
| xx1 | word | Координата х огня |
| yy1 | word | Координата у огня |
| messize | byte | Размер заглавия |
| title | array of string | Заглавие |
| Переменные | ||
| mas | array of real | Основная матрица вычислений |
| coord_point | array of real | Координаты вершин графа |
| i | integer | Переменная для организации цикла |
| j | integer | Переменная для организации цикла |
| t | integer | Используется при расчете пути |
| m | integer | Счетчик кол-ва вершин в крат. Пути |
| n | integer | Кол-во вершин в графе |
| z | integer | Код ошибки |
| x1 | integer | Исп. в процедуре вывода на экран |
| y1 | integer | Исп. в процедуре вывода на экран |
| x2 | integer | Исп. в процедуре вывода на экран |
| y2 | integer | Исп. в процедуре вывода на экран |
| kk | integer | Промежуточное значение |
| iii | integer | Промежуточное значение |
| x | integer | Координата х конца отрезка |
| y | integer | Координата у конца отрезка |
| lenth | integer | Кол-во вершин в кратчайшем маршруте |
| chrus | integer | Номер шрифта пользователя |
| z1 | integer | Номер графического драйверв |
| z2 | integer | Номер графического режима |
| k | array of real | Используется для нахождения минимума |
| result | array of integer | Номера вершин, которые входят в кратчайший маршрут |
| error_code | array of byte | Коды ошибок при вводе данных |
| fire1 | array of byte | Хранит цвета огня |
| fire2 | array of byte | Матрица промежуточных данных |
| aa | real | Используется при вычислении координат вершин графа |
| pi1 | real | Используется при вычислении координат вершин графа |
| s | real | Хранит промежуточное значение |
| l | boolean | Исп. при определении кратчайшего маршрута |
| inputdata | boolean | TRUE, если данные вводились |
| calculatedata | boolean | TRUE, если данные били обработаны |
| mov | boolean | Используется в процедуре меню |
| o | string | Используется при вводе с клавиатуры |
| temp | byte | Хранит временное значение |
| cursor | byte | Координаты курсора меню |
| lastcursor | byte | Последние координаты курсора меню |
| menulevel | byte | Уровень меню |
| nline | byte | Кол-во строк в текушем уровне меню |
| pressed | char | Используется при вводе с клавиатуры |
| f1 | text | Файловая переменная |
| f2 | text | Файловая переменная |
5. Примеры решения контрольных задач.
Исходная таблица расстояний для одного из вариантов ранжированного графа:
| Pi/Pj | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | X | 5 | 3 | | | |
| 2 | | X | | 2 | 5 | |
| 3 | | | X | 7 | 7 | |
| 4 | | | | X | | 3 |
| 5 | | | | | X | 2 |
| 6 | | | | | | X |
После обработки таблицы с заданными исходными данными, программа выдает следующие результаты:
- кратчайший маршрут: 1-2-4-6
- длинна кратчайшего маршрута: 10
Исходная таблица расстояний для одного из вариантов не ранжированного графа:
| Pi/Pj | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | X | | 1 | 6 | 2 | |
| 2 | | X | | | | 1 |
| 3 | | 8 | X | | | |
| 4 | | 2 | | X | | 5 |
| 5 | | | 1 | 3 | X | 9 |
| 6 | | | | | | X |
После обработки таблицы с заданными исходными данными, программа выдает следующие результаты:
- кратчайший маршрут: 1-5-4-2-6
- длинна кратчайшего маршрута: 8
Программа работоспособна при любых других вариантах исходных данных.
6. Выводы.
Анализ алгоритма операций, необходимых при решении сетевой транспортной задачи методом Форда в заданной постановке подтверждает:
1. Достижение конечного результата производится в четыре этапа.
2. Каждый этап описывается простыми математическими операциями и может быть записан на одном из языков программирования.
3. Составлена программа на алгоритмическом языке высокого уровня «Pascal», позволяющая решать задачу в диалоговом режиме, удобном для пользователя не программиста.
4. Алгоритм решения транспортной задачи методом Форда является универсальным, что позволяет производить расчёты как с ранжированными, так и с не ранжированными графами (примеры решения задачи приведены на странице 11).
5. Возможность реализаций для удобства работы пользователя в программе сервисной части.
6. Возможность неоднократного решения задачи методом Форда при различных исходных данных.
7. Литература.
1. ВЕНТЦЕЛЬ Е.С. «Исследование операций» М.: Сов.Радио 1972 г.
2. ЗАХАРОВ В.Н. «Алгоритмические методы решения задач оптимального планирования и управления» ВАД. 1986 г.
3. ЗУБОВ В.С. «Программирование на языке Turbo Pascal» М.: Филин 1997 г.
[IE1]
