А
Б В
Г Д
Е Ж
З И
К Л
М Н
О П
Р С
Т У
Ф Х
Ц Ч
Ш Э
Ю Я
Реферат: Расчет системы сбора и передачи данных
Расчет системы сбора и передачи данных
Домашнее задание по дисциплине:
Алгоритмические методы исследования операций.
Тема: «Разработка программ для решения задач исследования операций в диалоговом режиме на ПК.»
Вариант №:
«Решение задачи о кратчайшем маршруте методом Форда.»
Руководитель домашнего задания:
Исполнитель:
1998 год.
Содержание:
1 Постановка сетевой транспортной задачи. 3
2 Описание метода и алгоритма решения. 4
Составление исходной таблицы расстояний. 4
Определение (i и (j 4
Определение длинны кратчайших путей. 4
Нахождение кратчайшего пути. 5
3 Описание программы. 7
4 Описание подпрограмм и процедур. 8
Подпрограммы и функции. 8
Таблица идентификаторов. 9
5 Пример решения контрольной задачи. 11
6 Выводы. 12
7 Список литературы. 13
Приложение 1: Инструкция программисту и пользователю (содержимое README.TXT файла).
Приложение 2: Исходный текст программы.
1. Постановка сетевой транспортной задачи.
На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P1,P2,...,Pn, причем некоторые упорядоченные пары (Pi,Pj) пунктов назначения соединены дугами заданной длинны ((Pi,Pj)=lij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.
На рис.1 построена ориентированная транспортная сеть, содержащая шесть пунктов P1,P2,...,P6, которые связаны между собой восьмью транспортными путями.
Необходимо определить кратчайший маршрут из пункта P1 в P6. Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута.
Например маршрут из пункта P1 в пункт P6: P1P2P4P6; L=l12+l24+l46=10.
Постановка задачи приобретает смысл в том случае, если имеется несколько вариантов маршрута из начального пункта в конечный. В этом случае физический смысл функции цели задачи состоит в минимизации общей длинны маршрута, т.е. в определении кратчайшего пути из P1 в Pn.
2. Описание метода и алгоритма решения.
Метод Форда бал разработан специально для решения сетевых транспортных задач и основан, по существу, на принципе оптимальности.
Алгоритм метода Форда содержит четыре этапа (схема 1). На первом этапе производится заполнение исходной таблицы расстояний от любого i-го пункта в любой другой j-й пункт назначения. На втором этапе определяются для каждого пункта некоторые параметры (i и (j по соответствующим формулам. Далее на третьем этапе определяются кратчайшие расстояния. Наконец, на четвертом этапе определяются кратчайшие маршруты из пункта отправления Р1 в любой другой пункт назначения Рj, j=1,2,...,n.
Рассмотрим подробнее каждый из этих четырех этапов.
2.1 Первый этап: Составление исходной таблицы расстояний.
Данная таблица содержит n+1 строк и такое же количество столбцов; Pi - пункты отправления; Pj - пункты назначения. Во второй строке и втором столбце проставляется значения параметров (i и(j, определение значений которых производятся на втором этапе решения задачи. В остальных клетках таблицы проставляются значения расстояний lij из i-го пункта в j-й пункт. Причем заполняем клетки таблицы, лежащие выше главной диагонали. Если пункт Pi не соединен отрезком пути с пунктом Pj, то соответствующая клетка таблицы не заполняется.
2.2 Второй этап: Определение (i и (j.
Определяется значение параметров в соответствии с формулой:
(j=min((i+lij); i=1,2,...,n; j=1,2,...,n, (1)
где (1=0.
Эти значения заполняются во второй строке и во втором столбце.
2.3 Третий этап: Определение длинны кратчайших путей.
Возможны два случая определения длинны кратчайших путей из пунктов Pi в пункты Pj, i=1,2,...,n; j=1,2,...,n.
В первом случае, если выполняются неравенство:
(j - (i ( lij; lij(0; j=1,2,...,n; j=1,2,...,n, (2)
то значения параметров (1,...,(n удовлетворяют условиям оптимальности. Каждое значение (j есть не что иное, как кратчайшее расстояние от пункта Pi до пункта Pj, j=2,3,...,n.
Во втором случае, если для некоторых клеток (i,j) таблицы имеет место неравенство:
(j - (i > lij; i=1,...,n; j=1,...,n, (3)
то значения (j и (i могут быть уменьшены.
Если справедливо (3), тогда исправим значение (j0, пересчитав его по формуле:
((j0=(i0+li0j0. (4)
2.4 Четвертый этап: Нахождение кратчайшего пути.
Определения последовательности пунктов кратчайшего маршрута. С этой целью для каждого столбца определяют величину:
lr1,j = (j - (r1, (5)
где lr1,j берется из таблицы, причем (r1 выбирается так, чтобы выполнилось равенство (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. Описание подпрограмм и процедур.
Подпрограммы и функции.
ТИП
НАЗВАНИЕ
НАЗНАЧЕНИЕ
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. Выводы.
Анализ алгоритма операций, необходимых при решении сетевой транспортной задачи методом Форда в заданной постановке подтверждает:
Достижение конечного результата производится в четыре этапа.
Каждый этап описывается простыми математическими операциями и может быть записан на одном из языков программирования.
Составлена программа на алгоритмическом языке высокого уровня «Pascal», позволяющая решать задачу в диалоговом режиме, удобном для пользователя не программиста.
Алгоритм решения транспортной задачи методом Форда является универсальным, что позволяет производить расчёты как с ранжированными, так и с не ранжированными графами (примеры решения задачи приведены на странице 11).
Возможность реализаций для удобства работы пользователя в программе сервисной части.
Возможность неоднократного решения задачи методом Форда при различных исходных данных.
7. Литература.
1. ВЕНТЦЕЛЬ Е.С. «Исследование операций» М.: Сов.Радио 1972 г.
2. ЗАХАРОВ В.Н. «Алгоритмические методы решения задач оптимального планирования и управления» ВАД. 1986 г.
ЗУБОВ В.С. «Программирование на языке Turbo Pascal» М.: Филин 1997 г.
|