Материалы сайта
Это интересно
Расчет сетевой модели методом Форда (с программой)
[pic] Домашнее задание по дисциплине: Алгоритмические методы исследования операций. Тема: «Разработка программ для решения задач исследования операций в диалоговом режиме на ПК.» Вариант №: «Решение задачи о кратчайшем маршруте методом Форда.» Руководитель домашнего задания: Исполнитель: 1998 год. Содержание: 1 Постановка сетевой транспортной задачи. 3 2 Описание метода и алгоритма решения. 4 1 Составление исходной таблицы расстояний. 4 2 Определение (i и (j 4 3 Определение длинны кратчайших путей. 4 4 Нахождение кратчайшего пути. 5 3 Описание программы. 7 4 Описание подпрограмм и процедур. 8 1 Подпрограммы и функции. 8 2 Таблица идентификаторов. 9 5 Пример решения контрольной задачи. 11 6 Выводы. 12 7 Список литературы. 13 Приложение 1: Инструкция программисту и пользователю (содержимое README.TXT файла). Приложение 2: Исходный текст программы. 1. Постановка сетевой транспортной задачи. [pic] На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.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. [pic] 3. Описание программы. Программа «FORD» написана на языке высокого уровня - Pascal, в интегрированной среде разработки «Turbo Pascal 7.0» фирмы Borland Inc. Программа предназначена для нахождения кратчайшего пути в сетевом графе по методу Форда. Программа легка в использовании, что достигается за счет использования дружественного интерфейса и иерархического меню. Вначале программы производится ввод данных, затем нахождение кратчайшего маршрута и вычисление его длинны, далее выводится результат. Вывод результатов возможен как в файл, так и на экран. В программе предусмотрена возможность повторного решения задачи с другими исходными данными. 4. Описание подпрограмм и процедур. 1 Подпрограммы и функции. | | | | |ТИП |НАЗВАНИЕ |НАЗНАЧЕНИЕ | |Function |min; |Вычисляет минимальное значение вектора| |type : | |k[i]; | |real | | | |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 г.